Paper 2021/1204

Attacks on Pseudo Random Number Generators Hiding a Linear Structure

Florette Martinez
Abstract

We introduce lattice-based practical seed-recovery attacks against two efficient number-theoretic pseudo-random number generators: the fast knapsack generator and a family of combined multiple recursive generators. The fast knapsack generator was introduced in 2009 by Von Zur Gathen and Shparlinski. It generates pseudo-random numbers very efficiently with strong mathematical guarantees on their statistical properties but its resistance to cryptanalysis was left open since 2009. The given attacks are surprisingly efficient when the truncated bits do not represent a too large proportion of the internal states. Their complexities do not strongly increase with the size of parameters, only with the proportion of discarded bits. A multiple recursive generator is a pseudo-random number generator based on a constant-recursive sequence. A combined multiple recursive generator is a pseudo-random number generator based on combining two or more multiple recursive generators. L’Écuyer presented the general construction in 1996 and a popular instantiation deemed MRG32k3a in 1999. We use algebraic relations of both pseudo-random generators with underlying algebraic generators to show that they are cryptographically insecure. We provide a theoretical analysis as well as efficient implementations.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. CT-RSA 2022
Keywords
Pseudo-random number generators Knapsack problem Coppersmith Methods Cryptanalysis
Contact author(s)
florette martinez @ lip6 fr
History
2022-07-05: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1204
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1204,
      author = {Florette Martinez},
      title = {Attacks on Pseudo Random Number Generators Hiding a Linear Structure},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1204},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1204}},
      url = {https://eprint.iacr.org/2021/1204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.