Subject: [Cfrg] AES-GCM weakness

From: Jérémie Crenne <[email-masked]>
Date: Mon, 18 Jul 2011 21:46:20 +0200

Hi everybody, 

What is the feeling of the community about the recent potential AES-GCM
weakness due to weak keys ? I'm still considering the usage of AES-GCM to be
an attractive mode for hardware implementations. I'm a little bit concerned
about this since the "new" proposition described here would require
significant addition of logic.

http://eprint.iacr.org/2011/202
http://eprint.iacr.org/2011/326

Thanks,

Jérémie

---

From: David McGrew <[email-masked]>
Date: Mon, 18 Jul 2011 14:18:19 -0700

Hi Jérémie,

http://eprint.iacr.org/2011/202 provides some interesting insights  
into how polynomial hash based authentication works, but it does *not*  
describe any way of attacking GCM that improves on what was known  
before GCM was adopted.

"GCM, GHASH and Weak Keys" describes a particular way of forging a  
message, given a valid message, which works with probability of about  
n/2^128 for messages that are n*128 bits long.  Observation 1 reads:  
"Let n be a number satisfying gcd(2^128 − 1, n) = n. Blindly swapping  
Xi and Xj , where i ≡ j (mod n) will result in a successful forgery  
with probability of at least n/2^128."

This corresponds to the original security analysis, from "The Security  
and Performance of the Galois/Counter Mode (GCM) of  
Operation" (Indocrypt 2004).  Lemma 2 from that reference(GHASH is  
almost xor universal) reads: "The function GHASH is (n + 1)/2^128  
almost xor universal when its second and third inputs are restricted  
so that their lengths sum to n*128 or fewer bits ..."   Here I have  
set w=128 and l=n*128 so that the notations are similar.

The newer work does describe an optimal attack, which is interesting,  
though see also the attacks described by Ferguson in his comments to  
NIST [1], and [2].  But it does not describe a way to attack GCM that  
works with higher chance of success than was previously known.

SGCM, described in http://eprint.iacr.org/2011/326, I don't think is a  
good idea, because it shares GCM's least desirable property (a broken  
implementation that repeats IVs will give away its authentication key)  
and it is not backwards compatible with GCM.   If that algorithm is  
extended, it would be much more worthwhile to have a different method  
of encrypting the hash, as suggested by Joux (Section 5 of [3]) and as  
done by the CWC authors [4].  It might be useful to have an additional  
ECB encryption of the tag, which could be described as a post- 
processing step for GCM as it is currently specified.

regards,

David

[1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf

[2] http://eprint.iacr.org/2005/161.pdf

[3] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/Joux_comments.pdf

[4] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/cwc/cwc-spec.pdf

On Jul 18, 2011, at 12:46 PM, Jérémie Crenne wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 18 Jul 2011 15:14:17 -0700

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> David McGrew (mcgrew)
> Sent: Monday, July 18, 2011 5:18 PM
> To: Jérémie Crenne
> Cc: [email-masked]
> Subject: Re: [Cfrg] AES-GCM weakness
> 
> Hi Jérémie,
> 
> and it is not backwards compatible with GCM.

In addition, SGCM doesn't address the problem that's under discussion: that by modifying a valid n-word message, you can create a forgery with probability circa n/2^128.  The specific attack described in the paper doesn't work, however there are other ways of modifying the message that will achieve this probability with SGCM.

> If that algorithm is

That would help against accidental reuse of the nonce.  However, it doesn’t address deliberate forgery attempts (because the forger can choose not to modify the tag).

> [3]
> http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/Joux_comments.pdf
> 
> [4]
> http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/cwc/
> cwc-spec.pdf
>

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 19 Jul 2011 17:02:30 +1200

=?iso-8859-1?Q?J=E9r=E9mie_Crenne?= <[email-masked]> writes:

>weakness due to weak keys ?

GCM's problem isn't the weak keys in AES-GCM, it's that it's a KSG rather than
a standard block cipher.  It's RC4 all over again, and we're going to see the
same problems with GCM that we've already seen with RC4.  There have been
several already, and the only reason why we haven't seen more is that GCM
isn't used that much (that is, it's used in a small number of widely-deployed
applications, but hasn't become the universal algorithm of choice that RC4
was.  Once, or if, it does, we'll see exactly the same problems that plagued
RC4 throughout its effective lifetime).

