International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Practical seed-recovery for the PCG Pseudo-Random Number Generator

Authors:
Charles Bouillaguet , Univ. Lille, CNRS, Centrale Lille, UMR 9189 - CRIStAL - Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France
Florette Martinez , Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Julia Sauvage , Sorbonne Université, F-75005 Paris, France
Download:
DOI: 10.13154/tosc.v2020.i3.175-196
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8700
Search ePrint
Search Google
Abstract: The Permuted Congruential Generators (PCG) are popular conventional (non-cryptographic) pseudo-random generators designed in 2014. They are used by default in the NumPy scientific computing package. Even though they are not of cryptographic strength, their designer stated that predicting their output should nevertheless be "challenging".In this article, we present a practical algorithm that recovers all the hidden parameters and reconstructs the successive internal states of the generator. This enables us to predict the next “random” numbers, and output the seeds of the generator. We have successfully executed the reconstruction algorithm using 512 bytes of challenge input; in the worst case, the process takes 20 000 CPU hours.This reconstruction algorithm makes use of cryptanalytic techniques, both symmetric and lattice-based. In particular, the most computationally expensive part is a guessand-determine procedure that solves about 252 instances of the Closest Vector Problem on a very small lattice.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30568,
  title={Practical seed-recovery for the PCG Pseudo-Random Number Generator},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 3},
  pages={175-196},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8700},
  doi={10.13154/tosc.v2020.i3.175-196},
  author={Charles Bouillaguet and Florette Martinez and Julia Sauvage},
  year=2020
}