**Tags:** sha256 crypto hmac

Rating: 5.0

The `h4mc.py` service essentially accepts a `message` and returns

sha256((key ⊕ message) + message)

Where ⊕ is bitwise XOR and `+` is bitwise addition

Suppose `key = 01100001` and our `message = 00000000`, then

key = 01100001

message = 00000000

key ⊕ message = 01100001

(key ⊕ message) + message = 01100001

That is `(key ⊕ message) + message = key`

So immediately we can get `sha256(key)`.

However, this is not particularly useful on it's own, as it would be computationally intractible to find the 'preimage' of the hash.

However suppose Suppose `key = 01100001` and our `message = 00000001`.

Notice how `message` matches `key` on the `0`th bit.

Then

key = 01100001

message = 00000001

key ⊕ message = 01100000

(key ⊕ message) + message = 01100001

So because the `0`th bit `message` matched the `0`th bit of `key`, `(key ⊕ message) + message = key` again.

We now have the kernel of an algorithm for inferring `key` by testing the `i`th bit of `key`.

If the `sha256` of our test of the `i`th bit is equal to `sha256(key)`, we can infer that the `i`th bit of `key` is set.

Otherwise the `i`th bit of `key` is not set.

The exploiable flaw in the toy implementation of an 'HMAC' is that the `+` should be concatenation, not bitwise addition.

`hm4c_solution.py` connects to a `hm4c.py` service, either locally or remotely, and tests each bit until the entire `key` has been inferred. View code [here](https://github.com/newjam/hm4c) and here:

```

from pwn import process, remote

from base64 import b64encode

from hashlib import sha256

from string import printable

from functools import partial

from itertools import count, islice, izip, tee, takewhile, imap

def get_digest_from_tube(io, x):

io.recvuntil('Quit\n')

io.sendline('1')

io.recvline()

io.sendline(b64encode(x))

return int(io.recvline())

def matches(get_digest):

# get the sha256 of the flag by digesting 0

key_hash = get_digest('\x00')

key = 0

for i in count():

# get sha256((flag ^ 2**i) + 2^i) from the server

digest = get_digest(from_int(2**i))

# test if the ith bit is set in the flag and it to the key if it is

if digest == key_hash:

key = key ^ 2**i

# if we have tested a multiple of 8 bits, yield the answer so far

if i % 8 == 0:

yield from_int(key)

def main():

print('Starting to pwn')

# io = remote('crypto.midnightsunctf.se', 31337)

io = process(['python', 'hm4c.py'])

get_digest = partial(get_digest_from_tube, io)

curr, prev = tee(matches(get_digest))

prev = islice(prev, 1, None)

not_equal = lambda (x, y): x != y

second = lambda (x, y): y

# keep printing the partial flag until we have found the entire flag

for x in imap(second, takewhile(not_equal, izip(curr, prev))):

print(x)

def from_int(i):

''' inverse of the to_int function on the server '''

h = hex(i)[2:]

h = h if len(h) % 2 == 0 else '0' + h

return h.decode('hex')

if __name__ == "__main__":

main()

```

Original writeup (https://github.com/newjam/hm4c).