International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Provable Security of Linux-DRBG in the Seedless Robustness Model

Authors:
Woohyuk Chung , KAIST, Daejeon, Korea
Hwigyeom Kim , Norma Inc., Seoul, Korea
Jooyoung Lee , KAIST, Daejeon, Korea
Yeongmin Lee , DESILO Inc., Seoul, Korea
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: This paper studies the provable security of the deterministic random bit generator~(DRBG) utilized in Linux 6.4.8, marking the first analysis of Linux-DRBG from a provable security perspective since its substantial structural changes in Linux 4 and Linux 5.17. Specifically, we prove its security up to $O(\min\{2^{\frac{n}{2}},2^{\frac{\lambda}{2}}\})$ queries in the seedless robustness model, where $n$ is the output size of the internal primitives and $\lambda$ is the min-entropy of the entropy source. Our result implies $128$-bit security given $n=256$ and $\lambda=256$ for Linux-DRBG. We also present two distinguishing attacks using $O(2^{\frac{n}{2}})$ and $O (2^{\frac{\lambda}{2}})$ queries, respectively, proving the tightness of our security bound.
BibTeX
@inproceedings{asiacrypt-2024-34599,
  title={Provable Security of Linux-DRBG in the Seedless Robustness Model},
  publisher={Springer-Verlag},
  author={Woohyuk Chung and Hwigyeom Kim and Jooyoung Lee and Yeongmin Lee},
  year=2024
}