Entity authentication with a KEM

In cryptography, the process of authenticating a user (or app/service) is known as entity authentication or identification (to distinguish it from message authentication or data origin authentication). There are lots of ways to do this. In this post I’m going to talk about authentication schemes based on public key cryptography. It turns out that the notion of Key Encapsulation Mechanism (KEM), originally invented for (unauthenticated) public key encryption, also provides a unifying framework for thinking about public key entity authentication.

Continue reading “Entity authentication with a KEM”

Book review: The Joy of Cryptography

Mike Rosulek, Oregon State University. Draft of January 3, 2021. Online: The Joy of Cryptography.

This is a freely-available book covering introductory material on cryptography. It’s suitable for anyone with undergraduate-level computer science knowledge. As is often the case in cryptography textbooks, there is a brief review of mathematical background in the first (or zeroth in this case) chapter: modular arithmetic, probability, and Big-O notation. This chapter is brief but clear and establishes the sense of humour that is present throughout the book.

Overall, the book is very well-presented and -written for the target audience—undergraduates and practitioners. I have read several other textbooks on cryptography, but most are pitched more at a level for post-graduate students (even if apparently meant for undergrads). The writing here is always clear and focused, without leaving out essential details. In particular, I appreciated that security definitions are immediately followed by a discussion on the implications of that definition, and what it leaves out.

On a more basic note, the book is beautifully presented, and clearly a lot of thought has gone into the typography, layout, and diagrams (which have a pleasing “tightness” in their use of space).

It is largely a book about symmetric cryptography—the first 12 chapters cover symmetric material in depth, and only the last 3 chapters cover public key crypto. I actually quite like this split, because I believe many topics that are discussed in the context of public key cryptography have simpler illustrations in a symmetric setting. Still, you may find the public key material a little sparse. There is no discussion of elliptic curves, for example, or the developing field of post-quantum cryptography. There is also no material on hybrid encryption (i.e., using a combination of public key and symmetric primitives) or the KEM-DEM paradigm, which I would expect in any modern textbook.

Update: Mike Rosulek pointed out that the book does actually cover hybrid encryption in the very last section: 15.4. Mea culpa.

It is a draft though, and the roadmap makes clear that some subjects that I would expect to be covered are coming at some point. On the other hand, by the time you finish the book you will know enough to tackle some of the more comprehensive textbooks, such as Smart’s Cryptography Made Simple (lol) or Boneh & Shoup’s Graduate Course in Applied Cryptography.

The presentation is also quite slow, taking its time to develop topics and foster a real understanding. This is both a blessing and a curse. The clarity is welcome, but you have to get to chapter 12 before authenticated encryption is covered. If you are looking to find out “what should I be using?”, waiting 12 chapters to find out might be testing your patience a little. But if you want to really understand the topics and what modern cryptography is all about, your patience is paid off.

The approach used in the book to proving security of schemes is that of code-based games. The idea here is that a cryptographic scheme is developed as a kind of abstract data type or API, defining the operations that can be performed: generating a key, encrypting a message, decrypting a message, and so on. An adversary is then given access to two implementations of that API: one that is our real encryption scheme, and another that is some idealised (typically random) implementation of it. The API the attacker sees is restricted in some ways compared to what a real user would see (e.g., the attacker doesn’t get to see the key used for encryption). A scheme is secure if we can prove that no “reasonable” adversary can tell which implementation they have been given any better than a blind guess.

A proof in this scheme proceeds by replacing parts of the real implementation with idealised versions, until we can show that an attack on the real implementation is equivalent to an attack on the idealised version. Such proofs are always relative to some basic set of primitives that we believe to be close enough to the ideal versions already (generally because a lot of smart people have tried to break them for a long time and failed).

This is a different approach than a lot of textbooks, which use this indistinguishability proof style only for encryption, and then switch to other types of games for other security notions (such as message authentication). I found this uniform presentation very helpful in understanding the material and in seeing connections between security notions that I hadn’t appreciated before. For example, this book is the first time I’ve appreciated the importance of the Decisional Diffie-Hellman assumption to proving pseudorandomness of key agreement, which then motivates the use of quadratic residues and safe primes. (Although it’s missing a follow-up discussion on the use of hashing/random oracles to relax this assumption, which is what you would do in practice—a chapter on hybrid encryption would help clarify this).