Peter.

---

From: David McGrew <[email-masked]>
Date: Tue, 19 Jul 2011 06:22:46 -0700

Hi Peter,

your note seems like a good introduction for this topic.  I wrote up a  
draft describing how deterministic IVs should be generated, and  
reviewing how they are used in different protocols:

http://tools.ietf.org/html//draft-mcgrew-iv-gen-00

Comments welcome.  You have a lot of experience with the  
implementation of robust crypto software, so if you have additions or  
improvements to Section 5 that would be great.

Side note: I was somewhat surprised that I was able to write a 24 page  
document on a topic as narrow as IV generation, and your reminder to  
everyone of how important a topic it is makes me feel a bit better :-)

David

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 20 Jul 2011 03:32:36 +1200

David McGrew <[email-masked]> writes:

>I wrote up a draft describing how deterministic IVs should be generated, and

>From a quick read, it looks good, with comprehensive coverage of all the
issues.  However (and you knew there was going to be a 'however' :-), it
depends on who the target audience is.  I'm concerned that, as with advice on
the correct use of RC4, the people who will be reading this (security people)
will probably be the ones who don't need it, and those who need it (J.Random
software developer) won't be reading it, or even know that it exists.  The
problem is that CTR mode (and derived modes) don't work the way that (most)
people think they do, and as 15-odd years of RC4 have shown, user education is
unlikely to be effective in dealing with this.  Developers don't even
understand how to use IVs, with all-zero IVs being frighteningly popular when
they're forced to use a mode like CBC ("I kept getting the first 8/16 bytes
scrambled, but it's OK now, when you set the IV to zeroes everything works").
In CBC mode it's..., well not good, but also not instantly fatal like it is in
CTR mode and derived modes.

If the goal is to "fix the IV problem" then I think that the solution isn't to
try and change the users to match the encryption (RC4 has shown that that
doesn't work so well), but to change the encryption to match the users'
expectations.  So start by assuming that an all-zero IV will be used and
design defensively around that.  What we'd then need, when the cipher is used
by non-cryptographers (which is what virtually all programmers are) is CBC or
CFB instead of CTR, and GCFBM or GCBCM instead of GCM.

Getting back to the draft, it'd be nice to recommend some single standard way
of dealing with IVs (with an accompanying "AND STICK WITH IT!").  Did you
notice, in Table 1, that every single protocol that uses them has invented
their own incompatible way of handling them?  Ugh.  You can't even provide a
standard implementation ("encrypt this message with AES-GCM") because each
protocol has its own incompatible way of applying it.  This also means that,
for section 6, you're going to need test vectors not to exercise AES-GCM but
to exercise AES-GCM as used in ESP, AES-GCM as used in IKE, AES-GCM as used in
TLS, AES- GCM as used in ...

Peter.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 19 Jul 2011 15:03:32 -0700 (PDT)

> CFB instead of CTR, and GCFBM or GCBCM instead of GCM.

  Let me remind everyone of SIV mode*. It's a CTR mode derivative but is
resistant to nonce misuse. Unlike CBC, the nonce doesn't need to be
unguessable. And it even provides a strong assurance of security if
the nonce is reused.

  One of the drawbacks of CBC (as opposed to SIV) is that it does not
do authenticated encryption and something like an HMAC-xxx is required.
Now if the real problem is, as you suggest, that J.Random Software
Developer won't be reading the literature he won't know whether he should
be doing authenticate-then-encrypt or encrypt-then-authenticate or even
encrypt-and-authenticate. With SIV it's all integrated. J.Random doesn't
need to worry about any of that. And he doesn't need to worry about
whether the nonce he's supplying is random, unguessable, or deterministic.

  regards,

  Dan.

[*] http://www.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf
[*] RFC 5297

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 20 Jul 2011 19:50:07 +1200

"Dan Harkins" <[email-masked]> writes:

>unguessable. And it even provides a strong assurance of security if the nonce
>is reused.

Doesn't SIV require the entire message to be buffered, which makes it unusable
in streaming implementations?

[Checks]

Unless I've misinterpreted some part of Fig.3 and Fig.8 of RFC 5297, this
can't be used in a streaming implementation because the CMAC operation to
create the IV has to make a complete pass over the message before you can
start encrypting (this is also similar to a key-wrap mechanism that Colin
Plumb and I came up with for RFC 3211, although it'd need a tweak to use a
proper MAC for full integrity-protection, it was designed for non-expanding
512-byte disk sector encryption and dates from the early 1990s, so it predates
pretty much all of the work that newer modes and mechanisms are built on).
SIV is quite nice for something like 802.11, SRTP, DTLS, and others, but
unfortunately won't work as a general-purpose mechanism.

Are there any IP issues around SIV?

Peter.

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 20 Jul 2011 09:57:52 -0700

That is completely correct.  SIV requires two passes for the sender - but
only one pass for the recipient.

> Peter Gutmann
> Sent: Wednesday, July 20, 2011 12:50 AM
> To: [email-masked]; [email-masked]
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cfrg] request for comments on "Generation of Deterministic
> Initialization Vectors (IVs) and Nonces"
> 
> >unguessable. And it even provides a strong assurance of security if the
> >nonce is reused.
> 
> Doesn't SIV require the entire message to be buffered, which makes it
> unusable in streaming implementations?
> 
> [Checks]
> 
can't
> be used in a streaming implementation because the CMAC operation to
Plumb
> and I came up with for RFC 3211, although it'd need a tweak to use a
proper
> MAC for full integrity-protection, it was designed for non-expanding 512-
> byte disk sector encryption and dates from the early 1990s, so it predates

