Challenge

1
2
3

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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

1

359d5317c1adc9f750ebcdbe6b02929bfc1f72bd92e67d00e4914b819524b743,a94058c640ab1fcb920da3056d7e518bc9cc7e886af7d389d71d754bb942fa65,

or

1

2002f00883a023e155a08db1e87d17bc8004785194f527dff9e9a3453339f960,c5e01c06a18d7d4e1061ba3ab920988c5281cf48653a35757193239fc6956018,

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

1

359d5317c1adc9f750ebcdbe6b02929bfc1f72bd92e67d00e4914b819524b743,a94058c640ab1fcb920da3056d7e518bc9cc7e886af7d389d71d754bb942fa65,

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

1

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.

1
2
3
4
5
6
7

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