WOTS Up 2
3 minutos de lectura
I fixed the problem with my last scheme, now I can confidently sign my WOTScoin transactions.
Challenge contributed by CryptoHack
Challenge files:
Este es otro reto que implementa WOTS (más información en www.codingninjas.com).
Análisis del código fuente
La clase Winternitz es un poco diferente de la primera parte del reto, en la generación de teclas:
class Winternitz:
def __init__(self):
self.priv_key = []
for _ in range(KEY_LEN):
priv_seed = urandom(KEY_LEN)
self.priv_key.append(priv_seed)
self.gen_pubkey()
def gen_pubkey(self):
self.pub_key = []
for i in range(KEY_LEN):
pub_item = self.hash(self.priv_key[i])
for _ in range(BYTE_MAX):
pub_item = self.hash(pub_item)
self.pub_key.append(pub_item)
def hash(self, data):
return hashlib.sha256(data).digest()
Ahora, cada elemento de la lista de claves privadas es un valor aleatorio de 32 bytes. Entonces, cada elemento de la clave pública es el hash $\mathrm{SHA256}^{(256)}$ de cada elemento de la lista de claves privadas. Nuevamente, no es fácil encontrar las claves privadas a partir de las claves públicas.
Esta vez, se nos proporcionan un total de $20$ mensajes y firmas, y estamos obligados a firmar otro mensaje para construir una clave AES y descifrar la flag:
if __name__ == "__main__":
w = Winternitz()
output = {
"signatures": []
}
for i in range(20):
message = f"{w.pub_key[0].hex()} sent {int.from_bytes(urandom(1))} WOTScoins to {urandom(32).hex()}".encode()
signature = w.sign(message)
assert w.verify(signature, message)
output["signatures"].append({
"message": message.decode(),
"signature": [s.hex() for s in signature],
})
message2 = f"{w.pub_key[0].hex()} sent 999999 WOTScoins to me".encode()
signature2 = w.sign(message2)
assert w.verify(signature2, message2)
with open("flag.txt") as f:
flag = f.read().strip().encode()
aes_key = bytes([s[0] for s in signature2])
aes_iv = urandom(16)
cipher = AES.new(aes_key, AES.MODE_CBC, aes_iv)
encrypted = cipher.encrypt(flag)
with open("data.json", "w") as f:
output["public_key"] = [s.hex() for s in w.pub_key]
output["iv"] = aes_iv.hex()
output["enc"] = encrypted.hex()
f.write(json.dumps(output))
En este reto, necesitaremos explotar el algoritmo de firma, que es exactamente el mismo que antes:
def sign(self, data):
data_hash = self.hash(data)
data_hash_bytes = bytearray(data_hash)
sig = []
for i in range(KEY_LEN):
sig_item = self.priv_key[i]
int_val = data_hash_bytes[i]
hash_iters = BYTE_MAX - int_val
for _ in range(hash_iters):
sig_item = self.hash(sig_item)
sig.append(sig_item)
return sig
Rompiendo el algoritmo WOTS
Dado que WOTS significa Winternitz One-Time Signature, y tenemos $20$ firmas con la misma clave privada, debería ser factible romper el algoritmo.
La firma funciona de la siguiente manera. Tomemos el primer mensaje como ejemplo:
$ echo -n "6df32bef41a3a6242af1702da255d01baf84ebcf9a6a310d8ca90760c0579f28 sent 53 WOTScoins to 25c6c68522eec18d2f68ba962170745ff009c63f49746cefd5ff020bb1b062dc" | sha256sum
db72f2691dd68b04db5f5bb23632294d9a0c3d741ac3366ac7a11b0df5fa1847 -
El algoritmo toma cada byte del hash y hace lo siguiente:
$$ \begin{cases} h_1 = \mathrm{0xdb} &\Rightarrow 255 - \mathrm{0xdb} = 36 &\Rightarrow s_1 = \mathrm{SHA256}^{(36)}(k_1) \\ h_2 = \mathrm{0x72} &\Rightarrow 255 - \mathrm{0x72} = 141 &\Rightarrow s_2 = \mathrm{SHA256}^{(141)}(k_2) \\ h_3 = \mathrm{0xf2} &\Rightarrow 255 - \mathrm{0xf2} = 13 &\Rightarrow s_3 = \mathrm{SHA256}^{(13)}(k_3) \\ h_4 = \mathrm{0x69} &\Rightarrow 255 - \mathrm{0x69} = 150 &\Rightarrow s_4 = \mathrm{SHA256}^{(150)}(k_4) \\ \dots \\ h_{32} = \mathrm{0x47} &\Rightarrow 255 - \mathrm{0x47} = 184 &\Rightarrow s_{32} = \mathrm{SHA256}^{(184)}(k_{32}) \end{cases} $$
Recordemos que el objetivo es encontrar la firma de un mensaje dado.
El algoritmo de firma no es seguro cuando se usa varias veces. Imaginemos que queremos firmar un mensaje y el primer byte del hash SHA256 comienza con 0xda. Como ya sabemos el valor $s_1 = \mathrm{SHA256}^{(36)}(k_1)$, que corresponde a $h_1 = \mathrm{0xdb}$, si tuviéramos que firmar 0xda, solo tendríamos que aplicar el hash una vez más. Inductivamente, podríamos firmar los hashes de los mensajes que comienzan con un byte igualo menor que 0xdb, iterando hashes SHA256.
Como resultado, tomaremos el hash del mensaje que estamos obligados a firmar y buscaremos bytes altos para cada hash entre los $20$ mensajes que nos dan. Una vez que tengamos uno, podremos encontrar la firma esperada para cada byte.
Flag
Finalmente, tendremos la firma esperada y podremos construir la clave AES para descifrar la flag:
$ python3 solve.py
ECSC{0ne_m0r3_t1m3_s1gn4tur3_ff}
El script completo se puede encontrar aquí: solve.py.