Is the Salsa20-GCM composition secure?

Question

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 07 '15 at 16:34
You exclude the possibility of abandoning AES for different reasons. — ArekBulski, Apr 07 '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 07 '15 at 18:08
A statement from Daniel Bernstein would be authoritative enough (to me), for example. — ArekBulski, Apr 07 '15 at 18:14
why would you want to use Salsa and not ChaCha? AND I answered your question, but I don't recommend implementing it if anyhow possible. — SEJPM, Apr 07 '15 at 19:32
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 07 '15 at 21:28
Could you detail your construction ? What do you mean with Salsa20-GCM ? Are you encrypting with Salsa ? And what are you doing with GCM ? Where does the GCM key come from ? — Ruggero, Apr 08 '15 at 07:24

score 3 · Accepted Answer · edited Oct 07 '21 at 07:24

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.

[1] https://eprint.iacr.org/2004/331

[2] https://eprint.iacr.org/2014/613

[3] https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-chacha20-poly1305-10

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 08 '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 08 '15 at 23:57

score 1 · Answer 2 · answered Apr 07 '15 at 20:22

1

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.

answered Apr 07 '15 at 20:22

Richie Frame

13,097
1
25
42

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 07 '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 08 '15 at 03:45

score 0 · Answer 3 · answered Apr 07 '15 at 19:31

I'm pretty sure there are no papers about this.
I'm also pretty sure that no of the well-known cryptographers (Bernstein, Fergueson, Schneier, ...) will answer here.
However I can provide you an answer that is very likely to be correct.

FIRST: this is a severe abuse of the GCM construction and should be avoided if anyhow possible, use any of the other AES-finalists if you don't trust AES and there's no reason at the moment to do so. Even more you'd need to write your own GCM-implementation or modify an existing one which may be avoided if possible.

Now the answer:
Yes, you can use a streamcipher with slight modifications instead of CTR-Mode.
In this specification you'll find two nice pictures that show how GCM is working. You'll see that there's a counter that will be incremented with every call and then encrypted and used as an XOR-pad. This is basically how any standard stream cipher is used.
Hence using a stream cipher should work if you replace the whole CTR-Mode construction appropiately and should be secure as the stream cipher is used as intended.
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?).

With abuse is meant, that GCM was never designed to be used with a stream-cipher but only with a blockcipher (->AES) and hence I see it as an "abuse" — SEJPM, Apr 07 '15 at 21:27
@Arek The proofs assume a PRP. They use the fact that a PRP acts like a PRF with small inputs, but they are in fact premised on the function used being a pseudorandom permutation. A stream cipher is not a permutation, pseudorandom or otherwise. — cpast, Apr 07 '15 at 21:27

Is the Salsa20-GCM composition secure?

3 Answers3

Linked