Skip to Main content Skip to Navigation
Journal articles

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

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 be 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 guess-and-determine procedure that solves about 2^52 instances of the Closest Vector Problem on a very small lattice.
Document type :
Journal articles
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02700791
Contributor : Charles Bouillaguet <>
Submitted on : Monday, June 1, 2020 - 1:17:47 PM
Last modification on : Friday, November 27, 2020 - 2:20:05 PM
Long-term archiving on: : Friday, September 25, 2020 - 2:40:33 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

Charles Bouillaguet, Florette Martinez, Julia Sauvage. Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2020, ⟨10.13154/tosc.v2020.i3.175-196⟩. ⟨hal-02700791⟩

Share

Metrics

Record views

456

Files downloads

4310