[CFRG] Comment on AES-GCM-SST

[Yehuda Lindell <[e-mail]>]

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