Re: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt

[John Mattsson <[e-mail]>]

Thanks Shay,

See reply inline.

Cheers,
John

From: Shay Gueron <[e-mail]<mailto:[e-mail]>>
Date: Thursday, 19 January 2017 at 02:05
To: Adam Langley <[e-mail]<mailto:[e-mail]>>
Cc: John Mattsson2 <[e-mail]<mailto:[e-mail]>>, "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>, Shay Gueron <[e-mail]<mailto:[e-mail]>>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt

Hello everyone,


I will try to address, really briefly, two of the points raised here and deferred to me.

The definition of POLYVAL: there is an inherent discrepancy in the definition of AES-GCM. 128-bit blocks need to be viewed as polynomials, and also as 16 bytes for input/output for AES (AES is defined over bytes). The way that the polynomials are defined leads to bytes that have the reverse order of bits, compared to how AES views a bytes. I will publish a  detailed paper on this issue. For now, there is some explanation in my talk at RWC 2011 [1].
POLYVAL is defined in a way that is consistent with AES.

The other topic is why truncate the AES (throw away half of the bits) when generating per-nonce keys. The idea is to get indistinguishabilityle bounds that do not have a term that is quadratic in the number of queries (like the ones we would get if we used all of the bits). Roughly speaking the truncation gets us a term that looks like q/2^(96) instead of q^2/2^{129}. The bounds and discussion can be seen at  [2].

Asymptotically yes, but in this case we have q=2 and q=3 and any disadvantage of using a PRP should be negligible.
In fact, if the above terms were true for small q (which they are likely not) the the then quadratic term is preferable as  2^2/2^{129} = 1/2^{127} << 2/2^{96} = 1/2^{95}
Feels like doubling the amount of AES operations may be overkill and not worth the negligible security increase. GCM is popular for its performance, not for high security bounds.



Anyway an organized paper with a statement on the security bounds, is going to come out in a paper that we are working on these very days. We will post it soon.

Thank you, Shay

[1] https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf

[2] S. Gilboa, S. Gueron, “The Advantage of Truncated Permutations”,
https://arxiv.org/abs/1610.02518   (submitted on 8 Oct 2016).

2017-01-18 16:13 GMT-08:00 Adam Langley <[e-mail]<mailto:[e-mail]>>:
On Wed, Jan 18, 2017 at 1:05 PM, John Mattsson
<[e-mail]<mailto:[e-mail]>> wrote:
> - In addition to listing the performance penalty compared to GCM. The
>   draft should also mention that compared to GCM, some nice properties
>   disappear:
>   - Neither Encryption nor Decryption is online as encryption/decryption
>     cannot start before the whole plaintext/ciphertext is known.

I agree that this is true for encryption, but I don't believe that
AES-GCM should be *de*crypted in a streaming fashion, but rather that
records should be sized so that this isn't a problem. (At which point
the benefit for streaming encryption becomes small or moot.)

I've a long spiel about the dangers of processing unauthenticated
ciphertext which I'll spare you :) But, even for small machines, the
memory needed to safely buffer the decrypted plaintext to avoid
releasing it before it's authenticated is equal to the memory to
buffer the ciphertext followed by decrypting in-place.

So I actually quite like that the tag is at the end of the message
with AES-GCM-SIV because it makes it harder to do what I think is the
"wrong" thing.

>   - GCM-SIV removes the possibility to preprocess static headers (AAD).

Indeed.

(I wasn't sure where to put these points in the spec so, for the
moment, I've added an appendix for "Additional comparisons with
AES-GCM". I'm collecting changes in GitHub before making a new
version. For this message, see
https://github.com/agl/gcmsiv/commit/c6c7fd388dd122251264222b7491c6212e818319.)

> - “The result of the encryption is the resulting ciphertext (truncated
>    to the length of the plaintext) followed by the tag."
>
>   I suggest that the tag is placed first instead of last in the
>   ciphertext. This makes decryption online, which makes a large
>   difference. Suggestion:
>
>   “The result of the encryption is the tag followed by the ciphertext
>    (truncated to the length of the plaintext)"

(See above.)

>
>
> - "within 5% of the speed of AES-GCM."
>   Should state when this is the case, e.g. long plaintext/aad.

Done.

>
> - I think the draft should give performance data also for short
>   plaintexts/aad or even better list the performance in number of
>   operations:
>
>   GCM:
>     Block Cipher Operations = p + 1
>     GF(2^128) Multiplications = p + a + 1
>
>   GCM-SIV-128
>     Block Cipher Operations = p + 5
>     GF(2^128) Multiplications = p + a + 1
>
>   GCM-SIV-256
>     Block Cipher Operations = p + 7
>     GF(2^128) Multiplications = p + a + 1
>
>   (if I got it right...)

I think that's correct and I've added that to the new appendix.

>   Where p is the block length of the plaintext and a is the block length
>   of the additional authenticated data,
>
>   I doubt that encryption of short messages are anywhere near 5% of GCM.
>
> - The "++" and "[:8]" operation should probably be defined.

Done.

>
> - What it the security/performance tradeoff with truncation in the key
>   derivation? What would the security properties be if "[:8]" was
>   removed?

I'll have to let Shay answer this, but the rough idea is that, since
AES is a permutation, not two ciphertexts can be equal given that
we're encrypting different plaintexts using the KDF phase. However,
ideally we would want a PRF where outputs can be the same. By taking
only the first eight bytes of each ciphertext block, we better
approximate a PRF.

> - The definition of U32LE seems unnecessary and only adds complexity.
>   I suggest:
>     OLD "U32LE(3) ++ nonce"
>     NEW "03 ++ 000000 ++ nonce

Good point.

>
> - The term K1 is only used in Test Vectors. I guess it is an old term
>   that should be removed.

Done.

> Some editorials:

Thank you for all these. They should be taken care of.

> - OLD "The record-authentication key is 128-bit and the
>        record-authentication key"
>   NEW "The record-authentication key is 128-bit and the
>        record-encryption key"
>
> - "} else if bytelen(key-generating-key) == 32 {
>      record-encryption-key = AES128(key = key-generating-key,"
>
>   Should be AES256

Indeed, and record-authentication-key is wrong too!

> - Spacing around "+" and "*" are not consistent.
>
> - "the the"
>
> - yeilds
>
> - remainding
>
> - RFC7322 says "A comma is used before the last item of a series"

I think I've leave this one to the RFC Editor!



Cheers

AGL

_______________________________________________
Cfrg mailing list
[e-mail]<mailto:[e-mail]>
https://www.irtf.org/mailman/listinfo/cfrg