Security and performance of RNG on modern OS

AI Quick Summary

Random number generators (RNG) are used everywhere nowadays, and they are a critical component for modern cryptography. For example, they are use to initialize vectors, during key-agreement schemes, in the process of creating pairs of keys for asymmetric encryption protocols, and so on. If you break the RNG, most of the times you are breaking the whole security system. For more details, check the long description. Initial situation and problem definitionRandom number generators (RNG) are used everywhere nowadays, and they are a critical component for modern cryptography. For example, they are used to initialize vectors, during key-agreement schemes, in the process of creating pairs of keys for asymmetric encryption protocols, and so on. If you break the RNG, most of the times you are breaking the whole security system.Computers are very predictable devices. Hence, it is extremely hard to produce "truly" random numbers on them, as opposed to pseudorandom numbers which can be easily generated with an algorithm. However, attackers can just as easily guess the sequence of PRNG, and this is not acceptable in cryptographic applications.Fundamentally, it is not possible to get truly random numbers from non-random devices such as a computer. Therefore, similar to other computational security protocols, when we argue if a RNG is secure or not, we rely on assumptions about the difficulty for an adversary to predict future outputs given knowledge on previous ones.How can we analyze RNG that claim to be cryptographically secure? How are these RNG initialized? What are the actual RNG used by OS nowadays? Are there any known attacks on RNG? What about standards or certifications? How can we measure their performance?Aim of the work and expected resultsThis bachelor thesis will cover the following points:Research about random number generation in general (RNG, PRNG, CPRNG, etc.), with special emphasis on cryptographically secure random number generatorsStudy how random numbers are generated in linux. In particular, explore the random.c driver, the /dev/random pseudo-device and the entropy poolInvestigate recent merged changes to the random.c driver (for the future linux 5.17 release) and their impact to performanceExplore LRNG, a 5 year ongoing effort by Stephan Müller to replace /dev/random on linux with a more efficient RNG and compliant to the recommendation of FIPS 140-2Compare Linux' RNG with other well-known and widely used generators such as Fortuna (FreeBSD, macOS)Explore hardware random number generator (HRNG)Try out randomness tests (e.g. NIST SP 800-22, TestU01, Dieharder) on a selection of RNGStudy previous and well known attacks and, maybe, find additional issues in current RNG implementationsAnd the expected results:A better understanding of the RNG panorama on modern OSA performance benchmark of the random.c driver with linux <=5.16 and linux 5.17A benchmark comparing quality and performance of a selection of RNGA written thesis with an overview of RNG, randomness tests and benchmark resultsCreativity, variations, innovationFrom all the points mentioned above, more emphasis will be put on those where the student has more interest (e.g. Fortuna over the new LRNG, or the other way around). The student is also welcome to find and propose additional RNG or statistical test suites to check.ReferencesSome lecture notes on PRNG, CRNG and cryptographySlides chapter 6 from Modeling and Performance Analysis with Simulation (Mesut Günes, Freie Universität Berlin)Lecture 10 from Spectral Graph Theory (Thomas Sauerwald and He Sun, Max Planck Institut)Chapter 3 from Math 577-002 - Monte Carlo Methods (Tom Kennedy, University of Arizona)Lectures 7-9 from Introduction to Cryptography (Vipul Goyal, Carnegie Mellon University)Zvi Gutterman, Benny Pinkas. Analysis of the Linux Random Number Generator. IEEE Symposium on Security and Privacy (2006)Patrick Lacharme, Andrea Röck, Vincent Strubel, Marion Videau. The Linux Pseudorandom Number Generator Revisited (2012)Stephan Müller. Linux Random Number Generator. A New Approach (2021)John Kelsey, Bruce Schneier, David Wagner, Chris Hall. Cryptanalytic Attacks on Pseudorandom Number Generators. Lecture Notes in Computer Science, vol. 1372 (1988)NIST Special Publication 800-90A, 800-90B and 800-90C

Project Idea Metadata

• Project Idea Name: Security and performance of RNG on modern OS
• Date: 11/23/2021 1:40:55 PM
• Administrators:
  • Iyan Mendez Veiga

