WOTS Up
3 minutos de lectura
With the need to find post-quantum schemes, hash-based signatures are cool again.
Challenge contributed by CryptoHack
Challenge files:
Se nos da una clase llamada Winternitz que implementa un protocolo de firma basado en el hash SHA256. En realidad, WOTS significa Winternitz One-Time Signature y es un algoritmo post-cuántico de firma, que se explica perfectamente en www.codingninjas.com.
Análisis del código fuente
En primer lugar, la clase crea una lista de claves privadas:
class Winternitz:
def __init__(self, priv_seed=urandom(KEY_LEN)):
self.priv_key = []
for _ in range(KEY_LEN):
priv_seed = self.hash(priv_seed)
self.priv_key.append(priv_seed)
self.gen_pubkey()
# ...
def hash(self, data):
return hashlib.sha256(data).digest()
Llaves privadas
Como se puede ver, la primera clave privada de la lista es el hash SHA256 de un valor aleatorio de 32 bytes, pero las siguientes 31 claves privadas son el hash SHA256 de la anterior:
$$ k_{i} = \mathrm{SHA256}(k_{i - 1}) = \mathrm{SHA256}^{(i - 1)}(k_1) \quad \forall i = 2, 3, \dots, 32 $$
Claves públicas
Entonces, la clave pública se genera de manera similar:
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)
Básicamente, toma cada clave privada y hace el hash un total de $256$ veces. Por lo tanto, es casi imposible obtener las claves privadas a partir de las claves públicas, al menos con esta información.
Cifrado
El script firma un mensaje y nos da el resultado. Luego firma otro mensaje y usa esa firma para crear una clave AES que cifre la flag:
if __name__ == "__main__":
w = Winternitz()
message1 = b"WOTS Up???"
signature1 = w.sign(message1)
assert w.verify(signature1, message1)
message2 = b"Sign for flag"
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:
f.write(json.dumps({
"public_key": [s.hex() for s in w.pub_key],
"message": message1.decode(),
"signature": [s.hex() for s in signature1],
"iv": aes_iv.hex(),
"enc": encrypted.hex(),
}))
Conocemos ambos mensajes, pero solo tenemos la firma del primer mensaje.
Algoritmo de firma
El algoritmo de firma funciona de la siguiente manera:
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
Se necesita el hash del mensaje para firmar y se toman los bytes del hash (data_hash_bytes). Entonces, con cada clave privada (sig_item), se utiliza un valor hash_iters = BYTE_MAX - int_val para aplicar el hash a sig_item un total de hash_iters veces. El resultado se añade a la lista de firmas.
Como resultado, una firma para un mensaje es una lista de $32$ hashes, que corresponden a un hash iterado de cada clave privada.
Solución
Puede haber una mejor manera de resolver este reto (tal vez abordada en WOTS up 2), pero sucede que el hash SHA256 de "WOTS Up???" comienza por ff:
$ echo -n 'WOTS Up???' | sha256sum
ff3ae04c073c4d935ab9f42271795cdaf537b2c619aeedf0b92f3de17b33fd95 -
Esto significa que el primer elemento de la lista de firmas es simplemente la primera clave privada, ya que hash_iters = 255 - 255 = 0, por lo que no hay hash.
Y recordemos cómo se construyeron las claves privadas. Como tenemos la primera, podemos encontrar las $32$ claves privadas por inducción y, por lo tanto, firmar el segundo mensaje.
Flag
Una vez que tenemos la firma esperada, podemos encontrar la clave AES y obtener la flag:
$ python3 solve.py
ECSC{h4sh1ng_ch41n_r34ct1on_ff_}
El script completo se puede encontrar aquí: solve.py.