david wong

Hey! I'm David, a security engineer at the Blockchain team of Facebook, previously a security consultant for the Cryptography Services of NCC Group. I'm also the author of the Real World Cryptography book. This is my blog about cryptography and security and other related topics that I find interesting.

User authentication with passwords, What’s SRP? posted 2 weeks ago

The Secure Remote Password (SRP) protocol is first and foremost a Password Authenticated Key Exchange (PAKE). Specifically, SRP is an asymmetric or augmented PAKE: it’s a key exchange where only one side is authenticated thanks to a password. This is usually useful for user authentication protocols. Theoretically any client-server protocol that relies on passwords (like SSH) could be doing it, but instead such protocols often have the password directly sent to the server (hopefully on a secure connection). As such, asymmetric PAKEs offer an interesting way to augment user authentication protocols to avoid the server learning about the user’s password.

Note that the other type of PAKE is called a symmetric or balanced PAKE. In a symmetric PAKE two sides are authenticated thanks to the same password. This is usually useful in user-aided authentication protocols where a user attempts to pair two physical devices together, for example a mobile phone or laptop to a WiFi router. (Note that the recent WiFi protocol WPA3 uses the DragonFly symmetric PAKE for this.)

user (aided) authentication

In this blog post I will answer the following questions:

  • What is SRP?
  • How does SRP work?
  • Should I use SRP today?

What is SRP?

The stanford SRP homepage puts it in these words:

The Secure Remote Password protocol performs secure remote authentication of short human-memorizable passwords and resists both passive and active network attacks. Because SRP offers this unique combination of password security, user convenience, and freedom from restrictive licenses, it is the most widely standardized protocol of its type, and as a result is being used by organizations both large and small, commercial and open-source, to secure nearly every type of human-authenticated network traffic on a variety of computing platforms.

and goes on to say:

The SRP ciphersuites have become established as the solution for secure mutual password authentication in SSL/TLS, solving the common problem of establishing a secure communications session based on a human-memorized password in a way that is crytographically sound, standardized, peer-reviewed, and has multiple interoperating implementations. As with any crypto primitive, it is almost always better to reuse an existing well-tested package than to start from scratch.

But the Stanford SRP homepage seems to date from the late 90s.

SRP was standardized for the first time in 2000 in RFC 2944 - Telnet Authentication: SRP. Nowadays, most people refer to SRP as the implementation used in TLS. This one was specified in 2007 in RFC 5054 - Using the Secure Remote Password (SRP) Protocol for TLS Authentication.

How does SRP work?

The Stanford SRP homage lists 4 different versions of SRP, with the last one being SRP 6. Not sure where version 4 and 5 are, but version 6 is the version that is standardized and implemented in TLS. There is also the revision SRP 6a, but I’m also not sure if it’s in use anywhere today.

SRP registration

To register, Alice sends her identity, a random $salt$, and a salted hash $x$ of her password. Right from the start, you can see that a hash function is used (instead of a password hash function like Argon2) and thus anyone who sees this message can efficiently brute-force the hashed password. Not great. The use of the user-generated salt though, manage to prevent brute-force attacks that would impact all users.

The server can then register Alice by exponentiating a generator of a pre-determined ring (an additive group with a multiplicative operation) with the hashed password. This is an important step as you will see that anyone with the knowledge of $x$ can impersonate Alice.

What follows is the login protocol:

SRP login

You can now see why this is called a password authenticated key exchange, the login flow includes the standard ephemeral key exchange with a twist: the server’s public key $B’$ is blinded or hidden with $v$, a random value derived from Alice’s password. (Note here $k$ is a constant fixed by the protocol so we will just ignore it.)

Alice can only unblinds the server’s ephemeral key by deriving $v$ herself. To do this, she needs the $salt$ she registered with (and this is why the server sends it back to Alice as part of the flow). 
For Alice, the SRP login flow goes like this:

  • Alice re-computes $x = H(salt, password)$ using her password and the salt received from the server.
  • Alice unblinds the server’s ephemeral key by doing $B=B’- kg^x = g^b$
  • Alice then computes the shared secret $S$ by multiplying the results of two key exchanges:
    • $B^a$, the ephemeral key exchange
    • $B^{ux}$, a key exchange between the server’s public key and a value combining the hashed password and the two ephemeral public keys


Interestingly, the second key exchange makes sure that the hashed password and the transcript gets involved in the computation of the shared secret. But strangely, only the public keys and not the full transcript are used.

The server can then compute the shared secret $S$ as well, using the multiplication of the same two key exchanges:

  • $A^b$, the ephemeral key exchange
  • $v^{ub}$, the other key exchange involving the hashed password and the two ephemeral public keys

The final step is for both sides to hash the shared secret and use it as the session key $K = H(S)$. Key confirmation can then happen after both sides make successful use of this session key. (Without key confirmation, you’re not sure if the other side managed to perform the PAKE.)

Should I use SRP today?

The SRP scheme is a much better way to handle user passwords, but it has a number of flaws that make the PAKE protocol less than ideal. For example, someone who intercepts the registration process can then easily impersonate Alice as the password is never directly used in the protocol, but instead the salted hash of the password which is communicated during the registration process.

This was noticed by multiple security researchers along the years. Matthew Green in 2018 wrote Should you use SRP?, in which he says:

Lest you think these positive results are all by design, I would note that there are [five prior versions] of the SRP protocol, each of which contains vulnerabilities. So the current status seems to have arrived through a process of attrition, more than design.

After noting that the combination of multiplication and addition makes it impossible to implement in elliptic curve groups, Matthew Green concludes with:

In summary, SRP is just weird. It was created in 1998 and bears all the marks of a protocol invented in the prehistoric days of crypto. It’s been repeatedly broken in various ways, though the most recent [v6] revision doesn’t seem obviously busted — as long as you implement it carefully and use the right parameters. It has no security proof worth a damn, though some will say this doesn’t matter (I disagree with them.)

Furthermore, SRP is not available in the last version of TLS (TLS 1.3).

Since then, many schemes have been proposed, and even standardized and productionized (for example PAK was standardized by Google in 2010) The IETF 104, March 2019 - Overview of existing PAKEs and PAKE selection criteria has a list:

PAKE list

In the summer of 2019, the Crypto Forum Research Group (CFRG) of the IETF started a PAKE selection process, with goal to pick one algorithm to standardize for each category of PAKEs (symmetric/balanced and asymmetric/augmented):

PAKE CFRG selection process

Two months ago (March 20th, 2020) the CFRG announced the end of the PAKE selection process, selecting:

  • CPace as the symmetric/balanced PAKE (from Björn Haase and Benoît Labrique)
  • OPAQUE as the asymmetric/augmented PAKE (from Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu)

Thus, my recommendation is simple, today you should use OPAQUE!

If you want to learn more about OPAQUE, check out chapter 11 of my book real world cryptography.

2 comments

Alternatives to PGP posted 4 weeks ago

As part of my book's chapter on end-to-end encryption I've been writing about the horrors of PGP.

As a recap of what's bad with PGP:

  • No authenticated encryption. This is my biggest issue with PGP personally.
  • Receiving a signed message means nothing about who sent it to you (see picture below).
  • Usability issues with GnuPG (the main implementation).
  • Discoverability of public keys issue.
  • Bad integration with emails.
  • No forward secrecy.

For more, see my post on a history of end-to-end encryption and the death of PGP.

signature pgp

(excerpt from the book Real World Cryptography)

The latter two I don't care that much. Integration with email is doomed from my point of view. And there's just not way to have forward secrecy if we want a near-stateless system.

Email is insecure. Even with PGP, it’s default-plaintext, which means that even if you do everything right, some totally reasonable person you mail, doing totally reasonable things, will invariably CC the quoted plaintext of your encrypted message to someone else (we don’t know a PGP email user who hasn’t seen this happen). PGP email is forward-insecure. Email metadata, including the subject (which is literally message content), are always plaintext. (Thomas Ptatcek)

OK so what can I advise to my readers? What are the alternatives out there?

For file signing, Frank Denis wrote minisign which looks great.

minisign

For file encryption, I wrote eureka which does the job. There's also magic wormhole which is often mentioned, and does some really interesting cryptography, but does not seem to address a real use-case (in my opinion) for the following reason: it's synchronous. We already have a multitude of asynchronous ways to transfer files nowadays (dropbox, google drive, email, messaging, etc.) so the problem is not there. Actually there's really no problem... we just all need to agree on one way of encrypting a file and eureka does just that in a hundred lines of code.

