Living with Elegance

6 minutos de lectura

Se nos proporciona el siguiente script en Python que cifra la flag:

from secrets import token_bytes, randbelow
from Crypto.Util.number import bytes_to_long as b2l

class ElegantCryptosystem:
    def __init__(self):
        self.d = 16
        self.n = 256
        self.S = token_bytes(self.d)

    def noise_prod(self):
        return randbelow(2*self.n//3) - self.n//2

    def get_encryption(self, bit):
        A = token_bytes(self.d)
        b = self.punc_prod(A, self.S) % self.n
        e = self.noise_prod()
        if bit == 1:
            return A, b + e
        else:
            return A, randbelow(self.n)
    
    def punc_prod(self, x, y):
        return sum(_x * _y for _x, _y in zip(x, y))

def main():
    FLAGBIN = bin(b2l(open('flag.txt', 'rb').read()))[2:]
    crypto = ElegantCryptosystem()

    while True:
        idx = input('Specify the index of the bit you want to get an encryption for : ')  
        if not idx.isnumeric():
            print('The index must be an integer.')
            continue
        idx = int(idx)
        if idx < 0 or idx >= len(FLAGBIN):
            print(f'The index must lie in the interval [0, {len(FLAGBIN)-1}]')
            continue
        
        bit = int(FLAGBIN[idx])
        A, b = crypto.get_encryption(bit)
        print('Here is your ciphertext: ')
        print(f'A = {b2l(A)}')
        print(f'b = {b}')


if __name__ == '__main__':
    main()

Análisis del código fuente

El servidor nos permite obtener el resultado de cifrado para cada bit de la flag que indiquemos:

    while True:
        idx = input('Specify the index of the bit you want to get an encryption for : ')  
        if not idx.isnumeric():
            print('The index must be an integer.')
            continue
        idx = int(idx)
        if idx < 0 or idx >= len(FLAGBIN):
            print(f'The index must lie in the interval [0, {len(FLAGBIN)-1}]')
            continue
        
        bit = int(FLAGBIN[idx])
        A, b = crypto.get_encryption(bit)
        print('Here is your ciphertext: ')
        print(f'A = {b2l(A)}')
        print(f'b = {b}')

El texto cifrado está compuesto por dos valores: A y b. Veamos cómo se calculan:

class ElegantCryptosystem:
    def __init__(self):
        self.d = 16
        self.n = 256
        self.S = token_bytes(self.d)

    def noise_prod(self):
        return randbelow(2*self.n//3) - self.n//2

    def get_encryption(self, bit):
        A = token_bytes(self.d)
        b = self.punc_prod(A, self.S) % self.n
        e = self.noise_prod()
        if bit == 1:
            return A, b + e
        else:
            return A, randbelow(self.n)
    
    def punc_prod(self, x, y):
        return sum(_x * _y for _x, _y in zip(x, y))

Cuando se instancia la clase ElegantCryptosystem, se calcula un valor S como número de 16 bytes
Luego, en cada cifrado, el servidor calcula un valor aleatorio A
Después multiplica A y S usando el producto escalar (punc_prod) para hallar b
e es un ruido aleatorio
Si el bit es 1, el resultado es A y b + e; si no, A y un número aleatorio menor que n = 256

Learning With Errors

En términos matemáticos, podemos expresar A y S como vectores de números enteros de 8 bits:

$$ A = (a_0, a_1, \dots, a_{15}) \qquad S = (s_0, s_1, \dots, s_{15}) $$

Entonces, b es solo su producto escalar:

$$ b = A \circ S = \sum_{i = 0}^{15} a_i \cdot s_i $$

Y si el bit para cifrar es un 1, entonces recibimos el siguiente texto cifrado:

$$ \begin{cases} A = (a_0, a_1, \dots, a_{15}) \\ c = A \circ S + e = b + e \end{cases} $$

Este criptosistema se conoce como Learning With Errors (LWE), y el nombre del reto es una pista. La idea detrás de este criptosistema es que es difícil recuperar la clave secreta $S$ a partir de de $A$ y $c$ porque $c$ es solo $b$ corrompido con un ruido aleatorio $e$.

Solución

Esta vez, necesitamos encontrar una manera de saber si nos han dado b + e o randbelow(self.n). Podemos hacer esto mirando los límites que estos valores pueden tomar:

Sabemos que b es un número entero en $[0, 256)$ porque se reduce módulo n = 256
El valor de e viene de noise_prod, que devuelve randbelow(2*self.n//3) - self.n//2. Entonces, tenemos los siguientes límites para e:

$$ [0, 2 \cdot 256 / 3) - 256 / 2 = [0, 170) - 128 = [-128, 42) $$

Por lo tanto, el límite para b + e es:

$$ [0, 256) + [-128, 42) = [-128, 298) $$

Por otro lado, randbelow(self.n) es un valor entero en $[0, 256)$

Como resultado, tenemos una forma de determinar si el bit es 1: Es decir, si recibimos un valor $c$ tal que $c < 0$ o $c \geqslant 256$, entonces podemos estar seguros de que vino de b + e, Entonces el bit cifrado es un 1.

Dado que tenemos consultas ilimitadas al servidor, podemos realizar un enfoque probabilístico. Por ejemplo, consultamos 30 veces para el mismo bit:

Si alguna de estas consultas decuelve $c < 0$ o $c \geqslant 256$, entonces sabemos con certeza que es un 1 y detenemos el proceso para continuar
Si ninguna de las consultas da un resultado fuera de $[0, 256)$, entonces podemos suponer con alta probabilidad que el bit cifrado es un 0

Podemos repetir este proceso para todos los bits hasta que tengamos la flag.

Implementación

Esta vez, estoy usando Go con mi módulo de pwntools. Esta es una función de ayuda para consultar al servidor en un índice de bit dado (solo devuelve el valor de texto cifrado, porque A no es relevante):

func getEncryption(index int) int {
        io.SendLineAfter([]byte("Specify the index of the bit you want to get an encryption for : "), []byte(strconv.Itoa(index)))  
        io.RecvUntil([]byte("b = "))
        c, _ := strconv.Atoi(strings.TrimSpace(io.RecvLineS()))
        return c
}

Podemos encontrar la longitud en bits de la flag (el servidor enviará un error si el índice consultado no es válido y mostrará el índice máximo) y comenzar a encontrar bits con el procedimiento anterior:

func main() {
        io = getProcess()
        defer io.Close()

        io.SendLineAfter([]byte("Specify the index of the bit you want to get an encryption for : "), []byte("10000"))  
        io.RecvUntil([]byte("The index must lie in the interval [0, "))
        bitLength, _ := strconv.Atoi(io.RecvUntilS([]byte{']'}, true))
        bitLength++

        bits := make([]int, bitLength)
        prog := pwn.Progress("Bits")

        for i := 0; i < bitLength; i++ {
                prog.Status(fmt.Sprintf("%d / %d", i+1, bitLength))

                for range 30 {
                        c := getEncryption(i)

                        if c < 0 || 256 < c {
                                bits[i] = 1
                                break
                        }
                }
        }

        prog.Success(fmt.Sprintf("%[1]d / %[1]d", bitLength))

A continuación, necesitamos aplicar un relleno para llenar bloques de 8 bits (para decodificar posteriormente):

        for len(bits)%8 != 0 {
                bits = append([]int{0}, bits...)  
        }

Finalmente, decodificamos cada bloque de 8 bits a un byte y mostramos la flag como una string:

        flag := make([]byte, len(bits)/8)

        for i := 0; i < bitLength; i += 8 {
                for j, v := range bits[i : i+8] {
                        flag[i/8] |= byte(v << (7 - j))  
                }
        }

        pwn.Success(string(flag))
}

Flag

Con este script, obtenemos la flag:

$ echo 'HTB{f4k3_fl4g_f0r_t3st1ng}' > flag.txt

$ go run solve.go
[+] Starting local process 'python3': pid 91076
[+] Bits: 215 / 215
[+] HTB{f4k3_fl4g_f0r_t3st1ng}
[*] Stopped process 'python3' (pid 91076)

$ go run solve.go 94.237.52.200:59555
[+] Opening connection to 94.237.52.200 on port 59555: Done  
[+] Bits: 175 / 175
[+] HTB{s3cur3_cust0m_LW3}
[*] Closed connection to 94.237.52.200 port 59555

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