Don’t Use Session (Signal Fork)

Last year, I outlined the specific requirements that an app needs to have in order for me to consider it a Signal competitor.

Afterwards, I had several people ask me what I think of a Signal fork called Session. My answer then is the same thing I’ll say today:

Don’t use Session.

The main reason I said to avoid Session, all those months ago, was simply due to their decision to remove forward secrecy (which is an important security property of cryptographic protocols they inherited for free when they forked libsignal).

Lack of forward secrecy puts you in the scope of Key Compromise Impersonation (KCI) attacks, which serious end-to-end encryption apps should prevent if they want to sit at the adults table. This is why I don’t recommend Tox.

And that observation alone should have been enough for anyone to run, screaming, in the other direction from Session. After all, removing important security properties from a cryptographic security protocol is exactly the sort of thing a malicious government would do (especially if the cover story for such a change involves the introduction of swarms and “onion routing”–which computer criminals might think sounds attractive due to their familiarity with the Tor network).

Unfortunately, some people love to dig their heels in about messaging apps. So let’s take a closer look at Session.

I did not disclose this blog post privately to the Session developers before pressing publish.

I do not feel that cryptographic issues always require coordinated disclosure with the software vendor. As Bruce Schneier argues, full disclosure of security vulnerabilities is a “damned good idea”.

I have separated this blog post into two sections: Security Issues and Gripes.

Security Issues

1. Insufficient Entropy in Ed25519 Keys
2. In-Band Negotiation for Message Signatures
3. Using Public Keys as AES-GCM Keys

Insufficient Entropy in Ed25519 Keys

One of the departures of Session from Signal is the use of Ed25519 rather than X25519 for everything.

Ed25519 Keypairs generated from their KeyPairUtilities object only have 128 bits of entropy, rather than the ~253 bits (after clamping) you’d expect from an Ed25519 seed.

