Sponge-based pseudo-random number generators

Conclusions

We have presented a construction for building a reseedable pseudo-random num- ber generator using a sponge function. This construction is efficient in terms of memory use and processing, and inherits the provable security properties of the sponge construction. We have provided bounds on generic state recovery attacks allowing the use of a small state. We have given a concrete example of such a PRNG based on Keccak with a state of only 25 bytes that is particularly suitable for embedded devices.

References

1. 
   M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, ACM Conference on Computer and Communications Security 1993 (ACM, ed.), 1993, pp. 62–73.
   
2. 
   M. Bellare and B. Yee, Forward-security in private-key cryptography, Cryptology ePrint Archive, Report 2001/035, 2001, http://eprint.iacr.org/.
   
3. 
   G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, Sponge functions, Ecrypt Hash Workshop 2007, May 2007, also available as public comment to NIST from http://www.csrc.nist.gov/pki/HashWorkshop/Public_Comments/ 2007_May.html.
   
4. 
   , On the indifferentiability of the sponge construction, Advances in Cryp- tology – Eurocrypt 2008 (N. P. Smart, ed.), Lecture Notes in Computer Science, vol. 4965, Springer, 2008, http://sponge.noekeon.org/, pp. 181–197.
   
5. 
   , Cryptographic sponges, 2009, http://sponge.noekeon.org/.
   
6. 
   , Keccak specifications, version 2, NIST SHA-3 Submission, September 2009, http://keccak.noekeon.org/.
   
7. 
   , Keccak sponge function family main document, NIST SHA-3 Submission (updated), June 2010, http://keccak.noekeon.org/.
   
8. 
   J. Coron, Y. Dodis, C. Malinaud, and P. Puniya, Merkle-Damg˚ard revisited: How to construct a hash function, Advances in Cryptology – Crypto 2005 (V. Shoup, ed.), LNCS, no. 3621, Springer-Verlag, 2005, pp. 430–448.
   
9. 
   A. Desai, A. Hevia, and Y. L. Yin, A practice-oriented treatment of pseudorandom number generators, Advances in Cryptology – Eurocrypt 2002 (L. R. Knudsen, ed.), Lecture Notes in Computer Science, vol. 2332, Springer, 2002, pp. 368–383.
   
10. 
    N. Ferguson and B. Schneier, Practical cryptography, John Wiley & Sons, 2003.
    
11. 
    U. Maurer, R. Renner, and C. Holenstein, Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, Theory of Cryp- tography - TCC 2004 (M. Naor, ed.), Lecture Notes in Computer Science, no. 2951, Springer-Verlag, 2004, pp. 21–39.
    
12. 
    NIST, Federal information processing standard 186-2, digital signature standard (DSS), May 1994.
    
13. 
    , Announcing request for candidate algorithm nominations for a new cryp- tographic hash algorithm (SHA-3) family, Federal Register Notices 72 (2007), no. 212, 62212–62220, http://csrc.nist.gov/groups/ST/hash/index.html.
    
14. 
    , NIST special publication 800-90, recommendation for random number gen- eration using deterministic random bit generators (revised), March 2007.
    
15. 
    , NIST special publication 800-22, a statistical test suite for random and pseudorandom number generators for cryptographic applications (revision 1), Au- gust 2008.
    
16. 
    J. Viega, Practical random number generation in software, ACSAC ’03: Proceedings of the 19th Annual Computer Security Applications Conference (Washington, DC, USA), IEEE Computer Society, 2003, p. 129.