# Is the Salsa20-GCM composition secure?

AES-GCM seems to be used by everyone, but I have never seen even one post about Salsa20-GCM. Is it secure? Wikipedia mentions that GCM uses a block cipher, but also that it uses CTR mode.

I am seeking an authoritative citation that I can reference in my project documentation, but personal opinions and arguments are welcomed too.

• Strictly speaking GCM has been defined using a 128 bit block cipher, but it's easy to generalize it to any stream cipher that takes a nonce and it's be secure that way. But I see little reason to do so, since GCM only works well if you have specialized instructions, which are typically only available on CPUs which can also accelerate AES. – CodesInChaos Apr 7 '15 at 16:34
• You exclude the possibility of abandoning AES for different reasons. – ArekBulski Apr 7 '15 at 17:47
• The AES cipher is not just used for encryption in GCM. You probably would need to make some superficial changes before a stream cipher can be used (but I don't see any big problems with that). I doubt you will find an authoritative citation though (authoritative to whom?) – Maarten Bodewes Apr 7 '15 at 18:08
• A statement from Daniel Bernstein would be authoritative enough (to me), for example. – ArekBulski Apr 7 '15 at 18:14
• If you aren't using a block cipher, your result is not GCM. It might use GHASH, and might resemble GCM, but it isn't GCM. Also, GCM seems to assume the length of the counter is the length of the output from that counter; this is not true for Salsa20 (it has what amounts to 128 bits of nonce, but for 512 bits of output). – cpast Apr 7 '15 at 21:28

As SOJPM says in their answer, the proofs for AES-GCM assumes that AES is a PRP. I can't believe that there is anywhere in the proof that using a PRF (possibly truncated) would break things -- but I haven't looked carefully for this. Depending on how the GCM proof is structured, (using/not using) the PRP/PRF switching lemma [1] may suffice, but I don't remember well enough to say for certain.

I think that the closest reference you will find is [2], which analyses the ChaCha20-Poly1305 construction in IETF protocols [3]. As both ChaCha20 and Salsa20 can be assumed to be a PRF, this change is not significant; similarly GMAC and Poly1305 are fundamentally the same (a MAC based on a polynomial-evaluation hash). However, the scheme in [1] is not precisely ChaCha20-GCM; unless you want to dive into the GCM proofs (either to check that a PRF is ok at every point, or that you can use/not use the PRP/PRF lemma) I think it is the closest analysed scheme that you will find.

• I noticed the introduction of ChaCha20-Poly1305 and it made me thinking, but your link [2] to academic analysis pushed me through it. I will switch to that. – ArekBulski Apr 8 '15 at 23:14
• [2] quotes Bernstein: "There is nothing special about AES here. One can replace AES with an arbitrary keyed function from an arbitrary set of nonces to 16-byte strings." – ArekBulski Apr 8 '15 at 23:57

GCM is a specific mode for block ciphers that combines CTR encryption mode and GMAC authentication. Since Salsa and ChaCha are already based on CTR mode internally, that would not be a relevant mode.

However, there is no problem using GMAC. Salsa and ChaCha output larger blocks than GMAC accepts, so you would need to break them in the correct size chunks to process. This is already done in Poly1305 authentication, so that is not a problem.

• Wikipedia states that GCM security depends on "block cipher that is indistinguishable from a random permutation" which seems to imply any PRF but it still seems a bit vague to me. GMAC still uses AES to encrypt the authentication tag. Poly1305 is, even by DJB himself, called Poly1305-AES and it is stated that AES can be substituted with "identical security guarantee", whatever that is exactly. – ArekBulski Apr 7 '15 at 20:52
• @ArekBulski that means a cipher with a key strength at least as good as the security guarantee of the authentication, which is 128-bits. ChaCha with Poly1305 has been added as an RFC for the next version of TLS, and is already available in Google Chrome – Richie Frame Apr 8 '15 at 3:45

The only other issue may be the generation of the H value which is $E_K(0^{128})$. Here you may just use your stream-cipher will a well-defined IV (maybe derived from the normal IV using a hash-function?).