(There is a use-case for synchronous file transfer though, and that's when we're near by. Apple's airdrop is for that.)

eureka

For one-time authenticated messaging (some people call that signcryption) which is pretty much the whole use-case of PGP, there seems to be only one contender so far: saltpack. The format looks pretty great and seems to address all the issues that PGP had (except for forward secrecy, but again I don't consider this a deal breaker). It seems to only have two serious implementations: keybase and keys.pub. Keybase a bit more involved, and keys.pub is dead simple and super well put. Note that age and rage (which are excellent engineering work) seem to try to address this use case. Unfortunately they do not provide signing as Adam Caudill pointed out. Let's keep a close eye on these tools though as they might evolve in the right direction. To obtain public keys, the web of trust (signing other people keys) hasn't been proven to really scale, instead we are now in a different key distribution model where people broadcast their public keys on various social networks in order to instill their identity to a specific public key. I don't think there's a name for it... but I like to call it broadcast of trust.

keys.pub

For encrypted communications, Signal has clearly succeeded as a proprietary solution, but everyone can benefit from it by using other messaging apps like WhatsApp and Wire or even federated protocols like Matrix. Matrix' main implementation seems to be Riot which I've been using and really digging so far. It also looks like the French government agrees with me. Same thing here, the web of trust doesn't seem to work, and instead what seems to be working is relying on centralized key distribution servers and TOFU but verify (trust the first public key you see, but check the fingerprint out-of-band later).

riot

5 comments

Hardware Solutions To Highly-Adversarial Environments Part 3: Trusted Execution Environment (TEE), SGX, TrustZone and Hardware Security Tokens posted last month

This is end of my blog post series on cryptography with hardware. I’ve written about smart cards and secure elements in part 1 and about HSMs and TPMs in part 2.

Trusted Execution Environment (TEE)

So far, all of the hardware solutions we’ve talked about have been standalone secure hardware solutions (with the exceptions of smart cards which can be seen as tiny computers). Secure elements, HSMs, and TPMs can be seen as an additional computer.

standalone vs integrated

(picture taken from The right secure hardware for your IoT deployment)

Let’s now talk about integrated secure hardware!

Trusted Execution Environment (TEE) is a concept that extends the instruction set of a processor to allow for programs to run in a separate secure environment. The separation between this secure environment and the ones we are used to deal with already (often called “rich” execution environment) is done via hardware. So what ends up happening is that modern CPUs run both a normal OS as well as a secure OS simultaneously. Both have their own set of registers but share most of the rest of the CPU architecture (and of course system). By using clever CPU-enforced logic, data from the secure world cannot be accessed from the normal world. Due to TEE being implemented directly on the main processor, not only does it mean a TEE is a faster and cheaper product than a TPM or secure element, it also comes for free in a lot of modern CPUs.

TEE like all other hardware solutions has been a concept developed independently by different vendors, and then a standard trying to play catch up (by Global Platform). The most known TEEs are Intel’s Software Guard Extensions (SGX) and ARM’s TrustZone. But there are many more like AMD PSP, RISC-V MultiZone and IBM Secure Service Container.

By design, since a TEE runs on the main CPU and can run any code given to it (in a separate environment called an “enclave”), it offers more functionality than secure elements, HSMs, TPMs (and TPM-like chips). For this reason TEEs are used in a wilder range of applications. We see it being used in clouds when clients don’t trust servers with their own data, multi-party computation (see CCF), to run smart contracts.

TEE’s goal is to first and foremost thwart software attacks. While the claimed software security seems to be really attractive, it is in practice hard to segregate execution while on the same chip as can attest the many software attacks against SGX:

Trustzone is not much better, Quarkslab has a list of paper successfully attacking it as well.

security

(picture taken from Certification of the Trusted Execution Environment – one step ahead for secure mobile devices)

In theory a TPM can be re-implemented in software only via a TEE (which was done by Microsoft) but one must be careful as again, TEE as a concept provides no resistance against hardware attacks besides the fact that things at this microscopic level are way too tiny and tightly packaged together to analyze without expensive equipment. But by default a TEE does not mean you’ll have a secure internal storage (you need to have a fused key that can’t be read to encrypt what you want to store), or a hardware random number generator, and other wished hardware features. But every manufacturers sure has different offers with different levels of physical security and tamper resistance when it comes to chip that supports TEE.

Hardware Security Tokens

Finally, hardware security tokens are keys that you can usually plug into your machine and that can do some cryptographic operations. For example yubikeys are small dongles that you can plug in the USB port of a laptop, and that will perform some cryptographic operations if you touch its yellow ring.

yubikey

The word “token” in hardware security token comes from the fact that using it produces a “token” per-authentication request instead of sending the same credentials over and over again.

Yubikeys started as a way to provide 2nd factor authentication, usually in addition to a password, which an attacker can’t exploit in a phishing attack. The idea is that if an attacker calls your grandmother, and asks her to spell out the yubikey output, she won’t be able to. There is no output. Furthermore, modern yubikeys implement the FIDO 2 protocol which will not produce the correct response unless you are on the right webpage (if we are talking about usage for the web). The reason is that the protocol signs metadata that is linked to what’s in the url bar of your browser.

More recently laptops and mobile devices have started offering other ways to provide the same value as a hardware security token via their own secure module. For example Apple provides a biometric-protected (Touch ID or Face ID) authenticator via the secure enclave.

It’s not clear how much protection against hardware attacks your typical hardware security token has to implement since the compromise of one is not enough to authenticate as a user in most cases (unless you use one as single factor authentication). Yet yubikeys are known to have secure elements inside. Still, this doesn’t exclude software attacks if badly programmed. For example in 2013, a low-cost and non-intrusive side-channel attack managed to extract keys from a yubikey.

Cryptocurrency has similar dongles that will sign transactions for a user, but the threat model is different and they will usually have to authenticate the user in some ways and provide tamper resistance. Here is a picture of a Nano ledger.

nano ledger

As with any hardware solutions, attacks have been found there as well (for example one the trezor).

Conclusion

As a summary, this 3-part blog series surveys different techniques that exist to deal with physical attacks:

  • Smart cards are microcomputers that needs to be turned on by an external device like a payment terminal. They can run arbitrary java applications. Bank cards are smart cards for example.
  • Secure elements are a generalization of smart cards, which rely on a set of Global Platform standards. SIM Cards are secure elements for example.
  • TPMs are re-packaged secure elements plugged on personal and enterprise computers’ motherboards. They follow a standardized API (by the Trusted Computing Group) that are used in a multitude of ways from measured/secure boot with FDE to remote attestation.
  • HSMs can be seen as external and big secure elements for servers. They’re faster and more flexible. Seen mostly in data centers to store keys.
  • TEEs like TrustZone and SGX can be thought of secure elements implemented within the CPU. They are faster and cheaper but mostly provide resistance against software attacks unless augmented to be tamper-resistant. Most modern CPUs ship with TEEs and various level of defense against hardware attacks.
  • Hardware Security Tokens are dongles like yubikeys that often repackage secure elements to provide a 2nd factor by implementing some authentication protocol (usually TOTP or FIDO2).
  • There are many more that I haven’t talked about. In reality vendors can do whatever they want. We’ve seen a lot of TPM-like chips. Apple has the secure enclave, Google has Titan, Microsoft has Pluton, Atmel for example sells “crypto elements”.

Keep in mind that no hardware solution is the panacea, you're only increasing the attack's cost. Against a sophisticated attacker all of that is pretty much useless. For this reason design your system so that one device compromised doesn't imply all devices are compromised. Even against normal adversaries, compromising the main operating system often means that you can make arbitrary calls to the secure element. Design your protocol to make sure that the secure element doesn't have to trust the caller by either verifying queries, or relying on an external trusted part, or by relying on a trusted remote party, or by being self-contained, etc. And after all of that, you still have to worry about side channel attacks :)

PS: thanks to Gabe Pike for the many discussions around TEE!

comment on this story

Hardware Solutions To Highly-Adversarial Environments Part 2: HSM vs TPM vs Secure Enclave posted last month

In the previous post (part 1) you learned about:

  • The threat today is not just an attacker intercepting messages over the wire, but an attacker stealing or tampering with the device that runs your cryptography. So called Internet of Things (IoT) devices often run into this type of threats and are by default unprotected against sophisticated attackers.
  • Hardware can help protect cryptography applications in highly-adversarial environment. One of the idea is to provide a device with a tamper-resistant chip to store and perform crypto operations. That is, if the device falls in the hands of an attacker, extracting keys or modifying the behavior of the chip will be hard. But hardware-protected crypto is not a panacea, it is merely defense-in-depth, effectively slowing down and increasing the cost of an attack.
  • smart cards were one of the first such secure microcontroller that could be used as a micro computer to store secrets and perform cryptographic operations with them. These are supposed to use a number of techniques to discourage physical attackers.
  • the concept of a smart card was generalized as a secure element, which is a term employed differently in different domains, but boils down to a smart card that can be used as a coprocessor in a greater system that already has a main processor.
  • Google having troubles dealing with the telecoms to host credit card information on SIM cards (which are secure elements), the concept of secure element in the cloud was born. In the payment space this is called host card emulation (HCE). It works simply by storing the credit card information (which is a 3DES symmetric key shared with the bank) in a secure element in the cloud, and only giving a single-use token to the user: if the phone is compromised, the attacker can only use it to pay once.

All good?

In this part 2 of our blog series you will learn about more hardware that supports cryptographic operations! These are all secure elements in concept, and are all doing sort of the same things but in different contexts. Let’s get started!

Hardware Security Module (HSM)

If you understood what a secure element was, well a hardware secure module (HSM) is pretty much a bigger secure element. Not only the form factor of secure elements require specific ports, but they are also slow and low on memory. (Note that being low on memory is sometimes OK, as you can encrypt keys with a secure element master key, and then store the encrypted keys outside of the secure element.) So HSM is a solution for a more portable, more efficient, more multi-purpose secure element. Like some secure elements, some HSMs can run arbitrary code as well.

HSMs are also subject to their own set of standards and security level. One of the most widely accepted standard is FIPS 140-2: Security Requirements for Cryptographic Modules, which defines security levels between 1 and 4, where level 1 HSMs do not provide any protection against physical attacks and level 4 HSMs will wipe their whole memory if they detect any intrusion!

Typically, you find an HSM as an external device with its own shelf on a rack (see the picture of a luna HSM below) plugged to an enterprise server in a data center.

luna HSM

(To go full circle, some of these HSMs can be administered using smart cards.)

Sometimes you can also find an HSM as a PCIe card plugged into a server’s motherboard, like the IBM Crypto Express in the picture below.

IBM crypto express

Or even as small dongles that you can plug via USB (if you don’t care about performance), see the picture of a YubiHSM below.

yubiHSM

HSMs are highly used in some industries. Every time you enter your PIN in an ATM or a payment terminal, the PIN ends up being verified by an HSM somewhere. Whenever you connect to a website via HTTPS, the root of trust comes from a Certificate Authority (CA) that stores its private key in an HSM, and the TLS connection is possibly terminated by an HSM. You have an Android or iPhone? Chances are Google or Apple are keeping a backup of your phone safe with a fleet of HSMs. This last case is interesting because the threat model is reversed: the user does not trust the cloud with its data, and thus the cloud service provider claims that its service can’t see the user’s encrypted backup nor can access the keys used to encrypt it.

HSMs don’t really have a standard, but most of them will at least implement the Public-Key Cryptography Standard 11 (PKCS#11), one of these old standards that were started by the RSA company and that were progressively moved to the OASIS organization (2012) in order to facilitate adoption of the standards.

While PKCS#11 last version (2.40) was released in 2015, it is merely an update of a standard that originally started in 1994. For this reason it specifies a number of old cryptographic algorithms, or old ways of doing things. Nevertheless, it is good enough for many uses, and specifies an interface that allow different systems to easily interoperate with each other.

While HSMs’ real goals are to make sure nobody can extract key material from them, their security is not always shining. A lot about the security of these hardware solutions really relies on their high price, the protection techniques used not being disclosed, and the certifications (like FIPS and Common Criteria) mostly focusing on the hardware side of things. In practice, devastating software bugs have been found and it is not always straight forward to know if the HSM you use is vulnerable to any of these vulnerabilities (Cryptosense has a good summary of known attacks against HSMs).

By the way, not only the price of one HSM is high (it can easily be dozens of thousands of dollars depending on the security level), in addition to an HSM you often have another HSM you use for testing, and another one you use for backup (in case your first HSM dies with its keys in it). It can add up!

Furthermore, I still haven’t touched on the elephant in the room with all of these solutions: while you might prevent most attackers from reaching your secret keys, you can't prevent attackers from compromising the system and making their own calls to the secure hardware module (be it a secure element or an HSM). Again, these hardware solutions are not a panacea and depending on the scenario they provide more or less defense-in-depth.

By the way, if it applies to your situation modern cryptography can offer better ways of reducing the consequences of key material compromise and mis-use. For example using multi-signatures! Check my blog post on the subject.

Trusted Platform Module (TPM)

A Trusted Platform Module (TPM) is first and foremost a standard (unlike HSMs) developed in the open by the non-profit Trusted Computing Group (TCG). The latest version is TPM 2.0, published with the ISO/IEC (International Organization for Standardization and the International Electrotechnical Commission).

A TPM complying with the TPM 2.0 standard is a secure microcontroller that carries a hardware random number generator also called true random number generator (TRNG), secure memory for storing secrets, cryptographic operations, and the whole thing is tamper resistant. If this description reminds you of smart cards, secure element, and HSMs well… I told you that everything we were going to be talking about in this chapter were going to be secure elements of some form. (And actually, it’s common to see TPMs implemented as repackaging of secure elements.)

You usually find a TPM directly soldered to the motherboard of many enterprise servers, laptops, and desktop computers (see picture below).

tpm

Unlike solutions that we’ve seen previously though, a TPM does not run arbitrary code. It offers a well-defined interface that a greater system can take advantage of. Due to these limitations, a TPM is usually pretty cheap (even cheap enough that some IoT devices will ship with one!).

Here is a non-exhaustive list of interesting applications that a TPM can enable:

  • User authentication. Ever heard of the FBI iPhone fiasco? TPMs can be used to require a user PIN or password. In order to prevent low entropy credentials to be easily bruteforced, a TPM can rate limit or even count the number of failed attempts.
  • Secure boot. Secure boot is about starting a system in a known trusted state in order to avoid tampering of the OS by malware or physical intrusion. This can be done by using a platform’s TPM and the Unified Extensible Firmware Interface (UEFI) which is the piece of code that launches an operating system. Whenever the image of a new boot loader or OS or driver is loaded, the TPM can store the associated expected hash and compare it before running the code, and failing if the hash of the image is different. If you hold a public key you can also verify that a piece of code has been signed before running it. This is a gross over-simplification of how secure boot works in practice, but the crypto is pretty straight forward.
  • Full disk encryption (FDE). This allows to store the key (or encrypt the key) that encrypts all data on the device at rest. If the device has been proven to be in a known good state (via secure boot) and the user authenticates correctly, the key can be released to decrypt data. When the devices is locked or shut down, the key vanishes from memory and has to be released by the TPM again. This is a must feature if you lose, or get your device stolen.
  • Remote attestation. This allows a device to authenticate itself or prove that it is running specific software. In other words, a TPM can sign a random challenge and/or metadata with a key that can be tied to a unique per-TPM key (and is signed by the TPM vendor). Every TPM comes with such a unique key (called an endorsement key) along with the vendor’s certificate authority signature on the public key part. For example, during employee onboarding a company can add a new employee’s laptop’s TPM endorsement key to a whitelist of approved devices. Later, if the user wants to access one of the company’s service, the service can request the TPM to sign a random challenge along with hashes of what OS was booted to authenticate the user and prove the well-being of the user’s device.

There are more functionalities that a TPM can enable (there's afterall hundreds of commands that a TPM implements) which might even benefit user applications (which should be able to call the TPM).

Note that having a standard is great for inter-operability, and for us to understand what is going on, but unfortunately not everyone use TPMs. Apple has the secure enclave, Microsoft has Pluton, Google has Titan.

Perhaps, on a darker note, it is good to note that TPMs have their own controversies and have also been subjected to devastating vulnerabilities. For example the ROCA attack found that an estimated million TPMs (and even smart cards) from the popular Infineon vendor had been wrongly generating RSA private keys for years (the prime generation was flawed).

To recap, you’ve learned about:

  • HSMs. They are external, bigger and faster secure elements. They do not follow any standard interface, but usually implement the PKCS#11 standard for cryptographic operations. HSMs can be certified with different levels of security via some NIST standard (FIPS 140-2).
  • TPMs. They are chips that follow the TPM standard, more specifically they are a type of secure element with a specified interface. A TPM is usually a secure chip directly linked to the motherboard and perhaps implemented using a secure element. While it does not allow to run arbitrary programs like some secure elements, smart cards, and HSMs do, it enables a number of interesting applications for devices as well as user applications.

That’s it for now, check this blog again to read part 3 which will be about TEEs!

Many thanks to Jeremy O'Donoghue, Thomas Duboucher, Charles Guillemet, and Ryan Sleevi who provided help and reviews!

4 comments

Hardware Solutions To Highly-Adversarial Environments Part 1: Whitebox Crypto vs Smart Cards vs Secure Elements vs Host-Card Emulation (HCE) posted March 2020

If at some point you realize that doing cryptography means having to manage long-term keys, it means you’re standing in the world of key management.

Makes sense right?

In these lands, you are going to run into scenarios where attackers can be quite close to your applications. I call these highly-adversarial environments.

Imagine using your credit card on an ATM skimmer (a doodads that a thief can place on top of the card reader of an ATM in order to copy the content of your credit card, see picture bellow); downloading an application on your mobile phone that compromises the OS; hosting a web application in a colocated server shared with a malicious customer; managing highly-sensitive secrets in a data center that gets breached; and so on.

skimmers

These scenarios suck, and are very counterintuitive to most cryptographers. This is because cryptography has come a long way since the historical “Alice wants to encrypt a message to Bob without Eve intercepting it”. Nowadays, it’s often more like “Alice wants to encrypt a message to Bob, but Alice is also Eve”.

The key here is that in these scenarios, there’s not much that can be done cryptographically (unless you believe in whitebox crypto) and hardware can go a long way to help.

OK, so now we have a whole world of new doohickeys to learn about, and there’s a lot of thingamabob believe me (hence the dense title). It can be quite confusing to learn about all of this, so here we go: my promise is that by the end of this blogpost series you’ll have a better understanding of what are all these different hardware solutions.

Keep in mind that none of these solutions are pure cryptographic solutions: they are all defense-in-depth (and sometimes dubious) solutions that serve to hide secrets and their associated sensitive cryptographic operations. They also all have a given cost, meaning that if a sophisticated attacker decides to break the bank, there’s not much we can do (besides raising the cost of an attack).

OK let's get started.

Obfuscation

By definition obfuscation has nothing to do with security: it is the act of scrambling something so that it still work but is hard to understand. So for the laugh, let’s first mention whitebox cryptography which attempts to “cryptographically” obfuscate the key inside of an algorithm. That’s right, you have the source code of some AES-based encryption algorithm with a fixed key, and it encrypts and decrypts fine, but the key is mixed so well with the implementation that it is too confusing for anyone to extract the key from the algorithm. That's the theory. Unfortunately in practice, no published whitebox crypto algorithm has been found to be secure, and most commercial solutions are closed-source due to this fact (security through obscurity kinda works in the real world). Again, it’s all about raising the cost and making it harder for attackers.

All in all, whitebox crypto is a big industry that sells dubious products to businesses in need of DRM solutions. On the more serious side, there is a branch of cryptography called Indistinguishability obfuscation (iO) that attempts to do this cryptographically (so for realz). iO is a very theoretical, impractical, and so far not-really-proven field of research. We’ll see how that one goes.

timeline whitebox crypto

(Timeline of whitebox cryptography, taken from Matthieu Rivain’s slides)

Smart Cards

OK, whitebox crypto is not great, and worse: even if you can’t extract the key, you can still copy the program instead of trying to extract the key (and use it to do whatever cryptographic operation it features). It would be great if we could prevent people from copying secrets from sensitive devices though, or even prevent them from seeing what’s going on when the device performs cryptographic operations. A smart card is exactly this. It’s what you commonly find in credit cards, and is activated by either inserting it into, or using Near-field Communication (NFC) by getting the smart card close enough to, a payment terminal (also called Point of Sale or PoS terminal).

smart cards

Smart cards are pretty old, and started as a practical way to get everyone a pocket computer. Indeed, a smart cart embarks a CPU, memory (RAM, ROM and EEPROM), input/output, hardware random number generator (so called TRNGs), etc.) unlike the not-so-smart cards that only had data stored in them via a magnetic stripe (which in turn can be easily copied via the skimmers I talked about previously). Today, it seems like the same people all have a much more powerful computer in their pockets, so smart cards are probably going to die. (Rob Wood is pointing to me that more than a quarter of the US still doesn’t have a smart phone, so there’s still some time before this prophecy come to fruition.)

Smart cards mix a number of physical and logical techniques to prevent observation, extraction, and modification of its execution environment and some of its memory (where secrets are stored). But as I said earlier, it’s all about how much money you want an attacker to be spending, and there exist many techniques that attempt at breaking these cards:

  • Non-invasive attacks such as differential power analysis (DPA) analyze the power consumption of the smart card while it is doing cryptographic operations in order to extract the associated keys.
  • Semi-invasive attacks require access to the chip’s surface to mount attacks such as differential fault analysis (DFA) which use heat, lasers, and other techniques to modify the execution of a program running on the smart card in order to leak the key via cryptographic attacks (see my post on RSA signature fault attacks for an example).
  • Finally invasive silicon attacks can modify the circuitry in the silicon itself to alter its function and reveal secrets.

Secure Elements

Smart cards got really popular really fast, and it became obvious that having such a secure blackbox in other devices could be useful. The concept of a secure element was born: a tamper-resistant microcontroller that can be found in a pluggable form factor like UUICs (SIM cards required by carriers to access their 3G/4G/5G network) or directly bonded on chips and motherboards like the embedded SE (eSE) attached to an iPhone’s NFC chip. Really just a small separate piece of hardware meant to protect your secrets and their usage in cryptographic operations.

SEs are an evolution of the traditional chip that resides in smart cards, which have been adapted to suit the needs of an increasingly digitalized world, such as smartphones, tablets, set top boxes, wearables, connected cars, and other internet of things (IoT) devices. (GlobalPlatform)

Secure elements are a key concept to protect cryptographic operations in the Internet of Things (IoTs), a colloquial (and overloaded) term to refer to devices that can communicate with other devices (think smart cards in credit cards, SIM cards in phones, biometric data in passports, garage keys, smart home sensors, and so on).

Thus, you can see all of the solutions that will follow in this blogpost series as secure elements implemented in different form factors, using different techniques, and providing different level of defense-in-depth.

If you are required to use a secure element (to store credit card data for example), you also most likely have to get it certified. The main definition and standards around a secure element come from GlobalPlatform, but there exist more standards like Common Criteria (CC), NIST’s FIPS, EMV (for Europay, Mastercard, and Visa), and so on. If you’re in the market of buying secure microcontrollers, you will often see claims like “FIPS 140-2 certified” and “certified CC EAL 5+” next to it. Claims that can be obtained after spending some quality time, and a lot of money, with licensed certification labs.

Host Card Emulation (HCE)

It’s 2020, most people have a computer in their pocket: a smart phone. What’s the point of a credit card anymore? Well, not much, nowadays more and more payment terminals support contactless payment via the Near-field Communication (NFC) protocol, and more and more smartphones ship with an NFC chip that can potentially act as a credit card.

NFC for payment is specified as Card Emulation. Literally: it emulates a bank card. Banks allow you to do this only if you have a secure element.

Since Apple has full control over its hardware, it can easily add a secure element to its new iPhones to support payment, and this is what Apple did (with an embedded SE bonded to the NFC chip since the iPhone 6). iPhone users can register a bank card with the Apple wallet application, Apple can then obtain the card’s secrets from the issuing bank, and the card secrets can finally be stored in the eSE. The secure element communicates directly with the NFC chip and then to NFC readers, thus a compromise of the phone OS does not impact the secure element.

Google, on the other hand, had quite a hard time introducing payment to Android-based mobile phones due to phone vendors all doing different things. The saving technology for Google ended up being a cloud-based secure element called Host Card Emulation (HCE) introduced in 2013 in Android 4.4.

How does it work? Google stores your credit card information in a secure element in the cloud (instead of your phone), and only gives your phone access to short-lived single-use PAN (card numbers). (Note that some Android devices do have an eSE that can be used instead of HCE, and some SIM cards can also be used as secure elements for payment.) This concept of replacing sensitive long-term information with short-lived tokens is called tokenization. Sending a random card number that can be linked to your real one is great for privacy: merchants can’t track you as it’ll look like you’re always using a new card number. If your phone gets compromised, the attacker only gets access to a short-lived secret that can only be used for a single payment. Tokenization is a common concept in security: replace the sensitive data with some random stuff, and have a table secured somewhere safe that maps the random stuff to the real data.

Wikipedia has some cool diagram to show what’s going on whenever you pay with Android Pay or Apple Pay:

tokenization

Although Apple theoretically doesn't have to use tokenization, since iPhones have secure elements that can store the real PAN, they do use it in order to gain more privacy (it's afterall their new bread and butter).

In part 2 of this blog series I’ll cover HSMs, TPMs, and much more :)

