^December January – 2008

An $(n,k)$-affine source over a finite field F is a random variable $X=(X_1,...,X_n) \in F^n$, which is uniformly distributed over an (unknown) k-dimensional affine subspace of $F^n$. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than $n^c$ (where $c$ is a large enough constant).

Our main results are as follows: (For arbitrary k): For any n,k and any F of size larger than $n^{20}$, we give an explicit construction for a function $D: F^n \rightarrow F^{k-1}$, such that for any $(n,k)$-affine source X over F, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. (For k=1): For any n and any F of size larger than $n^{c}$, we give an explicit construction for a function $D: F^n \rightarrow \{0,1\}^{(1-\delta) \log_2|F|}$, such that for any $(n,1)$-affine source X over F, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. Here, $\delta > 0$ is an arbitrary small constant, and $c$ is a constant depending on $\delta$.

Joint work with Ran Raz

Random numbers are essential in every cryptographic protocol. The quality of a system's random number generator (RNG) is therefore vital to its security. In Microsoft Windows, the operating system provides an RNG for security purposes, through an API function named CryptGenRandom. This is the cryptographic RNG used by the operating system itself and by important applications like the Internet Explorer, and the only RNG recommended for security purposes on Windows. This is the most common security RNG in the world, yet its exact algorithm was never published until now. We provide a description of the Windows RNG, based on examining the binary code of Windows 2000. We reconstructed the RNG's algorithm, and present its exact description and an analysis of the design. Our analysis shows a number of weaknesses in the design and implementation, and we demonstrate practical attacks on the RNG. We propose our recommendations for users and implementers of RNGs on the Windows platform. In addition, we describe the reverse-engineering process which led to our findings.