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.

CMYKat

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.

CMYKat

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.

CMYKat

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.

CMYKat

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.

CMYKat

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.

From the X-Wing paper.

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!

CMYKat

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

Dhole Moments

2022-01-27 11:13:50

Did you know that, in the Furry Fandom, the most popular choice in species for one’s fursona is actually a hybrid?

Source: FurScience

Of course, we’re not talking about that kind of hybrid today. I just thought it was an amusing coincidence.

Art: Lynx vs Jackalope

Nor are we talking about what comes to mind for engineers accustomed to classical cryptography when you say Hybrid.

(Such engineers typically envision some combination of asymmetric key encapsulation with symmetric encryption; because too many people encrypt with RSA directly and the sane approach is often described as a Hybrid Cryptosystem in the literature.)

Rather, Hybrid Cryptography in today’s context refers to:

Cryptography systems that use a post-quantum cryptography algorithm, combined with one of the algorithms deployed today that aren’t resistant to quantum computers.

If you need to differentiate the two, PQ-Hybrid might be a better designation.

Why Hybrid Cryptosystems?

At some point in the future (years or decades from now), humanity may build a practical quantum computer. This will be a complete disaster for all of the cryptography deployed on the Internet today.

In response to this distant existential threat, cryptographers have been hard at work designing and attacking algorithms that remain secure even when quantum computers arrive. These algorithms are classified as post-quantum cryptography (mostly to distinguish it from techniques that uses quantum computers to facilitate cryptography rather than attack it, which is “quantum cryptography” and not really worth our time talking about). Post-quantum cryptography is often abbreviated as “PQ Crypto” or “PQC”.

However, a lot of the post-quantum cryptography designs are relatively new or comparatively less studied than their classical (pre-quantum) counterparts. Several of the Round 1 candidates to NIST’s post quantum cryptography project were broken immediately (PDF). Exploit code referenced in PDF duplicated below.:

#!/usr/bin/env python3import binascii, structdef recover_bit(ct, bit): assert bit < len(ct) // 4000 ts = [struct.unpack('BB', ct[i:i+2]) for i in range(4000*bit, 4000*(bit+1), 2)] xs, ys = [a for a, b in ts if b == 1], [a for a, b in ts if b == 2] return sum(xs) / len(xs) >= sum(ys) / len(ys)def decrypt(ct): res = sum(recover_bit(ct, b) << b for b in range(len(ct) // 4000)) return int.to_bytes(res, len(ct) // 4000 // 8, 'little')kat = 0for l in open('KAT_GuessAgain/GuessAgainEncryptKAT_2000.rsp'): if l.startswith('msg = '): # only used for verifying the recovered plaintext. msg = binascii.unhexlify(l[len('msg = '):].strip()) elif l.startswith('c = '): ct = binascii.unhexlify(l[len('c = '):].strip()) print('{}attacking known-answer test #{}'.format('\n' * (kat > 0), kat)) print('correct plaintext: {}'.format(binascii.hexlify(msg).decode())) plain = decrypt(ct) print('recovered plaintext: {} ({})'.format(binascii.hexlify(plain).decode(), plain == msg)) kat += 1

More pertinent to our discussions: Rainbow, which was one of the Round 3 Finalists for post-quantum digital signature algorithms, was discovered in 2020 to be much easier to attack than previously thought. Specifically, for the third round parameters, the attack cost was reduced by a factor of , , and .

That security reduction is just a tad bit more concerning than a Round 1 candidate being totally broken, since NIST had concluded by then that Rainbow was a good signature algorithm until that attack was discovered. Maybe there are similar attacks just waiting to be found?

Given that new cryptography is accompanied by less confidence than incumbent cryptography, hybrid designs are an excellent way to mitigate the risk of attack advancements in post-quantum cryptography:

If the security of your system requires breaking the cryptography used today AND breaking one of the new-fangled designs, you’ll always be at least as secure as the stronger algorithm.

Art: Lynx vs Jackalope

Why Is Hybrid Cryptography Controversial?

Despite the risks of greenfield cryptographic algorithms, the NSA has begun recommending a strictly-PQ approach to cryptography and have explicitly stated that they will not require hybrid designs.

Another pushback on hybrid cryptography comes from Uri Blumenthal of MIT’s Lincoln Labs on the IETF CFRG mailing list (the acronym CRQC expands to “Cryptographically-Relevant Quantum Computer”):

Here are the possibilities and their relation to the usefulness of the Hybrid approach.

1. CRQC arrived, Classic hold against classic attacks, PQ algorithms hold – Hybrid is useless.

2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail – Hybrid is useless.

3. CRQC arrived, Classic broken against classic attacks, PQ algorithms hold – Hybrid is useless.

4. CRQC arrived, Classic hold against classic attacks, PQ algorithms broken – Hybrid useless.

5. CRQC doesn’t arrive, Classic hold against classic attacks, PQ algorithms hold – Hybrid is useless.

6. CRQC doesn’t arrive, Classic hold against classic attacks, PQ algorithms broken – Hybrid helps.

7. CRQC doesn’t arrive, Classic broken against classic attacks, PQ algorithms hold – Hybrid is useless.

8. CRQC doesn’t arrive, Classic broken against classic attacks, PQ algorithms broken – Hybrid is useless.

Uri Blumenthal, IETF CFRG mailing list, December 2021 (link)

Why Hybrid Is Actually A Damn Good Idea

Art: Scruff Kerfluff

Uri’s risk analysis is, of course, flawed. And I’m not the first to disagree with him.

First, Uri’s framing sort of implies that each of the 8 possible outputs of these 3 boolean variables are relatively equally likely outcomes.

It’s very tempting to look at this and think, “Wow, that’s a lot of work for something that only helps in 12.5% of possible outcomes!” Uri didn’t explicitly state this assumption, and he might not even believe that, but it is a cognitive trap that emerges in the structure of his argument, so watch your step.

Second, for many candidate algorithms, we’re already in scenario 6 that Uri outlined! It’s not some hypothetical future, it’s the present state of affairs.

To wit: The advances in cryptanalysis on Rainbow don’t totally break it in a practical sense, but they do reduce the security by a devastating margin (which will require significantly larger parameter sets and performance penalties to remedy).

For many post-quantum algorithms, we’re still uncertain about which scenario is most relevant. But since PQ algorithms are being successfully attacked and a quantum computer still hasn’t arrived, and classical algorithms are still holding up fine, it’s very clear that “hybrid helps” is the world we most likely inhabit today, and likely will for many years (until the existence of quantum computers is finally settled).

Finally, even in other scenarios (which are more relevant for other post-quantum algorithms), hybrid doesn’t significantly hurt security. It does carry a minor cost to bandwidth and performance, and it does mean having a larger codebase to review when compared with jettisoning the algorithms we use today, but I’d argue that the existing code is relatively low risk compared to new code.

From what I’ve read, the NSA didn’t make as strong an argument as Uri; they said hybrid would not be required, but didn’t go so far as to attack it.

Hybrid cryptography is a long-term bet that will protect the most users from cryptanalytic advancements, contrasted with strictly-PQ and no-PQ approaches.

Why The Hybrid Controversy Remains Unsettled

Even if we can all agree that hybrid is the way to go, there’s still significant disagreement on exactly how to do it.

Hybrid KEMs

There are two schools of thought on hybrid Key Encapsulation Mechanisms (KEMs):

1. Wrap the post-quantum KEM in the encrypted channel created by the classical KEM.
2. Use both the post-quantum KEM and classical KEM as inputs to a secure KDF, then use a single encrypted channel secured by both.

The first option (layered) has the benefit of making migrations smoother. You can begin with classical cryptography (i.e. ECDHE for TLS ciphersuites), which is what most systems online support today. Then you can do your post-quantum cryptography inside the existing channel to create a post-quantum-secure channel. This also lends toward opportunistic upgrades (which might not be a good idea).

The second option (composite) has the benefit of making the security of your protocol all-or-nothing: You cannot attack the weak now and the strong part later. The session keys you’ll derive require attacking both algorithms in order to get access to the plaintext. Additionally, you only need a single layer. The complexity lies entirely within the handshake, instead of every packet.

Personally, I think composite is a better option for security than layered.

Hybrid Signatures

There are, additionally, two different schools of thought on hybrid digital signature algorithms. However, the difference is more subtle than with KEMs.

1. Require separate classical signatures and post-quantum signatures.
2. Specify a composite mode that combines the two together and treat it as a distinct algorithm.

To better illustrate what this looks like, I outlined what a composite hybrid digital signature algorithm could look like on the CFRG mailing list:

primary_seed := randombytes_buf(64) // store thised25519_seed := hash_sha512256(PREFIX_CLASSICAL || primary_seed)pq_seed := hash_sha512256(PREFIX_POSTQUANTUM || primary_seed)ed25519_keypair := crypto_sign_seed_keypair(ed25519_seed)pq_keypair := pqcrypto_sign_seed_keypair(pq_seed)

Your composite public key would be your Ed25519 public key, followed by your post-quantum public key. Since Ed25519 public keys are always 32 bytes, this is easy to implement securely.

Every composite signature would be an Ed25519 signature concatenated with the post-quantum signature. Since Ed25519 signatures are always 64 bytes, this leads to a predictable signature size relative to the post-quantum signature.

The main motivation for preferring a composite hybrid signature over a detached hybrid signature is to push the hybridization of cryptography lower in the stack so developers don’t have to think about these details. They just select HYBRIDSIG1 or HYBRIDSIG2 in their ciphersuite configuration, and cryptographers get to decide what that means.

TL;DR

Hybrid designs of post-quantum crypto are good, and I think composite hybrid designs make the most sense for both KEMs and signatures.

https://soatok.blog/2022/01/27/the-controversy-surrounding-hybrid-cryptography/

#asymmetricCryptography #classicalCryptography #cryptography #digitalSignatureAlgorithm #hybridCryptography #hybridDesigns #KEM #keyEncapsulationMechanism #NISTPostQuantumCryptographyProject #NISTPQC #postQuantumCryptography

Earlier this week, NIST announced Round 3 of the Post-Quantum Cryptography project and published their rationale for selecting from the Round 2 candidates.

NIST did something clever this time, and Round 3 was separated into two groups: Finalists and Alternative Candidates.

Finalists are algorithms that NIST (and the majority of the cryptographers involved in NIST’s decisionmaking) believe are production-ready and worth standardizing immediately.

Meanwhile, Alternative Candidates are algorithms that NIST believes need a few more years of cryptanalysis and research before feeling confident about, for one reason or another.

I’m sure everyone in cryptography has their own opinions about the Round 3 selection, but I’d like to analyze the Round 3 finalists from a very opinionated, real-world perspective.

I’ll look at the alternative candidates in a future post.

Art by Khia

Judgement Criteria

I will be evaluating Key Encapsulation algorithms based on real world operational requirements–rather than theoretical notions of security–for public key encryption and key encapsulation, namely:

1. Feasibility to integrate with existing transport-layer protocols (TLS, Noise, etc.)
2. Support for offline public-key encryption (a.k.a. “sealing”) APIs in application-layer cryptography.
   This means you can encrypt with an online public key, but decryption requires a secret key that is kept offline and only accessed when needed.

I will be evaluating Digital Signature algorithms based on the following criteria:

1. Statelessness: Can the algorithm be safely used in a virtual machine that gets rolled back?
2. Bandwidth: Are signatures reasonably small?

Some people might object to this criteria, but this post is ultimately my opinion, and those are the criteria I care about the most.

Post-Quantum Key Encapsulation Round 3 Finalists

Classic McEliece

Classic McEliece is based on error-correcting codes.

Classic McEliece has large public keys (ranging from 261120 bytes to 1357824 bytes in the Round 2 submission) but short ciphertexts (128 to 240 bytes). This makes it difficult to implement Classic McEliece in protocols like TLS (since it will require a minimum of 4 TCP packets just to transmit a public key).

Classic McEliece does not have decryption failures, making it suitable for offline public-key encryption. However, the enormous public key may hinder adoption here too.

CRYSTALS-KYBER

CRYSTALS (Cryptographic Suite for Algebraic Lattices) encompasses two proposals: Kyber (key encapsulation) and Dilithium (signatures).

Kyber public keys range from 800 bytes (for Kyber-512) to 1568 bytes (for Kyber-1024) and ciphertexts range from 736 bytes to 1568 bytes, which means that Kyber can be easily used in protocols like TLS.

Kyber decryptions have a failure probability of about 1 in 2^160. While this probability is unlikely to ever occur in the real world, any nonzero failure probability baked into the algorithm does mean that encrypting a symmetric key with Kyber, strictly speaking, can prevent you from decrypting the symmetric key successfully. This makes it difficult to recommend Kyber in confidence for offline-decryption protocols, since there is no opportunity to recover from the (however improbable) error.

(This isn’t an argument that 2^-160 is too high. Any nonzero probability baked into any algorithm is still nonzero, and therefore irks me.)

NTRU

NTRU is another lattice-based scheme, and one of the oldest post-quantum lattice cryptosystems ever developed. (It’s so old that the patents have all expired.)

Like Kyber, NTRU offers small public keys (699 bytes for ntruhps2048509 on the low end, 1230 bytes for ntruhps4096821on the high end), making NTRU suitable for protocols like TLS that require small-ish public keys.

Like Kyber, NTRU boasts a decryption failure rate less often than 1 in 2^100 for all parameter sets. (The precise failure rates are not given in the NTRU specification document.) Strictly speaking, this might never be a practical concern, but it is still technically possible to encrypt something with NTRU that cannot be decrypted. This makes it difficult to recommend NTRU for this use case.

Update (2020-10-06): Paulo Barreto emailed me with a correction: NTRU’s submission for Round 2 boasts zero decryption failures.

SABER

SABER is another lattice-based key encapsulation algorithm. SABER’s security is based on a different problem than Kyber and NTRU. However, SABER gets bonus points for calling its lightweight mode LightSABER and using a lightsaber in their website’s design.

SABER offers small public keys (672 to 1312 bytes) and ciphertexts (736 to 1472 bytes). TLS should have no problem with SABER.

As with the other lattice-based proposals, the decryption failure probability is nonzero (2^-120 to 2^-165 for the SABER variants).

Round 3 Key Encapsulation Finalist Summary

If your only goal for post-quantum cryptography was to design primitives that can be used in online modes like TLS, then any of the lattice based proposals (Kyber, NTRU, SABER) are great.

For offline public-key encryption, all three of those proposals carry a nonzero risk of decryption failure, which can only really be mitigated by encrypting the same session key multiple times and storing multiple ciphertexts. (Update: See below.) This failure risk is already negligible (cosmic rays are more likely), but offline protocols have no recovery mechanism (whereas online protocols can just re-initiate a key exchange and call it a day).

One might argue that the probability is negligible (in fact, most cryptographers agree that a failure probability below 1 in 2^120 isn’t worth thinking about, since it will never happen in the real world), but I contend that a nonzero risk means they cannot be used in sealing APIs for general purpose cryptography libraries, since the developers of that library cannot be responsible for the decryption failure risk calculus for all of its users.

That is to say: In my humble opinion, in order to safely implement offline decryption, the algorithmic failure probability must be zero. Any nonzero algorithmic failure rate makes me grumpy (even if there’s no real-world, practical risk).

You might be tempted to just use Classic McEliece for sealing APIs, but since the public keys are enormous, I don’t see this being an option for constrained environments (i.e. embedded devices).

In short, I think the NIST PQC Round 3 finalists completely missed a use case that’s important to me, but apparently not important to NIST. (Offline decryption with a long-lived keypair.) Here’s hoping one or more of the non-lattice key encapsulation algorithms reaches maturity so we’re not caught in a catch-22.

Update (2020-10-06): I was mistaken about NTRU on two fronts:

1. I had overlooked NTRU HRSS701 (as Bo-Yin Yang points out in the comments section).
2. Round 2 of the NTRU NIST submission has a failure probability of zero (as Paulo Barreto informed me via email).

Given that NTRU is therefore suitable for offline public-key encryption (or, more to the point, offline HPKE), my above complaints about missed use-cases are therefore invalid. (However, for the sake of transparency, I’m only retracting them, not erasing them.)

Post-Quantum Digital Signature Round 3 Finalists

CRYSTALS-DILITHIUM

Yes, that’s really the Dilithium logo.

Dilithium is the signature counterpart to Kyber.

Dilithium is stateless. Public keys range between 1184 and 1760 bytes. Signatures range between 2044 bytes and 3366 bytes.

Nothing to complain about here.

FALCON

FALCON is difficult to implement, but it offers great performance and compact public keys (897 to 1793 bytes) and small signatures (~657 to ~1273 bytes). According to the Falcon website, Falcon-512 is about five times as fast as 2048-bit RSA.

Did I mention it’s stateless?

Rainbow

No, not that kind of Rainbow! Probably. (Art by LindseyVi)

Rainbow is not a lattice-based scheme, in case you were sick of those. Instead it’s multivariate cryptography.

Rainbow public keys are somewhat large (149 KB to 1705.5 KB, although you can get 58.1 KB to 491.9 KB if you use compressed public keys). However, it boasts short signatures (64 bytes to 204 bytes).

Unlike the other schemes, the specification for Rainbow doesn’t spend a lot of time on introducing it in words. Instead, the paper just dives into the algorithm details without explaining “why?”.

Round 3 Digital Signature Finalist Summary

If you’re going to implement Kyber, it makes sense to also use Dilithium for signatures. Otherwise, FALCON’s performance is hard to beat.

Rainbow is interesting but requires large public keys and needs better documentation.

TL;DR

The Round 3 key encapsulation finalists are great for online encryption, but I don’t feel all warm and fuzzy about algorithms that possess an inherent decryption failure probability, which several of them do. McEliece’s enormous key and ciphertext sizes make it less attractive than the lattice-based candidates.

The Round 3 digital signature finalists are solid. I have a slight preference for FALCON but Dilithium looks great. I don’t know enough about Rainbow to evaluate it.

If I had to make any prediction about the PQC selection, it would be (in order of most-to-least likely to be selected, assuming anyone at NIST shares my priorities):

• Key encapsulation
  
  1. NTRU
  2. CRYSTALS-KYBER
  3. SABER
  4. Classical McEliece

  
  

• Digital signatures
  
  1. CRYSTALS-DILITHIUM
  2. FALCON
  3. Rainbow

  
  

(Excluding the alternative candidates, which merit a deeper analysis.)

Header art by Riley.

https://soatok.blog/2020/07/24/a-brief-opinionated-of-nists-post-quantum-cryptography-round-3-candidates/

#asymmetricCryptography #ClassicalMcEliece #cryptography #Dilithium #FALCON #Kyber #lattices #NIST #NTRU #PQC #Rainbow #SABER

Dhole Moments

2020-07-24 17:55:45

Earlier this week, NIST announced Round 3 of the Post-Quantum Cryptography project and published their rationale for selecting from the Round 2 candidates.

NIST did something clever this time, and Round 3 was separated into two groups: Finalists and Alternative Candidates.

Finalists are algorithms that NIST (and the majority of the cryptographers involved in NIST’s decisionmaking) believe are production-ready and worth standardizing immediately.

Meanwhile, Alternative Candidates are algorithms that NIST believes need a few more years of cryptanalysis and research before feeling confident about, for one reason or another.

I’m sure everyone in cryptography has their own opinions about the Round 3 selection, but I’d like to analyze the Round 3 finalists from a very opinionated, real-world perspective.

I’ll look at the alternative candidates in a future post.

Art by Khia

Judgement Criteria

I will be evaluating Key Encapsulation algorithms based on real world operational requirements–rather than theoretical notions of security–for public key encryption and key encapsulation, namely:

1. Feasibility to integrate with existing transport-layer protocols (TLS, Noise, etc.)
2. Support for offline public-key encryption (a.k.a. “sealing”) APIs in application-layer cryptography.
   This means you can encrypt with an online public key, but decryption requires a secret key that is kept offline and only accessed when needed.

I will be evaluating Digital Signature algorithms based on the following criteria:

1. Statelessness: Can the algorithm be safely used in a virtual machine that gets rolled back?
2. Bandwidth: Are signatures reasonably small?

Some people might object to this criteria, but this post is ultimately my opinion, and those are the criteria I care about the most.

Post-Quantum Key Encapsulation Round 3 Finalists

Classic McEliece

Classic McEliece is based on error-correcting codes.

Classic McEliece has large public keys (ranging from 261120 bytes to 1357824 bytes in the Round 2 submission) but short ciphertexts (128 to 240 bytes). This makes it difficult to implement Classic McEliece in protocols like TLS (since it will require a minimum of 4 TCP packets just to transmit a public key).

Classic McEliece does not have decryption failures, making it suitable for offline public-key encryption. However, the enormous public key may hinder adoption here too.

CRYSTALS-KYBER

CRYSTALS (Cryptographic Suite for Algebraic Lattices) encompasses two proposals: Kyber (key encapsulation) and Dilithium (signatures).

Kyber public keys range from 800 bytes (for Kyber-512) to 1568 bytes (for Kyber-1024) and ciphertexts range from 736 bytes to 1568 bytes, which means that Kyber can be easily used in protocols like TLS.

Kyber decryptions have a failure probability of about 1 in 2^160. While this probability is unlikely to ever occur in the real world, any nonzero failure probability baked into the algorithm does mean that encrypting a symmetric key with Kyber, strictly speaking, can prevent you from decrypting the symmetric key successfully. This makes it difficult to recommend Kyber in confidence for offline-decryption protocols, since there is no opportunity to recover from the (however improbable) error.

(This isn’t an argument that 2^-160 is too high. Any nonzero probability baked into any algorithm is still nonzero, and therefore irks me.)

NTRU

NTRU is another lattice-based scheme, and one of the oldest post-quantum lattice cryptosystems ever developed. (It’s so old that the patents have all expired.)

Like Kyber, NTRU offers small public keys (699 bytes for ntruhps2048509 on the low end, 1230 bytes for ntruhps4096821on the high end), making NTRU suitable for protocols like TLS that require small-ish public keys.

Like Kyber, NTRU boasts a decryption failure rate less often than 1 in 2^100 for all parameter sets. (The precise failure rates are not given in the NTRU specification document.) Strictly speaking, this might never be a practical concern, but it is still technically possible to encrypt something with NTRU that cannot be decrypted. This makes it difficult to recommend NTRU for this use case.

Update (2020-10-06): Paulo Barreto emailed me with a correction: NTRU’s submission for Round 2 boasts zero decryption failures.

SABER

SABER is another lattice-based key encapsulation algorithm. SABER’s security is based on a different problem than Kyber and NTRU. However, SABER gets bonus points for calling its lightweight mode LightSABER and using a lightsaber in their website’s design.

SABER offers small public keys (672 to 1312 bytes) and ciphertexts (736 to 1472 bytes). TLS should have no problem with SABER.

As with the other lattice-based proposals, the decryption failure probability is nonzero (2^-120 to 2^-165 for the SABER variants).

Round 3 Key Encapsulation Finalist Summary

If your only goal for post-quantum cryptography was to design primitives that can be used in online modes like TLS, then any of the lattice based proposals (Kyber, NTRU, SABER) are great.

For offline public-key encryption, all three of those proposals carry a nonzero risk of decryption failure, which can only really be mitigated by encrypting the same session key multiple times and storing multiple ciphertexts. (Update: See below.) This failure risk is already negligible (cosmic rays are more likely), but offline protocols have no recovery mechanism (whereas online protocols can just re-initiate a key exchange and call it a day).

One might argue that the probability is negligible (in fact, most cryptographers agree that a failure probability below 1 in 2^120 isn’t worth thinking about, since it will never happen in the real world), but I contend that a nonzero risk means they cannot be used in sealing APIs for general purpose cryptography libraries, since the developers of that library cannot be responsible for the decryption failure risk calculus for all of its users.

That is to say: In my humble opinion, in order to safely implement offline decryption, the algorithmic failure probability must be zero. Any nonzero algorithmic failure rate makes me grumpy (even if there’s no real-world, practical risk).

You might be tempted to just use Classic McEliece for sealing APIs, but since the public keys are enormous, I don’t see this being an option for constrained environments (i.e. embedded devices).

In short, I think the NIST PQC Round 3 finalists completely missed a use case that’s important to me, but apparently not important to NIST. (Offline decryption with a long-lived keypair.) Here’s hoping one or more of the non-lattice key encapsulation algorithms reaches maturity so we’re not caught in a catch-22.

Update (2020-10-06): I was mistaken about NTRU on two fronts:

1. I had overlooked NTRU HRSS701 (as Bo-Yin Yang points out in the comments section).
2. Round 2 of the NTRU NIST submission has a failure probability of zero (as Paulo Barreto informed me via email).

Given that NTRU is therefore suitable for offline public-key encryption (or, more to the point, offline HPKE), my above complaints about missed use-cases are therefore invalid. (However, for the sake of transparency, I’m only retracting them, not erasing them.)

Post-Quantum Digital Signature Round 3 Finalists

CRYSTALS-DILITHIUM

Yes, that’s really the Dilithium logo.

Dilithium is the signature counterpart to Kyber.

Dilithium is stateless. Public keys range between 1184 and 1760 bytes. Signatures range between 2044 bytes and 3366 bytes.

Nothing to complain about here.

FALCON

FALCON is difficult to implement, but it offers great performance and compact public keys (897 to 1793 bytes) and small signatures (~657 to ~1273 bytes). According to the Falcon website, Falcon-512 is about five times as fast as 2048-bit RSA.

Did I mention it’s stateless?

Rainbow

No, not that kind of Rainbow! Probably. (Art by LindseyVi)

Rainbow is not a lattice-based scheme, in case you were sick of those. Instead it’s multivariate cryptography.

Rainbow public keys are somewhat large (149 KB to 1705.5 KB, although you can get 58.1 KB to 491.9 KB if you use compressed public keys). However, it boasts short signatures (64 bytes to 204 bytes).

Unlike the other schemes, the specification for Rainbow doesn’t spend a lot of time on introducing it in words. Instead, the paper just dives into the algorithm details without explaining “why?”.

Round 3 Digital Signature Finalist Summary

If you’re going to implement Kyber, it makes sense to also use Dilithium for signatures. Otherwise, FALCON’s performance is hard to beat.

Rainbow is interesting but requires large public keys and needs better documentation.

TL;DR

The Round 3 key encapsulation finalists are great for online encryption, but I don’t feel all warm and fuzzy about algorithms that possess an inherent decryption failure probability, which several of them do. McEliece’s enormous key and ciphertext sizes make it less attractive than the lattice-based candidates.

The Round 3 digital signature finalists are solid. I have a slight preference for FALCON but Dilithium looks great. I don’t know enough about Rainbow to evaluate it.

If I had to make any prediction about the PQC selection, it would be (in order of most-to-least likely to be selected, assuming anyone at NIST shares my priorities):

• Key encapsulation
  
  1. NTRU
  2. CRYSTALS-KYBER
  3. SABER
  4. Classical McEliece

  
  

• Digital signatures
  
  1. CRYSTALS-DILITHIUM
  2. FALCON
  3. Rainbow

  
  

(Excluding the alternative candidates, which merit a deeper analysis.)

Header art by Riley.

https://soatok.blog/2020/07/24/a-brief-opinionated-of-nists-post-quantum-cryptography-round-3-candidates/

#asymmetricCryptography #ClassicalMcEliece #cryptography #Dilithium #FALCON #Kyber #lattices #NIST #NTRU #PQC #Rainbow #SABER

There are two mental models for designing a cryptosystem that offers end-to-end encryption to all of its users.

The first is the Signal model.

Predicated on Moxie’s notion that the ecosystem is moving, Signal (and similar apps) maintain some modicum of centralized control over the infrastructure and deployment of their app. While there are obvious downsides to this approach, it allows them to quickly roll out ecosystem-wide changes to their encryption protocols without having to deal with third-party clients falling behind.

The other is the federated model, which is embraced by Matrix, XMPP with OMEMO, and other encrypted chat apps and protocols.

This model can be attractive to a lot of people whose primary concern is data sovereignty rather than cryptographic protections. (Most security experts care about both aspects, but we differ in how they rank the two priorities relative to each other.)

As I examined in my criticisms of Matrix and XMPP+OMEMO, they kind of prove Moxie’s point about the ecosystem:

• Two years after the Matrix team deprecated their C implementation of Olm in favor of a Rust library, virtually all of the clients that actually switched (as of the time of my blog post disclosing vulnerabilities in their C library) were either Element, or forks of Element. The rest were still wrapping libolm.
• Most OMEMO libraries are still stuck on version 0.3.0 of the specification, and cannot communicate with XMPP+OMEMO implementations that are on newer versions of the specification.

And this is personally a vexing observation, for two reasons:

1. I don’t like that Moxie’s opinion is evidently more correct when you look at the consequences of each model.
2. I’m planning to develop end-to-end encryption for direct messages on the Fediverse, and don’t want to repeat the mistakes of Matrix and OMEMO.
   (Aside from them mistakenly claiming to be Signal competitors, which I am not doing with my E2EE proposal or any implementations thereof.)

Fortunately, I have a solution to both annoyances that I intend to implement in my end-to-end encryption proposal.

Thus, I’d like to introduce Cryptographic Alacrity to the discussion.

Note: The term “crypto agility” was already coined by people who never learned from the alg=none vulnerability of JSON Web Tokens and think it’s A-okay to negotiate cryptographic primitives at run-time based on attacker-controllable inputs.

Because they got their foolish stink all over that term, I discarded it in favor of coining a new one. I apologize for the marginal increase in cognitive load this decision may cause in the future.

Cryptographic Alacrity

For readers who aren’t already familiar with the word “alacrity” from playing Dungeons & Dragons once upon a time, the Merriam-Webster dictionary defines Alacrity as:

promptness in response : cheerful readiness

Alacrity Definition & Meaning – Merriam Webster

When I describe a cryptography protocol as having “cryptographic alacrity”, I mean there is a built-in mechanism to enforce protocol upgrades in a timely manner, and stragglers (read: non-compliant implementations) will lose the ability to communicate with up-to-date software.

Alacrity must be incorporated into a protocol at its design phase, specified clearly, and then enforced by the community through its protocol library implementations.

The primary difference between Alacrity and Agility is that Alacrity is implemented through protocol versions and a cryptographic mechanism for enforcing implementation freshness across the ecosystem, whereas Agility is about being able to hot-swap cryptographic primitives in response to novel cryptanalysis.

This probably still sounds a bit abstract to some of you.

CMYKat

To best explain what I mean, let’s look at a concrete example. Namely, how I plan on introducing Alacrity to my Fediverse E2EE design, and then enforcing it henceforth.

Alacrity in E2EE for the Fediverse

One level higher in the protocol than bulk message and/or media attachment encryption will be a Key Derivation Function. (Probably HKDF, probably as part of a Double Ratchet protocol or similar. I haven’t specified that layer just yet.)

Each invocation of HKDF will have a hard-coded 256-bit salt particular to the protocol version that is currently being used.

(What most people would think to pass as the salt in HKDF will instead be appended to the info parameter.)

The protocol version will additionally be used in a lot of other places (i.e., domain separation constants), but those are going to be predictable string values.

The salt will not be predictable until the new version is specified. I will likely tie it to the SHA256 hash of a Merkle root of a Federated Public Key Directory instance and the nickname for each protocol version.

Each library will have a small window (probably no more than 3 versions at any time) of acceptable protocol versions.

A new version will be specified, with a brand new KDF salt, every time we need to improve the protocol to address a security risk. Additionally, we will upgrade the protocol version at least once a year, even if no security risks have been found in the latest version of the protocol.

If your favorite client depends on a 4 year old version of the E2EE protocol library, you won’t be able to silently downgrade security for all of your conversation participants. Instead, you will be prevented from talking to most users, due to incompatible cryptography.

Version Deprecation Schedule

Let’s pretend, for the sake of argument, that we launch the first protocol version on January 1, 2025. And that’s when the first clients start to be built atop the libraries that speak the protocols.

Assuming no emergencies occur, after 9 months (i.e., by October 1, 2025), version 2 of the protocol will be specified. Libraries will be updated to support reading (but not sending) messages encrypted with protocol v2.

Then, on January 1, 2026 at midnight UTC–or a UNIX timestamp very close to this, at least–clients will start speaking protocol v2. Other clients can continue to read v1, but they should write v2.

This will occur every year on the same cadence, but with a twist: After clients are permitted to start writing v3, support for reading v1 MUST be removed from the codebase.

This mechanism will hold true even if the protocols are largely the same, aside from tweaked constants.

AJ

What does Alacrity give us?

Alacrity allows third-party open source developers the capability of writing their own software (both clients and servers) without a significant risk of the Matrix and OMEMO problem (i.e., stale software being used years after it should have been deprecated).

By offering a sliding window of acceptable versions and scheduling planned version bumps to be about a year apart, we can minimize the risk of clock skew introducing outages.

Additionally, it provides third-party developers ample opportunity to keep their client software conformant to the specification.

It doesn’t completely eliminate the possibility of stale versions being used in silos. Especially if some developers choose malice. However, anyone who deviates from the herd to form their own cadre of legacy protocol users has deliberately or negligently accepted the compatibility risks.

Can you staple Alacrity onto other end-to-end encryption projects?

Not easily, no.

This is the sort of mechanism that needs to be baked in from day one, and everyone needs to be onboard at the project’s inception.

Retroactively trying to make Matrix, XMPP, OpenPGP, etc. have Cryptographic Alacrity after the horses left the barn is an exercise in futility.

I would like your help introducing Alacrity into my pet project.

I’d love to help, but I’m already busy enough with work and my own projects.

If you’re designing a product that you intend to sell to the public, talk to a cryptography consulting firm. I can point you to several that are reputable, but most of them are pretty good.

If you’re designing something for the open source community, and don’t have the budget to hire professionals, I’ll respond to such inquiries when my time, energy, and emotional bandwidth is available to do so. No promises on a timeline, of course.

AJ

How do you force old versions to get dropped?

You don’t.

The mechanism I mostly care about is forcing new versions get adopted.

Dropping support for older versions is difficult to mechanize. Being actively involved in the community to encourage implementations do this (if for no other reason to reduce risk by deleting dead code) is sufficient.

I am choosing to not make perfect the enemy of good with this proposal.

This isn’t a new idea.

No, it isn’t a new idea. The privacy-focused cryptocurrency, Zcash, has a similar mechanism build into their network upgrades.

It’s wildly successful when federated or decentralized systems adopt such a policy, and actually enforce it.

The only thing that’s novel in this post is the coined term, Cryptographic Alacrity.

Addendum – Questions Asked After This Post Went Live

Art: ScruffKerfluff

What about Linux Distros with slow release cycles?

What about them?!

In my vision of the future, the primary deliverable that users will actually hold will most likely be a Browser Extension, not a binary blob signed by their Linux distro.

They already make exceptions to their glacial release cadences for browsers, so I don’t anticipate whatever release cadence we settle on being a problem in practice.

For people who write clients with desktop software: Debian and Ubuntu let users install PPAs. Anyone who does Node.js development on Linux is familiar with them.

Why 1 year?

It was an example. We could go shorter or longer depending on the needs of the ecosystem.

How will you enforce the removal of old versions if devs don’t comply?

That’s a much lower priority than enforcing the adoption of new versions.

But realistically, sending pull requests to remove old versions would be the first step.

Publicly naming and shaming clients that refuse to drop abandoned protocol versions is always an option for dealing with obstinance.

We could also fingerprint clients that still support the old versions and refuse to connect to them at all, even if there is a version in common, until they update to drop the old version.

That said, I would hope to not need to go that far.

I really don’t want to overindex on this, but people keep asking or trying to send “what about?” comments that touch on this question, so now I’m writing a definitive statement to hopefully quell this unnecessary discourse.

The ubiquitous adoption of newer versions is a much higher priority than the sunsetting of old versions. It should be obvious that getting your users to use the most secure mode available is intrinsically a net-positive.

If your client can negotiate in the most secure mode available (i.e., if we move onto post-quantum cryptography), and your friends’ clients enforce the correct minimum version, it doesn’t really matter so much if your client in particular is non-compliant.

Focusing so much on this aspect is a poor use of time and emotional bandwidth.

Header art also made by AJ.

https://soatok.blog/2024/08/28/introducing-alacrity-to-federated-cryptography/

#cryptographicAgility #cryptographicAlacrity #cryptography #endToEndEncryption #fediverse #Matrix #OMEMO #XMPP

Dhole Moments

2024-08-14 12:00:00

I don’t consider myself exceptional in any regard, but I stumbled upon a few cryptography vulnerabilities in Matrix’s Olm library with so little effort that it was nearly accidental.

It should not be this easy to find these kind of issues in any product people purportedly rely on for private messaging, which many people evangelize incorrectly as a Signal alternative.

Later, I thought I identified an additional vulnerability that would have been much worse, but I was wrong about that one. For the sake of transparency and humility, I’ll also describe that in detail.

This post is organized as follows:

• Disclosure Timeline
• Vulnerabilities in Olm (Technical Details)
• Recommendations
• Background Information
• An Interesting Non-Issue That Looked Critical

I’ve opted to front-load the timeline and vulnerability details to respect the time of busy security professionals.

Please keep in mind that this website is a furry blog, first and foremost, that sometimes happens to cover security and cryptography topics.

Many people have, over the years, assumed the opposite and commented accordingly. The ensuing message board threads are usually is a waste of time and energy for everyone involved. So please adjust your expectations.

Art by Harubaki

If you’re curious, you can learn more here.

Disclosure Timeline

• 2024-05-15: I took a quick look at the Matrix source code. I identified two issues and emailed them to their security@ email address.
  In my email, I specify that I plan to disclose my findings publicly in 90 days (i.e. on August 14), in adherence with industry best practices for coordinated disclosure, unless they request an extension in writing.
• 2024-05-16: I checked something else on a whim and find a third issue, which I also email to their security@ email address.
• 2024-05-17: Matrix security team confirms receipt of my reports.
• 2024-05-17: I follow up with a suspected fourth finding–the most critical of them all. They point out that it is not actually an issue, because I overlooked an important detail in how the code is architected. Mea culpa!
• 2024-05-18: A friend discloses a separate finding with Matrix: Media can be decrypted to multiple valid plaintexts using different keys and Malicious homeservers can trick Element/Schildichat into revealing links in E2EE rooms.
  They instructed the Matrix developers to consult with me if they needed cryptography guidance. I never heard from them on this externally reported issue.
• 2024-07-12: I shared this blog post draft with the Matrix security team while reminding them of the public disclosure date.
• 2024-07-31: Matrix pushes a commit that announces that libolm is deprecated.
• 2024-07-31: I email the Matrix security team asking if they plan to fix the reported issues (and if not, if there’s any other reason I should withhold publication).
• 2024-07-31: Matrix confirms they will not fix these issues (due to its now deprecated status), but ask that I withhold publication until the 14th as originally discussed.
• 2024-08-14: This blog post is publicly disclosed to the Internet.
• 2024-08-14: The lead Matrix dev claims they already knew about these issues, and, in fact, knowingly shipped cryptography code that was vulnerable to side-channel attacks for years. See Addendum.
• 2024-08-23: MITRE has assigned CVE IDs to these three findings.

Vulnerabilities in Olm

I identified the following issues with Olm through a quick skim of their source code on Gitlab:

1. AES implementation is vulnerable to cache-timing attacks
2. Ed25519 signatures are malleable
3. Timing leakage in base64 decoding of private key material

