with interesting info on them dropping SSLv3 from chrome to google in an attempt to identify what is downgrading connections (which must be extra fun if you are wondering who is hiding in the noise).
I think it's an interesting idea, but I admit I'm a bit surprised at the choice of ChaCha20. The related Salsa20 algorithm has received far more public analysis and while ChaCha20 has some interesting (if minor) performance and theoretical security improvements, but they don't seem worth giving up the assurance you get from the extra review of Salsa20.
I agree that ChaCha seems like a better function (designed for faster diffusion, better block layout, etc), and it is comforting that fewer ChaCha rounds can be attacked with the same attacks that apply to Salsa. But ChaCha does still represent a substantial change in the core function from Salsa, and I do wonder if it's possible those changes introduce a problem not found in Salsa. To be honest, I really suspect the answer is no, and that ChaCha is a good choice...just surprising given the relative interest in Salsa compared to ChaCha. But maybe your choice will also spur more people to consider ChaCha for both usage and further cryptanalysis.
He is, but just for what it's worth, ChaCha20 (and Salsa20, from which it's derived) and Poly1305 aren't based on elliptic curves, and the TLS ECC features aren't based on Curve25519/Ed25519.
why does DJ Bernstein advocate using a counter for r (see section 3 of the poly1305 paper)? this RFC uses a random value (derived from the one-time key), which seems reasonable to me (i think there are 106 bits available, so you're getting a collision in 53 bits, which at 1000 connections a second is over 10^5 years).
just seems odd to go to the effort of specifying how to safely implement a counter in some detail in the paper when a random value seems fine (it's also quite possible i've misunderstood something - these are all new to me).
The paper specifies Poly1305-AES, which is a little different.
In Poly1305-AES, the point at which the polynomial is evaluated (r) is random, but the value added at the end is calculated as AES_k(nonce). Basically, AES was used to map from a counter to a secret value. It's very important that that value not be reused, because the security the system falls apart.
In my draft, I'm not using AES. Rather I use a block of ChaCha20 to generate the value to add at the end and a different r value for each message.
But there is essentially the same problem: an nonce still needs to be fed into the cipher and it must not repeat. (Additionally, repeating the nonce here breaks confidentiality too as the keystream will repeat and the attacker gets the XOR of the two plaintexts.)
TLS already has a counter for this, which is used here.
(Alternatively, some AES-GCM implementations in TLS use an 8-byte, random value as the nonce, which stands a good chance of repeating after 232 records :( )
As far as I have understood the draft in the context of my mental model of TLS, there already is a counter available for every message to prevent replay attacks. And if you get one for free then using it is definitely better than using a random number.
GHASH requires carryless multiplication of large numbers, and fast software implementations of that operation involve lookup tables, which leak memory timing.
And large lookup tables create potential performance problems for large numbers of simultaneous connections. Plus there is non-trivial per-key setup time for the GHASH tables, which hurts key agility. Both of these things tend not to be measured well in benchmarks, which makes even "fast" GCM software implementations somewhat slower in practice than might be expected.
So cache timing attacks increasing with table size? I thought the table was only for the authentication section. I guess that would be reversible to the key. Are there any papers on this?
I'm not exactly sure on the details of AES-GCM, but in general if you use secret data to influence either the data path (indexing tables), code path (branches) or timing (either branches or non-constant instructions) then your secret data should be considered compromised in a model allowing side channel attacks.
Comments
related blog post from agl: https://www.imperialviolet.org/2013/10/07/chacha20.html
with interesting info on them dropping SSLv3 from chrome to google in an attempt to identify what is downgrading connections (which must be extra fun if you are wondering who is hiding in the noise).
I think it's an interesting idea, but I admit I'm a bit surprised at the choice of ChaCha20. The related Salsa20 algorithm has received far more public analysis and while ChaCha20 has some interesting (if minor) performance and theoretical security improvements, but they don't seem worth giving up the assurance you get from the extra review of Salsa20.
The feeling seems to be that the analysis of Salsa carries to ChaCha and that ChaCha is slightly preferable: http://www.ietf.org/mail-archive/web/tls/current/msg10222.ht...
I started out with Salsa but switched because I also slight prefer ChaCha and people seemed to agree.
I agree that ChaCha seems like a better function (designed for faster diffusion, better block layout, etc), and it is comforting that fewer ChaCha rounds can be attacked with the same attacks that apply to Salsa. But ChaCha does still represent a substantial change in the core function from Salsa, and I do wonder if it's possible those changes introduce a problem not found in Salsa. To be honest, I really suspect the answer is no, and that ChaCha is a good choice...just surprising given the relative interest in Salsa compared to ChaCha. But maybe your choice will also spur more people to consider ChaCha for both usage and further cryptanalysis.
One positive is the indirect attention it has received through BLAKE and BLAKE2, where it has done extremely well.
By Google's Adam Langley. Nice. I know he's been a big supporter of DJB's curves.
He is, but just for what it's worth, ChaCha20 (and Salsa20, from which it's derived) and Poly1305 aren't based on elliptic curves, and the TLS ECC features aren't based on Curve25519/Ed25519.
why does DJ Bernstein advocate using a counter for r (see section 3 of the poly1305 paper)? this RFC uses a random value (derived from the one-time key), which seems reasonable to me (i think there are 106 bits available, so you're getting a collision in 53 bits, which at 1000 connections a second is over 10^5 years).
just seems odd to go to the effort of specifying how to safely implement a counter in some detail in the paper when a random value seems fine (it's also quite possible i've misunderstood something - these are all new to me).
The paper specifies Poly1305-AES, which is a little different.
In Poly1305-AES, the point at which the polynomial is evaluated (r) is random, but the value added at the end is calculated as AES_k(nonce). Basically, AES was used to map from a counter to a secret value. It's very important that that value not be reused, because the security the system falls apart.
In my draft, I'm not using AES. Rather I use a block of ChaCha20 to generate the value to add at the end and a different r value for each message.
But there is essentially the same problem: an nonce still needs to be fed into the cipher and it must not repeat. (Additionally, repeating the nonce here breaks confidentiality too as the keystream will repeat and the attacker gets the XOR of the two plaintexts.)
TLS already has a counter for this, which is used here.
(Alternatively, some AES-GCM implementations in TLS use an 8-byte, random value as the nonce, which stands a good chance of repeating after 232 records :( )
For anyone wondering, Cryptography in NaCl [1] goes in to some detail about the benefit of generating a per-message r vs a static r in section 9.
[1] http://cr.yp.to/highspeed/naclcrypto-20090310.pdf
2^32 I assume? 232 seems a little small :)
As far as I have understood the draft in the context of my mental model of TLS, there already is a counter available for every message to prevent replay attacks. And if you get one for free then using it is definitely better than using a random number.
How do you know the random value used by the other end is actually random, and not backdoored?
Why do people consider GCM difficult to implement in software?
(disclaimer: I worked for a company that sold a GCM implementation)
GHASH requires carryless multiplication of large numbers, and fast software implementations of that operation involve lookup tables, which leak memory timing.
And large lookup tables create potential performance problems for large numbers of simultaneous connections. Plus there is non-trivial per-key setup time for the GHASH tables, which hurts key agility. Both of these things tend not to be measured well in benchmarks, which makes even "fast" GCM software implementations somewhat slower in practice than might be expected.
My understanding is that fast implementations in software require look up tables which are susceptible to timing attacks.
OpenSSL has a GCM implementation which is very fast and I believe is not susceptible to timing attacks due to using vpclmulqdq: http://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=crypto...
You can debate whether it's a "software implementation" since it's using AESNI and PCLMULQDQ.
I think PCLMULQDQ is noncontroversial, but also considered "hardware supported".
So cache timing attacks increasing with table size? I thought the table was only for the authentication section. I guess that would be reversible to the key. Are there any papers on this?
I'm not exactly sure on the details of AES-GCM, but in general if you use secret data to influence either the data path (indexing tables), code path (branches) or timing (either branches or non-constant instructions) then your secret data should be considered compromised in a model allowing side channel attacks.
Exciting!