ECDSA has the undesirable property that if a key pair reuses a nonce in a signing operation, the cryptosystem experiences catastrophic failure in the form of private key leakage. I've heard this referred to as "sudden death" cryptography. Of course the PS3 misuse of ECDSA is probably the most widely publicised incident.

One advantage of DJB-advocated cryptosystems like Ed25519 is that they lack this weakness. The Ed25519 website states that "hash function collisions do not break this system."

A perfect implementation of ECDSA will be problem free, but since implementation flaws are inevitable, it seems preferable to use cryptography without huge exposed sharp edges.

This being the case, I am puzzled by the DJB's and other's advocacy for an authentication function that exhibits "sudden death" in the event of inadvertent nonce reuse.

Is the use of Poly1305 really informed only by performance? If so, why is this so crucial? The widespread use of e.g. HMAC suggests that MAC computation costs are tenable as they are and without pressing issue. I don't understand why Poly1305 is receiving such preference when it seems so dangerous. Can someone explain this?


One particularly interesting aspect of Poly1305 is that its security is guaranteed, assuming the underlying cipher is secure. In other words, Poly1305-AES is guaranteed to be secure, as long as AES has not been broken. In the event that AES is broken, AES could be replaced with another cipher, and get a similar security guarantee.

DJB talks about his choice to use nonces in his Poly1305-AES paper:

There are several reasons that Poly1305-AES uses nonces. First, comparable protocols without nonces have security bounds that look like C(C + D)L / 2^106 rather than DL / 2^106 -- here C is the number of messages authenticated by the sender, D is the number of forgery attempts, and L is the maximum message length -- and thus cannot be used with confidence for large C. Second, nonces allow the invocation of AES to be carried out in parallel with most of the other operations in Poly1305-AES, reducing latency in many contexts. Third, most protocols have nonces anyway, for a variety of reasons: nonces are required for secure encryption, for example, and nonces allow trivial rejection of replayed messages.

| improve this answer | |
  • $\begingroup$ For what it's worth, you could use a nonce with HMAC too if you wanted. It's just not required for security. $\endgroup$ – Jack O'Connor Dec 31 '15 at 16:09
  • 1
    $\begingroup$ Actually, Poly1305 is guaranteed to be secure, assuming the underlying cipher is secure and you never reuse a nonce. edifice was asking about why adding the second condition was considered acceptable. $\endgroup$ – poncho Mar 25 '16 at 16:05

At least in the case of NaCl, Poly1305's "sudden death" properties aren't much worse than XSalsa20's. With any stream cipher, if you reuse the same stream with two messages, then the XOR of the ciphertexts gives you the XOR of the plaintexts. So your security is already ruined by nonce reuse, whether or not you rely on Poly1305.

| improve this answer | |
  • 1
    $\begingroup$ An additional factor in NaCl's use case is that a new Poly1305 key is generated for every nonce. So "sudden death" only affects messages with that nonce. $\endgroup$ – otus Dec 31 '15 at 11:09
  • $\begingroup$ For privacy we only have to worry about nonces that the sender chooses, so it's maybe not a big deal if some other nonces are compromised. But for authenticity we also need to worry about nonces that an attacker might choose, and in that sense even a single compromised nonce could allow the attacker to forge arbitrary messages with it. $\endgroup$ – Jack O'Connor Jul 17 '17 at 16:52

ECDSA based on NIST curves contain hard-coded numbers that the community find suspicious. In cryptography, the rule is to throw away the baby, the bath tube and the water when there is some doubt about chlorine origin.

DJB curve (the 2 variants ed25519 and c25519) is not based on hardcoded numbers. It is based on a modulus easy to use on standard computer architecture. The choice of c25519 is based on the fact that this curve is convenient for DH exchange, where coordinate Y is not needed. The choice of ed25519 is based on its convenience is signature scenarios, where point at infinity is not a concern in strongly unified addition formula.

SHA1 has magic numbers too, even if they are more or less vetted by the community. Poly1305 has no such magic numbers.

Speed arguments depend on implementations and optimizations.

Implementations based on flat unconditional code are more likely to be bug-free.

Computation costs IS a concern in data centers where crypto computing requirements exploded over the last years, under the pressure for privacy and security.

The problem was not to solve existing problems at a higher level (like the reuse of nonce and salt in any crypto algorithm). The problem was to create crypto function which cannot be questionned.

| improve this answer | |
  • 1
    $\begingroup$ This doesn't attempt to answer the question actually asked. It also asserts motivations of DJB that are completely unsupported. $\endgroup$ – Stephen Touset Feb 13 '15 at 1:25
  • $\begingroup$ @Stephen: the increase of interest to DJB ciphers (published since 2005, 10 years ago) started with wikileaks (only a few years ago). They have the property of "no magic number". I do not speculate on DJB motivations. $\endgroup$ – Pierre Feb 13 '15 at 3:19
  • $\begingroup$ And that has little to do with the actual question. HMAC is a provably secure construct, even assuming many kinds of broken hash function. The security of HMAC is under no doubt whatsoever by the cryptographic community. $\endgroup$ – Stephen Touset Feb 13 '15 at 4:24
  • $\begingroup$ HMAC is based on SHA-1, and SHA-1 is based on magic constants. When the community perceived that magic constants in all crypto algorithms might be cause of troubles, people turned their attention to algorithms with equivalent security levels, good academic vetting, and NO magic. This is not a claim that HMAC is b0rked and unsecure. This is not a claim that standardized ECC is unsecure following lobbying by (3 letter acronym). This is a matter of perception by the community. $\endgroup$ – Pierre Feb 13 '15 at 4:32
  • 2
    $\begingroup$ HMAC is not based on any particular hash function. In fact, any PRF may be used as the underlying primitive for an HMAC. $\endgroup$ – Stephen Touset Feb 13 '15 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.