This is sorted by the order in which they were discovered, rather than severity.

AES implementation is vulnerable to cache-timing attacks

a.k.a. CVE-2024-45191

Olm ships a pure-software implementation of AES, rather than leveraging hardware acceleration.

// Substitutes a word using the AES S-Box.WORD SubWord(WORD word){unsigned int result;result = (int)aes_sbox[(word >> 4) & 0x0000000F][word & 0x0000000F];result += (int)aes_sbox[(word >> 12) & 0x0000000F][(word >> 8) & 0x0000000F] << 8;result += (int)aes_sbox[(word >> 20) & 0x0000000F][(word >> 16) & 0x0000000F] << 16;result += (int)aes_sbox[(word >> 28) & 0x0000000F][(word >> 24) & 0x0000000F] << 24;return(result);}

The code in question is called from this code, which is in turn used to actually encrypt messages.

Software implementations of AES that use a look-up table for the SubWord step of the algorithm are famously susceptible to cache-timing attacks.

This kind of vulnerability in software AES was previously used to extract a secret key from OpenSSL and dm-crypt in about 65 milliseconds. Both papers were published in 2005.

A general rule in cryptography is, “attacks only get better; they never get worse“.

As of 2009, you could remotely detect a timing difference of about 15 microseconds over the Internet with under 50,000 samples. Side-channel exploits are generally statistical in nature, so such a sample size is generally not a significant mitigation.

How is this code actually vulnerable?

In the above code snippet, the vulnerability occurs in
aes_sbox[/* ... */][/* ... */].

Due to the details of how the AES block cipher works, the input variable (word) is a sensitive value.

Software written this way allows attackers to detect whether or not a specific value was present in one of the processor’s caches.

To state the obvious: Cache hits are faster than cache misses. This creates an observable timing difference.

Such a timing leak allows the attacker to learn the value that was actually stored in said cache. You can directly learn this from other processes on the same hardware, but it’s also observable over the Internet (with some jitter) through the normal operation of vulnerable software.

See also: cryptocoding’s description for table look-ups indexed by secret data.

How to mitigate this cryptographic side-channel

The correct way to solve this problem is to use hardware accelerated AES, which uses distinct processor features to implement the AES round function and side-steps any cache-timing shenanigans with the S-box.

Not only is this more secure, but it’s faster and uses less energy too!

If you’re also targeting devices that don’t have hardware acceleration available, you should first use hardware acceleration where possible, but then fallback to a bitsliced implementation such as the one in Thomas Pornin’s BearSSL.

See also: the BearSSL documentation for constant-time AES.

Art by AJ

Ed25519 signatures are malleable

a.k.a. CVE-2024-45193

Ed25519 libraries come in various levels of quality regarding signature validation criteria; much to the chagrin of cryptography engineers everywhere. One of those validation criteria involves signature malleability.

Signature malleability usually isn’t a big deal for most protocols, until suddenly you discover a use case where it is. If it matters, that usually that means you’re doing something with cryptocurrency.

Briefly, if your signatures are malleable, that means you can take an existing valid signature for a given message and public key, and generate a second valid signature for the same message. The utility of this flexibility is limited, and the impact depends a lot on how you’re using signatures and what properties you hope to get out of them.

For ECDSA, this means that for a given signature , a second signature is also possible (where is the order of the elliptic curve group you’re working with).

Matrix uses Ed25519, whose malleability is demonstrated between and .

This is trivially possible because S is implicitly reduced modulo the order of the curve, , which is a 253-bit number (0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed) and S is encoded as a 256-bit number.

The Ed25519 library used within Olm does not ensure that , thus signatures are malleable. You can verify this yourself by looking at the Ed25519 verification code.

int ed25519_verify(const unsigned char *signature, const unsigned char *message, size_t message_len, const unsigned char *public_key) { unsigned char h[64]; unsigned char checker[32]; sha512_context hash; ge_p3 A; ge_p2 R; if (signature[63] & 224) { return 0; } if (ge_frombytes_negate_vartime(&A, public_key) != 0) { return 0; } sha512_init(&hash); sha512_update(&hash, signature, 32); sha512_update(&hash, public_key, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, h); sc_reduce(h); ge_double_scalarmult_vartime(&R, h, &A, signature + 32); ge_tobytes(checker, &R); if (!consttime_equal(checker, signature)) { return 0; } return 1;}

This is almost certainly a no-impact finding (or low-impact at worst), but still an annoying one to see in 2024.

If you’d like to learn more, this page is a fun demo of Ed25519 malleability.

To mitigate this, I recommend implementing these checks from libsodium.

Art: CMYKat

Timing leakage in base64 decoding of private key material

a.k.a. CVE-2024-45192

If you weren’t already tired of cache-timing attacks based on table look-ups from AES, the Matrix base64 code is also susceptible to the same implementation flaw.

while (pos != end) { unsigned value = DECODE_BASE64[pos[0] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[1] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[2] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[3] & 0x7F]; pos += 4; output[2] = value; value >>= 8; output[1] = value; value >>= 8; output[0] = value; output += 3;}

The base64 decoding function in question is used to load the group session key, which means the attack published in this paper almost certainly applies.

How would you mitigate this leakage?

Steve Thomas (one of the judges of the Password Hashing Competition, among other noteworthy contributions) wrote some open source code a while back that implements base64 encoding routines in constant-time.

The real interesting part is how it avoids a table look-up by using arithmetic (from this file):

// Base64 character set:// [A-Z] [a-z] [0-9] + /// 0x41-0x5a, 0x61-0x7a, 0x30-0x39, 0x2b, 0x2finline int base64Decode6Bits(char src){int ch = (unsigned char) src;int ret = -1;// if (ch > 0x40 && ch < 0x5b) ret += ch - 0x41 + 1; // -64ret += (((0x40 - ch) & (ch - 0x5b)) >> 8) & (ch - 64);// if (ch > 0x60 && ch < 0x7b) ret += ch - 0x61 + 26 + 1; // -70ret += (((0x60 - ch) & (ch - 0x7b)) >> 8) & (ch - 70);// if (ch > 0x2f && ch < 0x3a) ret += ch - 0x30 + 52 + 1; // 5ret += (((0x2f - ch) & (ch - 0x3a)) >> 8) & (ch + 5);// if (ch == 0x2b) ret += 62 + 1;ret += (((0x2a - ch) & (ch - 0x2c)) >> 8) & 63;// if (ch == 0x2f) ret += 63 + 1;ret += (((0x2e - ch) & (ch - 0x30)) >> 8) & 64;return ret;}

Any C library that handles base64 codecs for private key material should use a similar implementation. It’s fine to have a faster base64 implementation for non-secret data.

Worth noting: Libsodium also provides a reasonable Base64 codec.

Recommendations

These issues are not fixed in libolm.

Instead of fixing libolm, the Matrix team recommends all Matrix clients adopt vodozemac.

I can’t speak to the security of vodozemac.

Art: CMYKat

But I can speak against the security of libolm, so moving to vodozemac is probably a good idea. It was audited by Least Authority at one point, so it’s probably fine.

Most Matrix clients that still depended on libolm should treat this blog as public 0day, unless the Matrix security team already notified you about these issues.

Background Information

If you’re curious about the backstory and context of these findings, read on.

Otherwise, feel free to skip this section. It’s not pertinent to most audiences. The people that need to read it already know who they are.

End-to-end encryption is one of the topics within cryptography that I find myself often writing about.

In 2020, I wrote a blog post covering end-to-end encryption for application developers. This was published several months after another blog I wrote covering gripes with AES-GCM, which included a shallow analysis of how Signal uses the algorithm for local storage.

In 2021, I published weaknesses in another so-called private messaging app called Threema.

In 2022, after Elon Musk took over Twitter, I joined the Fediverse and sought to build end-to-end encryption support for direct messages into ActivityPub, starting with a specification. Work on this effort was stalled while trying to solve Public Key distribution in a federated environment (which I hope to pick up soon, but I digress).

Earlier this year, the Telegram CEO started fearmongering about Signal with assistance from Elon Musk, so I wrote a blog post urging the furry fandom to move away from Telegram and start using Signal more. As I had demonstrated years prior, I was familiar with Signal’s code and felt it was a good recommendation for security purposes (even if its user experience needs significant work).

I thought that would be a nice, self-contained blog post. Some might listen, most would ignore it, but I could move on with my life.

I was mistaken about that last point.

Art by AJ

An overwhelming number of people took it upon themselves to recommend or inquire about Matrix, which prompted me to hastily scribble down my opinion on Matrix so that I might copy/paste a link around and save myself a lot of headache.

Just when I thought the firehose was manageable and I could move onto other topics, one of the Matrix developers responded to my opinion post.

Thus, I decided to briefly look at their source code and see if any major or obvious cryptography issues would fall out of a shallow visual scan.

Since you’re reading this post, you already know how that ended.

Credit: CMYKat

Since the first draft of this blog post was penned, I also outlined what I mean when I say an encrypted messaging app is a Signal competitor or not, and published my opinion on XMPP+OMEMO (which people also recommend for private messaging).

Why mention all this?

Because it’s important to know that I have not audited the Olm or Megolm codebases, nor even glanced at their new Rust codebase.

The fact is, I never intended to study Matrix. I was annoyed into looking at it in the first place.

My opinion of their project was already calcified by the previously discovered practically-exploitable cryptographic vulnerabilities in Matrix in 2022.

The bugs described above are the sort of thing I mentally scan for when I first look at a project just to get a feel for the maturity of the codebase. I do this with the expectation (hope, really) of not finding anything at all.

(If you want two specific projects that I’ve subjected to a similar treatment, and failed to discover anything interesting in: Signal and WireGuard. These two set the bar for cryptographic designs.)

It’s absolutely bonkers that an AES cache timing vulnerability was present in their code in 2024.

It’s even worse when you remember that I was inundated with Matrix evangelism in response to recommending furries use Signal.

I’m a little outraged because of how irresponsible this is, in context.

It’s so bad that I didn’t even need to clone their git repository, let alone run basic static analysis tools locally.

So if you take nothing else away from this blog post, let it be this:

There is roughly a 0% chance that I got extremely lucky in my mental grep and found the only cryptography implementation flaws in their source code. I barely tried at all and found these issues.

I would bet money on there being more bugs or design flaws that I didn’t find, because this discovery was the result of an extremely half-assed effort to blow off steam.

Wasn’t libolm deprecated in May 2022?

The Matrix developers like to insist that their new Rust hotness “vodozemac” is what people should be using today.

I haven’t looked at vodozemac at all, but let’s pretend, for the sake of argument, that its cryptography is actually secure.

(This is very likely if they turn out to be using RustCrypto for their primitives, but I don’t have the time or energy for that nerd snipe, so I’m not going to look. Least Authority did audit their Rust library, for what it’s worth, and Least Authority isn’t clownshoes.)

It’s been more than 2 years since they released vodozemac. What does the ecosystem penetration for this new library look like, in practice?

A quick survey of the various Matrix clients on GitHub says that libolm is still the most widely used cryptography implementation in the Matrix ecosystem (as of this writing):

Matrix Client	Cryptography Backend
https://github.com/tulir/gomuks	libolm (1, 2)
https://github.com/niochat/nio	libolm (1, 2)
https://github.com/ulyssa/iamb	vodozemac (1, 2)
https://github.com/mirukana/mirage	libolm (1)
https://github.com/Pony-House/Client	libolm (1)
https://github.com/MTRNord/cetirizine	vodozemac (1)
https://github.com/nadams/go-matrixcli	none
https://github.com/mustang-im/mustang	libolm (1)
https://github.com/marekvospel/libretrix	libolm (1)
https://github.com/yusdacra/icy_matrix	none
https://github.com/ierho/element	libolm (through the python SDK)
https://github.com/mtorials/cordless	none
https://github.com/hwipl/nuqql-matrixd	libolm (through the python SDK)
https://github.com/maxkratz/element-web	vodozemac (1, 2, 3, 4)
https://github.com/asozialesnetzwerk/riot	libolm (wasm file)
https://github.com/NotAlexNoyle/Versi	libolm (1, 2)

3 of the 16 clients surveyed use the new vodozemac library. 10 still use libolm, and 3 don’t appear to implement end-to-end encryption at all.

If we only focus on clients that support E2EE, vodozemac has successfully been adopted by 19% of the open source Matrix clients on GitHub.

I deliberately excluded any repositories that were archived or clearly marked as “old” or “legacy” software, because including those would artificially inflate the representation of libolm. It would make for a more compelling narrative to do so, but I’m not trying to be persuasive here.

Deprecation policies are a beautiful lie. The impact of a vulnerability in Olm or Megolm is still far-reaching, and should be taken seriously by the Matrix community.

Worth calling out: this quick survey, which is based on a GitHub Topic, certainly misses other implementations. Both FluffyChat and Cinny, which were not tagged with this GitHub Topic, depend a language-specific Olm binding.

These bindings in turn wrap libolm rather than the Rust replacement, vodozemac.

But the official clients…

I thought the whole point of choosing Matrix over something like Signal is to be federated, and run your own third-party clients?

If we’re going to insist that everyone should be using Element if they want to be secure, that defeats the entire marketing point about third-party clients that Matrix evangelists cite when they decry Signal’s centralization.

So I really don’t want to hear it.

CMYKat

An Interesting Non-Issue That Looked Critical

As I mentioned in the timeline at the top, I thought I found a fourth issue with Matrix’s codebase. Had I been correct, this would have been a critical severity finding that the entire Matrix ecosystem would need to melt down to remediate.

Fortunately for everyone, I made a mistake, and there is no fourth vulnerability after all.

However, I thought it would be interesting to write about what I thought I found, the impact it would have had if it were real, and why I believed it to be an issue.

Let’s start with the code in question:

void ed25519_sign(unsigned char *signature, const unsigned char *message, size_t message_len, const unsigned char *public_key, const unsigned char *private_key) { sha512_context hash; unsigned char hram[64]; unsigned char r[64]; ge_p3 R; sha512_init(&hash); sha512_update(&hash, private_key + 32, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, r); sc_reduce(r); ge_scalarmult_base(&R, r); ge_p3_tobytes(signature, &R); sha512_init(&hash); sha512_update(&hash, signature, 32); sha512_update(&hash, public_key, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, hram); sc_reduce(hram); sc_muladd(signature + 32, hram, private_key, r);}

The highlighted segment is doing pointer arithmetic. This means it’s reading 32 bytes, starting from the 32nd byte in private_key.

What’s actually happening here is: private_key is the SHA512 hash of a 256-bit seed. If you look at the function prototype, you’ll notice that public_key is a separate input.

Virtually every other Ed25519 implementation I’ve ever looked at before expected users to provide a 32 byte seed followed by the public key as a single input.

This led me to believe that this private_key + 32 pointer arithmetic was actually using the public key for calculating r.

The variable r (not to be confused with big R) generated via the first SHA512 is the nonce for a given signature, it must remain secret for Ed25519 to remain secure.

If r is known to an attacker, you can do some arithmetic to recover the secret key from a single signature.

Because I had mistakenly believed that r was calculated from the SHA512 of only public inputs (the public key and message), which I must emphasize isn’t correct, I had falsely concluded that any previously intercepted signature could be used to steal user’s private keys.

Credit: CMYKat

But because private_key was actually the full SHA512 hash of the seed, rather than the seed concatenated with the public key, this pointer arithmetic did NOT use the public key for the calculation of r, so this vulnerability does not exist.

If the code did what I thought it did, however, this would have been a complete fucking disaster for the Matrix ecosystem. Any previously intercepted message would have allowed an attacker to recover a user’s secret key and impersonate them. It wouldn’t be enough to fix the code; every key in the ecosystem would need to be revoked and rotated.

Whew!

I’m happy to be wrong about this one, because that outcome is a headache nobody wants.

So no action is needed, right?

Well, maybe.

Matrix’s library was not vulnerable, but I honestly wouldn’t put it past software developers at large to somehow, somewhere, use the public key (rather than a secret value) to calculate the EdDSA signature nonces as described in the previous section.

To that end, I would like to propose a test vector be added to the Wycheproof test suite to catch any EdDSA implementation that misuses the public key in this way.

Then, if someone else screws up their Ed25519 implementation in the exact way I thought Matrix was, the Wycheproof tests will catch it.

For example, here’s a vulnerable test input for Ed25519:

{ "should-fail": true, "secret-key": "d1d0ef849f9ec88b4713878442aeebca5c7a43e18883265f7f864a8eaaa56c1ef3dbb3b71132206b81f0f3782c8df417524463d2daa8a7c458775c9af725b3fd", "public-key": "f3dbb3b71132206b81f0f3782c8df417524463d2daa8a7c458775c9af725b3fd", "message": "Test message", "signature": "ffc39da0ce356efb49eb0c08ed0d48a1cadddf17e34f921a8d2732a33b980f4ae32d6f5937a5ed25e03a998e4c4f5910c931b31416e143965e6ce85b0ea93c09"}

A similar test vector would also be worth creating for Ed448, but the only real users of Ed448 were the authors of the xz backdoor, so I didn’t bother with that.

(None of the Project Wycheproof maintainers knew this suggestion is coming, by the way, because I was respecting the terms of the coordinated disclosure.)

Closing Thoughts

Despite finding cryptography implementation flaws in Matric’s Olm library, my personal opinion on Matrix remains largely unchanged from 2022. I had already assumed it would not meet my bar for security.

Cryptography engineering is difficult because the vulnerabilities you’re usually dealing with are extremely subtle. (Here’s an unrelated example if you’re not convinced of this general observation.) As SwiftOnSecurity once wrote:

https://twitter.com/SwiftOnSecurity/status/832058185049579524

The people that developed Olm and Megolm has not proven themselves ready to build a Signal competitor. In balance, most teams are not qualified to do so.

I really wish the Matrix evangelists would accept this and stop trying to cram Matrix down other people’s throats when they’re talking about problems with other platforms entirely.

More important for the communities of messaging apps:

You don’t need to be a Signal competitor. Having E2EE is a good thing on its own merits, and really should be table stakes for any social application in 2024.

It’s only when people try to advertise their apps as a Signal alternative (or try to recommend it instead of Signal), and offer less security, that I take offense.

Just be your own thing.

My work-in-progress proposal to bring end-to-end encryption to the Fediverse doesn’t aim to compete with Signal. It’s just meant to improve privacy, which is a good thing to do on its own merits.

If I never hear Matrix evangelism again after today, it would be far too soon.

If anyone feels like I’m picking on Matrix, don’t worry: I have far worse things to say about Telegram, Threema, XMPP+OMEMO, Tox, and a myriad other projects that are hungry for Signal’s market share but don’t measure up from a cryptographic security perspective.

If Signal fucked up as bad as these projects, my criticism of Signal would be equally harsh. (And remember, I have looked at Signal before.)

Addendum (2024-08-14)

One of the lead Matrix devs posted a comment on Hacker News after this blog post went live that I will duplicate here:

the author literally picked random projects from github tagged as matrix, without considering their prevalence or whether they are actually maintained etc.

if you actually look at % of impacted clients, it’s tiny.

meanwhile, it is very unclear that any sidechannel attack on a libolm based client is practical over the network (which is why we didn’t fix this years ago). After all, the limited primitives are commented on in the readme and https://github.com/matrix-org/olm/issues/3 since day 1.

So the Matrix developers already knew about these vulnerabilities, but deliberately didn’t fix them, for years.

Congratulations, you’ve changed my stance. It used to be “I don’t consider Matrix a Signal alternative and they’ve had some embarrassing and impactful crypto bugs but otherwise I don’t care”. Now it’s a stronger stance:

Don’t use Matrix.

I had incorrectly assumed ignorance, when it was in fact negligence.

There’s no reasonable world in which anyone should trust the developers of cryptographic software (i.e., libolm) that deliberately ships with side-channels for years, knowing they’re present, and never bother to fix them.

This is fucking clownshoes.

https://soatok.blog/2024/08/14/security-issues-in-matrixs-olm-library/

#crypto #cryptography #endToEndEncryption #Matrix #sideChannels #vuln

Earlier this year, I wrote about planned effort to design a federated Key Transparency proposal.

The end goal for this work was constrained to building end-to-end encryption into a new type of Direct Message on the Fediverse, with other protocols and services being a stretch goal rather than its primary purpose.

The ideal situation is to enable developers to write code that looks as simple as this:

async function initialize(message, recipient) { const bundle = await fediverse.getSignedPreKeyBundle(recipient); // This also checks the inclusion proof and witness cosigs: const pubKey = await directory.fetch(recipient, bundle.keyId); if (!await pubKey.verify(bundle)) { throw new Error('Invalid signature or bundle'); } const session = await e2ee.beginSession(bundle); return session.send(message);}initialize("OwO what's this?", "soatok@furry.engineer") .then(async (session) => { /* ... */ });

And then have secure end-to-end encryption such that only a trusted public key for the intended recipient can decrypt.

Work on the specification for the Public Key Directory component has recently started. A few things have changed since my last blog post on the topic. I’ve also gotten a lot of similar questions that wouldn’t be appropriate to try to answer within the specification itself.

Original art: CMYKat, poorly edited by myself

The Big Picture

This section is written mostly for anyone who hasn’t paid attention to my other writing on this project.

This is how I believe this project will develop in the immediate future.

1. Public Key Directory (PKD)
   
   • Specification (WIP)
   • Reference Implementation (Not Started)
   • Client-Side SDKs (Not Started)
     
     • Go
     • Ruby
     • PHP
     • TypeScript

     
     

   
   

2. End-to-End Encryption for the Fediverse (FediE2EE)
   
   • Specification (WIP)
     
     • Client-Side Secret Key Management
     • Federated Public Key Infrastructure (See: PKD)
     • Asynchronous Forward-Secure Ratcheting Protocol + Group Key Agreement
     • Symmetric-Key Authenticated Encryption

     
     

   • Reference Implementations (Not Started)
     
     • Go
     • Ruby
     • PHP
     • TypeScript

     
     

   
   

3. Fediverse Instance Patches to Support E2EE
   
   • Mastodon
   • ?????

   
   

4. Client-Side Software
   
   • ?????

   
   

5. PKD Extensions
   
   • age v1 public keys

   
   

Once the PKD complete is complete, there’s nothing stopping other people from defining their own PKD extensions and building on top of our design to add Key Transparency to their own protocols.

My focus, once we have a solid specification and reference implementation, is going to shift towards building FediE2EE.

I will not, however, be working on client-side software unless no one else expresses interest.

The reason for my tentative recusal is simple: I absolutely suck at user interface design, and you’ll probably hate whatever I can cobble together. I am many things, but an artist is not one of them.

You don’t want me designing UIs.
Art: CMYKat

To that end, my final deliverable in this project will be open source libraries (and accompanying guidance for using said libraries) than user experience experts can glue into their own clients.

That said, the only client-side software that should exist are browser extensions, desktop clients, and mobile apps.

I strongly discourage anyone from trying to deploy any code that touches secret keys to a traditional web application, or JavaScript running inside of a WebView.

I’m ambivalent on Electron. It’s better than redownloading the code from a server and running it blindly every page load, but it’s not highly regarded by security professionals.

Decisions Made

The most important topic to cover is design decisions I’ve made with my specification that will shape the evolution of this project.

Account Recovery

The current draft of the specification includes two Protocol Message types, BurnDown and Fireproof, which warrant further examination.

BurnDown is simple in concept: It revokes all of a particular user’s public keys and auxiliary data records. If you have no currently-trusted public keys, you are permitted to push a self-signed AddKey message.

A not-so-subtle detail of BurnDown that everyone should pay attention to is that the instance admin can issue them on behalf of other users hosted on that server.

CMYKat

If you aren’t comfortable with your admin being able to issue a BurnDown at any time, that’s where Fireproof comes in: It allows you to opt out of this capability entirely.

Fireproof is a double-edged sword. It protects you from malicious admins, but it prevents you from ever recovering your account if you lose access to all of your secret keys.

The most important decision I made here is: Fireproof is an opt-in protection, which (as of the current draft) has no “undo”. (I’m considering allowing an “undo” if it makes sense to ever do so. Tell me what you think!)

It’s often said that security at the expense of usability comes at the expense of security. Account recovery mechanisms are, necessarily, always some kind of a backdoor.

Conversely, defaults matter to security. Allowing BurnDown messages be issued by default, from a specification perspective, implies most users will not issue a Fireproof message. (Client software may counteract this by prompting users with a choice when they first enroll, without a default setting, but I digress.)

I believe this choice is the best of all possible options, but you’re certainly welcome to disagree. It’s important to me that I be very loudly transparent about this decision.

No ECDSA Support

I had floated the idea of supporting NIST P-384 in my initial blog post.

Ultimately, there is no real incentive to do so, considering Ed25519 is now in FIPS 186-5 (which has been a standard for 18 months now).

And since we’re already using Ed25519, that satisfies any hypothetical FIPS use-case, should any governments choose to use my design for anything.

Thus, there will be no NIST P-384 support in the Public Key Directory project.

Art: AJ

Right To Be Forgotten

Key Transparency involves creating a global, immutable history. The Right To Be Forgotten enshrined in the EU’s GDPR law is fundamentally incompatible with the security goals of key transparency.

What this means is that, if I just shrugged and plugged Actor IDs and Public Keys into a hash function and committed that hash to a Merkle tree, then, years later, a malicious troll demands their data be removed in accordance with the GDPR, it immediately becomes a catch-22.

Do you comply with the asserted right and break the history and provable security of your transparency ledger? Or do you risk legal peril for noncompliance?

When I first noodled over this, a few people said, “But you’re not in the EU. Why do you care?”

And, like, some of the people that will want to use this design one day are in the EU. Some of them may want to run their own Public Key Directory instances. I want them to have a good time with it. Is that so strange?

There is a way to get both properties without sacrificing the universal consistency of a single Merkle tree, but it relies on untested legal theory.

MarleyTanuki

In short, what you need to do is:

1. Client-side: Encrypt the sensitive fields, then send the ciphertext and the ephemeral key to the Directory.
2. The Directory will commit to the ciphertext, not the plaintext, and hold onto the keys in order to decrypt records on-the-fly.
3. When a data erasure request comes in by an EU citizen asserting their right to be forgotten, erase the key to render the data irrecoverable.

This constitutes a forceful BurnDown with amnesia.

Does This Introduce Any Specific Risks?

This works in principle, but a couple of things need to hold true in order to maintain the integrity of the transparency log.

1. You need to use a committing authenticated encryption mode.
   Without this property, it’s possible to swap one key for another (rather than simply erasing it) and get a valid plaintext for the (ciphertext, tag) committed in the ledger.

   This protects the Directory from a malicious user that later gets privileged access and manipulates stored keys.

2. You need a plaintext commitment that is independent of the key. In addition to key-independence, it needs to be difficult to brute force, and you can’t have additional randomness (i.e., salts) added that could be changed after-the-fact to produce a “valid” commitment for another plaintext.
   This protects users from a Directory that lies about which plaintext a particular ciphertext decrypts to.

This is currently specified as follows:

1. Encryption is AES-256-CTR then HMAC-SHA512, Encrypt-then-MAC.
2. The authentication tag covers a random value used for subkey derivation, as well as a Plaintext Commitment (Q).
3. The Plaintext Commitment (Q) is derived from Argon2id and HMAC of the plaintext. There are some subtle detains with how the Argon2id salt is derived, and why specific parameters were chosen the way they are, but this is covered in the specification document.

I had considered using Zero Knowledge Proofs here, but the current HMAC + Argon2 approach solves the problem securely without needing to study ZKDocs (and its supporting material) for hours.

Does This Give Us Compliance?

If we assume that “crypto shredding” is a valid technique for complying with data erasure demands, this lets us honor those requests while ensuring independent third parties can maintain a consistent view of the state of the transparency log.

It is worth repeating: This is not based on a tested legal theory. It is not legal advice. It is a best effort, good faith attempt to engineer a solution that would adhere to the “spirit of the law” as interpreted by an American furry with no academic or legal credentials from any country.

That being said, page 75 of this report about distributed ledgers and GDPR implies it’s not an entirely unfounded hypothesis.

Frequently Asked Questions

I’ve been asked a lot of similar questions since I started this project. This is a good a place as any to answer some of them.

Have you talked with ____?

Short answer: No, I haven’t.

Longer answer: My goal is simply to build a specification, then an implementation, that allows end-to-end encryption on the Fediverse.

No part of that sentence implies getting anyone else’s permission, or compromising on my security decisions in order to meet a competing concern.

For example, there’s always pressure from the open source community to support RSA keys, or to interoperate with other software (i.e., Matrix).

Those are non-goals of mine.

Should the ActivityPub authors or Mastodon developers decide differently from me, I wouldn’t want to sign off on their protocol design just because it appeases someone else.

I also don’t have any sort of requirement that what I specify and build becomes “standardized” in any meaningful way.

So, no, I haven’t talked with any of them yet. I also don’t plan to until the specifications and reference implementations are closer to maturity.

And even then, the message I have in mind for when that time comes looks something like this:

Hiya,

I’m building my own end-to-end encryption design for the Fediverse. Here’s the specification, here’s a reference implementation. (Links go here.)

[If applicable: I see you accepted a grant to build something similar.]

Please feel free to reuse whatever you deem useful (if anything) of my work in your own designs. I’m not interested in changing mine.

If you’d like to just adopt what I’ve already built, that’s fine too.

Soatok

I don’t want a deep involvement in anyone else’s political or social mess. I don’t want any of their grant money either, for that matter.

I just want to make security and privacy possible, to help queer people decide when, where, and how they selectively reveal themselves to others.

That said, if the W3C grant recipients want to look at the work I’m doing, they can consider it licensed under public domain, ISC, CC0, WTFPL, or whatever license is easiest for their lawyers to digest. I literally do not give a shit about intellectual property with this project. Go wild.

What if no one steps up to build client software?

Then, as a last resort, I will build something myself. Most likely, a browser extension.

It will probably be ugly, but lightweight, as I am deathly allergic to React Native, NextJS, and other front-end development frameworks.

How can I contribute?

The GitHub repository for the Public Key Directory spec is located here, if you’d like to read and/or suggest improvements to the specification.

As mentioned in my previous blog post on this topic, there is a Signal group for meta-discussion. If you are interested in writing code, that would be the best place to hang out.

What about money? Although my Ko-Fi isn’t difficult to locate, nor hard to guess, I’m not soliciting any financial contributions for this project. It isn’t costing me anything to design or build, presently.

If you represent a company that focuses on cryptography development or software assurance consulting, I may be interested in talking at some point about getting the designs reviewed and implementations audited by professionals. However, we’re a long way from that right now.

Do you have a timeline in mind?

Somewhat, yeah.

I’d like to have version 0.1 of the specification tagged by the end of September 2024.

If I have the time to stick to that timeline, I intend to start working on the reference implementation and client SDKs in a few languages. This is when software developers’ contributions will begin to be the most welcomed.

I can’t really project a timeline beyond that, today.

In addition to building a reference implementation, I would like to pursue formal verification for my protocol design. This allows us to be confident in the correctness and security of the protocol as specified. I cannot provide even a rough estimate for how long that will take to complete.

Once this Public Key Directory project is in a good place, however, my focus will be shifting back towards specifying end-to-end encryption for the Fediverse. Because that’s why I’m doing all this in the first place.

AJ

https://soatok.blog/2024/08/21/federated-key-transparency-project-update/

#crypto #cryptography #OnlinePrivacy #symmetricCryptography

Dhole Moments

2024-06-06 05:37:50

In late 2022, I blogged about the work needed to develop a specification for end-to-end encryption for the fediverse. I sketched out some of the key management components on GitHub, and then the public work abruptly stalled.

A few of you have wondered what’s the deal with that.

This post covers why this effort stalled, what I’m proposing we do next.

What’s The Hold Up?

The “easy” (relatively speaking) parts of the problem are as follows:

1. Secret key management. (This is sketched out already, and provides multiple mechanisms for managing secret key material. Yay!)
2. Bulk encryption of messages and media. (I’ve done a lot of work in this space over the years, so it’s an area I’m deeply familiar with. When we get to this part, it will be almost trivial. I’m not worried about it at all.)
3. Forward-secure ratcheting / authenticated key exchange / group key agreement. (RFC 9420 is a great starting point.)

That is to say, managing secret keys, using secret keys, and deriving shared secret keys are all in the “easy” bucket.

The hard part? Public key management.

CMYKat made this

Why is Public Key Management Hard?

In a centralized service (think: Twitter, Facebook, etc.), this is actually much easier to build: Shove your public keys into a database, and design your client-side software to trust whatever public key your server gives them. Bob’s your uncle, pack it up and go home.

Unfortunately, it’s kind of stupid to build anything that way.

If you explicitly trust the server, the server could provide the wrong public key (i.e., one for which the server knows the corresponding secret key) and you’ll be none the wiser. This makes it trivial for the server to intercept and read your messages.

If your users are trusting you regardless, they’re probably just as happy if you don’t encrypt at the endpoint at all (beyond using TLS, but transport encryption is table stakes for any online service so nevermind that).

But let’s say you wanted to encrypt between peers anyway, because you’re feeling generous (or don’t want to field a bunch of questionably legal demands for user data by law enforcement; a.k.a. the Snapchat threat model).

You could improve endpoint trust by shoving all of your users’ public keys into an append-only data structure; i.e. key transparency, like WhatsApp proposed in 2023:

https://www.youtube.com/watch?v=_N4Q05z5vPE

And, to be perfectly clear, key transparency is a damn good idea.

Key transparency keeps everyone honest and makes it difficult for criminals to secretly replace a victim’s public key, because the act of doing so is unavoidably published to an append-only log.

The primary challenge is scaling a transparency feature to serve a public, federated system.

AJ

Federated Key Transparency?

Despite appearances, I haven’t been sitting on my thumbs for the past year or so. I’ve been talking with cryptography experts about their projects and papers in the same space.

Truthfully, I had been hoping to piggyback off one of those upcoming projects (which is focused more on public key discovery for SAML- and OAuth-like protocols) to build the Federated PKI piece for E2EE for the Fediverse.

Unfortunately, that project keeps getting delayed and pushed back, and I’ve just about run out of patience for it.

Additionally, there are some engineering challenges that I would need to tackle to build atop it, so it’s not as simple as “let’s just use that protocol”, either.

So let’s do something else instead:

Art: ScruffKerfluff

Fediverse Public Key Directories

Orthogonal to the overall Fediverse E2EE specification project, let’s build a Public Key Directory for the Fediverse.

This will not only be useful for building a coherent specification for E2EE (as it provides the “Federated PKI” component we’d need to build it securely), but it would also be extremely useful for software developers the whole world over.

Imagine this:

• If you want to fetch a user’s SSH public key, you can just query for their username and get a list of non-expired, non-revoked public keys to choose from.
• If you wanted public key pinning and key rotation for OAuth2 and/or OpenID Connect identity providers without having to update configurations or re-deploy any applications, you can do that.
• If you want to encrypt a message to a complete stranger, such that only they can decrypt it, without any sort of interaction (i.e., they could be offline for a holiday and still decrypt it when they get back), you could do that.

Oh, and best of all? You can get all these wins without propping up any cryptocurrency bullshit either.

From simple abstractions, great power may bloom.

Mark Miller

How Will This Work?

We need to design a specific kind of server that speaks a limited set of the ActivityPub protocol.

I say “limited” because it will only not support editing or deleting messages provided by another instance. It will only append data.

To understand the full picture, let’s first look at the message types, public key types, and how the message types will be interpreted.

Message Types

Under the ActivityPub layer, we will need to specify a distinct set of Directory Message Types. An opening offer would look like this:

1. [b]AddKey[/b] — contains an Asymmetric Public Key, a number mapped to the user, and instance that hosts it, and some other metadata (i.e., time)
2. [b]RevokeKey[/b] — marks an existing public key as revoked
3. [b]MoveIdentity[/b] — moves all of the public keys from identity A to identity B. This can be used for username changes or instance migrations.

We may choose to allow more message types at the front-end if need be, but that’s enough for our purposes.

Public Key Types

We are not interested in backwards compatibility with every existing cryptosystem. We will only tolerate a limited set of public key types.

At the outset, only Ed25519 will be supported.

In the future, we will include post-quantum digital signature algorithms on this list, but not before the current designs have had time to mature.

RSA will never be included in the set.

ECDSA over NIST P-384 may be included at some point, if there’s sufficient interest in supporting e.g., US government users.

If ECDSA is ever allowed, RFC 6979 is mandatory.

Message Processing

When an instance sends a message to a Directory Server, it will need to contain a specific marker for our protocol. Otherwise, it will be rejected.

Each message will have its own processing rules.

After the processing rules are applied, the message will be stored in the Directory Server, and a hash of the message will be published to a SigSum transparency ledger. The Merkle root and inclusion proofs will be stored in an associated record, attached to the record for the new message.

Every message will have its hash published in SigSum. No exceptions.

We will also need a mechanism for witness co-signatures to be published and attached to the record.

Additionally, all messages defined here are generated by the users, client-side. Servers are not trusted, generally, as part of the overall E2EE threat model.

AddKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "AddKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

The first AddKey for any given identity will need to be self-signed by the key being added (in addition to ActivityPub messages being signed by the instance).

After an identity exists in the directory, every subsequent public key MUST be signed by a non-revoked keypair.

RevokeKey

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "RevokeKey", "message": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfMessage"}

This marks the public key as untrusted, and effectively “deletes” it from the list that users will fetch.

Important: RevokeKey will fail unless there is at least one more trusted public key for this user. Otherwise, a denial of service would be possible.

Replaying an AddKey for a previously-revoked key MUST fail.

MoveIdentity

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "action": "MoveIdentity", "message": { "time": "2024-12-31T23:59:59Z", "old-identity": "foo@mastodon.example.com", "new-identity": "bar@akko.example.net" }, "signature": "SignatureOfMessage"}

This exists to facilitate migrations and username changes.

Other Message Types

The above list is not exhaustive. We may need other message types depending on the exact feature set needed by the final specification.

Fetching Public Keys

A simple JSON API (and/or an ActivityStream; haven’t decided) will be exposed to query for the currently trusted public keys for a given identity.

{ "@context": "https://example.com/ns/fedi-e2ee/v1", "public-keys": [ { "data": { "time": "2024-12-31T23:59:59Z", "identity": "foo@mastodon.example.com", "public-key": "ed25519:<key goes here>" }, "signature": "SignatureOfData", "sigsum": { /* ... */ }, }, { "data": { /* ... */ }, /* ... */ }, /* ... */ ]}

Simple and easy.

CMYKat

Gossip Between Instances

Directory Servers should be configurable to mirror records from other instances.

Additionally, they should be configurable to serve as Witnesses for the SigSum protocol.

The communication layer here between Directory Servers will also be ActivityPub.

Preventing Abuse

The capability of learning a user’s public key doesn’t imply the ability to send messages or bypass their block list.

Additionally, Fediverse account usernames are (to my knowledge) generally not private, so I don’t anticipate there being any danger in publishing public keys to an append-only ledger.

That said, I am totally open to considering use cases where the actual identity is obfuscated (e.g., HMAC with a static key known only to the instance that hosts them instead of raw usernames).

What About GDPR / Right To Be Forgotten?

Others have previously suggested that usernames might be subject to the “right to be forgotten”, which would require breaking history for an append-only ledger.

