We investigate the security properties of the three deterministic random bit generator (DRBG) mechanisms in the NIST SP 800-90A standard . This standard received a considerable amount of negative attention, due to the controversy surrounding the now retracted DualEC-DRBG, which was included in earlier versions. Perhaps because of the attention paid to the DualEC, the other algorithms in the standard have received surprisingly patchy analysis to date, despite widespread deployment. This paper addresses a number of these gaps in analysis, with a particular focus on HASH-DRBG and HMAC-DRBG. We uncover a mix of positive and less positive results. On the positive side, we prove (with a caveat) the robustness  of HASH-DRBG and HMAC-DRBG in the random oracle model (ROM). Regarding the caveat, we show that if an optional input is omitted, then – contrary to claims in the standard — HMAC-DRBG does not even achieve the (weaker) property of forward security. We also conduct a more informal and practice-oriented exploration of flexibility in implementation choices permitted by the standard. Specifically, we argue that these DRBGs have the property that partial state leakage may lead security to break down in unexpected ways. We highlight implementation choices allowed by the overly flexible standard that exacerbate both the likelihood, and impact, of such attacks. While our attacks are theoretical, an analysis of two open source implementations of CTR-DRBG shows that potentially problematic implementation choices are made in the real world.
We present True2F, a system for second-factor authentication that provides the benefits of conventional authentication tokens in the face of phishing and software compromise, while also providing strong protection against token faults and backdoors. To do so, we develop new lightweight two-party protocols for generating cryptographic keys and ECDSA signatures, and we implement new privacy defenses to prevent cross-origin token-fingerprinting attacks. To facilitate real-world deployment, our system is backwards-compatible with today’s U2F-enabled web services and runs on commodity hardware tokens after a firmware modification. A True2F-protected authentication takes just 57ms to complete on the token, compared with 23ms for unprotected U2F.
Software implementations of discrete logarithm based cryptosystems over finite fields typically make the assumption that any domain parameters they encounter define cyclic groups for which the discrete logarithm problem is assumed to be hard. In this paper we explore this trust assumption and examine situations where it may not be justified. In particular we focus on groups for which the order is unknown and not easily determined, and explore the scenario in which the modulus is trapdoored to make computing discrete logarithms efficient for an entity with knowledge of the trapdoor, while simultaneously leaving its very existence as matter of speculation to everyone else.
We conducted an investigation of discrete logarithm domain parameters in use across the Internet and discovered a multitude of instances of groups of unknown order in use in TLS and STARTTLS spanning numerous countries, organizations, and implementations. Although our disclosures resulted in a number of organizations taking down their suspicious parameters, none were able or willing to rule out the possibility that their parameters were trapdoors, and obtaining conclusive evidence in each case could be as hard as factoring an RSA modulus, highlighting a key feature of this attack method deniability.