Instantly share code, notes, and snippets.

# robot-dreams/challenge_002.md Secret

Created January 7, 2022 21:39
Show Gist options
• Save robot-dreams/678bac9ef5d021fbf610d6e171243e0a to your computer and use it in GitHub Desktop.
Challenge 002

Previous: Challenge 001

This one is based on Exercise 19.1 of A Graduate Course in Applied Cryptography.

The poor signer realized their mistake and upgraded their implementation to randomly generate (private) nonces. Unfortunately, they also didn't get the memo to use a secure PRNG, and ended up using a Linear Congruential Generator instead.

You're given Schnorr signatures on two different messages signed by the same private key. Although the signatures both verify under BIP-340, the two private nonces are related via `r2 = a * r1 + b`, where `a = 31337` and `b = 69420`.

Can you still extract the signer's private key?

#### Public Key

``````21922E7D5988A711123794D70B19C2827B1630BC2AB99887418D9EF4AFDB1AC2
``````

#### Message 1

``````49276D20626574746572207769746820636F6465207468616E20776974682077
``````

#### Signature 1

``````19D6493FBA397CDD1C1E10F9AB51E65531D587D7C53C04673779E1A307AC795CF801B1BF3D103771F74C5F70BB3A3557D87E5116294A9ABD357DC4367D123C9D
``````

#### Message 2

``````4265696E67206F70656E20736F75726365206D65616E7320616E796F6E652063
``````

#### Signature 2

``````0293422DCE97000231B98AFE3CBE405601D4129296AB902822514DF9B2F0BC9D7FC2B9C64FA080688D020407900CE9DE887B9CBB25C34280DAB6E172CC39C2F0
``````

## Bonus Challenge

If the signer happened to use `a = 1337` instead of `a = 31337`, there's a good chance your attack will now fail. Can you fix the issue?

Hint: How is BIP-340 able to use only 32 bytes to store a public key?

#### Public Key

``````21922E7D5988A711123794D70B19C2827B1630BC2AB99887418D9EF4AFDB1AC2
``````

#### Message 1

``````49276D20626574746572207769746820636F6465207468616E20776974682077
``````

#### Signature 1

``````19D6493FBA397CDD1C1E10F9AB51E65531D587D7C53C04673779E1A307AC795CF801B1BF3D103771F74C5F70BB3A3557D87E5116294A9ABD357DC4367D123C9D
``````

#### Message 2

``````4265696E67206F70656E20736F75726365206D65616E7320616E796F6E652063
``````

#### Signature 2

``````B0D1BB19E0FDC76FF9702EF847D486B39F78DFAF59A3AE5D88C6FE44A1E4ED46110C668DA0C408E4B5A8DBD021B56FE82A2A816962D19C2D7747ED32DCCA3396
``````

### siv2r commented Jan 24, 2022 • edited

I don't understand why the attack will fail on making `a = 1337`.
On solving the two schnorr equations, we get `x = (a.s1 - s2 + b) . (a.e1 - e2)^-1` this equation is valid for all values of `a`and `b` right?

### robot-dreams commented Jan 24, 2022 • edited

@siv2r You're right (well, except you still do need `a.e1 - e2` to be invertible). The failure for `a = 1337` is not an issue with this attack (in general), but a specific implementation detail of BIP-340.

### siv2r commented Jan 24, 2022

well, except you still do need a.e1 - e2 to be invertible)

Thanks for pointing this out! I assumed that the scalar elements (range [0, q]) forms a cyclic group like the one created by the generator point. I was wrong.

a specific implementation detail of BIP-340

Ah, I see. I used libsecp's internal structs so, I don't need to worry about this :)

### robot-dreams commented Jan 24, 2022

Well, they form a cyclic group if you exclude 0, and that's all I meant :) the element `a.e1 - e2` has to be nonzero