After discussing a proposed workaround with a few people in the Signal group for this project, we realized complying necessarily introduced security issues by giving instance admins the capability of selectively remapping the user ID to different audiences, and detecting/mitigating this remapping is annoying.

However, we don’t need to do that in the first place.

According to this webpage about GDPR’s Right to be Forgotten:

However, an organization’s right to process someone’s data might override their right to be forgotten. Here are the reasons cited in the GDPR that trump the right to erasure:

• (…)
• The data is being used to perform a task that is being carried out in the public interest or when exercising an organization’s official authority.
• (…)
• The data represents important information that serves the public interest, scientific research, historical research, or statistical purposes and where erasure of the data would likely to impair or halt progress towards the achievement that was the goal of the processing.

Enabling private communication is in the public interest. The only information that will be stored in the ledger in relation to the username are cryptographic public keys, so it’s not like anything personal (e.g., email addresses or legal names) will be included.

However, we still need to be extremely up-front about this to ensure EU citizens are aware of the trade-off we’re making.

Account Recovery

In the event that a user loses access to all of their secret keys and wants to burn down the old account, they may want a way to start over with another fresh self-signed AddKey.

However, the existing policies I wrote above would make this challenging:

1. Since every subsequent AddKey must be signed by an incumbent key, if you don’t have access to these secret keys, you’re locked out.
2. Since RevokeKey requires one trusted keypair remains in the set, for normal operations, you can’t just burn the set down to zero even while you still had access to the secret keys.

There is an easy way out of this mess: Create a new verb; e.g. BurnDown that an instance can issue that resets all signing keys for a given identity.

The use of BurnDown should be a rare, exceptional event that makes a lot of noise:

• All existing E2EE sessions must break, loudly.
• All other participants must be alerted to the change, through the client software.
• Witnesses and watchdog nodes must take note of this change.

This comes with some trade-offs. Namely: Any account recovery mechanism is a backdoor, and giving the instance operators the capability of issuing BurnDown messages is a risk to their users.

Therefore, users who trust their own security posture and wish to opt out of this recovery feature should also be able to issue a Fireproof message at any point in the process, which permanent and irrevocably prevents any BurnDown from being accepted on their current instance.

If users opt out of recovery and then lose their signing keys, they’re locked out and need to start over with a new Fediverse identity. On the flipside, their instance operator cannot successfully issue a BurnDown for them, so they have to trust them less.

Notice

This is just a rough sketch of my initial ideas, going into this project. It is not comprehensive, nor complete.

There are probably big gaps that need to be filled in, esp. on the ActivityPub side of things. (I’m not as worried about the cryptography side of things.)

How Will This Be Used for E2EE Direct Messaging?

I anticipate that a small pool of Directory Servers will be necessary, due to only public keys and identities being stored.

Additional changes beyond just the existence of Directory Servers will need to be made to facilitate private messaging. Some of those changes include:

• Some endpoint for users to know which Directory Servers a given ActivityPub instance federates with (if any).
• Some mechanism for users to asynchronously exchange Signed Pre-Key bundles for initiating contact. (One for users to publish new bundles, another for users to retrieve a bundle.)
  
  • These will be Ed25519-signed payloads containing an ephemeral X25519 public key.

  
  

This is all outside the scope of the proposal I’m sketching out here today, but it’s worth knowing that I’m aware of the implementation complexity.

The important thing is: I (soatok@furry.engineer) should be able to query pawb.fun, find the Directory Server(s) they federate with, and then query that Directory server for Crashdoom@pawb.fun and get his currently trusted Ed25519 public keys.

From there, I can query pawb.fun for a SignedPreKey bundle, which will have been signed by one of those public keys.

And then we can return to the “easy” pile.

MarleyTanuki

Development Plan

Okay, so that was a lot of detail, and yet not enough detail, depending on who’s reading this blog post.

What I wrote here today is a very rough sketch. The devil is always in the details, especially with cryptography.

Goals and Non-Goals

We want Fediverse users to be able to publish a public key that is bound to their identity, which anyone else on the Internet can fetch and then use for various purposes.

We want to leverage the existing work into key transparency by the cryptography community.

We don’t want to focus on algorithm agility or protocol compatibility.

We don’t want to involve any government offices in the process. We don’t care about “real” identities, nor about codifying falsehoods about names.

We don’t want any X.509 or Web-of-Trust machinery involved in the process.

Tasks

The first thing we would need to do is write a formal specification for a Directory Server (whose job is only to vend Public Keys in an auditable, transparent manner).

Next, we need to actually build a reference implementation of this server, test it thoroughly, and then have security experts pound at the implementation for a while. Any security issues that can be mitigated by design will require a specification update.

We will NOT punt these down to implementors to be responsible for, unless we cannot avoid doing so.

Once these steps are done, we can start rolling the Directory Servers out. At this point, we can develop client-side libraries in various programming languages to make it easy for developers to adopt.

My continued work on the E2EE specification for the Fediverse can begin after we have an implementation of the Directory Server component ready to go.

Timeline

I have a very demanding couple of months ahead of me, professionally, so I don’t yet know when I can commit to starting the Fediverse Directory Server specification work.

Strictly speaking, it’s vaguely possible to get buy-in from work to focus on this project as part of my day-to-day responsibilities, since it has immediate and lasting value to the Internet.

However, I don’t want to propose it because that would be crossing the professional-personal streams in a way I’m not really comfortable with.

The last thing I need is angry Internet trolls harassing my coworkers to try to get under my fur, y’know?

If there is enough interest from the broader Fediverse community, I’m also happy to delegate this work to anyone interested.

Once the work can begin, I don’t anticipate it will take more than a week for me to write a specification that other crypto nerds will take seriously.

I am confident in this because most of the cryptography will be constrained to hash functions, preventing canonicalization and cross-protocol attacks, and signatures.

Y’know, the sort of thing I write about on my furry blog for fun!

Building a reference implementation will likely take a bit longer; if, for no other reason, than I believe it would be best to write it in Go (which has the strongest SigSum support, as of this writing).

This is a lot of words to say, as far as timelines go:

CMYKat

How to Get Involved

Regardless of whether my overall E2EE proposal gets adopted, the Directory Server component is something that should be universally useful to the Fediverse and to software developers around the world.

If you are interested in participating in any technical capacity, I have just created a Signal Group for discussing and coordinating efforts.

All of these efforts will also be coordinated on the fedi-e2ee GitHub organization.

The public key directory server’s specification will eventually exist in this GitHub repository.

Can I Contribute Non-Technically?

Yes, absolutely. In the immediate future, once it kicks off, the work is going to be technology-oriented.

However, we may need people with non-technical skills at some point, so feel free to dive in whenever you feel comfortable.

What About Financially?

If you really have money burning a hole in your pocket and want to toss a coin my way, I do have a Ko-Fi. Do not feel pressured at all to do so, however.

Because I only use Ko-Fi as a tip jar, rather than as a business, I’m not specifically tracking which transaction is tied to which project, so I can’t make any specific promises about how any of the money sent my way will be allocated.

What I will promise, however, is that any icons/logos/etc. created for this work will be done by an artist and they will be adequately compensated for their work. I will not use large-scale computing (a.k.a., “Generative AI”) for anything.

Closing Thoughts

What I’ve sketched here is much simpler (and more ActivityPub-centric) than the collaboration I was originally planning.

Thanks for being patient while I tried, in vain, to make that work.

As of today, I no longer think we need to wait for them. We can build this ourselves, for each other.

https://soatok.blog/2024/06/06/towards-federated-key-transparency/

#cryptography #endToEndEncryption #fediverse #KeyTransparency #Mastodon #MerkleTrees #PublicKeys

If you’ve paid attention to Hacker News or various technology subreddits in recent years, you may have noticed the rise of VPN companies like Tailscale and ZeroTier. At the core of their networking products is a Noise-based Protocol (often WireGuard).

If you haven’t been paying attention to Hacker News or Reddit, that’s probably healthy. Keep up the good work.

(EDIT: The Noise protocol is not presently in the production version of ZeroTier, but an upcoming version instead. Thanks to api for clarifying this detail.)

What’s This All About?

Noise is a framework for building protocols based on the Diffie-Hellman key agreement algorithm, combined with a few other cryptographic primitives (authenticated encryption and a hash function). The Noise specification is quite readable, if you want to see what it looks like.

WireGuard and other protocols are built atop the Noise framework, which means that each peer has an ECDH public key (typically Curve25519) and establishing a session generally involves generating an ephemeral ECDH keypair for that recipient.

Thus far, the relationship between Noise-based protocols and the aforementioned companies’ use cases has been a happy one: The security and performance are extremely competitive, and the amount of source code needed to support these protocols is minimal.

However, the networking provided by Noise-based protocols is inherently unicast in their design (as most Internet-based protocols you use every day are). Multicast networking is mostly supported through emulation, rather than by low-level protocol design.

Today, I’d like to sketch out an idea of mine for integrating multicast networking support with Noise-based protocols. This idea may be a bit half-baked, but I don’t have the free time to analyze it fully and build a demo.

Art: Harubaki

If anyone working for one of these companies believes it’s worth exploring, feel free to pick it up and run with it.

Why Multicast?

The classical use case for multicast networking is video conferencing or streaming; typically high-bandwidth operations.

However, there are some other usages of multicast that are more attractive for VPN customers; i.e. it lends well to load-balancing as well as creating more privileged partitions of your network with a public interface.

Elevator Pitch

Use Ratchet Trees from Messaging Layer Security (MLS, RFC 9420) as a primitive for establishing a shared group public key for a subset of nodes in your network.

Then, use the group key as you would a typical ECDH public key in a Noise-based protocol.

You can then encrypt traffic to any node in that subnet and they’ll be capable of decrypting it.

Art: CMYKat

Sounds Simple; What’s the Catch?

Remember earlier when I mentioned WireGuard? Their homepage gives an example for Cryptokey routing that looks like this on the server side:

[Interface]PrivateKey = yAnz5TF+lXXJte14tji3zlMNq+hd2rYUIgJBgB3fBmk=ListenPort = 51820[Peer]PublicKey = xTIBA5rboUvnH4htodjb6e697QjLERt1NAB4mZqp8Dg=AllowedIPs = 10.192.122.3/32, 10.192.124.1/24[Peer]PublicKey = TrMvSoP4jYQlY6RIzBgbssQqY3vxI2Pi+y71lOWWXX0=AllowedIPs = 10.192.122.4/32, 192.168.0.0/16[Peer]PublicKey = gN65BkIKy1eCE9pP1wdc8ROUtkHLF2PfAqYdyYBz6EA=AllowedIPs = 10.10.10.230/32

And may look something like this on a client computer:

[Interface]PrivateKey = gI6EdUSYvn8ugXOt8QQD6Yc+JyiZxIhp3GInSWRfWGE=ListenPort = 21841[Peer]PublicKey = HIgo9xNzJMWLKASShiTqIybxZ0U3wGLiUeJ1PKf8ykw=Endpoint = 192.95.5.69:51820AllowedIPs = 0.0.0.0/0

This is elegant and works beautifully for its intended use case, but adding multicast complicates matters.

Most significant: Your group key will ratchet forward every time you perform a group operation (e.g., adding or removing a node).

Whether this is a significant obstacle for the tooling these companies already provide is not my place to speculate.

As I said above, the idea is somewhat half-baked, so there may be other complications staring me in the face that I’m oblivious to.

A Subtlety of Ratchet Trees

One of the really cool things about Ratchet Trees from MLS, that probably doesn’t get talked about enough, is that any peer in a tree could secretly be an entire separate tree and the top-level group will have no idea (unless it’s, like, the only node that rotates its key often).

When this is brought up, it’s often highlighted as a boon for multi-device support. In federated messaging protocols, it’s one way to obfuscate some social graph metadata from being observable to outside observers.

How Would This Affect Protocol Complexity?

Other than rotating a peer’s identity public key every time a group operation is performed, it’s totally backwards compatible with what Noise already does today. No fundamental changes to the transport cryptography needed.

That being said, printing the contents of RFC 9420 clocks in at over 130 pages, so the ratchet tree itself does add overall protocol complexity.

Integrating ratchet trees with a Noise-based protocol will require careful planning and review from other cryptographers.

Closing Thoughts

Is this idea a good one? Is it doomed from the start? Will this effort be doomed by the advent of a cryptography-relevant quantum computer before any code gets written?

Who’s to say? I don’t really have the time to flesh it out and explore it fully.

Art: CMYKat

Header art by Harubaki and AJ.

https://soatok.blog/2023/10/10/a-plan-for-multicast-support-in-noise-based-protocols/

#cryptography #MLS #Networking #NoiseProtocolFramework #Tailscale #VPNs #WireGuard

Hector Martin

2023-06-07 12:59:05

So I was wondering why my Hacker News block didn't work any more.

Lovely to know that instead of fixing their community going down the drain and outright hosting harassment and abuse that goes unchecked, they decided to just evade our block.

EDIT: WAIT, THEY ADDED IT JUST FOR US. IT'S JUST ON ASAHILINUX LINKS

OMFG.

Keep in mind other people have been blocking them for ages, by doing things like redirecting to pictures of testicles, and they didn't care. We just redirected to google.com. Yet, apparently, being blocked by us was insult enough to... evade the block instead of doing a little self-reflection.

Fuck you, HN.

Wikipedia’s definition of a digital signature is:

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.

—Wikipedia

They also have a handy diagram of the process by which digital signatures are created and verified:
Source: https://commons.m.wikimedia.org/wiki/File😛rivate_key_signing.svg#mw-jump-to-license (CC-BY-SA)
Alice signs a message using her private key and Bob can then verify that the message came from Alice, and hasn’t been tampered with, using her public key. This all seems straightforward and uncomplicated and is probably most developers’ view of what signatures are for and how they should be used. This has led to the widespread use of signatures for all kinds of things: validating software updates, authenticating SSL connections, and so on.

But cryptographers have a different way of looking at digital signatures that has some surprising aspects. This more advanced way of thinking about digital signatures can tell us a lot about what are appropriate, and inappropriate, use-cases.

Identification protocols

There are several ways to build secure signature schemes. Although you might immediately think of RSA, the scheme perhaps most beloved by cryptographers is Schnorr signatures. These form the basis of modern EdDSA signatures, and also (in heavily altered form) DSA/ECDSA.

The story of Schnorr signatures starts not with a signature scheme, but instead with an interactive identification protocol. An identification protocol is a way to prove who you are (the “prover”) to some verification service (the “verifier”). Think logging into a website. But note that the protocol is only concerned with proving who you are, not in establishing a secure session or anything like that.

There are a whole load of different ways to do this, like sending a username and password or something like WebAuthn/passkeys (an ironic mention that we’ll come back to later). One particularly elegant protocol is known as Schnorr’s protocol. It’s elegant because it is simple and only relies on basic security conjectures that are widely accepted, and it also has some nice properties that we’ll mention shortly.

The basic structure of the protocol involves three phases: Commit-Challenge-Response. If you are familiar with challenge-response authentication protocols this just adds an additional commitment message at the start.

Alice (for it is she!) wants to prove to Bob who she is. Alice already has a long-term private key, a, and Bob already has the corresponding public key, A. These keys are in a Diffie-Hellman-like finite field or elliptic curve group, so we can say A = g^a mod p where g is a generator and p is the prime modulus of the group. The protocol then works like this:

1. Alice generates a random ephemeral key, r, and the corresponding public key R = g^r mod p. She sends R to Bob as the commitment.
2. Bob stores R and generates a random challenge, c and sends that to Alice.
3. Alice computes s = ac + r and sends that back to Bob as the response.
4. Finally, Bob checks if g^s = A^c * R (mod p). If it is then Alice has successfully authenticated, otherwise it’s an imposter. The reason this works is that g^s = g^(ac + r) and A^c * R = (g^a)^c * g^r = g^(ac + r) too. Why it’s secure is another topic for another day.

Don’t worry if you don’t understand all this. I’ll probably do a blog post about Schnorr identification at some point, but there are plenty of explainers online if you want to understand it. For now, just accept that this is indeed a secure identification scheme. It has some nice properties too.

One is that it is a (honest-verifier) zero knowledge proof of knowledge (of the private key). That means that an observer watching Alice authenticate, and the verifier themselves, learn nothing at all about Alice’s private key from watching those runs, but the verifier is nonetheless convinced that Alice knows it.

This is because it is easy to create valid runs of the protocol for any private key by simply working backwards rather than forwards, starting with a response and calculating the challenge and commitment that fit that response. Anyone can do this without needing to know anything about the private key. That is, for any given challenge you can find a commitment for which it is easy to compute the correct response. (What they cannot do is correctly answer a random challenge after they’ve already sent a commitment). So they learn no information from observing a genuine interaction.

Fiat-Shamir

So what does this identification protocol have to do with digital signatures? The answer is that there is a process known as the Fiat-Shamir heuristic by which you can automatically transform certain interactive identification protocols into a non-interactive signature scheme. You can’t do this for every protocol, only ones that have a certain structure, but Schnorr identification meets the criteria. The resulting signature scheme is known, amazingly, as the Schnorr signature scheme.

You may be relieved to hear that the Fiat-Shamir transformation is incredibly simple. We basically just replace the challenge part of the protocol with a cryptographic hash function, computed over the message we want to sign and the commitment public key: c = H(R, m).

That’s it. The signature is then just the pair (R, s).

Note that Bob is now not needed in the process at all and Alice can compute this all herself. To validate the signature, Bob (or anyone else) recomputes c by hashing the message and R and then performs the verification step just as in the identification protocol.

Schnorr signatures built this way are secure (so long as you add some critical security checks!) and efficient. The EdDSA signature scheme is essentially just a modern incarnation of Schnorr with a few tweaks.

What does this tell us about appropriate uses of signatures

The way I’ve just presented Schnorr signatures and Fiat-Shamir is the way they are usually presented in cryptography textbooks. We start with an identification protocol, performed a simple transformation and ended with a secure signature scheme. Happy days! These textbooks then usually move on to all the ways you can use signatures and never mention identification protocols again. But the transformation isn’t an entirely positive process: a lot was lost in translation!

There are many useful aspects of interactive identification protocols that are lost by signature schemes:

• A protocol run is only meaningful for the two parties involved in the interaction (Alice and Bob). By contrast a signature is equally valid for everyone.
• A protocol run is specific to a given point in time. Alice’s response is to a specific challenge issued by Bob just prior. A signature can be verified at any time.

These points may sound like bonuses for signature schemes, but they are actually drawbacks in many cases. Signatures are often used for authentication, where we actually want things to be tied to a specific interaction. This lack of context in signatures is why standards like JWT have to add lots of explicit statements such as audience and issuer checks to ensure the JWT came from the expected source and arrived at the intended destination, and expiry information or unique identifiers (that have to be remembered) to prevent replay attacks. A significant proportion of JWT vulnerabilities in the wild are caused by developers forgetting to perform these checks.

WebAuthn is another example of this phenomenon. On paper it is a textbook case of an identification protocol. But because it is built on top of digital signatures it requires adding a whole load of “contextual bindings” for similar reasons to JWTs. Ironically, the most widely used WebAuthn signature algorithm, ECDSA, is itself a Schnorr-ish scheme.

TLS also uses signatures for what is essentially an identification protocol, and similarly has had a range of bugs due to insufficient context binding information being included in the signed data. (SSL also uses signatures for verifying certificates, which is IMO a perfectly good use of the technology. Certificates are exactly a case of where you want to convert an interactive protocol into a non-interactive one. But then again we also do an interactive protocol (DNS) in that case anyway 🤷).

In short, an awful lot of uses of digital signatures are actually identification schemes of one form or another and would be better off using an actual identification scheme. But that doesn’t mean using something like Schnorr’s protocol! There are actually better alternatives that I’ll come back to at the end.

Special Soundness: fragility by design

Before I look at alternatives, I want to point out that pretty much all in-use signature schemes are extremely fragile in practice. The zero-knowledge security of Schnorr identification is based on it having a property called special soundness. Special soundness essentially says that if Alice accidentally reuses the same commitment (R) for two runs of the protocol, then any observer can recover her private key.

This sounds like an incredibly fragile notion to build into your security protocol! If I accidentally reuse this random value then I leak my entire private key??! And in fact it is: such nonce-reuse bugs are extremely common in deployed signature systems, and have led to compromise of lots of private keys (eg Playstation 3, various Bitcoin wallets etc).

But despite its fragility, this notion of special soundness is crucial to the security of many signature systems. They are truly a cursed technology!

To solve this problem, some implementations and newer standards like EdDSA use deterministic commitments, which are based on a hash of the private key and the message. This ensures that the commitment will only ever be the same if the message is identical: preventing the private key from being recovered. Unfortunately, such schemes turned out to be more susceptible to fault injection attacks (a much less scalable or general attack vector), and so now there are “hedged” schemes that inject a bit of randomness back into the hash. It’s cursed turtles all the way down.

If your answer to this is to go back to good old RSA signatures, don’t be fooled. There are plenty of ways to blow your foot off using old faithful, but that’s for another post.

Did you want non-repudiation with that?

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.

You don’t need to explicitly want anonymity or deniability to understand that these strong security properties can have damaging and unforeseen side-effects. Non-repudiation should never be the default in open systems.

I could go on. From the fact that there are basically zero acceptable post-quantum signature schemes (all way too large or too risky), to issues with non-canonical signatures and cofactors and on and on. The problems of signature schemes never seem to end.

What to use instead?

Ok, so if signatures are so bad, what can I use instead?

Firstly, if you can get away with using a simple shared secret scheme like HMAC, then do so. In contrast to public key crypto, HMAC is possibly the most robust crypto primitive ever invented. You’d have to go really far out of your way to screw up HMAC. (I mean, there are timing attacks and that time that Bouncy Castle confused bits and bytes and used 16-bit HMAC keys, so still do pay attention a little bit…)

If you need public key crypto, then… still use HMAC. Use an authenticated KEM with X25519 to generate a shared secret and use that with HMAC to authenticate your message. This is essentially public key authenticated encryption without the actual encryption. (Some people mistakenly refer to such schemes as designated verifier signatures, but they are not).

Signatures are good for software/firmware updates and pretty terrible for everything else.

https://neilmadden.blog/2024/09/18/digital-signatures-and-how-to-avoid-them/

#authenticatedEncryption #cryptography #misuseResistance #signatures

Neil Madden

2021-02-16 13:14:46

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.

Authenticated KEMs

Let’s look first at how to create authenticated encryption in the KEM/DEM paradigm. The DEM used to encrypt the body of a message in the KEM/DEM paradigm already provides authenticated encryption, so the only work that needs to be done is to authenticate the KEM so that the recipient can be confident the encapsulated DEM key came from a trusted source. Although we could try to manually combine a KEM with some kind of authentication mechanism, it’s almost always better to define a single abstraction that provides both properties. In this case, we can extend our KEM interface to become an authenticated KEM or AKEM. An AKEM is like a KEM, but the encapsulation function takes the sender’s private key as an additional argument, and the decapsulation function takes the sender’s public key:
function auth_encapsulate(senderPrivateKey, recipientPublicKey): // returns (aesKey, encapsulatedKey) as beforefunction auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey): // returns either the original aesKey or an error if // authentication fails
A straightforward implementation of this idea would be to combine an existing (unauthenticated) KEM with a signature scheme. The KEM produces an encapsulated key, which we then sign with our private key so that the recipient can be sure that it really came from us:
function auth_encapsulate_sig(senderPrivateKey, recipientPublicKey): var (aesKey, encapsulatedKey) = KEM.encapsulate(recipientPublicKey); var signature = sign(senderPrivateKey, encapsulatedKey); return (aesKey, encapsulatedKey || signature);function auth_decapsulate_sig(senderPublicKey, recipientPrivateKey, encapsulatedSignedKey): var (encapsulatedKey, signature) = parse(encapsulatedSignedKey); if !verify_signature(senderPublicKey, encapsulatedKey, signature): return error; return KEM.decapsulate(recipientPrivateKey, encapsulatedKey);
This works, but it can produce very large encapsulated keys. For example, if you use RSA-KEM with an RSA signature scheme and 3072-bit keys, then the encapsulated key will end up being at least 768 bytes long. We can do better by removing the explicit signature and instead using implicit authentication, where we derive the DEM key in such a way that only the genuine sender could have calculated it. Any attempt to change the encapsulated key, without using the sender’s private key, will result in a different DEM key being calculated and the DEM authenticated decryption step will fail with an authentication error.

One way to achieve this is to adapt the elliptic curve Diffie-Hellman (ECDH) KEM to include the sender’s private key in the key agreement calculation. Rather than performing a single ECDH calculation between an ephemeral private key and the recipient’s public key, we additionally perform one between the sender’s private key and the recipient’s public key. The two derived shared secrets are then concatenated before being fed into the Key Derivation Function to produce the AES key:
function auth_encapsulate_ecdh(senderPrivateKey, recipientPublicKey): var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(recipientPublicKey.curve); var ess = ecdh(ephemeralSecretKey, recipientPublicKey); var sss = ecdh(senderPrivateKey, recipientPublicKey); var aesKey = sha256(ess || sss || ephemeralPublicKey); return (aesKey, ephemeralPublicKey);function ecdh_decapsulate_ecdh(senderPublicKey, recipientPrivateKey, ephemeralPublicKey): var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); return sha256(ess || sss || ephemeralPublicKey);
(Note: as before we include the ephemeral public key in the KDF step to ensure non-malleability, and we’re using SHA-256 as a cheap and cheerful stand-in for a real KDF).

The advantage of this approach is that the encapsulated key is still just an ephemeral public key—just 32 bytes for X25519. It’s also more deniable than the signature version. NIST call this scheme the One-Pass Unified Model, and it’s also broadly similar to the Noise “K” one-way handshake pattern and the AKEM defined for the upcoming HPKE standard. Although this scheme is more compact than the combination of a KEM plus a signature, it is still computationally quite expensive because of the two ECDH computations that are needed. More efficient options such as (one-pass) MQV can reduce this overhead, but these are not widely used in practice due to patent issues and potential weaknesses of some variants.

Both of these AKEM designs suffer from some security weaknesses:

• They are both vulnerable to something called Key Compromise Impersonation (KCI) attacks. What this means is that if an attacker compromises your long-term secret key, they can not only pretend to be you when sending messages to other people, but can pretend to be anyone else when sending messages to you! For the ECDH scheme they can immediately do this. The KEM-then-sign variant is a bit stronger, in that an attacker would have to capture at least one message sent to you by the party they want to impersonate, but in practice this is often possible. Preventing KCI generally involves either an interactive authentication protocol or signing the entire message, both of which I’ll leave out of this article.
• Neither design incorporates any notion of the identity of the users involved. In some cases this can lead to Unknown Key Share attacks, in which we think we’re communicating with Alice but actually are talking to Bob. You can solve this problem by including identity information and long-term public keys in the signature or key-derivation steps. It can be useful to add a general “context” argument to the encapsulate and decapsulate functions to allow additional data to be included in the KDF:

function auth_encapsulate_ecdh(senderPrivateKey, recipientPublicKey, context): var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(recipientPublicKey.curve); var ess = ecdh(ephemeralSecretKey, recipientPublicKey); var sss = ecdh(senderPrivateKey, recipientPublicKey); var aesKey = sha256(ess || sss || ephemeralPublicKey || context); return (aesKey, ephemeralPublicKey);function ecdh_decapsulate_ecdh(senderPublicKey, recipientPrivateKey, ephemeralPublicKey, context): var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); return sha256(ess || sss || ephemeralPublicKey || context);

Sending to multiple recipients

The basic KEM/DEM paradigm runs into a problem if we want to send the same message to multiple recipients. In the traditional approach to hybrid encryption before KEMs, you’d simply generate a random AES key and then encrypt it for each recipient. But this doesn’t work for KEMs: we’d have to run the KEM separately for each recipient, obtaining a separate AES key for each one, and then encrypt the entire message with each AES key. This is very inefficient.

We can solve this problem by introducing a notion called symmetric key-wrapping, where we use one AES key to encrypt (“wrap”) another AES key. In principle, any secure authenticated encryption scheme (such as a DEM) could be used, but there are some specialised algorithms that are more compact.

The idea is a bit like the original version of hybrid encryption, but instead of directly encrypting the AES key for each recipient, we will instead use the KEM to derive a key-encryption key (KEK) for each recipient, and then use that to encrypt the random AES key (which we’ll call the Data Encryption Key, or DEK):

1. Generate a random DEK, dek = DEM.keygen()
2. Encrypt the message with dk: ciphertext = DEM.encrypt(dek, message);
3. For each recipient, r, calculate the Key Encryption Key:
   kek[r], encapsulatedKey[r] = KEM.encapsulate(r.publicKey);
4. For each KEK, encrypt the DEK: wrappedKey[r] = wrap(kek[r], dk);
5. Send the encrypted ciphertext, the wrapped keys, and the encapsulated keys to the recipients.

Each recipient then runs the KEM to decapsulate their encapsulated key and uses the result to decrypt (“unwrap”) the DEK. They then use the DEK to decrypt the rest of the message.

There is still an inefficiency here though, in that we’ll have a separate encapsulated key for each recipient. For the ECDH-KEM the encapsulated key is an ephemeral public key, and we can safely reuse the same ephemeral key pair for every recipient. This saves a costly key-pair generation step for each recipient and reduces the size of the final ciphertext, but we can’t achieve this with the existing KEM API.

Once again, we can adapt the KEM interface to natively support this. The encapsulation function is changed to take a set of public keys for the recipients rather than just one. The result is known as an mKEM, and you can find more details in this article by Nigel Smart (*cough* over here). For example, here’s an unauthenticated mKEM based on ECDH:
function mkem_encapsulate(recipientPublicKeys): var aesKey = DEM.keygen(); var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ss = ecdh(ephemeralSecretKey, pk); var kek = sha256(ss || ephemeralPublicKey); var wrappedKey = wrap(kek, aesKey); wrappedKeys += wrappedKey; end return (aesKey, ephemeralPublicKey || wrappedKeys);

Authenticated mKEMs

It’s easy to see how we could adapt the generic mKEM approach of the previous section to provide authenticated encryption (AmKEM? mAKEM?): simply add the sender’s private key to the interface and then perform an authenticated key derivation for each recipient, just as we did for the single-recipient AKEM:
function auth_mkem_encapsulate(senderPrivateKey, recipientPublicKeys): var aesKey = DEM.keygen(); var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ess = ecdh(ephemeralSecretKey, pk); var sss = ecdh(senderPrivateKey, pk); var kek = sha256(ess || sss || ephemeralPublicKey); var wrappedKey = wrap(kek, aesKey); wrappedKeys += wrappedKey; end return (aesKey, ephemeralPublicKey || wrappedKeys);
This does provide authenticated encryption, but only if all the recipients are honest. If any of the recipients is malicious, or have had their private key compromised, they can create a new message that appears to come from the original sender:

• First they decapsulate the genuine message to obtain the DEM key, dek.
• They then create a new message and encrypt it using the DEM and the same DEK: var c2 = DEM.encrypt(dek, "My new message");
• Finally, they re-attach the wrapped keys and ephemeral public key from the original message and send the whole thing to the same recipients (or a subset of them).

When the recipients decrypt the message it will appear that it is a genuine message from the original sender. This can happen regardless of whether you use signatures or implicit authentication in the AKEM. The fundamental reason is that neither the encapsulated keys nor the wrapped keys are in any way tied to the actual message. The KEM ensures the authenticity of the data encryption key, and the DEM ensures that a message could only have been created by someone who had access to that DEK. The problem is that the set of people who have access to the DEK is the original sender and all of the recipients.

Protecting against this kind of attack is known as insider security, and to solve it we’ll need to give up some measure of deniability. We could just sign the entire message, in which case we give up all deniability: any third party can verify that we sent that message, not just our intended recipients. Let’s call this outsider non-repudiation. What we really want is a slightly weaker guarantee: the recipients can prove to each other that the message came from the original sender (or didn’t in the case of a forgery), but they can’t prove that to anyone outside the group. We’ll call this insider non-repudiation.

For example, if Alice sends a message to Bob and Charlie, then Bob can prove to Charlie that Alice really did send that message (even if Charlie failed to receive it), but Bob can’t prove anything about the origin of the message to Delilah, who wasn’t in the original set of recipients. As far as Delilah is concerned, Bob could have fabricated the message.

It turns out that we can quite easily solve this problem, but first we need a little detour.

Tag-KEM: KEMs with associated data

The original formulation of the KEM/DEM paradigm required both the KEM and the DEM to be secure against chosen ciphertext attacks (CCA). This is a strong notion of security, but was found to be too strong in some cases. There are efficient hybrid encryption schemes in which either the KEM or the DEM is not CCA-secure, but when combined in the right way can achieve CCA-secure public key encryption. Some of these schemes are more efficient than they would be otherwise. To accommodate these schemes into the KEM/DEM paradigm, a new variant known as Tag-KEM was introduced. A Tag-KEM (TKEM) splits the encapsulation of a symmetric key into two phases:

• First, a function is called with the recipient’s public key and it outputs an AES key to use with the DEM and a private state value:
  var (aesKey, state) = TKEM.key(recipientPublicKey);
• Then, after the message has been encrypted with the DEM, a second function of the TKEM is called to generate an encapsulated key from the internal state and a tag. The tag is some arbitrary associated data that will be linked to the encapsulated key. You can think of it a bit like the context argument we added earlier to allow user identities to be bound to the encapsulated key.
  var encapsulatedKey = TKEM.encapsulate(state, tag);
• To decapsulate the key, the recipient has to provide the same tag. If they provide a different tag then an error is returned.

In the original paper, this is used to allow the DEM to be a simple CPA-secure (unauthenticated) encryption algorithm. The entire encrypted ciphertext from the DEM is passed in as the tag to the TKEM. The TKEM then applies a MAC to the tag as part of the encapsulation process, effectively transforming it into a secure Encrypt-then-MAC scheme. We can use the same mechanism to ensure that the key encapsulation is tied to the message to prevent insider attacks against authenticated KEMs, by ensuring that the tag is included in the authentication step. The same idea has been used to construct secure signcryption schemes from Tag-KEM (signcryption is a strong form of public key authenticated encryption that provides the same authenticity guarantees as a signature, and so provides the stronger outsider non-repudiation we want to avoid).

There are two ways that we could accomplish this:

• We can add a tag argument to the AKEM mechanism, so that the tag is directly included in the authentication provided by the AKEM. For example, using the context argument we described earlier. If the AKEM is based on signatures, then this effectively becomes a signcryption scheme, which has the advantage of also preventing KCI attacks, but destroys deniability.
• If we are using key-wrapping, and the key-wrapping function allows associated data (SIV-AES does, AES-KW doesn’t) then we can include the tag there instead. This better preserves deniability, but remains vulnerable to KCI.

If we’re using a KEM based on ECDH with a strong KDF like HKDF, then these two options are pretty similar: the tag ends up getting included in a strong MAC (PRF) protected by a key known only to the sender and an individual recipient. If the tag is the whole message, then this ensures that a new message can’t be created with the same encapsulated DEK without the other recipients being able to detect this.

mATKEMs

Putting it all together, we’d get a multi-recipient authenticated Tag-KEM, or mATKEM for short! A mATKEM has the following functions:

• keygen() – generates public and private keys for a sender/recipient and returns them.
• key(senderPrivateKey, recipientPublicKeys) – returns a fresh DEM key and a private state object that is tied to the sender, recipients, and the DEM key.
• auth_encapsulate(state, tag) – encapsulates the DEM key for each of the recipients in a way that they can authenticate the sender, with the tag also authenticated (but not encapsulated). Returns the encapsulated key.
• auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag) – authenticates that the encapsulated key was produced by the given sender with the given tag, and then decapsulates and returns the DEM key. If authentication fails then an error is returned instead.

A sketch of an implementation of a secure mATKEM based on ECDH with key-wrapping is shown below. This is just a sketch of how such a thing could be implemented, I haven’t rigorously analysed it or attempted to prove it correct.
function key(senderPrivateKey, recipientPublicKeys): var dek = DEM.keygen(); var state = (dek, senderPrivateKey, recipientPublicKeys); return (dek, state);function auth_encapsulate(state, tag): var (dek, senderPrivateKey, recipientPublicKeys) = state; var (ephemeralSecretKey, ephemeralPublicKey) = generateKeyPair(); var wrappedKeys = []; for pk in recipientPublicKeys: var ess = ecdh(ephemeralSecretKey, pk); var sss = ecdh(senderPrivateKey, pk); var kek = KDF(ess || sss || ephemeralPublicKey || tag); var wrappedKey = wrap(kek, dek); wrappedKeys += wrappedKey; end return ephemeralPublicKey || wrappedKeys;function auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag): var ephemeralPublicKey || wrappedKeys = encapsulatedKey; var ess = ecdh(recipientPrivateKey, ephemeralPublicKey); var sss = ecdh(recipientPrivateKey, senderPublicKey); var kek = KDF(ess || sss || ephemeralPublicKey || tag); for wrappedKey in wrappedKeys: var dek = unwrap(kek, wrappedKey); if dek != error: return dek end return error;

Compactly committing DEMs

In the original formulation of a Tag-KEM, the tag input is the full ciphertext output of the (unauthenticated) DEM. But in the mATKEM implementation this entire ciphertext gets passed into the KDF or MAC for every recipient, which is very inefficient for long messages. This can be optimised in the multi-recipient case by hashing the tag once with a collision-resistant hash function rather than including the whole ciphertext in the KEM or key-wrap calculation for every recipient.

An alternative approach would be to use an authenticated DEM that is compactly committing (which I’ll refer to as ccDEM) and then use the MAC tag from the DEM as the tag for the authenticated TKEM. The advantage of reusing the authentication tag from the DEM rather than calculating it in the KEM, is that it allows us to use DEM schemes that are not based on Encrypt-then-MAC, for example misuse-resistant modes like SIV-AES.

Not all authenticated encryption algorithms are compactly committing, and several popular algorithms such as AES-GCM and ChaCha20-Poly1305 are definitely not. Although those algorithms prevent an attacker who doesn’t know the DEK from altering or forging new ciphertexts, if the attacker does know the key (as in insider security) then they can actually find other messages that have the same tag. The same is true for CMAC used by SIV and CCM. The definition of a compactly committing encryption algorithm requires that the MAC is a collision-resistant pseudorandom function (PRF) such as HMAC. If we assume that Alice (the sender) is honest then we should be able to get away with just second-preimage resistance instead for this application, which allows us to use shorter tags.

A ccDEM would be a DEM that takes a key, message, and (optional) associated data and returns a ciphertext and compactly committing authentication tag. An insider-secure multi-recipient authenticated public key encryption scheme (phew!) can then be built as the following generic composition:
function encrypt(senderPrivateKey, recipientPublicKeys, plaintext): var (dek, state) = mATKEM.key(senderPrivateKey, recipientPublicKeys); var (ciphertext, tag) = ccDEM.encrypt(dek, plaintext); var encapsulatedKey = mATKEM.auth_encapsulate(state, tag); return (encapsulatedKey, ciphertext, tag);function decrypt(senderPublicKey, recipientPrivateKey, receivedMessage): var (encapsulatedKey, ciphertext, tag) = receivedMessage; var dek = mATKEM.auth_decapsulate(senderPublicKey, recipientPrivateKey, encapsulatedKey, tag); if dek = error: return error; return DEM.decrypt(dek, ciphertext, tag);
The combination of a compactly committing DEM and an authenticated Tag-KEM seems like a powerful way of thinking about secure public key encryption schemes. This was first suggested to me by Paul Grubbs on the CFRG mailing list, but as he says it has not been formally analysed so please don’t rush to deploy such a scheme in production. Hopefully a real cryptographer will find this problem interesting and decide to fill in the gaps.