---

From: David Jacobson <[email-masked]>
Date: Wed, 20 Jul 2011 10:44:56 -0700

I looked at David McGrew's IV draft.  Here are some comments.

Section 5 is about implementation.  The scope is limited to 
deterministic IVs.  One of the premises is that IV generation is a 
crypto operation that needs skill and care to be correct, and should not 
be left to application developers.  Two methods are indicated:  generate 
the IV in the crypto module, and (for backward compatibility) the 
application generates the IV, but the crypto module verifies that the 
supplied IVs satisfy the requirements.  I'll address only the case of 
generating IVs in the crypto module.

If IVs are generated without a source of random numbers, then there must 
be non-volatile memory if keys last across reboots or power cycles.  Yet 
most designers of crypto modules want to stay away from as much system 
dependency as possible.   In addition, many systems do not have reliable 
non-volatile memory with sufficiently fine grain.  Suppose the system 
has just booted.  It reads the counter from a file in the file system, 
increments it, writes it back, and then encrypts and transmits the first 
message using the new counter to derive the IV.  Then power is lost or 
the system crashes.  If the writes are buffered, the new counter value 
may not have made it to the storage medium.  This illustrates that an 
entanglement between crypto and systems issues is difficult to avoid, 
and just putting the IV generation in the crypto module does not 
guarantee that everything is right.   In addition, if the crypto module 
uses the file system to store the counter, then the crypto module must 
have code to access the file system (system dependent) and there must be 
a pre-agreed file name (more system dependency), or it must be some sort 
of parameter.  In any case the file name has to be managed correctly so 
the file is not shared between different subsystems with their own 
encryption.

One minor comment is that the proposed scheme shows the IV going back to 
the application.  It is not obvious why the application needs to know 
the IV.

Finally, the draft is limited to deterministic IVs.  It might be good to 
address both deterministic and random IVs in the same document.  Since 
random numbers are already needed for crypto, there should a facility 
inside the crypto module for getting them, and using it for IV 
generation would add almost no complexity.  Addressing random IVs would 
allow you to educate the readers about the need to limit the number of 
messages to avoid collisions due to the birthday bound.

   --David Jacobson

On 7/19/2011 6:22 AM, David McGrew wrote:
> -----
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 10.0.1390 / Virus Database: 1518/3773 - Release Date: 07/18/11
>
>

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 20 Jul 2011 11:36:46 -0700 (PDT)

Hi Peter,

On Wed, July 20, 2011 12:50 am, Peter Gutmann wrote:
>> nonce

  You're correct. All the AAD and plaintext must be known prior to
invocation of the encrypt function.

> Are there any IP issues around SIV?

  Not that I know of. The inventors have made the following statement
on the subject of IP.

http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/siv/ip.pdf

  regards,

  Dan.