Is using different public keys for different peers safer than reusing the public key, beyond forward secrecy?

In X25519 (ECDH over Curve25519) Peer A and B exchange their Public Keys PkA and PkB and then calculate a shared-secret SecAB using cominationOf(SkA, PkB) == combinationOf(SkB, PkA).

For forward secrecy, I think it's recommended for A and B to re-negotiate a new shared-secret regularly (thus advertise new Public Keys).

Leaving that aside is there any other disadvantage if A uses the same Public Key that they have with everyone to get corresponding shared-secret VS if they use new Public Key with each new peer ?

In other words:

1. Peer A gives PkA to all, B, C, D ..., and as usual calculates shared-secret using PkB, PkC, PkD as SecAB, SecAC, SecAD and so on and uses those to encrypt/decrypt messages to the corresponding peers.
2. Peer A gives new Public Keys to each. So PkAB to B, PkAC to C, PkAD to D and so on. Then, just like before, calculate the shared-secret after using Public Keys of the corresponding peers as SecAB, SecAC, SecAD and so on.

Is 1. above less secure in context of how X25519 (and its maths) works than 2. ? Or is it just wasteful to do 2. and 1. is equally good ?

• – kelalaka Sep 4 at 22:01

Well, as often when it comes to "practical security", the answer is: it depends.

First things first, there is nothing special about the keys or the way the maths in X25519 works that would make the one or the other more secure:

• publishing many public keys will not significantly ease the process of recovering any single secret key, although each new key decreases slightly the complexity of performing a brute-force against you.
That is: if we consider Curve25519 has a security level of 128 bits (arguably), the difficult of a bruteforce attempting to find just (any) one key out of $$n$$ keys is such that we still have an expected running time of $$2^{128}$$, which means it remains way too hard as long as you don't have more than $$2^{191}$$ public keys out there... (Because then plain enumeration is faster than Pollard's Rho, but note this value is ridiculously big.) (Also, notice I'm assuming that the SHA1 collision can be used as a reference to sets the maximum bruteforce capability of an attacker at ~64 bits nowadays, which is not really the case in practice for most attackers, but again, it could depend... if the stakes were high enough, it might be possible to reach $$2^{65}$$)

So theoretically, no problems in both cases. Which means it's a practical problem, so let's take a look around.

You already mention the forward secrecy, so leaving it aside, here are two reasons (there could be other, but nothing else comes to my mind at the moment) you might prefer to use individuals secret keys:

• anonymity: when you are relying on the same public key to speak to different peers, it is a sensible conclusion to assume that all these peers would easily agree they were talking to the same person. (Assuming no other authentication method has been used. But careful there, since unauthenticated Diffie-Hellman is prone to man-in-the-middle attacks). Whereas using different keys for different peers might provide better "segmentation" between the peers and would make correlation more difficult (notice other PI could be used, but that's not the question.)
• having different shared secret between two sessions: it is worth noticing (but it comes back to forward secrecy) that if you use the same fixed public key all the time, then whenever you're doing the X25519 operation with someone that also uses the same public key as previously, you would always get the same shared value (before key-derivation, since the derivation could have introduced a variable that changed between now and the last time, depending on what you're including during key-derivation, obviously.) You might want to avoid this, for example, to avoid having problems after you've transmitted too much data, or depending on what you are doing with that shared secret.

Finally, let me come back to forward secrecy and to scheme 3 (which I explain now):

1. whenever you initiate an X25519 key exchange, you want to first generate a new key and then use that key. So if you speak twice to party A and once to B, you would be using three different keys, one for each time you speak to someone. This is the way ephemeral Diffie-Hellman (EDH) works, and it is the best way from the security point of view.

Overall, the consensus is that EDH is the best way to do things, mostly because it provides forward secrecy, but notice it is also super important to always authenticate things such as your public key, as EDH is also prone to man-in-the-middle attacks, just like DH.

(Notice X25519 in the end is just a regular Diffie-Hellman on a specific elliptic curve, with specific encodings and details, and as such, it can be both ephemeral or fixed. )

• Agreed, I'll change it to the expected running time, so that it's clearer. – Lery Sep 12 at 9:24
• @SqueamishOssifrage I don't care about finding the first one, I just need to find any secret key corresponding to one out of $n$ public keys. I've "consumed" $n$ possible outcomes, if I have $n$ public keys and I just need to find one of the corresponding secret keys. – Lery Sep 12 at 20:53
• Oh! Wait, I have $2^{252}$ points on Ed25519, which means I'm off by quite a bit if I "just" consider a bruteforce attack. And then the best attacks against Ed25519 might not scale in the same way, indeed. I'll need to double-check the latest ECDLP advances to give an accurate estimate, there... I'm guessing it's still Pollard’s Rho, right? – Lery Sep 12 at 21:04
• Parallel $\rho$ finds one of $n$ targets (you don't get to choose which one) after about $\sqrt{\ell}$ cost, and finds all of $n$ targets after about $\sqrt{\ell \cdot n}$ cost. (Here $\ell$ is the order of the curve.) See safecurves.cr.yp.to/rho.html for some details and references, and crypto.stackexchange.com/a/59763 for commentary and references on how this is qualitatively different from a brute force attack on AES-128 even though a single-target attack cost is the same. – Squeamish Ossifrage Sep 12 at 21:08
• Tiny nit remaining: parallel $\rho$ (which I don't think I would call brute force, since it's not a generic preimage search like parallel rainbow tables, but not a big deal) can find a discrete log much faster than $2^{128}$—if I parallelize it $p$ ways, I can get an answer in time $2^{128}\!/p$. But the cost (in AT metric, which serves as a proxy for dinars) is still $2^{128}$. – Squeamish Ossifrage Sep 12 at 21:31

Generally for forward secrecy you should not just limit the use of the private key (and thus public key) in time, but also per connection. For that reason, you can assume that in most implementations that require forward secrecy that there will be one ephemeral key pair per connection, not per time frame.

Similarly, you're assuming that a new key pair is generated regularly, but please note that this kind of wording may be interpreted as once in a certain time frame. It makes a lot of difference how much the key is actually used within that particular time frame. So I think in your scheme you're using the private keys too much (you could tie that to forward secrecy, but you haven't made is explicit that you did see this tie to PFS).

One of the big disadvantages of your scheme is that the delivery of the public keys is required for each party. Some parties actually may not be active at all, and therefore distribution of the keys would be waste full. It also means that there must a central distribution point, which could wreak havoc in a distributed design.

Possibly you should simply exchange public keys each time you want to generate a new symmetric key, tying the validity of the private key to the symmetric key. How long you want to keep that symmetric key active is another matter. I'd say you could keep it active for a certain amount of actions within a specific time frame; having two rather than one limit for invalidating key pair and generating new ones. I'd certainly do that for each connection separately as indicated in the first section.

• Thanks for the info about the forward secrecy. The rest of your answer doesn't seem to answer the question. I'm mainly interested in if 1. is worse than 2. due to something inherent. I don't really care about the external factor of how the distribution works etc. That is orthogonal to the question. I could exchange keys at some point when peers are online etc. That is system design problem. This is more about if reusing a public key is know to be less secure than using different public keys with the same set of peers. – ustulation Sep 4 at 14:41
• Sorry, but as nothing other than the key pair changes, then what is your actual question? Obviously if you reuse the same key pair then you must make sure that the key agreement is not deterministic (i.e. introduce a nonce) but otherwise the security should indeed be the same. Is that enough of an answer for you? I feel you're trying to have an answer to your question while the basics are currently not covered. – Maarten Bodewes Sep 4 at 14:45
• check the other answer from @Lery - esp the theoretical part they discuss – ustulation Sep 4 at 14:50
• Fine, but that basically states that reusing ECDH is secure, something that should be considered a pre-requisite. Otherwise it comes to the same conclusions. – Maarten Bodewes Sep 4 at 14:55
• Ah, no, lets leave it at this. You've got your answer (which I already upvoted of course) and you've been informed about the issues when it comes to reusing key pairs. I'll leave my answer simply because it words some things differently than the accepted one - in other words I think it offers a different viewpoint. – Maarten Bodewes Sep 4 at 15:07