That concludes this look at building authenticated KEMs for multiple recipients. We’ve seen how the original KEM interface can be adapted to accommodate stronger security goals. As with the original KEM proposal, finding the right API is an important part of building secure software, and the wrong API can leave you constantly fighting subtle security issues or inefficiencies. In the next article, I look at forward secrecy and how that tantalising state argument in the Tag-KEM API can be a bridge towards secure interactive protocols like Signal or Noise.

https://neilmadden.blog/2021/02/16/when-a-kem-is-not-enough/

#authenticatedEncryption #cryptography #kemDemParadigm #publicKeyEncryption

If you follow me on Twitter, you probably already knew that I attended DEFCON 30 in Las Vegas.

If you were there in person, you probably also saw this particular nerd walking around:

That’s me, wearing a partial fursuit.
The collar reads “Warning: PUNS” in a marquee.

In addition to being shamelessly furry and meeting a lot of really cool hackers (including several readers of this blog!), I attended several village talks (and at least one Sky Talk).

For some of these talks, I attended in fursuit. For others, I opted instead to bring my laptop and take notes. (Doing both things is ill-advised because it’s hard to type with paws, and the risk of laptop damage from excess sweat gives me pause, so it was one or the other.)

To be terse, my DEFCON experience was overwhelmingly positive. However, one talk at the Quantum Village had an extremely sus abstract (which was pointed out to me by Cendyne), so I decided to attend in person and see for myself.

Screenshot of the talk abstract.

Unfortunately, my intuition as a security engineer did not let me down, as we’ll explore below. But first, some background information.

What is DEFCON, Exactly?

(Feel free to skip this section if you already know.)

DEFCON is a hacking and security conference that takes place every year in Las Vegas, NV.

Unlike the stuffy Industry- and vendor-oriented events, DEFCON is more Community focused. Consequently, DEFCON has an inextricable counterculture element to it, and that makes it unique among security conferences.

(Some of the Security BSides events may also retain the same counterculture attitudes. However, that depends heavily on the attitudes of the local security/hacking scene. Give them a chance if you live near one, or consider starting your own.)

Put another way: DEFCON is to punk rock what USENIX is to classical. You’ll find good practitioners in both genres, and a surprising amount of overlap, but they can be appreciated independently too.

Which is why very few people balked at a group of furries running through Closing Ceremonies.

https://twitter.com/DCFurs/status/1558947697469448192

The weirdness and acceptance of DEFCON is a reflection of the diversity of the infosec community, and that’s a damn good thing.

In addition to DEFCON’s main track, there are a lot of so-called Villages that focus on different aspects of hacking, security, and the community.

For example, the Crypto & Privacy Village.

Photo: Cendyne

One of the many aspects of DEFCON is that you find yourself surrounded by people with deep expertise in many different areas (not just technological) who aren’t afraid to call you on any bullshit you spew. (Some of this fearlessness may be due to how much alcohol some people consume at the conference; I generally don’t drink alcohol, especially when fursuiting.)

Vikram Sharma’s Talk at the Quantum Village at DEFCON 30

The M.C. of the Quantum Village introduced Vikram by saying, “You should know who he is,” and saying that he’s deeply involved in policy discussions with government agencies. He was also described as a TED speaker.

https://www.youtube.com/watch?v=SQB9zNWw9MA

I came to the talk intentionally unfamiliar with Vikram’s previous presentations, and with an open mind to the material he was going to share, so to avoid preconceived notions or unconscious bias as much as humanly possible.

The M.C.’s introduction primed me to expect a level of technical competence with cryptography and cryptanalysis on par with, or better than, a typical engineering manager that oversees cryptographers.

Vikram’s talk did not deliver on this built-up expectation.

Vikram Sharma’s Arguments

Vikram’s talk can be loosely distilled into a few important points:

1. Cryptography-Relevant Quantum Computers are coming, and we don’t know when, but most experts believe within the next 30 years (at most).
2. Although NIST has been working since 2015 on post-quantum cryptography, the advancements in cryptanalysis against Rainbow and SIKE highlight how nascent these algorithms are, and how brittle they may prove to be against mathematical advancements.
3. In order to be ready to defend against Quantum Adversaries, we must adopt a mindset of “crypto agility” when engineering our applications.
4. For enterprise customers, a Key Management Service that uses Quantum Key Distribution between endpoints in addition to post-quantum cryptography is likely necessary to hedge against advancements to post-quantum cryptanalysis.

The first two points are totally uncontroversial.

The third is interesting, and the fourth is a thinly-veiled sales pitch for Vikram’s company, QuintessenceLabs, rather than a serious technical argument.

Let’s explore the latter two points in more detail.

Art: LvJ

“Crypto Agility” From an Applied Cryptography Perspective

Protocols that utilize “crypto agility” are not new. SSL/TLS, SSH, and JWT all permit some degree of flexibility in the ciphersuite selection, rather than hard-coding the parameters.

For earlier versions of SSL/TLS, you could encrypt with RC4 with SHA1, and that was totally permitted. Stupid, but permitted. Nowadays, we use AES-GCM or ChaCha20-Poly1305 with TLS 1.3.

The story with SSH is similar, and there’s a lot of overlap in the user experience of configuring SSL/TLS for webservers and configuring OpenSSH. Even PGP supported different ciphers and modes. Crypto agility was the norm for many years.

JSON Web Tokens (JWT) is the perfect example of what happens when you take “crypto agility” too far:

• An attacker can change the alg header’s value to none to allow for trivial existential forgery. This surprises users.
• An attacker can take an existing token that uses an asymmetric mode (RS256, ES256, etc.), change the alg to a symmetric mode (i.e. HS256), then use the public key (or a hash of the public key) as a symmetric key, and the verifier would just blindly accept it.

When you maximize “crypto agility”, you introduce dangerous levels of in-band protocol negotiation.

Crypto Agility tends to become a security problem: When an attacker can entirely decide how the target system behaves, they can often bypass your security controls entirely.

Therefore, anyone who speaks in favor of crypto agility should be very careful about what, precisely, they’re advocating for.

Vikram’s talk wasn’t clear about these nuances. At the opening of the Q&A session, I asked the following question:

How do you balance your proposal for crypto agility with the risks of in-band protocol negotiation?

He declined to answer this question directly. Instead, he directed me to email his CTO, John Leiseboer, adding, “He would be better able to speak to that.”

Art: LvJ

So I returned to my DEFCON hotel room and sent an email to the email address that was displayed on Vikram’s slideshow.

Soatok’s First Email to QuintessenceLabs

This was mostly an attempt to be diplomatic so as to not scare them off from responding:

Hi,

I attended your CEO’s talk at the Quantum Village at DEFCON 30. I was very interested in the subject, and Vikram’s delivery of the material was appropriate for the general audience. I did have one question, but he suggested that would be better answered by your CTO.

For a bit of background: I work in applied cryptography.

My question is, “How do you balance your proposal for crypto agility with the risks of in-band protocol negotiation?”

To add color to this question, consider the widely exploited standard, JSON Web Tokens. To change the cryptographic properties of a JWT, you only need to change the “alg” header. This is maximally agile.

Unfortunately, you can specify “none” as an algorithm. This surprises users: https://www.howmanydayssinceajwtalgnonevuln.com/

Additionally, an attacker can take a token signed with an asymmetric key (e.g. RSA), change the alg header to HMAC, and then use [a hash of] the asymmetric public key as if it were a symmetric HMAC key, and achieve trivial existential forgery.

The same concerns, I feel, will crop up when migrating to a hybrid post-quantum design. Cross-protocol interactions of the incorrect secret keys would, from by understanding of Vikram’s talk, be made possible if an attacker can mutate the metadata table.

There is a way out of this mess: Versioned Protocols. Using JWT as an example, a contrary proposal that can support cipher agility but only for ciphers (and constructions of ciphers) that cryptographers have approved is called PASETO. https://paseto.io

If a vulnerability in the current supported protocols (v3, v4) is discovered, the cryptographers behind PASETO will specify new modes (e.g. v5 and v6). Currently the only reason they’re considering any such migration is for hybrid post-quantum signatures (P384 + Dilithium, Ed25519 + Dilithium).

I think the general idea of crypto agility is the right direction for addressing the risk of cryptography relevant quantum computers, but I would caution against recreating the protocol foot-guns made possible by the wrong sort of agility.

Vikram suggested you would be able to speak more to how your designs take these threats into consideration. I’m very interested in this space and would love to learn more about how your designs work at a deeper level.

Thank you for your time,

Soatok

(Typos included in original email)

I didn’t hear back from them for several days, so I hunted down the CTO’s email address directly (thanks, old mailing list discussions!).

He quickly responded with this:

John Leiseboer’s First Response Email

Hi Soatok,

My apologies for not responding sooner. I’ve been travelling and in meetings across three time zones. It’s been difficult to find time to absorb your questions and put together a response.

Please give me a few more days to find some time to get back to you.

Regards,
John

I want to pause here and make something very clear: My actual question is the most basic and obvious question any credible security engineer that works with cryptography would ask in response to Vikram’s presentation.

Art: Swizz

If you were to claim, “Everyone should use crypto agility,” and don’t qualify that statement with nuance or context, then a follow-up question about the risks of crypto agility is inevitable.

If this question somehow doesn’t come up, you’re in the wrong room of the wrong security engineers when you rehearse your pitch.

Why, then, would the speaker not be prepared for such a question? Isn’t he routinely offering similar talks to policy experts for government agencies?

Why, also, would his company’s CTO not be able to readily answer the question without needing additional time to “absorb” this question and put together a response?

It’s not like I asked them to provide a machine-verifiable, formal proof of correctness for their proposals.

I only asked the most basic Cryptography Protocol Design 101 question in response to their assertion that “crypto agility” is something that “companies” should adopt.

The proof, the proof, the proof is invalid!

We don’t need no lemma–Proof by contradiction fail!

Fail, contradiction, fail!

With apologies to Rock Master Scott & The Dynamic Three

Was this company’s leadership blind-sided by the most basic question of the field of study they’re hoping to, at least in part, replace?

Did they fail to consider an attacker that alters the metadata associated with their encrypted data in order to convince the “agile” cryptosystems to misbehave?

I will update this post when I have an answer to these very interesting questions.

(Update) QuintessenceLabs Responds

This is one email, but I’m going to add my commentary between paragraph breaks.

Hello again Soatok,

I’ve just read your blog where you criticised Vikram’s DEFCON talk. I was disappointed that you couldn’t wait for me to get back to you with the more detailed response that I promised to provide you last night.

Mea culpa. If I don’t press “publish” when the iron is hot, these posts stay in rough draft hell for 12-15 months, and I wanted to get my feedback (and the necessary context for said feedback) to the Quantum Village.

The short answer to your question, “How do you balance your proposal for crypto agility with the risks of in-band protocol negotiation?”, is simply that our proposal does not permit in-band negotiation. I suppose I could have provided you with that simple answer, but I expected that you’d want more than that. And I certainly wanted to provide you more. So, with apologies to Winston Churchill, if I had more time I would have written a shorter response.

The problem with the term “crypto agility” is that it means different things to different people. In your case, you talk about the “crypto agility” of SSL/TLS, SSH and JWT. The problem, as you are aware, and point out in your email and blog, is that crypto agility, as implemented in these protocols, introduces security issues. At QuintessenceLabs we are well aware of the issues arising from the sort of crypto agility that provides too much flexibility to users (and attackers are a class of user as far as I’m concerned), and fails to account for imaginative use of the agile features.

Although I do not yet have access to Vikram’s slides, I will point out that the specific example used during the talk included encrypted credit card numbers and a separate metadata table that stored the algorithms used to encrypt said credit card numbers.

(He specifically spoke to upgrading from AES-128 to Kyber; which I thought was an odd proposition considering Kyber is a KEM not a symmetric cipher, but I dismissed that as misspeaking.)

Vikram’s metadata table proposal necessarily implies some kind of in-band negotiation, which is the bad type of crypto agility.

The following is taken from the introduction of an internal QuintessenceLabs Technical Note:

“The term “cryptographic agility” is defined within QuintessenceLabs as a key management capability that permits the coding of software applications without the application code needing to specify or refer to specific cryptographic algorithms, key lengths, modes of operation, or similar cryptographic details. This capability enables applications to migrate between key types and cryptographic algorithms without a need to update the application software.

Specification of key types, strengths, modes, and cryptographic algorithms, etc. is the responsibility of a key management administrator. The key management platform delivers key material and meta data to applications in such a way that the cryptographic service or library used by the application can perform cryptographic operations in accordance with the attributes attached to the key material.”

This would have been very useful to include in the DEFCON talk. (It would have also been helpful if the speaker was prepared to answer such questions about the proposal!)

I generally think developers shouldn’t even need to care about the ciphers and algorithms being used; only that they’re secure, fast, and appropriate for their security goals. i.e. While AES-256-GCM might be okay for many use cases, it’s not how you should be storing users’ passwords.

In this regard, it sounds like the actual proposal is closer to NaCl/libsodium’s crypto_box() API, except the underlying library can tolerate algorithm upgrades (e.g. from X25519 + Xsalsa20poly1305 to something like X25519/Kyber768 + XChaCha20 + BLAKE2b-MAC). Which is totally reasonable.

This is very similar to what I did with my open source cryptography library, after all. It wraps libsodium, and if I decided to upgrade it to be post-quantum secure, I could do so without my users noticing (except maybe some bandwidth and performance differences).

The simplest way to tolerate such upgrades, by the by, is to use some sort of versioning scheme (which is the non-agile crypto design), which is what I’ve been proposing all along.

Some key points to note about our implementation:

1. The application developer has absolutely no control over which algorithms, key lengths, modes of operation or other crypto-related attributes are used.
2. The cryptographic key is actually a “managed object”. It is a protected object that encapsulates the key values and attributes that define how the key is to be used, including attributes such as cryptographic algorithm, key length, mode of operation, permitted uses (e.g. encrypt, decrypt, sign, signature verify, MAC, wrap, unwrap, etc.), links to related managed objects (e.g. a private key has an attribute that is it’s associated public key identifier), not-before and not-after time stamps, and maximum usage limits after which the key must be retired for use for protect operations.
3. The cryptographic subsystem (whether that is an HSM, smart card, library, external service, …) presents a very simple API. Again from our internal Technical Note (was this in Vikram’s presentation?):

This is actually reasonable! Per Sophie Schmieg:

https://twitter.com/SchmiegSophie/status/1264567198091079681

“The application code is responsible for the business logic of the application. The application code makes no low level and direct cryptographic calls. Instead, it makes calls that abstract away the cryptographic details.

An example of how this may work is as follows:

protected_data = protect(sensitive_data, policy);

In this example the sensitive data is the data to be protected, the policy indicates what type of data, or type of protection is required, and the result returned is the protected data. More specifically, the policy could be a template name such as “CCN-Policy”, which might be used for protecting credit card numbers.”

I’m not sure I like this API (protect is way too vague), but the intent is much clearer than some vague notion of “crypto agility”.

The application is responsible for understanding the type of information it is working with. It needs to know whether it’s handling sensitive data or not. It needs to know whether sensitive data needs to be protected. It needs to know the classification of, or how to classify, the data. I think that’s reasonable, after all the application is implementing the business logic.

Why not simply encrypt everything by default and let developers specifically opt out for data classified as not sensitive?

Then if a developer adds a field down the road and somehow forgets to classify it, the database administrator only ever sees ciphertext.

So as the pseudo code above illustrates, the application passes the sensitive data and the classification (encoded in the ‘policy’ attribute) to the cryptographic subsystem to figure out what to do cryptographically.

If you can avoid developers having to even care about these details, while still getting the details right, that’s a win.

1. The policy that defines the cryptographic attributes is separately managed. In the case of QuintessenceLabs’ products, this is the responsibility of a key management administrator, or a security officer, who has a cryptographic policy management role.
2. The returned, protected data is an object, or structure that encapsulates not only the result of the cryptographic operation, but attributes that allow the inverse operation (“unprotect”) to be performed by the crypto subsystem.

This is actually not clownshoes. Thankfully.

1. The policy can be changed at any time. This the agile part of the implementation. Today the policy says use AES-128-CBC, tomorrow is says use AES-256-GCM.

So, a couple of things about this specific example.

1. AES-128-CBC is vulnerable to padding oracle attacks.
2. If you support both AES-CBC and AES-GCM in the same code path, you can use the legacy CBC mode support to trigger a padding oracle attack to decrypt GCM ciphertexts.

Isn’t cryptography fun?

Art: Swizz

Adaptive attacks aside, cryptography migrations are way more challenging that your technical description implies. You’re going to have to do the following, in this specific order.

1. Make sure your entire fleet can decrypt messages AES-GCM ciphertexts before any machine writes any data using AES-GCM.
2. Only after step 1 is complete, you can upgrade your fleet to start writing records with AES-GCM.
3. Re-encrypt all old records to use AES-GCM instead of AES-CBC.
4. Turn off support for the legacy CBC mode.

If you attempt to move onto step 2 before step 1 is finished, you will find your network in a split-brain scenario where freshly-encrypted data cannot be read by some machines.

If you attempt to move onto step 3 before step 2 is finished, you will find some machines are still writing the legacy format.

If you attempt to move onto step 4 before step 3 is finished, you will lose access to some subset of old encrypted data.

Art: LvJ

It’s simply not possible to design a “crypto agile” application at any significant scale that totally avoids any window of downgrade susceptibility without also losing access to old encrypted data.

Until your entire network has reached step 4, you’re necessarily going to be vulnerable to in-band negotiation.

Also if you’re using the same key for multiple records (or the same wrapping key for multiple data keys), you’re going to read up on symmetric wear-out and the birthday paradox.

HKDF helps, but it has a specific way it needs to be used in security proofs.

Obviously as new algorithms are introduced, the crypto subsystem will need to be upgraded. But the application should not have to be changed.

Please feel free to ask more questions. But please be patient. Right now I’m sitting at the check-in gate at Dulles Airport using a laptop with a battery rapidly running down. For the next 30 or so hours I’ll be flying back home to Australia. I’m always happy to receive questions. I would ask though that you have some respect for my time and give me a chance to catch my wind before you publish an article without allowing me the time to respond properly.

The technical details that were absent from the DEFCON talk I watched, which only cryptographers and security engineers will really care about, were essential and should have been included.

I still disagree about the properties of their proposed “crypto agility” in practice (especially at cloud scale, which seems to be where QuintessenceLabs’ CEO wants to operate), but at least this is a much more reasonable proposal.

(The remainder of this blog post remains unchanged from what was written before John’s reply was edited in.)

Against Quantum Key Distribution

While the response to my question about “crypto agility” was disappointing, their argument for Quantum Key Distribution is just weird.

Quantum Key Distribution (QKD) doesn’t scale well enough to protect consumers.

Suppose you’re accessing a brand new computer and want to login to your bank’s website to check your account balance. In this scenario, QKD is useless for you: You haven’t established a secure channel via quantum entanglement yet. You probably don’t even have the hardware or optic channel necessary to do so.

QuintessenceLabs doesn’t acknowledge this scaling issue explicitly in their Quantum Village slides. Instead, they pitch QKD as a solution for businesses (rather than users) that want to add a layer of quantum security to their Key Management Services (described vaguely as “interacting with HSMs”).

I’m not sure who exactly their intended audience is with this sales pitch: Are they trying to sell this to, or compete with, large cloud providers?

Art: LvJ

Either way, this isn’t the sort of thing that resonates well with most hackers (who are more aligned with protecting users than protecting companies), so DEFCON isn’t really the best venue for such a sales pitch.

To their credit, they don’t entirely handwave post-quantum cryptography as a solution to cryptography relevant quantum computers. Instead, they claim that QKD is an “optional” way to protect communications when post-quantum cryptography is broken. Vikram comes short of describing these algorithmic breaks as “inevitable” in his presentation.

Here’s the rub: QKD isn’t magic.

Just as the correct response to, “What’s your threat model?” isn’t, “Well why don’t you try to disprove Heisenberg? Checkmate atheists!” the solution to quantum computing isn’t to throw all of discrete mathematics out with the bathwater in favor of relying only on quantum entanglement.

Even if you assume that the physical properties being leveraged to secure QKD cannot be directly defeated, you still have to deal with side-channel attacks. Et cetera.

That’s not to say that QKD research isn’t valuable or interesting. But I would strongly caution anyone who’s considering deploying it in production to talk to cryptographers and other security experts first.

We’re here to help!
Art: Harubaki

Burning Trust at DEFCON 30

DEFCON isn’t at all a vendor expo like Black Hat USA where you send sales drones to hock blinkenboxen that claim to secure networks.

DEFCON is where serious researchers and eccentric geeks exchange 0days for cocktails and solve interesting technical challenges.

https://twitter.com/telechallenge/status/1558891761610723330

My point is: If you present bullshit at DEFCON, you will be called out on it.

When I sat down at the Quantum Village to watch Vikram’s presentation, I honestly wanted it to not be bullshit.

After all, a lot of talented hackers lack refinement in public speaking, especially with talk abstracts. Conversely, a lot of business people (i.e. the CEO of a company) might be so accustomed to writing abstracts for a different audience, even if they ultimately deliver a hacker-focused talk in the end.

Therefore, in my mind, it’s possible that the content of the talk would be surprisingly excellent. Unfortunately, I left disappointed.

I can’t help but wonder if Vikram’s company being one of the four sponsors for the nascent Quantum Village prevented the necessary bullshit filter from being utilized to screen his talk.

He, and his employees, might rightfully claim to be experts on quantum technology, but they certainly don’t understand cryptography as well as they like to believe.

The thought of a sponsor bypassing the bullshit filter certainly makes me a little distrustful of the Quantum Village going into DEFCON 31.

Recommendation for DEFCON 31 and Beyond

The Quantum Village should reach out to the Crypto & Privacy Village to help review any talks that involve cryptography, moving forward.

This will help in two ways:

1. Cryptography and privacy experts will be involved in the process.
2. Someone who doesn’t have a perverse incentive will likely be involved in the process, which makes it easier to tell a sponsor, “Hell no.”

A particularly motivated bullshit artist with sufficient capital might simply sponsor both villages, so it’s not 100% foolproof, but you can always count on weirdos in fursuits like me to be the last line of defense, should all else fail.

Update:

https://twitter.com/FiloSottile/status/1560165504312135680

I stand corrected. This attack vector won’t work. Thanks, Filippo!

Closing Thoughts

I was originally going to delay publishing this until QuintessenceLabs had a chance to respond to my question, or at least until all of the slide decks were published (so I could cite them carefully in my critique), but I honestly wanted to get my recommendation off my chest and in the hands of the Quantum Village organizers before I get distracted by the work that piled up while I was at DEFCON.

I might blog for free, but that doesn’t mean I don’t have a job to do, or bills to pay.

If you (or someone you work for) were sold on “crypto agility”, consider versioned protocols instead. And if you’re going to invest in custom hardware, take a page out of Nintendo’s book: simply burn fuses with each new protocol version to prevent downgrade attacks.

You probably don’t need quantum encryption to solve any of the problems you face in the immediate future.

https://soatok.blog/2022/08/18/burning-trust-at-the-quantum-village-at-defcon-30/

#cryptographicProtocols #cryptography #DEFCON #inBandNegotiation #JWT #postQuantumCryptography #QKD #QuantumEncryption #QuantumKeyDistribution #QuantumVillage #QuintessenceLabs #QuintessenceLabs #securityEngineering #VikramSharma

Dhole Moments

2020-07-09 09:28:32

Sometimes my blog posts end up on social link-sharing websites with a technology focus, such as Lobste.rs or Hacker News.

On a good day, this presents an opportunity to share one’s writing with a larger audience and, more importantly, solicit a wider variety of feedback from one’s peers.

However, sometimes you end up with feedback like this, or this:

Apparently my fursona is ugly, and therefore I’m supposed to respect some random person’s preferences and suppress my identity online.

I’m no stranger to gatekeeping in online communities, internet trolls, or bullying in general. This isn’t my first rodeo, and it won’t be my last.

These kinds of comments exist to send a message not just to me, but to anyone else who’s furry or overtly LGBTQIA+: You’re weird and therefore not welcome here.

Of course, the moderators rarely share their views.

https://twitter.com/pushcx/status/1281207233020379137

Because of their toxic nature, there is only one appropriate response to these kinds of comments: Loud and persistent spite.

So here’s some more art I’ve commissioned or been gifted of my fursona over the years that I haven’t yet worked into a blog post:

Art by kazetheblaze
Art by leeohfox
Art by Diffuse Moose

If you hate furries so much, you will be appalled to learn that factoids about my fursona species have landed in LibreSSL’s source code (decoded).

Never underestimate furries, because we make the Internets go.

I will never let these kind of comments discourage me from being open about my hobbies, interests, or personality. And neither should anyone else.

If you don’t like my blog posts because I’m a furry but still find the technical content interesting, know now and forever more that, when you try to push me or anyone else out for being different, I will only increase the fucking thing.

---

Header art created by @loviesophiee and inspired by floccinaucinihilipilification.

https://soatok.blog/2020/07/09/a-word-on-anti-furry-sentiments-in-the-tech-community/

#antiFurryBullying #cyberculture #furry #HackerNews #LobsteRs #Reddit

I don’t consider myself exceptional in any regard, but I stumbled upon a few cryptography vulnerabilities in Matrix’s Olm library with so little effort that it was nearly accidental.

It should not be this easy to find these kind of issues in any product people purportedly rely on for private messaging, which many people evangelize incorrectly as a Signal alternative.

Later, I thought I identified an additional vulnerability that would have been much worse, but I was wrong about that one. For the sake of transparency and humility, I’ll also describe that in detail.

This post is organized as follows:

• Disclosure Timeline
• Vulnerabilities in Olm (Technical Details)
• Recommendations
• Background Information
• An Interesting Non-Issue That Looked Critical

I’ve opted to front-load the timeline and vulnerability details to respect the time of busy security professionals.

Please keep in mind that this website is a furry blog, first and foremost, that sometimes happens to cover security and cryptography topics.

Many people have, over the years, assumed the opposite and commented accordingly. The ensuing message board threads are usually is a waste of time and energy for everyone involved. So please adjust your expectations.

Art by Harubaki

If you’re curious, you can learn more here.

Disclosure Timeline

• 2024-05-15: I took a quick look at the Matrix source code. I identified two issues and emailed them to their security@ email address.
  In my email, I specify that I plan to disclose my findings publicly in 90 days (i.e. on August 14), in adherence with industry best practices for coordinated disclosure, unless they request an extension in writing.
• 2024-05-16: I checked something else on a whim and find a third issue, which I also email to their security@ email address.
• 2024-05-17: Matrix security team confirms receipt of my reports.
• 2024-05-17: I follow up with a suspected fourth finding–the most critical of them all. They point out that it is not actually an issue, because I overlooked an important detail in how the code is architected. Mea culpa!
• 2024-05-18: A friend discloses a separate finding with Matrix: Media can be decrypted to multiple valid plaintexts using different keys and Malicious homeservers can trick Element/Schildichat into revealing links in E2EE rooms.
  They instructed the Matrix developers to consult with me if they needed cryptography guidance. I never heard from them on this externally reported issue.
• 2024-07-12: I shared this blog post draft with the Matrix security team while reminding them of the public disclosure date.
• 2024-07-31: Matrix pushes a commit that announces that libolm is deprecated.
• 2024-07-31: I email the Matrix security team asking if they plan to fix the reported issues (and if not, if there’s any other reason I should withhold publication).
• 2024-07-31: Matrix confirms they will not fix these issues (due to its now deprecated status), but ask that I withhold publication until the 14th as originally discussed.
• 2024-08-14: This blog post is publicly disclosed to the Internet.
• 2024-08-14: The lead Matrix dev claims they already knew about these issues, and, in fact, knowingly shipped cryptography code that was vulnerable to side-channel attacks for years. See Addendum.
• 2024-08-23: MITRE has assigned CVE IDs to these three findings.

Vulnerabilities in Olm

I identified the following issues with Olm through a quick skim of their source code on Gitlab:

1. AES implementation is vulnerable to cache-timing attacks
2. Ed25519 signatures are malleable
3. Timing leakage in base64 decoding of private key material

This is sorted by the order in which they were discovered, rather than severity.

AES implementation is vulnerable to cache-timing attacks

a.k.a. CVE-2024-45191

Olm ships a pure-software implementation of AES, rather than leveraging hardware acceleration.

// Substitutes a word using the AES S-Box.WORD SubWord(WORD word){unsigned int result;result = (int)aes_sbox[(word >> 4) & 0x0000000F][word & 0x0000000F];result += (int)aes_sbox[(word >> 12) & 0x0000000F][(word >> 8) & 0x0000000F] << 8;result += (int)aes_sbox[(word >> 20) & 0x0000000F][(word >> 16) & 0x0000000F] << 16;result += (int)aes_sbox[(word >> 28) & 0x0000000F][(word >> 24) & 0x0000000F] << 24;return(result);}

The code in question is called from this code, which is in turn used to actually encrypt messages.

Software implementations of AES that use a look-up table for the SubWord step of the algorithm are famously susceptible to cache-timing attacks.

This kind of vulnerability in software AES was previously used to extract a secret key from OpenSSL and dm-crypt in about 65 milliseconds. Both papers were published in 2005.

A general rule in cryptography is, “attacks only get better; they never get worse“.

As of 2009, you could remotely detect a timing difference of about 15 microseconds over the Internet with under 50,000 samples. Side-channel exploits are generally statistical in nature, so such a sample size is generally not a significant mitigation.

How is this code actually vulnerable?

In the above code snippet, the vulnerability occurs in
aes_sbox[/* ... */][/* ... */].

Due to the details of how the AES block cipher works, the input variable (word) is a sensitive value.

Software written this way allows attackers to detect whether or not a specific value was present in one of the processor’s caches.

To state the obvious: Cache hits are faster than cache misses. This creates an observable timing difference.

Such a timing leak allows the attacker to learn the value that was actually stored in said cache. You can directly learn this from other processes on the same hardware, but it’s also observable over the Internet (with some jitter) through the normal operation of vulnerable software.

See also: cryptocoding’s description for table look-ups indexed by secret data.

How to mitigate this cryptographic side-channel

The correct way to solve this problem is to use hardware accelerated AES, which uses distinct processor features to implement the AES round function and side-steps any cache-timing shenanigans with the S-box.

Not only is this more secure, but it’s faster and uses less energy too!

If you’re also targeting devices that don’t have hardware acceleration available, you should first use hardware acceleration where possible, but then fallback to a bitsliced implementation such as the one in Thomas Pornin’s BearSSL.

See also: the BearSSL documentation for constant-time AES.

Art by AJ

Ed25519 signatures are malleable

a.k.a. CVE-2024-45193

Ed25519 libraries come in various levels of quality regarding signature validation criteria; much to the chagrin of cryptography engineers everywhere. One of those validation criteria involves signature malleability.

Signature malleability usually isn’t a big deal for most protocols, until suddenly you discover a use case where it is. If it matters, that usually that means you’re doing something with cryptocurrency.

Briefly, if your signatures are malleable, that means you can take an existing valid signature for a given message and public key, and generate a second valid signature for the same message. The utility of this flexibility is limited, and the impact depends a lot on how you’re using signatures and what properties you hope to get out of them.

For ECDSA, this means that for a given signature , a second signature is also possible (where is the order of the elliptic curve group you’re working with).

Matrix uses Ed25519, whose malleability is demonstrated between and .

This is trivially possible because S is implicitly reduced modulo the order of the curve, , which is a 253-bit number (0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed) and S is encoded as a 256-bit number.

The Ed25519 library used within Olm does not ensure that , thus signatures are malleable. You can verify this yourself by looking at the Ed25519 verification code.

int ed25519_verify(const unsigned char *signature, const unsigned char *message, size_t message_len, const unsigned char *public_key) { unsigned char h[64]; unsigned char checker[32]; sha512_context hash; ge_p3 A; ge_p2 R; if (signature[63] & 224) { return 0; } if (ge_frombytes_negate_vartime(&A, public_key) != 0) { return 0; } sha512_init(&hash); sha512_update(&hash, signature, 32); sha512_update(&hash, public_key, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, h); sc_reduce(h); ge_double_scalarmult_vartime(&R, h, &A, signature + 32); ge_tobytes(checker, &R); if (!consttime_equal(checker, signature)) { return 0; } return 1;}

This is almost certainly a no-impact finding (or low-impact at worst), but still an annoying one to see in 2024.

If you’d like to learn more, this page is a fun demo of Ed25519 malleability.

To mitigate this, I recommend implementing these checks from libsodium.

Art: CMYKat

Timing leakage in base64 decoding of private key material

a.k.a. CVE-2024-45192

If you weren’t already tired of cache-timing attacks based on table look-ups from AES, the Matrix base64 code is also susceptible to the same implementation flaw.

while (pos != end) { unsigned value = DECODE_BASE64[pos[0] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[1] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[2] & 0x7F]; value <<= 6; value |= DECODE_BASE64[pos[3] & 0x7F]; pos += 4; output[2] = value; value >>= 8; output[1] = value; value >>= 8; output[0] = value; output += 3;}

The base64 decoding function in question is used to load the group session key, which means the attack published in this paper almost certainly applies.

How would you mitigate this leakage?

Steve Thomas (one of the judges of the Password Hashing Competition, among other noteworthy contributions) wrote some open source code a while back that implements base64 encoding routines in constant-time.

The real interesting part is how it avoids a table look-up by using arithmetic (from this file):

// Base64 character set:// [A-Z] [a-z] [0-9] + /// 0x41-0x5a, 0x61-0x7a, 0x30-0x39, 0x2b, 0x2finline int base64Decode6Bits(char src){int ch = (unsigned char) src;int ret = -1;// if (ch > 0x40 && ch < 0x5b) ret += ch - 0x41 + 1; // -64ret += (((0x40 - ch) & (ch - 0x5b)) >> 8) & (ch - 64);// if (ch > 0x60 && ch < 0x7b) ret += ch - 0x61 + 26 + 1; // -70ret += (((0x60 - ch) & (ch - 0x7b)) >> 8) & (ch - 70);// if (ch > 0x2f && ch < 0x3a) ret += ch - 0x30 + 52 + 1; // 5ret += (((0x2f - ch) & (ch - 0x3a)) >> 8) & (ch + 5);// if (ch == 0x2b) ret += 62 + 1;ret += (((0x2a - ch) & (ch - 0x2c)) >> 8) & 63;// if (ch == 0x2f) ret += 63 + 1;ret += (((0x2e - ch) & (ch - 0x30)) >> 8) & 64;return ret;}

Any C library that handles base64 codecs for private key material should use a similar implementation. It’s fine to have a faster base64 implementation for non-secret data.

Worth noting: Libsodium also provides a reasonable Base64 codec.

Recommendations

These issues are not fixed in libolm.

Instead of fixing libolm, the Matrix team recommends all Matrix clients adopt vodozemac.

I can’t speak to the security of vodozemac.

Art: CMYKat

But I can speak against the security of libolm, so moving to vodozemac is probably a good idea. It was audited by Least Authority at one point, so it’s probably fine.

Most Matrix clients that still depended on libolm should treat this blog as public 0day, unless the Matrix security team already notified you about these issues.

Background Information

If you’re curious about the backstory and context of these findings, read on.

Otherwise, feel free to skip this section. It’s not pertinent to most audiences. The people that need to read it already know who they are.

End-to-end encryption is one of the topics within cryptography that I find myself often writing about.

In 2020, I wrote a blog post covering end-to-end encryption for application developers. This was published several months after another blog I wrote covering gripes with AES-GCM, which included a shallow analysis of how Signal uses the algorithm for local storage.

In 2021, I published weaknesses in another so-called private messaging app called Threema.

In 2022, after Elon Musk took over Twitter, I joined the Fediverse and sought to build end-to-end encryption support for direct messages into ActivityPub, starting with a specification. Work on this effort was stalled while trying to solve Public Key distribution in a federated environment (which I hope to pick up soon, but I digress).

Earlier this year, the Telegram CEO started fearmongering about Signal with assistance from Elon Musk, so I wrote a blog post urging the furry fandom to move away from Telegram and start using Signal more. As I had demonstrated years prior, I was familiar with Signal’s code and felt it was a good recommendation for security purposes (even if its user experience needs significant work).

I thought that would be a nice, self-contained blog post. Some might listen, most would ignore it, but I could move on with my life.

I was mistaken about that last point.

Art by AJ

An overwhelming number of people took it upon themselves to recommend or inquire about Matrix, which prompted me to hastily scribble down my opinion on Matrix so that I might copy/paste a link around and save myself a lot of headache.

Just when I thought the firehose was manageable and I could move onto other topics, one of the Matrix developers responded to my opinion post.

Thus, I decided to briefly look at their source code and see if any major or obvious cryptography issues would fall out of a shallow visual scan.

Since you’re reading this post, you already know how that ended.

Credit: CMYKat

Since the first draft of this blog post was penned, I also outlined what I mean when I say an encrypted messaging app is a Signal competitor or not, and published my opinion on XMPP+OMEMO (which people also recommend for private messaging).

Why mention all this?

Because it’s important to know that I have not audited the Olm or Megolm codebases, nor even glanced at their new Rust codebase.

The fact is, I never intended to study Matrix. I was annoyed into looking at it in the first place.

My opinion of their project was already calcified by the previously discovered practically-exploitable cryptographic vulnerabilities in Matrix in 2022.

The bugs described above are the sort of thing I mentally scan for when I first look at a project just to get a feel for the maturity of the codebase. I do this with the expectation (hope, really) of not finding anything at all.

(If you want two specific projects that I’ve subjected to a similar treatment, and failed to discover anything interesting in: Signal and WireGuard. These two set the bar for cryptographic designs.)

It’s absolutely bonkers that an AES cache timing vulnerability was present in their code in 2024.

It’s even worse when you remember that I was inundated with Matrix evangelism in response to recommending furries use Signal.

I’m a little outraged because of how irresponsible this is, in context.

It’s so bad that I didn’t even need to clone their git repository, let alone run basic static analysis tools locally.

So if you take nothing else away from this blog post, let it be this:

There is roughly a 0% chance that I got extremely lucky in my mental grep and found the only cryptography implementation flaws in their source code. I barely tried at all and found these issues.

I would bet money on there being more bugs or design flaws that I didn’t find, because this discovery was the result of an extremely half-assed effort to blow off steam.

Wasn’t libolm deprecated in May 2022?

The Matrix developers like to insist that their new Rust hotness “vodozemac” is what people should be using today.

I haven’t looked at vodozemac at all, but let’s pretend, for the sake of argument, that its cryptography is actually secure.

(This is very likely if they turn out to be using RustCrypto for their primitives, but I don’t have the time or energy for that nerd snipe, so I’m not going to look. Least Authority did audit their Rust library, for what it’s worth, and Least Authority isn’t clownshoes.)

