6

I'm creating an internal security course for developers. To make it more interesting, I'm trying to reinforce each chapter with some real-world attacks but stumbled upon insecure random usage section.

So, let's assume that out-of-the-box RNG (any popular backend language is okay) is used in an insecure manner (for example, for generating passwords functionality). Is there any step-by-step algorithm or automatic tool that can calculate RNG state and previous/future values?

getupandgo
  • 63
  • 6
  • 2
    For a real world example, you might be interested in the Debian not-so-random SSH keys fiasco: https://research.swtch.com/openssl (many other blog articles can be found on this incident) – A. Hersean Nov 29 '18 at 15:21
  • 1
    @A.Hersean I thought of that, but that was more about improperly seeding a CSPRNG rather than using a PRNG instead of a CSPRNG. I'd look into stuff for the Mersenne Twister (maybe [this](https://github.com/fx5/not_random)?) – AndrolGenhald Nov 29 '18 at 15:23

4 Answers4

3

Insecure use PRNG: An extremely naive demonstration of this (if you want to do a lab) is to use a seed derived from the current time to generate a Pseudo Random password for an open source password manager (you could add in some other bit of knowable information if you want to make it look more random). If the students notice this fact in the source they could predict passwords. Of course the source isn't actually needed to determine this information ( it would just speed up the lab)

for well known real world examples check out https://en.wikipedia.org/wiki/Random_number_generator_attack

DarkMatter
  • 2,671
  • 2
  • 5
  • 23
  • 2
    I like this answer because there is no high learning curve (no crypt-analysis required) and it is quite common to have non-secure RNG's to be based on current time. Note that sometimes that even breaks the requirements of a non-secure RNG by the way, CPU's are terribly quick so if you use multiple threads started at the same time you get synchronized RNG's. – Maarten Bodewes Nov 29 '18 at 18:39
  • 2
    There was also a problem where the Debian devs found a possible vulnerability wrt using unprotected memory in OpenSSL. So they tried to put a stop to it by fixing the code - disabling *all* entropy sources for the OpenSSL random number generator *other than the process ID*. The read of the uninitialized data was actually used as an entropy source of sorts. Description of this old "whoops" on [the Schneider security blog](https://www.schneier.com/blog/archives/2008/05/random_number_b.html). This is rather similar to just using the current time, only worse. – Maarten Bodewes Nov 30 '18 at 07:48
3

Yes, there is. See Factorable for a famous example where RSA and DSA keys were generated by embedded devices immediately as they booted up when insufficient randomness was collected:

We performed a large-scale study of RSA and DSA cryptographic keys in use on the Internet and discovered that significant numbers of keys are insecure due to insufficient randomness. These keys are being used to secure TLS (HTTPS) and SSH connections for hundreds of thousands of hosts.

Nearly all the vulnerable hosts are headless and embedded network devices, such as routers, firewalls, and server management cards. These types of devices often generate keys automatically on first boot, and lack many of the physical sources of randomness used by traditional PCs to generate random numbers. We identified apparently vulnerable devices and software from 54 manufacturers and notified these companies about the problems.

Read their research paper to see exactly how they did this.

forest
  • 64,616
  • 20
  • 206
  • 257
2

Some of the PRNG algorithms standard in programming languages can be broken after enough samples are seen. Refer to https://security.stackexchange.com/a/31645/192426 for a description and link to an example script.

Jonathan
  • 103
  • 3
2

The attack I'm going to describe is a bit different from the ones mentioned in other answers, insofar as it would be a hardware-based attack, and insofar as it would take years of planning and significant financial clout. It also represents a non-algorithmic kind of PRNG failure, which is probably where it's most-applicable to your class: basing all of your entropy on only one source can backfire if that entropy can be poisoned.

Theoretically, you could create a piece of hardware that generates numbers per an algorithm that you know, and then sell that hardware while claiming that it is a true RNG. Any code that uses that hardware to generate all of its entropy would be easily attackable by the maker of that hardware.

(While this may seem fantastical, there is legitimate concern that such a situation could occur in real life, such as with Intel's RdRand instruction.)

Miles B Huff
  • 150
  • 1
  • 13
  • 1
    Is rumored to contain backdoors, or "some people are afraid it might contain backdoors"? Anyway, -1 because this doesn't answer the question and just says whether or not it is possible to backdoor an RNG. Note also that you're incorrect wrt the claim "proportional to how much [...]". In reality, all you need is 128 good bits of unpredictable entropy, and then even a trillion bits from a bad RNG mixed into the pool won't cause any harm. – forest Dec 01 '18 at 05:05
  • I'm not sure how "rumoured to contain" differs from "people being afraid it might contain". Backdooring an RNG allows you, the backdoorer, to attack any PRNGs that uses it exclusively or nigh-exclusively -- *backdooring can still result in an attack*. The "out-of-the-box RNG" from the question would in this case be /dev/random, and the "popular backend language" could be any number of things. So in those respects, I don't see how this *doesn't* answer the question. – Miles B Huff Dec 01 '18 at 05:13
  • 2
    Then I retract my pedantry. However, OP is asking about RNG failure (correlated outputs, etc.), not intentional RNG backdoors. Your "proportional to" claim is incorrect as well. – forest Dec 01 '18 at 05:15
  • It *is* roughly proportional, when averaged out over many runs -- but you're right that that wasn't the best description. Nevertheless, no-one creates trillion-bit keys. In a typical 128-bit key, every bit that came from the fake RNG is one less bit of good encryption, at least insofar as you can guess relatively well which bits came from the fake RNG. The rest can be bruteforced. – Miles B Huff Dec 01 '18 at 05:17
  • That is incorrect. I wasn't talking about trillion bit keys, but a hypothetical trillion bits of non-randomness injected into the pool. With entropy mixing (which is implied by the use of the term entropy pool), all that matters is having _at least_ 128 good bits. It doesn't matter how many bad bits are injected into the pool. For example, if you take 128 bits from an entropy pool which was fed 128 bits of randomness from dice, and 10^12 bits of randomness from a backdoored RNG, the key would still be secure. – forest Dec 01 '18 at 05:18
  • I think I see what you're saying. So if there's entropy mixing, then the whole pool is as good as the amount of true random data. The stream that we get from /dev/random would be post-mixing. So the attack here would more-or-less depend on 100% of the entropy coming from the fake RNG. Should I edit my answer to reflect this, removing the "proportional" part in the process? Or should I leave my answer as-is, for posterity? – Miles B Huff Dec 01 '18 at 05:22
  • 2
    I think removing the proportional comment would be good, or expanding upon it to explain that the amount of entropy from the pool is equivalent to the most entropic source, no less. – forest Dec 01 '18 at 05:24
  • Okay, done. I also revised the comment more generally, to try and relate it more directly to the class, with a specific moral-to-the-story for the students. I also made the real-life example seem less absolute, and morphed it into a kind of footnote. – Miles B Huff Dec 01 '18 at 05:36
  • 2
    It's a lot better now! I've changed my downvote into an upvote. :) – forest Dec 01 '18 at 05:38
  • 2
    Thanks for helping me to make the answer more useful! :) – Miles B Huff Dec 01 '18 at 05:39