4
$\begingroup$

I'm looking for a PRNG that is deliberately weak, that is, follows a set of rules stochasticly.

For example: Encounters a set of bits that is a multiple of X, starts exhibiting bias, or starts to oscillate somewhat. etc...

The weaknesses need to both be simple and complex, the experiment would consist of trying to identify those weaknesses to attain some probability P of predicting future output information using various machine learning methods.

$\endgroup$
  • $\begingroup$ Can you just use a known-weak RNG like the Mersenne Twister? $\endgroup$ – pg1989 Feb 10 '16 at 3:04
  • $\begingroup$ @pg1989: actually, the weaknesses in MT would be far too subtle for an ML to pick up on. It would appear that someone would need to select the biases, and then create a PRNG that deliberately achieves those biases. $\endgroup$ – poncho Feb 10 '16 at 3:28
2
$\begingroup$

I'd suggest starting with the dieharder suite of generators, as that list covers a lot of popular generators with known weaknesses, and the application can emit bitstreams from each generator.

The most famous bad RNG (other than the xkcd comic one) is RANDU. That's very low-hanging fruit as a warm-up exercise.

Typically these generators produce something like a 32-bit or 64-bit word, and to treat this as a bitstream from a black box you just append all the words. This implies that the bitstream is likely to show patterns with respect to every 32nd or 64th bit; and a naive test might be confounded by simply emitting 31 bits instead of 32 (this can be perfectly sensible in hardware, but rare in software).

What I don't see in that list (or may simply fail to recognise in their abbreviated names) are LFSR and xorshift generators. These have an upper limit on the number of zeroes they can emit in a row (commonly 32 or 64) and their output is always a fairly simple bitwise transform of bits seen recently, but at least xorshift can still pass a lot of statistical tests.

Linear congruential generators have high-frequency periodicity in their low-order bits (the least significant bit can only oscillate between 0 and 1, the next bit cycles through four states before repeating, etc.); some generators discard the low order bits so that the least-significant bit might repeat on a period of 65536. There's a bunch of heavier mathematics I've never bothered to think about which might be interesting to you.

Any of the dieharder tests that fail dieharder's own testing obviously do have a pattern, and that'd be a good place to look. In that sense I suppose dieharder documents your options better than I ever will.

Of those that pass all statistical tests, most are still considered insecure when you have insight into how the generator might work. dieharder is not a cryptographic tool.

| improve this answer | |
$\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.