2
$\begingroup$

I read in a book: mastering bitcoin that one should not create his own random number generator and instead use a cryptographic secure pseudorandom number generator (CSPRNG)

Why is it so? Say I'm writing a simple python code to choose a number between 1 and 2^256 in the following way: create an array with 256 bits, fill up each index with a random number (1 or 0)

Why, or in what way, it is inferior to the CSPRNG? and how is this code is predictable?

$\endgroup$
  • 5
    $\begingroup$ You didn't define how you choose your random 0 or 1. How do you measure the randomness for this? What CSPRNG are you comparing it to? What is the basis of your comparison, e.g. what metrics are you using? $\endgroup$ – floor cat Aug 19 '17 at 2:39
  • 1
    $\begingroup$ fill up each index with a random number That's not writing your own generator, but using an existing one. (Depending on it's properties, it might be ok to just collect bits and use them together, or it might be not. Likely, it's not ok.) $\endgroup$ – deviantfan Aug 19 '17 at 10:48
  • $\begingroup$ If you have a magical oracle that gives you truly random, private, unbiased and independent bits, you can use your approach. The closest thing to such a magic oracle on standard computers is the RDSEED instruction (and even it has some CSPRNG like post-processing), but then you fully entrust Intel with your randomness generation. Also I'm not aware of python offering access to RDSEED in its standard library. $\endgroup$ – CodesInChaos Aug 19 '17 at 11:46
  • $\begingroup$ far more people are killed on kitplanes than jumbo jets... $\endgroup$ – dandavis Aug 20 '17 at 9:58
  • $\begingroup$ @dandavis professionals built the Titanic, but an amateur built the Ark... $\endgroup$ – Paul Uszak Sep 5 '17 at 12:06
5
$\begingroup$

So, you use integrated Python random, instead of CSPRNG. The problem is here: integrated random functions in programming languages are designed to be very fast, and they have some small period. For example, in C#, standard Random class is seeded by 32 bit integer. Let imagine I use it to generate 256 bit number, like you.

In this case, it can generate only 2^32 different numbers (one for each seed). But we know, there are 2^256 such numbers. If I have generated 256 bit number with this method, anyone can hack my number. He just have to run generator for all possible seeds. 4 billions is very small number and anyone with PC can brute force it.

In case with bitcoins, that means, anyone can restore your private key and steal your bitcoins. Because you used weak random.

$\endgroup$
3
$\begingroup$

If you can reseed the random generator, your approach is fine and secure, but very inefficient. You're reinventing the proverbial wheel.

Python 3's random module uses the Mersenne Twister which has a period of 2^19937. It's not a CSPRNG so can be predicted, but that requires 624 consecutive 32 bit integers of output due to it's huge internal state. That's 19968 bits. You're only using 256 of them. That still leaves 19712 bits of security against prediction. If you adhered to 256 bits of security, you should be able to generate 77 such keys and still remain very secure against predicting the 78th. You would of course have to reseed the generator with a corresponding 256 bits of entropy to generate a single fully random key. Otherwise your seed material is diluted across all keys, creating keys with only 78 bits of entropy in them (for a 256 bit seed).

This leads to using the OS inbuilt generator to self seed random(). Python can use /dev/urandom for this (or CryptGenRandom probably). The inefficiency mentioned earlier is that you might as well dispense with Python's random number generator and use bits from /dev/urandom directly. Or use Python's secrets module and keep the whole thing in house via an OS /CSPRNG combination.

So in a way, Mr Antonopoulos was right in his book, but your bit banging method will work too. It's just a tad circuitous.


It then becomes somewhat of a dialectic as to what the true entropy content is of keys generated via /dev/urandom.

$\endgroup$
  • $\begingroup$ The Mersenne Twister gets its randomness from the seed and the number of times it's been used, which means that the first pull from the algorithm will have basically only the initial 32 bits of entropy. If you also know the number of pulls that has occurred since the start, it's possible to exploit the RNG, for example in games like Pokemon. $\endgroup$ – March Ho Dec 27 '18 at 16:47
1
$\begingroup$

Creating any cryptographic algorithm is a hard task, but creating your own random number generator is very hard indeed. Designing the algorithm itself is hard, but there are plenty of existing ones to choose from. Once you've chosen one that is cryptographically secure you need to know how to seed it. This is much harder than people think. First of all the source must be private to you, it must be fast enough.

Now you only need 256 bits. That's next to nothing, the absolute minimum amount of bits as not to brute force the random seed is about 64 bits. This is only about 4 times as much. So performance is not such a big problem. So in the end there is no downside to simply using the system random number generator or an existing CSPRNG that seeded by this random number generator.

Even if you've got your own entropy source then you should still be better off seeding the system or platform random number generator.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.