6 ms·

AES-GCM-SIV: Specification and Analysis [pdf]

49 points by remx 10y ago

tyingq 10y ago
Reading this first was helpful for me: https://www.lvh.io/posts/nonce-misuse-resistance-101.html https://www.lvh.io/posts/nonce-misuse-resistance-101.html
memming 10y ago
Sadly hard to read...I was away from the crypto world for too long!
bascule 10y ago
For context, this is describing an updated AES-GCM-SIV construction following a number of attacks reported by NSA earlier this year: https://mailarchive.ietf.org/arch/attach/cfrg/pdfL0pM_N.pdf https://mailarchive.ietf.org/arch/attach/cfrg/pdfL0pM_N.pdf Several cryptographers have been wary of this construction, both because of the history of attacks and also because it generally hasn't lived up to the goals of (nonce) "misuse resistant authenticated encryption" as described in the seminal Rogaway paper on the matter: https://eprint.iacr.org/2006/221.pdf https://eprint.iacr.org/2006/221.pdf It will be interesting to see more analysis on the latest version. For the intended use case (QUIC ticket encryption) it would be helpful.
- azet 10y ago
  For the record: I'm not a cryptographer. :)
tveita 10y ago
Going directly to CFRG with this kind of feels like stealing the thunder from the ongoing CAESAR competition. Unfortunately the only misuse-resistant CAESAR candidate left in the running is AEZ, according to https://aezoo.compute.dtu.dk/doku.php https://aezoo.compute.dtu.dk/doku.php.
- azet 10y ago
  yea. I don't get why HS1-SIV isn't in the next round.
  - aicez 10y ago
    Hardware performance might be the reason.
- aicez 10y ago
  This is incorrect. Deoxys also supports misuse-resistant as well. You just need to pick the right mode =).
p1mrx 10y ago
Do I understand correctly that the change from GHASH to POLYVAL is basically saying "screw tradition, let's put Little Endian on the wire"? In general, when you see Little Endian on the wire, that means someone forgot to call htonl() in their code.
- nbadg 10y ago
  I'm reading that the same, but in this case it's a performance consideration; most systems expected to use AES-GCM-SIV use little-endian order internally, and since AES is often implemented at extremely low level (including in hardware), for most real-world systems (in particular, ones where crypto is extremely performance-sensitive), it doesn't make sense to impose an extra byte reordering for a value that is only used by the encryption process itself.
