Description

Our hot new cryptocurrency uses powerful techniques to make the asymmetric key signatures just as hard to crack on a quantum computer as a binary one. Maybe we forgot something though? Send some money to a weird address if you get any.

nc challenges.fbctf.com 8088

---

The challenge begin with the above description and two files. The first one is a python script named verifier.py and the second is a csv database of transactions named signature.csv. The python script verify that the transactions in the database are genuine. Moreover, when using the netcat command, the server is asking to enter a signature row.

Clearly, we need to craft a transaction that send money to a custom address and that transaction needs to be validated by verifier.py. A transaction is a row in the database and the format of such a row is:

sender identity, transaction msg, H1, ... H512, R1:O1, ...)

H1 to H512 are sha256 digests, the R(n) are numbers (0 or 1) and the O(n) are sha256 digests. Moreover, R(n) and O(n) are optional.

The core of verification algorithm is in the function verify_signed_message which does:

def verify_signed_message(msg_w_signature):
    identity, h_msg, signature, others = parse_signed_message(msg_w_signature)
    sign_msg = msg_to_hashes(h_msg, signature)
    initial = make_top_hash_from_leaves(sign_msg)
    top = make_top_hash_from_others(initial, others)
    return (identity, top)

And parse_signed_message is:

def parse_signed_message(msg_w_signature):
    # separate a formatted message and signature into components
    top_identity = msg_w_signature[0]
    msg = msg_w_signature[1]
    h_msg = s256(msg)
    signature = msg_w_signature[2:514]
    others = group_by_n(msg_w_signature[514:])
    return (top_identity, h_msg, signature, others)

There is a major mistake in parse_signed_message on the line signature = msg_w_signature[2:514]. Indeed, the slice (i.e. 2:514) is clamped to the boundaries of the tuple msg_w_signature. So if there is only 2 elements in msg_w_signature, msg_w_signature[2:514] will returns an empty tuple.

Hence, if we have a transaction with the format sender identity, transaction, H1, H2, the function msg_to_hashes will only create one group of signatures and hence only iterate once.

def msg_to_hashes(msg, signature):
    # turn a message with signature into an ordered list of key pairs
    bit_stream = bit_stream_from_msg(msg)
    sign_stream = group_by_n(signature, 2)
    return_stream = []
    for bit, sign in zip(bit_stream, sign_stream):
        if bit:
            return_stream.append(sign[0])
            return_stream.append(s256(sign[1]))
        else:
            return_stream.append(s256(sign[0]))
            return_stream.append(sign[1])
    return return_stream

So, we will have the following operations to compute our identity.

# msg_to_hashes
return_stream = []
# b1 = first bit of h_msg
if b1 == 1:
    return_stream.append(H1)
    return_stream.append(s256(H2))
else:
    return_stream.append(s256(H1))
    return_stream.append(H2)

# make_top_hash_from_leaves which implement the Merkle signature scheme
identity = s256(return_stream[0] + return_stream[1])

Now, assuming that b1 is 1, we need to find H1 & H2 such that sha256(H1 + sha256(H2)) = identity. For that we can use make_top_hash_from_others.

def make_top_hash_from_others(initial, others):
    # traverse asymmetic segments of public key signature to get public key
    top_hash = initial
    for rank, other in others:
        if int(rank):
            top_hash = s256(other + top_hash)
        else:
            top_hash = s256(top_hash + other)
    return top_hash

Indeed, if the last hash in others is of rank 1, we get:

top_hash = s256(other + top_hash)
# or top_hash = s256(top_hash + other)
top_hash = s256(other + top_hash)

That is:

HH = H(H2) # "H2 = top_hash + other" or H2 = "other + top_hash"
identity = H(H1 + HH) # H1 = other

Similarly if b1 is 0 and the rank of last “other” is 0.

Because of that, the difficulty boils down to building a transaction message with first bit of the hash equals to an existing transaction of the same sender. It’s easy to do, by changing the ammount of zuccoins sent.

In my case the final transaction was:

Dest: 34a4e8ed19e3e08cf4719af6550afde1f97137dfe8af1565d8c9a8a5cbcb99df
Msg:  34a4e8ed19e3e08cf4719af6550afde1f97137dfe8af1565d8c9a8a5cbcb99df sent 102.10247476840064 zuccoins to 59bb2642bbf7f009e9bf3c6c45ac30cbc1a897235e0e3a407d49966aa4867a93

H1: 1a96f6d19e9258935a97d41f9507ba9b9241113d641362fa55642c4a1dad277a
H2: e7cfafb7f08de90f7cb44994024b6baa870b8a780837c0bb9e0835e6c4a856a03163753c32343907f466d4af6823b8db62e5594cc90f97762c86104ceb6a9217