srandom is not secure (README.md bugs)

[atoponce]

The README.md file make false claims about security:

srandom is a Linux kernel module that can be used to replace the built-in /dev/urandom & /dev/random device files.
...
It is secure.
...
still produces excellent random numbers that is indistinguishable from true random numbers.
...
Generating random numbers which is indistinguishable from true randomness is the goal here
...
Any security type applications rely heavily on random numbers. For example, Apache SSL (Secure Socket Level), PGP (Pretty Good Privacy), VPN (Virtual Private Networks). All types of Encryption, Password seeds, Tokens would rely on a source of random number.
...
Using /dev/srandom to securely wipe SSD disks.

The xorshift family of PRNGs are not secure. Observing enough output can predict all future output with 100% accuracy. They should not be used for anything where security is required, such as cryptographic keys.

Some resources:

• "For execution in software, xorshift generators are among the fastest non-cryptographically-secure random number generators."
• "This post discussed how the xorshift128 PRNG works and how to build a machine learning model that can learn from the PRNG’s “randomly” generated numbers to predict them with 100% accuracy."
• "xoshiro256++/xoshiro256** (XOR/shift/rotate) are our all-purpose generators (not cryptographically secure generators, though, like all PRNGs in these pages)."
• "5.1 Xorshift. Xorshift is not cryptographically secure due to its design. The next and previous numbers can easily be predicted due to their linear structure.." (PDF)
• "Some of the drawbacks of xorshift include its lack of cryptological security." (PDF)

When you run "make install", the srandom kernel module is moved to /usr/lib/modules/.../kernel/drivers/. If you run "make load" or reboot, the kernel module will be loaded into the running kernel, but now will replace the /dev/urandom device file. The old /dev/urandom device is renamed (keeping it's inode number). This allows any running process that had /dev/urandom to continue running without issues. All new requests for /dev/urandom will use the srandom kernel module.

It's fine to create a separate kernel module for insecure PRNG needs, but it should not be replacing the cryptographically secure /dev/urandom.

Also, because xorshift is not cryptographically secure, the following is very dangerous security practice:

Java: Use the following command line argument to tell Java to use the new random device

-Djava.security.egd=file:///dev/srandom switch
    or
-Djava.security.egd=file:/dev/./srandom

Java: To make the setting as default, add the following line to the configuration file. ($JAVA_HOME/jre/lib/security/java.security)

securerandom.source=file:/dev/./srandom

https: (Apache SSL), Configure /etc/httpd/conf.d/ssl.conf

SSLRandomSeed startup file:/dev/srandom 512
SSLRandomSeed connect file:/dev/srandom 512

Postfix: Change the following line in /etc/postfix/main.cf

tls_random_source = dev:/dev/srandom

PHP: Change the following line in PHP config file.

session.entropy_file = /dev/srandom

OpenLDAP: Change the following line in /etc/openldap/slapd.conf

TLSRandFile /dev/srandom

A lot of development has changed with random.c in the Linux kernel since this README.md was initially written.

My tests show it can be over 150x faster then /dev/urandom.

   time dd if=/dev/urandom of=/dev/null count=64k bs=64k
   
   65536+0 records in
   65536+0 records out
   4294967296 bytes (4.3 GB) copied, 277.96 s, 15.5 MB/s
   
   real    4m37.961s
   user    0m0.028s
   sys     4m37.923s

Since Linux 4.8 (released in 2016), the RNG primitive replaced SHA-1 with ChaCha20. This produced a significant speed improvement:

$ dd if=/dev/urandom of=/dev/null count=64k bs=64k
65536+0 records in
65536+0 records out
4294967296 bytes (4.3 GB, 4.0 GiB) copied, 9.79351 s, 439 MB/s

/dev/random (the true random number generator) is BLOCKED most of the time waiting for more entropy makeing it basically unusable. The PRNG /dev/urandom is unblocked, but is very slow when compared to srandom.

/dev/random has never been a true random number generator. Both /dev/random and /dev/urandom are userspace device files that were exported from the same CSPRNG. The only difference being that /dev/random prviously would block producing bytes when its output entropy pool size dropped below the input entropy pool size. /dev/urandom did not have such a check and as such would always produce random bytes.

The "Blocking" random number generator. ( I pressed [CTRL-C] after 5 minutes and got 35 bytes!) If you really NEED true random numbers, you would need to purchase a true random number device.)

   time dd if=/dev/random of=/dev/null count=64k bs=64k
   [CTRL]-C
   0+35 records in
   0+0 records out
   0 bytes (0 B) copied, 325.303 s, 0.0 kB/s
   
   real    5m25.306s
   user    0m0.001s
   sys     0m0.003s

