From a crypto challenge i have the following PMAC variant where the task is to forge a signature to fulfil a specific condition:

Preparation: in the finite Field GF(2^128) with the polynomial x^128 + x^7 + x^2 + x + 1 as modulus we generate the PMAC-L constants like that:

L(0)=AES(0) -> standard AES-128 with a random fixed key K and the all 0 plaintext as input

L(i) = L(i-1) * 2 -> for i=1..257 the actual L is just the L before multiplied by 2 (decimal)

The MAC:

  • we have a fixed block of 4096 bytes, which is filled with all 0
  • we can copy an arbitrary text/bytes of up to 4095 bytes into that block for testing
  • the block is then split into 256 * 16 byte messages and processed like

    S = 0

    for i from 1..257 do S = S + AES(L[i] + M[i-1]) (+ means here addition in GF(2), xor otherwise)

    final step: H = AES(S)

    H is the 128 bit MAC then

  • we can do 511 queries to an oracle with that setup

  • no message padding is performed, just always processing all 256 16-byte message blocks
  • the oracle gives us only the 16 byte MAC as result of those operations

The challenge:

we have to to fill that 4096 bytes bufffer in such a way that the resulting hash is the same as AES(0). Some fixed 27 chars text is copied into the start of the buffer before, the remaining space is at our disposal.

I cannot see any angle of attack for a forgery, cause the only access for results is the result after that last AES step H = AES(S). And the only input available are the message blocks.

i think its ok to assume we aim at

AES(0) === AES(S) which would result in the condition S === 0 ?

if there would be any way to know the results of single hashes like AES(L[i] + M[i-1]), one could construct a basis of a vector space, and maybe construct an arbitrary value which cancels out the result to 0 in the end - but this information is not available

I would be very glad about ANY pointer in ANY direction - thanks

PS: please dont be harsh with me when i used some mathematical terms not in the correct way

  • $\begingroup$ In the L(i) = L(i-1) * 2 step, is the multiplication in $GF(2^{128})$ or integer multiplication modulo $2^{128}$? Normally, it'd be the former, however your phraseology makes that unclear... $\endgroup$ – poncho Feb 22 at 18:14
  • $\begingroup$ its unclear yes - its a left shift by 1 bit - no clue how to express it exactly $\endgroup$ – nobody Feb 22 at 18:25
  • $\begingroup$ its like page 13 Figure 5 - without the additional steps in the end, the field description is on page 2 "preliminaries" web.cs.ucdavis.edu/~rogaway/papers/offsets.pdf $\endgroup$ – nobody Feb 22 at 18:32
  • $\begingroup$ If it is, in fact, integer multiplication modulo $2^{128}$, it's solvable. Hint: first step is to recover most of the bits of $L(0)$ via a series of queries. $\endgroup$ – poncho Feb 22 at 18:58
  • $\begingroup$ thank you for answering - i see no access to L(0) related to the last AES step AES(S) $\endgroup$ – nobody Feb 22 at 19:21

Your Answer

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

Browse other questions tagged or ask your own question.