3 ms·

Are there accessible techniques to establish if a number sequence is from a good RNG or not? I appreciate that people are probably bad judges of randomness but

Are there accessible techniques to establish if a number sequence is from a good RNG or not? I appreciate that people are probably bad judges of randomness but I keep noticing odd patterns with a supposedly random number generated as part of an MFA process.. I'm interested in seeing if there's a problem or if it's actually working effectively. What terms should I search for to find out more on this?

deleted 3y ago
[deleted]
sweetjuly 3y ago
For CSPRNGs, we tend to use hardness proofs (i.e. prove that an attacker cannot predict the CSPRNG output in polynomial time). To understand these, you'll need to figure out what the algorithm in use is. This isn't particularly relevant to TOTPs since they are built on unforgeable message authentication codes (TOTP usually uses HMAC) so the proof would usually be less about predicting a bit (though, if you could, that would be a valid security break) and more about proving an attacker cannot forge a signature on a message without violating the hardness assumptions. For regular ol PRNGs (i.e. non-cryptographically secure), there are various tools [1] which let you feed in enormous amounts of samples and then automatically apply a variety of known techniques to try to find correlations. But, generally, you wouldn't expect a PRNG to pass these tests. Instead, you should focus on getting a distribution and behavior that is helpful to your use case. [1] https://pracrand.sourceforge.net/PractRand.txt https://pracrand.sourceforge.net/PractRand.txt
- nmstoker 3y ago
  Thanks a lot - this is helpful!
nneonneo 3y ago
Hah, if you’re referring to the fact that repetitive digits show up in 2FA codes, this is a great example of a randomness illusion. Of the 1000000 possible 6-digit numbers: 151200 have six unique digits 453600 have five unique digits 327600 have four unique digits 64800 have three unique digits 2790 have two unique digits 10 have only one unique digit Almost 40% of the time you will have a 2FA code that has at most four unique digits: it has two digits appear twice (e.g. 463426), or one digit appear thrice (e.g. 838819), etc. These look distinctly “non-random”, but appear frequently when using 2FA systems. In fact, having a number that “looks random” (has all unique digits) is comparatively uncommon at 15%; even in that set, there are many numbers with discernible patterns like “234719” and “136420”. Hence, if you find yourself believing that your 2FA codes look non-random, it’s probably an illusion. If you’re really uncertain, you could always record a large sample of codes and look for statistical anomalies.
- nmstoker 3y ago
  Good point - I definitely need to record them and see if the patterns are really there (it's possible I'm naively noticing only when it fits!)
loeg 3y ago
Sort of, but think many many samples. BigCrush / PractRand / DieHarder are all in this space. https://stackoverflow.com/questions/9780267/testing-the-quality-of-prngs https://stackoverflow.com/questions/9780267/testing-the-qual...

deleted 3y ago

[deleted]

sweetjuly 3y ago

For CSPRNGs, we tend to use hardness proofs (i.e. prove that an attacker cannot predict the CSPRNG output in polynomial time). To understand these, you'll need to figure out what the algorithm in use is. This isn't particularly relevant to TOTPs since they are built on unforgeable message authentication codes (TOTP usually uses HMAC) so the proof would usually be less about predicting a bit (though, if you could, that would be a valid security break) and more about proving an attacker cannot forge a signature on a message without violating the hardness assumptions. For regular ol PRNGs (i.e. non-cryptographically secure), there are various tools [1] which let you feed in enormous amounts of samples and then automatically apply a variety of known techniques to try to find correlations. But, generally, you wouldn't expect a PRNG to pass these tests. Instead, you should focus on getting a distribution and behavior that is helpful to your use case. [1] https://pracrand.sourceforge.net/PractRand.txt https://pracrand.sourceforge.net/PractRand.txt

nmstoker 3y ago
Thanks a lot - this is helpful!

nneonneo 3y ago

Hah, if you’re referring to the fact that repetitive digits show up in 2FA codes, this is a great example of a randomness illusion. Of the 1000000 possible 6-digit numbers: 151200 have six unique digits 453600 have five unique digits 327600 have four unique digits 64800 have three unique digits 2790 have two unique digits 10 have only one unique digit Almost 40% of the time you will have a 2FA code that has at most four unique digits: it has two digits appear twice (e.g. 463426), or one digit appear thrice (e.g. 838819), etc. These look distinctly “non-random”, but appear frequently when using 2FA systems. In fact, having a number that “looks random” (has all unique digits) is comparatively uncommon at 15%; even in that set, there are many numbers with discernible patterns like “234719” and “136420”. Hence, if you find yourself believing that your 2FA codes look non-random, it’s probably an illusion. If you’re really uncertain, you could always record a large sample of codes and look for statistical anomalies.

nmstoker 3y ago
Good point - I definitely need to record them and see if the patterns are really there (it's possible I'm naively noticing only when it fits!)

loeg 3y ago

Sort of, but think many many samples. BigCrush / PractRand / DieHarder are all in this space. https://stackoverflow.com/questions/9780267/testing-the-quality-of-prngs https://stackoverflow.com/questions/9780267/testing-the-qual...