Bitcoin Forum
May 23, 2019, 08:17:12 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Isn't doing % N while generating a random key a flaw?  (Read 130 times)
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 625
Merit: 851


Novice C♯ Coder


View Profile WWW
September 26, 2018, 04:23:37 PM
Merited by suchmoon (4), HeRetiK (1)
 #1

I have been going around and reading a lot of ECC code lately, and recently I realized some of them do something that at first sight seems harmless but I think can potentially cause some bugs. But I am not sure!

Basically when generating a new key they generate a new 256 bit number (byte[32]) then they calculate I256 % n (I being the 256 bit number equivalent) to make sure it falls within range of curve values.

Here is the problem. A 256 bit number can be as big as
115792089237316195423570985008687907853269984665640564039457584007913129639935
While the order of the curve (for example secp256k1 that bitcoin uses):
115792089237316195423570985008687907852837564279074904382605163141518161494337
So the difference would be:
432420386565659656852420866394968145598
(Which is 17 bytes by the way).

So technically you can end up with a number that is between n and 2256 and eventually because of that mod end up with a key with little entropy. For example if I256 is n+1 you will end up with private key 1 while the byte[32] was random and big enough.

I guess my question is whether this chance is too small that it doesn't matter or is it in fact a flaw in this type of implementation?

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

1558599432
Hero Member
*
Offline Offline

Posts: 1558599432

View Profile Personal Message (Offline)

Ignore
1558599432
Reply with quote  #2

1558599432
Report to moderator
1558599432
Hero Member
*
Offline Offline

Posts: 1558599432

View Profile Personal Message (Offline)

Ignore
1558599432
Reply with quote  #2

1558599432
Report to moderator
GET 25 FREE SPINS AT REGISTRATION
GET 100% BONUS ON FIRST DEPOSIT
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1558599432
Hero Member
*
Offline Offline

Posts: 1558599432

View Profile Personal Message (Offline)

Ignore
1558599432
Reply with quote  #2

1558599432
Report to moderator
1558599432
Hero Member
*
Offline Offline

Posts: 1558599432

View Profile Personal Message (Offline)

Ignore
1558599432
Reply with quote  #2

1558599432
Report to moderator
odolvlobo
Legendary
*
Offline Offline

Activity: 2506
Merit: 1314



View Profile
September 26, 2018, 05:21:12 PM
Last edit: September 26, 2018, 05:32:37 PM by odolvlobo
 #2

A random number generator will occasionally give you a value of 1, so the fact that I256 % n can be 1 does not make it not random. If I256 is generated randomly, then I256 % n is also random regardless of what the resulting value is, though you could say the result is very slightly less random in this case because the distribution is not uniform.


Buy bitcoins with cash from somebody near you: LocalBitcoins
Buy stuff on Amazon at a discount with bitcoins or convert Amazon points to bitcoins: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
aleksej996
Sr. Member
****
Offline Offline

Activity: 476
Merit: 326


Do not trust the government


View Profile WWW
September 26, 2018, 06:28:25 PM
 #3

It isn't a big issue.

This just means that those 432420386565659656852420866394968145598 first numbers are twice more likely to occur in the generator then they would naturally.

If you pick a random number between 0 and 2256, there is 1 in 2120 chance that it will be in the range between 0 and 2136. Due to this suboptimal behaviour, it will be 1 in 2119, so not a big difference when it comes to security.

So as an attacker, you would likely want to start by searching that keyspace first at the beginning, although the key will be there only once in 2119 keys that you try to break, but it is still a bit more likely to be there then any other range of same size in that keyspace, so it is a nice optimization technique if you are braking a lot of keys.

Technically it is a flaw, since using this for an attack is slightly better then brute force, but I assume many brute force implementations would have this optimization by an accident, simply because it makes sense to start at the beginning, perhaps, if the numbers are random.
ETFbitcoin
Legendary
*
Offline Offline

Activity: 1652
Merit: 1766

Use SegWit and enjoy lower fees.


View Profile WWW
September 26, 2018, 06:56:39 PM
 #4

Since the biggest valid value of the secp256k1 is known, the code simply shouldn't use invalid key created from out-of-range value. But some implementation automatically check whether the value is bigger than biggest valid value, so IMO you don't need to worry about it.

gmaxwell
Moderator
Legendary
*
qt
Online Online

Activity: 2744
Merit: 2260



View Profile
September 27, 2018, 12:27:56 AM
Merited by Foxpup (4), suchmoon (4), ETFbitcoin (1), HeRetiK (1), Coding Enthusiast (1)
 #5

Using a 256 bit number mod N will result in a key with less entropy but not in the way you think.

Imagine you had an random number generator that generated a key perfectly uniformly.  It could possibly generate a small value. That small value doen't have "less entropy"  all values out of it have the same entropy (just under 256 bits).

256-bits Mod N results in less entropy because it makes small values more likely: It could generate a small value directly, or by wrapping a big value.  But a big value can only be found directly.

But for secp256k1 N is so ridiculously close to 2^256, relative to the size the amount of bias created is very tiny. Other than with a broken RNG, a wrapping event will probably never happen to anyone ever much less enough of them to account for a meaningful bias.    For some other curves, however, N is not near a power of 2, and wrapping may result in enough bias to actually matter.

The normal way to avoid this problem is to use rejection sampling:  If your random ceil(log2(N)) bit number is greater than N, throw it out and generate a new random number. This eliminates the bias completely but at an expense of making the operation variable time and using more randomness.  Another approach is to generate a much bigger number, like one with several times the number of bits as N, and reduce that mod N.  This will make the bias much smaller.

I prefer to get rid of the bias when I can, but for secp256k1's N it really shouldn't be a problem practically anywhere.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!