SHA-based subclass for random module

[Jeff Epler]

Since the size of plaintext is only 2^53, can't I just calculate 
all 2^53 md5 values in advance, and invert the output of MD5Random to
get MT outputs, then attack MT just like any LFSR?

A time-space tradeoff could be made between the number of precalculated
hashes and the number of outputs from the MD5Random PRNG needed, too.
A quick search on the internet indicates that about 2n bits are needed
to find the initial state of an n-bit LSFR[1], so something like 40000 bits
would be needed to find the internal state of MT, or 380 53-bit outputs.

So let's say you can precalculate 2^30 MD5 inverses, the chance of any
particular output being in the table is 2^-23.  So you'd need something
like 2^31 outputs from MD5Random().  I'm sure the analysis is also
complicated by the fact that your 2n bits won't be consecutive outputs,
but will be widely separated, but it's likely to remain possible.

2^53 is a big number, but it's well less than the 2^128 range for
all MD5 signatures or the 2^64 signatures needed to find a collision.
2^30 storage and 2^31 calls to random is something many of us could at
work, if not at home.

IANAC,
Jeff
[1] http://www.ciphersbyritter.com/RES/COMBCORR.HTM 
"(The Berlekamp-Massey algorithm will recover the unknown state of a
simple n-bit LFSR, and its feedback polynomial, with just 2n known
bits.)"