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 0th bit.
Then

key = 01100001
message = 00000001
key ⊕ message = 01100000
(key ⊕ message) + message = 01100001

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

We now have the kernel of an algorithm for inferring key by testing the ith bit of key.
If the sha256 of our test of the ith bit is equal to sha256(key), we can infer that the ith bit of key is set.
Otherwise the ith 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).