In addition to the problems with Dual EC DRBG that have now been well documented, it is apparent to many of us in the clear bright light of the Snowden revelations that quite a few things that were previously dismissed as mere ineptitude or accident may in fact be aspects of a carefully planned and executed “advanced persistent threat”(APT). A number of aspects of TLS like extended random come to mind, for instance. Also the recent silent omission of the RSA 4096 modulus size from FIPS 140-2 CAVP algorithm testing.
But, I think the biggest aspect of this entire APT thing is hiding in plain sight. I’m referring to the very existence of the FIPS 140-2 validation program. Matt Green once quipped that “FIPS is the answer to the question ‘how can we force all cryptographic software to be approved by a government committee?’” and that about sums it up.
A common feature of these various engineered exploits we’re discovering is that they are relatively fragile. The positioning of Dual EC, for instance, must have been very tedious and expensive in time and money, and not just the $10M payment to RSA which was just the end game in a much longer process of discovering and developing the backdoored algorithm and guiding the formation of the technical standards and policies to encourage its use. In the “real” world of software development code is constantly tweaked, improved, refined, extended. It would suck to spend years and millions carefully maneuvering a subtle vulnerability into mainstream products (or to discover and exploit a naturally occurring vulnerability) only to have it suddenly vanish with a routine minor software upgrade.
The single most distinguishing (and IMHO deplorable) feature of FIPS 140-2 validation is the almost total prohibition of changes to validated modules. I call it the “ready, fire, aim” approach to software development: first there is a mad scramble to write your code and push it through the formal testing (which as we well know is shallow in terms of real-world implementation issues), as time is always a pressing concern when you have to wait 6, 9, or even 13(!) months for government action on the submission). Even absent rigged and constantly shifting standards that is a recipe for bugs. Then, once submitted you can’t change it even as the inevitable flaws are discovered. In the OpenSSL FIPS module for instance there are a number of vulnerabilities such as the notorious “Lucky 13″ and (recently) CVE-2014-0076 that we are not permitted to mitigate. That’s why I’ve long been on record as saying that “a validated module is necessarily less secure than its unvalidated equivalent”, e.g. the OpenSSL FIPS module versus stock OpenSSL.
That, I think, perhaps even more than rigged standards like Dual EC DRBG, is the real impact of the cryptographic module validation program. It severely inhibits the naturally occurring process of evolutionary improvement that would otherwise limit the utility of consciously exploited vulnerabilities.
The presence of Dual EC DRBG in the OpenSSL FIPS Object Module is a contemporary case in point. Even though it is not enabled by default, and even though an inadvertent bug means that it can’t even be used without a minor code change or other workarounds, the mere presence of that executable code still represents a vulnerability of sorts from the APT perspective. Imagine if you will that you were an APT agent responsible for maintaining the capability of accessing communications or data secured through Dual EC DRBG based cryptography. Your ideal situation is Dual EC DRBG used silently and automatically, as was the case with RSA BSAFE until recently. That particular channel is now closing, but second best is having the Dual EC DRBG code already present in a latent form where it can be enabled with the lightest of touches. As an APT agent you already have access to many target systems via multiple means such as “QUANTUM INTERCEPT” style remote compromises and access to products at multiple points in the supply chain. You don’t want to install ransomware or steal credit card numbers, you want unobtrusive and persistent visibility into all electronic communications. You want to leave as little trace of that as possible, and the latent Dual EC DRBG implementation in the OpenSSL FIPS module aids discrete compromise. By only overwriting a few words of object code you can silently enable use of Dual EC, whether FIPS mode is actually enabled or not. Do it in live memory and you have an essentially undetectable hack. In contrast introducing the multiple kilobytes of object code that implements Dual EC would require a much heavier touch.
So, on a general software hygiene basis, and particularly if you want to frustrate that level of APT compromise, you don’t want the Dual EC object code present at all. That is why OSF is attempting to remove the Dual EC DRBG implementation entirely from the OpenSSL FIPS Object Module 2.0. That pending revision will be 2.0.6 and the requisite formal paperwork (“Maintenance Letter”) was submitted to the CMVP on January 20, 2014. It’s typical to wait two to three months for review of such submissions and I hope to be updating this post soon to note a successful outcome. [update 2014-07024]: This “change letter” update was finally approved on 2014-06-27, more than six months after submission. Unfortunately, with approval uncertain we had to proceed in the interim with testing of new platforms on the original code base that still included Dual EC DRBG and that change letter for revision 2.0.7 was approved on 2014-07-03. So Dual EC DRBG was gone and then back in the blink of an eye. We will attempt to remove it again for the next upcoming revision, 2.0.8.
[updated 2014-03-29]:I should clarify the distinction between the two different hacks discussed here; enabling Dual EC DRBG and bypassing the POST integrity test. A hack in live memory would most likely take the form of tweaking the run-time variables that determine the DRBG; the POST could be ignored if it had already been performed, else the hack could just preset the global static variables that indicate the successful completion of a POST. A hack on the executable image on disk, i.e. libcrypto could involve bypassing the POST and/or integrity test as suggested in footnote 9.
[updated 2016-01-29]: Add CVE-2016-0701 to the list of vulnerabilities we’re forbidden to address in the FIPS module. Fortunately as a practical matter this vulnerability will only be an issue for the most obscure use cases; i.e. direct use of libcrypto and reuse of keys and use of affected DH parameters and FIPS mode enabled.
1 On the Practical Exploitability of Dual EC in TLS Implementations. This study examines actual Dual EC based TLS implementations, showing the ease of exploitation by anyone possessing the “up-my-sleeve” secret numbers. It does not address exploitation of other types of Dual EC based cryptography.
2 I’m trying to be neutral in the use of this term. There are two separate issues here, one being “is it right/appropriate/moral/prudent that <insert your nation-state APT agent of choice here> spy on <insert your target of choice here>?”. The other separate issue, assuming your answer to the first is “yes”, becomes “what are the implications of massive subversion of widely used technical standards and infrastructure?”. This discussion addresses the second issue and I attempt to avoid the first.
3 This is an odd one, not documented anywhere that I’m aware of (e.g., SP800-57 table 2 doesn’t exclude RSA key sizes above 3072). We noticed when researching the new RSA algorithm test vectors for the new post-2013 SP800-131A “transition” requirements that the 4096 modulus size had disappeared from the set of possible sizes (along with the smallest sizes which was expected). We inquired about this through a couple of test labs and the most coherent response we received was that 4096 was eliminated as “not practical”. That isn’t a very credible response on two counts: 1) OpenSSL has implemented 4096 and larger modulus sizes for a long time, and 2) the FIPS 140-2 validation testing process is rather notoriously unconcerned with “practicality”.
4 I’m referring to the Level 1 FIPS 140-2 validations which by design completely ignore issues like performance, buffer overruns, side-channel and other vulnerabilities, etc. Level 2 and higher do pay more attention to some security relevant issues, though still having the immutability problem.
5 Defenders of the status quo will correctly note that there is indeed a process for modifying already validated modules, and even a “fast track” for addressing urgent situations like security vulnerabilities. That process is even moderately feasible for some validations, the small ones encompassing only a few platforms (“Operational Environments”). For a larger validation, like #1747 with eighty platforms, the mandated retesting on each and every such platform, generally required even when study of the source code would clearly show no platform specific dependencies, isn’t even remotely feasible in either time or money. Anyone have roughly a million dollars to spare, and be willing to wait a couple of years for results?
6 Note this is much more than just TLS. Any RSA key pair generated using Dual EC is suspect, for instance encryption keys used to protect storage arrays (and obviously the data protected by those keys including unmounted disks), or hardware tokens where the seed record was generated with a toolkit using Dual EC (e.g. BSAFE).
7 Though I suspect it is closing very, very slowly. The presence or use of a cryptographic library often is not at all apparent to the end users of products that contain or reference it.
8 For proprietary closed source software this enabling can be done at any point in the product distribution process from initial vendor generation of executable code to final deployment on individual end systems. For open source software compiled by the end user, or for uncorrupted binary software distributed via a robust cryptographically secure means, this enabling must be effected against the deployed executable code. Such enabling can still be done relatively easily because the mechanism for run-time enabling of Dual EC is already present.
9 The integrity test mandated by FIPS 140-2 is worthless in preventing such a compromise (I’d even argue it is worthless period). The integrity test consists of an elaborate determination of a digest over the object code (executable code and read-only data) of the cryptographic module for comparison with a known good digest also embedded in the module. But you don’t even have to modify that embedded digest value, as on any machine architecture and for any compiler there will always be a conditional branch instruction at the point the fail/succeed determination is made. Depending on the specific architecture and compiler you just overwrite that conditional branch with a NOOP or an unconditional branch, a one word (or even one bit) mod.