CoolTest: Randomness test suited for small data volumes

In this work, we present CoolTest, a randomness test well-suited for scenarios with only small volumes of data. CoolTest searches for a correlation among any k bits within a fixed-size window. CoolTest generalizes BoolTest (ICETE’17) and builds on the innovative idea of Chatterjee et al. (INDOCRYPT’22), making it practical. Using this idea, CoolTest identifies the strongest correlation on k bits by evaluating only 2 k candidates instead of all 2 2 k Boolean functions. CoolTest finds arbitrary k -bit correlations with complexity comparable to BoolTest and the method of Chatterjee et al., evaluating 100 MB of data in tens of seconds, while those approaches are limited to predefined or nearby-bit correlations. We evaluated CoolTest on outputs of 14 reduced-round cryptographic functions (e.g., AES, Twofish, Keccak, and MD5). CoolTest performs at least as well as BoolTest in 26 out of 28 cases and often finds stronger correlations. On 100 MB of data, CoolTest detects bias in a higher number of rounds of SHA-2, SHA-1, MD6, and SHACAL-2 than the commonly used test suites NIST STS, Dieharder, and TestU01. We estimate the minimal amount of data required to detect correlations depending on the type and relative frequency of the underlying non-random pattern, and show how increasing data size improves the statistical significance of the detected correlations.