Speakers
Jithra Adikari, Farhad Haghighizadeh and Xiao Ma
Topic
Designing, Implementing and Validating Random Bit Generators
Abstract
The National Institute of Standards and Technology (NIST) and the Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik – BSI) have published recommendations for designing, implementing and validating true random bit generators (non-deterministic random bit generators -NRBG) and pseudo random bit generators (deterministic random bit generators – DRBG) in Special Publications (SP) 80090a/b/c (all in drafts) and Application Notes and Interpretations of the Scheme (Anwendungshinweise und Interpretationen – AIS) 20/31 documents, respectively. According to SP800-90's and AIS recommendations, a random bit generator has three main components namely, an entropy source, a DRBG, and on-line health test circuits.
The entropy source is the heart of a random bit generator. It includes a noise source which generates random bits by a non-deterministic process in a probabilistic manner, and a filtering mechanism which makes the output bit stream of noise source unbiased. Then the output of noise source is fed into a conditioning circuit to generate independent and identically distributed (IID) data using either symmetric encryption, hash function or number theoretic algorithm. An output bit stream of a random bit generator is considered as IID data if each element of the bit sequence has the same probability distribution as the other values and all values are mutually independent.
Output data rate of an entropy source cannot match the demand of higher data rate applications, because generating a new random number from an entropy source takes a relatively long period. However, a DRBG seeded by an entropy source can be used to achieve higher throughput. A DRBG is a pseudo-random bit generator that produces a sequence of IID data using a secret seed acquired from the entropy source. The output of the DRBG is completely predictable if the seed is compromised. From a security perspective, a DRBG should be re-seeded with sufficient entropy at intervals. Finally, additional health circuits are introduced to monitor the quality of the randomness of the generated bit stream. This is achieved by measuring basic statistical properties of the random bit stream in real-time. The known answer test (KAT) is performed on output bit stream to verify the functionality of the DRBG. The KAT uses predefined input vectors and compares the actual output with expected value to detect faults/errors in datapath.
On-line health tests have limited capabilities to validate the randomness in a bit stream generated by a random bit generator. Hence, several instances of random bit generators are implemented to collect data for a long period (several weeks) in our lab environment. This set-up accumulates data in several tens/hundreds of gigabytes that can be used to feed into statistical testing tools to validate the randomness. The diehard test suite by George Marsaglia and in house developed test suite based on statistical tests specified in both SP800-90 and AIS publications are used as validation platform tools.
Speaker's biographies
Jithra Adikari received the B.Sc. degree in electronic and telecommunication engineering from the University of Moratuwa, Moratuwa, Sri Lanka, and the M.Sc. degree in Information and Communication Systems Security from the Royal Institute of Technology (KTH), Stockholm, Sweden. He received Ph.D. degree in electrical engineering from the University of Calgary, Alberta, Canada in 2010. He worked as a Postdoctoral Fellow at the Department of Electrical and Computer Engineering at the University of Waterloo, Ontario, Canada from 2010 to 2011. Currently, Dr. Adikari is working as a Senior ASIC Designer/Architect at Elliptic Technologies Inc. Ottawa, Ontario, Canada.
Farhad Haghighizadeh received his B.Sc. in Electrical Engineering from Sharif University of Technology, Tehran, Iran in 2010 and his M.A.Sc. degree in Electrical and Computer Engineering from the University of Waterloo, Ontario, Canada in 2012. Farhad joined Insight Design Labs Inc., Ottawa, Ontario, Canada in 2013 and worked there as a Design Engineer. He joined Elliptic Technologies Inc., Ottawa, Ontario, Canada in the same year where, he is currently working as an ASIC Designer/Architect.
Xiao Ma is a doctoral student at the Department of Electrical and Computer Engineering at the University of Waterloo under the supervision of Dr. Anwar Hasan. He has been working on random number generator projects during his internship at Elliptic Technologies Inc. Ottawa, Ontario, Canada.
Invited by Professor Anwar Hasan.