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?

  • 2
    For a real world example, you might be interested in the Debian not-so-random SSH keys fiasco: 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?) – AndrolGenhald Nov 29 '18 at 15:23
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

  • 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. This is rather similar to just using the current time, only worse. – Maarten Bodewes Nov 30 '18 at 7: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.

  • 1
    and, the NSA RSA DUAL_EC_DRBG. – kelalaka Nov 30 '18 at 21:15
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.

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.)

  • 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 1 '18 at 5:05
  • 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 1 '18 at 5:15
  • 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 1 '18 at 5:24
  • 2
    It's a lot better now! I've changed my downvote into an upvote. :) – forest Dec 1 '18 at 5:38
  • 2
    Thanks for helping me to make the answer more useful! :) – Miles B Huff Dec 1 '18 at 5:39

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.