Implement ChaCha20-Poly1305-SIV(-ish) Nonce-Misuse-Resistant AEAD

[briansmith]

[I've not thought deeply about whether this makes sense. I'm just recording it so we can start making progress on nonce-misuse-resistant AEADs.]

See #412 about adding AES-GCM-SIV. The same reasons that make ChaCha20-Poly1305 useful (vs. AES-GCM) seem to imply that a nonce-misuse-resistant variant of ChaCha20-Poly1305 is warranted.

It seems like we can generalize AES-GCM-SIV and then instantiate the generalized form with ChaCha20-Poly1305 to get a Nonce-Misuse-Resistant AEAD with similar properties, which seem like they would be better than what XChaCha20-Poly1305 (#411) would offer. Interestingly, our ChaCha20-Poly1305 code already computes ChaCha20 and Poly1305 serially, unlike (some variants of) our AES-GCM code, which interleaves them. Thus it seems like ChaCha20-Poly1305-SIV should perform at about the same speed as our ChaCha20-Poly1305 implementation. (This differs from AES-GCM-SIV vs AES-GCM on some architectures, because some AES-GCM implementations exploit the ability to compute AES-CTR and GCM in parallel.)

The AES-GCM-SIV paper already defines a generalized Cipher-Authenticator-SIV construct similar to what we need. However, the instantiation for AES-GCM doesn't map 1-to-1 to what the instantiation for ChaCha20-Poly1305 would be due to inherent differences, IIUC. However, having just read the AES-GCM-SIV draft IETF RFC and the AES-GCM-SIV paper again, it doesn't seem too hard. However, I could very well be missing something really important.

[briansmith]

Note also that many people have suggested that HS1-SIV should be considered the nonce-misuse-resistant counterpart to ChaCha20-Poly1305, in the same way as AES-GCM-SIV seems destined to be the nonce-misuse-resistant counterpart to AES-GCM. However, HS1-SIV didn't make it into the 3rd round of CAESAR and so I expect interest in it will wane, and thus it makes sense to try to define a ChaCha20-Poly1305-based construct now. However, we should make sure we understand why people suggested HS1-SIV in the first place, and in particular why some dismissed ChaCha20-Poly1305-SIV as a reasonable alternative; http://crypto.stackexchange.com/a/33080 is probably a good starting point for this.

[briansmith]

See also RIV for Robust Authenticated Encryption.

[lvh]

FWIW, I did the following in an experimental API for caesium, my libsodium wrapper:
https://github.com/lvh/caesium/blob/master/src/caesium/magicnonce/secretbox.clj

TL;DR prefix nonce in the ctext, provide a nice API where you get a random nonce by default, have a deterministic version that essentially just uses keyed BLAKE2 to generate the nonce to begin with, and then runs regular secretbox. The NMR version does both. That's slow (although not particularly; see benchmark dir), but should be safe.

Fortunately, the prefix-nonce-decryption bit is consistent, so I could e.g. use siphash for short messages; although its output is shorter than the nonce size of XSalsa20, and I haven't done any analysis on that construction.

[lvh]

@Bascule raised a valid criticism elsewhere that bears repeating: magicnonce isn't as parsimonious as it could be, involving 3 primitives. That's true (XChaCha20 might make that better by sharing internals with BLAKE2); it's important to consider the design constraint was "what's really easy to implement given that I have libsodium" not "what's really easy to implement from scratch" -- so it may not useful to take in verbatim, but might still be useful as an API design suggestion.

[tarcieri]

So if I understand it correctly, AES-SIV (and I believe also the AES-GCM-SIV construction on which @briansmith was proposing to base this) are able to authenticate the message in a single pass by using MAC-then-encrypt. However, where this would normally be frowned upon, the SIV construction retains security under the random oracle model (provided you're using a stream cipher that's free of padding oracles, I guess?)

http://web.cs.ucdavis.edu/~rogaway/papers/siv.pdf

NOTE: Hm in the diagram is a header, not a hash

[DemiMarie]

I once created my own such algorithm, based on libsodium. I don’t remember all of the details, but it went something like (pseudocode):

poly_key = hchacha20(key, nonce)
poly_mac_val = poly1305(poly_key, msg) // includes XOR
tag = hchacha20(key, poly_mac_val)
encrypted = xchacha20(key = key, nonce = tag, msg = msg)
ciphertext = (tag, encrypted)

and reverse for decryption.

I actually preferred HS1-SIV, not least because of higher authentication security (especially important in the nonce-reuse case, since it takes O(sqrt(auth-security)) before a collision occurs and security is lost).

[tarcieri]

and reverse for decryption.

Well, it's a bit more nuanced than that. With decryption you already have the synthetic IV/MAC so there's no initial pass to compute it. Instead you should be able to authenticate each block at the time it's decrypted, so ideally SIV decryption is zero overhead compared to EtM.

[DemiMarie]

True. But that's just an optimization. It doesn't change anything from a cryptographic perspective.

…

On Jul 19, 2017 10:20 PM, "Tony Arcieri" ***@***.***> wrote: and reverse for decryption. Well, it's a bit more nuanced than that. With decryption you already have the synthetic IV/MAC so there's no initial pass to compute it. Instead you should be able to authenticate each block at the time it's decrypted, so ideally SIV decryption is zero overhead compared to EtM. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#413 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGWB_A9n9qjM4SvWOE1sa76NGtReij4ks5sPrl_gaJpZM4LitW_> .

[briansmith]

There are no plans to do this as nobody is using this construction.

[tarcieri]

There was an I-D for a similar-ish construction, however it was not adopted as a CFRG work item: https://datatracker.ietf.org/doc/draft-madden-generalised-siv/

That said, it seems there is little demand for ChaCha20 SIV modes like this, especially with the upcoming (eventual?) publication of the AES-GCM-SIV RFC.