TY - GEN
T1 - On Seedless PRNGs and Premature Next
AU - Coretti, Sandro
AU - Dodis, Yevgeniy
AU - Karthikeyan, Harish
AU - Stephens-Davidowitz, Noah
AU - Tessaro, Stefano
N1 - Publisher Copyright:
© Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, and Stefano Tessaro; licensed under Creative Commons License CC-BY 4.0
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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.
AB - 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.
KW - Fortuna
KW - PRNG
KW - premature next
KW - pseudorandom number generators
KW - seedless PRNGs
UR - http://www.scopus.com/inward/record.url?scp=85134290576&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134290576&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITC.2022.9
DO - 10.4230/LIPIcs.ITC.2022.9
M3 - Conference contribution
AN - SCOPUS:85134290576
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 3rd Conference on Information-Theoretic Cryptography, ITC 2022
A2 - Dachman-Soled, Dana
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 3rd Conference on Information-Theoretic Cryptography, ITC 2022
Y2 - 5 July 2022 through 7 July 2022
ER -