Project Idea Description

Initial situation and problem definition

Random number generators (RNG) are used everywhere nowadays, and they are a critical component for modern cryptography. For example, they are used to initialize vectors, during key-agreement schemes, in the process of creating pairs of keys for asymmetric encryption protocols, and so on. If you break the RNG, most of the times you are breaking the whole security system.

Computers are very predictable devices. Hence, it is extremely hard to produce "truly" random numbers on them, as opposed to pseudorandom numbers which can be easily generated with an algorithm. However, attackers can just as easily guess the sequence of PRNG, and this is not acceptable in cryptographic applications.

Fundamentally, it is not possible to get truly random numbers from non-random devices such as a computer. Therefore, similar to other computational security protocols, when we argue if a RNG is secure or not, we rely on assumptions about the difficulty for an adversary to predict future outputs given knowledge on previous ones.

How can we analyze RNG that claim to be cryptographically secure? How are these RNG initialized? What are the actual RNG used by OS nowadays? Are there any known attacks on RNG? What about standards or certifications? How can we measure their performance?

Aim of the work and expected results

This bachelor thesis will cover the following points:

• Research about random number generation in general (RNG, PRNG, CPRNG, etc.), with special emphasis on cryptographically secure random number generators
• Study how random numbers are generated in linux. In particular, explore the random.c driver, the /dev/random pseudo-device and the entropy pool
• Investigate recent merged changes to the random.c driver (for the future linux 5.17 release) and their impact to performance
• Explore LRNG, a 5 year ongoing effort by Stephan Müller to replace /dev/random on linux with a more efficient RNG and compliant to the recommendation of FIPS 140-2
• Compare Linux' RNG with other well-known and widely used generators such as Fortuna (FreeBSD, macOS)
• Explore hardware random number generator (HRNG)
• Try out randomness tests (e.g. NIST SP 800-22, TestU01, Dieharder) on a selection of RNG
• Study previous and well known attacks and, maybe, find additional issues in current RNG implementations

And the expected results:

• A better understanding of the RNG panorama on modern OS
• A performance benchmark of the random.c driver with linux <=5.16 and linux 5.17
• A benchmark comparing quality and performance of a selection of RNG
• A written thesis with an overview of RNG, randomness tests and benchmark results

Creativity, variations, innovation

From all the points mentioned above, more emphasis will be put on those where the student has more interest (e.g. Fortuna over the new LRNG, or the other way around). The student is also welcome to find and propose additional RNG or statistical test suites to check.

References

• Some lecture notes on PRNG, CRNG and cryptography
• Slides chapter 6 from Modeling and Performance Analysis with Simulation (Mesut Günes, Freie Universität Berlin)
• Lecture 10 from Spectral Graph Theory (Thomas Sauerwald and He Sun, Max Planck Institut)
• Chapter 3 from Math 577-002 - Monte Carlo Methods (Tom Kennedy, University of Arizona)
• Lectures 7-9 from Introduction to Cryptography (Vipul Goyal, Carnegie Mellon University)
• Zvi Gutterman, Benny Pinkas. Analysis of the Linux Random Number Generator. IEEE Symposium on Security and Privacy (2006)
• Patrick Lacharme, Andrea Röck, Vincent Strubel, Marion Videau. The Linux Pseudorandom Number Generator Revisited (2012)
• Stephan Müller. Linux Random Number Generator. A New Approach (2021)
• John Kelsey, Bruce Schneier, David Wagner, Chris Hall. Cryptanalytic Attacks on Pseudorandom Number Generators. Lecture Notes in Computer Science, vol. 1372 (1988)
• NIST Special Publication 800-90A, 800-90B and 800-90C

Random number generators (RNG) are used everywhere nowadays, and they are a critical component for modern cryptography. For example, they are use to initialize vectors, during key-agreement schemes, in the process of creating pairs of keys for asymmetric encryption protocols, and so on. If you break the RNG, most of the times you are breaking the whole security system.

For more details, check the long description.