(I would like to thank Rob Wood, Thomas Duboucher, and Lionel Rivière for answering my many questions!)

PS: I'm writing a book which will contain this and much more, check it out!

2 comments

Coronavirus and cryptography posted March 2020

The coronavirus is shaking the world, on its multiple layers, and cryptography hasn't been spared.

The IACR announced on March 14th that multiple conferences were postponed:

FSE 2020, which was supposed to be held in Athens, Greece, during 22-26 March 2020, has been postponed to 8-12 November 2020.

PKC 2020, which was supposed to be held in Edinburgh, Scotland, during 4-7 May 2020, has been postponed.

EUROCRYPT 2020, which was supposed to be held in Zagreb, Croatia, during 10-14 May 2020, has been postponed.

While some others were not:

No changes have been made at this time to the schedule of CRYPTO 2020, CHES 2020, TCC 2020, and ASIACRYPT 2020, but we will continue to closely monitor the situation and will inform members if changes are needed.

While many workplaces (including mine) are moving to a WFH (work from home) model, will conferences follow?

It seems to be the case at least for Consensus 2020, a cryptocurrency conference organized by coindesk, which is moving to an online model:

Consensus 2020 will now be a completely virtual experience, where attendees from all over the world can participate online at no charge.

On a more dramatic note it seems like several participants of EthCC, which was held in Paris almost a week ago, have contracted the virus. A google spreadsheet has been circulating in order to self-report and figure out who else could have potentially contracted the virus. Even Vitalik Buterin is rumored to have had mild COVID-19 symptoms. Nobody is out of reach.

