# Security benefits of Ed25519 generating signatures deterministically

I am reading on the Ed25519 curve, and I am trying to understand a claim. Here is the claim:

Foolproof session keys. Signatures are generated deterministically; key generation consumes new randomness but new signatures do not. This is not only a speed feature but also a security feature, directly relevant to the recent collapse of the Sony PlayStation 3 security system.

Does that mean a node or device in the system will have its own unique key? (The Sony PlayStation 3 reference is confusing me).

Since Curve22519 is Diffie-Hellman based, does that mean a Ed25519 curve simply assigns a different base point on the curve? (And derives the public point from a serial number or other hardware characteristic).

Its also not clear to me why a "fast" verification is needed in this case. It seems to me it should not matter how fast (or slow) a node or device is when verifying a signature since its not a frequent operation.

The paper itself has more details on this:

ECDSA, like many other signature systems, asks users to generate not merely a random long-term secret key, but also a new random secret session key $r$ for each message to be signed. ... If the same value r is ever used for 2 diff erent messages the secret key can be computed as well, as ElGamal... It was reported in [24] that the latter failure had occurred in Sony's ECDSA implementation for code-signing for the PlayStation3, immediately revealing Sony's long-term secret key.

As is also mentioned in that section, but to avoid me quoting the TeX, actually knowing $r$ lets you recover the key directly - you don't actually need two messages using the same $r$, although as I understand it the PS3 hack used two messages.

Since Curve22519 is Diffie-Hellman based

I think there's a slight confusion there. I believe the origin of Curve25519 was for use with ECDH,but:

Curve25519 is just an elliptic curve - that is, a curve of the form $x^2 = y^3 + ax^2 +b$. Curve 25519 is just a specific set of parameters $a,b$, as opposed to nistp-521, which is again just a different set of parameters. See Curve25519,

You can perform any group operation over a rational points on an elliptic curve (it turns out they form a group) so you can perform DH in elliptic curves. You can also perform DSA, hence ECDSA, ECDH (DSA, DH over EC).

This is the beauty of algebraic number theory :)

In this paper they are concerned with signature verification, hence the use of DSA.

EdDSA avoids these issues by generating $r=H(h_b, \ldots, h_{2b-1}, M)$ so that diff erent messages will lead to diff erent, hard-to-predict values of r. No per-message randomness is consumed ...

From this it sounds like they're taking a hash of the message and the key (the $h_b$) and using this to derive the per-message secret (hence determinism - it is directly related to the message).

At first glance, this looks a little insecure since knowing the message and assuming a relatively short key length you could potentially compute the inverses of the hash using a rainbow table. However, bear in mind $r$ is supposed to be secret too - knowing $r$ breaks DSA.

I can't comment on its security beyond that as I am not qualified to - someone with far deeper knowledge of DSA would have to say something - but the authors are all well respected cryptographers.

ts also not clear to me why a "fast" verification is needed in this case. It seems to me it should not matter how fast (or slow) a node or device is when verifying a signature since its not a frequent operation.

I think it depends really. If you have an embedded device, which I believe is the target here, a lower clock speed (and fewer cores) makes any verification more costly. If you go as far as say smartcards, then fast verification is desirable. Likewise, if you are producing for example a HSM or any other dedicated, embedded cryptographic device you might be concerned about performance.

• "I think there's a slight confusion there.... Diffie-Hellman" - yes, poorly worded. – jww May 5 '14 at 13:51
• @noloader no worries. I wasn't sure so I clarified just in case - you never know. – user46 May 5 '14 at 13:51
• Obviously if the signature is deterministic then the signature will leak information about the message that was signed. Normally not an issue, but it is wise to keep this in mind (e.g. RSA-PSS does use the output of a RNG to pad the message, giving distinct signatures for each operation). – Maarten Bodewes May 6 '14 at 0:39
• The points on the elliptic curve form a group, not a field. (A group has just one operation. A field has two operations.) Each point on the elliptic curve consists of an x and a y coordinate. The values of x and y are chosen from a field, typically the integers modulo a prime number. – Brock Hansen May 6 '14 at 22:51
• @Brock thanks, yes, I am not sure why I left 'actually a field' in there. Thanks for pointing that out! – user46 May 6 '14 at 23:22