Re: P1619.1: Unauthenticated data attacks

Thread Links	Date Links
Thread Prev	Thread Next	Thread Index	Date Prev	Date Next	Date Index

On Sep 28, 2006, at 5:52 AM, Doug Whiting wrote:

Let me try to clarify #2. Suppose that I'm a tape drive and I only have 1MB of buffer RAM. Suppose that there is a 16MB tape record encrypted with GCM. Clearly, if the entire record is a single GCM encryption, I cannot buffer the whole record in order to check the MAC before releasing any of the data. However, I could instead (when the record is written) break the 16MB up into, say, 8KB GCM blocks, each with its own IV and MAC. Then I can "release" 8KB of data at a time, once the GCM MAC has checked. In this case, there would be 2048 such MAC checks for the entire tape record, but there is no longer a security "hole". The buffer requirement is now only 8KB, which easily fits in my buffer. There is certainly more overhead, but at 8KB it's no more than 32/8K = 0.4%, assuming a full 16-byte IV and 16-byte MAC are added. If that amount of overhead is too high, then you could use GCM blocks of 16KB, or 32KB, etc. -- anything that fits easily into my buffer space, to cut the overhead down even further.

Does this make the idea clear?

From: David McGrew [mailto:mcgrew@cisco.com]
Sent: Thu 9/28/2006 5:00 AM
To: Doug Whiting
Cc: Hal Finney; SISWG
Subject: Re: P1619.1: Unauthenticated data attacks

Hi Doug,

On Sep 26, 2006, at 11:14 AM, Doug Whiting wrote:

I wish I were smart enough to figure out the attack. I can't, at least not yet. Maybe somebody else can. What I am saying is that it just scares me to have such a brittle MAC function combined with an allowed plaintext/keystream "early release" mechanism. Can I guarantee there will eventually be an attack based on this? No. But it does seem to me prudent to be extremely cautious about allowing this partial record "early release" feature within the spec. If an attack were to happen, it would be very painful and/or expensive for all of us, in many ways.

Remember that there ARE solutions available to this problem:

1) require implementations to buffer the whole record and check the MAC before releasing plaintext

or

that recommendation sounds good to me. I'd expect that it should be made without regard to the authenticated-encryption method, since with algorithm, there is a loss of authentication and a potential loss of confidentiality.

2) require implementations to use smaller GCM records than the tape records if they cannot comply with #1.

I'm curious: what is the benefit for using smaller blocks if there is an "early release" mechanism? If the blocks are smaller than the decrypter's buffer, then there should be no need for "early release", but if I understand right that's not what you're citing here.

David

Is #2 a pain? Yes, perhaps. But it's not really all that difficult to do, at least not if starting from scratch on a design (I realize that implementations may be well down the road). For example, suppose that an implementation broke up large tape records into 4KB or 8KB GCM blocks and checked the MAC on those blocks; this involves less than a 0.5% overhead on the tape capacity, and does not inherently limit speed. Note that #2 can clearly be done within the current spec, without allowing the early-release-plaintext "feature".

So I guess I'm torn between the lure of "easy-to-do" versus "what we really should do for security". My experience has always been that, in the long run, I always regret going with "easy-to-do" when it comes to security. If nothing else, I want to make sure we go into such a decision with our eyes wide open.

From: David McGrew [mailto:mcgrew@cisco.com]
Sent: Tue 9/26/2006 10:30 AM
To: Doug Whiting
Cc: Hal Finney; SISWG
Subject: Re: P1619.1: Unauthenticated data attacks

Thanks, Doug. I have a few more questions inline.

On Sep 26, 2006, at 5:57 AM, Doug Whiting wrote:

I don't know exactly (yet) what the attack model is. My point is that there's a difference between revealing the plaintext and revealing the MAC key value, which is what could happen here.

I don't understand how the MAC key gets revealed. It sounds to me like you are saying that there is an attack that takes advantage of decrypted data to find the GCM hash key - is that right?

It's somewhat similar to the LRW situation, where an unexpected "attack" led to revealing part of the key.

I'm not saying that GCM isn't good here. I think it's the right mode. My point is only that we have to be very, very careful in discussing consequences of allowing partial decrypted data to be seen, since it can lead to ALL FUTURE blocks being insecure w.r.t. the MAC. That's not a "feature" of CCM or HMAC, for example (or at least not anywhere nearly as trivially so).

It sounds to me like there is a need to consider blockwise adaptive attacks (like http://eprint.iacr.org/2006/271 and http://citeseer.ist.psu.edu/joux02blockwiseadaptive.html). I'm not familiar with any blockwise-adaptive attack against the message authentication component of an authenticated encryption scheme, which IIUC is what you're suggesting, but it seems natural enough. It should not be hard to show that GCM is secure against these attacks, since the hash is computed over the ciphertext and not the plaintext, so any partial decryption of the data doesn't give the attacker any new information.

I wasn't on the call yesterday, and so I didn't benefit from the discussion that took place. If I'm misunderstanding your points, please let me know.

David

From: David McGrew [mailto:mcgrew@cisco.com]
Sent: Tue 9/26/2006 5:18 AM
To: Doug Whiting
Cc: Hal Finney; SISWG
Subject: Re: P1619.1: Unauthenticated data attacks

Hi Doug,

I certainly agree that there is a potential problem in a system in which "the host may begin to act on unauthenticated data, without waiting to see if the MAC is good," as Hal put it. But this concern is generic to any MAC.

On Sep 25, 2006, at 2:26 PM, Doug Whiting wrote:

I don't have an attack offhand. I agree that careful implementations may/should be able to get it right.

However, I'm particularly concerned about GCM in this environment, because of the inherent fragility of the GHASH key. In particular, if you can get a small handful of unencrypted packets with their hash value, you can probably derive the hash key, which allows you to make trivial modifications that do not invalidate the MAC. So we have to be very, very careful here and not take a cavalier approach to this problem.

What is the particular concern with GCM? A vulnerability would only occur if a "hash value" (that is, the GHASH result that has not yet been AES-encrypted) got known to the adversary. That hash is computed over the ciphertext, and GCM is secure in a known or chosen plaintext scenario. You're suggesting that the hash value will get revealed - how could that happen?  A system that passes along decrypted messages before checking the MAC will not protect the confidentiality of the messages, but it won't give away any information on the hash key.

If I'm not understanding something about the attack model, please let me know.

David