3
$\begingroup$

Every single PRNG attack I could find during my research depends on knowing the PRNG algorithm(s) as well as having definite output.

Suppose you have the following scenario: nothing is known about the PRNG design and the output you get is filtered through an application such that you only get $A,B,C,D$ where each symbol has some 'probability'. To simplify this you can assume that the output of the PRNG is between 0 and 100 and that it is arbitrarily divided such that each symbol in $A,B,C,D$ has its own range. You do not actually get to see the PRNG output at any point.

What kind of attack is possible on this $A,B,C,D$ output stream? The only one I can think of is if the PRNG cycle is short and it starts repeating.

$\endgroup$
  • $\begingroup$ The goal is for the algorithm to emulate a perfect black box RNG. The reason why people focus on the algorithm is because we want really, REALLY strong assurance that the algorithm is safe. Security through obscurity is not good enough $\endgroup$ – Future Security Oct 28 '18 at 16:55
4
$\begingroup$

This depends on the type of attack planned, and the information available. Given only the output string (or parts of it), any decent cryptographic PRNG is infeasible to try to predict (which is usually what you want, since future keys or other parameters are desired).

Additionally, if your symbol distribution is uneven, it is not a very good PRNG. (For the simple reason that it is easier to try to simply brute-force prediction guesses). Their main protection typically is limited number of brute-force trials possible for the attacker.

However, NIST has a standardized test suite to test bit-valued PRNGs (NIST SP 800-22. Simple googling will give you the document, source code and binaries).

The test suite will try to find a common set of weaknesses from a bit-valued PRNG output. Using the results from the test suite, it would be possible to try to estimate the PRNG behavior, statistically, in case it was badly designed.

In case the PRNG symbols are not binary, and/or they have an uneven distribution, most of the NIST-tests would fail, or refuse to start. It is a straightforward (but not necessarily trivial) transformation of number bases to move from N (evenly distributed) symbols to a binary base.

For the unevenly distributed case, it might be useful to try to find an evenly distributed set of symbols to try to arrive to applicable binary base. For example:

  • Given a distribution of A: 1/2, B: 1/4, C: 3/16, D: 1/16
  • Assign a set of 4-bit codes for each: 8 codes for A, 4 codes for B, 3 codes for C and 1 code for D
  • Replace the symbol string with this assigned bit-string such that for example for an occurence of A, assign randomly one of its 8 codes to that occurrence.

Because this transformation does not look like the original bit string, you will need more samples (probably at least as many times as is the size of the largest bit-set) to compensate.

In general, some of the NIST tests require in the order of billion-bit samples to complete, so they may be applicable only for automated systems, not for example physical world gaming devices. (Slot machines have sometimes been attacked via weak PRNGs inside them, see e.g. https://www.ethicalhacker.net/features/book-reviews/mitnick-the-art-of-intrusion-ch-1-hacking-the-casinos-for-a-million-bucks)

$\endgroup$
  • $\begingroup$ The application utilizes PRNG output to determine its output, after collecting a large enough sample it is possible to work out what the hardcoded biases are (unless the PRNG implementation is really bad and the results don't correspond to intent). So I end up with say, 20,000 samples and my goal is to try and predict the next sample with a degree of accuracy higher than the inherent bias (if A has a 40% chance of appearing, I want to be able to predict it with >40 percent chance based on previous samples). The assumption is that the RNG is weak. And I'm not sure of what approach to take. $\endgroup$ – Alex Beckin Jan 7 '17 at 19:51
  • $\begingroup$ Let's call the application output symbol stream (the one with A's, B's, C's, etc.) the symbol stream, and the PRNG output a bitstream (the underlying assumption, if the environment is digital at all). Then, I would try to find out the relative frequencies of each symbol, as you mentioned. Try to have as many samples as possible, to have sufficient accuracy. Then I would try to find rational numbers m_A/n_A, m_B/n_B,... as close to those individual frequencies as possible. If all n_A , n_B,... are powers of two, it gives an indication that a bitstream is used directly, some bits at a time. $\endgroup$ – Mikko_K_123 Jan 8 '17 at 18:32
  • $\begingroup$ If n_A, n_B are other integers, it usually means that an additional layer is present, between the system PRNG and the application (possibly a library routine, script,... don't know your setup). After finding the denominators, you should find their least common multiple, call that N. N will help you to find evenly distributed (variable-length) chunks of the symbol stream, which you can then analyze like a "normal-quality" PRNG. $\endgroup$ – Mikko_K_123 Jan 8 '17 at 18:39
  • $\begingroup$ An independent and easy approach would be to try to find repeating chunks of symbols. Say you find that "ABCDE" appears more often than expected, then even if expected value of E is, say 10%, after seeing "ABCD", you would be able to tell with likelihood > 10% that the next symbol is "E". $\endgroup$ – Mikko_K_123 Jan 8 '17 at 18:42

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.