On a lighter note, my coworker Kostas presented on proofs of solvency at the lightning talks of Real World Crypto 2020. With his merkle tree-like construction he hopes to make governments accountable when they count the number of people who counted positive to the virus.

comment on this story

EdDSA, Ed25519, Ed25519-IETF, Ed25519ph, Ed25519ctx, HashEdDSA, PureEdDSA, WTF? posted March 2020

The Edwards-curve Digital Signature Algorithm (EdDSA)

You've heard of EdDSA right? The shiny and new signature scheme (well new, it's been here since 2008, wake up).

Since its inception, EdDSA has evolved quite a lot, and some amount of standardization process has happened to it. It's even doomed to be adopted by the NIST in FIPS 186-5!

First, some definition:

  • EdDSA stands for Edwards-curve Digital Signature Algorithm. As its name indicates, it is supposed to be used with twisted Edwards curves (a type of elliptic curve). Its name can be deceiving though, as it is not based on the Digital Signature Algorithm (DSA) but on Schnorr signatures!
  • Ed25519 is the name given to the algorithm combining EdDSA and the Edwards25519 curve (a curve somewhat equivalent to Curve25519 but discovered later, and much more performant).

EdDSA, Ed25519, and the more secure Ed448 are all specified in RFC 8032.

RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA)

