I'm gRoot
6 minutes to read
We are given the Python source code of a server:
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
Source code analysis
The challenge creates some sort of transactions in a Blockchain with a Merkle Tree. The aim of this challenge is to forge transaction signatures so that we get the same root:
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)
The source code might be too long, but it is easy to understand. The Blockchain is initialized with three blocks, each of them containing eight transactions:
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)
Each of the blocks is mined:
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()
})
Here we have a hint on what we need to accomplish. Since security=False in the MerkleTree constructor, we can investigate the consequences of this. There is a GitHub issue that says it is vulnerable to a second preimage attack.
Merkle Tree
A Merkle Tree is built as follows:
Source: https://en.wikipedia.org/wiki/Merkle_tree
In our case, each block is a Merkle Tree, started from 8 transactions. The 8 leaf nodes are the SHA256 hash of the transaction signatures. The second row is composed by 4 nodes that are the SHA256 hash of each two child nodes concatenated. The third row is composed by 2 nodes. And finally we have the root node.
Let’s take an example from the server:
$ 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']
In a Python REPL, we can define the following function and the transactions of the first block:
$ python3 -q
>>> from hashlib import sha256
>>> h = lambda b: sha256(bytes.fromhex(b)).hexdigest()
>>>
>>> tx = ['1c6e1b8c366fcc78f18b8256f5c005089716baef4d3ecb779b178f93ad98a3a9', '157ca6ef30415dac2905f216e5d0861e426a1a453bdf4f6e1ae941a373a77db9', 'a0fc805c702107349facf8c837b0a009602e0a573ab31e62ec8721139eac95f6', 'ffa7108a484b1a13e0fd18a95c8b2a671156f5b56b170c0a1d7d594522b84fa5', '4f23a92e3543cb1d19064ae037b683a5848cf1455ada39640c543b5c3e6aace6', 'd21e9b1258e4d7debf07e3bfd74e1794fad14f1eacd06ab4ba6b1e09e064a1fc', '7a19233e1ca502e696790c2ceeebbe415d07e0f50c859f1083f8923bb570674a', '0278615ec7726ea88a80ee2afdf94f673f11b56990cc288dff1e30ddab91fa70']
Now, we can compute the levels of the tree (in this case, r0, r1, r2 and r3, the root hash):
>>> 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']
As can be seen, the root hash matches the one shown by the server. And each node is the SHA256 hash of the two child nodes concatenated.
Solution
Now, we must provide forged signatures to build a Merkle Tree with the same root hash. For this, we need to perform a second preimage attack.
Second preimage attack
The key here is that we can take any intermediate row and use them as transaction signatures. For instance:
>>> 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']
This one is also valid:
>>> 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']
And even this one:
>>> 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']
Implementation
So, let’s take the third block (which is the one we need to forge), build the Merkle Tree and provide the second preimage attack to get the 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'
The concatenation of de second-to-last level nodes of the Merkle Tree will be a valid payload to forge the list of transactions.
Flag
So here’s the flag:
[1] Explore mined blocks
[2] Forge the last block
> 2
Forged transaction signatures: a40e6baca5c856e073b52161616835f9431850a44da135c98fc28b9cdd381cbdb717c2fa5328a0771f1a950746c34ba82975976724ef7f78c9b0270f1bc5eb92
HTB{m3rkl3_tr33s_4nd_f0rg3d_s1gn4tur3s___34sy!}