19
$\begingroup$

This happened during a discussion of RNG entropy, and the difficulty of verifying the level of entropy in a long sequence of bits (e.g. a private key.)

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from. As an example, he told me that he had submitted data from OpenSSL's random number generator and the website had identified "Open SSL" as the source.

This was about three years ago. He encountered the website at a previous company he worked at.

I can't find this site by googling, and my colleague may not be able to find the URL (he's looking it up.) Not surprisingly, I'm very worried if the output from supposedly-cryptographically-secure-PRNGs is vulnerable to a distinguisher attack with trivial complexity!

If anyone here recognises this website, could they please post an answer containing its URL?

Improve this question
$\endgroup$
3
  • 10
    $\begingroup$ Although there is nothing inherently wrong with the question, the problem is that it specifies an unknown website, and it is not clear at all what it does. It could well return OpenSSL if it cannot find any distinguishing features that would indicate an insecure algorithm. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 31, 2020 at 21:35
  • 1
    $\begingroup$ @MaartenBodewes Luckily, it turned out that the website was a proof-of-concept for research that could identify the piece of software that had created a given RSA modulus. RNG weaknesses were only a very small part of the methodology used. This being the case, I'd like your opinion as a diamond mod - should I edit the question, since it's turned out to be based on a flawed premise? $\endgroup$
    – AJM
    Commented Apr 1, 2020 at 10:03
  • 1
    $\begingroup$ No, not necessary. I guess that it is clear from the comments and the answers what the situation is. $\endgroup$
    – Maarten Bodewes ♦
    Commented Apr 1, 2020 at 11:49

2 Answers 2

Reset to default
32
$\begingroup$

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from.

As you correctly identified this would present an immediate and probably devastating attack to any cryptographic PRNG as it indeed would allow you to easily distinguish a random string from a PRNG output, something cryptographers try to make impossible efficiently.

However, there might be some truth to the story. Here are the two cases I know of where it would be possible:

  • The website identifies the output to be from the infamous OpenSSL Debian bug.
  • The site is given an RSA public key and can tell which implementation produced it as the prime-search strategies vary a bit in a secure way between different libraries. This was presented at Usenix Security 2016 (PDF) and perhaps someone converted this into a website.
Improve this answer
$\endgroup$
1
  • 8
    $\begingroup$ Thankfully, it turned out that it was the proof-of-concept website for the Usenix 2016 research - rsa.sekan.eu - and that this relied on a lot of quirks in RSA key generation that weren't related to RNG weaknesses. (Or at least, most of them weren't.) I can now stop worrying! $\endgroup$
    – AJM
    Commented Apr 1, 2020 at 9:59
29
$\begingroup$

One tool that tries to do this is untwister. It's almost certainly not the tool you were thinking of, though, as it cannot determine if the output came from OpenSSL specifically.

It can determine Glibc's rand(), Mersenne Twister (MT19937), PHP's MT-variant (php_mt_rand), Ruby's MT-variant DEFAULT::rand(), and Java's Random() class, though, and can recover the seed, thereby allowing you to predict future output.

All these are however insecure random bit generators; the name of the website (after the Mersenne Twister no doubt) means that it likely won't be able to distinguish secure random number generators.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Thanks. Fortunately, it turned out that there were some crossed wires, and the website was in fact taking RSA moduli as input and identifying the software that produced them - see crocs.fi.muni.cz/public/papers/usenix2016 $\endgroup$
    – AJM
    Commented Apr 1, 2020 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.