RFC 8032 takes some new direction from the original paper:

  • It specifies a malleability check during verification, which prevents ill-intentioned people to forge an additional valid signature from an existing signature of yours. Whenever someone talks about Ed25519-IETF, they probably mean "the algorithm with the malleability check".
  • It specifies a number of Ed25519 variants, which is the reason of this post.
  • Maybe some other stuff I'm missing.

To sign with Ed25519, the original algorithm defined in the paper, here is what you're supposed to do:

  1. compute the nonce as HASH(nonce_key || message)
  2. compute the commitment R = [nonce]G with G the generator of the group.
  3. compute the challenge as HASH(commitment || public_key || message)
  4. compute the proof S = nonce + challenge × signing_key
  5. the signature is (R, S)

where HASH is just the SHA-512 hash function.

eddsa

At a high-level this is similar to Schnorr signatures, except for the following differences:

  • The nonce is generated deterministically (as opposed to probabilistically) using a fixed nonce_key (derived from your private key, and the message M. This is one of the cool feature of Ed25519: it prevents you from re-using the same nonce twice.
  • The challenge is computed not only with the commitment and the message to sign, but with the public key of the signer as well. Do you know why?

Important: notice that the message here does not need to be hashed before being passed to the algorithm, as it is already hashed as part of the algorithm.

Anyway, we still don't know WTF all the variants specified are.

PureEdDSA, ContextEdDSA and HashEdDSA

Here are the variants that the RFC actually specifies:

  • PureEdDSA, shortened as Ed25519 when coupled with Edwards25519.
  • HashEdDSA, shortened as Ed25519ph when coupled with Edwards25519 (and where ph stands for "prehash").
  • Something with no name we'll call ContextEdDSA, defined as Ed25519ctx when coupled with Edwards25519.

All three variants can share the same keys. They differ only in their signing and verification algorithms.

By the way Ed448 is a bit different, so from now on I'll focus on EdDSA with the Edwards25519 curve.

Ed25519 (or pureEd25519) is the algorithm I described in the previous section.

Easy!

Ed25519ctx (or ContextEd25519) is pureEd25519 with some additional modification: the HASH(.) function used in the signing protocol I described above is re-defined as HASH(x) = SHA-512(some_encoding(flag, context) || x) where:

  • flag is set to 0
  • context is a context string (mandatory only for Ed25519ctx)

In other words, the two instances of hashing in the signing algorithm now include some prefix. (Intuitively, you can also see that these variants are totally incompatible with each other.)

Right out of the bat, you can see that ContextEd25519 big difference is just that it mandates some domain separation to Ed25519.

Ed25519ph (or HashEd25519), finally, builds on top of ContextEd25519 with the following modifications:

  • flag is set to 1
  • context is now optional, but advised
  • the message is replaced with a hash of the message (the specification says that the hash has to be SHA-512, but I'm guessing that it can be anything in reality)

OK. So the big difference now seems that we are doubly-hashing.

ed25519

Why HashEdDSA and why double hashing?

First, pre-hashing sucks, this is because it kills the collision resistance of the signature algorithm. In PureEdDSA we assume that we take the original message and not a hash. (Although this is not always true, the caller of the function can do whatever they want.) Then a collision on the hash function wouldn't matter (to make you create a signature that validates two different messages) because you would have to find a collision on the nonce which is computed using a secret (the nonce key).

But if you pre-hash the message, then finding a collision there is enough to obtain a signature that validates two messages.

Thus, you should use PureEdDSA if possible. And use it correctly (pass it the correct message.)

Why is HashEdDSA a thing then?

The EdDSA for more curves paper which was the first to introduce the algorithm has this to say:

The main motivation for HashEdDSA is the following storage issue (which is irrelevant to most well-designed signature applications). Computing the PureEdDSA signature of M requires reading through M twice from a buffer as long as M, and therefore does not support a small-memory “InitUpdate-Final” interface for long messages. Every common hash function H0 supports a smallmemory “Init-Update-Final” interface for long messages, so H0 -EdDSA signing also supports a small-memory “Init-Update-Final” interface for long messages. Beware, however, that analogous streaming of verification for long messages means that verifiers pass along forged packets from attackers, so it is safest for protocol designers to split long messages into short messages to be signed; this splitting also eliminates the storage issue.

Why am I even looking at this rabbit hole?

Because I'm writing a book, and it'd be nice to explain what the hell is going on with Ed25519.

8 comments

What's a key exchange? posted March 2020

book

I've been writing about cryptography for a book for a year now, and it has brought me some interesting challenges. One of them is that I constantly have to throw away what I've learned a long time ago, and imagine what it feels like not to know about a concept.

For example what are key exchanges?

The most intuitive explanation that I knew of (up until recently) was the one given by the wikipedia page on key exchanges. You might already know about it (unless you're reading this post to learn about key exchanges). It's a picture that involves paint. Take a look at it, but don't try to understand what is going on if you don't know about key exchanges yet. You can come back to it later.

wikipedia

I thought this was great. At least until I tried to explain key exchanges to my friends using this analogy. Nobody got it.

Nobody.

The other problem was that I couldn't use colors to explain anything in my book, as it'll be printed in black & white.

So I sat on the sad realization that I didn't have a great explanation for key exchanges, this for a number of months, and that until a more intuitive idea came to my mind.

soda

The idea goes like this. Imagine that Alice and Bob wants to share a secret, but are afraid that someone is intercepting their communications. What they do is that they go to the store and buy the same bottle of generic soda.

Once home, they both start a random timer and shake their respective bottles until their timer end.

shaking

What they obtain are some shaked, pressurized, ready to gush out bottles of sodas. Each of the bottles will release a different amount of pressure.

After that, they swap bottles. Now Alice has the bottle of Bob, and Bob has Alice's bottle.

swap

What do they do now? They restart their timers and shake the other person's bottle for the same amount of time.

Shake shake shake!

shake again

What do they finally obtain? Try to guess.

If I did my job correctly, then I gave you an intuition of how key exchanges work. Both Alice and Bob should now have two bottle of sodas that will release the same pressure once opened. And that's the secret!

And even if I steal the two bottles, I can't get a bottle that combines both bottles' pressure.

I recap the whole flow in the picture below:

final

Did you know about key exchanges before? Did you get it? Or did you think the painting example made more sense?

Please tell me in the comment!

This is probably what I'll include in my book as an introduction of what key exchanges are, unless I find a better way to explain it :)

4 comments

Cryptographic Signatures, Surprising Pitfalls, and LetsEncrypt posted March 2020

The Let's Encrypt Accident

On August 11th, 2015, Andrew Ayer posted the following email to the IETF mailing list:

I recently reviewed draft-barnes-acme-04 and found vulnerabilities in the DNS, DVSNI, and Simple HTTP challenges that would allow an attacker to fraudulently complete these challenges.

(The author has since then written a more complete explanation of the attack.)

The draft-barnes-acme-04 mentioned by Andrew Ayer is a document specifying ACME, one of the protocols behind the Let's Encrypt Certificate Authority. The thing that your browser trust and that signs the public keys of websites you visit.

The attack was found merely 6 weeks before major browsers were supposed to ship with Let's Encrypt's public keys in their trust store. The draft has since become RFC 8555: Automatic Certificate Management Environment (ACME), mitigating the issues. Since then no cryptographic attacks are known on the protocol.

But how did we get there? What's the deal with signature schemes these days? and are all of our protocols doomed? This is what this blog post will answer.

Let's Encrypt Use Of Signatures

Let's Encrypt is a pretty big deal. Created in 2014, it is a certificate authority ran as a non-profit, and currently providing trust to ~200 million of websites. (You can read my article Let's Encrypt Overview to learn more about it.)

The key to Let's Encrypt's success are two folds:

  • It is free. Before Let's Encrypt most certificate authorities charged fees from webmasters who wanted to obtain certificates.
  • It is automated. If you follow their standardized protocol, you can request, renew and even revoke certificates via an API. Contrast that to other certificate authorities who did most processing manually, and took time to issue certificates.

If a webmaster wants her website example.com to provide a secure connection to her users (via HTTPS), she can request a certificate from Let's Encrypt, and after proving that she owns the domain example.com and getting her certificate issued, she will be able to use it to negotiate a secure connection with any browser trusting Let's Encrypt.

That's the theory.

In practice the flow is the following:

  1. Alice registers on Let's Encrypt with an RSA public key.
  2. Alice asks Let's Encrypt for a certificate for example.com.
  3. Let's Encrypt asks Alice to prove that she owns example.com, for this she has to sign some data and upload it to example.com/.well-known/acme-challenge/some_file.
  4. Once Alice has signed and uploaded the signature, she asks Let's Encrypt to go check it.
  5. Let's Encrypt checks if it can access the file on example.com, if it successfully downloaded the signature and the signature is valid then Let's Encrypt issues a certificate to Alice.

I recapitulate some of this flow in the following figure:

let's encrypt flow

Now, you might be wondering, what if Alice does not own example.com and manage to man-in-the-middle Let's Encrypt in step 5? That's a real issue that's been bothering me ever since Let's Encrypt launched, and turns out a team of researchers at Princeton demonstrated exactly this in Bamboozling Certificate Authorities with BGP:

We perform the first real-world demonstration of BGP attacks to obtain bogus certificates from top CAs in an ethical manner. To assess the vulnerability of the PKI, we collect a dataset of 1.8 million certificates and find that an adversary would be capable of gaining a bogus certificate for the vast majority of domains

The paper continues and proposes two solutions to sort of remediate, or at least reduce the risk of these attacks:

Finally, we propose and evaluate two countermeasures to secure the PKI: 1) CAs verifying domains from multiple vantage points to make it harder to launch a successful attack, and 2) a BGP monitoring system for CAs to detect suspicious BGP routes and delay certificate issuance to give network operators time to react to BGP attacks.

