Generate cryptographically secure random number

[Anh Hai Trinh]

Python random uses the Mersenne Twister RNG, which is "completely
unsuitable for cryptographic purposes." [1]

AppEngine also includes pyCrypto.randpool, but it needs access to '/
dev/random' because "if it can't get entropy from the OS, it silently
produces predictable output." [2] (plus it will be deprecated)

So my question is, is it possible to generate cryptographically secure
random number in AppEngine?

Reference
=========
[1] http://docs.python.org/library/random.html
[2] http://lists.dlitz.net/pipermail/pycrypto/2008q3/000000.html

[Brandon N. Wirtz]

Yep. You can write anything you want in python.

Need a random number... Try this...
Perform a database transform 18 times, take the execution times of these,
find the min execution time, and Max execution time.

Assign the longest time to be 100% and the shortest to be 0% the remaining
16 passes are then converted to 0 if they are closer to 0 and 1 if closer to
100

Construct a 16 bit number from the 0's and 1's

This method, assuming you pick a database or other operation that has an
expected time frame which is predictable, but follows a natural
distribution, will create truly random 16 bit numbers.

Depending on how many bit number you need you can increase the number of
numbers generated.

If you need a longer random number in low volume you can do a hash of the
most recent page added to digg.

Construct a random number based on the difference in system time between
your server and the client making the request.


Suitability for cryptography is a stupid blanket statement:
If you need one 128 bit random number you could ask 128 people 1 or 0 and
have a suitable number. But because of the way people work if you did that
1 million times you'd find that you don't get good distribution of 1s and
0s.

If instead you said give me a number between 1 and 100 and assigned even
numbers a 0 and odds a 1 you would get a more random number suitable for
100's of thousands of crypto keys.

If you instead took the temperature of 128 people and if the thermometer
said an even decimal assigned that a 0 and odd decimals a 1, you would have
a random number that would be suitable for millions of random numbers.

If you took the hash of a password some one gave you, you'd be good for a
few thousand random numbers but would find some passwords came up more than
statistically random should..

-Brandon Wirtz
Blackwaterops.com

[Nick Johnson (Google)]

Hi Anh,

Good question! There's nothing built directly in, but you have several options:

- You can implement, or use an existing implementation of a well known cryptographically secure PRNG, such as Blum Blum Shub.

- You can make use of one of the block ciphers provided by pycrypto to generate a PRNG stream - just use it in CTR mode with a random key as seed data.

- You can make use of a secure hash from the hashlib module - again, start with a random input and increment it for each block of random data.

On Wed, Oct 7, 2009 at 7:55 AM, Brandon N. Wirtz <dra...@digerat.com> wrote:

Yep.  You can write anything you want in python.

Need a random number...   Try this...
Perform a database transform 18 times, take the execution times of these,
find the min execution time, and Max execution time.

Assign the longest time to be 100% and the shortest to be 0%  the remaining
16 passes are then converted to 0 if they are closer to 0 and 1 if closer to
100

Construct a 16 bit number from the 0's and 1's

This method, assuming you pick a database or other operation that has an
expected time frame which is predictable, but follows a natural
distribution, will create truly random 16 bit numbers.

Please don't suggest inventing cryptographic primitives oneself! Doing so is one of the fastest and easiest ways to end up with security flaws in your software.

-Nick Johnson

--
Nick Johnson, Developer Programs Engineer, App Engine
Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration Number: 368047

[Anh Hai Trinh]

On Oct 7, 4:07 pm, "Nick Johnson (Google)" <nick.john...@google.com>
wrote:

> Hi Anh,
> Good question! There's nothing built directly in, but you have several
> options:
> - You can implement, or use an existing implementation of a well known
> cryptographically secure PRNG, such as Blum Blum Shub.
> - You can make use of one of the block ciphers provided by pycrypto to
> generate a PRNG stream - just use it in CTR mode with a random key as seed
> data.
> - You can make use of a secure hash from the hashlib module - again, start
> with a random input and increment it for each block of random data.
>

Dear Nick,

How would you advise implementing any of these approaches in
AppEngine. It is difficult because the random number is usually
needed as a nonce (not en mass, like in a simulation) and therefore
we'll need to maintain the state of the RNG, which is impossible since
we can't have long running process in AppEngine. Maybe we can store
the counter in the Datastore, and it'll need to be sharded, possibly
memcached, and will need to deal with timeout, etc. It is always
tricky to roll our own cryptographic implementation, of any kind,
securely.

[Jason Smith]

Frankly this is when I would start exploring supplying random data to
my app myself, externally. For example, many hosting providers supply
hardware random number generators. I'd find an economical one and have
it dump as much entropy as you need into into AppEngine via cron. Sign
the data from the host, confirm it in GAE, and store it for later as a
blob.

Yes, there is a cost of splitting your application into multiple
components with dependencies, but I don't know, I wouldn't feel
comfortable implementing an RNG myself. And a PRNG still needs a
secure seed so that only gets you so far. On the other hand you could
have gigabytes of true randomness in a day's work and a few dollars
per month.

[Nick Johnson (Google)]

Hi Anh,

Depending on what you need the nonce for, you could simply construct a value from a secret key you include with the app, the ID of the user or record it's for, and something ephemeral such as the current time, then hash the value with a secure hash function to generate the nonce. This is secure as long as the secret key remains confidential.

-Nick Johnson

[N. Rosencrantz]

7 generators are Lehmer, Rotenberg, GGL, Neave Oakenfull (2) and
Wichmann-Hill
docs.python.org/library/random.html
Weibull function or Brownian motion are also wellknown randomnesses:
import random
print random.weibullvariate(2,2)
output:
1.85255758863