Random Number Generators for Cryptography Viktor Fischer, Patrick Haddad

Circuits and Systems for Security and Privacy

Farhana Sheikh, Leonel Sousa

chapter 7

Abstract : Random number generators (RNGs) are computational or physical functions generating a sequence of bits or symbols (e.g. groups of bits - numbers) that do not feature any pattern - generated bits or symbols (numbers) are independent and uniformly distributed. Random number generators have many applications in modern technologies. They are widely used in cryptography, but also in Monte Carlo simulations of complex systems, as noise generators in telecommunication systems, in games, slot machines, etc. Many methods of generating random numbers exist, starting from ancient methods using dice and coin flipping, sophisticated methods using quantum mechanics, up to modern principles that can be implemented in electronic systems and in particular in logic devices. Random numbers are crucial in cryptography: they are used as confidential keys, padding data, initialization vectors, nonces in challenge-response protocols, but also as random masks in side channel attack countermeasures. Since the era of Kerckhoff, the confidentiality of data is based on encryption keys: it is supposed that cryptographic algorithm is known to the adversary and that confidentiality is guaranteed only by a confidential key unknown to him. It is interesting to note that one of the simplest and the most secure encryption techniques called one time pad is entirely based on a direct use of random numbers. It can be proved that the one time pad cannot be broken if used correctly, i.e. if each of the generated random sequences is used only once. However, this information-theoretic guarantee only holds if these sequences come from a high quality random source with high entropy. Compared to other application areas, except for good statistical quality and knowledge of the distribution of generated random numbers, cryptography applications have strong security requirements - random number generators must be cryptographically secure. Cryptographically secure random number generators must generate random numbers that have good statistical quality and the generated sequences must not be predictable and manipulable. In cryptographic applications, for security reasons, cryptographic keys and other security critical data must be generated inside cryptographic modules and in particular inside semiconductor devices if the cryptographic module is implemented as a cryptographic system on a chip (e.g. in smartcards). For this reason, we will deal only with generators that can be implemented inside digital devices.

Table of Contents

Introduction
Farhana Sheikh and Leonel Sousa

Mathematics and Cryptography
David O. Novick

Block Ciphers
Deniz Toz, Josep Balasch, and Farhana Sheikh

Secure Hashing: SHA-1, SHA-2, and SHA-3
Ricardo Chaves, Leonel Sousa, Nicolas Sklavos, Apostolos P. Fournaris, Georgina Kalogeridou, Paris Kitsos, and Farhana Sheikh

Public Key Cryptography
Nathaniel Pinckney, David Money Harris, Nan Jiang, Kyle Kelley, Samuel Antao, and Leonel Sousa

Physically Unclonable Functions: A Window into CMOS Process Variations
Raghavan Kumar, Xiaolin Xu, Wayne Burleson, Sami Rosenblatt, and Toshiaki Kirihata

Random Number Generators for Cryptography
Viktor Fischer and Patrick Haddad

Side-Channel Attacks
Josep Balasch, Oscar Reparaz, Ingrid Verbauwhede, Sorin A. Huss, Kai Rohde, Marc Stöttinger, and Michael Zohne

Remarks and Conclusion
Farhana Sheikh and Leonel Sousa