Further, since Linux 5.6 (released 2020), the /dev/random device file no longer blocks.

$ dd if=/dev/random of=/dev/null count=64k bs=64k
65536+0 records in
65536+0 records out
4294967296 bytes (4.3 GB, 4.0 GiB) copied, 9.64281 s, 445 MB/s

[josenk]

1. None of your resource are relevant when it's implemented the way I have... Of course, if you have any single single XOR prg seeded once, it will be predictable. But srandom has two PRNGs that are XOR'd together using different algorithims. The two PRNGs are randomly re-seeded using the last bits of the nano timer. The random data is buffered and fed to you in random order, etc...

2. I have a challenge that has been available since 2019. Be my guest to predict all future output with 100% accuracy.

I do agree that some of the documentation may be outdated. (unblocked /dev/random, for example).

[atoponce]

The resources show that xorshift is not cryptographically secure. So if you're using it to build a cryptographic primitive, you need to supply a proof of its security, which I don't see in your README. XORing two independent xorshift64 RNGs and discarding output likely isn't enough.

[josenk]

Nobody can really prove anything. It needs to be disproved.

https://github.com/josenk/srandom/releases/tag/1.37 (I challenge you to solve the challenge)

The closest I have to prove it provides random numbers is that it passes dieharder, which is well documented in the README.

[atoponce]

Nobody can really prove anything. It needs to be disproved.

That's not true. Provable security is what you need to provide here. You've taken an insecure RNG and claimed that your construction is secure. However, you haven't provided any formal arguments in how. You haven't threat modeled the RNG showing how the state cannot be recovered from observing the output, which would be the bare minimum here.

https://github.com/josenk/srandom/releases/tag/1.37 (I challenge you to solve the challenge)

I'm not the one claiming it's secure, so I don't need to prove anything or participate in any challenge. As stated, you've taken an insecure RNG and built a construction that you claim is secure. As such, the burden of proof rests on you. If you can't supply such a proof, then we can assume that it's not secure by falling back on the insecure primitive you chose.

The closest I have to prove it provides random numbers is that it passes dieharder, which is well documented in the README.

Randomness tests such as Dieharder, NIST, TestU01, and PractRand don't prove security, only randomness. Plenty of insecure RNGs will pass randomness tests with flying colors while still remaining insecure. Mersenne Twister, PCG family, xorshift family, WELL family, multiply-with-carry, and plenty others are evidence of this.

[Sc00bz]

I have a challenge that has been available since 2019. Be my guest to predict all future output with 100% accuracy.

That's not how CSPRNGs work. It's you are given any reasonable amount of data (think 1 TiB) before and after, a reasonable amount of time (think 2^64), and you need to guess a bit at >50% probability. See https://github.com/Sc00bz/break-uheprng... oh right I improved it. Anyway an older version didn't try to guess the carry bit. So it was guessing a 53 bit int of either x or x+1 at 100% accuracy. Which would fail your challenge, but is obviously broken.

Nobody can really prove anything. It needs to be disproved. [...] The closest I have to prove it provides random numbers is that it passes dieharder [...]

No, UHEPRNG passes dieharder. Also this code passes all random tests but is obviously broken in a similar way that UHEPRNG is broken:

uint32_t getRandomInt(const void *seed = NULL, size_t seedSize = 0)
{
  static uint32_t data[8] = {0};
  static uint32_t intsLeft = 0;

  if (seed != NULL)
  {
    sha256(data, seed, seedSize);
    intsLeft = 8;
  }
  if (intsLeft == 0)
  {
    sha256(data, data, sizeof(data));
    intsLeft = 8;
  }
  return data[--intsLeft];
}

void sha256(void *out, const void *in, size_t inSize)
{
  ...
}

It uses 16 x 512byte buffers and outputs them randomly.

From README.md. Yeah that sounds like a timing attack. Assuming it can't be attacked in other ways.

---

Also "anyone can create something that they themselves can't break, but that doesn't mean it's secure" or something like that.

[atoponce]

Also "anyone can create something that they themselves can't break, but that doesn't mean it's secure" or something like that.

Shneier's Law: https://www.schneier.com/blog/archives/2011/04/schneiers_law.html

[josenk]

I'll assume your done ranting...

[atoponce]

It's unfortunate you're closing the ticket without addressing the security concerns. You're unfortunately putting your users at high risk.

You claim you've made a cryptographically secure RNG by taking xorshift64 and xoring it with another xorshift64 instance and discarding bits, but haven't provided any evidence to backup that claim. This isn't how secure programming or cryptography works.

Using your kernel module for security is dangerous.

[Sc00bz]

#14 Looks like it's broken.