Skip to content

Latest commit

 

History

History
59 lines (47 loc) · 1.82 KB

hmac_crc.md

File metadata and controls

59 lines (47 loc) · 1.82 KB
Raw

There was given following hmac function:

CRC_POLY = to_bits(65, (2**64) + 0xeff67c77d13835f7)
CONST = to_bits(64, 0xabaddeadbeef1dea)

def crc(mesg):
  mesg += CONST
  shift = 0
  while shift < len(mesg) - 64:
    if mesg[shift]:
      for i in range(65):
    mesg[shift + i] ^= CRC_POLY[i]
    shift += 1
  return mesg[-64:]

INNER = to_bits(8, 0x36) * 8
OUTER = to_bits(8, 0x5c) * 8

def hmac(h, key, mesg):
  return h(xor(key, OUTER) + h(xor(key, INNER) + mesg))

Given string "zupe zecret", that gives hmac: 0xa57d43a032feb286, task was to find hmac for a string "BKPCTF". So we need to find a key.

Let's start by rewriting hmac function a bit, "||" is concatenation:

HMAC(KEY, m) = CRC( (KEY xor O) || CRC( (KEY xor I) || m))

PRE and POST inverts are 0 in crc, so we COULD rewrite inner CRC as a polynomial mod CRC_POLY, normally it would be

M = len(m) * 8 -- length of message m in bits
CRC( (K xor I) || m) = m*x^64 + K*x^(64+M) + I*x^(64+M) mod CRC_POLY

but you need to notice, that there is CONST added right at the beginning, to the polynomial actually looks like:

CRC( (K xor I) || m) = m*x^64 + K*x^(64+M) + I*x^(64+M) + CONST mod CRC_POLY

Now we can rewrite whole HMAC as a polynomial:

HMAC(key, m) = m*x^128 + K*x^(128+M) + I*x^(128+M) + CONST*x^64 + K*x^128 + O*x^128 + CONST mod CRC_POLY

Since we know HMAC (0xa57d43a032feb286), let's move most of the things:

K*(x^(128+M) + x^128) = HMAC(key, m) - ( m*x^128 + I*x^(128+M) + O*x^128 + CONST*x^64 + CONST) mod CRC_POLY

We can calculate right side without any problems. Luckily gcd(CRC_POLY, x^(128+M) + x^128)) == 1, so our solution for key is given by:

K = (right part) * inverse( x^(128+M) + x^128 ) mod CRC_POLY

You can read more about arithmetic on wikipedia: https://en.wikipedia.org/wiki/Finite_field_arithmetic