<- CRYPTO

Not that random

6 minutes to read

We are provided with the server source code in Python:

from Crypto.Util.number import *
from Crypto.Random import random, get_random_bytes
from hashlib import sha256

def success(s):
    print(f'\033[92m[+] {s} \033[0m')

def fail(s):
    print(f'\033[91m\033[1m[-] {s} \033[0m')

MENU = '''
Make a choice:

1. Buy flag (-500 coins)
2. Buy hint (-10 coins)
3. Play (+5/-10 coins)
4. Print balance (free)
5. Exit'''

def keyed_hash(key, inp):
    return sha256(key + inp).digest()

def custom_hmac(key, inp):
    return keyed_hash(keyed_hash(key, b"Improving on the security of SHA is easy"), inp) + keyed_hash(key, inp)

def impostor_hmac(key, inp):
    return get_random_bytes(64)

class Casino:
    def __init__(self):
        self.player_money = 100
        self.secret_key = get_random_bytes(16)
    
    def buy_flag(self):
        if self.player_money >= 500:
            self.player_money -= 500
            success(f"Winner winner chicken dinner! Thank you for playing, here's your flag :: {open('flag.txt').read()}")  
        else:
            fail("You broke")
    
    def buy_hint(self):
        self.player_money -= 10
        hash_input = bytes.fromhex(input("Enter your input in hex :: "))
        if random.getrandbits(1) == 0:
            print("Your output is :: " + custom_hmac(self.secret_key, hash_input).hex())
        else:
            print("Your output is :: " + impostor_hmac(self.secret_key, hash_input).hex())

    def play(self):
        my_bit = random.getrandbits(1)
        my_hash_input = get_random_bytes(32)

        print("I used input " + my_hash_input.hex())

        if my_bit == 0:
            my_hash_output = custom_hmac(self.secret_key, my_hash_input)
        else:
            my_hash_output = impostor_hmac(self.secret_key, my_hash_input)

        print("I got output " + my_hash_output.hex())

        answer = int(input("Was the output from my hash or random? (Enter 0 or 1 respectively) :: "))

        if answer == my_bit:
            self.player_money += 5
            success("Lucky you!")
        else:
            self.player_money -= 10
            fail("Wrong!")

    def print_balance(self):
        print(f"You have {self.player_money} coins.")



def main():
    print("Welcome to my online casino! Let's play a game!")
    casino = Casino()

    while casino.player_money > 0:
        print(MENU)
        option = int(input('Option: '))

        if option == 1:
            casino.buy_flag()
                
        elif option == 2:
            casino.buy_hint()
                
        elif option == 3:
            casino.play()
                
        elif option == 4:
            casino.print_balance()
            
        elif option == 5:
            print("Bye.")
            break
        
    print("The house always wins, sorry ):")

if __name__ == '__main__':
    main()

Source code analysis

The server implements a casino where we can bet for money. If we get enough, we can use option 1 to get the flag (500 coins):

    def buy_flag(self):
        if self.player_money >= 500:
            self.player_money -= 500
            success(f"Winner winner chicken dinner! Thank you for playing, here's your flag :: {open('flag.txt').read()}")  
        else:
            fail("You broke")

We can get 5 coins if we, as players, win the server (we lose 10 coins if we don’t win…):

    def play(self):
        my_bit = random.getrandbits(1)
        my_hash_input = get_random_bytes(32)

        print("I used input " + my_hash_input.hex())

        if my_bit == 0:
            my_hash_output = custom_hmac(self.secret_key, my_hash_input)
        else:
            my_hash_output = impostor_hmac(self.secret_key, my_hash_input)

        print("I got output " + my_hash_output.hex())

        answer = int(input("Was the output from my hash or random? (Enter 0 or 1 respectively) :: "))  

        if answer == my_bit:
            self.player_money += 5
            success("Lucky you!")
        else:
            self.player_money -= 10
            fail("Wrong!")

