Thursday, 14 December 2017

Hash forgery

In my opinion, Hashing is one of the best invention in the field of algorithms. You can do so much with hashing, And the mathematics behind all of the hash functions are so amazing! Though it comes with a lot of risks, implementing your own hash function is very challenging. It is because there are uncountably many ways to do it incorrectly!

Hash functions have lots application, Today I will talk about key generation technique. and how to forge it. Interesting?

so, let's see first what is key generation?

def generate_key(msg):
if is_valid(msg):
return sha256(SOME_MAGIC || msg)
raise ValueError('invalid message')

def submit(key, msg):
if key != generate_key(msg)
return -1
accept(msg)
return 0

Target is to get an invalid message successfully accepted by submit procedure. You might be wondering what is the application of this.

Imagine a case, server generates a cookie and inject that in your browser, everytime you visit the website server check if cookie is valid or not. if it is valid then get data from cookies. Interesting right?

so how to forge it? Is it possible to get a invalid message accepted by the server? And Is it valid for every key generation function?

This code is vulnerable because of this line return sha256(SOME_MAGIC || msg). So what is wrong with this line? we are simply appending message to some internal magic string which is unknown to attacker and finding hash of it, even I have used this way of generating key many time when I was not so much in cryptography.

To see what is wrong with this method of hashing we need to find how sha256 works.

def sha256(msg):
""" Return the SHA-256 hash of msg as a hex string. """
# Pad the message
msg = pad_message_512(msg)
# Initialization vector
md = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
# Break msg into 512-bit chunks
view = memoryview(msg)
for chunk_num in range(0, len(msg), CHUNK_SIZE):
chunk_start = chunk_num * CHUNK_SIZE
process_chunk(md, view[chunk_start:chunk_start + CHUNK_SIZE])
# Produce the final value
return hexdigest(md)
this is my implementation of sha256

if you are not good at reading python code:
1) pad the message with zeros (roughly)
2) process message in the blocks of size 512-bits
3) return internal register values in string format

Before reading further you take your time to figure out what is wrong with that generate_key function, it should be clear by now.

So, sha256 returns the value of internal register, which gets updated after processing each chunk of 512 bits right? if I call generate_key("") it should return hash of empty message.

Assume empty string is a valid message and SOME_MAGIC hash length less than 512 bits. what you can say about key now?

Can we say key is actually internal state of sha256 after processing SOME_MAGIC || PADDING (size 512 bits). what if I know this internal state can I use it to call process_chunk again with next 512-bit block of data? ofcourse! And do I need SOME_MAGIC to know what will be hash of this new added block if I have passed it through generate_key. NO!

putting it all together
1) generate key of empty message.
2) split key into 8-internal registers
3) convert your invalid data into bits and add necessary padding
4) use 8-internal registers and your data block to generate new key.

This hack is valid on all hashing function that process data this way. So, never hash data this way. Happy Hacking!