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).