1
$\begingroup$

From what I've read in section 5.3 of NIST 800-38D it states:

The hash subkey, denoted H, is generated by applying the block cipher to the “zero” block.

In serious crypto J.P Aumasson describes the implementation of it as H = AES(K,0) for a single block of zeros, hence no block chaining mode, hence no IV as I understand it. Therefore the mapping between H and K should be universally constant.

The book notes:

In GCM, GHASH doesn't use K directly in order to ensure that if GHASH's key is compromised, the master key K remains secret. Given K, you can get H by computing AES(K,0), but you can't recover K from that value since K acts as AES's key.

If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere? (I wanted to say rainbow table here, but that probably doesn't quite apply based on what I read in this response)

So is the strength just that storing this permutation space for later indexing is thought to be too large? Or is there more to it that what I laid out?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ fixed plaintext variable K is not always a bijection, there can be multiple K where encrypting 0 gives the same H $\endgroup$
    – Richie Frame
    Dec 6, 2017 at 14:57

2 Answers 2

Reset to default
3
$\begingroup$

In GCM, GHASH doesn't use K directly in order to ensure that if GHASH's key is compromised, the master key K remains secret.

Actually, there's not why GCM was designed the way it was (it may be an effect, but not the reason). Instead, the reasons were:

  • To allow provable security (based on the assumption that the block cipher was a secure keyed random permutation). If we used $k$ as both the block cipher key, and used as an input to compute the tag, we need to make additional assumptions on the block cipher.

  • Because of the size mismatch; $h$ is 128 bits, $k$ is (at least, for AES) is either 128, 192 or 256 bits. Yes, one could select an arbitrary section of $k$ as your $h$, however, that seems a bit, well, arbitrary...

In any case, to answer the question you did ask:

If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere?

Not really, the effort of pre-computing such a table would be at least $O(2^{128})$ operations; we believe that is infeasible for anyone, even as a one-time effort. And, generating a rainbow table doesn't decrease this effort any; it just makes the generated table smaller...

Improve this answer
$\endgroup$
2
  • $\begingroup$ A secure keyed random permutation or a secure keyed pseudorandom permutation? $\endgroup$
    – Melab
    Dec 6, 2017 at 14:22
  • 1
    $\begingroup$ @Melab: a keyed operation which is computationally indistinguishable from a random permutation $\endgroup$
    – poncho
    Dec 6, 2017 at 14:50
2
$\begingroup$

Therefore the mapping between H and K should be universally constant.

Well, no, of course not. Because $K$ is not universally constant. It is only constant for the same key. $K$ picks a permutation out of all possible permutations (for the set of keys). And therefore $K$ determines the value of $H$.

If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere? (I wanted to say rainbow table here, but that probably doesn't quite apply based on what I read in this response)

So is the strength just that storing this permutation space for later indexing is thought to be too large? Or is there more to it that what I laid out?

Yes, because you cannot pre-compute a rainbow table for things like AES keys. You cannot compute nor store a table of $2^{128}$ elements, or even a large subset of the keys.

Rainbow tables work only for limited input ranges; relatively simple passwords - for instance - are in this category.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think the word mapping was important here, I never said k was constant. Someone above made a good point that it's not always a bijection, as block size is 128bits and key size is that or greater, hence by pigeonhole it won't be 1:1, but in the case where keysize is 128bits it wouldn't be too far off. $\endgroup$
    – JoeKir
    Dec 6, 2017 at 16:51
  • $\begingroup$ There is a mapping from K to H. The order is important here because different elements of K will map to the same value within H. $\endgroup$
    – Maarten Bodewes ♦
    Dec 6, 2017 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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