The point is to see the server’s output and tell if it comes from custom_hmac or impostor_hmac (using a random input my_hash_input that is also shown):

def keyed_hash(key, inp):
    return sha256(key + inp).digest()

def custom_hmac(key, inp):
    return keyed_hash(keyed_hash(key, b"Improving on the security of SHA is easy"), inp) + keyed_hash(key, inp)  

def impostor_hmac(key, inp):
    return get_random_bytes(64)

There’s an option to get a hint (paying 10 coins):

    def buy_hint(self):
        self.player_money -= 10
        hash_input = bytes.fromhex(input("Enter your input in hex :: "))
        if random.getrandbits(1) == 0:
            print("Your output is :: " + custom_hmac(self.secret_key, hash_input).hex())
        else:
            print("Your output is :: " + impostor_hmac(self.secret_key, hash_input).hex())

This is a way to control the input for custom_hmac or impostor_hmac.

Notice that we start with 100 coins, so we can use 9 hints before trying to bet (balance must be greater than 0):

class Casino:
    def __init__(self):
        self.player_money = 100
        self.secret_key = get_random_bytes(16)

Solution

We can use math terms to model custom_hmac, let $H = \mathrm{SHA256}$. First of all, this is keyed_hash, denoted by $K$:

$$ K(\mathrm{key}, \mathrm{inp}) = H(\mathrm{key} \;||\; \mathrm{inp}) $$

Where $||$ stands for string concatenation. Therefore:

$$ \begin{align} \mathtt{custom\_hmac} & = K(K(\mathrm{key}, M), \mathrm{inp}) \;||\; K(\mathrm{key}, \mathrm{inp}) \\ & = H(H(\mathrm{key} \;||\; M) \;||\; \mathrm{inp}) \;||\; H(\mathrm{key} \;||\; \mathrm{inp}) \\ \end{align} $$

Where $M$ is the message "Improving on the security of SHA is easy".

Given that $\mathrm{key}$ is random, but the custom_hmac function is composed of two SHA256 hashes joined together, we can try to find $H(\mathrm{key} ;||; M)$ using buy_hint and inputing $M$.

There’s no 100% chance we get $H(\mathrm{key} \;||\; M)$, because the function might use impostor_hmac instead. However, we can buy several hints until we find two equal values $H(\mathrm{key} \;||\; M)$ (the lower 32 bytes of custom_hmac).

We can also find $H(H(\mathrm{key} \;||\; M))$ using an empty string as input. With this, we can assert that we have found $H(\mathrm{key} \;||\; M)$ correctly, by hashing it and comparing to $H(H(\mathrm{key} \;||\; M))$.

We can do a little proof of concept in Python:

$ python3 -q
>>> from Crypto.Random import random, get_random_bytes
>>> from hashlib import sha256
>>>
>>> def keyed_hash(key, inp):
...     return sha256(key + inp).digest()
...
>>> def custom_hmac(key, inp):
...     return keyed_hash(keyed_hash(key, b"Improving on the security of SHA is easy"), inp) + keyed_hash(key, inp)
...
>>>
>>> key = get_random_bytes(16)
>>>
>>> h = custom_hmac(key, b"Improving on the security of SHA is easy")
>>> print(h[:32].hex(), h[32:].hex())
b5378abce995852c7cff743f864f468ad2cb263c3bf50d1fc4c6a0469e719c93 b38bdb24edca5a1e3f33f1060088ce191422a374f28b30e159265c1c3c267373  
>>>
>>> h = custom_hmac(key, b'')
>>> print(h[:32].hex(), h[32:].hex())
0cb0d2dfca31fcde9006d870aaa3e967a646e004a59e1e3deff26b5d72fa6d81 bdfbd52f57385eceb44e12e3bf9257b1f61b52d59dd2f698b1b7c59a311f248a
>>>
>>> print(keyed_hash(key, b"Improving on the security of SHA is easy").hex())
b38bdb24edca5a1e3f33f1060088ce191422a374f28b30e159265c1c3c267373
>>>
>>> print(sha256(keyed_hash(key, b"Improving on the security of SHA is easy")).hexdigest())
0cb0d2dfca31fcde9006d870aaa3e967a646e004a59e1e3deff26b5d72fa6d81

