Simona Buchovecká, Josef Hlaváč Faculty of Information Technology Czech Technical University in Prague buchosim@fit.cvut.cz, josef.hlavac@fit.cvut.cz
Abstract—In this paper we present a frequency injection attack on a random number generator implemented in an Atmel AVR microcontroller. Two variants of the attack are attempted:
an invasive attack with a direct modification of the power supply, and a non-invasive attack with no modification of the device.
Keywords—Random Number Generator, Frequency Injection Attack, Atmel AVR
I. INTRODUCTION
Random numbers are indispensable in cryptography – they are needed in almost all cryptographic protocols. Random numbers are used to generate public and private keys, nonces (salts), padding, etc. Therefore, the security of the entire cryptosystem also depends on the security of its random number generator. For that reason, a random number generator for cryptographic applications must produce truly random and unpredictable sequences, and must be secured against potential attacks.
Such a true random number generator is proposed in [1].
It is implemented in a low-cost Atmel AVR microcontroller.
The jitter of the microcontroller’s built-in RC oscillator is used as the source of entropy. In this paper, we present two variants of the frequency injection attack that can affect the randomness of the produced bit sequence and thus reduce the strength of any cryptosystem that would rely on the generator.
II. RANDOM NUMBER GENERATOR
The method of generating random numbers, as presented in [1], utilizes the ATmega169 microcontroller on the AVR Butterfly demo board. The principle is depicted in Fig. 1.
Fig. 1. Principle of random number generation
The microcontroller uses its on-chip RC oscillator for the system clock, and an oscillator with an externally connected crystal as an asynchronous clock generator for the Timer/Counter 2 unit. These oscillators are never perfectly stable. Their frequencies are influenced by many physical factors, such as the supply voltage or ambient temperature, and are also subject to inherent jitter. Due to these factors, the
“COUNT” value obtained at every interrupt is different and can be used as a source of entropy.
III. FREQUENCY INJECTION ATTACK
A frequency injection attack, which is able to destroy the source of entropy in ring-oscillator-based true random number generators, was proposed in [3]. The main idea is that an on-chip ring oscillator may have a tendency to “synchronize”
itself to an externally applied frequency. A contactless variant of the attack is elaborated in [4]; the authors again attempted to influence a ring-oscillator-based true random number generator. We based our attacks on these ideas.
Because the method of generating random numbers described above uses the instability of the RC oscillator as the source of entropy, the goal of our attack is to “stabilize” the oscillator and thus reduce its quality as an entropy source. The reasoning is that by using a relatively stable oscillator operating near the nominal operating frequency (8 MHz) of the RC oscillator, said RC oscillator would lock to this externally applied, parasitic frequency. Consequently, there would be less variation in the obtained “COUNT” values.
In subsequent processing, individual bits from the obtained
“COUNT” values are processed. Bit 0 is always thrown away because it is program-dependent. Bit 1 was found to be sufficiently random [5,6] and is therefore added to the output sequence. Other bits, even though they still carry some randomness, are also thrown away.
A. Invasive Variant of the Frequency Injection Attack In the invasive variant of the attack, a direct access to the device and its power source are needed. We attempted to inject a frequency of 8 MHz from a relatively stable source directly into the device’s power supply connection. The principle of the attack is shown in Fig. 2.
The injected frequency is generated by a simple 8 MHz crystal oscillator consisting of a crystal resonator (30 ppm stability) and inverting Schmitt triggers (74HC14). The
oscillator is then connected to an external power supply of the AVR Butterfly board as shown in Fig. 2.
Fig. 2. Modified external power supply circuit
When examining the generated values, we found out that under normal operation with unmodified power supply, 6493 unique “COUNT” values were generated. With the modified power supply and 8 MHz external oscillator, only 2167 unique
“COUNT” values appeared in the generated sequence of the same length. The histogram is shown in Fig. 3.
Fig. 3. Frequency injection with modified power supply – histograms.
Individual “COUNT” values are plotted on the horizontal axis, the number of occurrences of each respective value on the vertical axis.
Wider and lower curve is better and indicates more randomness.
Afterwards, we investigated the randomness of individual bits of the generated numbers using the ENT test suite [2]. We found out that the entropy in the sequence generated under the attack was significantly lower in highest two bits, and the other bits were slightly influenced compared to normal operation, too. Furthermore, results of other tests were much more interesting and revealed attack more clearly.
From previous work [5,6] we know that bit 1 of each generated value is truly random and secure for use even in sensitive applications. However, with the attack, we succeeded in influencing this bit. This bit (as well as all other bits) totally failed in the chi-square test, and also performed worse in other tests (Arithmetic Mean, Monte Carlo, Correlation Coefficient).
The effect of the attack is particularly visible in the Monte Carlo test (probabilistic computation of π). The most interesting results are shown in Table I.
TABLE I. INVASIVE FREQUENCY INJECTION
Bit Normal operation Device under attack Entropy Test (ideal result 8.0)
1 7.999902 7.990001
Arithmetic Mean (ideal result 127.5)
1 127.4328 132.6571
B. Non-Invasive Variant of the Frequency Injection Attack Because gaining direct physical access to the device and modifying it may not always be possible, we tried a non-invasive variant of the attack, too. In this variant of the attack, a HP 3310A function generator was used to generate an 8 MHz sinusoid signal. A simple antenna was connected to the generator and placed near the AVR Butterfly board with the random number generator running. The generated sequence was captured and analyzed. The principle of the attack is depicted in Fig. 4.
Fig. 4. Non-invasive frequency injection attack – principle
4.2. Frequency injection attack on random number generator
The generated numbers were again visualized in histograms that are shown in Fig. 5. The figure demonstrates that when the device is under the attack, the histogram is significantly thinner and higher. This indicates that fewer unique “COUNT” values were generated and thus less randomness was available.
We again used the ENT test suite [2] to examine the entropy of individual bits in the generated sequence. The generator was not influenced as significantly as in the invasive attack. The influence was evident in the entropy of the two highest bits – it was considerably smaller (2.154833 for bit 6 and 1.30974 for bit 7 when no fault was injected, compared to 0.743732 for bit 6 and 0.351782 when device was under the attack).
Fig. 5. Non-invasive frequency injection attack – histograms. Multiple measurements with similar results are shown overlapped in the “Device under attack” portion, hence the multiple peaks. Again, individual
“COUNT” values are plotted on the horizontal axis, and the number of occurrences of each respective value on the vertical axis.
We also tried to inject a signal that is a harmonic of the RC oscillator operating frequency (8 MHz) – 16, 32 and 48 MHz.
The 7th bit was still significantly influenced but the influence on the 6th bit was not so pronounced. The remaining bits were not affected significantly. This may be caused, besides other factors, by the fact that the frequency of the function generator was not as stable compared to the crystal oscillator used in the invasive variant of our attack.
IV. CONCLUSIONS
We presented an invasive and a non-invasive variant of a frequency injection attack on a random number generator implemented on an Atmel AVR microcontroller.
The invasive variant of the frequency injection attack is powerful enough to influence and reduce the randomness of all generated bits – even bit 1 which was found to be truly random in previous work [5,6]. However, it may be difficult to gain access to the device to connect the parasitic frequency to its power supply line.
The non-invasive variant of the attack is not as powerful because it only affected the higher bits of the generated values.
Still, significantly less unique values were generated under the attack. One should also consider the fact that no physical manipulation with the device was necessary and no physical traces of the attack were left when it ceased.
The results also demonstrate the importance of continuous self-testing of random number generators. In this way, such attacks can be immediately discovered and the random number generator failure properly handled.
ACKNOWLEDGMENT
This work was supported by the Czech Technical University grant No. SGS13/102/OHK3/1T/18 “Information Systems and their Security”.
REFERENCES
[1] J. Hlaváč, M. Hadáček, R.Lórencz, “True random number generation on an Atmel AVR microcontroller,” in Proceedings of 2nd International Conference on Computer Engineering and Technology – ICCET 2010, 2010, vol. 2, p. 493-495.
[2] J. Walker, ENT – A pseudorandom number sequence test program [online], Fourmilab 2008, available at http://www.fourmilab.ch/random.
[3] T. Markettos, S. W. Moore, “The frequency injection attack on ring-oscillator-based true random number generators,” in Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2009), September 2009, p. 317–331.
[4] P. Bayon, L. Bossuet, A. Aubert, V. Fischer, F. Poucheret, B. Robisson, P. Maurine, “Contactless electromagnetic active attack on ring oscillator based true random number generator,” in Proceedings of the 3rd International Conference on Constructive Side-Channel Analysis and Secure Design (COSADE’12), May 2012, p. 151–166.
[5] J. Hlaváč, S. Buchovecká, R. Lórencz, “New results in generating true random numbers on simple microcontrollers,” in Proceedings of the 9th International Workshop on Cryptographic Architectures Embedded in Reconfigurable Devices (CryptArchi), June 2011.
[6] S. Buchovecká, “Testing a random number generator,” in Proceedings of the 15th International Student Conference on Electrical Engineering (POSTER 2011), May 2011.
4.3. RP3 - True Random Number Generator based on ROPUF circuit
4.3 RP3 - True Random Number Generator based on ROPUF circuit
The goal of RP3 paper is to prove that it is possible to design the universal crypto system, that can be used for various applications by allowing to generated PUF and TRNG at the same time. The PUF can be utilized for asymmetric cryptography and generating asymmetric keys, TRNG for symmetric cryptography (generating session and ephemeral keys), nonces and salts. In the paper the results of evaluation of such a circuit utilized for TRNG purpose are presented. The presented design is based on 150 pairs of ROs, whose oscillations are counted by two counters. As soon as one of these counters overflows, the measurement is stopped. The resulting value in the counter that did not overflow is used for further processing. We showed that it is possible to gain up to 142x3 random bits in one run of the ROPUF, but further post processing is needed, which shortens the generated bit stream by 50 % (XOR corrector), or by approx. 75 % (von Neumann corrector). The paper was presented on DSD 2016 – Euromicro Conference on Digital System Design [A.3].