The output of cryptographic functions, be it encryption routines or hash functions, should be statistically indistinguishable from a truly random data for an external observer. The property can be partially tested automatically using batteries of statistical tests. However, it is not easy in practice: multiple incompatible test suites exist, with possibly overlapping and correlated tests, making the statistically robust interpretation of results difficult. Additionally, a significant amount of data processing is required to test every separate cryptographic function. Due to these obstacles, no large-scale systematic analysis of the the round-reduced cryptographic functions w.r.t their input mixing capability, which would provide an insight into the behaviour of the whole classes of functions rather than few selected ones, was yet published. We created a framework to consistently run 414 statistical tests and their variants from the commonly used statistical testing batteries (NIST ST S, Dieharder, TestU01, and BoolTest). Using the distributed computational cluster providing required significant processing power, we analyzed the output of 109 round-reduced cryptographic functions (hash, lightweight, and block-based encryption functions) in the multiple configurations, scrutinizing the mixing property of each one. As a result, we established the fraction of a function’s rounds with still detectable bias (a.k.a. security margin) when analyzed by randomness statistical tests.

We measure the popularity of cryptographic libraries in large datasets of RSA public keys. We do so by improving a recently proposed method based on biases introduced by alternative implementations of prime selection in different cryptographic libraries. We extend the previous work by applying statistical inference to approximate a share of libraries matching an observed distribution of RSA keys in an inspected dataset (e.g., Internet-wide scan of TLS handshakes). The sensitivity of our method is sufficient to detect transient events such as a periodic insertion of keys from a specific library into Certificate Transparency logs and inconsistencies in archived datasets.

The semiconductor industry is fully globalized and integrated circuits (ICs) are commonly defined, designed and fabricated in different premises across the world. This reduces production costs, but also exposes ICs to supply chain attacks, where insiders introduce malicious circuitry into the final products. Additionally, despite extensive post-fabrication testing, it is not uncommon for ICs with subtle fabrication errors to make it into production systems. While many systems may be able to tolerate a few byzantine components, this is not the case for cryptographic hardware, storing and computing on confidential data. For this reason, many error and backdoor detection techniques have been proposed over the years. So far all attempts have been either quickly circumvented, or come with unrealistically high manufacturing costs and complexity.

We report on our discovery of an algorithmic flaw in the construction of primes for RSA key generation in a widely-used library of a major manufacturer of cryptographic hardware. The primes generated by the library suffer from a significant loss of entropy. We propose a practical factorization method for various key lengths including 1024 and 2048 bits. Our method requires no additional information except for the value of the public modulus and does not depend on a weak or a faulty random number generator. We devised an extension of Coppersmith's factorization attack utilizing an alternative form of the primes in question. The library in question is found in NIST FIPS 140-2 and CC~EAL~5+ certified devices used for a wide range of real-world applications, including identity cards, passports, Trusted Platform Modules, PGP and tokens for authentication or software signing. As the relevant library code was introduced in 2012 at the latest (and probably earlier), the impacted devices are now widespread. Tens of thousands of such keys were directly identified, many with significant impacts, especially for electronic identity documents, software signing, Trusted Computing and PGP. We estimate the number of affected devices to be in the order of at least tens of millions.

The wide range of security applications requires data either truly random or indistinguishable from the random. The statistical tests included in batteries like NIST STS or Dieharder are frequently used to assess this randomness property. We designed principally simple, yet powerful statistical randomness test working on the bit level and based on a search for boolean function(s) exhibiting bias not expected for truly random data when applied to the tested stream. The deviances are detected in seconds rather than tens of minutes required by the common batteries. Importantly, the boolean function exhibiting the bias directly describes the pattern responsible for this bias - allowing for construction of bit predictor or fixing the cause of bias in tested function design. The present bias is frequently detected in at least order of magnitude less data than required for NIST STS or Dieharder showing that the tests included in these batteries are either too simple to spot the common biases (like Monobit test) or overly complex (like Fourier Transform test) which requires an extensive amount of data. The proposed approach called BoolTest fills this gap. The performance was verified on more than 20 real world cryptographic functions – block and stream ciphers, hash functions and pseudorandom generators. Among others, the previously unknown bias in output of C rand() and Java Random generators which can be utilized as practical distinguisher was found.

Network Address Translators often cause trouble for VoIP and other P2P services since central servers are needed for communication. The presence of such potentially malicious hosts in a communication path is not desired, mainly due to security consequences, poor link quality and increased cost. Several solutions exist for traversing NAT, but a symmetric one is still problematic. We propose algorithms using a single source port for symmetric NAT traversal. Each with different properties and applicability.