Facebook CTF 2019 - postquantumsig (Crypto, 125)

Challenge

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

Given : verifier.py, signatures.csv

There’re tons of signatures.

Those format is :
identity | transaction msg | H1, H2, ..., H512 | Others

The part of others is made up of five to six [bit(0 or 1), sha256(?)]

In verifier.py, I found it just do something to hash of transaction msg(bit by bit).

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, I take a look at signature.csv and found no matter what transaction message is, H1, H2 are

359d5317c1adc9f750ebcdbe6b02929bfc1f72bd92e67d00e4914b819524b743,a94058c640ab1fcb920da3056d7e518bc9cc7e886af7d389d71d754bb942fa65,

or

2002f00883a023e155a08db1e87d17bc8004785194f527dff9e9a3453339f960,c5e01c06a18d7d4e1061ba3ab920988c5281cf48653a35757193239fc6956018,

e.g. If the first bit is 0, H1,H2 are

359d5317c1adc9f750ebcdbe6b02929bfc1f72bd92e67d00e4914b819524b743,a94058c640ab1fcb920da3056d7e518bc9cc7e886af7d389d71d754bb942fa65,

else if the first bit is 1, then H1,H2 are

2002f00883a023e155a08db1e87d17bc8004785194f527dff9e9a3453339f960,c5e01c06a18d7d4e1061ba3ab920988c5281cf48653a35757193239fc6956018,

This seems determined by the hash of transaction message corresponding bit is 0 or 1.

Not only that, I also found out each transaction send by 9bca65c9376209ede04b5df3b02cb832f8997ff978069d171dc9cbfca657f91a using the same value of others to get the identity.

[
0, d0387c7bd1f8776829397426ee43ed5ce3d640b78379762582e330c9472a2ec0,
0, cc0ab8c97096f3f7894ef4c76c573ea8f65072cf2f58fa72a0ac679718371c1e,
0, d48e7be8713e54c00c0a45786667916459e545ea2795e068a20f18c0a230e476,
0, 017b9a1fa38e2c572de41e02d339ace47d8463ae0b86e9ee9289e5e13539eb84,
0, fc9e2ba2edfd3a75ffee8a6b2b20411763f17575c6aeb76950c777b9ea335370
]

Solution

Maybe …

  1. If I use 9bca65c9376209ede04b5df3b02cb832f8997ff978069d171dc9cbfca657f91a to send the transaction message.

  2. collect all corresponding hash value to make the right set of H1,H2,…H512 depends on the hash of transaction message.

  3. Add that others behind it.

Then I will pass the veritify … ?

BINGO.

fb{reduce_reuse_recycle_is_bad_advice_for_ots}

After the game, I learned that this algorithm is called Lamport signature or Lamport one-time signature

I hope this message helps xD.