Definition 1 Advanced Computational Diffie-Hellman [BFPV11])
5.4 Comparison with Other Approaches
We first mention that comparisons with other countermeasures against side- channel attacks are difficult, as the present proposal is not efficiently applicable to all ciphers. For example, plugging 8-bit S-boxes such as the ones of the AES Rijndael into the performance formulas of the previous section would lead to unrealistic memory requirements. On the other hand, low cost block ciphers are a very active research area and designs based on 4-bit S-boxes, such as PRESENT [3], or even 3-bit S-boxes, such as SEA [36], have been proposed in the literature.
So the implementation of RLUT masking is possible for existing ciphers.
Besides, and as already mentioned in the introduction, our proposal has strong connections with the OTP implementation described in [18]. We similarly build masked programs, with two main differences. First, we consider random tables rather than random gates. This makes the execution of a block cipher protected with the RLUT countermeasure (which only requiresNsãNrtable lookups and Nr applications of the d transform) much faster than a OTP. But it implies larger memory requirements, as the cost of masking am×m-bit table grows with 22mãm. Second, we take advantage of the specificities of modern block ciphers, e.g. the linearity of their diffusion transform, that makes their protection easier.
As a side-result, we also obtain very simple security arguments and proofs.
The RLUT masking also shares objectives with the higher-order masking scheme of Rivain and Prouff at CHES 2010. Their work describes protected AES implementations for masking of ordersd= 1,2,3. It is an interesting counterpart to our proposal as it implies different types of overheads. [34] only increases the code size moderately. Its main drawback is the execution time. For d = 3, it multiplies the one of an unprotected implementation in an 8-bit smart card by more than 100. By contrast, RLUT masking requires a large memory and allows fast online encryption. The main difference between these approaches is their security model: RLUT directly tackle attacks of all orders, while the higher-order masking scheme in [34] uses the orderdas a security parameter, which allows to adapt the security level and performances depending on the applications.
Conclusion and Open Problems
Inspired by previous models and designs in the area of physically observable cryptography, we proposed a new type of masking scheme, based on the use of randomized look up tables. It illustrates that relatively simple principles can lead to strong security guarantees. Admittedly, our solution is not directly applicable to standard algorithms such as the AES Rijndael. But it highlights that the
structure of a block cipher has a strong impact on the possibilities to protect its implementations against side-channel attacks. Hence, one important consequence of these results is the statement of clear design principles for leakage-resilient block ciphers. Namely, our analysis gives a strong motivation for designing low cost block ciphers, with small (e.g. 3-bit, 4-bit) S-boxes, and powerful linear transforms, achieving complete diffusion in a small number of rounds.
References
1. Akkar, M.-L., Giraud, C.: An Implementation of DES and AES, Secure against Some Attacks. In: Koác, Cá .K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 309–318. Springer, Heidelberg (2001)
2. Billet, O., Gilbert, H., Ech-Chatbi, C.: Cryptanalysis of a White Box AES Imple- mentation. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp.
227–240. Springer, Heidelberg (2004)
3. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An Ultra-Lightweight Block Cipher.
In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466.
Springer, Heidelberg (2007)
4. Brakerski, Z., Tauman Kalai, Y., Katz, J., Vaikuntanathan, V.: Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leak- age. In: FOCS 2010, Las Vegas, NV, USA (October 2010)
5. Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards Sound Approaches to Counteract Power-Analysis Attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999)
6. Chow, S., Eisen, P.A., Johnson, H., van Oorschot, P.C.: A White-Box DES Im- plementation for DRM Applications. In: Feigenbaum, J. (ed.) DRM 2002. LNCS, vol. 2696, pp. 1–15. Springer, Heidelberg (2003)
7. Chow, S., Eisen, P.A., Johnson, H., van Oorschot, P.C.: White-Box Cryptography and an AES Implementation. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 250–270. Springer, Heidelberg (2003)
8. Coron, J.-S., Prouff, E., Rivain, M.: Side Channel Cryptanalysis of a Higher Or- der Masking Scheme. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 28–44. Springer, Heidelberg (2007)
9. Daudigny, R., Ledig, H., Muller, F., Valette, F.: SCARE of the DES. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 393–406.
Springer, Heidelberg (2005)
10. Dodis, Y., Haralambiev, K., Lopez-Alt, A., Wichs, D.: Cryptography Against Con- tinuous Memory Attacks. In: FOCS 2010, Las Vegas, NV, USA (October 2010) 11. Fumaroli, G., Martinelli, A., Prouff, E., Rivain, M.: Affine masking against higher-
order side channel analysis. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 262–280. Springer, Heidelberg (2011)
12. Goubin, L., Patarin, J.: DES and Differential Power Analysis. In: Koác, Cá .K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158–172. Springer, Heidelberg (1999) 13. Goubin, L., Masereel, J.-M., Quisquater, M.: Cryptanalysis of White Box DES
Implementations. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 278–295. Springer, Heidelberg (2007)
14. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: One-Time Programs. In: Wagner, D.
(ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 39–56. Springer, Heidelberg (2008)
15. Golic, J.D., Tymen, C.: Multiplicative Masking and Power Analysis of AES. In:
Kaliski Jr., B.S., Koác, Cá .K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp.
198–212. Springer, Heidelberg (2003)
16. Herbst, C., Oswald, E., Mangard, S.: An AES Smart Card Implementation Resis- tant to Power Analysis Attacks. In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006.
LNCS, vol. 3989, pp. 239–252. Springer, Heidelberg (2006)
17. Ishai, Y., Sahai, A., Wagner, D.: Private Circuits: Securing Hardware against Prob- ing Attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481.
Springer, Heidelberg (2003)
18. J¨arvinen, K., Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Garbled Circuits for Leakage-Resilience: Hardware Implementation and Evaluation of One-Time Pro- grams. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp.
383–397. Springer, Heidelberg (2010)
19. Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999) 20. Mangard, S., Popp, T., Gammel, B.M.: Side-Channel Leakage of Masked CMOS
Gates. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 351–365. Springer, Heidelberg (2005)
21. Mangard, S., Schramm, K.: Pinpointing the Side-Channel Leakage of Masked AES Hardware Implementations. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 76–90. Springer, Heidelberg (2006)
22. Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks. Springer, Heidelberg (2007)
23. Messerges, T.S.: Using Second-Order Power Analysis to Attack DPA Resistant Software. In: Paar, C., Koác, Cá .K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 238–
251. Springer, Heidelberg (2000)
24. Nikova, S., Rechberger, C., Rijmen, V.: Threshold Implementations Against Side- Channel Attacks and Glitches. In: Ning, P., Qing, S., Li, N. (eds.) ICICS 2006.
LNCS, vol. 4307, pp. 529–545. Springer, Heidelberg (2006)
25. Nikova, S., Rijmen, V., Schl¨affer, M.: Secure Hardware Implementation of Non- linear Functions in the Presence of Glitches. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 218–234. Springer, Heidelberg (2009)
26. Oswald, E., Mangard, S., Pramstaller, N., Rijmen, V.: A Side-Channel Analysis Resistant Description of the AES S-Box. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 413–423. Springer, Heidelberg (2005)
27. Oswald, E., Schramm, K.: An Efficient Masking Scheme for AES Software Im- plementations. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 292–305. Springer, Heidelberg (2006)
28. Oswald, E., Mangard, S.: Template Attacks on Masking—Resistance Is Futile. In:
Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 243–256. Springer, Heidelberg (2006)
29. Piret, G., Standaert, F.-X.: Security Analysis of Higher-Order Boolean Masking Schemes for Block Ciphers (with Conditions of Perfect Masking). IET Information Security 2(1), 1–11 (2008)
30. Prouff, E., Rivain, M., Bevan, R.: Statistical Analysis of Second Order Differential Power Analysis. IEEE Transactions on Computers 58(6), 799–811 (2009)
31. R´eal, D., Dubois, V., Guilloux, A.-M., Valette, F., Drissi, M.: SCARE of an Un- known Hardware Feistel Implementation. In: Grimaud, G., Standaert, F.-X. (eds.) CARDIS 2008. LNCS, vol. 5189, pp. 218–227. Springer, Heidelberg (2008) 32. Rijmen, V.: Cryptanalysis and Design of Iterated Block Ciphers, PhD thesis,
Katholieke Universiteit Leuven, Belgium (October 1997)
33. Rivain, M., Dottax, E., Prouff, E.: Block Ciphers Implementations Provably Secure Against Second Order Side Channel Analysis. In: Nyberg, K. (ed.) FSE 2008.
LNCS, vol. 5086, pp. 127–143. Springer, Heidelberg (2008)
34. Rivain, M., Prouff, E.: Provably Secure Higher-Order Masking of AES. In: Man- gard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 413–427.
Springer, Heidelberg (2010)
35. Schramm, K., Paar, C.: Higher Order Masking of the AES. In: Pointcheval, D.
(ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 208–225. Springer, Heidelberg (2006) 36. Standaert, F.-X., Piret, G., Gershenfeld, N., Quisquater, J.-J.: SEA: a Scalable
Encryption Algorithm for Small Embedded Applications. In: Domingo-Ferrer, J., Posegga, J., Schreckling, D. (eds.) CARDIS 2006. LNCS, vol. 3928, pp. 222–236.
Springer, Heidelberg (2006)
37. Standaert, F.-X., Malkin, T.G., Yung, M.: A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks. In: Joux, A. (ed.) EUROCRYPT 2009.
LNCS, vol. 5479, pp. 443–461. Springer, Heidelberg (2009)
38. Standaert, F.-X., Veyrat-Charvillon, N., Oswald, E., Gierlichs, B., Medwed, M., Kasper, M., Mangard, S.: The World is Not Enough: Another Look on Second- Order DPA. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 112–129.
Springer, Heidelberg (2010)
39. von Willich, M.: A Technique with an Information-Theoretic Basis for Protecting Secret Data from Differential Power Attacks. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 44–62. Springer, Heidelberg (2001) 40. Wyseur, B.: White-Box Cryptography, PhD thesis, Katholieke Universiteit Leuven,
Belgium (2009)
A Modified Algorithms 1 and 2
Algorithm 3.Table refreshing.
-input:pk,a1. 1. Picka2←− {R 0,1}n 2. Picka3←− {0,R 1}n;
3. Precomputer(I) =pk(I)⊕a2; 4. Precomputeg2(I, J) =I⊕J⊕a3;
5. Precomputec(I, J) =r(I)⊕pk(I⊕J⊕a1)⊕a3; -output:r,g2,c.
Algorithm 4.S-box evaluation on masked inputg1(x, m) and maskm.
-input:r,c.
1. Computer(g1(x, m));
2. Computec(g1(x, m), m);
-output:r(g1(x, m)),c(g1(x, m), m)
Note thatg1,g2are not used explicitly during the S-box evaluation but must be kept in memory for unmasking, after a secure computation is completed.
Number Generator Based on SRAM PUFs
Vincent van der Leest, Erik van der Sluis, Geert-Jan Schrijen, Pim Tuyls, and Helena Handschuh
Intrinsic-ID, Eindhoven, The Netherlands http://www.intrinsic-id.com
Abstract. An important building block for many cryptographic sys- tems is a random number generator. Random numbers are required in these systems, because they are unpredictable for potential attackers.
These random numbers can either be generated by a truly random phys- ical source (that is non-deterministic) or using a deterministic algorithm.
In practical applications where relatively large amounts of random bits are needed, it is also possible to combine both of these generator types.
A non-deterministic random number generator is used to provide a truly random seed, which is used as input for a deterministic algorithm that generates a larger amount of (pseudo-)random bits. In cryptographic systems where Physical Unclonable Functions (PUFs) are used for au- thentication or secure key storage, an interesting source of randomness is readily available. Therefore, we propose the construction of a FIPS 140-3 compliant random bit generator based on an SRAM PUF in this paper. These PUFs are a source of instant randomness, which is available when powering an IC. Based on large sets of measurements, we derive the min-entropy of noise on the start-up patterns of SRAM memories.
The min-entropy determines the compression factor of a conditioning al- gorithm, which is used to extract a truly random (256 bits) seed from the memory. Using several randomness tests we prove that the conditioned seed has all the properties of a truly random string with full entropy. This truly random seed can be derived in a low cost and area efficient manner from the standard IC component SRAM. Furthermore, an efficient imple- mentation of a deterministic algorithm for generating (pseudo-)random output bits will be proposed. Combining these two functions leads to an ideal way to generate large amounts of random data based on non- deterministic randomness.
1 Introduction
Physical Unclonable Functions (PUFs) are most commonly used for identifica- tion or authentication of Integrated Circuits (ICs), either by using its inherent unique device fingerprint or by using it to derive a device unique cryptographic key. Due to deep-submicron manufacturing process variations every transistor in an IC has slightly different physical properties that lead to measurable dif- ferences in terms of its electronic properties e.g. threshold voltage, gain factor,
D. Naccache (Ed.): Quisquater Festschrift, LNCS 6805, pp. 300–318, 2012.
c Springer-Verlag Berlin Heidelberg 2012
etc. Since these process variations are uncontrollable during manufacturing, the physical properties of a device can neither be copied nor cloned. It is very hard, expensive and economically not viable to purposely create a device with a given electronic fingerprint. Therefore, one can use this inherent physical fingerprint to uniquely identify an IC.
However, there is another possible application area for PUFs. This application is the generation of random numbers, which can be done based on the noise properties of PUFs. As studies on identification of ICs using PUFs have proven, measurements of the physical structures that make up PUFs are always noisy.
This means that two measurements of the same PUF (under the same external conditions) will always result in two slightly different outputs. In case of SRAM PUFs, where this paper focusses on, two measurements of start-up patterns on an SRAM will result in two patterns that are very similar. However, several bits have a different value between the two measurements. In order to be able to use this phenomenon for random number generation, a sufficient amount of bits should change between measurements. Furthermore, the bits that have changed should be unpredictable. In this publication we will prove that both of these requirements are met for the SRAM memories that we have measured.
Therefore, we will propose a construction for utilizing this random behaviour of SRAM PUFs in a streaming random number generator that is FIPS 140-3 compliant.