runeks 10y ago
What is this used for? Stuff like file encryption?
- nbadg 10y ago
  AES-GCM-SIV is useful for applications that require some combination of: 1. A distinct message-based format (ie not streaming) 2. Protection against modified plaintext/malleable ciphertext without a separate MAC/signature construct (this protection can extend to some "attached" plaintext called "associated data") 3. Multiple entities making encrypted messages that cannot necessarily communicate with each other to negotiate safe nonces (for example, a server farm, or in distributed computing) As such, it would not be the best choice for file encryption. ----- In more detail: AES-GCM-SIV has three parts: AES, GCM, and SIV. AES is a (some might say the) choice for symmetric encryption. In general, symmetric encryption is ultimately used for any and all content that you encrypt; asymmetric encryption is used almost exclusively with other cryptographic primitives, because it is very slow in comparison (among other issues). Cryptosystems like PGP make it seem like you're using asymmetric encryption on content by going like this: asymmetric_encrypt(symmetric_key) + symmetric_encrypt(content, symmetric_key) AES, like all other "block ciphers", by definition operate on small chunks of data at a time -- in the case of AES, 128 bits. The process by which you turn the AES primitive, which can only deal with 128 bits, into something that can encrypt arbitrary-length data, is called a "block mode of operation". AES-GCM-SIV is one such block mode. GCM is one (again, some might say the) choice for "authenticated encryption with associated data", or AEAD. It is a more sophisticated construct than "simple" encryption, in that it also asserts that the ciphertext (and, optionally, some attached in-the-clear plaintext, for example, metadata) was encrypted by someone who had the symmetric key to the data. This is important, because otherwise, the ciphertext is "malleable" -- that is to say, an active attacker could modify the ciphertext without discovery by the client. This can be a big problem; an easy example why is this scenario: 1. Imagine an encrypted "on/off" boolean value for a lightbulb. Alice (client) sends True for "on" to Bob (lightbulb), and Mallory (the active attacker) intercepts the message 2. Mallory knows the format of the plaintext because she has the same kind of lightbulb. She flips the bit in the ciphertext that corresponds to the on/off value, and then transmits the modified message to Bob 3. Bob successfully decrypts the message, sees Mallory's "off" command, despite Mallory never knowing the encryption key for the message, and turns himself off GCM solves this problem in a way that is analogous to combining a MAC construct with the AES encryption, in one integrated primitive. You could do these separately, and for a long time that's what the industry standard was, but it's easy (and catastrophic) to screw up, so there's been a substantial movement towards AEAD primitives instead. Finally, SIV ("synthetic initialization vector"). GCM (and a number of other block modes) require an initialization vector, or IV. No key + IV combination can ever be used twice; if it is, the plaintext of both messages is fairly trivially recoverable. AKA, total system failure, equivalent to no encryption, etc. It is difficult to understate the severity of this; it's a really, really big deal to reuse the same key and IV combination. The problem that SIV seeks to solve is one where you have a bunch of different sources for the IV, and you can't necessarily guarantee their uniqueness. Traditionally, you would choose a random IV from a very large set of values to avoid the birthday paradox (you're basically relying on random chance to avoid reusing the IV+key, but because the selection space is so large, you're extremely confident it won't be a problem). But this doesn't always work; the linked paper gives an example of a server cluster running Google's new QUIC protocol, which would be subject to IV birthday collisions during a DDoS attack. SIV is part of a relatively new area termed "nonce reuse resistance" or "nonce misuse resistance". These constructs seek to protect against accidental IV reuse, as in the birthday collision above, by constructing the IV from the plaintext of the message. The idea is that, if you accidentally reuse the same key + IV, by definition, you must also have the same plaintext -- resulting in an identical ciphertext, which protects the contents of the message. As such, you can safely use AES in an AEAD block mode, in a stateless distributed system, without worrying about two different protocol instances accidentally reusing the same key + IV combination (which would, again, break everything). Disclaimer: this is significantly simplified for the purposes of explanation.

49 points by remx 10y ago

Reading this first was helpful for me: https://www.lvh.io/posts/nonce-misuse-resistance-101.html https://www.lvh.io/posts/nonce-misuse-resistance-101.html

memming 10y ago

Sadly hard to read...I was away from the crypto world for too long!

bascule 10y ago

For context, this is describing an updated AES-GCM-SIV construction following a number of attacks reported by NSA earlier this year: https://mailarchive.ietf.org/arch/attach/cfrg/pdfL0pM_N.pdf https://mailarchive.ietf.org/arch/attach/cfrg/pdfL0pM_N.pdf Several cryptographers have been wary of this construction, both because of the history of attacks and also because it generally hasn't lived up to the goals of (nonce) "misuse resistant authenticated encryption" as described in the seminal Rogaway paper on the matter: https://eprint.iacr.org/2006/221.pdf https://eprint.iacr.org/2006/221.pdf It will be interesting to see more analysis on the latest version. For the intended use case (QUIC ticket encryption) it would be helpful.

azet 10y ago
For the record: I'm not a cryptographer. :)

tveita 10y ago

Going directly to CFRG with this kind of feels like stealing the thunder from the ongoing CAESAR competition. Unfortunately the only misuse-resistant CAESAR candidate left in the running is AEZ, according to https://aezoo.compute.dtu.dk/doku.php https://aezoo.compute.dtu.dk/doku.php.

azet 10y ago
yea. I don't get why HS1-SIV isn't in the next round.
- aicez 10y ago
  Hardware performance might be the reason.
aicez 10y ago
This is incorrect. Deoxys also supports misuse-resistant as well. You just need to pick the right mode =).

p1mrx 10y ago

Do I understand correctly that the change from GHASH to POLYVAL is basically saying "screw tradition, let's put Little Endian on the wire"? In general, when you see Little Endian on the wire, that means someone forgot to call htonl() in their code.