An another example, the book introduces secret sharing early on and then points out that a one-time pad can be viewed as a simple 2-of-2 secret sharing technique, a connection I had never made before. Secret sharing can be viewed as a type of multi-party computation (MPC) and the author is an MPC researcher and co-author of an MPC textbook. This specialist knowledge provides a welcome fresh perspective on otherwise familiar material.

Overall, this is an excellent introduction to cryptography, with a novel and engaging approach to security proofs. The draft status and some lacking topic areas make me hesitant to recommend it as your sole introduction to cryptography just yet, but as a companion to another textbook it has a lot to recommend it. Even if you believe you already know all this material, you may still gain a lot from reading it: I know I did.

On PBKDF2 iterations

There has been a lot of discussion recently around the LastPass breach, especially with regards to the number of PBKDF2 iterations applied to the master password to derive the vault encryption key. Other people have already dissected this particular breach, but I want to more generally talk about PBKDF2 iterations and security models. (I’m not going to talk about Argon2 or Bcrypt or any other algorithms).

Continue reading “On PBKDF2 iterations”

A few clarifications about CVE-2022-21449

Just a few quick notes/updates to correct some potentially inaccurate statements that are floating around on Reddit/Twitter etc:

  • The bug only impacts Java 15 and above. The original advisory from Oracle incorrectly listed earlier versions (like 7, 8 and 11) as being impacted. They have since corrected this. Note that they now only list 17 and 18, because 15 and 16 are no longer supported.
  • Bouncy Castle is not impacted by this vulnerability. They have their own ECDSA implementation, and it performs the relevant check to prevent this bug.
  • Although an all-zero signature value is the simplest way to exploit this, there are several alternative values that exhibit the same bug. As previously mentioned, Project Wycheproof has an excellent selection of test vectors for this bug and many variations on it, in different signature formats, and for different elliptic curves.
  • On a related note, some JWT libraries were initially assumed to be unaffected because a quirk of re-encoding raw (IEEE P1363) format signatures into ASN.1 format rejected zero values. But, as pointed out above, there are other invalid values that are not rejected by this conversion that still trigger the bug. Either upgrade your JVM, or your JWT library, and ideally both.
  • Some JWT libraries also apparently accept signature values in several alternative encodings, so if you are checking for bad signatures in a pre-processing step then you have even more values to check. Again, best to update to get the patches rather than trying to fix this yourself.

CVE-2022-21449: Psychic Signatures in Java

The long-running BBC sci-fi show Doctor Who has a recurring plot device where the Doctor manages to get out of trouble by showing an identity card which is actually completely blank. Of course, this being Doctor Who, the card is really made out of a special “psychic paper“, which causes the person looking at it to see whatever the Doctor wants them to see: a security pass, a warrant, or whatever.

Doctor Who holding up a blank ID card with a badly superimposed image of Duke (the Java mascot) holding a glass of wine.
“Looks legit to me. Hic!

It turns out that some recent releases of Java were vulnerable to a similar kind of trick, in the implementation of widely-used ECDSA signatures. If you are running one of the vulnerable versions then an attacker can easily forge some types of SSL certificates and handshakes (allowing interception and modification of communications), signed JWTs, SAML assertions or OIDC id tokens, and even WebAuthn authentication messages. All using the digital equivalent of a blank piece of paper.

It’s hard to overstate the severity of this bug. If you are using ECDSA signatures for any of these security mechanisms, then an attacker can trivially and completely bypass them if your server is running any Java 15, 16, 17, or 18 version before the April 2022 Critical Patch Update (CPU). For context, almost all WebAuthn/FIDO devices in the real world (including Yubikeys*) use ECDSA signatures and many OIDC providers use ECDSA-signed JWTs.

If you have deployed Java 15, Java 16, Java 17, or Java 18 in production then you should stop what you are doing and immediately update to install the fixes in the April 2022 Critical Patch Update.

