Themes from Real World Crypto 2020

Over 642 brilliant cryptographic minds gathered for Real World Crypto 2020, an annual conference that brings together cryptographic researchers with developers implementing cryptography in the wild. Overall, RWC 2020 was an impressive conference that demonstrated some amazing work. Here we explore three major themes that emerged:

  1. Crypto bugs are everywhere...Whether it’s a somewhat unsurprising Bleichenbacher attack on TLS, or cryptographic side-channel attacks on (supposedly) secure hardware, there are a lot of cryptographic vulnerabilities out there. This became abundantly clear this past week.
  1. …so we need more cryptographers on projects…When designing, implementing, and reviewing cryptographic systems, the more cryptographers involved, the better. RWC 2020 featured big examples of how well collaboration can work, and how badly important systems can fail without it.
  1. …but cryptographic capabilities are growing fast! Advanced cryptography is becoming more practical, as shown by new multi-party computation frameworks and improvements to ZK-proofs. Plus we saw exciting new applications in Apple’s Find My protocol for finding offline devices, message authentication for satellites to prevent spoofing, and more.

Let’s dig in! 

1. Crypto bugs are everywhere

Traditional attacks

Yet another Bleichenbacher attack was presented: The 9 Lives of Bleichenbacher’s CAT:

New Cache ATtacks on TLS Implementations. (Which brings us to a fourth theme: Cryptographers still love using tortured puns and silly acronyms.) The attack leverages Bleichenbacher’s attack on PKCS#1 v1.5 padding for RSA key exchanges. Specifically, the attack takes advantage of the fact that many companies reuse certificates across multiple servers, so the Bleichenbacher attack can be parallelized and thus completed before the 30-second session timeout occurs. 

Unfortunately, this insecure padding scheme is still supported by ~6% of the internet; further, a man-in-the-middle downgrade attack can be performed, so any server that supports a vulnerable implementation can be broken 100% of the time (and this works even if the client does not support RSA key exchange).

Another talk, SHA-1 is a Shambles, discussed a chosen-prefix collision on SHA-1, and showed that SHA-1 can now be attacked in practice with affordable hardware.  The authors used this vulnerability to perform an impersonation attack on PGP. This project was the culmination of several years of work, with theoretical attacks discovered in the early 2000s, and the first practical attack found in the 2017 paper, SHAttered. In other words, SHA-1 shall never be used again (ok, coming up with puns is harder than it looks). 

Other attacks

Two different attacks on secure hardware were presented at RWC: one on a hardware security module (HSM) and another on a trusted platform module (TPM). The first attack targeted a specific HSM model and was able to (among other things) perform arbitrary code execution and decrypt all secrets. Although the attack itself was not heavily cryptographic, the talk demonstrated (yet again) that we cannot necessarily trust that our cryptographic secrets will be safe on HSMs. The second talk combined a timing side-channel attack with a lattice attack on ECDSA to recover the private signing key, demonstrating that TPMs are unfortunately not side-channel resistant.

Meanwhile, “Pseudorandom Black Swans: Cache Attacks on CTR DRBG” demonstrated that random number generators are also vulnerable to side-channel attacks. The cache attack leverages two problems with CTR_DRBG: Keys are not rotated fast enough, and adding more entropy is optional (and chosen by the API caller). This means keys can be compromised, and if inadequate entropy is used, an attack can then obtain all future states. These attacks were not a part of the previous standard’s threat model; fortunately, FIPS 140-3 updates this threat model.

2. The case for more cryptographers

From all of these attacks, the lesson is to involve more cryptographers and think about a variety of threat scenarios when designing your system (and in the case of the last talk, use Hash_DRBG). Several RWC 2020 presentations confirmed this. For instance, we saw how CRLite, a scalable system for TLS revocations, was achieved through academic and industrial collaboration. On the other hand, two different cryptographic reviews of e-voting systems and an analysis of the handshake protocol in WPA3 showed the dangers of too few cryptographic cooks.

The good

CRLite, the system for TLS revocations, started as an academic design and Firefox extension proof of concept; from there industry improved on the scheme, taking into account infrastructure that exceeded the means of academia alone. Now there is a working prototype and development is progressing while academia continues to refine the protocol.

More promising news came from model-checking 5G security: Our tools are sufficiently advanced that standardization now can and should be accompanied by formal models and analysis. This idea was pioneered by the symbolic analysis of TLS 1.3, and it’s great to see the trend continuing. These types of analysis are very powerful for protocols and standards, as they ensure that security goals are clearly stated and achieved by the protocol. 

In the case of 5G, the security goals were not clearly stated in the initial conception of the protocol. The RWC 2020 presentation, “A Formal Analysis of 5G Authentication,” specified the security goals more clearly, which led to the discovery that 5G does not achieve untraceability (perhaps this is bad after all!). Nevertheless, this work serves as an important demonstration and should be replicated for future standardization efforts.

The bad

“Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd” makes a pretty compelling case for involving cryptographers in protocol design. WPA2 is vulnerable to offline dictionary attacks, and WPA3 was proposed as the improvement. However, Dragonblood found that WPA3 is vulnerable to side-channels, and, according to the authors of the paper, “WPA3 does not meet the standards of a modern security protocol.” To make matters worse, the countermeasures are costly and may not be adopted. Worst of all, as the authors state, these issues could have been avoided if the protocol design process was open to more cryptographers.