Recently Let's Encrypt implemented the first solution multi-perspective domain validation, which changes the way step 5 of the above flow is performed: now Let's Encrypt downloads the proof from example.com from multiple places.

How Did The Let's Encrypt Attack Worked

But let's get back to what I was talking about, the attack that Andrew Ayer found in 2015.

In it, Andrew proposes a way to gain control of a Let's Encrypt account that has already validated a domain (let's say example.com)

The attack goes like this:

  1. Alice registers and goes through the process of verifying her domain example.com by uploading some signature over some data on example.com/.well-known/acme-challenge/some_file. She then successfully manages to obtain a certificate from Let's Encrypt.
  2. Later, Eve signs up to Let's Encrypt with a new account and new RSA public key, and request to recover the example.com domain
  3. Let's Encrypt asks Eve to sign some new data, and upload it to example.com/.well-known/acme-challenge/some_file (note that the file is still lingering there from Alice's previous domain validation)
  4. Eve crafts a new malicious keypair, and updates her public key on Let's Encrypt. She then asks Let's Encrypt to check the signature
  5. Let's Encrypt obtains the signature file from example.com, the signature matches, Eve is granted ownership of the domain example.com.

I recapitulate the attack in the following figure:

attack let's encrypt

Wait what?

What happened there?

Key Substitution Attack With RSA

In the above attack Eve managed to create a valid public key that validates a given signature and message.

This is because, as Andrew Ayer wrote:

A digital signature does not uniquely identify a key or a message

If you remember how RSA works, this is actually not too hard to understand.

RSA