Alright, it works. Notice how we have $K(\mathrm{key}, M)$, which is what we need to win every round.

Now, when playing, we will get a random input $\mathrm{inp}$, we simply need to compute $K(K(\mathrm{key}, M), \mathrm{inp})$ and compare it with the upper 32 bits of the output $\mathrm{out}$. If it matches, then the server used custom_hmac; if not, then it is impostor_hmac.

Implementation

This time, I am using Go with my pwntools module. With this function, we buy 4 hints and return the most common value:

func buyHint(inp []byte) []byte {
        var outs []string

        for range 4 {
                io.SendLineAfter([]byte("Option: "), []byte{'2'})
                io.SendLineAfter([]byte("Enter your input in hex :: "), []byte(pwn.Hex(inp)))  
                io.RecvUntil([]byte("Your output is :: "))
                out := strings.TrimSpace(io.RecvLineS())
                outs = append(outs, out)
        }

        counter := map[string]int{}

        for _, out := range outs {
                counter[out]++
        }

        var max string
        maxCount := 0

        for out, count := range counter {
                if count > maxCount {
                        max = out
                }
        }

        return pwn.UnHex(max)
}

With this function, we can find $H(H(\mathrm{key} \;||\; M))$ and $H(\mathrm{key} \;||\; M)$:

        io = getProcess()
        defer io.Close()

        message := []byte("Improving on the security of SHA is easy")  

        hint := buyHint([]byte{})
        hashHashKeyMessage := hint[:32]

        hint = buyHint(message)
        hashKeyMessage := hint[32:]

We must test that everything is correct, because buyHint might give a wrong result:

        hashKeyMessage := hint[32:]

        h := sha256.Sum256(hashKeyMessage)

        if !bytes.Equal(hashHashKeyMessage, h[:]) {
                pwn.Error("Try again")
        }

        h = sha256.Sum256(append(hashKeyMessage, message...))  

        if !bytes.Equal(h[:], hint[:32]) {
                pwn.Error("Try again")
        }

At this point, we can play and win until we get 500 coins (we start from 20 because we used a total of 8 hints):

        for range (500 - 20) / 5 {
                io.SendLineAfter([]byte("Option: "), []byte{'3'})
                io.RecvUntil([]byte("I used input "))
                inp := pwn.UnHex(strings.TrimSpace(io.RecvLineS()))
                io.RecvUntil([]byte("I got output "))
                out := pwn.UnHex(strings.TrimSpace(io.RecvLineS()))

                res := []byte{'1'}
                h = sha256.Sum256(append(hashKeyMessage, inp...))

                if bytes.Equal(out[:32], h[:]) {
                        res[0] = '0'
                }

                io.SendLineAfter([]byte("Was the output from my hash or random? (Enter 0 or 1 respectively) :: "), res)  

                if !strings.Contains(io.RecvLineS(), "Lucky you!") {
                        pwn.Error("Failed")
                }
        }

        io.SendLineAfter([]byte("Option: "), []byte{'1'})
        msg := io.RecvLineS()
        pwn.Success(msg[strings.Index(msg, "HTB"):])

Flag

At this point, we can get the flag:

$ go run solve.go 83.136.251.112:36321
[+] Opening connection to 83.136.251.112 on port 36321: Done
[+] HTB{#custom_Hash-based_Message_Authentication_Codes_can_be_predictable_without_knowledge_of_the_secret_key#}  
[*] Closed connection to 83.136.251.112 port 36321

The full script can be found in here: solve.go.