I'm gRoot
6 minutos de lectura
Se nos proporciona el código fuente en Python de un servidor:
server.py:
from pymerkle import InmemoryTree as MerkleTree
from hashlib import sha256
from os import urandom
from secret import FLAG
from utils import *
class Transaction:
def __init__(self, _from, _to):
self._from = _from
self._to = _to
self._signature = self.getSignature(self._from, self._to)
def signature(self):
return self._signature
def getSignature(self, _from, _to):
return sha256(_from + _to).digest()
class Block:
def __init__(self):
self._transactions = []
def transactions(self):
return self._transactions
def add(self, transaction):
self._transactions.append(transaction)
class BlockChain:
def __init__(self):
self._mined_blocks = []
def initialize(self):
for _ in range(3):
block = Block()
for _ in range(8):
transaction = Transaction(urandom(16), urandom(16))
block.add(transaction)
self.mine(block)
def mined_blocks(self):
return self._mined_blocks
def size(self):
return len(self._mined_blocks)
def mine(self, block):
self.mt = MerkleTree(security=False)
for transaction in block.transactions():
self.mt.append(transaction.signature())
root_hash = self.mt.get_state()
self._mined_blocks.append({
"number": len(self._mined_blocks),
"transactions": block.transactions(),
"hash": root_hash.hex()
})
def valid(self, _signatures):
_mt = MerkleTree(security=False)
for _signature in _signatures:
_mt.append(_signature)
if self.mt.get_state() == _mt.get_state():
return True
return False
def main():
blockchain = BlockChain()
blockchain.initialize()
mined_blocks = blockchain.mined_blocks()
while True:
menu()
choice = input("> ")
if choice == "1":
print_mined_blocks(mined_blocks)
elif choice == "2":
# 1. Provide the forged signatures of the last block.
_signatures = input("Forged transaction signatures: ")
# 2. Test if the signatures are different from the provided ones.
signatures = extract_signatures(mined_blocks[-1]["transactions"])
_signatures = evaluate_signatures(_signatures, signatures)
# 3. Test if the signatures you gave generate the same root hash.
if blockchain.valid(_signatures):
print(FLAG)
exit(0)
else:
print("Try again")
else:
print("Good Bye")
exit(0)
if __name__ == "__main__":
main()
utils.py:
def menu():
print("[1] Explore mined blocks")
print("[2] Forge the last block")
def extract_signatures(transactions):
return [transaction.signature() for transaction in transactions]
def hexify(elements):
return [element.hex() for element in elements]
def unhexify(elements):
return [bytes.fromhex(element) for element in elements]
def print_mined_blocks(mined_blocks):
for block in mined_blocks:
print(f"Block: {block['number']}")
print(f"Hash: {block['hash']}")
print(f"Transactions: {hexify(extract_signatures(block['transactions']))}")
print()
def evaluate_signatures(_signatures, signatures):
try:
_signatures = _signatures.split(",")
_signatures = unhexify(_signatures)
if _signatures == signatures:
print(f"Signatures are the same.")
exit(0)
except Exception as e:
print(f"Something went wrong {e}")
exit(0)
return _signatures
Análisis del código fuente
El reto crea unas transacciones en una especie de Blockchain con un Árbol de Merkle. El objetivo de este reto es falsificar firmas de transacciones para que obtengamos la misma raíz:
if choice == "1":
print_mined_blocks(mined_blocks)
elif choice == "2":
# 1. Provide the forged signatures of the last block.
_signatures = input("Forged transaction signatures: ")
# 2. Test if the signatures are different from the provided ones.
signatures = extract_signatures(mined_blocks[-1]["transactions"])
_signatures = evaluate_signatures(_signatures, signatures)
# 3. Test if the signatures you gave generate the same root hash.
if blockchain.valid(_signatures):
print(FLAG)
exit(0)
else:
print("Try again")
else:
print("Good Bye")
exit(0)
El código fuente puede parecer demasiado largo, pero es fácil de entender. La Blockchain se inicializa con tres bloques, cada uno de ellos con ocho transacciones:
class BlockChain:
def __init__(self):
self._mined_blocks = []
def initialize(self):
for _ in range(3):
block = Block()
for _ in range(8):
transaction = Transaction(urandom(16), urandom(16))
block.add(transaction)
self.mine(block)
Cada uno de los bloques se mina:
def mine(self, block):
self.mt = MerkleTree(security=False)
for transaction in block.transactions():
self.mt.append(transaction.signature())
root_hash = self.mt.get_state()
self._mined_blocks.append({
"number": len(self._mined_blocks),
"transactions": block.transactions(),
"hash": root_hash.hex()
})
Aquí tenemos una pista de lo que necesitamos lograr. Como security=False en el constructor de MerkleTree, podemos investigar las consecuencias de esto. Hay un issue en GitHub que dice que es vulnerable a un ataque de segunda preimagen.
Árbol de Merkle
Un Árbol de Merkle se construye de la siguiente manera:
Fuente: https://en.wikipedia.org/wiki/Merkle_tree
En nuestro caso, bloque es un Árbol de Merkle, comenzado a partir de 8 transacciones. Los 8 nodos hoja son el hash SHA256 de las firmas de cada transacción. La segunda fila está compuesta por 4 nodos que son el hash SHA256 de la concatenación de dos nodos hijo. La tercera fila está compuesta por 2 nodos. Y finalmente tenemos el nodo raíz.
Tomemos un ejemplo del servidor:
$ nc 94.237.63.83 59020
[1] Explore mined blocks
[2] Forge the last block
> 1
Block: 0
Hash: e0ad19eef177ca9b5cbbd38f87147fd1258b7e8562d4c813ef5409b257b09bd6
Transactions: ['1c6e1b8c366fcc78f18b8256f5c005089716baef4d3ecb779b178f93ad98a3a9', '157ca6ef30415dac2905f216e5d0861e426a1a453bdf4f6e1ae941a373a77db9', 'a0fc805c702107349facf8c837b0a009602e0a573ab31e62ec8721139eac95f6', 'ffa7108a484b1a13e0fd18a95c8b2a671156f5b56b170c0a1d7d594522b84fa5', '4f23a92e3543cb1d19064ae037b683a5848cf1455ada39640c543b5c3e6aace6', 'd21e9b1258e4d7debf07e3bfd74e1794fad14f1eacd06ab4ba6b1e09e064a1fc', '7a19233e1ca502e696790c2ceeebbe415d07e0f50c859f1083f8923bb570674a', '0278615ec7726ea88a80ee2afdf94f673f11b56990cc288dff1e30ddab91fa70']
Block: 1
Hash: 2754fae551f5d348e4a67ab9fa2b5bccdf1c3f8d082d3e5af9192fb94ef3ed60
Transactions: ['01ce0571d5e13ae3829bb7cb321ad6c8c2ff206f85d71121bc104afb0c9fe24d', 'cb0f4191e70ce08073a06a9da716d5b7adf80b88c465e9e8ee0d5e8bb1bb6b86', '11516328773d5f2a26438a3ce2b9db6d416fae0ea7c67c82a8689fa4512c5ca8', '6e757926deba2529174aeec80b55b36918ff7413462cf9bba1f9d4503d83a99b', '560bf167e304e536960807dab66967d2b993498b7c1244863899fe7418da258f', 'ece80e6e79497ae3bcfaa62bb4c906d61ae5c28ee393b076b83e27bbe5df3780', '6362fa418ddc5c3e238fea74d85c70c3593700e9e6b2918e2223b29496d36270', '86dc100f03b733b4527d06eeb48e1e6e1e8834cc27c8ef943f4c372db0714ef5']
Block: 2
Hash: 72173973511b7474acdcf21ff9238ab16646bd0954f318e259f516fd3262b52f
Transactions: ['97544a093e6813aa0731fb65891509bb8e7f7990bf2a05d548c31f2073beba1b', '1fb1f46148181e34aaa2be64f36cdd49187cdef5ec2f4cb80e325e208352d0c8', '45ffd5489014b390e0774a762fea54e083c68ecd13cdb44f2389c76ea1f9be13', 'a0ee992426eb5d24cf94b11da73430de5b04155de29ca4b961e8d43cbf5118f3', '40f7113578aa01e733c8a1337a4216015bb3c43c14a7edba57fd4c85a286b896', '7995c44bc52bc895ef40f41e9e860ca661e484fcb0e1f19ae24a72b5bea7ac9a', '699bc1bfdaa5db823a1d180442452431c8d752ea9110a6963983a5b72e0a92b2', 'f8fdf03a7dd6ba9706d046b2fca867f5faff40cb1afdf66a8f7206f104110fcc']
En un Python REPL, podemos definir la siguiente función y las transacciones del primer bloque:
$ python3 -q
>>> from hashlib import sha256
>>> h = lambda b: sha256(bytes.fromhex(b)).hexdigest()
>>>
>>> tx = ['1c6e1b8c366fcc78f18b8256f5c005089716baef4d3ecb779b178f93ad98a3a9', '157ca6ef30415dac2905f216e5d0861e426a1a453bdf4f6e1ae941a373a77db9', 'a0fc805c702107349facf8c837b0a009602e0a573ab31e62ec8721139eac95f6', 'ffa7108a484b1a13e0fd18a95c8b2a671156f5b56b170c0a1d7d594522b84fa5', '4f23a92e3543cb1d19064ae037b683a5848cf1455ada39640c543b5c3e6aace6', 'd21e9b1258e4d7debf07e3bfd74e1794fad14f1eacd06ab4ba6b1e09e064a1fc', '7a19233e1ca502e696790c2ceeebbe415d07e0f50c859f1083f8923bb570674a', '0278615ec7726ea88a80ee2afdf94f673f11b56990cc288dff1e30ddab91fa70']
Ahora, podemos calcular los niveles del árbol (en este caso, r0, r1, r2 y r3, el hash raíz):
>>> r0 = list(map(h, tx))
>>> r0
['bcc2b63ca170d9dfa11679e5609cd8030d178e26a5484fc69074c1bb71671d66', '086d46b118f8c989bdbae101ff90907c7826e1e7c692e3b193bd1dcfbcbb3642', '970a2ce1265bc56f6cfe64653d332bfcb4ea4513138f5a1e9352862abf03818d', 'fbc977b9479bc3e330c674ac1c5d649874bbd7563f4dfb03707af215852ea31f', 'b1e7947e6581792efd0a06e1babed0317bf662b3884c64f759ba9fd8f0515d3f', '7cd4dc293e829177d879178bae42060406eb13f0ae9f9defeaca9368f0157849', '045602b9172fc3511d733b28915fb811b9813e0ac4a8af94c42c41a16065d274', '4ff2da8be444085ff4774300a5a0a032d2a4a5a0136cc290f15feeac2f317c4b']
>>> r1 = [h(r0[i] + r0[i + 1]) for i in range(0, len(r0), 2)]
>>> r1
['9a34147e06f9b2ab4b4aaa9f40420bfb78184559368ba6b1cfa8e93ec5d87af9', 'b8966de78d413c8d266fd0e62b041cf658237719980369cd178a07ee56a54a3e', '85fa18a7a81c5eca7265fa57e55866eae375fb01b01c2ab58f50f796ca678fd0', '14e2a8f518b9fb65f9997d52b06669265295b7db75c969892869d990e4397521']
>>> r2 = [h(r1[i] + r1[i + 1]) for i in range(0, len(r1), 2)]
>>> r2
['40c0baf6daabda623276d7a9754be186c8045c22092fc8bda87e454d2477c823', 'c1776a3b23f5608b3d7341c3aa576de6950d58ade7430bb7a42c03f1ee1a8576']
>>> r3 = [h(r2[i] + r2[i + 1]) for i in range(0, len(r2), 2)]
>>> r3
['e0ad19eef177ca9b5cbbd38f87147fd1258b7e8562d4c813ef5409b257b09bd6']
Como se puede ver, el hash raíz coincide con el que muestra el servidor. Y cada nodo es el hash SHA256 de los dos nodos hijo concatenados.
Solución
Ahora, debemos proporcionar firmas falsificadas para construir un Árbol de Merkle con el mismo hash raíz. Para esto, necesitamos realizar un ataque de segunda preimagen.
Ataque de segunda preimagen
La clave aquí es que podemos tomar cualquier fila intermedia y usarla como firmas de transacción. Por ejemplo:
>>> new_tx = [r0[i] + r0[i + 1] for i in range(0, len(r0), 2)]
>>> new_tx
['bcc2b63ca170d9dfa11679e5609cd8030d178e26a5484fc69074c1bb71671d66086d46b118f8c989bdbae101ff90907c7826e1e7c692e3b193bd1dcfbcbb3642', '970a2ce1265bc56f6cfe64653d332bfcb4ea4513138f5a1e9352862abf03818dfbc977b9479bc3e330c674ac1c5d649874bbd7563f4dfb03707af215852ea31f', 'b1e7947e6581792efd0a06e1babed0317bf662b3884c64f759ba9fd8f0515d3f7cd4dc293e829177d879178bae42060406eb13f0ae9f9defeaca9368f0157849', '045602b9172fc3511d733b28915fb811b9813e0ac4a8af94c42c41a16065d2744ff2da8be444085ff4774300a5a0a032d2a4a5a0136cc290f15feeac2f317c4b']
>>> rr0 = list(map(h, new_tx))
>>> rr0
['9a34147e06f9b2ab4b4aaa9f40420bfb78184559368ba6b1cfa8e93ec5d87af9', 'b8966de78d413c8d266fd0e62b041cf658237719980369cd178a07ee56a54a3e', '85fa18a7a81c5eca7265fa57e55866eae375fb01b01c2ab58f50f796ca678fd0', '14e2a8f518b9fb65f9997d52b06669265295b7db75c969892869d990e4397521']
>>> rr1 = [h(rr0[i] + rr0[i + 1]) for i in range(0, len(rr0), 2)]
>>> rr1
['40c0baf6daabda623276d7a9754be186c8045c22092fc8bda87e454d2477c823', 'c1776a3b23f5608b3d7341c3aa576de6950d58ade7430bb7a42c03f1ee1a8576']
>>> rr2 = [h(rr1[i] + rr1[i + 1]) for i in range(0, len(rr1), 2)]
>>> rr2
['e0ad19eef177ca9b5cbbd38f87147fd1258b7e8562d4c813ef5409b257b09bd6']
Esta también es válido:
>>> new_tx = [r1[i] + r1[i + 1] for i in range(0, len(r1), 2)]
>>> new_tx
['9a34147e06f9b2ab4b4aaa9f40420bfb78184559368ba6b1cfa8e93ec5d87af9b8966de78d413c8d266fd0e62b041cf658237719980369cd178a07ee56a54a3e', '85fa18a7a81c5eca7265fa57e55866eae375fb01b01c2ab58f50f796ca678fd014e2a8f518b9fb65f9997d52b06669265295b7db75c969892869d990e4397521']
>>> rr0 = list(map(h, new_tx))
>>> rr0
['40c0baf6daabda623276d7a9754be186c8045c22092fc8bda87e454d2477c823', 'c1776a3b23f5608b3d7341c3aa576de6950d58ade7430bb7a42c03f1ee1a8576']
>>> rr1 = [h(rr0[i] + rr0[i + 1]) for i in range(0, len(rr0), 2)]
>>> rr1
['e0ad19eef177ca9b5cbbd38f87147fd1258b7e8562d4c813ef5409b257b09bd6']
E incluso esta:
>>> new_tx = [r2[i] + r2[i + 1] for i in range(0, len(r2), 2)]
>>> new_tx
['40c0baf6daabda623276d7a9754be186c8045c22092fc8bda87e454d2477c823c1776a3b23f5608b3d7341c3aa576de6950d58ade7430bb7a42c03f1ee1a8576']
>>> rr0 = list(map(h, new_tx))
>>> rr0
['e0ad19eef177ca9b5cbbd38f87147fd1258b7e8562d4c813ef5409b257b09bd6']
Implementación
Entonces, tomamos el tercer bloque (que es el que necesitamos falsificar), construimos el Árbol de Merkle y hacemos el ataque de segunda preimagen para obtener la flag:
>>> tx = ['97544a093e6813aa0731fb65891509bb8e7f7990bf2a05d548c31f2073beba1b', '1fb1f46148181e34aaa2be64f36cdd49187cdef5ec2f4cb80e325e208352d0c8', '45ffd5489014b390e0774a762fea54e083c68ecd13cdb44f2389c76ea1f9be13', 'a0ee992426eb5d24cf94b11da73430de5b04155de29ca4b961e8d43cbf5118f3', '40f7113578aa01e733c8a1337a4216015bb3c43c14a7edba57fd4c85a286b896', '7995c44bc52bc895ef40f41e9e860ca661e484fcb0e1f19ae24a72b5bea7ac9a', '699bc1bfdaa5db823a1d180442452431c8d752ea9110a6963983a5b72e0a92b2', 'f8fdf03a7dd6ba9706d046b2fca867f5faff40cb1afdf66a8f7206f104110fcc']
>>> r0 = list(map(h, tx))
>>> r1 = [h(r0[i] + r0[i + 1]) for i in range(0, len(r0), 2)]
>>> r2 = [h(r1[i] + r1[i + 1]) for i in range(0, len(r1), 2)]
>>> r3 = [h(r2[i] + r2[i + 1]) for i in range(0, len(r2), 2)]
>>> r3
['72173973511b7474acdcf21ff9238ab16646bd0954f318e259f516fd3262b52f']
>>> r2[0] + r2[1]
'a40e6baca5c856e073b52161616835f9431850a44da135c98fc28b9cdd381cbdb717c2fa5328a0771f1a950746c34ba82975976724ef7f78c9b0270f1bc5eb92'
La concatenación de los nodos del penúltimo nivel del Árbol de Merkle será un payload válido para falsificar la lista de transacciones.
Flag
Así que aquí está la flag:
[1] Explore mined blocks
[2] Forge the last block
> 2
Forged transaction signatures: a40e6baca5c856e073b52161616835f9431850a44da135c98fc28b9cdd381cbdb717c2fa5328a0771f1a950746c34ba82975976724ef7f78c9b0270f1bc5eb92
HTB{m3rkl3_tr33s_4nd_f0rg3d_s1gn4tur3s___34sy!}