nbadg 10y ago
I'm reading that the same, but in this case it's a performance consideration; most systems expected to use AES-GCM-SIV use little-endian order internally, and since AES is often implemented at extremely low level (including in hardware), for most real-world systems (in particular, ones where crypto is extremely performance-sensitive), it doesn't make sense to impose an extra byte reordering for a value that is only used by the encryption process itself.

runeks 10y ago

What is this used for? Stuff like file encryption?

nbadg 10y ago
AES-GCM-SIV is useful for applications that require some combination of: 1. A distinct message-based format (ie not streaming) 2. Protection against modified plaintext/malleable ciphertext without a separate MAC/signature construct (this protection can extend to some "attached" plaintext called "associated data") 3. Multiple entities making encrypted messages that cannot necessarily communicate with each other to negotiate safe nonces (for example, a server farm, or in distributed computing) As such, it would not be the best choice for file encryption. ----- In more detail: AES-GCM-SIV has three parts: AES, GCM, and SIV. AES is a (some might say the) choice for symmetric encryption. In general, symmetric encryption is ultimately used for any and all content that you encrypt; asymmetric encryption is used almost exclusively with other cryptographic primitives, because it is very slow in comparison (among other issues). Cryptosystems like PGP make it seem like you're using asymmetric encryption on content by going like this: asymmetric_encrypt(symmetric_key) + symmetric_encrypt(content, symmetric_key) AES, like all other "block ciphers", by definition operate on small chunks of data at a time -- in the case of AES, 128 bits. The process by which you turn the AES primitive, which can only deal with 128 bits, into something that can encrypt arbitrary-length data, is called a "block mode of operation". AES-GCM-SIV is one such block mode. GCM is one (again, some might say the) choice for "authenticated encryption with associated data", or AEAD. It is a more sophisticated construct than "simple" encryption, in that it also asserts that the ciphertext (and, optionally, some attached in-the-clear plaintext, for example, metadata) was encrypted by someone who had the symmetric key to the data. This is important, because otherwise, the ciphertext is "malleable" -- that is to say, an active attacker could modify the ciphertext without discovery by the client. This can be a big problem; an easy example why is this scenario: 1. Imagine an encrypted "on/off" boolean value for a lightbulb. Alice (client) sends True for "on" to Bob (lightbulb), and Mallory (the active attacker) intercepts the message 2. Mallory knows the format of the plaintext because she has the same kind of lightbulb. She flips the bit in the ciphertext that corresponds to the on/off value, and then transmits the modified message to Bob 3. Bob successfully decrypts the message, sees Mallory's "off" command, despite Mallory never knowing the encryption key for the message, and turns himself off GCM solves this problem in a way that is analogous to combining a MAC construct with the AES encryption, in one integrated primitive. You could do these separately, and for a long time that's what the industry standard was, but it's easy (and catastrophic) to screw up, so there's been a substantial movement towards AEAD primitives instead. Finally, SIV ("synthetic initialization vector"). GCM (and a number of other block modes) require an initialization vector, or IV. No key + IV combination can ever be used twice; if it is, the plaintext of both messages is fairly trivially recoverable. AKA, total system failure, equivalent to no encryption, etc. It is difficult to understate the severity of this; it's a really, really big deal to reuse the same key and IV combination. The problem that SIV seeks to solve is one where you have a bunch of different sources for the IV, and you can't necessarily guarantee their uniqueness. Traditionally, you would choose a random IV from a very large set of values to avoid the birthday paradox (you're basically relying on random chance to avoid reusing the IV+key, but because the selection space is so large, you're extremely confident it won't be a problem). But this doesn't always work; the linked paper gives an example of a server cluster running Google's new QUIC protocol, which would be subject to IV birthday collisions during a DDoS attack. SIV is part of a relatively new area termed "nonce reuse resistance" or "nonce misuse resistance". These constructs seek to protect against accidental IV reuse, as in the birthday collision above, by constructing the IV from the plaintext of the message. The idea is that, if you accidentally reuse the same key + IV, by definition, you must also have the same plaintext -- resulting in an identical ciphertext, which protects the contents of the message. As such, you can safely use AES in an AEAD block mode, in a stateless distributed system, without worrying about two different protocol instances accidentally reusing the same key + IV combination (which would, again, break everything). Disclaimer: this is significantly simplified for the purposes of explanation.