# Facebook CTF 2019 - postquantumsig (Crypto, 125)

### Challenge

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).

So, I take a look at signature.csv and found no matter what transaction message is, H1, H2 are

or

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

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

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.

### 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.

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