On Seedless PRNGs and Premature Next

Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, Stefano Tessaro

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Pseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE'98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropy-estimation methods to prevent such attacks (as in Linux's/dev/random) or sophisticated pool-based approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows). The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica'17) considers either a seeded setting or assumes constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO'19; Dodis et al., ITC'21, CRYPTO'21) do not consider premature next attacks. The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions: 1. We prove that it is impossible to achieve seedless PRNGs that are secure against premature-next attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible. 2. Given the above impossibility result, we investigate whether existing seedless pool-based approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following. We introduce a natural condition on the entropic input and prove that it implies security of the round-robin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy “not to vary too wildly” within a given round-robin round. We prove that the “root pool” approach (also used in Windows 10) is secure for general entropy inputs, provided that the system's state is not compromised after system startup.

Original languageEnglish (US)
Title of host publication3rd Conference on Information-Theoretic Cryptography, ITC 2022
EditorsDana Dachman-Soled
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772389
StatePublished - Jul 1 2022
Event3rd Conference on Information-Theoretic Cryptography, ITC 2022 - Cambridge, United States
Duration: Jul 5 2022Jul 7 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference3rd Conference on Information-Theoretic Cryptography, ITC 2022
Country/TerritoryUnited States


  • Fortuna
  • PRNG
  • premature next
  • pseudorandom number generators
  • seedless PRNGs

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On Seedless PRNGs and Premature Next'. Together they form a unique fingerprint.

Cite this