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 valorS
como número de 16 bytes - Luego, en cada cifrado, el servidor calcula un valor aleatorio
A
- Después multiplica
A
yS
usando el producto escalar (punc_prod
) para hallarb
e
es un ruido aleatorio- Si el bit es
1
, el resultado esA
yb + e
; si no,A
y un número aleatorio menor quen = 256
Learning With Errors
En términos matemáticos, podemos expresar A
y S
como vectores de números enteros de 8 bits:
Entonces, b
es solo su producto escalar:
Y si el bit para cifrar es un 1
, entonces recibimos el siguiente texto cifrado:
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
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 enporque se reduce módulo n = 256
- El valor de
e
viene denoise_prod
, que devuelverandbelow(2*self.n//3) - self.n//2
. Entonces, tenemos los siguientes límites parae
:
- Por lo tanto, el límite para
b + e
es:
- Por otro lado,
randbelow(self.n)
es un valor entero en
Como resultado, tenemos una forma de determinar si el bit es 1
: Es decir, si recibimos un valor 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
o , entonces sabemos con certeza que es un 1
y detenemos el proceso para continuar - Si ninguna de las consultas da un resultado fuera de
, 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 gopwntools
. 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
.