How much is GCM weakened by using the same MAC key $H = E_K(0^*)$ for all messages that use the same key (which is what GCM actually does) instead of using $E_K(N||0_{32})$ (which is different for each message)?

  • 1
    $\begingroup$ I'm not sure on this one, but my reasoned guess is: "allows for arbitrary forgery attacks and full key recovery". I think the re-use of this authentication key is the weak point of GCM and why nonce-re-use is so bad with GCM. But I'm not into GCM that much, so I can't give an authoritative answer. $\endgroup$ – SEJPM May 2 '16 at 18:58
  • $\begingroup$ @SEJPM no, you are thinking of $E_K(N||0_{31}1)$ which is used to encrypt the result of the hashing (by XOR). GCM actually does use the same $H$ for all messages that use a given key. $\endgroup$ – Demi May 2 '16 at 19:14
  • $\begingroup$ So you're not actually asking: "Is A weaker than B" (where everybody assumes A to be a modification of the standard B), but rather "Is A stronger than / as strong as B" (with A being the standard and B being the modification)? $\endgroup$ – SEJPM May 2 '16 at 19:19
  • $\begingroup$ @SEJPM I am asking "Is A stronger than B" where B is the standard (GCM) and A is my variation. $\endgroup$ – Demi May 3 '16 at 13:40

Under the ideal cipher model, security is not diminished by any choice of value $H = E_K(d)$ for a known value $d$, as long as none of the counter values that get encrypted to generate the encryption stream is equal to $d$. This is what "ideal cipher" means: you have no information on $E_K(x)$ for any $x$ that you have not already tried to encrypt with the same key, and that goes for all such $x$; none is beter or worse than any other. Using $d = N||0_{32}$ instead of $d = 0_{128}$ would thus not make GCM any weaker. It would not make it stronger either, for all we know, because making it "stronger" would require that we know of some weakness in GCM as it is defined nowadays; and we know of no such weakness.

Now, using $H = E_K(0_{128})$ has some implementation benefits. Namely, suppose that you want a constant-time implementation of GCM, thus without any memory access whose address depends on the data or the key (this is to avoid side-channel attacks through cache misses). On a modern PC, you will want to use specialized opcodes, but on a slightly less modern x86 CPU, or on a non-x86 architecture (e.g. ARM), you do not not necessarily have access to such facilities. Classical implementations of multiplications in $GF(2^{128})$ are either very slow, or use data-dependent table lookups, which are not constant-time. A constant-time multiplication by $H$ can be implemented relatively efficiently (at about 14 cpb) with the help of tables whose contents depend on $H$ -- but that's counting without the cost of generating these tables. If $H$ depends only on the key, not the IV, then the tables can be produced as part of the key schedule, for a much lower overhead if many messages are processed with the same key.

Thus, having an IV-dependent $H$ is not known to increase (or decrease) security, but may imply larger CPU costs in some situations. This is a good reason to have a fixed $H$, that depends on the key but not the IV.

Constant-time multiplications in $GF(2^{128})$ can also be done in other ways, but that's another story. One is to use additive Fourier transforms, which yields remarkable performance in generalized bitslicing, but only in situations where many blocks can be processed in parallel, and with a large fixed overhead. Another method is to use integer multiplications on the operands, with most bits cleared to make room for carries; this can be worthwhile if the architecture at hand offers constant-time efficient multiplications. An example of such an architecture is the very-low-power ARM Cortex M0+, where additions and multiplications have the same cost (1 cycle each).

Even then, having an IV-dependent $H$ still implies some extra work for each message, since that processing cannot be shared.

  • $\begingroup$ What about the birthday bound? AES is a PRP, not a PRF, so you leak some information that way. $\endgroup$ – Demi May 3 '16 at 4:51
  • $\begingroup$ GCM does allow for parallel processing of the multiplications up to a very large amount $\endgroup$ – Demi May 3 '16 at 4:58
  • $\begingroup$ The "ideal cipher model" means that the PRP is indistinguishable from a permutation chosen randomly and uniformly among the set of possible permutations of the input space (blocks of 128 bits). The only information you have is that two distinct inputs will yield distinct outputs; but as long as inputs are not repeated, then they are interchangeable in that respect. $\endgroup$ – Thomas Pornin May 3 '16 at 12:29

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.