What a lovely hat

Paper 2024/1594

Bit-fixing Correlation Attacks on Goldreich's Pseudorandom Generators

Abstract

We introduce a powerful attack, termed the bit-fixing correlation attack, on Goldreich's pseudorandom generators (PRGs), specifically focusing on those based on the $\mathsf{XOR}\text{-}\mathsf{THR}$ predicate. By exploiting the bit-fixing correlation property, we derive correlation equations with high bias by fixing certain bits. Utilizing two solvers to handle these high-bias correlation equations, we present inverse attacks on $\mathsf{XOR}\text{-}\mathsf{THR}$ based PRGs within the complexity class $\mathsf{NC}^{0}$. We efficiently attack the $\mathsf{XOR}\text{-}\mathsf{MAJ}$ challenges (STOC 2016), demonstrating that the $\mathsf{XOR}\text{-}\mathsf{MAJ}$ predicate fails to be $s$-pseudorandom with $n$-bit security even for a stretch factor $s = 1$, where $n$ is the size of the secret seed. For instance, a challenge of $n=42$ and $s = 1$ can be broken using approximately $2^{28}$ calls to Gaussian elimination. We extend our attack to an instance used in constructing silent Oblivious Transfer (OT) protocols (Eurocrypt 2024), with $n=256$. This attack can be realized with approximately $2^{29}$ calls to Gaussian elimination, and we have implemented this attack on a cluster of 32 CPU cores, successfully recovering the secret seed in 5.5 hours. Furthermore, we extend our results to general Piecewise Symmetric Predicates of the form $\mathsf{XOR}\text{-}\mathsf{X}$, showing that $\mathsf{XOR}\text{-}\mathsf{MAJ}$ is far from well designed predicate against bit-fixing correlation attack. With marginal modification, our attack can also be adapted to the FiLIP cipher instantiated with $\mathsf{THR}$-related predicates, making it effective against most FiLIP instances. For example, the FiLIP cipher instantiated on $\mathsf{XOR} \text{-}\mathsf{THR}$ with key size $982$ can be broken using approximately $2^{51}$ calls to Gaussian elimination. Based on these findings, we show that the traditional security assumptions for Goldreich's PRGs---namely, (a) $\Omega(s)$-resilience and (b) algebraic immunity---are insufficient to guarantee pseudorandomness or one-wayness.