[CFRG] Re: Comment on AES-GCM-SST

[Yehuda Lindell <[e-mail]>]

Hi John,

Indeed, it does require the decryptor to allow repeated nonces. However, it is very hard to prevent this. The reason why the encryptor can in general prevent nonce-reuse is by choosing nonces at random. If it’s a stateful machine, then it can also increment (but this limits usability and is a pain). However, the decryptor cannot verify that a nonce has not been used without storing previous nonces which isn’t practical. In a single session, this can of course be done, but that again is very limiting, and would be hard to enforce. It is also very error prone, so wouldn’t be recommended for a stand-alone mode of operation (in contrast to within a protocol like TLS/IPsec where you can include that).

Best,

Yehuda

> On 6 May 2024, at 17:41, John Mattsson <[e-mail]> wrote:
> 
> Hi Yehuda,
>  
> Thanks for the analysis.
>  
> I have not looked into the details of solving the suggested equations but it seems like the attack idea relies on the decryption function allowing nonce reuse. I.e., the attack is not possible when GCM-SST is used in a security protocol with replay protection, which is how it is intended to be used in mobile systems and media encryption. I think the problem goes away if a requirement is added that the nonces in both the encryption and decryption function must be unique. As long as the decryption function rejects nonces that has sucessfully been decrypted before, a single forgery does not help with multi-forgery as the the subkeys from one nonce does not help the attacker to get subkeys for other nonces.
>  
> Cheers,
> John
>  
> From: CFRG <[e-mail]> on behalf of Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]>
> Date: Monday, 6 May 2024 at 15:43
> To: Yehuda Lindell <[e-mail]>, [e-mail] <[e-mail]>
> Subject: Re: [CFRG] Comment on AES-GCM-SST
> 
> I believe this attack needs to be rewritten a bit before it works.
> 
> The issue is that X is a function of the message; X is a complex function of the message.  You could recover the truncated tag (and hence some information on Q*X) for a single message, however once you switch to another message, X changes.
> 
> A more correct way of stating it is to expand T to:
>         T = Q * H * S[z-1] + Q * H^2 * S[z-2] + const
> Where the attacker modifies S[z-1], S[z-2] (the last two message blocks) and keeps everything else (other than the guessed tag) constant.  Fortunately, H^2 is a bitwise linear function of H, and so the original attack based on expanding quadratic terms still works (and once the attacker recovers H, Q for this nonce, it's game over).
> 
> On the other hand, we should remember that this O(2^40) attack involves throwing 2^40 messages at the decryptor (and the vast majority of them will be rejected as invalid).  This is considerably more difficult than, say, breaking 40 bit DES given a plaintext/ciphertext pair; we need to assume that the device under attack won't realize that, after a massive number of decryption failures, that something is up.  We might not want to make such an assumption on the application, however we should be aware of the difference between an attack that the attacker can perform on his own, and one where he needs to interact with a legitimate party...
> 
> > -----Original Message-----
> > From: CFRG <[e-mail]> On Behalf Of Yehuda Lindell
> > Sent: Sunday, May 5, 2024 9:55 AM
> > To: [e-mail]
> > Subject: [CFRG] Comment on AES-GCM-SST
> > 
> > I've taken a look at AES-GCM-SST, and have a couple of comments.
> > 
> > First, I think that I have found another attack that doesn't require nonce-
> > reuse. It has a higher complexity but as stated works without nonce reuse,
> > and provides key extraction and thus a universal forgery.
> > 
> > By the standard,
> > 
> > X = POLYVAL(H, S[0], S[1], ..., S[m + n - 1]) T = POLYVAL(Q, X XOR S[m + n]) XOR
> > M
> > 
> > The POLYVAL in computing T is a single multiplication, and so we have T = Q *
> > (X XOR S[m+n]) XOR M = Q * X + Q * S[m+n] + M
> > 
> > For the same nonce (and the attacker can always use the same nonce) and
> > same-length messages, it follows that Q * S[m+n] + M is constant, and
> > therefore it remains to learn Q * X. This is a quadratic equation with 128
> > variables and so can be rewritten as a linear equation with 128-choose-2 ~
> > 2^13 new variables.
> > 
> > Consider a 32-bit tag. In each equation with tag=0 we obtain 32=2^5 linear
> > equations. Therefore we need 2^8 such equations. Each equation takes
> > expected 2^32 queries, and therefore with expected 2^40 queries we can
> > learn the key, and from then on forge any message desired.
> > 
> > Therefore the standard doesn't meet its stated goal which is to achieve
> > forgery probabilities close to ideal. Specifically, although it should be possible
> > to forge a single message with 2^32 queries, it should not be possible to
> > obtain a universal forgery in time 2^40.
> > 
> > As a second comment, in general, I believe that a proposal for a mode of
> > operation that aims to achieve something like the above needs to have a full
> > proof of security with concrete bounds. Otherwise we can expect to cat-and-
> > mouse finding and fixing attacks, like the one described by Scott Fluhrer and
> > the one above.
> > 
> > Best,
> > 
> > Yehuda
> > _______________________________________________
> > CFRG mailing list
> > [e-mail]
> > https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailman.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C44c2f762c8074bb1b7c808dc6dd273f9%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638505997859334216%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=3WDmJA07tiAAAqpxJHxyx4Z96EueRQ1FFLlqd3vu4cU%3D&reserved=0 <https://mailman.irtf.org/mailman/listinfo/cfrg>
> 
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailman.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C44c2f762c8074bb1b7c808dc6dd273f9%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638505997859341664%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=Cub0LO4C9XjszrMOdRT0UQxxZFcS6jpBZBYrxiwjvn4%3D&reserved=0 <https://mailman.irtf.org/mailman/listinfo/cfrg>