The ugly

There’s plenty of ugliness in the world of e-voting, as the talks at RWC 2020 confirmed. In one analysis of the Moscow internet voting system, two significant breaks to the encryption scheme were found within a somewhat constrained time frame. For example, the first break resulted from an insecure variant of ElGamal dubbed “Triple ElGamal,” which attempted to achieve 768-bit security, but actually achieved three separate instances of 256-bit security, which can be broken in under 10 minutes using CADO-NFS

Both breaks cited were fixed; however, the fixes to the second break were published only two days before the election, and the technology was still deployed. The general impression of the presenter was that the voting scheme achieved no privacy, very partial verifiability, no coercion resistance, and no protection against vote-buying. Although the Russian government should be commended for opening their source code, it is clear that more cryptographers should have been involved in this entire process.

Similar work on the Switzerland internet voting system led to the discovery of some significant cryptographic bugs. The protocol uses a zero-knowledge proof system to achieve both privacy and verifiability; however, due to a flaw in their Fiat-Shamir transformation, none of the zero-knowledge proofs were sound. Further, parameters were generated incorrectly in a way that could allow for votes to be modified. Even worse, statements were malformed for their zero-knowledge proofs, which broke their security proofs. This result is not ideal. However, to be fair, it is great to see cryptographers involved, as critical issues were spotted before deployment in Switzerland (and revealed similar issues to non-public systems in other countries).

3. New growth and cryptography applications

It’s not all bad; our cryptographic capabilities are growing quickly! And RWC 2020 displayed some fascinating efforts to apply cryptography to real world problems.

“Find My” cryptography

Earlier this year, Apple released a new “Find My” feature in iOS 13 that allows offline devices to be located while protecting privacy of both the owner and the finder of the device. Previously, similar features like “Find My Phone” required the device to be online, a serious limitation, particularly for devices like MacBooks which are typically offline. The cryptography behind this feature was presented at RWC 2020. Apple sought a protocol that achieved the following goals: 

  • Only the owner of the device can track the device and access location reports remotely
  • Previous locations of the device are protected if the device is compromised 
  • Owners only receive anonymous information from the finder  
  • The finder’s location is never revealed to others (including the server) 

To achieve this, the protocol calls for offline devices to broadcast public keys via Bluetooth. Active devices become “finders,” and when other offline devices are discovered via Bluetooth, the finder encrypts its location using the offline device’s public key and sends it to the cloud. This way, even the server does not know the location—however, IP-based information does leak to the server, and Apple’s only promise is that they do not store logs of this information.

The owner can then access the time and location of their offline device whenever there is an active device in its vicinity. (There are more subtleties to the protocol to achieve the remaining security goals, such as key rotation). In summary, Apple specified rigorous security and privacy goals, and constructed a novel design in their attempt to achieve them.

Private detection of compromised credentials

Protocols for Checking Compromised Credentials” presented a formal security analysis of two protocols for checking compromised credentials: HaveIBeenPwned (HIBP) and Google Password Checkup (GPC). These protocols aim to alert users if their credentials have been breached and shared across the web. GPC maintains an active database of username and password pairs for users to query. HIBP, on the other hand, only maintains passwords. 

Since these databases contain hundreds of millions of records, both protocols implement a bucketization strategy, where hash values corresponding to records are sorted into buckets, based on their hash prefix. This allows users to query the database with a hash prefix, receive a bucket of hash values, and check if their credentials have been compromised, without revealing their entire hash of their secret to the server. The study presented at RWC 2020 demonstrated that each protocol leaks noticeable information about user secrets due to their bucketization strategies—both protocols leak information for different, subtle reasons. Luckily, the study also produced mitigation strategies for both protocols.

Out of this world cryptography

RWC even included some cryptographic applications that are out of this world. Galileo is a global navigation satellite system (like GPS) used by the European Union. As discussed at RWC, these navigation systems are a critical part of our infrastructure, and spoofing location is actually fairly easy. Luckily, so far, this spoofing is mostly used for playing Pokemon Go; however, spoofing attacks on these satellite systems are real. To protect against potential future attacks, Galileo will offer a public navigation message authentication service.

Banking on collaboration

The final talk at RWC discussed using multi-party computation to detect money laundering. Financial regulators impose large fines on banks if they allow money laundering activities, so these banks are incentivized to detect illegal activities. However, collaboration between banks is difficult because transaction data is private. Fortunately, multi-party computation can facilitate this collaboration without violating privacy. Overall, this effort achieved promising results by applying a graph-based approach for modeling transactions and algorithms specialized for multi-party computation for efficient, collaborative analysis between various banks.

Conclusion

RWC 2020 made it clear that involving cryptographers in the design and implementation of your novel protocols will save you both time and money, as well as keeping everyone safer. If you’re involved in this type of work encourage everyone involved to open-source your code, publish your protocols for review, and hey, talk to the Trail of Bits cryptography team!

One thought on “Themes from Real World Crypto 2020

  1. Pingback: Announcing the 1st International Workshop on Smart Contract Analysis | Trail of Bits Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s