2
$\begingroup$

I would like to use GCM/GMAC in next manner:

abcd|Tag0|efgh|Tag1|ijkl|Tag2| ... |wxyz|TagN

The nuance is each tag I gonna generate is not from its last block but the all previous plain- or cipher text preceding last tag. Otherwise speaking, last tag let authenticate the whole received stream, for example:

Tag0 authentifies 'abcd'
Tag1 authentifies 'abcdefgh'
Tag2 authentifies 'abcdefghijkl'
TagN authentifies 'abcdefghijkl...wxyz'

I know that xor`ing of two tags together discards H and gives you some info about the internal cipher context.

So, my questions are:

  • Can xor`ed tags info be useful for any kind of attack?
  • What weakness does this scheme have?

Update. The full scheme of how I want to use GCM/GMAC

  • I have one randomly generated key
  • I have one randomly IV
  • I gonna encrypt and authenticate a bytestream of unknown length divided into blocks
  • After each block I gonna produce an intermediate tag that should authenticate all previous bytes of the stream
  • After intermediate tag generation, I gonna continue encryption flow further

Scheme from above with the single encryption function call may be considered as a scheme with separate calls but with the same Key, IV, and partially data.

Call 0:
'abcd'|Tag0

Call 1:
'abcdefgh'|Tag1

Call 2:
'abcdefghijkl'|Tag2

Call N:
'abcdefghijkl...wxyz'|TagN
$\endgroup$
4
$\begingroup$

Can xor`ed tags info be useful for any kind of attack?

Yup; by using the same IV for multiple generated tags, the attacker can effectively recover the internal GCM value $H$, and with that, generate tags for any arbitrary data.

(You stated that xor'ing the two tags discarded $H$; unless you are using the notation $H$ to mean something other than the secret value that the GMAC polynomial is evaluated at, this is not correct. It does discard the $Encr(IV)$ value that is exclusive-or'ed with the polynomial evaluation.

GMAC works this way: it takes a ciphertext (and AAD), formats them into a polynomial, and evaluates that polynomial at a point H. Then, it adds (xors) in a value that depends on the IV. So, to attack this, the attacker would take the two ciphertexts (and AADs), format them into the polynomials (with the tags as the constant coefficient), and then subtract (xor) those two polynomials. What he ends up with is a polynomial that he knows that evaluates to 0 at $H$; all he needs to do is find a zero of that polynomial.

That turns out to be a feasible task; in fact, with a second polynomial (which requires a third GMAC tag evaluated with the same IV), it becomes easy (the Euclidean Method over polynomials works).

This attack relies on the fact that the same IV is used for every tag; if a different IV is used (say, incrementing the IV whenever you generate a tag), this doesn't work, and it turns out to be secure.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What 2 blocks of ciphertext attacker would take? The result of my protocol is several ciphertexts sharing the same prefix (as plaintexts). If you xor ciphertext blocks corresponding to identical plaintext blocks (to discard IV-dependent part) you get 0 (yes, there`s still different tail part and tag). I understand well that your answer is true for different plaintexts with the same length. But in my case every ciphertext (as plaintext) is a predicate for the previous one, i.e. they differ in length. So, is the described attack still possible in my case? $\endgroup$ – Anatol Ivanov Feb 14 at 19:35
  • $\begingroup$ Yes, the attack is still possible. If the first tag is generated by the message 'abcd', and the second tag is generated by the message 'abcdefgh', you would subtract (exclusive-or) the polynomial corresponding to 'abcd' with the polynomial corresponding to 'abcdefgh'. These two polynomials are different, and so the xor is not 0 (that is, it is a nontrivial polynomial). And, the fact that they're different lengths is not important; the difference between the two polynomials is still well-defined (and $H$ is still a zero of the difference polynomial). $\endgroup$ – poncho Feb 14 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.