For a fixed signature and (PKCS#1 v1.5 padded) message, a public key (e, N) must satisfy the following equation to validate the signature:

\(\text{signature} = \text{message}^e \pmod{N}\)

One can easily craft a public key that will (most of the time) satisfy the equation:

  • \(e = 1\)
  • \(N = \text{signature} - \text{message}\)

You can easily verify that the validation works:

$$ \begin{align} &\text{signature} = \text{message}^e \pmod{N}\\ \iff&\text{signature} = \text{message} \pmod{\text{signature} - \text{message}}\\ \iff&\text{signature} - \text{message} = 0 \pmod{\text{signature} - \text{message}} \end{align} $$

By definition the last line is true.

Security of Cryptographic Signatures

Is this issue surprising?

It should be.

And if so why?

This is because of the gap that exists between the theoretical world and the applied world, between the security proofs and the implemented protocol.

Signatures in cryptography are usually analyzed with the EUF-CMA model, which stands for Existential Unforgeability under Adaptive Chosen Message Attack.

In this model YOU generated a key pair, and then I request YOU to sign a number of arbitrary messages. While I observe the signatures you produce, I win if I can at some point in time produce a valid signature over a message I hadn't requested.

Unfortunately, even though our modern signature schemes seem to pass the EUF-CMA test fine, they tend to exhibit some surprising properties.

Subtle Behaviors of Signature Schemes

The excellent paper Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures by Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon, and Ralf Sasse attempts to list these surprising properties and the signature schemes affected by them (and then find a bunch of these in protocols using formal verification, it's a cool paper read it).

Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures

Let me briefly describe each properties:

Conservative Exclusive Ownership (CEO)/Destructive Exclusive Ownership (DEO). This refers to what Koblitz and Menezes used to call Duplicate Signature Key Selection (DSKS). In total honesty, I don't think any of these terms are self-explanatory. I find these attacks easier to remember if thought of as the following two variants:

  1. key substitution attacks (CEO), where a different keypair or public key is used to validate a given signature over a given message.
  2. message key substitution attacks (DEO), where a different keypair or public key is used to validate given signature over a new message.

To recap: the first attack fixes both the message and the signature, the second one only fixes the signature.

Malleability. Most signature schemes are malleable, meaning that if you give me a valid signature I can tamper with it so that it becomes a different but still valid signature. Note that if I'm the signer I can usually create different signatures for the same message, but here malleability refers to the fact that someone who has zero knowledge of the private key can also create a new valid signature for the same signed message. It is not clear if this has any impact on any real world protocol, eventhough the bitcoin MtGox exchange blamed their loss of funds on this one. From the paper Bitcoin Transaction Malleability and MtGox:

In February 2014 MtGox, once the largest Bitcoin exchange, closed and filed for bankruptcy claiming that attackers used malleability attacks to drain its accounts.

Note that a newer security model called SUF-CMA (for strong EUF-CMA) attempts to include this behavior in the security definition of signature schemes, and some recent standards (like RFC 8032 that specifies Ed25519) are mitigating malleability attacks on their signature schemes.

Re-signability. This one is simple to explain. To validate a signature over message you often don't need the message itself but its digest. This would allow anyone to re-sign the message with their own keys without knowing the message itself. How is this impactful in real world protocols? Not sure, but we never know.

Collidability. This is another not-so-clear if it'll bite you one day: some schemes allow you to craft signatures that will validate under several messages. Worse, Ed25519 as designed allows one to craft a public key and a signature that would validate any message with high probability. (This has been fixed in some implementations like libsodium.)

I recapitulate the substitution attacks in the diagram below:

key substitution attack

What to do with all of this information?

Well, for one signature schemes are definitely not broken, and you probably shouldn't worry if your use of them are mainstream.

But if you're designing cryptographic protocols, or if you're implementing something that's more complicated than the every day use of cryptography you might want to keep these in the back of your mind.

book Did you like this content? This is part of a book about how to apply modern cryptography in real world applications. Check it out!

3 comments

Authentication What The Fuck: Part II posted February 2020

(part 1 is here)

Writing about real world cryptography, it seems like what I end up writing a lot about is protocols and how they solve origin/identity authentication.

Don't get me wrong, confidentiality has interesting problems to (e.g. how to bring confidentiality to a blockchain), but authentication is most of what applied cryptography is about, for realz.

Do I need to convince you?

If you think about it, most protocols are about finding ways to provide authentication to different scenarios. And that's why they can get complicated!

I'll take my life for example, here is the authentication problems and solutions that I use:

  • insecure → one-side authenticated. Every day I use HTTPS, which uses the web public-key infrastructure (web PKI) to allow my browser to authenticate any websites on the web. It's a mess, but that's how you scale machine-to-machine authentication nowadays.
  • one-side authenticated → mutually-authenticated. Whenever I log into a website, over a secure HTTPS connection, this is what happens. A machine asks me to present some password (in clear, or oblivious via an asymmetric password-authenticated key exchange), or maybe a one-time password (via TOTP), or maybe I'll have to press my thumb on a yubikey (FIDO 2), or maybe I'll have to do a combination of several things (MFA). These are usually machine authenticating humans-type of flow.
  • insecure → mutually-authenticated. Whenever I talk to someone on Signal, or connect to a new WiFi, or pair a bluetooth device (like my phone with a car), I go from an insecure connection to a mutually-authenticated connection. There is a bit more nuance here, as sometimes I'll authenticate a machine (a WiFi access point for example) and sometimes I'll authenticate a human (end-to-end encryption). So different techniques work best depending on the type of peer you're trying to talk to.

In the end, I think these are the main three big categories of origin authentication. Can you think of a better classification?

comment on this story

What Are Short Authenticated Strings (SAS)? posted February 2020

There is a whole field of authentication in cryptography that is often under-discussed (at least in my opinion).

See, we often like to talk about how key exchanges can also be authenticated, by mean of public-key infrastructures (e.g. HTTPS) or by pre-exchanging secrets (e.g. my previous post on sPAKE), but we seldom talk about post-handshake authentication.

Post-handshake authentication is the idea that you can connect to something (often a hardware device) insecurely, and then "augment" the connection via some information provided in a special out-of-band channel.

But enough blabla, let me give you a real-world example: you link your phone with your car and are then asked to compare a few digits (this pairing method is called "numeric comparison" in the bluetooth spec). Here:

  • Out-of-band channel. you are in your car, looking at your screen, this is your out-of-band channel. It provides integrity (you know you can trust the numbers displayed on the screen) but do not necessarily provide confidentiality (someone could look at the screen through your window).
  • Short authenticated string (SAS). The same digits displayed on the car's screen and on your phone are the SAS! If they match you know that the connection is secure.

This SAS thing is extremely practical and usable, as it works without having to provision devices with long secrets, or having the user compare long strings of unintelligible characters.

How to do this? You're probably thinking "easy!". An indeed it seems like we could just do a key exchange, and then pass the output in some KDF to create this SAS.

NOPE.

This has been discussed long-and-large on the internet: with key exchange protocols like X25519 it doesn't work. The reason is that X25519 does not have contributory behavior: I can send you a public key that will lead to a predictable shared secret. In other words: your public key does not contribute (or very little) to the output of the algorithm.

The correct™ solution here is to give more than just the key exchange output to your KDF: give it your protocol transcript. All the messages sent and received. This puts any man-in-the-middle attempts in the protocol to a stop. (And the lesson is that you shouldn't naively customize a key exchange protocol, it can lead to real world failures.)

The next question is, what's more to SAS-based protocols? After all, Sylvain Pasini wrote a 300-page thesis on the subject. I'll answer that in my next post.

comment on this story

What's a symmetric password-authenticated key exchange (sPAKE) and how does SPAKE2 work? posted February 2020

have you heard of sPAKE (or bPAKE)?

a sPAKE is first and foremost a PAKE, which stands for Password-Authenticated Key Exchange. This simply means that authentication in the key exchange is provided via the knowledge of a password. The s (resp. b) in front means symmetric (resp. balanced). This indicates that both sides know the password.

Alice and Bob trying to use a sPAKE to authenticate a key exchange

Other PAKEs where only one side knows the password exist, these are called aPAKE for asymmetric (or augmented) PAKEs. Yes I know the nomenclature is a bit confusing :)

The most promising sPAKE scheme currently seems to be SPAKE2, which is in the process of being standardized here. There are other sPAKEs, like Dragonfly which is used in WPA3, but they don't seem to provide as strong properties as SPAKE2.

The trick to a symmetric PAKE is to use the password to blind the key exchange's ephemeral keypairs.

The first part of a sPAKE with SPAKE2

Note that we can't use the password as is, instead we:

  • Pass the password into a memory-hard hash function like Argon2 to obtain w. Can you guess why we do this? (leave a comment if you do!)
  • Convert it to a group element. To do this we simply consider w a scalar and do a scalar multiplication with a generator of our subgroup (M or N depending if you're the client or the server, can you guess why we use different generators?)

NOTE: If you know BLS or OPAQUE, you might be wondering why we don't use a "hash-to-curve" algorithm, this is because we don't need to obtain a group element with an unknown discrete logarithm in SPAKE2.

Once the blinded (with the password) public keys have been exchanged, both sides can compute a shared group element:

  • Alice computes K = h × alice_private_key × (S - w × N)
  • Bob computes K = h × bob_private_key × (T - w × M)

Spend a bit of your time to understand these equations. What happens is that both Alice and Bob first unblind the public key they've received, then perform a key exchange with it, then multiply it with the value h. What's this value h? The cofactor, or simply put: the other annoying subgroup.

Finally Alice and Bob hash the whole transcript, which is the concatenation of:

  • Alice's identity.
  • Bob's identity.
  • The message Bob sent S.
  • The message Alice sent T.
  • The shared group element K.
  • The hardened password w.

The hash of this transcript gives us two things:

  • A shared secret !
  • A key that is further expanded (via a KDF) to obtain two authentication keys.

The key derivation of sPAKE

These authentication keys sole purpose is to provide key confirmation in the last round-trip of messages. That is to say at this point, if we don't do anything, we don't know if either Alice or Bob truly managed to compute the shared secret.

Key confirmation is pretty simple, both sides just have to compute an authentication tag with one of the authentication key produced over the transcript.

The final protocol looks a bit dense, but you should be able to decipher it if you've read this far.

Whole SPAKE2 protocol

2 comments

Authentication, What The Fuck? posted January 2020

Authentication is an overloaded word in cryptography.

In the context of cryptographic primitives like message authentication codes (MACs) and authenticated encryption with associated data (AEAD), authentication really refers to authenticity or integrity. And as the Cambridge dictionary says:

Authenticity. the quality of being real or true.
The poems are supposed to be by Sappho, but they are actually of doubtful authenticity.
The authenticity of her story is beyond doubt.

The proof is in the pudding. When talking about the security properties of primitives like MACs, cryptography talks about unforgeability, which does relate to authenticity.

So whenever you hear things like "is this payload authenticated with HMAC?", think authenticity, think integrity.

In the context of protocols though (e.g. TLS) authentication refers to identification: the concept of proving who you are.

So whenever you hear things like "Is the server authenticated?", think "identities are being proven".

This dual sense really annoys me, but in the end this ambiguity is encompassed in the definition of authentication:

the process or action of proving or showing something to be true, genuine, or valid.

Diego F. Aranha proposes a clever way to disambiguate the two:

  • origin/entity authentication. You're proving that an entity really is who they say they are.
  • message authentication. You're proving that a message is genuine.

Note that an argument against this distinction is the following: to authenticate a message, you need a key. This key comes from somewhere (it's your context, or your "who"). So when you authenticate a message, you are really authenticating the context. This falls short in scenarios where for example you trust the root hash of a merkle tree, which authenticates all of its leaves.

The bottom line is, authentication is about proving that something is what it is supposed to be. And that thing can be a person, or a message, or maybe even something else.

This is not all. In the security world people are confused with authorization vs authentication :)

(part 2 is here)

comment on this story

Messaging Layer Security: A Few Thoughts posted January 2020

I've been following the Messaging Layer Security (MLS) standardization a bit. I really appreciate what the people are doing there, and what they are trying to solve. I think group messaging is currently a huge mess, as every application I have seen/audited seemed to invent a new way to implement group chat. A common standard and guidelines would greatly help.

MLS' goal is to provide a solution to end-to-end encryption for group chats. A solution that scales.

If you don't know how the MLS protocol works, I advise you to read Michael Rosenberg's blog post or to watch the Real World Crypto talk on the subject (might not be available at the moment).

Thinking about the standard, I have two questions:

  1. Does a group chat loses any notion of privacy/confidentiality after it gets too large? For example, if you are in a Hong Kong group trying to organize a protest and there are more than 1,000 people in the group, what are the odds that one of them is a cop?
  2. Would a group chat protocol targeting groups with small numbers of participant (let's say 50 at most) be able to provide better security insurances efficiently?

For example, here are two security properties (taken from SoK: Secure Messaging) that MLS does not provide:

Speaker Consistency: All participants agree on the sequence of messages sent by each participant.

This means that if Alice (who is part of a group chat with Bob and Eve) colludes with the server, she can send "I like cats" to Bob and "I like dogs" to Eve.

Global Transcript: All participants see all messages in the same order. Note that this implies speaker consistency

This means that if Alice sends the following messages:

  • you must decide
  • your path

a server could re-order these messages so that Bob would see them in the same order, but Eve would see:

  • your path
  • you must decide

yoda


I have the following open questions:

  • Are these attacks important to protect against?
  • Is there an efficient protocol to prevent these attacks for groups of reasonable size?
  • If we cannot prevent them, can we detect them and warm the users?
  • If we are willing to change the protocol when going from 2 participants to 3 participants, would be willing to change the protocol when going from N to N+1 participants (where N is the number of participants threshold where confidentiality/privacy fades away)?
2 comments

A history of end-to-end encryption and the death of PGP posted January 2020


This is were everything starts, we now have an open peer-to-peer protocol that everyone on the internet can use to communicate.


  • 1991
    • The US government introduces the 1991 Senate Bill 266, which attempts to allow "the Government to obtain the plain text contents of voice, data, and other communications when appropriately authorized by law" from "providers of electronic communications services and manufacturers of electronic communications service equipment". The bill fails to pass into law.
    • Pretty Good Privacy (PGP) - released by Phil Zimmermann.
  • 1993 - The US Government launches a criminal investigation against Phil Zimmermann for sharing a cryptographic tool to the world (at the time crypto exporting laws are a thing).
  • 1995 - Zimmermann publishes PGP's source code in a book via MIT Press, dodging the criminal investigation by using the first ammendment's protection of books.

That's it, PGP is out there, people now have a weapon to fight government surveillance. As Zimmermann puts it:

PGP empowers people to take their privacy into their own hands. There's a growing social need for it. That's why I wrote it.


  • 1995 - The RSA Data Security company proposes S/MIME as an alternative to PGP.
  • 1996
  • 1997
    • GNU Privacy Guard (GPG) - version 0.0.0 released by Werner Koch.
    • PGP 5 is released.

      The original agreement between Viacrypt and the Zimmermann team had been that Viacrypt would have even-numbered versions and Zimmermann odd-numbered versions. Viacrypt, thus, created a new version (based on PGP 2) that they called PGP 4. To remove confusion about how it could be that PGP 3 was the successor to PGP 4, PGP 3 was renamed and released as PGP 5 in May 1997

  • 1997 - PGP Inc is acquired by Network Associates
  • 1998 - RFC 2440 - OpenPGP Message Format

    OpenPGP - This is a definition for security software that uses PGP 5.x as a basis.

  • 1999
    • GPG version 1.0 released
    • Extensible Messaging and Presence Protocol (XMPP) is developed by the open source community. XMPP is a federated chat protocol (users can run their own servers) that does not have end-to-end encryption and requires communications to be synchronous (both users have to be online).
  • 2002 - PGP Corporation is formed by ex-PGP members and the PGP license/assets are bought back from Network Associates
  • 2004 - Off-The-Record (OTR) is introduced by Nikita Borisov, Ian Avrum Goldberg, and Eric A. Brewer as an extension of the XMPP chat protocol in "Off-the-Record Communication, or, Why Not To Use PGP"

    We argue that [...] the encryption must provide perfect forward secrecy to protect from future compromises [...] the authentication mechanism must offer repudiation, so that the communications remain personal and unverifiable to third parties


We now have an interesting development: messaging (which is seen as a different way of communication for most people) is getting the same security treatment as email.


  • 2006 - GPG version 2.0 released
  • 2007 - RFC 4880 - OpenPGP Message Format
  • 2010 - Symantec purchases the rights for PGP for $300 million.
  • 2011 - Cryptocat is released.
  • 2013 - The TextSecure (now Signal) application is introduced, built on top of the TextSecure protocol with Axolotl (now the Signal protocol with the double ratchet) as an evolution of OTR and SCIMP. It provides asynchronous communication unlike other messaging protocols, closing the gap between messaging and email.
  • 2014

PGP becomes increasingly criticized, as Matt Green puts it in 2014:

It’s time for PGP to die.



Another unexpected development: security professionals are now giving up on encrypted emails, and are moving to secure messaging. Is messaging going to replace email, even though it feels like a different mean of communication?

Moxie's quotes are quite interesting:

In the 1990s, I was excited about the future, and I dreamed of a world where everyone would install GPG. Now I’m still excited about the future, but I dream of a world where I can uninstall it.

In addition to the design philosophy, the technology itself is also a product of that era. As Matthew Green has noted, “poking through an OpenPGP implementation is like visiting a museum of 1990s crypto.” The protocol reflects layers of cruft built up over the 20 years that it took for cryptography (and software engineering) to really come of age, and the fundamental architecture of PGP also leaves no room for now critical concepts like forward secrecy.

In 1997, at the dawn of the internet’s potential, the working hypothesis for privacy enhancing technology was simple: we’d develop really flexible power tools for ourselves, and then teach everyone to be like us. Everyone sending messages to each other would just need to understand the basic principles of cryptography. [...]

The GnuPG man page is over sixteen thousand words long; for comparison, the novel Fahrenheit 451 is only 40k words. [...]

Worse, it turns out that nobody else found all this stuff to be fascinating. Even though GPG has been around for almost 20 years, there are only ~50,000 keys in the “strong set,” and less than 4 million keys have ever been published to the SKS keyserver pool ever. By today’s standards, that’s a shockingly small user base for a month of activity, much less 20 years.


  • 2018
    • the first draft of Messaging Layer Security (MLS) is published, a standard for end-to-end encrypted group chat protocols.
    • EFAIL releases damaging vulnerabilities against most popular PGP and S/Mime implementations.

      In a nutshell, EFAIL abuses active content of HTML emails, for example externally loaded images or styles, to exfiltrate plaintext through requested URLs. To create these exfiltration channels, the attacker first needs access to the encrypted emails, for example, by eavesdropping on network traffic, compromising email accounts, email servers, backup systems or client computers. The emails could even have been collected years ago.

  • 2019 - Latacora - The PGP Problem

    Why do people keep telling me to use PGP? The answer is that they shouldn’t be telling you that, because PGP is bad and needs to go away.


EFAIL is the straw that broke the camel's back. PGP is officially dead.


  • 2019
    • Matrix is out of beta and working on making end-to-end encryption the default.
    • Moxie gives a controversial talk at CCC arguing that advancements in security, privacy, censorship resistance, etc. are incompatible with slow moving decentralized protocols. Today, most serious end-to-end encrypted messaging apps use the Signal protocol (Signal, Facebook Messenger, WhatsApp, Skype, etc.)
    • XMPP's response: Re: the ecosystem is moving
    • Matrix's response: On privacy versus freedom

did you like this? This will part of a book on cryptography! Check it out here.

5 comments