NIST Moves on Sweet32 - 3DES, Blowfish, and Others - Mostly Unsafe
By David Gamey - 19 Jul 2017.
Now is the time to stop using 64-bit block length ciphers such as 3DES (TDEA) and Blowfish in general purpose applications of cryptography. In 2016, an attack was demonstrated that affects all ciphers using 64-bit block lengths, including the most commonly used ciphers 3DES (TDEA), Blowfish, and IDEA; and specialized ciphers such as KASUMI, PRESENT, and HIGHT used in cellular, low power, and low resource applications.
The attack is novel, at least for the public, in that it does not hinge on the cipher algorithm, the key length, or the way the cipher is used. Before people panic, there are some use-cases that remain safe. There are, however, many unsafe use-cases that need to be addressed. The weakness stems from the fact that ciphers cannot use their keys indefinitely and keys must be changed before a critical volume of material is encrypted. Block length determines this frequency and modern ciphers like AES moved to 128-bit block lengths specifically to address this risk.
Naturally, you may be wondering why this hasn't been bigger news? Or why NIST or ISO hasn't deprecated 64-bit block ciphers earlier? All good questions. Perhaps they should have. We can only speculate, but it may be because this vulnerability is just a bit different, that it isn't related to key strength, protocol design, or implementation flaws. It may also be because there are mitigating strategies. However, the better question is are you at risk? And if so, how to make sense out of this and know what to do?
Note: NIST just announced their intent to deprecate TDEA (3DES). They are open for comments and feedback until October 1st, 2017. The announcement focuses on 3DES as the other ciphers were not promoted by NIST.
The State of Strong Cryptography
Before we look at this development, let's review recent history of cryptographic vulnerabilities.
- The strongest form of 3DES (aka TDEA) uses 3 rounds of DES with 3 different keys (i.e. 168-bits of keys). Well known weaknesses in 3DES mean that the effective strength is only 112-bits not 168-bits. Two key 3DES is too weak for general purpose applications; however, there are some special use-cases such as in payments and banking where 2-key 3DES can be used safely with constructs such as Derived Unique Key Per Transaction (DUKPT).
- Most Internet security protocols were developed before AES at a time when 64-bit block ciphers were standard. Many of these protocols were designed to be "agile" supporting multiple configurable ciphers and protocol versions. This flexibility facilitated both security upgrades and support of diverse client systems that were nearly seamless. In recent years, most of these protocols have been upgraded, enhanced, or outright replaced. Unfortunately, old crypto is often left lingering around for years past it's prime.
- Over the last 20 years, key strengths have increased from 56 to 128 bits (symmetric keys) and from 768 to 2048 bits (RSA keys).
- Hash algorithms like MD5 and SHA-1 are no longer secure.
- SSL and early TLS were deprecated due to a steady stream of attacks.
- Cipher Block Chaining (CBC) modes are showing weaknesses.
Summary of Recent Cryptographic Vulnerabilities
Recent years have seen a flood of attacks and bugs that affect Internet security. Many of these took a decade or more of research to develop after the discoveries of the original weaknesses:
- Implementation bugs (e.g. HeartBleed, or Virtual Host Confusion) are unrelated to the cryptography. Basically, these aren't design problems but are coding blunders that can be found and fixed. They tend to be widespread only if the library or solution is also widespread.
- Weaknesses in cryptographic algorithms (i.e. RC4, SHA1, MD5 , and Diffie-Hellman Key Exchange) as have been demonstrated in NOMORE, LogJam, SLOTH, and other attacks.
- Protocol downgrade attacks (e.g. DROWN, FREAK) force fallback to insecure methods.
- Attacks exploiting timing issues and compression (e.g. TIME, CRIME, BREACH).
- Padding Oracle problems with CBC mode ciphers (e.g. BEAST, POODLE, Lucky13).
The problem resulting from not changing keys often enough is known to cryptographers as the "Birthday Bound". It's related to the Birthday Paradox, where you only need about 23 people in a room to have a 50% chance of two of them having the same birthday.
The weakness arises because of "collisions" in the cipher output. By XOR'ing the collisions an attacker can get close to the plain text. If they also know some of the plain text or can predict it, then they can begin peeling back the encryption. And the more collisions and known plain text they have, the more they can decrypt.
The chance of collisions grows with the volume of encrypted data and becomes significant as volumes near the birthday bound. For 64-bit block ciphers this is 232 or about 4 billion blocks.
Attackers have a much easier time when they can control more of the plain text and when interesting data repeats. The attack framework used in BEAST and POODLE does an excellent job here.
The attack, called "Sweet32", was demonstrated last summer. It used the BEAST framework to significant advantage by forcing re-transmission of high volumes of valuable secrets. It succeeded in a surprisingly short time, specifically:
- 19 hours and 705GB of traffic to retrieve an HTTP session cookie protected by TLS / 3DES
- 30 hours and 610GB of traffic to retrieve an HTTP basic authentication credential protected by OpenVPN / Blowfish
The main risk factors for 64-bit block collision attacks are:
- Lengthy transmissions or transmissions than can be lengthened
- Connections where the attacker can inject large amounts of known plain text
- Connections that re-key traffic infrequently
- End-points susceptible to malware
- Connections that relay content
Given these factors, some 64-bit block use-cases are clearly unsafe
- Browsers and web-sites
- Site-to-site VPNs
- Encrypted email links
- Large file transfers
- Older legacy systems
Safe use-cases will have characteristics such as:
- Non-interactive / programmed
- Short / burst transmissions
- Frequent re-keying of transmissions
- Locked down endpoints
Impact on PCI Compliance Standards
Historically, PCI has taken its lead on cryptography matters from NIST. One only has to look at the deprecation of SSLv2, RSA 1024, and SSL/early TLS for examples. NIST's move to begin the deprecation of TDEA will inevitably result in PCI following suit. It's a fair question to ask: what will the this process will look like?
There is some good news in this as an excellent example of a safe use-case would be a hardware payment terminal connecting to a processors payment gateway for a credit/debit transaction. Consider:
- PTS approved terminals have a code signing mechanism that effectively locks down the end-point
- Many hardware payment terminals start new connections and re-key every transaction
- Limited opportunities for chosen plain text injection exist and these typically need manual interaction
These are typically payments based use-cases and these are precisely the same reasons that, despite POODLE, hardware terminals running SSL 3.0 can often get a pass under PCI DSS. Additionally, other cases such as small cryptograms in databases and message fields shouldn't be affected.
If there were no safer use cases and it were just the case of the cipher's use by individual organizations, there would likely be no modification of DSS as it would be covered by the general deference to NIST's position on strong cryptography. However, a major concern will be the impact on companion standards and the large world-wide installed base of payment devices, such as POS terminals, and ATMs. Final replacement of 3DES will take time and cost billions in upgrades and replacements.
This is our prediction as to how this process will unfold:
- The PCI SSC will begin to look at this issue and will publish interim guidance in preparation to update the DSS
- A final position will wait until NIST makes its recommendations which is expected in late 2017Q3.
- There will be a deprecation process and supporting requirements similar to, possibly an extension of, PCI DSS 3.2's Appendix A2: Additional PCI DSS Requirements for Entities using SSL/early TLS
- The process will similarly be three phased, firstly targeting short blocked ciphers in general use cases, then software use cases, and finally approved hardware use cases with set time frames for the first two phases
- There will need to be significant industry consultations to help set the time lines
- In addition to the DSS changes several of the other PCI standards, such as PA-DSS, PTS, P2PE, etc., will need adjustments as the world moves away from 3DES.
We would hope, that to maintain an even playing field, any changes to the PA-DSS will allow for the continued use of 3DES in hardware terminal based applications only where the encryption is provided by the PTS approved mechanism until those are deprecated.
Finally, we would expect to see a PCI DSS revision (possibly v3.3) in 2018 coming into effect after June 30th when all current future dated requirements become locked in.
What To Do?
Getting rid of 64-bit block ciphers should be easier than eliminating SSL. Still it will require planning including impact analysis. In each case consider:
- How easily can the cipher be replaced? Fortunately, most Internet security protocols are agile and can be configured to support or drop support for specific algorithms. Unfortunately, some legacy end-points may not support stronger ciphers. And while the prospect of losing a few customers with ancient browsers runs counter to most businesses philosophy, the real challenges will be internal legacy and B2B systems.
- It may be possible to force re-keying long before you get near a risky volume of data. The challenge is that this typically needs application modifications since protocols such as TLS only support but don't enforce re-keying.
Organizations should begin planning today:
- Understand where they are using legacy ciphers both externally and internally
- Prioritize the unsafe and at-risk use-cases
- Determine options to permanently replace the legacy ciphers or to mitigate their use in the short term
- Understand and document your use-cases and their associated risks
Vulnerability scanners will flag these legacy ciphers when used in a protocol. If you run scans as part of a compliance program such as PCI's ASV, the existence of these legacy ciphers will become a compliance issue. The scanners won't know if your use-case is safe and the documentation of those cases will be invaluable to show the finding is a false alarm and obtaining an exemption.
As for applications using small cryptograms, while they remain safe for now, industry and individual organizations need to start thinking about how they will replace them in the long term so that it doesn't become an emergency. This effort will eventually address the use of 3DES in financial systems such as ATMs and POS terminals.
- NIST announces plans to deprecate TDEA (3DES) https://beta.csrc.nist.gov/News/2017/Update-to-Current-Use-and-Deprecation-of-TDEA
- Vulnerability website https://sweet32.info/
- CCS 2016 web site https://www.sigsac.org/ccs/CCS2016/
- Presentation from CCS 2016 https://www.youtube.com/watch?v=KmBfBBkm1j0
- Technical paper "On the practical (in-Security) of 64-bit Block Ciphers" Karthikeyan Bhargavan, Gaëtan Leurent https://sweet32.info/SWEET32_CCS16.pdf
- Paper on various collision attacks on 64-bit block ciphers (referenced by Sweet32) https://eprint.iacr.org/2012/623.pdf
- SSL Labs https://blog.qualys.com/ssllabs/2017/01/18/ssl-labs-grading-changes-january-2017
- SHA-1 is dead https://controlgap.com/blog/sha-1-is-dead/
- PCI Security Standards Council set to kill off SSL in PCI DSS/PA-DSS 3.1 updates https://controlgap.com/blog/pci-dss-3-1-updates/
- DUKPT https://en.wikipedia.org/wiki/Deriveduniquekeypertransaction
- The Birthday Paradox https://en.wikipedia.org/wiki/Birthday_problem