rus
Issue #9/2018
Timoshin Sergey A., Nuykin Andrey V., Roldugina Zhanna I.
Developing and Using the Hardware Random Number Generator in the Structure of Secure Systems on Chip
Developing and Using the Hardware Random Number Generator in the Structure of Secure Systems on Chip
The article describes the features of designing and using a hardware random number generator as a part of secure systems on a chip. Generator’s block diagram is presented and the designed random number generator’s working principle is described. A comparative analysis of different methods of correction of the generated random sequence is presented and a research is done into their impact on the statistical properties of a random sequence obtained with the developed generator.
Today random number generators are widely used in microelectronic devices for various tasks, including the creation of cryptographic keys for secure data transmission. Due to their important function in devices, it is necessary for the elements of number sequence implemented by the generator to be independent of each other and have a uniform distribution.
These conditions are most accurately fulfilled for hardware random number generators. As off today one of the most secure integrated circuits using a hardware random number generator are payment and ID microprocessor-based smart cards with integrated non-volatile memory [1,2,3].
The operation of hardware random number generators is based on the measurement of physical process parameters that are randomly changing in time. The process can be described by classical or quantum physics. The probabilistic nature of quantum physics is more suitable as the basis for creating a similar device. However, these systems are currently suitable only for those areas where the reliability of random numbers is important to such an extent that it compensates for all material and intellectual efforts for these devices production. [4]
In cases where you want a wide practical application, the most suitable method is classical physics of macroscopic systems. Among these, such effects as tracking thermal noise in the resistor, the phase jitter in ring oscillators and others allow one to generate random number sequences. Such devices are simpler to be implemented and do not require special technology, but some factors, e.g. temperature, can affect the quality of the generated sequence.
The designed random number generator is a block that generates a random sequence of logic states at the unit output. Requirements for supply voltage correspond to the requirement voltage of the digital blocks. The current consumption is proportional to clock frequency (3.5µA at 10MHz). Limit clock frequency is 100MHz. Fig. 1 shows the symbolic designation of the developed block of the random number generator.
The generator output is out_rndgen. The input sel_rndgen is the pin for selecting random number generator circuit, input en_rndgen is the enable pin of the generator of random numbers, the input clk_rndgen is the pin for the clock signal. Fig. 2 shows the time diagram of the random number generator operation that illustrates the operation of the generator when signal from input en_rndgen is on or off. The switch-on time of the circuit is t0.
The current consumption of this block of the random number generator is less than 300mA, and the switching time is less than 1µs. This work deals with optimization of the circuit of the random number generator by current consumption and occupied area.
A study of generators of the random sequence in experimental samples and the composition of final products were conducted in the laboratory of IC development department of MERI JSC. The goal of this research is to estimate the functionality of generators of the random sequence, and to compare the functionality of the original and optimized random sequence.
The following equipment was used for measurements: power supply — GwInstek GPD-73303S, generator/analyzer of signal — Lecroy ArbStudio 1104, circuit board based on FPGA Xilinx Virtex-4. The sequence of data from the generator random sequence output with a length of 62500 bytes was collected using the generator/analyzer of signal — Lecroy ArbStudio 1104.
A significant problem of hardware random number generators is a large number of deviations, and correlations in the generated sequence. The processes themselves may be random, but problems can arise in the measurement process. Therefore it is necessary to correct the received sequence of random numbers for increasing the entropy with the probability of logic zero and logic one being approximately equal. There is a large number of correction methods of improving the quality of the sequence. The Von Neumann correction has been used in this work. The principle of this transformation is to split the original sequence into pairs of bits, and then select only those pairs where adjacent values are different, the pairs with the same value being removed. Specific values are assigned to selected pairs in the output sequence. Fig. 3 shows an example of such a transformation. In this example, the value 1 is assigned to the pair “10” and the value “0” is assigned to the pair “01”, the pairs “00” and “11” are deleted from the sequence.
As a result of the von Neumann correction the sequence is significantly reduced, and its statistical properties approach the properties of random sequences.
The sequence was investigated according to several parameters for the rapid assessment of the data quality. One of the most revealing criteria of random sequences is the probability of logical “0” and “1” in the sequence, which ideally is equal to 50 %. The next criterion was the degree of shrink of the sequence length during the von Neumann correction, which characterizes the uniformity of values distribution in the sequence. After the von Neumann correction the criterion of the degree of compression sequence by the archiver was used. The value of compression shows the absence or the presence of regularities discovered by the archiver. There should not be regularities in a random sequence, so the size of the compressed files should be not smaller than the source. There are clock generators in every complex digital circuit. Therefore it was decided to include the clock generator in the test crystal for the analysis of its influence on the quality of generated random sequence.
Random sequences obtained with original and optimized generators have been tested. Analysis of the results was carried out on nine samples of values. After the von Neumann correction the initial sequence decreased by a factor of 4–5.
Binary files of random numbers before compression had the following sizes: the source sequence is 62,500 bytes; the sequence after the von Neumann correction — 12,500 bytes. Data compression was performed using 7z with the following settings: archive format — zip compression, level — ultra, compression method is Deflate, size of dictionary — 32KB, word size is 128.
When the clock generator is off, the average size of the initial sequence after compression is 59458 bytes, which is 95 % of the original size. For a sequence obtained after the von Neumann correction, this number is 12245 bytes (98 %).
When the clock generator is on, the average size of the initial sequence after compression is 61754 bytes (98.8 %). For a sequence obtained after the von Neumann correction, this number is 12648 bytes (101.2 %).
The average size of the optimized sequence after compression when the clock generator is off is 60866 bytes (99.5 %). For the sequence obtained after the von Neumann correction, this number is 12633 bytes (101.1 %).
The average size of the optimized sequence after compression when the clock generator is on is 62216 bytes (98.8 %). For a sequence obtained after the von Neumann correction, this number is 12631 bytes (101 %).
Fig. 4 shows the sizes of files of compressed sequences obtained with original and optimized blocks of the random number generator, when the clock generator is disabled and enabled. For clarity the figure also illustrates the size of the original sequence.
Fig. 5 shows the file sizes of the compressed sequences obtained with the original and optimized blocks of the random number generator after the correction, when the clock generator is disabled and enabled. The size of the original sequence is also shown.
Fig. 6 shows the probability of logical one when the clock generator is off for the original and optimized sequences.
Fig. 7 shows the probability of logical one when the clock generator is on for the original and optimized sequences.
Due to the research it was found that the influence of the clock generator does not affect the statistical properties of the generated random sequence.
Different statistical tests are used for more accurate determination of the quality of the resulting random numbers. In general it is possible to highlight two classes of criteria: empirical criteria and theoretical criteria; the first being used for calculating some statistics from groups of random numbers, and the second — for analyzing the sequence of numbers by number-theoretic methods over recurrence rules that form random numbers [5].
There is a large number of software tools for testing the quality of random numbers. National Institute of Standards and Technology (NIST) has developed 15 tests for determining the random number. These tests are based on various statistical properties that are inherent only to random sequences. Another famous set of tests for the analysis of random sequences is a diehard test, which is one of the most stringent existing test suites. In this paper, tests from the dieharder package were used to check the properties of the sequence. The package contains 114 tests, including diehard, NIST, and other tests. The author contends that passing all the tests is impossible. The original and optimized generators were tested on the technologies of 180nm and 90nm.
The input test data may be both output of the generator and the input file with a sampling of random numbers. The dieharder package is very demanding as regards the amount of input data, so for the analysis large amounts of samples were collected. It is empirically established that the required minimum input for most tests is about 512 megabytes. Such a volume of random data was collected for each test sample. A volume of 1GB was collected for two additional samples. The result of dieharder tests for 1GB of data is similar to the package with volume of 512MB. The original sequence passed a small number of tests (2–3 of 114). An increase in entropy by the von Neumann correction led to the reduction of the sample by a factor of 12–14 (35–42MB) and increased the number of passed tests to 25–30 of 114.
For further analysis it was decided to encrypt the files with random numbers by the DES algorithm in the Electronic Codebook (ECB) mode with the keys “0”. As a result, sequences successfully passed 106 to 110 tests of 114. Thus, file encryption was selected as the most effective method of improving statistical properties of a random sequence.
The authors consider the following provisions and results as novel. The Von Neumann correction can only be used to assess the validity of the random number generator in the composition of the product; the evaluation criterion is the sample reduction by a factor not more than 16–18 times. To achieve a high quality random sequence it has been proposed to increase the entropy using an encryption block available in the composition of the crystal. As a result, product samples have been designed and manufactured using processes with minimal topological norms of 90nm and 180nm [6, 7].
REFERENCES
1. Krasnikov G. Ya., Gornev E. S. Razvitie poluprovodnikovoi mikroelektroniki OAO “NIIME i Mikron”, Istoriya otechestvennoi elektroniki: M.: 2012. T. 1. P. 539–563. (In Russian).
2. Krasnikov G. Ya., Shelepin N. A. “Sostoyanie i perspektivy razvitiya tekhnologii i elementnoi bazy SBIS s energonezavisimoi pamyat'yu”, Mezhdunarodnaya nauchno-tekhnicheskaya konferentsiya s elementami nauchnoi shkoly dlya molodezhi. M.: Zelenograd, 2010. (In Russian).
3. Timoshin S., Nuykin A., Kravtsov A. Extreme Low Cost Chip for HF RFID tag. 7th Annual IEEE International Conference on RFID, IEEE RFID 2013. Orlando, US — 2013.
4. Roldugina Zh. I., Nuikin A. V. Vliyanie vremeni modelirovaniya na statisticheskoe raspredelenie vykhodnykh znachenii signala apparatnogo generatora sluchainogo chisla // Mikroelektronika i informatika — 2017: sbornik statei. M.: MIET, 2017. P. 170–176. (In Russian).
5. Slepovichev I. I. Vvedenie v teoriyu generatorov psevdosluchainykh chisel. Saarbryukken: LAP LAMBERT Academic Publishing, 2016. 128 p. (In Russian).
6. Nuikin A. V., Kravtsov A. S. “Razrabotka i vnedrenie kristallov dlya smart-kart na rossiiskom i mezhdunarodnom rynkakh na osnove reshenii AO “NIIME” // Elektronnaya tekhnika. Seriya 3. Mikroelektronika. 2016. № 1(161). P. 4–8. (In Russian).
7. Nuikin A. V., Kravtsov A. S. “Perspektivy razvitiya sistem radiochastotnoi identifikatsii na osnove kart pamyati i mikroprotsessornykh kart”, Mezhdunarodnaya konferentsiya “Mikroelektronika 2015”. Krym, Alushta — 2015. (In Russian).
These conditions are most accurately fulfilled for hardware random number generators. As off today one of the most secure integrated circuits using a hardware random number generator are payment and ID microprocessor-based smart cards with integrated non-volatile memory [1,2,3].
The operation of hardware random number generators is based on the measurement of physical process parameters that are randomly changing in time. The process can be described by classical or quantum physics. The probabilistic nature of quantum physics is more suitable as the basis for creating a similar device. However, these systems are currently suitable only for those areas where the reliability of random numbers is important to such an extent that it compensates for all material and intellectual efforts for these devices production. [4]
In cases where you want a wide practical application, the most suitable method is classical physics of macroscopic systems. Among these, such effects as tracking thermal noise in the resistor, the phase jitter in ring oscillators and others allow one to generate random number sequences. Such devices are simpler to be implemented and do not require special technology, but some factors, e.g. temperature, can affect the quality of the generated sequence.
The designed random number generator is a block that generates a random sequence of logic states at the unit output. Requirements for supply voltage correspond to the requirement voltage of the digital blocks. The current consumption is proportional to clock frequency (3.5µA at 10MHz). Limit clock frequency is 100MHz. Fig. 1 shows the symbolic designation of the developed block of the random number generator.
The generator output is out_rndgen. The input sel_rndgen is the pin for selecting random number generator circuit, input en_rndgen is the enable pin of the generator of random numbers, the input clk_rndgen is the pin for the clock signal. Fig. 2 shows the time diagram of the random number generator operation that illustrates the operation of the generator when signal from input en_rndgen is on or off. The switch-on time of the circuit is t0.
The current consumption of this block of the random number generator is less than 300mA, and the switching time is less than 1µs. This work deals with optimization of the circuit of the random number generator by current consumption and occupied area.
A study of generators of the random sequence in experimental samples and the composition of final products were conducted in the laboratory of IC development department of MERI JSC. The goal of this research is to estimate the functionality of generators of the random sequence, and to compare the functionality of the original and optimized random sequence.
The following equipment was used for measurements: power supply — GwInstek GPD-73303S, generator/analyzer of signal — Lecroy ArbStudio 1104, circuit board based on FPGA Xilinx Virtex-4. The sequence of data from the generator random sequence output with a length of 62500 bytes was collected using the generator/analyzer of signal — Lecroy ArbStudio 1104.
A significant problem of hardware random number generators is a large number of deviations, and correlations in the generated sequence. The processes themselves may be random, but problems can arise in the measurement process. Therefore it is necessary to correct the received sequence of random numbers for increasing the entropy with the probability of logic zero and logic one being approximately equal. There is a large number of correction methods of improving the quality of the sequence. The Von Neumann correction has been used in this work. The principle of this transformation is to split the original sequence into pairs of bits, and then select only those pairs where adjacent values are different, the pairs with the same value being removed. Specific values are assigned to selected pairs in the output sequence. Fig. 3 shows an example of such a transformation. In this example, the value 1 is assigned to the pair “10” and the value “0” is assigned to the pair “01”, the pairs “00” and “11” are deleted from the sequence.
As a result of the von Neumann correction the sequence is significantly reduced, and its statistical properties approach the properties of random sequences.
The sequence was investigated according to several parameters for the rapid assessment of the data quality. One of the most revealing criteria of random sequences is the probability of logical “0” and “1” in the sequence, which ideally is equal to 50 %. The next criterion was the degree of shrink of the sequence length during the von Neumann correction, which characterizes the uniformity of values distribution in the sequence. After the von Neumann correction the criterion of the degree of compression sequence by the archiver was used. The value of compression shows the absence or the presence of regularities discovered by the archiver. There should not be regularities in a random sequence, so the size of the compressed files should be not smaller than the source. There are clock generators in every complex digital circuit. Therefore it was decided to include the clock generator in the test crystal for the analysis of its influence on the quality of generated random sequence.
Random sequences obtained with original and optimized generators have been tested. Analysis of the results was carried out on nine samples of values. After the von Neumann correction the initial sequence decreased by a factor of 4–5.
Binary files of random numbers before compression had the following sizes: the source sequence is 62,500 bytes; the sequence after the von Neumann correction — 12,500 bytes. Data compression was performed using 7z with the following settings: archive format — zip compression, level — ultra, compression method is Deflate, size of dictionary — 32KB, word size is 128.
When the clock generator is off, the average size of the initial sequence after compression is 59458 bytes, which is 95 % of the original size. For a sequence obtained after the von Neumann correction, this number is 12245 bytes (98 %).
When the clock generator is on, the average size of the initial sequence after compression is 61754 bytes (98.8 %). For a sequence obtained after the von Neumann correction, this number is 12648 bytes (101.2 %).
The average size of the optimized sequence after compression when the clock generator is off is 60866 bytes (99.5 %). For the sequence obtained after the von Neumann correction, this number is 12633 bytes (101.1 %).
The average size of the optimized sequence after compression when the clock generator is on is 62216 bytes (98.8 %). For a sequence obtained after the von Neumann correction, this number is 12631 bytes (101 %).
Fig. 4 shows the sizes of files of compressed sequences obtained with original and optimized blocks of the random number generator, when the clock generator is disabled and enabled. For clarity the figure also illustrates the size of the original sequence.
Fig. 5 shows the file sizes of the compressed sequences obtained with the original and optimized blocks of the random number generator after the correction, when the clock generator is disabled and enabled. The size of the original sequence is also shown.
Fig. 6 shows the probability of logical one when the clock generator is off for the original and optimized sequences.
Fig. 7 shows the probability of logical one when the clock generator is on for the original and optimized sequences.
Due to the research it was found that the influence of the clock generator does not affect the statistical properties of the generated random sequence.
Different statistical tests are used for more accurate determination of the quality of the resulting random numbers. In general it is possible to highlight two classes of criteria: empirical criteria and theoretical criteria; the first being used for calculating some statistics from groups of random numbers, and the second — for analyzing the sequence of numbers by number-theoretic methods over recurrence rules that form random numbers [5].
There is a large number of software tools for testing the quality of random numbers. National Institute of Standards and Technology (NIST) has developed 15 tests for determining the random number. These tests are based on various statistical properties that are inherent only to random sequences. Another famous set of tests for the analysis of random sequences is a diehard test, which is one of the most stringent existing test suites. In this paper, tests from the dieharder package were used to check the properties of the sequence. The package contains 114 tests, including diehard, NIST, and other tests. The author contends that passing all the tests is impossible. The original and optimized generators were tested on the technologies of 180nm and 90nm.
The input test data may be both output of the generator and the input file with a sampling of random numbers. The dieharder package is very demanding as regards the amount of input data, so for the analysis large amounts of samples were collected. It is empirically established that the required minimum input for most tests is about 512 megabytes. Such a volume of random data was collected for each test sample. A volume of 1GB was collected for two additional samples. The result of dieharder tests for 1GB of data is similar to the package with volume of 512MB. The original sequence passed a small number of tests (2–3 of 114). An increase in entropy by the von Neumann correction led to the reduction of the sample by a factor of 12–14 (35–42MB) and increased the number of passed tests to 25–30 of 114.
For further analysis it was decided to encrypt the files with random numbers by the DES algorithm in the Electronic Codebook (ECB) mode with the keys “0”. As a result, sequences successfully passed 106 to 110 tests of 114. Thus, file encryption was selected as the most effective method of improving statistical properties of a random sequence.
The authors consider the following provisions and results as novel. The Von Neumann correction can only be used to assess the validity of the random number generator in the composition of the product; the evaluation criterion is the sample reduction by a factor not more than 16–18 times. To achieve a high quality random sequence it has been proposed to increase the entropy using an encryption block available in the composition of the crystal. As a result, product samples have been designed and manufactured using processes with minimal topological norms of 90nm and 180nm [6, 7].
REFERENCES
1. Krasnikov G. Ya., Gornev E. S. Razvitie poluprovodnikovoi mikroelektroniki OAO “NIIME i Mikron”, Istoriya otechestvennoi elektroniki: M.: 2012. T. 1. P. 539–563. (In Russian).
2. Krasnikov G. Ya., Shelepin N. A. “Sostoyanie i perspektivy razvitiya tekhnologii i elementnoi bazy SBIS s energonezavisimoi pamyat'yu”, Mezhdunarodnaya nauchno-tekhnicheskaya konferentsiya s elementami nauchnoi shkoly dlya molodezhi. M.: Zelenograd, 2010. (In Russian).
3. Timoshin S., Nuykin A., Kravtsov A. Extreme Low Cost Chip for HF RFID tag. 7th Annual IEEE International Conference on RFID, IEEE RFID 2013. Orlando, US — 2013.
4. Roldugina Zh. I., Nuikin A. V. Vliyanie vremeni modelirovaniya na statisticheskoe raspredelenie vykhodnykh znachenii signala apparatnogo generatora sluchainogo chisla // Mikroelektronika i informatika — 2017: sbornik statei. M.: MIET, 2017. P. 170–176. (In Russian).
5. Slepovichev I. I. Vvedenie v teoriyu generatorov psevdosluchainykh chisel. Saarbryukken: LAP LAMBERT Academic Publishing, 2016. 128 p. (In Russian).
6. Nuikin A. V., Kravtsov A. S. “Razrabotka i vnedrenie kristallov dlya smart-kart na rossiiskom i mezhdunarodnom rynkakh na osnove reshenii AO “NIIME” // Elektronnaya tekhnika. Seriya 3. Mikroelektronika. 2016. № 1(161). P. 4–8. (In Russian).
7. Nuikin A. V., Kravtsov A. S. “Perspektivy razvitiya sistem radiochastotnoi identifikatsii na osnove kart pamyati i mikroprotsessornykh kart”, Mezhdunarodnaya konferentsiya “Mikroelektronika 2015”. Krym, Alushta — 2015. (In Russian).
Readers feedback