fun generate(): KeyPairGenerationResult {    val seed = sodium.randomBytesBuf(16)    try {        return generate(seed)    } catch (exception: Exception) {        return generate()    }}fun generate(seed: ByteArray): KeyPairGenerationResult {    val padding = ByteArray(16) { 0 }    val ed25519KeyPair = sodium.cryptoSignSeedKeypair(seed + padding)

As an implementation detail, they encode a recovery key as a “mnemonic” (see also: a gripe about their mnemonic decoding).

Does This Matter?

You might think that clearing the highest 128 bits of the Ed25519 seed is fine for one of the following reasons:

1. It’s hashed with SHA512 before clamping.
2. Ed25519 only offers 128 bits of security.
3. Some secret third (and possibly unreasonable) argument.

It’s true that Ed25519 targets the 128-bit security level, if you’re focused on the security of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Achieving 128 bits of security in this model requires 256-bit secrets, since the best attack against the ECDLP finds a discrete logarithm in guesses.

Additionally, having 256-bit secrets makes the multi-user security of the scheme easy to reason about, whereas 128-bit secrets makes it a lot harder. (This mostly comes up in criticism of AES, which has a 128-bit block size.)

When your secret only has possible values, your multi-user security is no longer as secure as Ed25519 expects.

Additionally, you can shove the SHA512 + clamping in your attack script (thus negating the first objection) and find the corresponding secret key in queries if you know the top 128 bits were initialized to 0, using a modified version of Pollard’s rho for discrete logarithms.

This means that Session’s KeyPairUtilities class only provides 64 bits of ECDLP security.

What does 64 bits of ECDLP Security actually mean?

I provided a technical definition already, but that’s probably not meaningful to most people outside computer security.

What this means is that a distributed computing effort can find the secret key for a given Ed25519 public key generated from this algorithm in only queries.

For flavor, queries is approximately the attack cost to find a SHA1 collision, which we know is possible and economical.

Based on this attack, the authors projected that a collision attack on SHA-1 may cost between US$75K and US$120K by renting GPU computing time on Amazon EC2 using spot-instances, which is significantly lower than Schneier’s 2012 estimates.

— from the Shattered paper, page 2.

I don’t know if this was mere stupidity or an intentional NOBUS backdoor that only well-resourced adversaries can crack. (I also don’t have hundreds of thousands of dollars lying around to test this myself.)

How would you exploit this in practice?

If you’re not familiar with Pollard’s rho, then this section might be a bit abstract and difficult to follow.

Instead of directly passing a full 256-bit value to your oracle with each iteration (like you do with a standard Pollard’s rho implementation), you would need mutate the output the same way Session does (n.b., replace 128 bits of the seed with zeroes), hash & clamp that, and then perform the scalar multiplication.

It should be a bit more expensive than a raw ECDLP attack against a 128-bit curve (due to the hashing), but the strategy should succeed in the expected number of queries (average case).

Although this makes the attack totally feasible for a nation state, I do not have the resources to build and test a proof of concept against a candidate keypair. If anyone does, get in touch, it would make for a fun research project.

Alternatively, Pollard’s kangaroo might be a better cryptanalysis technique for Session’s setup.

Note: If there is any classified government algorithm especially suited for cracking Ed25519 keys constructed exactly like Session does, it’s not one I’ve ever heard of. I don’t have any security clearances, nor do I want one.

However, ECDLP security of elliptic curve-based protocols is extremely well-understood in the cryptography literature.

In-Band Negotiation for Message Signatures

If you thought the previous issue was mitigated by the use of Ed25519 signatures on each message, don’t worry, the Session developers screwed this up too!

// 2. ) Get the message partsval signature = plaintextWithMetadata.sliceArray(plaintextWithMetadata.size - signatureSize until plaintextWithMetadata.size)val senderED25519PublicKey = plaintextWithMetadata.sliceArray(plaintextWithMetadata.size - (signatureSize + ed25519PublicKeySize) until plaintextWithMetadata.size - signatureSize)val plaintext = plaintextWithMetadata.sliceArray(0 until plaintextWithMetadata.size - (signatureSize + ed25519PublicKeySize))// 3. ) Verify the signatureval verificationData = (plaintext + senderED25519PublicKey + recipientX25519PublicKey)try {    val isValid = sodium.cryptoSignVerifyDetached(signature, verificationData, verificationData.size, senderED25519PublicKey)    if (!isValid) { throw Error.InvalidSignature }} catch (exception: Exception) {    Log.d("Loki", "Couldn't verify message signature due to error: $exception.")    throw Error.InvalidSignature}

What this code is doing (after decryption):

1. Grab the public key from the payload.
2. Grab the signature from the payload.
3. Verify that the signature on the rest of the payload is valid… for the public key that was included in the payload.

Congratulations, Session, you successfully reduced the utility of Ed25519 to that of a CRC32!

Using Public Keys As AES-GCM Keys

I wasn’t entirely sure whether this belongs in the “gripes” section or not, because it’s so blatantly stupid that there’s basically no way Quarkslab would miss it if it mattered.

When encrypting payloads for onion routing, it uses the X25519 public key… as a symmetric key, for AES-GCM. See, encryptPayloadForDestination().

val result = AESGCM.encrypt(plaintext, x25519PublicKey)deferred.resolve(result)

Session also does this inside of encryptHop().

val plaintext = encode(previousEncryptionResult.ciphertext, payload)val result = AESGCM.encrypt(plaintext, x25519PublicKey)

In case you thought, maybe, that this is just a poorly named HPKE wrapper… nope!

 /** * Sync. Don't call from the main thread. */internal fun encrypt(plaintext: ByteArray, symmetricKey: ByteArray): ByteArray {    val iv = Util.getSecretBytes(ivSize)    synchronized(CIPHER_LOCK) {        val cipher = Cipher.getInstance("AES/GCM/NoPadding")        cipher.init(Cipher.ENCRYPT_MODE, SecretKeySpec(symmetricKey, "AES"), GCMParameterSpec(gcmTagSize, iv))        return ByteUtil.combine(iv, cipher.doFinal(plaintext))    }}

This obviously doesn’t encrypt it such that only the recipient (that owns the secret key corresponding to the public key) can decrypt the message. It makes it to where anyone that knows the public key can decrypt it.

I wonder if this impacts their onion routing assumptions?

Why should I trust session?

(…)

When using Session, your messages are sent to their destinations through a decentralised onion routing network similar to Tor (with a few key differences) (…)

Session FAQs

Gripes

Some of these aren’t really security issues, but are things I found annoying as a security engineer that specializes in applied cryptography.

1. Mnemonic Decoding Isn’t Constant-Time
2. Unsafe Use of SecureRandom on Android

Mnemonic Decoding Isn’t Constant-Time

The way mnemonics are decoded involves the modulo operator, which implicitly uses integer division (which neither Java nor Kotlin nor Swift implement in constant-time).

return wordIndexes.windowed(3, 3) { (w1, w2, w3) ->    val x = w1 + n * ((n - w1 + w2) % n) + n * n * ((n - w2 + w3) % n)    if (x % n != w1.toLong()) throw DecodingError.Generic    val string = "0000000" + x.toString(16)    swap(string.substring(string.length - 8 until string.length))}.joinToString(separator = "") { it }

This isn’t a real security problem, but I did find it annoying to see in an app evangelized as “better than Signal” on privacy forums.

Unsafe Use of SecureRandom on Android

The recommended way to get secure random numbers on Android (or any Java or Kotlin software, really) is simply new SecureRandom(). If you’re running a service in a high-demand environment, you can take extra care to make a thread-local instance of SecureRandom. But a local RNG for a single user isn’t that.

What does Session do? They use SHA1PRNG, of course.

public static byte[] getSecretBytes(int size) {  try {    byte[] secret = new byte[size];    SecureRandom.getInstance("SHA1PRNG").nextBytes(secret);    return secret;  } catch (NoSuchAlgorithmException e) {    throw new AssertionError(e);  }}

And again here.

SecureRandom secureRandom = SecureRandom.getInstance("SHA1PRNG");

Why would anyone care about this?

On modern Android devices, this isn’t a major concern, but the use of SHA1PRNG used to be a source of vulnerabilities in Android apps. (See also: this slide deck.)

Closing Thoughts

There are a lot of Session’s design decisions that are poorly specified in their Whitepaper and I didn’t look at. For example, how group messaging keys are managed.

When I did try to skim that part of the code, I did find a component where you can coerce Android clients into running a moderately expensive Argon2 KDF by simply deleting the nonce from the message.

val isArgon2Based = (intermediate["nonce"] == null)if (isArgon2Based) {    // Handle old Argon2-based encryption used before HF16

That’s hilarious.

Cryptography nerds should NOT be finding the software that activists trust with their privacy hilarious.

So if you were wondering what my opinion on Session is, now you know: Don’t use Session. Don’t let your friends use Session.

If you’re curious about the cryptography used by other messaging apps, please refer to this page that collects my blogs about this topic.

#AESGCM #Android #asymmetricCryptography #cryptography #E2EE #Ed25519 #Java #Kotlin #messagingApps #OnlinePrivacy #privateMessaging #Session #Signal #SignalAlternatives #vuln

Neil Madden recently wrote a blog post titled, Digital Signatures and How to Avoid Them. One of the major points he raised is:

Another way that signatures cause issues is that they are too powerful for the job they are used for. You just wanted to authenticate that an email came from a legitimate server, but now you are providing irrefutable proof of the provenance of leaked private communications. Oops!

Signatures are very much the hammer of cryptographic primitives. As well as authenticating a message, they also provide third-party verifiability and (part of) non-repudiation.

Neil Madden

Later, he goes on to make recommendations for alternatives. Namely HMAC, possibly with a KEM. His recommendations are sensible and straightforward.

Where’s the fun in that, though?

Let’s design a type of digital signature algorithm that can only be verified by the intended recipients.

Standard Crypto Disclaimer

Don’t use any of this.

I’m rolling my own crypto, which is almost always a bad idea, for my own amusement.

Absolutely none of this has been peer-reviewed or audited.

Even if there’s no immediately obvious fatal flaw in this design, it’s always possible that I screwed something up.

If anything of value ever comes of this post, it will be serious cryptographers writing their own protocol that accomplishes the goals set out in this furry blog post, but with a machine verifiable security proof.

X3MAC

Let’s start with a somewhat simple building block (using libsodium), which I call X3MAC.

Why? Because it’s partly inspired by X3DH.

The idea is pretty straightforward, and basically in line with what Neil recommended:

1. Generate an ephemeral keypair.
2. Do two ECDHs. One between the sender and the recipient, the other between the ephemeral keypair and the recipient.
3. Use a domain-separated hash with both ECDH outputs and all three public keys to obtain a symmetric key.
4. Calculate a MAC over the message, using the symmetric key.
5. Return the ephemeral public key and MAC.

Verification is basically deriving the same symmetric key from the recipient’s perspective, recalculating the MAC, and comparing the two in constant-time.

This should be pretty easy to understand.

Why bother with ephemeral keypairs?

It doesn’t buy us much for the MAC use-case (since we aren’t encrypting so forward secrecy isn’t a consideration), but we will use it when we turn the X3MAC into X3SIG.

What are people saying about X3MAC?

When I showed X3MAC to some friends, some recoiled in horror and others said, “Oh, I think I have a use case!”

I really hope they’re joking. But out of caution, this is where I will cease to provide sample code.

Sarah Jamie Lewis said, “thank you i hate this.” That’s probably the correct response.

Turning X3MAC into a Signature

X3MAC isn’t actually very useful.

If Alice and Bob use X3MAC, it’s true that only the two of them can verify the authentication tag for a message… but both parties can also create authentication tags.

To turn this into a signature algorithm, we need to work with the Ristretto group and build a non-interactive variant of Schnorr’s identification protocol.

My modified protocol, X3SIG, uses Ristretto255 scalars and points instead of X25519 keypairs.

“What does any of that even mean?“

Ristretto255 is a prime-order group (imagine a clock, but instead of numbers going from 1 to 12, it’s between 0 and a very large prime number), built from Curve25519.

Scalars are analogous to secret keys.

Points are analogous to public keys.

You can do point arithmetic. You can do scalar arithmetic. You don’t have to worry about the cofactor (like you would with Ed25519 or X25519).

Schnorr’s identification protocol (explained above) is essentially the basis of elliptic curve signatures; i.e., you can construct EdDSA out of it with minor (yet important) tweaks.

That’s exactly what we’re doing here: Turning X3MAC into a signature by building Schnorr out of it.

The protocol begins the same way as X3MAC: Generate a random scalar, multiply it by the base point to get a point. Do some point-scalar multiplications and a domain-separated hash to derive a symmetric key. Hash the message with the symmetric key.

But this time, we don’t stop there. We use the X3MAC-alike hash in place of the Hash() step in non-interactive Schnorr.

Important: We can eschew some data from the hashing step because certain parameters are fixed by virtue of using Ristretto255.

If anyone ever builds something on another group, especially one where these parameters can change, you MUST also include all of them in the hash.

If you fail to do this, you will find yourself vulnerable to weak Fiat-Shamir attacks (e.g., Frozen Heart). If you’re writing Rust, check out Decree for transcript hashing.

(As stated before: No sample code will be provided, due to not wanting people to ship it to production.)

What does this give us?

Alice can sign a message that only she and Bob can verify. Bob cannot generate a new signature. Third parties cannot perform either action.

Thus, we still have a digital signature, but not one that provides third-party verifiability.

X3INU – Cryptographic Innuendos

If we had stopped the train at X3SIG, that’d be pretty neat.

However, X3SIG is limited to one sender and one recipient. This is kind of a bummer that doesn’t scale very well.

Fortunately, this is a solvable problem.

If you recall from my idea for multicast support in Noise-based protocols, I’m no stranger to reusing the TreeKEM abstraction from the MLS RFC to nerd-snipe my friends in the cryptography community.

So let’s do that here.

X3INU.Pack

Inputs:

1. 1 keypair (sk, pk)
2. A finite number of other public keys (pk_i for many values of i)

Output:

• Group public key gpk

Here, we use a Ratchet Tree (per RFC 9420) where each step is a scalar multiplication over the Ristretto group (since that’s what everyone’s public key is) and a Key Derivation Function.

The important property is that each participant in the Pack can asynchronously derive the group secret key, and it’s computationally infeasible to do so without one of the pack members’ secret keys.

This step must be performed ahead of time to establish the Pack (quorum of recipients that can verify a signature).

X3INU.Howl

Inputs:

1. The message being signed.
2. The secret key for the entity sending the message.
3. The pack public key for all of the recipients.

Outputs:

1. A signature that only pack members can validate.

Here, we just perform an X3SIG signature with the pack public key.

X3INU.Hear

Inputs:

1. The message being signed.
2. The signature.
3. The public key for the entity sending the message.
4. The secret key for a pack member.
5. The pack public key for all other recipients.

Outputs:

1. Boolean (is the signature valid?)

Here, we just perform an X3SIG validation.

If you’re a member of the pack that can validate the signature, you can derive the group secret key and perform X3SIG as usual.

If you’re not, you can’t tell if the signature is valid or not. To you, it should be indistinguishable from random.

X3INU Questions and Answers

Why “X3INU”?

It’s short for “innuendo”, but also “inu” is the Japanese word for “dog”, and I like to make furry puns.

Why “Pack”, “Howl”, and “Hear”?

See above! Furry puns!

Why are you like this?

I dunno.

You fool, this already exists in the cryptographic literature under a different name! What do you have to say for yourself?

Okay, yeah, probably.

I’m not an academic, so if I reinvented something that someone else made (except worse, because this is being published on a furry blog for fun), that’s kind of cool but not surprising.

It also shouldn’t be surprising that I haven’t heard of it before, due to me not being an academic.

(The closest I’ve heard of are designated verifier signatures, as Neil Madden alluded to at the bottom of his blog post.)

What if I think this might actually be useful?

Normally, I would say, “Talk to a cryptographer before writing any code,” especially if you’re writing your own protocol that uses a Fiat-Shamir transform like I did here.

However, if it turns out that X3INU is in any way novel or valuable, you should instead consult the entire cryptographic community and wait for their verdict on whether this idea is totally bonkers or not.

Why not just public-key-encrypt a digital signature?

Why not just use the existing digital signature algorithms, but encrypt it under the recipients’ public keys?

Tursiae

Because after decryption, the recipient possesses a signature that a third-party could still use to verify the contents of a communication.

If you transmit the signatures produced by X3INU, only the audience can tell if they’re genuine or not.

(This assumes your audience’s secret keys all remain secret, of course.)

Under what conditions do the security guarantees fall apart?

If the signer reveals their secret key, messages can be forged.

If one of the Pack members reveals their secret key, anyone can verify signatures again.

If one of the Pack members leaks the internal hash used for a given message, anyone who knows this hash can verify the signature. Pack members can do this without compromising their own signing key.

This leakage is possible because the signature is computed over a keyed hash, and the key used by the hash is a shared secret between the signer and the recipients.

Thanks to Thad for inquiring about this:

could Bob not reveal the shared symmetric key from the X3MAC to a third party? His private key is still protected by mixing the ephemeral key and the KDF, while having the shared key allows the third party to verify the message hash and prove it with Alice’s public signing key(?)

Thad

Additionally, nothing about this protocol is post-quantum secure.

Couldn’t you extend X3MAC instead of X3SIG for the Innuendo protocol?

Yes. It may even be desirable to do so.

The only downside is: Anyone in the quorum can forge messages, so there is no special “signer” role, really.

With that in mind, you’re probably better off just using a Ratchet Tree to get a shared secret, and then using that with HMAC.

Can we make it even more wild?

Here’s a fun one: Combine the idea behind innuendos (as outlined above) with ring signatures.

Now Alice is one indeterminate member of a discrete set of potential signers, rather than just one, who can sign a message such that only a designated group of recipients can verify (provided nobody’s secret key is leaked).

Header art by Harubaki and CMYKat.

https://soatok.blog/2024/09/20/cryptographic-innuendos/

#asymmetricCryptography #cryptographicInnuendos #RatchetTrees

There is, at the time of this writing, an ongoing debate in the Crypto Research Forum Group (CFRG) at the IETF about KEM combiners.

One of the participants, Deirdre Connolly, wrote a blog post titled How to Hold KEMs. The subtitle is refreshingly honest: “A living document on how to juggle these damned things.”

Deirdre also co-authored the paper describing a Hybrid KEM called X-Wing, which combines X25519 with ML-KEM-768 (which is the name for a standardized tweak of Kyber, which I happened to opine on a few years ago).

After sharing a link to Deirdre’s blog in a few places, several friendly folk expressed confusion about KEMs in general.

So very briefly, here’s an introduction to Key Encapsulation Mechanisms in general, to serve as a supplementary resource for any future discussion on KEMs.

You shouldn’t need to understand lattices or number theory, or even how to read a mathematics paper, to understand this stuff.

Building Intuition for KEMs

For the moment, let’s suspend most real-world security risks and focus on a simplified, ideal setting.

To begin with, you need some kind of Asymmetric Encryption.

Asymmetric Encryption means, “Encrypt some data with a Public Key, then Decrypt the ciphertext with a Secret Key.” You don’t need to know, or even care, about how it works at the moment.

Your mental model for asymmetric encryption and decryption should look like this:

interface AsymmetricEncryption {  encrypt(publicKey: CryptoKey, plaintext: Uint8Array);  decrypt(secretKey: CryptoKey, ciphertext: Uint8Array);}

As I’ve written previously, you never want to actually use asymmetric encryption directly.

Using asymmetric encryption safely means using it to exchange a key used for symmetric data encryption, like so:

// Alice sends an encrypted key to BobsymmetricKey = randomBytes(32)sendToBob = AsymmetricEncryption.encrypt(    bobPublicKey,    symmetricKey)// Bob decrypts the encrypted key from Alicedecrypted = AsymmetricEncryption.decrypt(    bobSecretKey,    sendToBob)assert(decrypted == symmetricKey) // true

You can then use symmetricKey to encrypt your actual messages and, unless something else goes wrong, only the other party can read them. Hooray!

And, ideally, this is where the story would end. Asymmetric encryption is cool. Don’t look at the scroll bar.

Unfortunately

The real world isn’t as nice as our previous imagination.

We just kind of hand-waved that asymmetric encryption is a thing that happens, without further examination. It turns out, you have to examine further in order to be secure.

The most common asymmetric encryption algorithm deployed on the Internet as of February 2024 is called RSA. It involves Number Theory. You can learn all about it from other articles if you’re curious. I’m only going to describe the essential facts here.

Keep in mind, the primary motivation for KEMs comes from post-quantum cryptography, not RSA.

From Textbook RSA to Real World RSA

RSA is what we call a “trapdoor permutation”: It’s easy to compute encryption (one way), but decrypting is only easy if you have the correct secret key (the other way).

RSA operates on large blocks, related to the size of the public key. For example: 2048-bit RSA public keys operate on 2048-bit messages.

Encrypting with RSA involves exponents. The base of these exponents is your message. The outcome of the exponent operation is reduced, using the modulus operator, by the public key.

(The correct terminology is actually slightly different, but we’re aiming for intuition, not technical precision. Your public key is both the large modulus and exponent used for encryption. Don’t worry about it for the moment.)

If you have a very short message, and a tiny exponent (say, 3), you don’t need the secret key to decrypt it. You can just take the cube-root of the ciphertext and recover the message!

That’s obviously not very good!

To prevent this very trivial weakness, cryptographers proposed standardized padding schemes to ensure that the output of the exponentiation is always larger than the public key. (We say, “it must wrap the modulus”.)

The most common padding mode is called PKCS#1 v1.5 padding. Almost everything that implements RSA uses this padding scheme. It’s also been publicly known to be insecure since 1998.

The other padding mode, which you should be using (if you even use RSA at all) is called OAEP. However, even OAEP isn’t fool proof: If you don’t implement it in constant-time, your application will be vulnerable to a slightly different attack.

This Padding Stinks; Can We Dispense Of It?

It turns out, yes, we can. Safely, too!

We need to change our relationship with our asymmetric encryption primitive.

Instead of encrypting the secret we actually want to use, let’s just encrypt some very large random value.

Then we can use the result with a Key Derivation Function (which you can think of, for the moment, like a hash function) to derive a symmetric encryption key.

class OversimplifiedKEM {  function encaps(pk: CryptoKey) {    let N = pk.getModulus()    let r = randomNumber(1, N-1)    let c = AsymmetricEncryption.encrypt(pk, r)    return [c, kdf(r)]  }  function decaps(sk: CryptoKey, c: Uint8Array) {    let r2 = AsymmetricEncryption.decrypt(sk, c)    return kdf(r2)  }}

In the pseudocode above, the actual asymmetric encryption primitive doesn’t involve any sort of padding mode. It’s textbook RSA, or equivalent.

KEMs are generally constructed somewhat like this, but they’re all different in their own special, nuanced ways. Some will look like what I sketched out, others will look subtly different.

Understanding that KEMs are a construction on top of asymmetric encryption is critical to understanding them.

It’s just a slight departure from asymmetric encryption as most developers intuit it.

Cool, we’re almost there.

The one thing to keep in mind: While this transition from Asymmetric Encryption (also known as “Public Key Encryption”) to a Key Encapsulation Mechanism is easy to follow, the story isn’t as simple as “it lets you skip padding”. That’s an RSA specific implementation detail for this specific path into KEMs.

The main thing you get out of KEMs is called IND-CCA security, even when the underlying Public Key Encryption mechanism doesn’t offer that property.

IND-CCA security is a formal notion that basically means “protection against an attacker that can alter ciphertexts and study the system’s response, and then learn something useful from that response”.

IND-CCA is short for “indistinguishability under chosen ciphertext attack”. There are several levels of IND-CCA security (1, 2, and 3). Most modern systems aim for IND-CCA2.

Most people reading this don’t have to know or even care what this means; it will not be on the final exam. But cryptographers and their adversaries do care about this.

What Are You Feeding That Thing?

Deirdre’s blog post touched on a bunch of formal security properties for KEMs, which have names like X-BIND-K-PK or X-BIND-CT-PK.

Most of this has to deal with, “What exactly gets hashed in the KEM construction at the KDF step?” (although some properties can hold even without being included; it gets complicated).

For example, from the pseudocode in the previous section, it’s more secure to not only hash r, but also c and pk, and any other relevant transcript data.

class BetterKEM {  function encaps(pk: CryptoKey) {    let N = pk.getModulus()    let r = randomNumber(1, N-1)    let c = AsymmetricEncryption.encrypt(pk, r)    return [c, kdf(pk, c, r)]  }  function decaps(sk: CryptoKey, c: Uint8Array) {    let pk = sk.getPublickey()    let r2 = AsymmetricEncryption.decrypt(sk, c)    return kdf(pk, c, r2)  }}

In this example, BetterKem is greatly more secure than OversimplifiedKEM, for reasons that have nothing to do with the underlying asymmetric primitive. The thing it does better is commit more of its context into the KDF step, which means that there’s less pliability given to attackers while still targeting the same KDF output.

If you think about KDFs like you do hash functions (which they’re usually built with), changing any of the values in the transcript will trigger the avalanche effect: The resulting calculation, which is not directly transmitted, is practically indistinguishable from random bytes. This is annoying to try to attack–even with collision attack strategies (birthday collision, Pollard’s rho, etc.).

However, if your hash function is very slow (i.e., SHA3-256), you might be worried about the extra computation and energy expenditure, especially if you’re working with larger keys.

Specifically, the size of keys you get from ML-KEM or other lattice-based cryptography.

That’s where X-Wing is actually very clever: It combines X25519 and ML-KEM-768 in such a way that binds the output to both keys without requiring the additional bytes of ML-KEM-768 ciphertext or public key.

However, it’s only secure to use it this way because of the specific properties of ML-KEM and X25519.

Some questions may come to mind:

1. Does this additional performance hit actually matter, though?
2. Would a general purpose KEM combiner be better than one that’s specially tailored to the primitives it uses?
3. Is it secure to simply concatenate the output of multiple asymmetric operations to feed into a single KDF, or should a more specialized KDF be defined for this purpose?

Well, that’s exactly what the CFRG is debating!

Closing Thoughts

KEMs aren’t nearly as arcane or unapproachable as you may suspect. You don’t really even need to know any of the mathematics to understand them, though it certainly does help.

I hope that others find this useful.

Header art by Harubaki and AJ.

https://soatok.blog/2024/02/26/kem-trails-understanding-key-encapsulation-mechanisms/

#asymmetricCryptography #cryptography #KDF #KEM #keyEncapsulationMechanism #postQuantumCryptography #RSA

I wonder if it's possible to implement public-key signing for posts within ActivityPub, it could be a good verification solution for those who really need it. Maybe it's already in the spec?

#Mastodon #ActivityPub #Fediverse #Cryptography #PublicKeyCryptography #AsymmetricCryptography #GnuPG #PGP #Verification #AccountVerification #DigitalIdentity #CyberSecurity #InfoSec