It’s been more than 2 years since they released vodozemac. What does the ecosystem penetration for this new library look like, in practice?

A quick survey of the various Matrix clients on GitHub says that libolm is still the most widely used cryptography implementation in the Matrix ecosystem (as of this writing):

3 of the 16 clients surveyed use the new vodozemac library. 10 still use libolm, and 3 don’t appear to implement end-to-end encryption at all.

If we only focus on clients that support E2EE, vodozemac has successfully been adopted by 19% of the open source Matrix clients on GitHub.

I deliberately excluded any repositories that were archived or clearly marked as “old” or “legacy” software, because including those would artificially inflate the representation of libolm. It would make for a more compelling narrative to do so, but I’m not trying to be persuasive here.

Deprecation policies are a beautiful lie. The impact of a vulnerability in Olm or Megolm is still far-reaching, and should be taken seriously by the Matrix community.

Worth calling out: this quick survey, which is based on a GitHub Topic, certainly misses other implementations. Both FluffyChat and Cinny, which were not tagged with this GitHub Topic, depend a language-specific Olm binding.

These bindings in turn wrap libolm rather than the Rust replacement, vodozemac.

But the official clients…

I thought the whole point of choosing Matrix over something like Signal is to be federated, and run your own third-party clients?

If we’re going to insist that everyone should be using Element if they want to be secure, that defeats the entire marketing point about third-party clients that Matrix evangelists cite when they decry Signal’s centralization.

So I really don’t want to hear it.

CMYKat

An Interesting Non-Issue That Looked Critical

As I mentioned in the timeline at the top, I thought I found a fourth issue with Matrix’s codebase. Had I been correct, this would have been a critical severity finding that the entire Matrix ecosystem would need to melt down to remediate.

Fortunately for everyone, I made a mistake, and there is no fourth vulnerability after all.

However, I thought it would be interesting to write about what I thought I found, the impact it would have had if it were real, and why I believed it to be an issue.

Let’s start with the code in question:

void ed25519_sign(unsigned char *signature, const unsigned char *message, size_t message_len, const unsigned char *public_key, const unsigned char *private_key) { sha512_context hash; unsigned char hram[64]; unsigned char r[64]; ge_p3 R; sha512_init(&hash); sha512_update(&hash, private_key + 32, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, r); sc_reduce(r); ge_scalarmult_base(&R, r); ge_p3_tobytes(signature, &R); sha512_init(&hash); sha512_update(&hash, signature, 32); sha512_update(&hash, public_key, 32); sha512_update(&hash, message, message_len); sha512_final(&hash, hram); sc_reduce(hram); sc_muladd(signature + 32, hram, private_key, r);}

The highlighted segment is doing pointer arithmetic. This means it’s reading 32 bytes, starting from the 32nd byte in private_key.

What’s actually happening here is: private_key is the SHA512 hash of a 256-bit seed. If you look at the function prototype, you’ll notice that public_key is a separate input.

Virtually every other Ed25519 implementation I’ve ever looked at before expected users to provide a 32 byte seed followed by the public key as a single input.

This led me to believe that this private_key + 32 pointer arithmetic was actually using the public key for calculating r.

The variable r (not to be confused with big R) generated via the first SHA512 is the nonce for a given signature, it must remain secret for Ed25519 to remain secure.

If r is known to an attacker, you can do some arithmetic to recover the secret key from a single signature.

Because I had mistakenly believed that r was calculated from the SHA512 of only public inputs (the public key and message), which I must emphasize isn’t correct, I had falsely concluded that any previously intercepted signature could be used to steal user’s private keys.

Credit: CMYKat

But because private_key was actually the full SHA512 hash of the seed, rather than the seed concatenated with the public key, this pointer arithmetic did NOT use the public key for the calculation of r, so this vulnerability does not exist.

If the code did what I thought it did, however, this would have been a complete fucking disaster for the Matrix ecosystem. Any previously intercepted message would have allowed an attacker to recover a user’s secret key and impersonate them. It wouldn’t be enough to fix the code; every key in the ecosystem would need to be revoked and rotated.

Whew!

I’m happy to be wrong about this one, because that outcome is a headache nobody wants.

So no action is needed, right?

Well, maybe.

Matrix’s library was not vulnerable, but I honestly wouldn’t put it past software developers at large to somehow, somewhere, use the public key (rather than a secret value) to calculate the EdDSA signature nonces as described in the previous section.

To that end, I would like to propose a test vector be added to the Wycheproof test suite to catch any EdDSA implementation that misuses the public key in this way.

Then, if someone else screws up their Ed25519 implementation in the exact way I thought Matrix was, the Wycheproof tests will catch it.

For example, here’s a vulnerable test input for Ed25519:

{ "should-fail": true, "secret-key": "d1d0ef849f9ec88b4713878442aeebca5c7a43e18883265f7f864a8eaaa56c1ef3dbb3b71132206b81f0f3782c8df417524463d2daa8a7c458775c9af725b3fd", "public-key": "f3dbb3b71132206b81f0f3782c8df417524463d2daa8a7c458775c9af725b3fd", "message": "Test message", "signature": "ffc39da0ce356efb49eb0c08ed0d48a1cadddf17e34f921a8d2732a33b980f4ae32d6f5937a5ed25e03a998e4c4f5910c931b31416e143965e6ce85b0ea93c09"}

A similar test vector would also be worth creating for Ed448, but the only real users of Ed448 were the authors of the xz backdoor, so I didn’t bother with that.

(None of the Project Wycheproof maintainers knew this suggestion is coming, by the way, because I was respecting the terms of the coordinated disclosure.)

Closing Thoughts

Despite finding cryptography implementation flaws in Matric’s Olm library, my personal opinion on Matrix remains largely unchanged from 2022. I had already assumed it would not meet my bar for security.

Cryptography engineering is difficult because the vulnerabilities you’re usually dealing with are extremely subtle. (Here’s an unrelated example if you’re not convinced of this general observation.) As SwiftOnSecurity once wrote:

https://twitter.com/SwiftOnSecurity/status/832058185049579524

The people that developed Olm and Megolm has not proven themselves ready to build a Signal competitor. In balance, most teams are not qualified to do so.

I really wish the Matrix evangelists would accept this and stop trying to cram Matrix down other people’s throats when they’re talking about problems with other platforms entirely.

More important for the communities of messaging apps:

You don’t need to be a Signal competitor. Having E2EE is a good thing on its own merits, and really should be table stakes for any social application in 2024.

It’s only when people try to advertise their apps as a Signal alternative (or try to recommend it instead of Signal), and offer less security, that I take offense.

Just be your own thing.

My work-in-progress proposal to bring end-to-end encryption to the Fediverse doesn’t aim to compete with Signal. It’s just meant to improve privacy, which is a good thing to do on its own merits.

If I never hear Matrix evangelism again after today, it would be far too soon.

If anyone feels like I’m picking on Matrix, don’t worry: I have far worse things to say about Telegram, Threema, XMPP+OMEMO, Tox, and a myriad other projects that are hungry for Signal’s market share but don’t measure up from a cryptographic security perspective.

If Signal fucked up as bad as these projects, my criticism of Signal would be equally harsh. (And remember, I have looked at Signal before.)

Addendum (2024-08-14)

One of the lead Matrix devs posted a comment on Hacker News after this blog post went live that I will duplicate here:

the author literally picked random projects from github tagged as matrix, without considering their prevalence or whether they are actually maintained etc.

if you actually look at % of impacted clients, it’s tiny.

meanwhile, it is very unclear that any sidechannel attack on a libolm based client is practical over the network (which is why we didn’t fix this years ago). After all, the limited primitives are commented on in the readme and https://github.com/matrix-org/olm/issues/3 since day 1.

So the Matrix developers already knew about these vulnerabilities, but deliberately didn’t fix them, for years.

Congratulations, you’ve changed my stance. It used to be “I don’t consider Matrix a Signal alternative and they’ve had some embarrassing and impactful crypto bugs but otherwise I don’t care”. Now it’s a stronger stance:

Don’t use Matrix.

I had incorrectly assumed ignorance, when it was in fact negligence.

There’s no reasonable world in which anyone should trust the developers of cryptographic software (i.e., libolm) that deliberately ships with side-channels for years, knowing they’re present, and never bother to fix them.

This is fucking clownshoes.

https://soatok.blog/2024/08/14/security-issues-in-matrixs-olm-library/

#crypto #cryptography #endToEndEncryption #Matrix #sideChannels #vuln

Dhole Moments

2024-07-31 16:25:41

A lot of recent (and upcoming) blog posts I’ve written, and Fediverse discussions I’ve participated in, have been about the security of communication products.

My criticism of these products is simply that, from a cryptography and security perspective, they’re not a real competitor to Signal.

For all its other faults, Signal sets the bar for secure private messaging. It’s a solid security tool, even if its user experience and feature set leaves a lot of people disappointed. I highly recommend it over, say, Telegram.

In response to my post about jettisoning Telegram, quite a few people have tried to evangelize other products. For example:

Edit: Oh yeah, DON’T USE SIGNAL. Use Matrix instead, offers the benefits of signal without the drawbacks of lack of sync and phone number requirements and is decentralized. The fact that everyone is going gaga for signal as “the BEST messaging app” should be a big red flag in and of itself, because hype trains like this aren’t organic, just saying.

Draconic_NEO on pawb.social

So, let me explain what it means for a communication product to qualify as a Signal competitor from the perspective of someone whose job involves auditing cryptography implementations.

The Minimum Bar to Clear

Open Source

Every private messaging app must be open source in order to qualify as a Signal competitor.

If it’s not open source, it’s not even worth talking about.

End-to-End Encryption

Messages MUST be end-to-end encrypted. This means that you encrypt on one participant’s device, decrypt on another’s, and nobody in the middle can observe plaintext.

When I say MUST, I mean the RFC 2119 keyword.

There must never be a “transmit plaintext” option. No excuses. Secure cryptography is not interoperable with insecure cryptography. If you allow a “transmit plaintext” mode for any reason whatsoever, you have failed to build an encryption product that meets the bar.

This disqualifies Matrix.

This disqualifies Telegram.

This disqualifies XMPP + OMEMO.

This alone disqualifies a lot of so-called private messaging apps.

This doesn’t mean your product is insecure, or that I’m aware of any specific ways to break it.

It just doesn’t occupy the same mindshare as Signal, which only transmits encrypted data and doesn’t have a plaintext protocol to downgrade to.

Therefore, it’s not a goddamn Signal alternative.

How You Encrypt Matters

Signal normalized the use of AES-256-CBC with HMAC-SHA256.

Facebook’s “Secret Conversations” feature deviated from this and preferred AES-GCM for attachments, but this bit them when the Invisible Salamanders attack was discovered.

The way Signal uses AES+HMAC is fine for their use case, but building a secure committing AEAD mode (rather than merely AE) out of these primitives is nontrivial.

If you’re aiming to compete with Signal on security, you should, at minimum, expect to engage with a cryptography auditing firm at least once a year to review and re-review your protocol designs and implementations.

I Will Heavily Scrutinize Your Group Messaging Protocols

Group messaging is one of those topics that might sound easy if you can do peer-to-peer messaging securely, but is catastrophically difficult once you get into the details.

See also: My blog post about Threema.

If you want a starting point, look at RFC 9420 (Messaging Layer Security, which is a group key agreement protocol for messaging apps).

How You Manage Keys Matters

Tox attempted to build atop NaCl’s crypto_box interface, but this is not suitable for a general purpose secure messaging due to a lack of KCI Security.

Key management (which is the focus of an upcoming blog post) is a problem that almost everyone underestimates. It’s also the most user-facing aspect of these messaging applications.

WhatsApp uses Key Transparency to scale user trust. I’m proposing something similar for E2EE for the Fediverse.

This is a much better strategy than expecting users to manually verify “fingerprints”.

Don’t look at OpenPGP as a role model when it comes to user experience. Johnny still cannot fucking encrypt.

Your Feature Should Not Bypass Privacy

Want to add all sorts of frills, like video chat or some dumb bullshit with AI and/or blockchain to secure the attention of venture capitalist investors?

You’d better not implement them in such a way that leaks users’ messages or search queries to your service.

The main reason Signal is “missing” features is because they are thoughtful about how these features are designed and implemented.

Guess what happens if you prioritize shipping features over privacy and cryptography engineering?

That’s right: You stop being a contender for a Signal alternative.

So What?

If your fave isn’t a viable alternative to Signal, don’t fucking recommend it to people in response to me recommending Signal.

That’s all I ask.

Art: Scruff

But what about…?

I’m not here to discuss your use cases, or usability, or anything else. I’m also not saying that Signal is perfect!

Signal is a private messaging app that I would feel safe recommending whistleblowers to use. It meets all these requirements.

In order to be a Signal competitor, no matter how much you like your app, it needs to meet them too, otherwise it isn’t a Signal competitor. Them’s the rules!

AJ

There may be other requirements that are more important to you, that Signal doesn’t meet. That’s fine! You can like other things.

But unless your favorite widget also meets all of the things on this page, it’s not a valid competitor from a security and privacy perspective, and therefore I don’t want to fucking hear about it in response to me saying “use Signal until something better comes along”.

Capiche?

Addendum (2024-08-01)

Since I originally posted this, there have been a lot of opinions expressed and questions asked about messaging apps that have nothing to do with cryptographic security.

Those are good discussions to have, elsewhere. Hell, most of this discussion would be a better response to my other blog post than this one.

The goal of this post was to specify what the minimum bar is for a different app to qualify as a Signal competitor. It’s written from the perspective of someone whose career is in applied cryptography.

If you have thoughts, feelings, opinions, questions, or concerns about messaging apps (including but not limited to Signal), that’s wonderful.

But this specific blog post is not the correct place to voice them!

Especially if the first line of your response is “you’re too focused on [technology, security, cryptography] (select appropriate)”.

Because… no shit? That’s the entire point of this particular post. It’s narrowly scoped for a reason. Please respect that.

My upcoming vulnerability disclosure in Matrix will make the same point, but I wanted a separate, less distracting blog post to link people to when someone tries to evangelize another chat app instead of Signal, especially if they make security claims while doing so.

https://soatok.blog/2024/07/31/what-does-it-mean-to-be-a-signal-competitor/

#cryptography #endToEndEncryption #privateMessengers #Signal

XMPP is a messaging protocol (among other things) that needs no introduction to any technical audience. Its various implementations have proliferated through technical communities for decades.

Many large tech companies today used to run XMPP servers. However, the basic protocol transmitted plaintext. If you were lucky, it was plaintext over SSL/TLS, but servers could still see all of your message contents.

OMEMO (XEP-0384) is an attempt to staple end-to-end encryption onto the XMPP ecosystem.

It’s largely inspired by, and based on, an earlier version of the Signal protocol, so you might be tempted to believing that it’s good.

In my opinion, it’s not.

OMEMO is not the worst attempt at making XMPP encrypted (see: XEP-0027 for that), but it still doesn’t meet the bar for the kind of private messaging app that Signal is, and is not a viable competitor to Signal.

To understand why this is true, you only need check whether OMEMO is on by default (it isn’t), or whether OMEMO can be turned off even if your client supports it (it can).

Both of these conditions fail the requirements I outlined under the End-to-End Encryption header in that other blog post.

And that’s all that I should have needed to say on the matter.

Art: Harubaki

Unfortunately, the Internet is full of cargo cults built around specific technologies, and their followers have an emotional interest in muddying the waters.

Criticize one, and their rivals will come out of the woodwork to say, “This is why I use $FooBar instead of $BazQuux!” and insist that their preferred solution is the secure one–with all the confident incorrectness of a climate change denier.

Art: AJ

Let me explain why I don’t recommend XMPP and OMEMO for private messaging.

But before I do, a quick reminder that me criticizing XMPP+OMEMO isn’t an endorsement of weird or stupid alternatives, like using PGP.

Also, this post is about the entire XMPP + OMEMO ecosystem, not just the OMEMO specification.

Art: ScruffKerfluff

Why People Like XMPP

Quite simply, people like XMPP because it’s federated, which means they can control who gets access to their data. This is also one reason why people like Matrix, Mastodon, NextCloud, etc. It gives them a sense of control over their data that a centralized platform doesn’t. You can feel like you’re controlling your own destiny, whether or not that’s true. And those emotions can be a powerful thing.

Unlike Moxie, I don’t inherently think federated technology is always bad.

There are mechanisms you can employ to roll the entire ecosystem forward and keep everyone up-to-date with security fixes to an underlying protocol. Being frozen in time is a real problem in federation, but not an inevitability.

Unfortunately, XMPP is the perfect exhibit for anyone that wants to argue in favor of Moxie’s perspective on federation.

OMEMO Problem 1: Protocol Freeze

When I decided to set out to survey the XMPP+OMEMO ecosystem, the first question that came to mind is, “Which implementation is everyone using?”

The answer is probably Conversations. Other answers I heard were Gajim and forks of Conversations.

We’ll get back to Conversations later, but right now, I want to address a bigger problem with the XMPP+OMEMO ecosystem.

The latest draft of XEP-0384 is version 0.8.3, published in January 2022.

Despite this, almost every OMEMO implementation I can find is still on version 0.3.0 (or earlier) of the OMEMO specification.

Art: CMYKat

The easiest way to tell if they aren’t implementing version 0.4.0 or newer is the absence of AES-256-CBC in their codebase.

See for yourself. All of the following implement version 0.3.0 or older of the OMEMO specification:

• libomemo, dependents:
  
  • weechat-xmpp

  
  

• Conversations, forks:
  
  • blabber.im
  • Monocles
  • Quicksy
  • Snikket

  
  

• Converse.js
• Gajim
• jaxmpp, dependents:
  
  • Stork IM

  
  

• jabber-web
• MartinOMEMO, dependents:
  
  • Siskin IM

  
  

The only implementations I found that supported newer protocol versions were Profanity and Kaidan (via QXmpp).

EDIT: Thanks to tant for pointing me to this list of versions.

What To Even Focus On?

A question comes to mind: Which version of the specification should an enterprising security researcher look at?

Art: CMYKat

The latest version available online, or an ancient version that’s still widely used?

If I find a problem in the latest draft of the specification, some will say that’s a non-issue because the spec is “experimental” and therefore should not implemented yet.

If I find a problem in the older draft of the specification, some will insist that those are known problems with an older version of the spec, and that people “should” be on the newer version if they expect to be secure.

Even worse, there’s probably some overlap between the two sets of people.

Regardless, anyone who’s vested in improving the security of the XMPP+OMEMO ecosystem is at an impasse right out of the gate. That’s not a good place to be in.

OMEMO Problem 2: YOLO Crypto

OMEMO doesn’t attempt to provide even the vaguest rationale for its design choices, and appears to approach cryptography protocol specification with a care-free attitude.

To put it mildly, this is the wrong way to approach cryptography. This is best explained with a concrete example.

Version 0.3.0 of XEP-0384 used AES-128-GCM to encrypt messages. (As we saw in the previous section, this is the version almost everyone is actually using.)

Version 0.4.0 was updated to use AES-256-CBC + HMAC-SHA-256 (Encrypt then HMAC), as Signal does.

Version 0.7.0 introduced yet another protocol change: The HMAC-SHA-256 authentication tag is now truncated to 128 bits.

And what was the changelog message for version 0.7.0?

Various fixes, clarifications and general improvements.

CHANGELOG, XEP-0384 0.7.0

You’ve got to be fucking kidding me.

Harubaki

So here’s the thing: These protocols all provide different security properties, and some of these differences are subtle. Switching from one to the other is the sort of change that should be accompanied by a clear reason.

See, for example, the PASETO v3/v4 rationale doc. That is the level of detail I’d want to see in OMEMO’s specification, especially the changelog. OMEMO’s rationale isn’t merely inadequate, it’s totally absent!

Technical Correction (2024-08-06)

A few people (or maybe the same person under different alts? Didn’t check, don’t really care) have pointed out that this section is not technically correct.

Apparently, while the actual steps in the encryption and decryption algorithms didn’t mention truncation at all, this was alluded to earlier in an earlier section.

I’m not going to significantly alter what I originally wrote above, because the earlier versions of the spec were poorly written and the instructions where absent from the section they needed to be in.

OMEMO Encryption Through the Ages

Before Version 0.4.0

AES-128-GCM doesn’t commit to the key, which can lead to an attack that we call “Invisible Salamanders”.

Historically, this was exploited in “abuse reporting” scenarios, but as I explained in my Threema disclosures, it can sometimes come up in group messaging scenarios.

For flavor, I wrote a GCM exploit in PHP for part of the DEFCON Furs’ badge challenge one year. It’s not a difficult one to pull off.

But if you’re in a setup where you only have one valid key for a given ciphertext, that’s not really a problem.

A bigger concern with this algorithm is that you’re constrained to 96-bit nonces, so if you’re using the same key for multiple messages, you have to worry about symmetric wear-out.

That being said, we can kind of summarize this as a short, reusable list.

• Key entropy: 128 bits
• Key commitment security: None
• Safety limit: messages, each with a max length of bytes.
• Authentication tag length: 128 bits
• Authentication security: 128 bits (polynomial MAC)

Version 0.4.0 – 0.6.0

As mentioned previously, version 0.4.0 of the OMEMO specification moved towards AES-256-CBC + HMAC-SHA-256 for Stanza Content Encryption.

This is congruent with what Signal does, so I won’t belabor the point.

If you implement the encryption algorithm faithfully from the specification’s order of operations, truncation is omitted. However, it does get a passing mention in the double ratchet section, so the authors can argue it was intended “all along”.

• Key entropy: 256 bits
• Key commitment security: 128 bits 64 bits
• Safety limit: It’s complicated. It can range from to bytes.
• Authentication tag length: 256 bits 128 bits (see edit)
• Authentication security: 128 bits 64 bits (cryptographic hash function)

EDIT: As mentioned above, this is actually not correct, because of an easy-to-miss detail in a previous section. There is no relevant encryption protocol change between 0.4.0 and 0.7.0.

Version 0.7.0 and Newer

And now we get to the latest version of the protocol, which is like the previous flavor, but now they truncate the HMAC-SHA-256 authentication tag to 128 bits in the actual steps to be performed.

Specifications should provide clear, unambiguous instructions for implementors. The OMEMO specification authors have failed to do this.

Interestingly, even the current version (0.8.3) doesn’t instruct implementations to use constant-time comparison for the truncated authentication tag in the decrypt path.

Surely, that won’t be a problem, right?

But to be congruent with the other sections in this historical breakdown, version 0.7.0+ looks like this:

• Key entropy: 256 bits
• Key commitment security: 64 bits
• Safety limit: It’s complicated. It can range from to bytes.
• Authentication tag length: 128 bits
• Authentication security: 64 bits (cryptographic hash function)

Remarks

Because there is no rationale given for this sudden square-root reduction in security against existential forgery attacks (EDIT: not correct, it was always truncated, just poorly written), we kind of have to fill in the gaps and assume it was because of some kind of performance or bandwidth considerations.

But even that doesn’t really justify it, does it?

You’re only saving 16 bytes of bandwidth by truncating the MAC. Meanwhile, the actual ciphertext blobs are being encoded with base64, which adds 33% of overhead.

For any message larger than 48 bytes, this base64 encoding will dominate the bandwidth consumption more than using the full HMAC tag would.

CMYKat

Is truncating the HMAC tag to to 128 bits still secure? According to Signal, yes, it is. And I offer no disagreement to Signal’s assessment here.

The problem is, as I’ve said repeatedly, OMEMO’s specification makes no attempt to justify their design decisions.

The “why?” is left as an exercise to the reader, and I’m not convinced that they themselves fully know the answer to that question.

OMEMO Problem 3: Market Penetration

I alluded to this above, but it bears repeating: Even if the previous two problems were resolved overnight, it’s entirely possible to use XMPP without encryption.

Further, you can disable OMEMO even if you’re using a client that supports OMEMO.

When I compare it to Signal, whose users always have end-to-end encryption, XMPP + OMEMO falls short of what is required to be a secure private messaging app.

XMPP+OMEMO evangelists are quick to point out that Conversations, the favored implementation, lets you enforce “always use encryption” mode. This is a damn good idea, but there’s no universal guarantee that all clients will do this, nor make it the default behavior.

On that note, let’s talk about Conversations.

OMEMO Problem 4: You’re not ready for that Conversation

Conversations is, from the best I can gather, the most popular XMPP client with OMEMO support.

If you’re going to discuss OMEMO, in practical terms, you need to look at the most popular implementation of OMEMO to have an informed opinion on the matter. Only focusing on the specification, rathe than actual implementations, would be a foolhardy endeavor.

Conversations appears to follow the “everything but the kitchen sink” methodology to managing their complexity.

Just looking at the crypto folder, I count the following:

1. Code that implements OpenPGP functions (signing, encryption)
2. X.509 certificate validation for XMPP domains based on BouncyCastle
3. An entire first-class SASL implementation, rather than a third-party library
4. Finally, their OMEMO implementation (still named Axolotl) that depends on libsignal

Update (2024-08-09): An earlier version of this blog post criticized them for having two PGP classes in the crypto folder.

The second one (PgpDecryptionService.java) appeared to call a separate API from the one next to it, which seemed like a legacy code path that was in need of refactoring away.

A closer examination reveals that it calls a Service class that in turn calls the first PGP class (PgpEngine.java), so I retracted that item from the above list.

To be clear: These aren’t separate dependencies that Conversations pulls in to implement plugin supports. They’re first-party cryptographic implementations all within this Android app’s codebase.

(Some of them also have third-party dependencies to boot, but that’s generally okay.)

The only thing they didn’t include is their own first-party TLS implementation forked from, like, OpenSSL 1.0.2f. That would’ve filled my Bingo card.

Art by AJ

Your Version Check Bounced

The latest version of Conversations depends on version 1.64 of the Bouncy Castle S/MIME implementation (October 2019), despite 1.70 being the latest that supports Java 1.5 (and 1.78 being the latest overall, but requires Java 1.8).

This means the following security enhancements and fixes are absent in the version Conversations depends on:

• Client-side OCSP Stapling was added in v1.65
• TLS 1.3 support was added in v1.68
• CVE-2023-33202, a DoS vulnerability in ASN.1 reachable through the PEM parser (i.e., any of the X.509 or OpenPGP code referenced above) is fixed in version v1.73.

The last one (CVE-2023-33202) is pernicious. Although it’s reachable through any usage of BouncyCastle’s Java PEM parser, the root cause is the underlying ASN.1 code, which means the domain verifier code is probably affected.

Why is Conversations in August 2024 still using an October 2019 version of their cryptography library?

Why am I pointing this out today when a component it provides that Conversations actually uses had a security fix in July 2023?

It’s not just BouncyCastle, either. Conversations also depends on a version of libsignal that was archived in 2022.

How We Got Here

Though it may be tempting for some readers to assign blame, let me be very clear: Doing so isn’t helpful, so don’t.

XMPP was a well-intentioned open protocol and Internet Standard. OMEMO was the least-bad effort to staple encryption onto XMPP.

If Conversations hadn’t cornered the XMPP market in recent years, the lack of discipline in complexity management (or a Dependabot or Semgrep integration, for that matter) would be a minor annoyance.

A lot of things had to go wrong for things to get as bad as they are.

Maybe part of the blame is a lack of investment or innovation in the XMPP developer community.

Maybe there should have been more dialogue between the security community and the XMPP Standards Foundation.

But the one thing I am certain of is the conclusion to this whole piece.

In Conclusion

As things stand today, I cannot recommend anyone use XMPP + OMEMO.

From the lack of a mechanism to keep implementations up-to-date with protocol versions, to a lack of clear rationale for protocol design decisions, to ecosystem issues with both the app availability and their third-party open source dependencies, to the most popular app (Conversations) being an absolute mess of complications, XMPP+OMEMO hasn’t earned my trust.

It’s possible that these flaws are correctable, and some future iteration of OMEMO will be better. It’s also possible that XMPP’s ecosystem will decide to make end-to-end encryption a non-optional component for all XMPP clients.

But I certainly wouldn’t bet my personal safety on good things happening; especially because of anything I wrote. I’m just some furry with a blog, after all.

CMYKat

“Don’t care, gonna keep using it!”

That’s fine. I’m not anyone’s boss or parent.

But in return, I really don’t appreciate unsolicited evangelism towards any technology.

It’s even worse when said evangelism is shouted over my informed opinions about cryptographic software. So, please don’t do that.

Addendum (2024-08-06)

Tim Henkes, one of the OMEMO authors, wrote a very tedious comment. The TL;DR of it is “you should distinguish between specification criticism and client software criticism, also truncation was in 0.4.0”.

I made the relevant changes above, because technical accuracy is important to me, but wasn’t interested in further involving myself with their project. So I replied saying as such.

Here’s a screenshot of their reply:

I’m just gonna let that speak for itself.

https://soatok.blog/2024/08/04/against-xmppomemo/

#cryptography #endToEndEncryption #softwareSecurity

Dhole Moments

2024-07-31 16:25:41

A lot of recent (and upcoming) blog posts I’ve written, and Fediverse discussions I’ve participated in, have been about the security of communication products.

My criticism of these products is simply that, from a cryptography and security perspective, they’re not a real competitor to Signal.

For all its other faults, Signal sets the bar for secure private messaging. It’s a solid security tool, even if its user experience and feature set leaves a lot of people disappointed. I highly recommend it over, say, Telegram.

In response to my post about jettisoning Telegram, quite a few people have tried to evangelize other products. For example:

Edit: Oh yeah, DON’T USE SIGNAL. Use Matrix instead, offers the benefits of signal without the drawbacks of lack of sync and phone number requirements and is decentralized. The fact that everyone is going gaga for signal as “the BEST messaging app” should be a big red flag in and of itself, because hype trains like this aren’t organic, just saying.

Draconic_NEO on pawb.social

So, let me explain what it means for a communication product to qualify as a Signal competitor from the perspective of someone whose job involves auditing cryptography implementations.

The Minimum Bar to Clear

Open Source

Every private messaging app must be open source in order to qualify as a Signal competitor.

If it’s not open source, it’s not even worth talking about.

End-to-End Encryption

Messages MUST be end-to-end encrypted. This means that you encrypt on one participant’s device, decrypt on another’s, and nobody in the middle can observe plaintext.

When I say MUST, I mean the RFC 2119 keyword.

There must never be a “transmit plaintext” option. No excuses. Secure cryptography is not interoperable with insecure cryptography. If you allow a “transmit plaintext” mode for any reason whatsoever, you have failed to build an encryption product that meets the bar.

This disqualifies Matrix.

This disqualifies Telegram.

This disqualifies XMPP + OMEMO.

This alone disqualifies a lot of so-called private messaging apps.

This doesn’t mean your product is insecure, or that I’m aware of any specific ways to break it.

It just doesn’t occupy the same mindshare as Signal, which only transmits encrypted data and doesn’t have a plaintext protocol to downgrade to.

Therefore, it’s not a goddamn Signal alternative.

How You Encrypt Matters

Signal normalized the use of AES-256-CBC with HMAC-SHA256.

Facebook’s “Secret Conversations” feature deviated from this and preferred AES-GCM for attachments, but this bit them when the Invisible Salamanders attack was discovered.

The way Signal uses AES+HMAC is fine for their use case, but building a secure committing AEAD mode (rather than merely AE) out of these primitives is nontrivial.

If you’re aiming to compete with Signal on security, you should, at minimum, expect to engage with a cryptography auditing firm at least once a year to review and re-review your protocol designs and implementations.

I Will Heavily Scrutinize Your Group Messaging Protocols

Group messaging is one of those topics that might sound easy if you can do peer-to-peer messaging securely, but is catastrophically difficult once you get into the details.

See also: My blog post about Threema.

If you want a starting point, look at RFC 9420 (Messaging Layer Security, which is a group key agreement protocol for messaging apps).

How You Manage Keys Matters

Tox attempted to build atop NaCl’s crypto_box interface, but this is not suitable for a general purpose secure messaging due to a lack of KCI Security.

Key management (which is the focus of an upcoming blog post) is a problem that almost everyone underestimates. It’s also the most user-facing aspect of these messaging applications.

WhatsApp uses Key Transparency to scale user trust. I’m proposing something similar for E2EE for the Fediverse.

This is a much better strategy than expecting users to manually verify “fingerprints”.

Don’t look at OpenPGP as a role model when it comes to user experience. Johnny still cannot fucking encrypt.

Your Feature Should Not Bypass Privacy

Want to add all sorts of frills, like video chat or some dumb bullshit with AI and/or blockchain to secure the attention of venture capitalist investors?

You’d better not implement them in such a way that leaks users’ messages or search queries to your service.

The main reason Signal is “missing” features is because they are thoughtful about how these features are designed and implemented.

Guess what happens if you prioritize shipping features over privacy and cryptography engineering?

That’s right: You stop being a contender for a Signal alternative.

So What?

If your fave isn’t a viable alternative to Signal, don’t fucking recommend it to people in response to me recommending Signal.

That’s all I ask.

Art: Scruff

But what about…?

I’m not here to discuss your use cases, or usability, or anything else. I’m also not saying that Signal is perfect!

Signal is a private messaging app that I would feel safe recommending whistleblowers to use. It meets all these requirements.

In order to be a Signal competitor, no matter how much you like your app, it needs to meet them too, otherwise it isn’t a Signal competitor. Them’s the rules!

AJ

There may be other requirements that are more important to you, that Signal doesn’t meet. That’s fine! You can like other things.

But unless your favorite widget also meets all of the things on this page, it’s not a valid competitor from a security and privacy perspective, and therefore I don’t want to fucking hear about it in response to me saying “use Signal until something better comes along”.

Capiche?

Addendum (2024-08-01)

Since I originally posted this, there have been a lot of opinions expressed and questions asked about messaging apps that have nothing to do with cryptographic security.

Those are good discussions to have, elsewhere. Hell, most of this discussion would be a better response to my other blog post than this one.

The goal of this post was to specify what the minimum bar is for a different app to qualify as a Signal competitor. It’s written from the perspective of someone whose career is in applied cryptography.

If you have thoughts, feelings, opinions, questions, or concerns about messaging apps (including but not limited to Signal), that’s wonderful.

But this specific blog post is not the correct place to voice them!

Especially if the first line of your response is “you’re too focused on [technology, security, cryptography] (select appropriate)”.

Because… no shit? That’s the entire point of this particular post. It’s narrowly scoped for a reason. Please respect that.

My upcoming vulnerability disclosure in Matrix will make the same point, but I wanted a separate, less distracting blog post to link people to when someone tries to evangelize another chat app instead of Signal, especially if they make security claims while doing so.

https://soatok.blog/2024/07/31/what-does-it-mean-to-be-a-signal-competitor/

#cryptography #endToEndEncryption #privateMessengers #Signal

A lot of recent (and upcoming) blog posts I’ve written, and Fediverse discussions I’ve participated in, have been about the security of communication products.

My criticism of these products is simply that, from a cryptography and security perspective, they’re not a real competitor to Signal.

For all its other faults, Signal sets the bar for secure private messaging. It’s a solid security tool, even if its user experience and feature set leaves a lot of people disappointed. I highly recommend it over, say, Telegram.

In response to my post about jettisoning Telegram, quite a few people have tried to evangelize other products. For example:

Edit: Oh yeah, DON’T USE SIGNAL. Use Matrix instead, offers the benefits of signal without the drawbacks of lack of sync and phone number requirements and is decentralized. The fact that everyone is going gaga for signal as “the BEST messaging app” should be a big red flag in and of itself, because hype trains like this aren’t organic, just saying.

Draconic_NEO on pawb.social

So, let me explain what it means for a communication product to qualify as a Signal competitor from the perspective of someone whose job involves auditing cryptography implementations.

The Minimum Bar to Clear

Open Source

Every private messaging app must be open source in order to qualify as a Signal competitor.

If it’s not open source, it’s not even worth talking about.

End-to-End Encryption

Messages MUST be end-to-end encrypted. This means that you encrypt on one participant’s device, decrypt on another’s, and nobody in the middle can observe plaintext.

When I say MUST, I mean the RFC 2119 keyword.

There must never be a “transmit plaintext” option. No excuses. Secure cryptography is not interoperable with insecure cryptography. If you allow a “transmit plaintext” mode for any reason whatsoever, you have failed to build an encryption product that meets the bar.

This disqualifies Matrix.

This disqualifies Telegram.

This disqualifies XMPP + OMEMO.

This alone disqualifies a lot of so-called private messaging apps.

This doesn’t mean your product is insecure, or that I’m aware of any specific ways to break it.

It just doesn’t occupy the same mindshare as Signal, which only transmits encrypted data and doesn’t have a plaintext protocol to downgrade to.

Therefore, it’s not a goddamn Signal alternative.

How You Encrypt Matters

Signal normalized the use of AES-256-CBC with HMAC-SHA256.

Facebook’s “Secret Conversations” feature deviated from this and preferred AES-GCM for attachments, but this bit them when the Invisible Salamanders attack was discovered.

The way Signal uses AES+HMAC is fine for their use case, but building a secure committing AEAD mode (rather than merely AE) out of these primitives is nontrivial.

If you’re aiming to compete with Signal on security, you should, at minimum, expect to engage with a cryptography auditing firm at least once a year to review and re-review your protocol designs and implementations.

I Will Heavily Scrutinize Your Group Messaging Protocols

Group messaging is one of those topics that might sound easy if you can do peer-to-peer messaging securely, but is catastrophically difficult once you get into the details.

See also: My blog post about Threema.

If you want a starting point, look at RFC 9420 (Messaging Layer Security, which is a group key agreement protocol for messaging apps).

How You Manage Keys Matters

Tox attempted to build atop NaCl’s crypto_box interface, but this is not suitable for a general purpose secure messaging due to a lack of KCI Security.

Key management (which is the focus of an upcoming blog post) is a problem that almost everyone underestimates. It’s also the most user-facing aspect of these messaging applications.

WhatsApp uses Key Transparency to scale user trust. I’m proposing something similar for E2EE for the Fediverse.

This is a much better strategy than expecting users to manually verify “fingerprints”.

Don’t look at OpenPGP as a role model when it comes to user experience. Johnny still cannot fucking encrypt.

Your Feature Should Not Bypass Privacy

Want to add all sorts of frills, like video chat or some dumb bullshit with AI and/or blockchain to secure the attention of venture capitalist investors?

You’d better not implement them in such a way that leaks users’ messages or search queries to your service.

The main reason Signal is “missing” features is because they are thoughtful about how these features are designed and implemented.

Guess what happens if you prioritize shipping features over privacy and cryptography engineering?

That’s right: You stop being a contender for a Signal alternative.

So What?

If your fave isn’t a viable alternative to Signal, don’t fucking recommend it to people in response to me recommending Signal.

That’s all I ask.

Art: Scruff

But what about…?

I’m not here to discuss your use cases, or usability, or anything else. I’m also not saying that Signal is perfect!

Signal is a private messaging app that I would feel safe recommending whistleblowers to use. It meets all these requirements.

In order to be a Signal competitor, no matter how much you like your app, it needs to meet them too, otherwise it isn’t a Signal competitor. Them’s the rules!

AJ

There may be other requirements that are more important to you, that Signal doesn’t meet. That’s fine! You can like other things.

But unless your favorite widget also meets all of the things on this page, it’s not a valid competitor from a security and privacy perspective, and therefore I don’t want to fucking hear about it in response to me saying “use Signal until something better comes along”.