Update: the official announcement from Oracle also lists older versions of Java, including 7, 8 and 11. Although I’m not aware of the bug impacting those older implementations they did fix a similar bug in the (non-EC) DSA implementation at the same time, so it’s possible older versions are also impacted. There are also other security vulnerabilities reported in the same CPU, so (as always) it is worth upgrading even if you are running an older Java version. The OpenJDK advisory on the other hand lists only versions 15, 17, and 18 as affected by this specific issue (CVE-2022-21449).

Update 2: Oracle have informed me they are in the process of correcting the advisory to state that only versions 15-18 are impacted. The CVE has already been updated. Note that 15 and 16 are no longer supported, so it will only list 17 and 18 as impacted.

Continue reading “CVE-2022-21449: Psychic Signatures in Java”

From KEMs to protocols

This is the third part of my series on Key Encapsulation Mechanisms (KEMs) and why you should care about them. Part 1 looked at what a KEM is and the KEM/DEM paradigm for constructing public key encryption schemes. Part 2 looked at cases where the basic KEM abstraction is not sufficient and showed how it can be extended to add support for multiple recipients and sender authentication. At the end of part 2, I promised to write a follow-up about tackling forward-secrecy and replay attacks in the KEM/DEM paradigm, so here it is. In this article we’ll go from simple one-way message encryption to a toy version of the Signal Protocol that provides forward secrecy and strong authentication of two (or more) parties.

WARNING: please pay attention to the word “toy” in the previous sentence. This is a blog post, not a thorough treatment of how to write a real end-to-end encrypted messaging protocol.

Continue reading “From KEMs to protocols”

When a KEM is not enough

In my previous post, I described the KEM/DEM paradigm for hybrid encryption. The key encapsulation mechanism is given the recipient’s public key and outputs a fresh AES key and an encapsulation of that key that the recipient can decapsulate to recover the AES key. In this post I want to talk about several ways that the KEM interface falls short and what to do about it:

  • As I’ve discussed before, the standard definition of public key encryption lacks any authentication of the sender, and the KEM-DEM paradigm is no exception. You often want to have some idea of where a message came from before you process it, so how can we add sender authentication?
  • If you want to send the same message to multiple recipients, a natural approach would be to encrypt the message once with a fresh AES key and then encrypt the AES key for each recipient. With the KEM approach though we’ll end up with a separate AES key for each recipient. How can we send the same message to multiple recipients without encrypting the whole thing separately for each one?
  • Finally, the definition of public key encryption used in the KEM/DEM paradigm doesn’t provide forward secrecy. If an attacker ever compromises the recipient’s long-term private key, they can decrypt every message ever sent to that recipient. Can we prevent this?

In this article I’ll tackle the first two issues and show how the KEM/DEM abstractions can be adjusted to cope with each. In a follow-up post I’ll then show how to tackle forward secrecy, along with replay attacks and other issues. Warning: this post is longer and has more technical details than the previous post. It’s really meant for people who already have some experience with cryptographic algorithms.

Continue reading “When a KEM is not enough”

Public key authenticated encryption and why you want it (Part II)

In Part I, I made the argument that even when using public key cryptography you almost always want authenticated encryption. In this second part, we’ll look at how you can actually achieve public key authenticated encryption (PKAE) from commonly available building blocks. We will concentrate only on approaches that do not require an interactive protocol. (Updated 12th January 2019 to add a description of a NIST-approved key-agreement mode that achieves PKAE).

Continue reading “Public key authenticated encryption and why you want it (Part II)”

Public key authenticated encryption and why you want it (Part I)

If you read or watch any recent tutorial on symmetric (or “secret key”) cryptography, one lesson should be clear: in 2018 if you want to encrypt something you’d better use authenticated encryption. This not only hides the content of a message, but also ensures that the message was sent by one of the parties that has access to the shared secret key and that it hasn’t been tampered with. It turns out that without these additional guarantees (integrity and authenticity), the contents of a message often does not remain secret for long either. Continue reading “Public key authenticated encryption and why you want it (Part I)”

Key-driven cryptographic agility

One of the criticisms of the JOSE/JWT standards is that they give an attacker too much flexibility, by allowing them to specify how a message should be processed. In particular, the standard “alg” header tells the recipient what cryptographic algorithm was used to sign or encrypt the contents. Letting the attacker chose the algorithm can lead to disastrous security vulnerabilities. Continue reading “Key-driven cryptographic agility”

%d bloggers like this: