A block cipher based pseudo random number generator secure against side-channel key recovery

ABSTRACT

We study the security of a block cipher-based pseudorandom number generator (PRNG), both in the black box world and in the physical world, separately. We first show that the construction is a secure PRNG in the ideal cipher model. Then, we demonstrate its security against a Bayesian side-channel key recovery adversary. As a main result, we show that our construction guarantees that the success rate of the adversary does not increase with the number of physical observations, but in a limited and controlled way. Besides, we observe that, under common assumptions on side-channel attack strategies, increasing the security parameter (typically the block cipher key size) by a polynomial factor involves an increase of a side-channel attack complexity by an exponential factor, making the probability of a successful attack negligible. We believe this work provides a first interesting example of the way the algorithmic design of a cryptographic scheme influences its side-channel resistance.

REFERENCES

• 1: Michel Abdalla , Mihir Bellare, Increasing the Lifetime of a Key: A Comparative Analysis of the Security of Re-keying Techniques, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.546-559, December 03-07, 2000
• 2: Mihir Bellare , Joe Kilian , Phillip Rogaway, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences, v.61 n.3, p.362-399, Dec. 2000 [doi>10.1006/jcss.1999.1694]
• 3: M. Bellare, T. Kohno, A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and applications, in the proceedings of Eurocrypt 2003, Lecture Notes in Computer Science, vol 5656, pp 491--506, Warsaw, Poland, May 2003.
• 4: John Black , Phillip Rogaway , Thomas Shrimpton, Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.320-335, August 18-22, 2002
• 5: Suresh Chari , Josyula R. Rao , Pankaj Rohatgi, Template Attacks, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.13-28, August 13-15, 2002
• 6: FIPS 197, "Advanced Encryption Standard," Federal Information Processing Standard, NIST, U.S. Dept. of Commerce, November 26, 2001.
• 7: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 8: Louis Goubin , Jacques Patarin, DES and Differential Power Analysis (The "Duplication" Method), Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.158-172, August 12-13, 1999
• 9: Boris Köpf , David Basin, An information-theoretic model for adaptive side-channel attacks, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315282]
• 10: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 11: P. Kocher, Design and Validation Strategies for Obtaining Assurance in Countermeasures to Power Analysis and Related Attacks, in the proceedings of the NIST Physical Security Workshop, Honolulu, Hawai, September 2005.
• 12: P. Kocher, Leak Resistant Cryptographic Indexed Key Update, US Patent 6539092.
• 13: S. Mangard, Hardware Countermeasures against DPA - A Statistical Analysis of Their Effectiveness, in the proceedings of CT-RSA 2004, Lecture Notes in Computer Science, vol 2964, pp 222--235, San Francisco, CA, USA, February 2004.
• 14: S. Micali, L. Reyzin, Physically Observable Cryptography, in the proceedings of TCC 2004, LNCS, vol 2951, pp. 278--296, Cambridge, Massachusetts, USA, February 2004.
• 15: C. E. Shannon, Communication theory of secrecy systems, in Bell Systems Technical Journal, vol 28, num 4, pp 656--715, 1949.
• 16: F.-X. Standaert, T. G. Malkin, M. Yung, A Formal Practice-Oriented Model for the Analysis of Side-Channel Attacks, Version 2.0, Cryptology ePrint Archive, Report 2006/139, 2006.
• 17: F.-X. Standaert, E. Peeters, C. Archambeau, J.-J. Quisquater, Towards Security Limits in Side-Channel Attacks, in the proceedings of CHES 2006, Lecture Notes in Computer Science, vol 4249, pp. 30--45, Yokohama, Japan, October 2006.
• 18: K. Tiri, M. Akmal, I. Verbauwhede, A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards, ESSCIRC 2003.
• 19: A. C. Yao, Theory and Applications of Trapdoor Functions (Extended Abstract), in the proceedings of FOCS 1982, pp. 80--91.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Security, Theory