Capiche?

Addendum (2024-08-01)

Since I originally posted this, there have been a lot of opinions expressed and questions asked about messaging apps that have nothing to do with cryptographic security.

Those are good discussions to have, elsewhere. Hell, most of this discussion would be a better response to my other blog post than this one.

The goal of this post was to specify what the minimum bar is for a different app to qualify as a Signal competitor. It’s written from the perspective of someone whose career is in applied cryptography.

If you have thoughts, feelings, opinions, questions, or concerns about messaging apps (including but not limited to Signal), that’s wonderful.

But this specific blog post is not the correct place to voice them!

Especially if the first line of your response is “you’re too focused on [technology, security, cryptography] (select appropriate)”.

Because… no shit? That’s the entire point of this particular post. It’s narrowly scoped for a reason. Please respect that.

My upcoming vulnerability disclosure in Matrix will make the same point, but I wanted a separate, less distracting blog post to link people to when someone tries to evangelize another chat app instead of Signal, especially if they make security claims while doing so.

https://soatok.blog/2024/07/31/what-does-it-mean-to-be-a-signal-competitor/

#cryptography #endToEndEncryption #privateMessengers #Signal

Dhole Moments

2024-05-14 16:26:41

I have been a begrudging user of Telegram for years simply because that’s what all the other furries use, despite their cryptography being legendarily bad.

When I signed up, I held my nose and expressed my discontent at Telegram by selecting a username that’s a dig at MTProto’s inherent insecurity against chosen ciphertext attacks: IND_CCA3_Insecure.

Art: CMYKat

I wrote about Furries and Telegram before, and included some basic privacy recommendations. As I said there: Telegram is not a private messenger. You shouldn’t think of it as one.

Recent Developments

Telegram and Elon Muck have recently begun attacking Signal and trying to paint it as insecure.

Matthew Green has a Twitter thread (lol) about it, but you can also read a copy here (archive 1, archive 2, PDF).

https://twitter.com/matthew_d_green/status/1789688236933062767

https://twitter.com/matthew_d_green/status/1789689315624169716

https://twitter.com/matthew_d_green/status/1789690652399170013

https://twitter.com/matthew_d_green/status/1789691417721282958

Et cetera.

This is shitty, and exacerbates a growing problem on Telegram: The prevalence of crypto-bros and fascist groups using it to organize.

Why Signal is Better for Furries

First, Signal has sticker packs now. If you want to use mine, here you go.

For years, the main draw for furries to Telegram over Signal was sticker packs. This is a solved problem.

Second, you can setup a username and keep your phone number private. You don’t need to give your phone number to strangers anymore!

(This used to be everyone’s criticism of Signal, but the introduction of usernames made it moot.)

Finally, it’s trivial for Americans to setup a second Signal account using Twilio or Google Voice, so you can compartmentalize your furry posting from the phone number your coworkers or family is likely to know.

(Note: I cannot speak to how to deal with technology outside of America, because I have never lived outside America for any significant length of time and do not know your laws. If this is relevant to you, ask someone in your country to help figure out how to navigate technological and political issues pertinent to your country; I am not local to you and have no fucking clue.)

The last two considerations were really what stopped furries (or queer people in general, really) from using Signal.

Why Signal?

There are two broadly-known private messaging apps that use state-of-the-art cryptography to ensure your messages are private, and one of them is owned by Meta (a.k.a., Facebook, which owns WhatsApp). So Signal is the only real option in my book.

That being said, Cwtch certainly looks like it may be promising in the near future. However, I have not studied its cryptography in depth yet. Neither has it been independently audited to my knowledge.

It’s worth pointing out that the lead developer of Cwtch is wrote a book titled Queer Privacy, so she’s overwhelmingly more likely to be receptive to the threat models faced by the furry community (which is overwhelmingly LGBTQ+).

For the sake of expedience, today, Signal is a “yes” and Cwtch is a hopeful “maybe”.

How I Setup a Second Signal Account

I own a Samsung S23, which means I can’t just use the vanilla Android tutorials for setting up a second profile on my device. Instead, I had to use the “Secure Folder” feature. The Freedom of the Press Foundation has more guidance worth considering.

If you don’t own a Samsung phone, you don’t need to bother with this “Secure Folder” feature (as the links above will tell you). You can just set up a work profile and get the same result! You probably also can’t access the same feature, since that’s a Samsung exclusive idiom. Don’t sweat it.

I don’t know anything about Apple products, so I can’t help you there, but there’s probably a way to set it up for yourself too. (If not, maybe consider this a good reason to stop giving abusive corporations like Apple money?)

The other piece of the puzzle you need is a second phone number. Google Voice is one way to acquire one; the other is to setup a Twilio account. There are plenty of guides online for doing that.

(Luckily, I’ve had one of these for several years, so I just used that.)

Why does Signal require a phone number?

The historical reason is that Signal was a replacement for text messaging (a.k.a., SMS). That’s probably still the official reason (though they don’t support SMS anymore).

From what I understand, the Signal development team has always been much more concerned about privacy for people that own mobile phones, but not computers, than they were concerned about the privacy of people that own computers, but not mobile phones.

After all, if you pick a random less privileged person, especially homeless or from a poor country, they’re overwhelmingly more likely to have a mobile phone than a computer. This doesn’t scratch the itch of people who would prefer to use PGP, but it does prioritize the least privileged people’s use case.

Their workflow, therefore, optimized for people that own a phone number. And so, needing a phone number to sign up wasn’t ever a problem they worried about for the people they were most interested in protecting.

Fortunately, using Signal doesn’t immediately reveal your phone number to anyone you want to chat with, ever since they introduced usernames. You still need one to register.

Tell Your Friends

I understand that the network effect is real. But it’s high time furries jettisoned Telegram as a community.

Lazy edit of the “Friendship Ended” meme

Finally, Signal is developed and operated by a non-profit. You should consider donating to them so that we can bring private messaging to the masses.

Addendum (2024-05-15)

I’ve been asked by several people about my opinions on other platforms and protocols.

Specifically, Matrix. I do not trust the Matrix developers to develop or implement a secure protocol for private messaging.

I don’t have an informed opinion about Signal forks (Session, Molly, etc.). Generally, I don’t review cryptography software for FOSS maximalists with skewed threat models unless I’m being paid to do so, and that hasn’t happened yet.

https://soatok.blog/2024/05/14/its-time-for-furries-to-stop-using-telegram/

#endToEndEncryption #furries #FurryFandom #privacy #Signal #Telegram

Since the IETF’s CFRG decided to recommend OPAQUE as a next-generation Password Authenticated Key Exchange, there has been a lot of buzz in the cryptography community about committing authenticated encryption (known to the more academically inclined as Random Key Robustness), because OPAQUE requires an RKR-secure AE scheme.

Random Key Robustness is a property that some symmetric encryption modes have, where it’s not feasible to decrypt a valid (ciphertext, tag) pair into two different plaintexts if both recipients are using different keys.

To illustrate this visually:

RKR-secure ciphers don’t let people produce the same ciphertext+tag from two different plaintexts, with two different keys. You might be able to create an identical ciphertext, but the authentication tag will differ. (Art by Swizz.)

In the wake of the CFRG discussion, it became immediately clear that AES-GCM doesn’t meet this requirement.

What wasn’t immediately clear is that AES-GCM-SIV also falls short. But don’t take my word for it, Sophie Schmieg worked out the math in the linked post, which I highly recommend reading.

This isn’t to say that AES-GCM or AES-GCM-SIV are doomed, or should be deprecated. You probably don’t even care about Random Key Robustness in most of the places you’d use either algorithm! But if you are doing something where RKR actually matters, you probably care a lot. And it certainly violates the principle of least astonishment.

ChaCha20-Poly1305 won’t save you here either, since this is a property that message authentication codes based on cryptographic hash functions (e.g. HMAC) provide, but polynomial MACs (GMAC, Poly1305, etc.) do not.

So, if every standardized and widely-supported AEAD construction fails to provide RKR security, what’s a software engineer to do?Roll their own crypto?!

Don’t actually do that. (Art by Swizz.)

If you’re always on a well-tread path with a well-defined, standard threat model (i.e. client-server application accessible via TLS 1.3, possibly storing hashed passwords server-side), then rolling your own crypto isn’t just dangerous; it’s wholly unnecessary.

Coping with Non-Standard Threat Models

Systems that require Random Key Robustness do not fall within the standard threat model of AEAD cipher constructions.

However, RKR is far from the only scenario in which application developers might find themselves without a clear solution. Another example that comes up a lot:

“I need to encrypt data in a relational database, but still somehow use it in SELECT queries.”

— Far too many damn developers who haven’t heard of CipherSweet.

The first thing that you should do is clearly document your requirements and what attacks your system must protect against. Any undefined attack vector in your model should be assumed to be a vulnerability in your design. (This gets into Unknown Unknowns territory quickly.)

And then you should have a cryptographer review your design, and then have a cryptography engineer build it for you.

But where’s the fun in that?

This would be a very boring blog post if I left it at that! (Art by Khia.)

Instead of copping out with sane and reasonable advice, let’s actually walk through the process. At the end of this post, I’ll share a toy example I cooked up for this blog post.

Designing New Cryptography

First, Understand the Problem

Why don’t AES-GCM, etc. provide Random Key Robustness? Because they’re built with universal hash functions rather than cryptographic hash functions.

Cryptographic hash functions have different properties (i.e. preimage resistance and collision resistance) that make it significantly difficult to calculate two different authentication tags under two different keys. Attacking HMAC-SHA-256 in this way is about as expensive as brute forcing a 128-bit AES key. (Good luck with that!)

However, cryptographic hash functions are much slower than polynomial MACs, and using them in a construction like HMAC approximately doubles the slowness.

You might be tempted to just hash they key and the message together to save on CPU cycles, but that’s actually not safe for the hash functions nearly everybody uses (due to length extension attacks).

It logically follows that, if we had an AEAD cipher construction based on a hash function, we could have RKR security.

Now we’re getting somewhere! (Art by Khia.)

Look At Prior Art

Before the days of AES-GCM and ChaCha20-Poly1305, there were a lot of ad hoc constructions used everywhere based on AES-CBC and HMAC. (In that era, everyone used HMAC-SHA1, but don’t do that.)

However, there are a number of problems with ad hoc CBC+HMAC that we don’t want to reintroduce in modern systems:

1. If you forget to include the initialization vector in the HMAC tag, you give attackers free reign over the first 16 bytes of the decrypted plaintext without having to break the MAC.
2. The order of operations (Encrypt-then-MAC, MAC-then-Encrypt, Encrypt and MAC) matters tremendously.
3. CBC+HMAC is usually implemented in application-layer code, but the security of such a construction depends heavily on the availability and utilization of constant-time functions.
4. There is no standard format for CBC+HMAC, nor the order of operations for what gets fed into the MAC.
   
   • IV + ciphertext? Ciphertext + IV?
   • Append the MAC, or prepend it?

   
   

5. CBC+HMAC is only an AE mode, there is no room for additional authenticated data. If you try to naively shove extra data into the HMAC, now you have to worry about canonicalization attacks!
6. CBC mode requires padding (usually PKCS #7 padding), whereas cipher modes based on CTR do not.

This is among the long list of reasons why cryptographers have spent the past decade (or longer) pushing developers towards AEAD modes.

Boring cryptography is good cryptography!

You never want to hear this about your design. (Art by Khia.)

Make sure you clearly understand the risks of the components other constructions have used.

Sketch Out A First Draft

By now, it should be clear that if we have an Encrypt-then-MAC construction, where the MAC is based on a cryptographic hash function (e.g. SHA-256), we may be able to attain RKR security.

With that in mind, our sketch will probably look something like this:

• Encrypt(K1, M, N) -> C
  
  • Where Encrypt() is AES-CTR or equivalent

  
  

• Auth(K2, C, A) -> T
  
  • Where Auth() wraps HMAC-SHA2 or equivalent
  • How we feed C and A into the underlying MAC is important

  
  

• ???? -> K1, K2

We still have to define some way of splitting a key (K) into two distinct keys (K1, K2). You never want to use a cryptographic key for more than one purpose, after all.

Key-Splitting and Robustness

Your encryption key and authentication key should be different, but they should also derived from the same input key! This is mainly to protect implementors from having independent keys and accidentally creating a forgery vulnerability.

There are several different ways you can split keys:

1. Just use SHA-512(k), then cut it in half. Use one half for encryption, the other for authentication.
2. Use HMAC-SHA256(k, c1) and HMAC-SHA256(k, c2), where c1 and c2 are distinct (yet arbitrary) constants.
3. Use HKDF. This works with any secure cryptographic hash function, and was specifically designed for situations like this. HKDF also supports salting, which can be used to randomize our derived keys.

We can really pick any of these three and be safe, but I’d advise against the first option. HKDF uses HMAC under-the-hood, so either of the latter options is fine.

Can We Make it Faster?

What if, instead of HMAC-SHA256, we used BLAKE3?

BLAKE3’s performance compared with other hash functions.

BLAKE3’s advertised 6.8 GiB/s can be even faster than Poly1305 or GHASH (and BLAKE3’s speed really shines through with long messages, due to its extreme parallelism through Merkle trees).

In Favor of ChaCha over AES

It’s no secret that I’m not a fan of AES. It’s not the mathematical properties of AES that bother me, it’s the 128-bit block size and the fact that software implementations have to decide between being fast or being secure.

Me, whenever I find an insecure software AES implementation. (Art by Khia.)

ChaCha’s 256-bit security level is easier to justify: The underlying PRF state is 512 bits (which implies an approximately 256-bit security level) and the keys are always 256 bits.

Furthermore, if you’re building ChaCha and BLAKE3 in the same codebase, you could reuse some components (i.e. the compression function, G). This is very desirable if you’re trying to ship a small amount of code (e.g. embedded systems). EDIT: One of the BLAKE3 authors informed me that I’m mistaken about this: “[N]ope, not exactly the same logic (rotations in different direction)”.

Other Desirable Security Properties

Nonce Nonsense

One of the biggest problems with standard AEAD modes is that they explode gloriously when you reuse a nonce. There are two ways out of this peril:

1. Use a nonce misuse resistant AEAD construction (AES-GCM-SIV, etc.).
   
   • For prior art on nonce-misuse resistant cipher modes based on ChaCha, check out DAENCE.

   
   

2. Use large nonces (e.g. XChaCha20 uses 192-bit nonces) and generate them randomly, so the probability of nonce reuse becomes negligible.

Since we’re already planning on using a hash function to derive subkeys (one for encryption, one for authentication), it makes sense to also accept a longer nonce than our stream cipher demands. The excess bytes can be passed to our KDF without significant risk or additional overhead.

Since the IETF’s ChaCha20 variant expects a 96-bit nonce, designing our construction to support 256-bit nonces means we can pass the first 160 bits of the nonce to the KDF and the latter 96 bits to the stream cipher. You can expect a single KDF collision after 2^80 encryptions, but it will almost certainly occur with a different nonce.

Safe MAC Canonicalization

We want to ensure it’s infeasible for an attacker to feed two different (ciphertext, AAD) pairs into our construction that produce the same tag.

Simply concatenating the two values will run the risk of someone shaving off a chunk of the ciphertext and storing it in the AAD instead.

There’s always a complication! (Art by Swizz.)

The simplest solution is to either prepend or append the lengths of the components (as the little-endian octet string representation of 64-bit unsigned integers).

The choice between prepending and appending doesn’t affect security much, but appending the lengths is friendlier for streaming interfaces.

After all, in a streaming encryption/decryption interface, you might not know the lengths of the either component until you’ve finished encrypting and authenticating all of the data.

(Art by Khia.)

Putting It All Together

Now that we’ve meandered through a rough list of desirable design properties, let’s recap:

• We want to Encrypt then MAC.
• We want to use ChaCha20 (the IETF’s variant) as our stream cipher.
• We want to use keyed BLAKE3 for the KDF and MAC algorithm.
• We want to accept 256-bit nonces (160 bits for the KDF, 96 for the stream cipher).
• We want to ensure our ChaCha20 and BLAKE3-MAC keys are derived from the same input key, using some domain separation constants.
• We want to feed the data into the MAC this order:
  
  1. AAD
  2. Ciphertext
  3. Length of AAD
  4. Length of Ciphertext

  
  

• We want to ensure our authentication tags are always verified in constant-time.

That sounds like a lot. But what does it yield in terms of code size? Surprisingly very little!

You can find the JS implementation of my design on Github.

Should I Use This?

No. Don’t do it.

I mean, would your users really feel safe if you got your cryptography recommendations and implementations from a furry blogger?

This is just a toy example I put together for the sake of illustrating how a new cryptographic design might be proposed. That’s only the first step.

Ultimately, you shouldn’t use this for one simple reason: Neither my design nor my implementation have been peer reviewed.

Maybe I’ll refine it a bit and kick it over to the CFRG for consideration for inclusion with OPAQUE someday. It might turn out to be a good design. It might be vulnerable to some subtle attack I can’t even imagine right now.

Until experts tell you otherwise, it’s hazardous material and you should only play with it for educational purposes.

(Art by Swizz.)

Further Reading

I’ve written a lot about cryptography, and there are always more topics to write about than I have the time or energy to cover, so here’s a few cool blogs/etc. to check out while I slog through Rough Draft Hell.

• Cryptography Dispatches — Newsletter ran by Filippo Valsorda, cryptographer and Go security team lead.
• Bulletproof TLS Newsletter — Newsletter ran by Hanno Böck, freelance journalist, IT security expert, and AES-GCM exploiter.
• Key Material — A new blog by Sophie Schmieg (cryptographer at Google) and Sarai Rosenberg (security engineer at Pager Duty).
• Little Man In My Head — A blog by Scott Contini, a security expert who frequently posts helpful comments on /r/crypto.

Header art by Khia. The figure in the background is from this paper on Message Franking via Committing Authentication Encryption.

https://soatok.blog/2020/09/09/designing-new-cryptography-for-non-standard-threat-models/

#BLAKE3 #ChaCha20 #cryptography #randomKeyRobustness #SecurityGuidance #symmetricCryptography

Dhole Moments

2020-04-21 12:25:46

Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).

What’s an AKE?

At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.

1. An authentication mechanism, such as a MAC or a digital signature.
2. Key encapsulation, usually through some sort of Diffie-Hellman.

A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.

I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)

AKEs get much more complicated, the more sophisticated your threat model becomes.

For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.

The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.

Password AKEs

Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.

PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.

Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).

Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.

I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.

📦 https://t.co/Q0kI19JOPY 📦

125 lines of code! Really happy with it and it was a lot of fun.

— Filippo Valsorda (@FiloSottile) March 29, 2020

Why So Complicated?

At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.

But how you combine these components together can vary wildly!

Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.

The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.

(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)

https://soatok.blog/2020/04/21/authenticated-key-exchanges/

#ake #authenticatedKeyExchange #cryptography #ECDH

Earlier this year, Cendyne wrote a blog post covering the use of HKDF, building partially upon my own blog post about HKDF and the KDF security definition, but moreso inspired by a cryptographic issue they identified in another company’s product (dubbed AnonCo).

At the bottom they teased:

Database cryptography is hard. The above sketch is not complete and does not address several threats! This article is quite long, so I will not be sharing the fixes.

Cendyne

If you read Cendyne’s post, you may have nodded along with that remark and not appreciate the degree to which our naga friend was putting it mildly. So I thought I’d share some of my knowledge about real-world database cryptography in an accessible and fun format in the hopes that it might serve as an introduction to the specialization.

Note: I’m also not going to fix Cendyne’s sketch of AnonCo’s software here–partly because I don’t want to get in the habit of assigning homework or required reading, but mostly because it’s kind of obvious once you’ve learned the basics.

I’m including art of my fursona in this post… as is tradition for furry blogs.
If you don’t like furries, please feel free to leave this blog and read about this topic elsewhere.

Thanks to CMYKat for the awesome stickers.

Contents

• Database Cryptography?
• Cryptography for Relational Databases
  
  • The Perils of Built-in Encryption Functions
  • Application-Layer Relational Database Cryptography
    
    • Confused Deputies
    • Canonicalization Attacks
    • Multi-Tenancy

    
    

  
  

• Cryptography for NoSQL Databases
  
  • NoSQL is Built Different
  • Record Authentication
    
    • Bonus: A Maximally Schema-Free, Upgradeable Authentication Design

    
    

  
  

• Searchable Encryption
  
  • Order-{Preserving, Revealing} Encryption
  • Deterministic Encryption
  • Homomorphic Encryption
  • Searchable Symmetric Encryption (SSE)
  • You Can Have Little a HMAC, As a Treat

  
  

• Intermission
• Case Study: MongoDB Client-Side Encryption
  
  • MongoCrypt: The Good
    
    • How is Queryable Encryption Implemented?

    
    

  • MongoCrypt: The Bad
  • MongoCrypt: The Ugly

  
  

• Wrapping Up

Database Cryptography?

The premise of database cryptography is deceptively simple: You have a database, of some sort, and you want to store sensitive data in said database.

The consequences of this simple premise are anything but simple. Let me explain.

Art: ScruffKerfluff

The sensitive data you want to store may need to remain confidential, or you may need to provide some sort of integrity guarantees throughout your entire system, or sometimes both. Sometimes all of your data is sensitive, sometimes only some of it is. Sometimes the confidentiality requirements of your data extends to where within a dataset the record you want actually lives. Sometimes that’s true of some data, but not others, so your cryptography has to be flexible to support multiple types of workloads.

Other times, you just want your disks encrypted at rest so if they grow legs and walk out of the data center, the data cannot be comprehended by an attacker. And you can’t be bothered to work on this problem any deeper. This is usually what compliance requirements cover. Boxes get checked, executives feel safer about their operation, and the whole time nobody has really analyzed the risks they’re facing.

But we’re not settling for mere compliance on this blog. Furries have standards, after all.

So the first thing you need to do before diving into database cryptography is threat modelling. The first step in any good threat model is taking inventory; especially of assumptions, requirements, and desired outcomes. A few good starter questions:

1. What database software is being used? Is it up to date?
2. What data is being stored in which database software?
3. How are databases oriented in the network of the overall system?
   
   • Is your database properly firewalled from the public Internet?

   
   

4. How does data flow throughout the network, and when do these data flows intersect with the database?
   
   • Which applications talk to the database? What languages are they written in? Which APIs do they use?

   
   

5. How will cryptography secrets be managed?
   
   • Is there one key for everyone, one key per tenant, etc.?
   • How are keys rotated?
   • Do you use envelope encryption with an HSM, or vend the raw materials to your end devices?

   
   

The first two questions are paramount for deciding how to write software for database cryptography, before you even get to thinking about the cryptography itself.

(This is not a comprehensive set of questions to ask, either. A formal threat model is much deeper in the weeds.)

The kind of cryptography protocol you need for, say, storing encrypted CSV files an S3 bucket is vastly different from relational (SQL) databases, which in turn will be significantly different from schema-free (NoSQL) databases.

Furthermore, when you get to the point that you can start to think about the cryptography, you’ll often need to tackle confidentiality and integrity separately.

If that’s unclear, think of a scenario like, “I need to encrypt PII, but I also need to digitally sign the lab results so I know it wasn’t tampered with at rest.”

My point is, right off the bat, we’ve got a three-dimensional matrix of complexity to contend with:

1. On one axis, we have the type of database.
   
   • Flat-file
   • Relational
   • Schema-free

   
   

2. On another, we have the basic confidentiality requirements of the data.
   
   • Field encryption
   • Row encryption
   • Column encryption
   • Unstructured record encryption
   • Encrypting entire collections of records

   
   

3. Finally, we have the integrity requirements of the data.
   
   • Field authentication
   • Row/column authentication
   • Unstructured record authentication
   • Collection authentication (based on e.g. Sparse Merkle Trees)

   
   

And then you have a fourth dimension that often falls out of operational requirements for databases: Searchability.

Why store data in a database if you have no way to index or search the data for fast retrieval?

Credit: Harubaki

If you’re starting to feel overwhelmed, you’re not alone. A lot of developers drastically underestimate the difficulty of the undertaking, until they run head-first into the complexity.

Some just phone it in with AES_Encrypt() calls in their MySQL queries. (Too bad ECB mode doesn’t provide semantic security!)

Which brings us to the meat of this blog post: The actual cryptography part.

Cryptography is the art of transforming information security problems into key management problems.

Former coworker

Note: In the interest of time, I’m skipping over flat files and focusing instead on actual database technologies.

Cryptography for Relational Databases

Encrypting data in an SQL database seems simple enough, even if you’ve managed to shake off the complexity I teased from the introduction.

You’ve got data, you’ve got a column on a table. Just encrypt the data and shove it in a cell on that column and call it a day, right?

But, alas, this is a trap. There are so many gotchas that I can’t weave a coherent, easy-to-follow narrative between them all.

So let’s start with a simple question: where and how are you performing your encryption?

The Perils of Built-in Encryption Functions

MySQL provides functions called AES_Encrypt and AES_Decrypt, which many developers have unfortunately decided to rely on in the past.

It’s unfortunate because these functions implement ECB mode. To illustrate why ECB mode is bad, I encrypted one of my art commissions with AES in ECB mode:

Art by Riley, encrypted with AES-ECB

The problems with ECB mode aren’t exactly “you can see the image through it,” because ECB-encrypting a compressed image won’t have redundancy (and thus can make you feel safer than you are).

ECB art is a good visual for the actual issue you should care about, however: A lack of semantic security.

A cryptosystem is considered semantically secure if observing the ciphertext doesn’t reveal information about the plaintext (except, perhaps, the length; which all cryptosystems leak to some extent). More information here.

ECB art isn’t to be confused with ECB poetry, which looks like this:

Oh little one, you’re growing up
You’ll soon be writing C
You’ll treat your ints as pointers
You’ll nest the ternary
You’ll cut and paste from github
And try cryptography
But even in your darkest hour
Do not use ECB

CBC’s BEASTly when padding’s abused
And CTR’s fine til a nonce is reused
Some say it’s a CRIME to compress then encrypt
Or store keys in the browser (or use javascript)
Diffie Hellman will collapse if hackers choose your g
And RSA is full of traps when e is set to 3
Whiten! Blind! In constant time! Don’t write an RNG!
But failing all, and listen well: Do not use ECB

They’ll say “It’s like a one-time-pad!
The data’s short, it’s not so bad
the keys are long–they’re iron clad
I have a PhD!”
And then you’re front page Hacker News
Your passwords cracked–Adobe Blues.
Don’t leave your penguins showing through,
Do not use ECB

— Ben Nagy, PoC||GTFO 0x04:13

Most people reading this probably know better than to use ECB mode already, and don’t need any of these reminders, but there is still a lot of code that inadvertently uses ECB mode to encrypt data in the database.

Also, SHOW processlist; leaks your encryption keys. Oops.

Credit: CMYKatt

Application-layer Relational Database Cryptography

Whether burned by ECB or just cautious about not giving your secrets to the system that stores all the ciphertext protected by said secret, a common next step for developers is to simply encrypt in their server-side application code.

And, yes, that’s part of the answer. But how you encrypt is important.

Credit: Harubaki

“I’ll encrypt with CBC mode.”
If you don’t authenticate your ciphertext, you’ll be sorry. Maybe try again?

“Okay, fine, I’ll use an authenticated mode like GCM.”
Did you remember to make the table and column name part of your AAD? What about the primary key of the record?

“What on Earth are you talking about, Soatok?”
Welcome to the first footgun of database cryptography!

Confused Deputies

Encrypting your sensitive data is necessary, but not sufficient. You need to also bind your ciphertexts to the specific context in which they are stored.

To understand why, let’s take a step back: What specific threat does encrypting your database records protect against?

We’ve already established that “your disks walk out of the datacenter” is a “full disk encryption” problem, so if you’re using application-layer cryptography to encrypt data in a relational database, your threat model probably involves unauthorized access to the database server.

What, then, stops an attacker from copying ciphertexts around?

Credit: CMYKatt

Let’s say I have a legitimate user account with an ID 12345, and I want to read your street address, but it’s encrypted in the database. But because I’m a clever hacker, I have unfettered access to your relational database server.

All I would need to do is simply…

UPDATE table SET addr_encrypted = 'your-ciphertext' WHERE id = 12345

…and then access the application through my legitimate access. Bam, data leaked. As an attacker, I can probably even copy fields from other columns and it will just decrypt. Even if you’re using an authenticated mode.

We call this a confused deputy attack, because the deputy (the component of the system that has been delegated some authority or privilege) has become confused by the attacker, and thus undermined an intended security goal.

The fix is to use the AAD parameter from the authenticated mode to bind the data to a given context. (AAD = Additional Authenticated Data.)

