search

clifordsymack / Electron-Cash

Electrum; Bitcoin thin client
MIT License
6 stars 3 forks source link

[KS-CSSH-F-001] Modulo bias in generate_random_sk() #57

Closed AnomalRoil closed 5 years ago

AnomalRoil commented 5 years ago

In generate_random_sk(), a random is drawn between 0 and 2^256 and then reduced modulo the curve order:

https://github.com/clifordsymack/Electron-Cash/blob/e22194f8c5403bc13478cd292381426b6ec36212/plugins/shuffle/client.py#L230-L235

This introduces a so-called modulo bias and should be avoided by either using rejection sampling (i.e. generating random numbers until it's small enough, which is the default behaviour of Python's ecdsa randrange function) or by using directly the right bounds in a secure random function.

We usually recommend to use directly Python 3.6’s Secrets module, which provides directly the function you need such as randbelow or, if using older Python versions os.urandom() along with rejection sampling.

This could also be fixed by using directly the order in ecdsa's randrange function.

cculianu commented 5 years ago

I didn’t write this code but I have been brought on to glue it to Electron Cash properly and to also update it.

So it would be enough just to get a randrange upperbounded by _r and call it a day, right? E.g. :

ecdsa.util.randrange(_r) ?

AnomalRoil commented 5 years ago

Yes, as long as the randrange from the Ecdsa module remains secure.

cculianu commented 5 years ago

Yeah good catch. I initially assumed order was 2^256 anyway when reading the code again (just now) but it wasn't -- I wrote something on Telegram about it which you can ignore.

It was actually less than 2^256 so there definitely was a modulo bias.

Fixed in latest commit. Thanks.