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 different 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
  different messages will lead to different, 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.