- $addr = aes_gcm_encrypt($addr, $key);+ $addr = aes_gcm_encrypt($addr, $key, canonicalize([+ $tableName,+ $columnName,+ $primaryKey+ ]);

Now if I start cutting and pasting ciphertexts around, I get a decryption failure instead of silently decrypting plaintext.

This may sound like a specific vulnerability, but it’s more of a failure to understand an important general lesson with database cryptography:

Where your data lives is part of its identity, and MUST be authenticated.

Soatok’s Rule of Database Cryptography

Canonicalization Attacks

In the previous section, I introduced a pseudocode called canonicalize(). This isn’t a pasto from some reference code; it’s an important design detail that I will elaborate on now.

First, consider you didn’t do anything to canonicalize your data, and you just joined strings together and called it a day…

function dumbCanonicalize( string $tableName, string $columnName, string|int $primaryKey): string { return $tableName . '_' . $columnName . '#' . $primaryKey;}

Consider these two inputs to this function:

1. dumbCanonicalize('customers', 'last_order_uuid', 123);
2. dumbCanonicalize('customers_last_order', 'uuid', 123);

In this case, your AAD would be the same, and therefore, your deputy can still be confused (albeit in a narrower use case).

In Cendyne’s article, AnonCo did something more subtle: The canonicalization bug created a collision on the inputs to HKDF, which resulted in an unintentional key reuse.

Up until this point, their mistake isn’t relevant to us, because we haven’t even explored key management at all. But the same design flaw can re-emerge in multiple locations, with drastically different consequence.

Multi-Tenancy

Once you’ve implemented a mitigation against Confused Deputies, you may think your job is done. And it very well could be.

Often times, however, software developers are tasked with building support for Bring Your Own Key (BYOK).

This is often spawned from a specific compliance requirement (such as cryptographic shredding; i.e. if you erase the key, you can no longer recover the plaintext, so it may as well be deleted).

Other times, this is driven by a need to cut costs: Storing different users’ data in the same database server, but encrypting it such that they can only encrypt their own records.

Two things can happen when you introduce multi-tenancy into your database cryptography designs:

1. Invisible Salamanders becomes a risk, due to multiple keys being possible for any given encrypted record.
2. Failure to address the risk of Invisible Salamanders can undermine your protection against Confused Deputies, thereby returning you to a state before you properly used the AAD.

So now you have to revisit your designs and ensure you’re using a key-committing authenticated mode, rather than just a regular authenticated mode.

Isn’t cryptography fun?

“What Are Invisible Salamanders?”

This refers to a fun property of AEAD modes based on Polynomical MACs. Basically, if you:

1. Encrypt one message under a specific key and nonce.
2. Encrypt another message under a separate key and nonce.

…Then you can get the same exact ciphertext and authentication tag. Performing this attack requires you to control the keys for both encryption operations.

This was first demonstrated in an attack against encrypted messaging applications, where a picture of a salamander was hidden from the abuse reporting feature because another attached file had the same authentication tag and ciphertext, and you could trick the system if you disclosed the second key instead of the first. Thus, the salamander is invisible to attackers.

Art: CMYKat

We’re not quite done with relational databases yet, but we should talk about NoSQL databases for a bit. The final topic in scope applies equally to both, after all.

Cryptography for NoSQL Databases

Most of the topics from relational databases also apply to NoSQL databases, so I shall refrain from duplicating them here. This article is already sufficiently long to read, after all, and I dislike redundancy.

NoSQL is Built Different

The main thing that NoSQL databases offer in the service of making cryptographers lose sleep at night is the schema-free nature of NoSQL designs.

What this means is that, if you’re using a client-side encryption library for a NoSQL database, the previous concerns about confused deputy attacks are amplified by the malleability of the document structure.

Additionally, the previously discussed cryptographic attacks against the encryption mode may be less expensive for an attacker to pull off.

Consider the following record structure, which stores a bunch of data stored with AES in CBC mode:

{ "encrypted-data-key": "<blob>", "name": "<ciphertext>", "address": [ "<ciphertext>", "<ciphertext>" ], "social-security": "<ciphertext>", "zip-code": "<ciphertext>"}

If this record is decrypted with code that looks something like this:

$decrypted = [];// ... snip ...foreach ($record['address'] as $i => $addrLine) { try { $decrypted['address'][$i] = $this->decrypt($addrLine); } catch (Throwable $ex) { // You'd never deliberately do this, but it's for illustration $this->doSomethingAnOracleCanObserve($i); // This is more believable, of course: $this->logDecryptionError($ex, $addrLine); $decrypted['address'][$i] = ''; }}

Then you can keep appending rows to the "address" field to reduce the number of writes needed to exploit a padding oracle attack against any of the <ciphertext> fields.

Art: Harubaki

This isn’t to say that NoSQL is less secure than SQL, from the context of client-side encryption. However, the powerful feature sets that NoSQL users are accustomed to may also give attackers a more versatile toolkit to work with.

Record Authentication

A pedant may point out that record authentication applies to both SQL and NoSQL. However, I mostly only observe this feature in NoSQL databases and document storage systems in the wild, so I’m shoving it in here.

Encrypting fields is nice and all, but sometimes what you want to know is that your unencrypted data hasn’t been tampered with as it flows through your system.

The trivial way this is done is by using a digital signature algorithm over the whole record, and then appending the signature to the end. When you go to verify the record, all of the information you need is right there.

This works well enough for most use cases, and everyone can pack up and go home. Nothing more to see here.

Except…

When you’re working with NoSQL databases, you often want systems to be able to write to additional fields, and since you’re working with schema-free blobs of data rather than a normalized set of relatable tables, the most sensible thing to do is to is to append this data to the same record.

Except, oops! You can’t do that if you’re shoving a digital signature over the record. So now you need to specify which fields are to be included in the signature.

And you need to think about how to model that in a way that doesn’t prohibit schema upgrades nor allow attackers to perform downgrade attacks. (See below.)

I don’t have any specific real-world examples here that I can point to of this problem being solved well.
Art: CMYKat

Furthermore, as with preventing confused deputy and/or canonicalization attacks above, you must also include the fully qualified path of each field in the data that gets signed.

As I said with encryption before, but also true here:

Where your data lives is part of its identity, and MUST be authenticated.

Soatok’s Rule of Database Cryptography

This requirement holds true whether you’re using symmetric-key authentication (i.e. HMAC) or asymmetric-key digital signatures (e.g. EdDSA).

Bonus: A Maximally Schema-Free, Upgradeable Authentication Design

Art: Harubaki

Okay, how do you solve this problem so that you can perform updates and upgrades to your schema but without enabling attackers to downgrade the security? Here’s one possible design.

Let’s say you have two metadata fields on each record:

1. A compressed binary string representing which fields should be authenticated. This field is, itself, not authenticated. Let’s call this meta-auth.
2. A compressed binary string representing which of the authenticated fields should also be encrypted. This field is also authenticated. This is at most the same length as the first metadata field. Let’s call this meta-enc.

Furthermore, you will specify a canonical field ordering for both how data is fed into the signature algorithm as well as the field mappings in meta-auth and meta-enc.

{ "example": { "credit-card": { "number": /* encrypted */, "expiration": /* encrypted */, "ccv": /* encrypted */ }, "superfluous": { "rewards-member": null } }, "meta-auth": compress_bools([ true, /* example.credit-card.number */ true, /* example.credit-card.expiration */ true, /* example.credit-card.ccv */ false, /* example.superfluous.rewards-member */ true /* meta-enc */ ]), "meta-enc": compress_bools([ true, /* example.credit-card.number */ true, /* example.credit-card.expiration */ true, /* example.credit-card.ccv */ false /* example.superfluous.rewards-member */ ]), "signature": /* -- snip -- */}

When you go to append data to an existing record, you’ll need to update meta-auth to include the mapping of fields based on this canonical ordering to ensure only the intended fields get validated.

When you update your code to add an additional field that is intended to be signed, you can roll that out for new records and the record will continue to be self-describing:

• New records will have the additional field flagged as authenticated in meta-auth (and meta-enc will grow)
• Old records will not, but your code will still sign them successfully
• To prevent downgrade attacks, simply include a schema version ID as an additional plaintext field that gets authenticated. An attacker who tries to downgrade will need to be able to produce a valid signature too.

You might think meta-auth gives an attacker some advantage, but this only includes which fields are included in the security boundary of the signature or MAC, which allows unauthenticated data to be appended for whatever operational purpose without having to update signatures or expose signing keys to a wider part of the network.

{ "example": { "credit-card": { "number": /* encrypted */, "expiration": /* encrypted */, "ccv": /* encrypted */ }, "superfluous": { "rewards-member": null } }, "meta-auth": compress_bools([ true, /* example.credit-card.number */ true, /* example.credit-card.expiration */ true, /* example.credit-card.ccv */ false, /* example.superfluous.rewards-member */ true, /* meta-enc */ true /* meta-version */ ]), "meta-enc": compress_bools([ true, /* example.credit-card.number */ true, /* example.credit-card.expiration */ true, /* example.credit-card.ccv */ false, /* example.superfluous.rewards-member */ true /* meta-version */ ]), "meta-version": 0x01000000, "signature": /* -- snip -- */}

If an attacker tries to use the meta-auth field to mess with a record, the best they can hope for is an Invalid Signature exception (assuming the signature algorithm is secure to begin with).

Even if they keep all of the fields the same, but play around with the structure of the record (e.g. changing the XPath or equivalent), so long as the path is authenticated with each field, breaking this is computationally infeasible.

Searchable Encryption

If you’ve managed to make it through the previous sections, congratulations, you now know enough to build a secure but completely useless database.

Art: CMYKat

Okay, put away the pitchforks; I will explain.

Part of the reason why we store data in a database, rather than a flat file, is because we want to do more than just read and write. Sometimes computer scientists want to compute. Almost always, you want to be able to query your database for a subset of records based on your specific business logic needs.

And so, a database which doesn’t do anything more than store ciphertext and maybe signatures is pretty useless to most people. You’d have better luck selling Monkey JPEGs to furries than convincing most businesses to part with their precious database-driven report generators.

Art: Sophie

So whenever one of your users wants to actually use their data, rather than just store it, they’re forced to decide between two mutually exclusive options:

1. Encrypting the data, to protect it from unauthorized disclosure, but render it useless
2. Doing anything useful with the data, but leaving it unencrypted in the database

This is especially annoying for business types that are all in on the Zero Trust buzzword.

Fortunately, the cryptographers are at it again, and boy howdy do they have a lot of solutions for this problem.

Order-{Preserving, Revealing} Encryption

On the fun side of things, you have things like Order-Preserving and Order-Revealing Encryption, which Matthew Green wrote about at length.

[D]atabase encryption has been a controversial subject in our field. I wish I could say that there’s been an actual debate, but it’s more that different researchers have fallen into different camps, and nobody has really had the data to make their position in a compelling way. There have actually been some very personal arguments made about it.

Attack of the week: searchable encryption and the ever-expanding leakage function

The problem with these designs is that they have a significant enough leakage that it no longer provides semantic security.

From Grubbs, et al. (GLMP, 2019.)
Colors inverted to fit my blog’s theme better.

To put it in other words: These designs are only marginally better than ECB mode, and probably deserve their own poems too.

Order revealing
Reveals much more than order
Softcore ECB

Order preserving
Semantic security?
Only in your dreams

Haiku for your consideration

Deterministic Encryption

Here’s a simpler, but also terrible, idea for searchable encryption: Simply give up on semantic security entirely.

If you recall the AES_{De,En}crypt() functions built into MySQL I mentioned at the start of this article, those are the most common form of deterministic encryption I’ve seen in use.

SELECT * FROM foo WHERE bar = AES_Encrypt('query', 'key');

However, there are slightly less bad variants. If you use AES-GCM-SIV with a static nonce, your ciphertexts are fully deterministic, and you can encrypt a small number of distinct records safely before you’re no longer secure.

From Page 14 of the linked paper. Full view.

That’s certainly better than nothing, but you also can’t mitigate confused deputy attacks. But we can do better than this.

Homomorphic Encryption

In a safer plane of academia, you’ll find homomorphic encryption, which researchers recently demonstrated with serving Wikipedia pages in a reasonable amount of time.

Homomorphic encryption allows computations over the ciphertext, which will be reflected in the plaintext, without ever revealing the key to the entity performing the computation.

If this sounds vaguely similar to the conditions that enable chosen-ciphertext attacks, you probably have a good intuition for how it works: RSA is homomorphic to multiplication, AES-CTR is homomorphic to XOR. Fully homomorphic encryption uses lattices, which enables multiple operations but carries a relatively enormous performance cost.

Art: Harubaki

Homomorphic encryption sometimes intersects with machine learning, because the notion of training an encrypted model by feeding it encrypted data, then decrypting it after-the-fact is desirable for certain business verticals. Your data scientists never see your data, and you have some plausible deniability about the final ML model this work produces. This is like a Siren song for Venture Capitalist-backed medical technology companies. Tech journalists love writing about it.

However, a less-explored use case is the ability to encrypt your programs but still get the correct behavior and outputs. Although this sounds like a DRM technology, it’s actually something that individuals could one day use to prevent their ISPs or cloud providers from knowing what software is being executed on the customer’s leased hardware. The potential for a privacy win here is certainly worth pondering, even if you’re a tried and true Pirate Party member.

Just say “NO” to the copyright cartels.
Art: CMYKat

Searchable Symmetric Encryption (SSE)

Forget about working at the level of fields and rows or individual records. What if we, instead, worked over collections of documents, where each document is viewed as a set of keywords from a keyword space?

Art: CMYKat

That’s the basic premise of SSE: Encrypting collections of documents rather than individual records.

The actual implementation details differ greatly between designs. They also differ greatly in their leakage profiles and susceptibility to side-channel attacks.

Some schemes use a so-called trapdoor permutation, such as RSA, as one of their building blocks.

Some schemes only allow for searching a static set of records, while others can accommodate new data over time (with the trade-off between more leakage or worse performance).

If you’re curious, you can learn more about SSE here, and see some open source SEE implementations online here.

You’re probably wondering, “If SSE is this well-studied and there are open source implementations available, why isn’t it more widely used?”

Your guess is as good as mine, but I can think of a few reasons:

1. The protocols can be a little complicated to implement, and aren’t shipped by default in cryptography libraries (i.e. OpenSSL’s libcrypto or libsodium).
2. Every known security risk in SSE is the product of a trade-offs, rather than there being a single winner for all use cases that developers can feel comfortable picking.
3. Insufficient marketing and developer advocacy.
   SSE schemes are mostly of interest to academics, although Seny Kamara (Brown Univeristy professior and one of the luminaries of searchable encryption) did try to develop an app called Pixek which used SSE to encrypt photos.

Maybe there’s room for a cryptography competition on searchable encryption schemes in the future.

You Can Have Little a HMAC, As a Treat

Finally, I can’t talk about searchable encryption without discussing a technique that’s older than dirt by Internet standards, that has been independently reinvented by countless software developers tasked with encrypting database records.

The oldest version I’ve been able to track down dates to 2006 by Raul Garcia at Microsoft, but I’m not confident that it didn’t exist before.

The idea I’m alluding to goes like this:

1. Encrypt your data, securely, using symmetric cryptography.
   (Hopefully your encryption addresses the considerations outlined in the relevant sections above.)
2. Separately, calculate an HMAC over the unencrypted data with a separate key used exclusively for indexing.

When you need to query your data, you can just recalculate the HMAC of your challenge and fetch the records that match it. Easy, right?

Even if you rotate your keys for encryption, you keep your indexing keys static across your entire data set. This lets you have durable indexes for encrypted data, which gives you the ability to do literal lookups for the performance hit of a hash function.

Additionally, everyone has HMAC in their toolkit, so you don’t have to move around implementations of complex cryptographic building blocks. You can live off the land. What’s not to love?

Hooray!

However, if you stopped here, we regret to inform you that your data is no longer indistinguishable from random, which probably undermines the security proof for your encryption scheme.

How annoying!

Of course, you don’t have to stop with the addition of plain HMAC to your database encryption software.

Take a page from Troy Hunt: Truncate the output to provide k-anonymity rather than a direct literal look-up.

“K-What Now?”

Imagine you have a full HMAC-SHA256 of the plaintext next to every ciphertext record with a static key, for searchability.

Each HMAC output corresponds 1:1 with a unique plaintext.

Because you’re using HMAC with a secret key, an attacker can’t just build a rainbow table like they would when attempting password cracking, but it still leaks duplicate plaintexts.

For example, an HMAC-SHA256 output might look like this: 04a74e4c0158e34a566785d1a5e1167c4e3455c42aea173104e48ca810a8b1ae

Art: CMYKat\

If you were to slice off most of those bytes (e.g. leaving only the last 3, which in the previous example yields a8b1ae), then with sufficient records, multiple plaintexts will now map to the same truncated HMAC tag.

Which means if you’re only revealing a truncated HMAC tag to the database server (both when storing records or retrieving them), you can now expect false positives due to collisions in your truncated HMAC tag.

These false positives give your data a discrete set of anonymity (called k-anonymity), which means an attacker with access to your database cannot:

1. Distinguish between two encrypted records with the same short HMAC tag.
2. Reverse engineer the short HMAC tag into a single possible plaintext value, even if they can supply candidate queries and study the tags sent to the database.

Art: CMYKat\

As with SSE above, this short HMAC technique exposes a trade-off to users.

• Too much k-anonymity (i.e. too many false positives), and you will have to decrypt-then-discard multiple mismatching records. This can make queries slow.
• Not enough k-anonymity (i.e. insufficient false positives), and you’re no better off than a full HMAC.

Even more troublesome, the right amount to truncate is expressed in bits (not bytes), and calculating this value depends on the number of unique plaintext values you anticipate in your dataset. (Fortunately, it grows logarithmically, so you’ll rarely if ever have to tune this.)

If you’d like to play with this idea, here’s a quick and dirty demo script.

Intermission

If you started reading this post with any doubts about Cendyne’s statement that “Database cryptography is hard”, by making it to this point, they’ve probably been long since put to rest.

Art: Harubaki

Conversely, anyone that specializes in this topic is probably waiting for me to say anything novel or interesting; their patience wearing thin as I continue to rehash a surface-level introduction of their field without really diving deep into anything.

Thus, if you’ve read this far, I’d like to demonstrate the application of what I’ve covered thus far into a real-world case study into an database cryptography product.

Case Study: MongoDB Client-Side Encryption

MongoDB is an open source schema-free NoSQL database. Last year, MongoDB made waves when they announced Queryable Encryption in their upcoming client-side encryption release.

Taken from the press release, but adapted for dark themes.

A statement at the bottom of their press release indicates that this isn’t clown-shoes:

Queryable Encryption was designed by MongoDB’s Advanced Cryptography Research Group, headed by Seny Kamara and Tarik Moataz, who are pioneers in the field of encrypted search. The Group conducts cutting-edge peer-reviewed research in cryptography and works with MongoDB engineering teams to transfer and deploy the latest innovations in cryptography and privacy to the MongoDB data platform.

If you recall, I mentioned Seny Kamara in the SSE section of this post. They certainly aren’t wrong about Kamara and Moataz being pioneers in this field.

So with that in mind, let’s explore the implementation in libmongocrypt and see how it stands up to scrutiny.

MongoCrypt: The Good

MongoDB’s encryption library takes key management seriously: They provide a KMS integration for cloud users by default (supporting both AWS and Azure).

MongoDB uses Encrypt-then-MAC with AES-CBC and HMAC-SHA256, which is congruent to what Signal does for message encryption.

How Is Queryable Encryption Implemented?

From the current source code, we can see that MongoCrypt generates several different types of tokens, using HMAC (calculation defined here).

According to their press release:

The feature supports equality searches, with additional query types such as range, prefix, suffix, and substring planned for future releases.

MongoDB Queryable Encryption Announcement

Which means that most of the juicy details probably aren’t public yet.

These HMAC-derived tokens are stored wholesale in the data structure, but most are encrypted before storage using AES-CTR.

There are more layers of encryption (using AEAD), server-side token processing, and more AES-CTR-encrypted edge tokens. All of this is finally serialized (implementation) as one blob for storage.

Since only the equality operation is currently supported (which is the same feature you’d get from HMAC), it’s difficult to speculate what the full feature set looks like.

However, since Kamara and Moataz are leading its development, it’s likely that this feature set will be excellent.

MongoCrypt: The Bad

Every call to do_encrypt() includes at most the Key ID (but typically NULL) as the AAD. This means that the concerns over Confused Deputies (and NoSQL specifically) are relevant to MongoDB.

However, even if they did support authenticating the fully qualified path to a field in the AAD for their encryption, their AEAD construction is vulnerable to the kind of canonicalization attack I wrote about previously.

First, observe this code which assembles the multi-part inputs into HMAC.

/* Construct the input to the HMAC */uint32_t num_intermediates = 0;_mongocrypt_buffer_t intermediates[3];// -- snip --if (!_mongocrypt_buffer_concat ( &to_hmac, intermediates, num_intermediates)) { CLIENT_ERR ("failed to allocate buffer"); goto done;}if (hmac == HMAC_SHA_512_256) { uint8_t storage[64]; _mongocrypt_buffer_t tag = {.data = storage, .len = sizeof (storage)}; if (!_crypto_hmac_sha_512 (crypto, Km, &to_hmac, &tag, status)) { goto done; } // Truncate sha512 to first 256 bits. memcpy (out->data, tag.data, MONGOCRYPT_HMAC_LEN);} else { BSON_ASSERT (hmac == HMAC_SHA_256); if (!_mongocrypt_hmac_sha_256 (crypto, Km, &to_hmac, out, status)) { goto done; }}

The implementation of _mongocrypt_buffer_concat() can be found here.

If either the implementation of that function, or the code I snipped from my excerpt, had contained code that prefixed every segment of the AAD with the length of the segment (represented as a uint64_t to make overflow infeasible), then their AEAD mode would not be vulnerable to canonicalization issues.

Using TupleHash would also have prevented this issue.

Silver lining for MongoDB developers: Because the AAD is either a key ID or NULL, this isn’t exploitable in practice.

The first cryptographic flaw sort of cancels the second out.

If the libmongocrypt developers ever want to mitigate Confused Deputy attacks, they’ll need to address this canonicalization issue too.

MongoCrypt: The Ugly

MongoCrypt supports deterministic encryption.

If you specify deterministic encryption for a field, your application passes a deterministic initialization vector to AEAD.

MongoDB documentation

We already discussed why this is bad above.

Wrapping Up

This was not a comprehensive treatment of the field of database cryptography. There are many areas of this field that I did not cover, nor do I feel qualified to discuss.

However, I hope anyone who takes the time to read this finds themselves more familiar with the subject.

Additionally, I hope any developers who think “encrypting data in a database is [easy, trivial] (select appropriate)” will find this broad introduction a humbling experience.

Art: CMYKat

https://soatok.blog/2023/03/01/database-cryptography-fur-the-rest-of-us/

#appliedCryptography #blockCipherModes #cryptography #databaseCryptography #databases #encryptedSearch #HMAC #MongoCrypt #MongoDB #QueryableEncryption #realWorldCryptography #security #SecurityGuidance #SQL #SSE #symmetricCryptography #symmetricSearchableEncryption

Dhole Moments

2021-11-17 11:46:54

NIST opened public comments on SP 800-108 Rev. 1 (the NIST recommendations for Key Derivation Functions) last month. The main thing that’s changed from the original document published in 2009 is the inclusion of the Keccak-based KMAC alongside the incumbent algorithms.

One of the recommendations of SP 800-108 is called “KDF in Counter Mode”. A related document, SP 800-56C, suggests using a specific algorithm called HKDF instead of the generic Counter Mode construction from SP 800-108–even though they both accomplish the same goal.

Isn’t standards compliance fun?

Interestingly, HKDF isn’t just an inconsistently NIST-recommended KDF, it’s also a common building block in a software developer’s toolkit which sees a lot of use in different protocols.

Unfortunately, the way HKDF is widely used is actually incorrect given its formal security definition. I’ll explain what I mean in a moment.

Art: Scruff

What is HKDF?

To first understand what HKDF is, you first need to know about HMAC.

HMAC is a standard message authentication code (MAC) algorithm built with cryptographic hash functions (that’s the H). HMAC is specified in RFC 2104 (yes, it’s that old).

HKDF is a key-derivation function that uses HMAC under-the-hood. HKDF is commonly used in encryption tools (Signal, age). HKDF is specified in RFC 5869.

HKDF is used to derive a uniformly-random secret key, typically for use with symmetric cryptography algorithms. In any situation where a key might need to be derived, you might see HKDF being used. (Although, there may be better algorithms.)

Art: LvJ

How Developers Understand and Use HKDF

If you’re a software developer working with cryptography, you’ve probably seen an API in the crypto module for your programming language that looks like this, or maybe this.

hash_hkdf( string $algo, string $key, int $length = 0, string $info = "", string $salt = ""): string

Software developers that work with cryptography will typically think of the HKDF parameters like so:

• $algo — which hash function to use
• $key — the input key, from which multiple keys can be derived
• $length — how many bytes to derive
• $info — some arbitrary string used to bind a derived key to an intended context
• $salt — some additional randomness (optional)

The most common use-case of HKDF is to implement key-splitting, where a single input key (the Initial Keying Material, or IKM) is used to derive two or more independent keys, so that you’re never using a single key for multiple algorithms.

See also: [url=https://github.com/defuse/php-encryption]defuse/php-encryption[/url], a popular PHP encryption library that does exactly what I just described.

At a super high level, the HKDF usage I’m describing looks like this:

class MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'encryption', $salt )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'message authentication', $salt )); return [$encryptKey, $authKey];}public function encryptString(string $plaintext, CryptographyKey $key): string{ $salt = random_bytes(32); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... encryption logic here ... return base64_encode($salt . $ciphertext . $mac);}public function decryptString(string $encrypted, CryptographyKey $key): string{ $decoded = base64_decode($encrypted); $salt = mb_substr($decoded, 0, 32, '8bit'); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... decryption logic here ... return $plaintext;}// ... other method here ...}

Unfortunately, anyone who ever does something like this just violated one of the core assumptions of the HKDF security definition and no longer gets to claim “KDF security” for their construction. Instead, your protocol merely gets to claim “PRF security”.

Art: Harubaki

KDF? PRF? OMGWTFBBQ?

Let’s take a step back and look at some basic concepts.

(If you want a more formal treatment, read this Stack Exchange answer.)

PRF: Pseudo-Random Functions

A pseudorandom function (PRF) is an efficient function that emulates a random oracle.

“What the hell’s a random oracle?” you ask? Well, Thomas Pornin has the best explanation for random oracles:

A random oracle is described by the following model:

• There is a black box. In the box lives a gnome, with a big book and some dice.
• We can input some data into the box (an arbitrary sequence of bits).
• Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
• If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message m. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really “random” oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Thomas Pornin

Alternatively, Wikipedia has a more formal definition available to the academic-inclined.

In practical terms, we can generate a strong PRF out of secure cryptographic hash functions by using a keyed construction; i.e. HMAC.

Thus, as long as your HMAC key is a secret, the output of HMAC can be generally treated as a PRF for all practical purposes. Your main security consideration (besides key management) is the collision risk if you truncate its output.

Art: LvJ

KDF: Key Derivation Functions

A key derivation function (KDF) is exactly what it says on the label: a cryptographic algorithm that derives one or more cryptographic keys from a secret input (which may be another cryptography key, a group element from a Diffie-Hellman key exchange, or a human-memorable password).

Note that passwords should be used with a Password-Based Key Derivation Function, such as scrypt or Argon2id, not HKDF.

Despite what you may read online, KDFs do not need to be built upon cryptographic hash functions, specifically; but in practice, they often are.

A notable counter-example to this hash function assumption: CMAC in Counter Mode (from NIST SP 800-108) uses AES-CMAC, which is a variable-length input variant of CBC-MAC. CBC-MAC uses a block cipher, not a hash function.

Regardless of the construction, KDFs use a PRF under the hood, and the output of a KDF is supposed to be a uniformly random bit string.

Art: LvJ

PRF vs KDF Security Definitions

The security definition for a KDF has more relaxed requirements than PRFs: PRFs require the secret key be uniformly random. KDFs do not have this requirement.

If you use a KDF with a non-uniformly random IKM, you probably need the KDF security definition.

If your IKM is already uniformly random (i.e. the “key separation” use case), you can get by with just a PRF security definition.

After all, the entire point of KDFs is to allow a congruent security level as you’d get from uniformly random secret keys, without also requiring them.

However, if you’re building a protocol with a security requirement satisfied by a KDF, but you actually implemented a PRF (i.e., not a KDF), this is a security vulnerability in your cryptographic design.

Art: LvJ

The HKDF Algorithm

HKDF is an HMAC-based KDF. Its algorithm consists of two distinct steps:

1. HKDF-Extract uses the Initial Keying Material (IKM) and Salt to produce a Pseudo-Random Key (PRK).
2. HKDF-Expand actually derives the keys using PRK, the info parameter, and a counter (from 0 to 255) for each hash function output needed to generate the desired output length.

If you’d like to see an implementation of this algorithm, defuse/php-encryption provides one (since it didn’t land in PHP until 7.1.0). Alternatively, there’s a Python implementation on Wikipedia that uses HMAC-SHA256.

This detail about the two steps will matter a lot in just a moment.

Art: Swizz

How HKDF Salts Are Misused

The HKDF paper, written by Hugo Krawczyk, contains the following definition (page 7).

The paper goes on to discuss the requirements for authenticating the salt over the communication channel, lest the attacker have the ability to influence it.

A subtle detail of this definition is that the security definition says that A salt value , not Multiple salt values.

Which means: You’re not supposed to use HKDF with a constant IKM, info label, etc. but vary the salt for multiple invocations. The salt must either be a fixed random value, or NULL.

The HKDF RFC makes this distinction even less clear when it argues for random salts.

We stress, however, that the use of salt adds significantly to the strength of HKDF, ensuring independence between different uses of the hash function, supporting “source-independent” extraction, and strengthening the analytical results that back the HKDF design.

Random salt differs fundamentally from the initial keying material in two ways: it is non-secret and can be re-used. As such, salt values are available to many applications. For example, a pseudorandom number generator (PRNG) that continuously produces outputs by applying HKDF to renewable pools of entropy (e.g., sampled system events) can fix a salt value and use it for multiple applications of HKDF without having to protect the secrecy of the salt. In a different application domain, a key agreement protocol deriving cryptographic keys from a Diffie-Hellman exchange can derive a salt value from public nonces exchanged and authenticated between communicating parties as part of the key agreement (this is the approach taken in [IKEv2]).

RFC 5869, section 3.1

Okay, sure. Random salts are better than a NULL salt. And while this section alludes to “[fixing] a salt value” to “use it for multiple applications of HKDF without having to protect the secrecy of the salt”, it never explicitly states this requirement. Thus, the poor implementor is left to figure this out on their own.

Thus, because it’s not using HKDF in accordance with its security definition, many implementations (such as the PHP encryption library we’ve been studying) do not get to claim that their construction has KDF security.

Instead, they only get to claim “Strong PRF” security, which you can get from just using HMAC.

Art: LvJ

What Purpose Do HKDF Salts Actually Serve?

Recall that the HKDF algorithm uses salts in the HDKF-Extract step. Salts in this context were intended for deriving keys from a Diffie-Hellman output, or a human-memorable password.

In the case of [Elliptic Curve] Diffie-Hellman outputs, the result of the key exchange algorithm is a random group element, but not necessarily uniformly random bit string. There’s some structure to the output of these functions. This is why you always, at minimum, apply a cryptographic hash function to the output of [EC]DH before using it as a symmetric key.

HKDF uses salts as a mechanism to improve the quality of randomness when working with group elements and passwords.

Extending the nonce for a symmetric-key AEAD mode is a good idea, but using HKDF’s salt parameter specifically to accomplish this is a misuse of its intended function, and produces a weaker argument for your protocol’s security than would otherwise be possible.

How Should You Introduce Randomness into HKDF?

Just shove it in the info parameter.

Art: LvJ

It may seem weird, and defy intuition, but the correct way to introduce randomness into HKDF as most developers interact with the algorithm is to skip the salt parameter entirely (either fixing it to a specific value for domain-separation or leaving it NULL), and instead concatenate data into the info parameter.

class BetterEncryptor extends MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'encryption', '' // intentionally empty )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'message authentication', '' // intentionally empty )); return [$encryptKey, $authKey];}}

Of course, you still have to watch out for canonicalization attacks if you’re feeding multi-part messages into the info tag.

Another advantage: This also lets you optimize your HKDF calls by caching the PRK from the HKDF-Extract step and reuse it for multiple invocations of HKDF-Expand with a distinct info. This allows you to reduce the number of hash function invocations from to (since each HMAC involves two hash function invocations).

Notably, this HKDF salt usage was one of the things that was changed in V3/V4 of PASETO.

Does This Distinction Really Matter?

If it matters, your cryptographer will tell you it matters–which probably means they have a security proof that assumes the KDF security definition for a very good reason, and you’re not allowed to violate that assumption.

Otherwise, probably not. Strong PRF security is still pretty damn good for most threat models.

Art: LvJ

Closing Thoughts

If your takeaway was, “Wow, I feel stupid,” don’t, because you’re in good company.

I’ve encountered several designs in my professional life that shoved the randomness into the info parameter, and it perplexed me because there was a perfectly good salt parameter right there. It turned out, I was wrong to believe that, for all of the subtle and previously poorly documented reasons discussed above. But now we both know, and we’re all better off for it.

So don’t feel dumb for not knowing. I didn’t either, until this was pointed out to me by a very patient colleague.

“Feeling like you were stupid” just means you learned.
(Art: LvJ)

Also, someone should really get NIST to be consistent about whether you should use HKDF or “KDF in Counter Mode with HMAC” as a PRF, because SP 800-108’s new revision doesn’t concede this point at all (presumably a relic from the 2009 draft).

This concession was made separately in 2011 with SP 800-56C revision 1 (presumably in response to criticism from the 2010 HKDF paper), and the present inconsistency is somewhat vexing.

(On that note, does anyone actually use the NIST 800-108 KDFs instead of HKDF? If so, why? Please don’t say you need CMAC…)

Bonus Content

These questions were asked after this blog post initially went public, and I thought they were worth adding. If you ask a good question, it may end up being edited in at the end, too.

Art: LvJ

Why Does HKDF use the Salt as the HMAC key in the Extract Step? (via r/crypto)

Broadly speaking, when applying a PRF to two “keys”, you get to decide which one you treat as the “key” in the underlying API.

HMAC’s API is HMACalg(key, message), but how HKDF uses it might as well be HMACalg(key1, key2).

The difference here seems almost arbitrary, but there’s a catch.

HKDF was designed for Diffie-Hellman outputs (before ECDH was the norm), which are generally able to be much larger than the block size of the underlying hash function. 2048-bit DH results fit in 256 bytes, which is 4 times the SHA256 block size.

If you have to make a decision, using the longer input (DH output) as the message is more intuitive for analysis than using it as the key, due to pre-hashing. I’ve discussed the counter-intuitive nature of HMAC’s pre-hashing behavior at length in this post, if you’re interested.

So with ECDH, it literally doesn’t matter which one was used (unless you have a weird mismatch in hash functions and ECC groups; i.e. NIST P-521 with SHA-224).

But before the era of ECDH, it was important to use the salt as the HMAC key in the extract step, since they were necessarily smaller than a DH group element.

Thus, HKDF chose HMACalg(salt, IKM) instead of HMACalg(IKM, salt) for the calculation of PRK in the HKDF-Extract step.

Neil Madden also adds that the reverse would create a chicken-egg situation, but I personally suspect that the pre-hashing would be more harmful to the security analysis than merely supplying a non-uniformly random bit string as an HMAC key in this specific context.

My reason for believing this is, when a salt isn’t supplied, it defaults to a string of 0x00 bytes as long as the output size of the underlying hash function. If the uniform randomness of the salt mattered that much, this wouldn’t be a tolerable condition.

https://soatok.blog/2021/11/17/understanding-hkdf/

#cryptographicHashFunction #cryptography #hashFunction #HMAC #KDF #keyDerivationFunction #securityDefinition #SecurityGuidance

Spyware written for educational institutions to flex their muscles of control over students and their families when learning from their home computer is still, categorically, spyware.

Depending on your persuasion, the previous sentence sounds like either needless pedantry, or it reads like tautology. But we need to be clear on our terms.

1. Educational spyware is still spyware.
2. Spyware is categorized as a subset of malware.

When vulnerabilities are discovered in malware, the normal rules of coordinated disclosure are out of scope. Are we clear?

(Art by Khia.)

So let’s talk about Proctorio!

https://twitter.com/Angry_Cassie/status/1301360994044850182

I won’t go into the details of Proctorio or why it’s terrible for (especially disadvantaged) students. Read Cassie’s Twitter thread for more context on that. Seriously. I’m not gonna be one of those guys that talks over women, and neither should you.

What I am here to talk about today is these dubious claim about the security of their product:

From their Data Security page.

Zero-Knowledge Encryption? OMGWTFBBQ!

In cryptography, there are a class of algorithms called Zero-Knowledge Proofs. In a Zero-Knowledge Proof, you prove that you possess some fact without revealing any details about the fact.

It’s kind of abstract to think about (and until we’re ready to talk about Pedersen commitments, I’m just going to defer to Sarah Jamie Lewis), but the only thing you need to know about “Zero Knowledge” in Cryptography is that the output is a boolean (True, False).

You can’t use “Zero Knowledge” anything to encrypt. So “Zero-Knowledge Encryption” is a meaningless buzzword.

https://twitter.com/SchmiegSophie/status/1304407483658592256

So what are they actually describing when they say Zero Knowledge Encryption?

Also from their Data Security page.

Okay, so they’ve built their own key distribution system and are encrypting with AES-GCM… and shipped this in a Chrome extension. But before we get to that, look at this Daily Vulnerability Tests claim.

Bullshit.

Running Nessus (or equivalent) on a cron job isn’t meaningful metric of security. At best, it creates alert fatigue when you accidentally screw up a deployment configuration or forget to update your software for 4+ years. (Y’know, like JsZip 3.2.1, which they bundle.)

A dumb vulnerability scan isn’t the same thing as a routine (usually quarterly) penetration test or a code audit. And if you’re working in cryptography, you better have both!

Timing Leaks in Proctorio’s AES-GCM Implementation

If you download version 1.4.20241.1.0 of the Proctorio Chrome Extension, run src/assets/J5HG.js through a JS beautifier, and then look at its contents, you will quickly realize this is a JavaScript cryptography library.

Since the “zero knowledge” encryption they’re so proud about uses AES-GCM, let’s focus on that.

Proctorio’s AES-GCM implementation exists in an object called dhs.mode.gcm, which is mildly obfuscated, but contains the following functions:

• encrypt() – Encrypt with AES-GCM
• decrypt() – Decrypt with AES-GCM
• aa() – GHASH block multiplication
• j() – XOR + GMAC utility function
• O() – Called by encrypt() and decrypt(); does all of the AES-CTR + GMAC fun

If you’re not familiar with AES-GCM, just know this: Timing leaks can be used to leak your GMAC key to outside applications, which completely breaks the authentication of AES-GCM and opens the door to chosen-ciphertext attacks.

So is their implementation of AES-GCM constant-time? Let’s take a look at aa():

aa: function(a, b) { var c, d, e, f, g, h = dhs.bitArray.ba; for (e = [0, 0, 0, 0], f = b.slice(0), c = 0; 128 > c; c++) { for ( (d = 0 !== (a[Math.floor(c / 32)] & 1 << 31 - c % 32)) && (e = h(e, f)), g = 0 !== (1 & f[3]), d = 3; d > 0; d-- ) f[d] = f[d] >>> 1 | (1 & f[d - 1]) << 31; f[0] >>>= 1, g && (f[0] ^= -520093696) } return e},

This is a bit obtuse, but this line leaks the lowest bit of f with each iteration: g = 0 !== (1 & f[3]).

Since f gets bitwise right-shifted 128 times, this actually leaks the bit of every value of f in each block multiplication, since the execution of (f[0] ^= -520093696) depends on whether or not g is set to true.

Timing leaks? So much for “zero-knowledge”!

Also, they claim to be FIPS 140-2 compliant, but this is how they generate randomness in their cryptography library.

https://twitter.com/SoatokDhole/status/1304623361461547009

(Although, that’s probably a lie.)

To mitigate these vulnerabilities, one needs look no further than the guide to side-channel attacks I published last month.

(Also, use WebCrypto to generate entropy! What the fuck.)

If Proctorio is Insecure, What Should We Use Instead?

Nothing.

Schools that demand students install spyware on their personal computers are only a step removed from domestic abusers who install stalkerware on their victims’ phones.

Proctorio isn’t the problem here, they’re only a symptom.

Schools that insist on violating the integrity and parental dominion of their students’ home computers are the problem here.

https://twitter.com/lex_about_sex/status/1304156305398140928

If you want to ensure the integrity of students’ education, try teaching them about consent and ethical computing. (Y’know, concepts that are fundamentally incompatible with the business model of Proctorio and Proctorio’s competitors.)

Disclosure Timeline

Really? Really?

This was a zero-day disclosure, because full disclosure is the responsible choice when dealing with spyware. Don’t even @ me.

Disclaimer: This security research was conducted by Soatok– some furry on the Internet–while bored on his off-time and does not reflect the opinions of any company.

Domains to Sinkhole

If you’re looking to protect your home network from this spyware, here are a list of domains to sinkhole (i.e. with Pi-Hole).

• proctorauth.com
• proctordata.com
• getproctorio.com
• proctor.io
• proctor.in
• az545770.vo.msecnd.net

Update (2020-09-16): AES in a Hole

I got curious about the security of how they were encrypting data, not just the authentication of that encrypted data.

After all, if Proctorio decided to home-bake GCM in an insecure way, it’s overwhelmingly likely that they rolled their own AES implementation too.

Interlude: Software AES

Implementing AES in software is terrifying. Even moreso in JavaScript, since your code might be secure in a Node.js environment but insecure in a web browser–or vice versa! And you have no way of knowing as a JavaScript developer because you can’t verify the interpreter.

At the risk of being slightly reductionist, Software AES can be implemented in roughly two ways:

1. The insecure but fast way.
2. The slow but secure way.

Option 1 means using table look-ups, which are fast, but vulnerable to cache-timing attacks.

Option 2 means using a bitsliced implementation, like BearSSL provides.

Naturally, Proctorio’s AES Implementation Went For Option 1

I’m beginning to think Proctorio’s use of “zero-knowledge” is nothing more than self-description. (Art by Khia.)

You can find their AES implementation in the dhs.cipher.aes and w functions in J5HG.js.

What Is the Risk to Students?

Cache-timing vulnerabilities are much more dangerous to students than the previously disclosed issue with GMAC.

That is to say: They cough up your encryption keys. Furthermore, these only took 65 milliseconds to exploit (on 2006 hardware, to boot).

Cache-timing leaks can be easily exploited from other processes running on the same computer as Proctorio. This includes JavaScript code running in another browser window or tab.

Successfully exploiting this vulnerability would net you the keys used by Proctorio to encrypt and authenticate data, and exploiting it would not require violating any of the operating system’s security boundaries. Just running exploit code on the same hardware.

Isn’t cryptography fun?

https://soatok.blog/2020/09/12/edutech-spyware-is-still-spyware-proctorio-edition/

#AESGCM #cryptography #EduTech #JavaScript #Spyware #ZeroDay

Dhole Moments

2020-05-13 10:00:22

If you’re reading this wondering if you should stop using AES-GCM in some standard protocol (TLS 1.3), the short answer is “No, you’re fine”.

I specialize in secure implementations of cryptography, and my years of experience in this field have led me to dislike AES-GCM.

This post is about why I dislike AES-GCM’s design, not “why AES-GCM is insecure and should be avoided”. AES-GCM is still miles above what most developers reach for when they want to encrypt (e.g. ECB mode or CBC mode). If you want a detailed comparison, read this.

To be clear: This is solely my opinion and not representative of any company or academic institution.

What is AES-GCM?

AES-GCM is an authenticated encryption mode that uses the AES block cipher in counter mode with a polynomial MAC based on Galois field multiplication.

In order to explain why AES-GCM sucks, I have to first explain what I dislike about the AES block cipher. Then, I can describe why I’m filled with sadness every time I see the AES-GCM construction used.

What is AES?

The Advanced Encryption Standard (AES) is a specific subset of a block cipher called Rijndael.

Rijndael’s design is based on a substitution-permutation network, which broke tradition from many block ciphers of its era (including its predecessor, DES) in not using a Feistel network.

AES only includes three flavors of Rijndael: AES-128, AES-192, and AES-256. The difference between these flavors is the size of the key and the number of rounds used, but–and this is often overlooked–not the block size.

As a block cipher, AES always operates on 128-bit (16 byte) blocks of plaintext, regardless of the key size.

This is generally considered acceptable because AES is a secure pseudorandom permutation (PRP), which means that every possible plaintext block maps directly to one ciphertext block, and thus birthday collisions are not possible. (A pseudorandom function (PRF), conversely, does have birthday bound problems.)

Why AES Sucks

Art by Khia.

Side-Channels

The biggest reason why AES sucks is that its design uses a lookup table (called an S-Box) indexed by secret data, which is inherently vulnerable to cache-timing attacks (PDF).

There are workarounds for this AES vulnerability, but they either require hardware acceleration (AES-NI) or a technique called bitslicing.

The short of it is: With AES, you’re either using hardware acceleration, or you have to choose between performance and security. You cannot get fast, constant-time AES without hardware support.

Block Size

AES-128 is considered by experts to have a security level of 128 bits.

Similarly, AES-192 gets certified at 192-bit security, and AES-256 gets 256-bit security.

However, the AES block size is only 128 bits!

That might not sound like a big deal, but it severely limits the constructions you can create out of AES.

Consider the case of AES-CBC, where the output of each block of encryption is combined with the next block of plaintext (using XOR). This is typically used with a random 128-bit block (called the initialization vector, or IV) for the first block.

This means you expect a collision after encrypting (at 50% probability) blocks.

When you start getting collisions, you can break CBC mode, as this video demonstrates:

https://www.youtube.com/watch?v=v0IsYNDMV7A

This is significantly smaller than the you expect from AES.

Post-Quantum Security?

With respect to the number of attempts needed to find the correct key, cryptographers estimate that AES-128 will have a post-quantum security level of 64 bits, AES-192 will have a post-quantum security level of 96 bits, and AES-256 will have a post-quantum security level of 128 bits.

This is because Grover’s quantum search algorithm can search unsorted items in time, which can be used to reduce the total number of possible secrets from to . This effectively cuts the security level, expressed in bits, in half.

Note that this heuristic estimate is based on the number of guesses (a time factor), and doesn’t take circuit size into consideration. Grover’s algorithm also doesn’t parallelize well. The real-world security of AES may still be above 100 bits if you consider these nuances.

But remember, even AES-256 operates on 128-bit blocks.

Consequently, for AES-256, there should be approximately (plaintext, key) pairs that produce any given ciphertext block.

Furthermore, there will be many keys that, for a constant plaintext block, will produce the same ciphertext block despite being a different key entirely. (n.b. This doesn’t mean for all plaintext/ciphertext block pairings, just some arbitrary pairing.)

Concrete example: Encrypting a plaintext block consisting of sixteen NUL bytes will yield a specific 128-bit ciphertext exactly once for each given AES-128 key. However, there are times as many AES-256 keys as there are possible plaintext/ciphertexts. Keep this in mind for AES-GCM.

This means it’s conceivable to accidentally construct a protocol that, despite using AES-256 safely, has a post-quantum security level on par with AES-128, which is only 64 bits.

This would not be nearly as much of a problem if AES’s block size was 256 bits.

Real-World Example: Signal

The Signal messaging app is the state-of-the-art for private communications. If you were previously using PGP and email, you should use Signal instead.

Signal aims to provide private communications (text messaging, voice calls) between two mobile devices, piggybacking on your pre-existing contacts list.

Part of their operational requirements is that they must be user-friendly and secure on a wide range of Android devices, stretching all the way back to Android 4.4.

The Signal Protocol uses AES-CBC + HMAC-SHA256 for message encryption. Each message is encrypted with a different AES key (due to the Double Ratchet), which limits the practical blast radius of a cache-timing attack and makes practical exploitation difficult (since you can’t effectively replay decryption in order to leak bits about the key).

Thus, Signal’s message encryption is still secure even in the presence of vulnerable AES implementations.

Hooray for well-engineered protocols managing to actually protect users.
Art by Swizz.

However, the storage service in the Signal App uses AES-GCM, and this key has to be reused in order for the encrypted storage to operate.

This means, for older phones without dedicated hardware support for AES (i.e. low-priced phones from 2013, which Signal aims to support), the risk of cache-timing attacks is still present.

This is unacceptable!

What this means is, a malicious app that can flush the CPU cache and measure timing with sufficient precision can siphon the AES-GCM key used by Signal to encrypt your storage without ever violating the security boundaries enforced by the Android operating system.

As a result of the security boundaries never being crossed, these kind of side-channel attacks would likely evade forensic analysis, and would therefore be of interest to the malware developers working for nation states.

Of course, if you’re on newer hardware (i.e. Qualcomm Snapdragon 835), you have hardware-accelerated AES available, so it’s probably a moot point.

Why AES-GCM Sucks Even More

AES-GCM is an authenticated encryption mode that also supports additional authenticated data. Cryptographers call these modes AEAD.

AEAD modes are more flexible than simple block ciphers. Generally, your encryption API accepts the following:

1. The plaintext message.
2. The encryption key.
3. A nonce (: A number that must only be used once).
4. Optional additional data which will be authenticated but not encrypted.

The output of an AEAD function is both the ciphertext and an authentication tag, which is necessary (along with the key and nonce, and optional additional data) to decrypt the plaintext.

Cryptographers almost universally recommend using AEAD modes for symmetric-key data encryption.

