Why is Poly1305 popular given its 'sudden death' properties?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.