<- CRYPTO

Not that random

6 minutos de lectura

Se nos proporciona el código fuente del servidor en 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()

Análisis del código fuente

El servidor implementa un casino donde podemos apostar por dinero. Si tenemos suficiente, podemos usar la opción 1 para conseguir la flag (500 monedas):

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

Podemos obtener 5 monedas si nosotros, como jugadores, ganamos al servidor (perdemos 10 monedas si no ganamos…):

    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!")

El punto es ver la salida del servidor y decir si proviene de custom_hmac o impostor_hmac (usando una entrada aleatoria my_hash_input que también se muestra):

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)

Hay una opción para obtener una pista (pagando 10 monedas):

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

Esta es una forma de controlar la entrada para custom_hmac o impostor_hmac.

Obsérvese que comenzamos con 100 monedas, por lo que podemos pedir 9 pistas antes de tratar de apostar (debemos tener más de 0 monedas):

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

Solución

Podemos usar términos matemáticos para modelar custom_hmac, sea $H = \mathrm{SHA256}$. En primer lugar, esto es keyed_hash, denotada por $K$:

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

Donde $||$ significa concatenación de cadenas. Por lo tanto:

$$ \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} $$

Donde $M$ es el mensaje "Improving on the security of SHA is easy".

Dado que $\mathrm{key}$ es aleatoria, pero la función custom_hmac está compuesto por dos hashes SHA256 unidos, podemos intentar encontrar $H(\mathrm{key} ;||; M)$ mediante buy_hint y usando $M$.

No hay 100% de probabilidad de tener $H(\mathrm{key} \;||\; M)$, porque la función podría usar impostor_hmac en su lugar. Sin embargo, podemos comprar varias pistas hasta que encontremos dos valores iguales de $H(\mathrm{key} \;||\; M)$ (los 32 bytes inferiores de custom_hmac).

Tambien podemos encontrar $H(H(\mathrm{key} \;||\; M))$ usando una cadena vacía como entrada. Con esto, podemos afirmar que hemos encontrado $H(\mathrm{key} \;||\; M)$ correctamente, al hacer el hash y comparándolo con $H(H(\mathrm{key} \;||\; M))$.

Podemos hacer una pequeña prueba de concepto en 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

Muy bien, funciona. Observe cómo tenemos $K(\mathrm{key}, M)$, que es lo que necesitamos para ganar cada ronda.

Ahora, al jugar, recibiremos una entrada aleatoria $\mathrm{inp}$ y simplemente necesitamos calcular $K(K(\mathrm{key}, M), \mathrm{inp})$ y compararlo icon los 32 bits superiores de la salida $\mathrm{out}$. Si coincide, entonces el servidor usó custom_hmac; si no, entonces es impostor_hmac.

Implementación

Esta vez, estoy usando Go con mi módulo de pwntools. Con esta función, compramos 4 pistas y devolvemos el valor más común:

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

De esta manera, podemos encontrar $H(H(\mathrm{key} \;||\; M))$ y $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:]

Debemos probar que todo es correcto, porque buyHint podría dar un resultado incorrecto:

        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")
        }

En este punto, podemos jugar y ganar hasta que obtengamos 500 monedas (comenzamos desde 20 porque hemos usado un total de 8 pistas):

        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

En este punto, podemos obtener la 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

El script completo se puede encontrar aquí: solve.go.