That being said, AES-GCM is possibly my least favorite AEAD, and I’ve got good reasons to dislike it beyond simply, “It uses AES”.

The deeper you look into AES-GCM’s design, the harder you will feel this sticker.

GHASH Brittleness

The way AES-GCM is initialized is stupid: You encrypt an all-zero block with your AES key (in ECB mode) and store it in a variable called . This value is used for authenticating all messages authenticated under that AES key, rather than for a given (key, nonce) pair.
Diagram describing Galois/Counter Mode, taken from Wikipedia.
This is often sold as an advantage: Reusing allows for better performance. However, it makes GCM brittle: Reusing a nonce allows an attacker to recover H and then forge messages forever. This is called the “forbidden attack”, and led to real world practical breaks.

Let’s contrast AES-GCM with the other AEAD mode supported by TLS: ChaCha20-Poly1305, or ChaPoly for short.

ChaPoly uses one-time message authentication keys (derived from each key/nonce pair). If you manage to leak a Poly1305 key, the impact is limited to the messages encrypted under that (ChaCha20 key, nonce) pair.

While that’s still bad, it isn’t “decrypt all messages under that key forever” bad like with AES-GCM.

Note: “Message Authentication” here is symmetric, which only provides a property called message integrity, not sender authenticity. For the latter, you need asymmetric cryptography (wherein the ability to verify a message doesn’t imply the capability to generate a new signature), which is totally disparate from symmetric algorithms like AES or GHASH. You probably don’t need to care about this nuance right now, but it’s good to know in case you’re quizzed on it later.

H Reuse and Multi-User Security

If you recall, AES operates on 128-bit blocks even when 256-bit keys are used.

If we assume AES is well-behaved, we can deduce that there are approximately different 256-bit keys that will map a single plaintext block to a single ciphertext block.

This is trivial to calculate. Simply divide the number of possible keys () by the number of possible block states () to yield the number of keys that produce a given ciphertext for a single block of plaintext: .

Each key that will map an arbitrarily specific plaintext block to a specific ciphertext block is also separated in the keyspace by approximately .

This means there are approximately independent keys that will map a given all-zero plaintext block to an arbitrarily chosen value of (if we assume AES doesn’t have weird biases).

Credit: Harubaki

“Why Does This Matter?”

It means that, with keys larger than 128 bits, you can model the selection of as a 128-bit pseudorandom function, rather than a 128-bit permutation. As a result, you an expect a collision with 50% probability after only different keys are selected.

Note: Your 128-bit randomly generated AES keys already have this probability baked into their selection, but this specific analysis doesn’t really apply for 128-bit keys since AES is a PRP, not a PRF, so there is no “collision” risk. However, you end up at the same upper limit either way.

But 50% isn’t good enough for cryptographic security.

In most real-world systems, we target a collision risk. So that means our safety limit is actually different AES keys before you have to worry about reuse.

This isn’t the same thing as symmetric wear-out (where you need to re-key after a given number of encryptions to prevent nonce reuse). Rather, it means after your entire population has exhausted the safety limit of different AES keys, you have to either accept the risk or stop using AES-GCM.

If you have a billion users (), the safety limit is breached after AES keys per user (approximately 262,000).

“What Good is H Reuse for Attackers if HF differs?”

There are two numbers used in AES-GCM that are derived from the AES key. is used for block multiplication, and (the value of with a counter of 0 from the following diagram) is XORed with the final result to produce the authentication tag.

The arrow highlighted with green is HF.

It’s tempting to think that a reuse of isn’t a concern because will necessarily be randomized, which prevents an attacker from observing when collides. It’s certainly true that the single-block collision risk discussed previously for will almost certainly not also result in a collision for . And since isn’t reused unless a nonce is reused (which also leaks directly), this might seem like a non-issue.

Art by Khia.

However, it’s straightforward to go from a condition of reuse to an adaptive chosen-ciphertext attack.

1. Intercept multiple valid ciphertexts.
   
   • e.g. Multiple JWTs encrypted with {"alg":"A256GCM"}

   
   

2. Use your knowledge of , the ciphertext, and the AAD to calculate the GCM tag up to the final XOR. This, along with the existing authentication tag, will tell you the value of for a given nonce.
3. Calculate a new authentication tag for a chosen ciphertext using and your candidate value, then replay it into the target system.

While the blinding offered by XORing the final output with is sufficient to stop from being leaked directly, the protection is one-way.

Ergo, a collision in is not sufficiently thwarted by .

“How Could the Designers Have Prevented This?”

The core issue here is the AES block size, again.

If we were analyzing a 256-bit block variant of AES, and a congruent GCM construction built atop it, none of what I wrote in this section would apply.

However, the 128-bit block size was a design constraint enforced by NIST in the AES competition. This block size was during an era of 64-bit block ciphers (e.g. Triple-DES and Blowfish), so it was a significant improvement at the time.

NIST’s AES competition also inherited from the US government’s tradition of thinking in terms of “security levels”, which is why there are three different permitted key sizes (128, 192, or 256 bits).

“Why Isn’t This a Vulnerability?”

There’s always a significant gap in security, wherein something isn’t safe to recommend, but also isn’t susceptible to a known practical attack. This gap is important to keep systems secure, even when they aren’t on the bleeding edge of security.

Using 1024-bit RSA is a good example of this: No one has yet, to my knowledge, successfully factored a 1024-bit RSA public key. However, most systems have recommended a minimum 2048-bit for years (and many recommend 3072-bit or 4096-bit today).

With AES-GCM, the expected distance between collisions in is , and finding an untargeted collision requires being able to observe more than different sessions, and somehow distinguish when collides.

As a user, you know that after different keys, you’ve crossed the safety boundary for avoiding collisions. But as an attacker, you need bites at the apple, not . Additionally, you need some sort of oracle or distinguisher for when this happens.

We don’t have that kind of distinguisher available to us today. And even if we had one available, the amount of data you need to search in order for any two users in the population to reuse/collide is challenging to work with. You would need the computational and data storages of a major cloud service provider to even think about pulling the attack off.

Naturally, this isn’t a practical vulnerability. This is just another gripe I have with AES-GCM, as someone who has to work with cryptographic algorithms a lot.

Short Nonces

Although the AES block size is 16 bytes, AES-GCM nonces are only 12 bytes. The latter 4 bytes are dedicated to an internal counter, which is used with AES in Counter Mode to actually encrypt/decrypt messages.

(Yes, you can use arbitrary length nonces with AES-GCM, but if you use nonces longer than 12 bytes, they get hashed into 12 bytes anyway, so it’s not a detail most people should concern themselves with.)

If you ask a cryptographer, “How much can I encrypt safely with AES-GCM?” you’ll get two different answers.

1. Message Length Limit: AES-GCM can be used to encrypt messages up to bytes long, under a given (key, nonce) pair.
2. Number of Messages Limit: If you generate your nonces randomly, you have a 50% chance of a nonce collision after messages.
   However, 50% isn’t conservative enough for most systems, so the safety margin is usually much lower. Cryptographers generally set the key wear-out of AES-GCM at random nonces, which represents a collision probability of one in 4 billion.

These limits are acceptable for session keys for encryption-in-transit, but they impose serious operational limits on application-layer encryption with long-term keys.

Random Key Robustness

Before the advent of AEAD modes, cryptographers used to combine block cipher modes of operation (e.g. AES-CBC, AES-CTR) with a separate message authentication code algorithm (e.g. HMAC, CBC-MAC).

You had to be careful in how you composed your protocol, lest you invite Cryptographic Doom into your life. A lot of developers screwed this up. Standardized AEAD modes promised to make life easier.

Many developers gained their intuition for authenticated encryption modes from protocols like Signal’s (which combines AES-CBC with HMAC-SHA256), and would expect AES-GCM to be a drop-in replacement.

Unfortunately, GMAC doesn’t offer the same security benefits as HMAC: Finding a different (ciphertext, HMAC key) pair that produces the same authentication tag is a hard problem, due to HMAC’s reliance on cryptographic hash functions. This makes HMAC-based constructions “message committing”, which instills Random Key Robustness.

Critically, AES-GCM doesn’t have this property. You can calculate a random (ciphertext, key) pair that collides with a given authentication tag very easily.

This fact prohibits AES-GCM from being considered for use with OPAQUE (which requires RKR), one of the upcoming password-authenticated key exchange algorithms. (Read more about them here.)

Better-Designed Algorithms

You might be thinking, “Okay random furry, if you hate AES-GCM so much, what would you propose we use instead?”

I’m glad you asked!

XChaCha20-Poly1305

For encrypting messages under a long-term key, you can’t really beat XChaCha20-Poly1305.

• ChaCha is a stream cipher based on a 512-bit ARX hash function in counter mode. ChaCha doesn’t use S-Boxes. It’s fast and constant-time without hardware acceleration.
• ChaCha20 is ChaCha with 20 rounds.
• XChaCha nonces are 24 bytes, which allows you to generate them randomly and not worry about a birthday collision until about messages (for the same collision probability as AES-GCM).
• Poly1305 uses different 256-bit key for each (nonce, key) pair and is easier to implement in constant-time than AES-GCM.
• XChaCha20-Poly1305 uses the first 16 bytes of the nonce and the 256-bit key to generate a distinct subkey, and then employs the standard ChaCha20-Poly1305 construction used in TLS today.

For application-layer cryptography, XChaCha20-Poly1305 contains most of the properties you’d want from an authenticated mode.

However, like AES-GCM (and all other Polynomial MACs I’ve heard of), it is not message committing.

The Gimli Permutation

For lightweight cryptography (n.b. important for IoT), the Gimli permutation (e.g. employed in libhydrogen) is an attractive option.

Gimli is a Round 2 candidate in NIST’s Lightweight Cryptography project. The Gimli permutation offers a lot of applications: a hash function, message authentication, encryption, etc.

Critically, it’s possible to construct a message-committing protocol out of Gimli that will hit a lot of the performance goals important to embedded systems.

Closing Remarks

Despite my personal disdain for AES-GCM, if you’re using it as intended by cryptographers, it’s good enough.

Don’t throw AES-GCM out just because of my opinions. It’s very likely the best option you have.

Although I personally dislike AES and GCM, I’m still deeply appreciative of the brilliance and ingenuity that went into both designs.

My desire is for the industry to improve upon AES and GCM in future cipher designs so we can protect more people, from a wider range of threats, in more diverse protocols, at a cheaper CPU/memory/time cost.

We wouldn’t have a secure modern Internet without the work of Vincent Rijmen, Joan Daemen, John Viega, David A. McGrew, and the countless other cryptographers and security researchers who made AES-GCM possible.

Change Log

• 2021-10-26: Added section on H Reuse and Multi-User Security.

https://soatok.blog/2020/05/13/why-aes-gcm-sucks/

#AES #AESGCM #cryptography #GaloisCounterMode #opinion #SecurityGuidance #symmetricCryptography

NIST opened public comments on SP 800-108 Rev. 1 (the NIST recommendations for Key Derivation Functions) last month. The main thing that’s changed from the original document published in 2009 is the inclusion of the Keccak-based KMAC alongside the incumbent algorithms.

One of the recommendations of SP 800-108 is called “KDF in Counter Mode”. A related document, SP 800-56C, suggests using a specific algorithm called HKDF instead of the generic Counter Mode construction from SP 800-108–even though they both accomplish the same goal.

Isn’t standards compliance fun?

Interestingly, HKDF isn’t just an inconsistently NIST-recommended KDF, it’s also a common building block in a software developer’s toolkit which sees a lot of use in different protocols.

Unfortunately, the way HKDF is widely used is actually incorrect given its formal security definition. I’ll explain what I mean in a moment.

Art: Scruff

What is HKDF?

To first understand what HKDF is, you first need to know about HMAC.

HMAC is a standard message authentication code (MAC) algorithm built with cryptographic hash functions (that’s the H). HMAC is specified in RFC 2104 (yes, it’s that old).

HKDF is a key-derivation function that uses HMAC under-the-hood. HKDF is commonly used in encryption tools (Signal, age). HKDF is specified in RFC 5869.

HKDF is used to derive a uniformly-random secret key, typically for use with symmetric cryptography algorithms. In any situation where a key might need to be derived, you might see HKDF being used. (Although, there may be better algorithms.)

Art: LvJ

How Developers Understand and Use HKDF

If you’re a software developer working with cryptography, you’ve probably seen an API in the crypto module for your programming language that looks like this, or maybe this.

hash_hkdf( string $algo, string $key, int $length = 0, string $info = "", string $salt = ""): string

Software developers that work with cryptography will typically think of the HKDF parameters like so:

• $algo — which hash function to use
• $key — the input key, from which multiple keys can be derived
• $length — how many bytes to derive
• $info — some arbitrary string used to bind a derived key to an intended context
• $salt — some additional randomness (optional)

The most common use-case of HKDF is to implement key-splitting, where a single input key (the Initial Keying Material, or IKM) is used to derive two or more independent keys, so that you’re never using a single key for multiple algorithms.

See also: [url=https://github.com/defuse/php-encryption]defuse/php-encryption[/url], a popular PHP encryption library that does exactly what I just described.

At a super high level, the HKDF usage I’m describing looks like this:

class MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'encryption', $salt )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, 'message authentication', $salt )); return [$encryptKey, $authKey];}public function encryptString(string $plaintext, CryptographyKey $key): string{ $salt = random_bytes(32); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... encryption logic here ... return base64_encode($salt . $ciphertext . $mac);}public function decryptString(string $encrypted, CryptographyKey $key): string{ $decoded = base64_decode($encrypted); $salt = mb_substr($decoded, 0, 32, '8bit'); [$encryptKey, $hmacKey] = $this->splitKeys($key, $salt); // ... decryption logic here ... return $plaintext;}// ... other method here ...}

Unfortunately, anyone who ever does something like this just violated one of the core assumptions of the HKDF security definition and no longer gets to claim “KDF security” for their construction. Instead, your protocol merely gets to claim “PRF security”.

Art: Harubaki

KDF? PRF? OMGWTFBBQ?

Let’s take a step back and look at some basic concepts.

(If you want a more formal treatment, read this Stack Exchange answer.)

PRF: Pseudo-Random Functions

A pseudorandom function (PRF) is an efficient function that emulates a random oracle.

“What the hell’s a random oracle?” you ask? Well, Thomas Pornin has the best explanation for random oracles:

A random oracle is described by the following model:

• There is a black box. In the box lives a gnome, with a big book and some dice.
• We can input some data into the box (an arbitrary sequence of bits).
• Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
• If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message m. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really “random” oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Thomas Pornin

Alternatively, Wikipedia has a more formal definition available to the academic-inclined.

In practical terms, we can generate a strong PRF out of secure cryptographic hash functions by using a keyed construction; i.e. HMAC.

Thus, as long as your HMAC key is a secret, the output of HMAC can be generally treated as a PRF for all practical purposes. Your main security consideration (besides key management) is the collision risk if you truncate its output.

Art: LvJ

KDF: Key Derivation Functions

A key derivation function (KDF) is exactly what it says on the label: a cryptographic algorithm that derives one or more cryptographic keys from a secret input (which may be another cryptography key, a group element from a Diffie-Hellman key exchange, or a human-memorable password).

Note that passwords should be used with a Password-Based Key Derivation Function, such as scrypt or Argon2id, not HKDF.

Despite what you may read online, KDFs do not need to be built upon cryptographic hash functions, specifically; but in practice, they often are.

A notable counter-example to this hash function assumption: CMAC in Counter Mode (from NIST SP 800-108) uses AES-CMAC, which is a variable-length input variant of CBC-MAC. CBC-MAC uses a block cipher, not a hash function.

Regardless of the construction, KDFs use a PRF under the hood, and the output of a KDF is supposed to be a uniformly random bit string.

Art: LvJ

PRF vs KDF Security Definitions

The security definition for a KDF has more relaxed requirements than PRFs: PRFs require the secret key be uniformly random. KDFs do not have this requirement.

If you use a KDF with a non-uniformly random IKM, you probably need the KDF security definition.

If your IKM is already uniformly random (i.e. the “key separation” use case), you can get by with just a PRF security definition.

After all, the entire point of KDFs is to allow a congruent security level as you’d get from uniformly random secret keys, without also requiring them.

However, if you’re building a protocol with a security requirement satisfied by a KDF, but you actually implemented a PRF (i.e., not a KDF), this is a security vulnerability in your cryptographic design.

Art: LvJ

The HKDF Algorithm

HKDF is an HMAC-based KDF. Its algorithm consists of two distinct steps:

1. HKDF-Extract uses the Initial Keying Material (IKM) and Salt to produce a Pseudo-Random Key (PRK).
2. HKDF-Expand actually derives the keys using PRK, the info parameter, and a counter (from 0 to 255) for each hash function output needed to generate the desired output length.

If you’d like to see an implementation of this algorithm, defuse/php-encryption provides one (since it didn’t land in PHP until 7.1.0). Alternatively, there’s a Python implementation on Wikipedia that uses HMAC-SHA256.

This detail about the two steps will matter a lot in just a moment.

Art: Swizz

How HKDF Salts Are Misused

The HKDF paper, written by Hugo Krawczyk, contains the following definition (page 7).

The paper goes on to discuss the requirements for authenticating the salt over the communication channel, lest the attacker have the ability to influence it.

A subtle detail of this definition is that the security definition says that A salt value , not Multiple salt values.

Which means: You’re not supposed to use HKDF with a constant IKM, info label, etc. but vary the salt for multiple invocations. The salt must either be a fixed random value, or NULL.

The HKDF RFC makes this distinction even less clear when it argues for random salts.

We stress, however, that the use of salt adds significantly to the strength of HKDF, ensuring independence between different uses of the hash function, supporting “source-independent” extraction, and strengthening the analytical results that back the HKDF design.

Random salt differs fundamentally from the initial keying material in two ways: it is non-secret and can be re-used. As such, salt values are available to many applications. For example, a pseudorandom number generator (PRNG) that continuously produces outputs by applying HKDF to renewable pools of entropy (e.g., sampled system events) can fix a salt value and use it for multiple applications of HKDF without having to protect the secrecy of the salt. In a different application domain, a key agreement protocol deriving cryptographic keys from a Diffie-Hellman exchange can derive a salt value from public nonces exchanged and authenticated between communicating parties as part of the key agreement (this is the approach taken in [IKEv2]).

RFC 5869, section 3.1

Okay, sure. Random salts are better than a NULL salt. And while this section alludes to “[fixing] a salt value” to “use it for multiple applications of HKDF without having to protect the secrecy of the salt”, it never explicitly states this requirement. Thus, the poor implementor is left to figure this out on their own.

Thus, because it’s not using HKDF in accordance with its security definition, many implementations (such as the PHP encryption library we’ve been studying) do not get to claim that their construction has KDF security.

Instead, they only get to claim “Strong PRF” security, which you can get from just using HMAC.

Art: LvJ

What Purpose Do HKDF Salts Actually Serve?

Recall that the HKDF algorithm uses salts in the HDKF-Extract step. Salts in this context were intended for deriving keys from a Diffie-Hellman output, or a human-memorable password.

In the case of [Elliptic Curve] Diffie-Hellman outputs, the result of the key exchange algorithm is a random group element, but not necessarily uniformly random bit string. There’s some structure to the output of these functions. This is why you always, at minimum, apply a cryptographic hash function to the output of [EC]DH before using it as a symmetric key.

HKDF uses salts as a mechanism to improve the quality of randomness when working with group elements and passwords.

Extending the nonce for a symmetric-key AEAD mode is a good idea, but using HKDF’s salt parameter specifically to accomplish this is a misuse of its intended function, and produces a weaker argument for your protocol’s security than would otherwise be possible.

How Should You Introduce Randomness into HKDF?

Just shove it in the info parameter.

Art: LvJ

It may seem weird, and defy intuition, but the correct way to introduce randomness into HKDF as most developers interact with the algorithm is to skip the salt parameter entirely (either fixing it to a specific value for domain-separation or leaving it NULL), and instead concatenate data into the info parameter.

class BetterEncryptor extends MyEncryptor {protected function splitKeys(CryptographyKey $key, string $salt): array { $encryptKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'encryption', '' // intentionally empty )); $authKey = new CryptographyKey(hash_hkdf( 'sha256', $key->getRawBytes(), 32, $salt . 'message authentication', '' // intentionally empty )); return [$encryptKey, $authKey];}}

Of course, you still have to watch out for canonicalization attacks if you’re feeding multi-part messages into the info tag.

Another advantage: This also lets you optimize your HKDF calls by caching the PRK from the HKDF-Extract step and reuse it for multiple invocations of HKDF-Expand with a distinct info. This allows you to reduce the number of hash function invocations from to (since each HMAC involves two hash function invocations).

Notably, this HKDF salt usage was one of the things that was changed in V3/V4 of PASETO.

Does This Distinction Really Matter?

If it matters, your cryptographer will tell you it matters–which probably means they have a security proof that assumes the KDF security definition for a very good reason, and you’re not allowed to violate that assumption.

Otherwise, probably not. Strong PRF security is still pretty damn good for most threat models.

Art: LvJ

Closing Thoughts

If your takeaway was, “Wow, I feel stupid,” don’t, because you’re in good company.

I’ve encountered several designs in my professional life that shoved the randomness into the info parameter, and it perplexed me because there was a perfectly good salt parameter right there. It turned out, I was wrong to believe that, for all of the subtle and previously poorly documented reasons discussed above. But now we both know, and we’re all better off for it.

So don’t feel dumb for not knowing. I didn’t either, until this was pointed out to me by a very patient colleague.

“Feeling like you were stupid” just means you learned.
(Art: LvJ)

Also, someone should really get NIST to be consistent about whether you should use HKDF or “KDF in Counter Mode with HMAC” as a PRF, because SP 800-108’s new revision doesn’t concede this point at all (presumably a relic from the 2009 draft).

This concession was made separately in 2011 with SP 800-56C revision 1 (presumably in response to criticism from the 2010 HKDF paper), and the present inconsistency is somewhat vexing.

(On that note, does anyone actually use the NIST 800-108 KDFs instead of HKDF? If so, why? Please don’t say you need CMAC…)

Bonus Content

These questions were asked after this blog post initially went public, and I thought they were worth adding. If you ask a good question, it may end up being edited in at the end, too.

Art: LvJ

Why Does HKDF use the Salt as the HMAC key in the Extract Step? (via r/crypto)

Broadly speaking, when applying a PRF to two “keys”, you get to decide which one you treat as the “key” in the underlying API.

HMAC’s API is HMACalg(key, message), but how HKDF uses it might as well be HMACalg(key1, key2).

The difference here seems almost arbitrary, but there’s a catch.

HKDF was designed for Diffie-Hellman outputs (before ECDH was the norm), which are generally able to be much larger than the block size of the underlying hash function. 2048-bit DH results fit in 256 bytes, which is 4 times the SHA256 block size.

If you have to make a decision, using the longer input (DH output) as the message is more intuitive for analysis than using it as the key, due to pre-hashing. I’ve discussed the counter-intuitive nature of HMAC’s pre-hashing behavior at length in this post, if you’re interested.

So with ECDH, it literally doesn’t matter which one was used (unless you have a weird mismatch in hash functions and ECC groups; i.e. NIST P-521 with SHA-224).

But before the era of ECDH, it was important to use the salt as the HMAC key in the extract step, since they were necessarily smaller than a DH group element.

Thus, HKDF chose HMACalg(salt, IKM) instead of HMACalg(IKM, salt) for the calculation of PRK in the HKDF-Extract step.

Neil Madden also adds that the reverse would create a chicken-egg situation, but I personally suspect that the pre-hashing would be more harmful to the security analysis than merely supplying a non-uniformly random bit string as an HMAC key in this specific context.

My reason for believing this is, when a salt isn’t supplied, it defaults to a string of 0x00 bytes as long as the output size of the underlying hash function. If the uniform randomness of the salt mattered that much, this wouldn’t be a tolerable condition.

https://soatok.blog/2021/11/17/understanding-hkdf/

#cryptographicHashFunction #cryptography #hashFunction #HMAC #KDF #keyDerivationFunction #securityDefinition #SecurityGuidance

Dhole Moments

2020-12-24 06:16:58

As we look upon the sunset of a remarkably tiresome year, I thought it would be appropriate to talk about cryptographic wear-out.

What is cryptographic wear-out?

It’s the threshold when you’ve used the same key to encrypt so much data that you should probably switch to a new key before you encrypt any more. Otherwise, you might let someone capable of observing all your encrypted data perform interesting attacks that compromise the security of the data you’ve encrypted.

My definitions always aim to be more understandable than pedantically correct.
(Art by Swizz)

The exact value of the threshold varies depending on how exactly you’re encrypting data (n.b. AEAD modes, block ciphers + cipher modes, etc. each have different wear-out thresholds due to their composition).

Let’s take a look at the wear-out limits of the more popular symmetric encryption methods, and calculate those limits ourselves.

Specific Ciphers and Modes

(Art by Khia. Poorly edited by the author.)

Cryptographic Limits for AES-GCM

I’ve written about AES-GCM before (and why I think it sucks).

AES-GCM is a construction that combines AES-CTR with an authenticator called GMAC, whose consumption of nonces looks something like this:

• Calculating H (used in GHASH for all messages encrypted under the same key, regardless of nonce):
  
  • Encrypt(00000000 00000000 00000000 00000000)

  
  

• Calculating J0 (the pre-counter block):
  
  • If the nonce is 96 bits long:
    
    • NNNNNNNN NNNNNNNN NNNNNNNN 00000001 where the N spaces represent the nonce hexits.

    
    

  • Otherwise:
    
    • s = 128 * ceil(len(nonce)/nonce) - len(nonce)
    • J0 = GHASH(H, nonce || zero(s+64) || int2bytes(len(nonce))

    
    

  
  

• Each block of data encrypted uses J0 + block counter (starting at 1) as a CTR nonce.
• J0 is additionally used as the nonce to calculate the final GMAC tag.

AES-GCM is one of the algorithms where it’s easy to separately calculate the safety limits per message (i.e. for a given nonce and key), as well as for all messages under a key.

AES-GCM Single Message Length Limits

In the simplest case (nonce is 96 bits), you end up with the following nonces consumed:

• For each key: 00000000 00000000 00000000 00000000
• For each (nonce, key) pair:
  
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000001 for J0
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000002 for encrypting the first 16 bytes of plaintext
  • NNNNNNNN NNNNNNNN NNNNNNNN 000000003 for the next 16 bytes of plaintext…
  • …
  • NNNNNNNN NNNNNNNN NNNNNNNN FFFFFFFFF for the final 16 bytes of plaintext.

  
  

From here, it’s pretty easy to see that you can encrypt the blocks from 00000002 to FFFFFFFF without overflowing and creating a nonce reuse. This means that each (key, nonce) can be used to encrypt a single message up to blocks of the underlying ciphertext.

Since the block size of AES is 16 bytes, this means the maximum length of a single AES-GCM (key, nonce) pair is bytes (or 68,719,476,480 bytes). This is approximately 68 GB or 64 GiB.

Things get a bit tricker to analyze when the nonce is not 96 bits, since it’s hashed.

The disadvantage of this hashing behavior is that it’s possible for two different nonces to produce overlapping ranges of AES-CTR output, which makes the security analysis very difficult.

However, this hashed output is also hidden from network observers since they do not know the value of H. Without some method of reliably detecting when you have an overlapping range of hidden block counters, you can’t exploit this.

(If you want to live dangerously and motivate cryptanalysis research, mix 96-bit and non-96-bit nonces with the same key in a system that does something valuable.)

Multi-Message AES-GCM Key Wear-Out

Now that we’ve established the maximum length for a single message, how many messages you can safely encrypt under a given AES-GCM key depends entirely on how your nonce is selected.

If you have a reliable counter, which is guaranteed to never repeat, and start it at 0 you can theoretically encrypt messages safely. Hooray!

Hooray!
(Art by Swizz)

You probably don’t have a reliable counter, especially in real-world settings (distributed systems, multi-threaded applications, virtual machines that might be snapshotted and restored, etc.).

Confound you, technical limitations!
(Art by Swizz)

Additionally (thanks to 2adic for the expedient correction), you cannot safely encrypt more than blocks with AES because the keystream blocks–as the output of a block cipher–cannot repeat.

Most systems that cannot guarantee unique incrementing nonces simply generate nonces with a cryptographically secure random number generator. This is a good idea, but no matter how high quality your random number generator is, random functions will produce collisions with a discrete probability.

If you have possible values, you should expect a single collision(with 50% probability) after (or )samples. This is called the birthday bound.

However, 50% of a nonce reuse isn’t exactly a comfortable safety threshold for most systems (especially since nonce reuse will cause AES-GCM to become vulnerable to active attackers). 1 in 4 billion is a much more comfortable safety margin against nonce reuse via collisions than 1 in 2. Fortunately, you can calculate the discrete probability of a birthday collision pretty easily.

If you want to rekey after your collision probability exceeds (for a random nonce between 0 and ), you simply need to re-key after messages.

AES-GCM Safety Limits

• Maximum message length: bytes
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

Not bad, but we can do better.
(Art by Khia.)

Cryptographic Limits for ChaCha20-Poly1305

The IETF version of ChaCha20-Poly1305 uses 96-bit nonces and 32-bit internal counters. A similar analysis follows from AES-GCM’s, with a few notable exceptions.

For starters, the one-time Poly1305 key is derived from the first 32 bytes of the ChaCha20 keystream output (block 0) for a given (nonce, key) pair. There is no equivalent to AES-GCM’s H parameter which is static for each key. (The ChaCha20 encryption begins using block 1.)

Additionally, each block for ChaCha20 is 512 bits, unlike AES’s 128 bits. So the message limit here is a little more forgiving.

Since the block size is 512 bits (or 64 bytes), and only one block is consumed for Poly1305 key derivation, we can calculate a message length limit of , or 274,877,906,880 bytes–nearly 256 GiB for each (nonce, key) pair.

The same rules for handling 96-bit nonces applies as with AES-GCM, so we can carry that value forward.

ChaCha20-Poly1305 Safety Limits

• Maximum message length: bytes
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

A significant improvement, but still practically limited.
(Art by Khia.)

Cryptographic Limits for XChaCha20-Poly1305

XChaCha20-Poly1305 is a variant of XSalsa20-Poly1305 (as used in libsodium) and the IETF’s ChaCha20-Poly1305 construction. It features 192-bit nonces and 32-bit internal counters.

XChaCha20-Poly1305 is instantiated by using HChaCha20 of the key over the first 128 bits of the nonce to produce a subkey, which is used with the remaining nonce bits using the aforementioned ChaCha20-Poly1305.

This doesn’t change the maximum message length, but it does change the number of messages you can safely encrypt (since you’re actually using up to distinct keys).

Thus, even if you manage to repeat the final ChaCha20-Poly1305 nonce, as long as the total nonce differs, each encryptions will be performed with a distinct key (thanks to the HChaCha20 key derivation; see the XSalsa20 paper and IETF RFC draft for details).

UPDATE (2021-04-15): It turns out, my read of the libsodium implementation was erroneous due to endian-ness. The maximum message length for XChaCha20-Poly1305 is blocks, and for AEAD_XChaCha20_Poly1305 is blocks. Each block is 64 bytes, so that changes the maximum message length to about . This doesn’t change the extended-nonce details, just the underlying ChaCha usage.

XChaCha20-Poly1305 Safety Limits

• Maximum message length: bytes (earlier version of this document said )
• Maximum number of messages (random nonce):
• Maximum number of messages (sequential nonce): (but you probably don’t have this luxury in the real world)
• Maximum data safely encrypted under a single key with a random nonce: about bytes

I can see encrypt forever, man.
(Art by Khia.)

Cryptographic Limits for AES-CBC

It’s tempting to compare non-AEAD constructions and block cipher modes such as CBC (Cipher Block Chaining), but they’re totally different monsters.

• AEAD ciphers have a clean delineation between message length limit and the message quantity limit
• CBC and other cipher modes do not have this separation

Every time you encrypt a block with AES-CBC, you are depleting from a universal bucket that affects the birthday bound security of encrypting more messages under that key. (And unlike AES-GCM with long nonces, AES-CBC’s IV is public.)

This is in addition to the operational requirements of AES-CBC (plaintext padding, initialization vectors that never repeat and must be unpredictable, separate message authentication since CBC doesn’t provide integrity and is vulnerable to chosen-ciphertext atacks, etc.).

My canned response to most queries about AES-CBC.
(Art by Khia.)

For this reason, most cryptographers don’t even bother calculating the safety limit for AES-CBC in the same breath as discussing AES-GCM. And they’re right to do so!

If you find yourself using AES-CBC (or AES-CTR, for that matter), you’d best be performing a separate HMAC-SHA256 over the ciphertext (and verifying this HMAC with a secure comparison function before decrypting). Additionally, you should consider using an extended nonce construction to split one-time encryption and authentication keys.

(Art by Riley.)

However, for the sake of completeness, let’s figure out what our practical limits are.

CBC operates on entire blocks of plaintext, whether you need the entire block or not.

On encryption, the output of the previous block is mixed (using XOR) with the current block, then encrypted with the block cipher. For the first block, the IV is used in the place of a “previous” block. (Hence, its requirements to be non-repeating and unpredictable.)

This means you can informally model (IV xor PlaintextBlock) and (PBn xor PBn+1) as a pseudo-random function, before it’s encrypted with the block cipher.

If those words don’t mean anything to you, here’s the kicker: You can use the above discussion about birthday bounds to calculate the upper safety bounds for the total number of blocks encrypted under a single AES key (assuming IVs are generated from a secure random source).

If you’re okay with a 50% probability of a collision, you should re-key after blocks have been encrypted.

https://www.youtube.com/watch?v=v0IsYNDMV7A

If your safety margin is closer to the 1 in 4 billion (as with AES-GCM), you want to rekey after blocks.

However, blocks encrypted doesn’t map neatly to bytes encrypted.

If your plaintext is always an even multiple of 128 bits (or 16 bytes), this allows for up to bytes of plaintext. If you’re using PKCS#7 padding, keep in mind that this will include an entire padding block per message, so your safety margin will deplete a bit faster (depending on how many individual messages you encrypt, and therefore how many padding blocks you need).

On the other extreme (1-byte plaintexts), you’ll only be able to eek encrypted bytes before you should re-key.

Therefore, to stay within the safety margin of AES-CBC, you SHOULD re-key after blocks (including padding) have been encrypted.

Keep in mind: single-byte blocks is still approximately 281 TiB of data (including padding). On the upper end, 15-byte blocks (with 1-byte padding to stay within a block) clocks in at about or about 4.22 PiB of data.

That’s Blocks. What About Bytes?

The actual plaintext byte limit sans padding is a bit fuzzy and context-dependent.

The local extrema occurs if your plaintext is always 16 bytes (and thus requires an extra 16 bytes of padding). Any less, and the padding fits within one block. Any more, and the data😛adding ratio starts to dominate.

Therefore, the worst case scenario with padding is that you take the above safety limit for block counts, and cut it in half. Cutting a number in half means reducing the exponent by 1.

But this still doesn’t eliminate the variance. blocks could be anywhere from to bytes of real plaintext. When in situations like this, we have to assume the worst (n.b. take the most conservative value).

Therefore…

AES-CBC Safety Limits

• Maximum data safely encrypted under a single key with a random nonce: bytes (approximately 141 TiB)

Yet another reason to dislike non-AEAD ciphers.
(Art by Khia.)

Take-Away

Compared to AES-CBC, AES-GCM gives you approximately a million times as much usage out of the same key, for the same threat profile.

ChaCha20-Poly1305 and XChaCha20-Poly1305 provides even greater allowances of encrypting data under the same key. The latter is even safe to use to encrypt arbitrarily large volumes of data under a single key without having to worry about ever practically hitting the birthday bound.

I’m aware that this blog post could have simply been a comparison table and a few footnotes (or even an IETF RFC draft), but I thought it would be more fun to explain how these values are derived from the cipher constructions.

(Art by Khia.)

https://soatok.blog/2020/12/24/cryptographic-wear-out-for-symmetric-encryption/

#AES #AESCBC #AESGCM #birthdayAttack #birthdayBound #cryptography #safetyMargin #SecurityGuidance #symmetricCryptography #symmetricEncryption #wearOut

Imagine you’re a software developer, and you need to authenticate users based on a username and password.

If you’re well-read on the industry standard best practices, you’ll probably elect to use something like bcrypt, scrypt, Argon2id, or PBKDF2. (If you thought to use something else, you’re almost certainly doing it wrong.)

Let’s say, due to technical constraints, that you’re forced to select PBKDF2 out of the above options, but you’re able to use a suitable hash function (i.e. SHA-256 or SHA-512, instead of SHA-1).

Every password is hashed with a unique 256-bit salt, generated from a secure random generator, and has an iteration count in excess of 80,000 (for SHA-512) or 100,000 (for SHA-256). So far, so good.

(Art by Khia.)

Let’s also say your users’ passwords are long, randomly-generated strings. This can mean either you’re building a community of password manager aficionados, or your users are actually software bots with API keys.

Every user’s password is, therefore, always a 256 character string of random hexadecimal characters.

Two sprints before your big launch, your boss calls you and says, “Due to arcane legal compliance reasons, we need to be able to detect duplicate passwords. It needs to be fast.”

You might might think, “That sounds like a hard problem to solve.”

Your boss insists, “The passwords are all too long and too high-entropy to reliably attacked, even when we’re using a fast hash, so we should be able to get by with a simple hash function for deduplication purposes.”

So you change your code to look like this:

<?phpuse ParagonIE\EasyDB\EasyDB;use MyApp\Security\PasswordHash;class Authentication { private EasyDB $db; public function __construct(EasyDB $db) { $this->db = $db; $this->pwhash = new PasswordHash('sha256'); } public function signUp(string $username, string $password) { // New: $hashed = hash('sha256', $password); if ($db->exists( "SELECT count(id) FROM users WHERE pw_dedupe = ?", $hashed )) { throw new Exception( "You cannot use the same username or password as another user." ); } // Original: if ($db->exists( "SELECT count(id) FROM users WHERE username = ?", $username )) { throw new Exception( "You cannot use the same username or password as another user." ); } $this->db->insert('users', [ 'username' => $username, 'pwhash' => $this->pwhash->hash($password), // Also new: 'pw_dedupe' => $hashed ]); } public function logIn(string $username, string $password): int { // This is unchanged: $user = $this->db->row("SELECT * FROM users WHERE username = ?", $username); if (empty($user)) { throw new Exception("Security Error: No user"); } if ($this->pwhash->verify($password, $user['pwhash'])) { throw new Exception("Security Error: Incorrect password"); } return (int) $user['id']; }}

Surely, this won’t completely undermine the security of the password hashing algorithm?

Is this a face that would mislead you? (Art by Khia.)

Three years later, a bored hacker discovers a read-only SQL injection vulnerability, and is immediately able to impersonate any user in your application.

What could have possibly gone wrong?

Cryptography Bugs Are Subtle

https://twitter.com/SwiftOnSecurity/status/832058185049579524

In order to understand what went wrong in our hypothetical scenario, you have to kinda know what’s under the hood in the monstrosity that our hypothetical developer slapped together.

PBKDF2

PBKDF2 stands for Password-Based Key Derivation Function #2. If you’re wondering where PBKDF1 went, I discussed its vulnerability in another blog post about the fun we can have with hash functions.