#asymmetriccryptography — Public Fediverse posts

@rmondello : what makes passkeys strong:

1. Software checks the domain name, which makes phishing hard;

2. Https is enforced, which helps prevent AitM attacks (unless Cloudflare et al. come into play);

3. A unique, long, unguessible, randomly generated "password" (public key) per account: dumb password rules and broken human RNG's no longer apply.

The rest is marketing (including the -hyped- asymmetric cryptography).

The "advantage" of denying the owner access to their own private keys hardly makes sense as long as session cookies are not device-bound.

The disadvantage of not being able to back up ones own private keys is the risk of vendor lock-in and the underestimated huge risk of account lockout [1]. And the latter leads to the necessity of being able to log in using weak authentication after the user loses access to their private keys.

@brandonbutler

[1] https://seclists.org/fulldisclosure/2024/Feb/15

#Passkeys #Phishing #PhishingResistant #AsymmetricCryptography #AndroidPasskeys #androidPasskeysGone #iOSpasskeys #iPadOSpasskeys #ApplePasskeys #BackUp #Export #BackUpPasskeys #ExportPassKeys #PasskeyBackUps #PasskeyExports

@rmondello : what makes passkeys strong:

1. Software checks the domain name, which makes phishing hard;

2. Https is enforced, which helps prevent AitM attacks (unless Cloudflare et al. come into play);

3. A unique, long, unguessible, randomly generated "password" (public key) per account: dumb password rules and broken human RNG's no longer apply.

The rest is marketing (including the -hyped- asymmetric cryptography).

The "advantage" of denying the owner access to their own private keys hardly makes sense as long as session cookies are not device-bound.

The disadvantage of not being able to back up ones own private keys is the risk of vendor lock-in and the underestimated huge risk of account lockout [1]. And the latter leads to the necessity of being able to log in using weak authentication after the user loses access to their private keys.

@brandonbutler

[1] https://seclists.org/fulldisclosure/2024/Feb/15

#Passkeys #Phishing #PhishingResistant #AsymmetricCryptography #AndroidPasskeys #androidPasskeysGone #iOSpasskeys #iPadOSpasskeys #ApplePasskeys #BackUp #Export #BackUpPasskeys #ExportPassKeys #PasskeyBackUps #PasskeyExports

@rmondello : what makes passkeys strong:

1. Software checks the domain name, which makes phishing hard;

2. Https is enforced, which helps prevent AitM attacks (unless Cloudflare et al. come into play);

3. A unique, long, unguessible, randomly generated "password" (public key) per account: dumb password rules and broken human RNG's no longer apply.

The rest is marketing (including the -hyped- asymmetric cryptography).

The "advantage" of denying the owner access to their own private keys hardly makes sense as long as session cookies are not device-bound.

The disadvantage of not being able to back up ones own private keys is the risk of vendor lock-in and the underestimated huge risk of account lockout [1]. And the latter leads to the necessity of being able to log in using weak authentication after the user loses access to their private keys.

@brandonbutler

[1] https://seclists.org/fulldisclosure/2024/Feb/15

#Passkeys #Phishing #PhishingResistant #AsymmetricCryptography #AndroidPasskeys #androidPasskeysGone #iOSpasskeys #iPadOSpasskeys #ApplePasskeys #BackUp #Export #BackUpPasskeys #ExportPassKeys #PasskeyBackUps #PasskeyExports

@rmondello : what makes passkeys strong:

1. Software checks the domain name, which makes phishing hard;

2. Https is enforced, which helps prevent AitM attacks (unless Cloudflare et al. come into play);

3. A unique, long, unguessible, randomly generated "password" (public key) per account: dumb password rules and broken human RNG's no longer apply.

The rest is marketing (including the -hyped- asymmetric cryptography).

The "advantage" of denying the owner access to their own private keys hardly makes sense as long as session cookies are not device-bound.

The disadvantage of not being able to back up ones own private keys is the risk of vendor lock-in and the underestimated huge risk of account lockout [1]. And the latter leads to the necessity of being able to log in using weak authentication after the user loses access to their private keys.

@brandonbutler

[1] https://seclists.org/fulldisclosure/2024/Feb/15

#Passkeys #Phishing #PhishingResistant #AsymmetricCryptography #AndroidPasskeys #androidPasskeysGone #iOSpasskeys #iPadOSpasskeys #ApplePasskeys #BackUp #Export #BackUpPasskeys #ExportPassKeys #PasskeyBackUps #PasskeyExports

Don’t Use Session (Signal Fork)

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

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

Don’t use Session.

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

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

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

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

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

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

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

Security Issues

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

Insufficient Entropy in Ed25519 Keys

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

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

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

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

Does This Matter?

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

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

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

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

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

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

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

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

What does 64 bits of ECDLP Security actually mean?

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

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

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

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

— from the Shattered paper, page 2.

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

How would you exploit this in practice?

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

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

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

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

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

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

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

In-Band Negotiation for Message Signatures

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

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

What this code is doing (after decryption):

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

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

Using Public Keys As AES-GCM Keys

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

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

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

Session also does this inside of encryptHop().

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

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

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

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

I wonder if this impacts their onion routing assumptions?

Why should I trust session?

(…)

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

Session FAQs

Gripes

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

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

Mnemonic Decoding Isn’t Constant-Time

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

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

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

Unsafe Use of SecureRandom on Android

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

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

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

And again here.

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

Why would anyone care about this?

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

Closing Thoughts

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

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

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

That’s hilarious.

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

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

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

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

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

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

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

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

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

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

Building Intuition for KEMs

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

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

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

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

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

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

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

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

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

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

Unfortunately

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

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

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

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

From Textbook RSA to Real World RSA

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

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

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

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

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

That’s obviously not very good!

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

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

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

This Padding Stinks; Can We Dispense Of It?

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

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

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

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

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

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

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

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

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

Cool, we’re almost there.

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

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

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

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

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

What Are You Feeding That Thing?

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

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

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

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

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

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

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

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

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

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

Some questions may come to mind:

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

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

Closing Thoughts

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

I hope that others find this useful.

Header art by Harubaki and AJ.

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

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

If you’re ever tasked with implementing a cryptography feature–whether a high-level protocol or a low-level primitive–you will have to take special care to ensure you’re not leaking secret information through side-channels.

The descriptions of algorithms you learn in a classroom or textbook are not sufficient for real-world use. (Yes, that means your toy RSA implementation based on GMP from your computer science 101 class isn’t production-ready. Don’t deploy it.)

But what are these elusive side-channels exactly, and how do you prevent them? And in cases where you cannot prevent them, how can you mitigate the risk to your users?

Contents

• Cryptographic Side-Channels
  • Timing Leaks
  • Power Usage
  • Electromagnetic Emissions
• Side-Channel Prevention and Mitigation
  • Prevention vs. Mitigation
  • What is Constant-Time?
  • Malicious Environments and Algorithmic Constant-Time
  • Mitigation with Blinding Techniques
• Design Patterns for Algorithmic Constant-Time Code
  • Constant-Time String Comparison
  • Alternative: “Double HMAC” String Comparison
  • Constant-Time Conditional Select
  • Constant-Time String Inequality Comparison
  • Constant-Time Integer Multiplication
  • Constant-Time Integer Division
  • Constant-Time Modular Inversion
  • Constant-Time Null-Byte Trimming
• Further Reading and Online Resources
• Errata

Cryptographic Side-Channels

The concept of a side-channel isn’t inherently cryptographic, as Taylor Hornby demonstrates, but a side-channel can be a game over vulnerability in a system meant to maintain confidentiality (even if only for its cryptography keys).

Cryptographic side-channels allow an attacker to learn secret data from your cryptography system. To accomplish this, the attacker doesn’t necessarily study the system’s output (i.e. ciphertext); instead, they observe some other measurement, such as how much time or power was spent performing an operation, or what kind of electromagnetic radiation was emitted.

Important: While being resistant to side-channels is a prerequisite for implementations to be secure, it isn’t in and of itself sufficient for security. The underlying design of the primitives, constructions, and high-level protocols needs to be secure first, and that requires a clear and specific threat model for what you’re building.

Constant-time ECDSA doesn’t help you if you reuse k-values like it’s going out of style, but variable-time ECDSA still leaks your secret key to anyone who cares to probe your response times. Secure cryptography is very demanding.

Timing Leaks

Timing side-channels leak secrets through how much time it takes for an operation to complete.

There are many different flavors of timing leakage, including:

• Fast-failing comparison functions (memcmp() in C)
• Cache-timing vulnerabilities (e.g. software AES)
• Memory access patterns
• Conditional branches controlled by secrets

The bad news about timing leaks is that they’re almost always visible to an attacker over the network (including over the Internet (PDF)).

The good news is that most of them can be prevented or mitigated in software.

Power Usage

Different algorithms or processor operations may require different amounts of power.

For example, squaring a large number may take less power than multiplying two different large numbers. This observation has led to the development of power analysis attacks against RSA.

Power analysis is especially relevant for embedded systems and smart cards, which are easier to extract a meaningful signal from than your desktop computer.

Some information leakage through power usage can be prevented through careful engineering (for example: BearSSL, which uses Montgomery multiplication instead of square-and-multiply).

But that’s not always an option, so generally these risks are mitigated.

Electromagnetic Emissions

Your computer is a reliable source of electromagnetic emissions (such as radio waves). Some of these emissions may reveal information about your cryptographic secrets, especially to an attacker with physical proximity to your device.

The good news is that research into EM emission side-channels isn’t as mature as side-channels through timing leaks or power usage. The bad news is that mitigations for breakthroughs will generally require hardware (e.g. electromagnetic shielding).

Side-Channel Prevention and Mitigation

Now that we’ve established a rough sense of some of the types of side-channels that are possible, we can begin to identify what causes them and aspire to prevent the leaks from happening–and where we can’t, to mitigate the risk to a reasonable level.

Note: To be clear, I didn’t cover all of the types of side-channels.

Prevention vs. Mitigation

Preventing a side-channel means eliminating the conditions that allow the information leak to occur in the first place. For timing leaks, this means making all algorithms constant-time.

There are entire classes of side-channel leaks that aren’t possible or practical to mitigate in software. When you encounter one, the best you can hope to do is mitigate the risk.

Ideally, you want to make the attack more expensive to pull off than the reward an attacker will gain from it.

What is Constant-Time?

When an implementation is said to be constant-time, what we mean is that the execution time of the code is not a function of its secret inputs.

Vulnerable AES uses table look-ups to implement the S-Box. Constant-time AES is either implemented in hardware, or is bitsliced.

Malicious Environments and Algorithmic Constant-Time

One of the greatest challenges with writing constant-time code is distinguishing between algorithmic constant-time and provably constant-time. The main difference between the two is that you cannot trust your compiler (especially a JIT compiler), which may attempt to optimize your code in a way that reintroduces the side-channel you aspired to remove.

A sufficiently advanced compiler optimization is indistinguishable from an adversary.

John Regehr, possibly with apologies to Arthur C. Clarke

For compiled languages, this is a tractable but expensive problem to solve: You simply have to formally verify everything from the source code to the compiler to the silicon chips that the code will be deployed on, and then audit your supply chain to prevent malicious tampering from going undetected.

For interpreted languages (e.g. PHP and JavaScript), this formal verification strategy isn’t really an option, unless you want to formally verify the runtime that interprets scripts and prove that the operations remain constant-time on top of all the other layers of distrust.

Is this level of paranoia really worth the effort?

For that reason, we’re going to assume that algorithmic constant-time is adequate for the duration of this blog post.

If your threat model prevents you from accepting this assumption, feel free to put in the extra effort yourself and tell me how it goes. After all, as a furry who writes blog posts in my spare time for fun, I don’t exactly have the budget for massive research projects in formal verification.

Mitigation with Blinding Techniques

The best mitigation for some side-channels is called blinding: Obfuscating the inputs with some random data, then deobfuscating the outputs with the same random data, such that your keys are not revealed.

Two well-known examples include RSA decryption and Elliptic Curve Diffie-Hellman. I’ll focus on the latter, since it’s not as widely covered in the literature (although several cryptographers I’ve talked with were somehow knowledgeable about it; I suspect gatekeeping is involved).

Blinded ECDH Key Exchange

In typical ECDH implementations, you will convert a point on a Weierstrass curve to a Jacobian coordinate system .

The exact conversion formula is (, ). The conversion almost makes intuitive sense.

Where does come from though?

It turns out, the choice for is totally arbitrary. Libraries typically set it equal to 1 (for best performance), but you can also set it to a random number. (You cannot set it to 0, however, for obvious reasons.)

Choosing a random number means the calculations performed over Jacobian coordinates will be obscured by a randomly chosen factor (and thus, if is only used once per scalar multiplication, the bitwise signal the attackers rely on will be lost).

I think it’s really cool how one small tweak to the runtime of an algorithm can make it significantly harder to attack.

Design Patterns for Algorithmic Constant-Time Code

Mitigation techniques are cool, but preventing side-channels is a better value-add for most software.

To that end, let’s look at some design patterns for constant-time software. Some of these are relatively common; others, not so much.

If you prefer TypeScript / JavaScirpt, check out Soatok’s constant-time-js library on Github / NPM.

Constant-Time String Comparison

Rather than using string comparison (== in most programming languages, memcmp() in C), you want to compare cryptographic secrets and/or calculated integrity checks with a secure compare algorithm, which looks like this:

1. Initialize a variable (let’s call it D) to zero.
2. For each byte of the two strings:
   1. Calculate (lefti XOR righti)
   2. Bitwise OR the current value of D with the result of the XOR, store the output in D
3. When the loop has concluded, D will be equal to 0 if and only if the two strings are equal.

In code form, it looks like this:

<?phpfunction ct_compare(string $left, string $right): bool{    $d = 0;    $length = mb_strlen($left, '8bit');    if (mb_strlen($right, '8bit') !== $length) {        return false; // Lengths differ    }    for ($i = 0; $i < $length; ++$i) {        $leftCharCode = unpack('C', $left[$i])[1];        $rightCharCode = unpack('C', $right[$i])[1];        $d |= ($leftCharCode ^ $rightCharCode);    }    return $d === 0;}

In this example, I’m using PHP’s unpack() function to avoid cache-timing leaks with ord() and chr(). Of course, you can simply use hash_equals() instead of writing it yourself (PHP 5.6.0+).

Alternative: “Double HMAC” String Comparison

If the previous algorithm won’t work (i.e. because you’re concerned your JIT compiler will optimize it away), there is a popular alternative to consider. It’s called “Double HMAC” because it was traditionally used with Encrypt-Then-HMAC schemes.

The algorithm looks like this:

1. Generate a random 256-bit key, K. (This can be cached between invocations, but it should be unpredictable.)
2. Calculate HMAC-SHA256(K, left).
3. Calculate HMAC-SHA256(K, right).
4. Return true if the outputs of step 2 and 3 are equal.

This is provably secure, so long as HMAC-SHA256 is a secure pseudo-random function and the key K is unknown to the attacker.

In code form, the Double HMAC compare function looks like this:

<?phpfunction hmac_compare(string $left, string $right): bool{    static $k = null;    if (!$k) $k = random_bytes(32);    return (        hash_hmac('sha256', $left, $k)            ===        hash_hmac('sha256', $right, $k)    );}

Constant-Time Conditional Select

I like to imagine a conversation between a cryptography engineer and a Zen Buddhist, that unfolds like so:

• CE: “I want to eliminate branching side-channels from my code.”
• ZB: “Then do not have branches in your code.”

And that is precisely what we intend to do with a constant-time conditional select: Eliminate branches by conditionally returning between one of two strings, without an IF statement.

This isn’t as tricky as it sounds. We’re going to use XOR and two’s complement to achieve this.

The algorithm looks like this:

1. Convert the selection bit (TRUE/FALSE) into a mask value (-1 for TRUE, 0 for FALSE). Bitwise, -1 looks like 111111111…1111111111, while 0 looks like 00000000…00000000.
2. Copy the right string into a buffer, call it tmp.
3. Calculate left XOR right, call it x.
4. Return (tmp XOR (x AND mask)).

Once again, in code this algorithm looks like this:

<?phpfunction ct_select(    bool $returnLeft,    string $left,    string $right): string {    $length = mb_strlen($left, '8bit');    if (mb_strlen($right, '8bit') !== $length) {        throw new Exception('ct_select() expects two strings of equal length');    }        // Mask byte    $mask = (-$returnLeft) & 0xff;    // X    $x = (string) ($left ^ $right);        // Output = Right XOR (X AND Mask)    $output = '';    for ($i = 0; $i < $length; $i++) {        $rightCharCode = unpack('C', $right[$i])[1];        $xCharCode = unpack('C', $x[$i])[1];        $output .= pack(            'C',            $rightCharCode ^ ($xCharCode & $mask)        );    }    return $output;}

You can test this code for yourself here. The function was designed to read intuitively like a ternary operator.

A Word of Caution on Cleverness

In some languages, it may seem tempting to use the bitwise trickery to swap out pointers instead of returning a new buffer. But do not fall for this Siren song.

If, instead of returning a new buffer, you just swap pointers, what you’ll end up doing is creating a timing leak through your memory access patterns. This can culminate in a timing vulnerability, but even if your data is too big to fit in a processor’s cache line (I dunno, Post-Quantum RSA keys?), there’s another risk to consider.

Virtual memory addresses are just beautiful lies. Where your data lives on the actual hardware memory is entirely up to the kernel. You can have two blobs with contiguous virtual memory addresses that live on separate memory pages, or even separate RAM chips (if you have multiple).

If you’re swapping pointers around, and they point to two different pieces of hardware, and one is slightly faster to read from than the other, you can introduce yet another timing attack through which pointer is being referenced by the processor.

If you’re swapping between X and Y before performing a calculation, where:

• X lives on RAM chip 1, which takes 3 ns to read
• Y lives on RAM chip 2, which takes 4 ns to read

…then the subsequent use of the swapped pointers reveals whether you’re operating on X or Y in the timing: It will take slightly longer to read from Y than from X.

The best way to mitigate this problem is to never design your software to have it in the first place. Don’t be clever on this one.

Constant-Time String Inequality Comparison

Sometimes you don’t just need to know if two strings are equal, you also need to know which one is larger than the other.

To accomplish this in constant-time, we need to maintain two state variables:

1. gt (initialized to 0, will be set to 1 at some point if left > right)
2. eq (initialized to 1, will be set to 0 at some point if left != right)

Endian-ness will dictate the direction our algorithm goes, but we’re going to perform two operations in each cycle:

1. gt should be bitwise ORed with (eq AND ((right – left) right shifted 8 times)
2. eq should be bitwise ANDed with ((right XOR left) – 1) right shifted 8 times

If right and left are ever different, eq will be set to 0.

If the first time they’re different the value for lefti is greater than the value for righti, then the subtraction will produce a negative number. Right shifting a negative number 8 places then bitwise ANDing the result with eq (which is only 1 until two bytes differ, and then 0 henceforth if they do) will result in a value for 1 with gt. Thus, if (righti – lefti) is negative, gt will be set to 1. Otherwise, it remains 0.

At the end of this loop, return (gt + gt + eq) – 1. This will result in the following possible values:

• left < right: -1
• left == right: 0
• left > right: 1

The arithmetic based on the possible values of gt and eq should be straightforward.

• Different (eq == 0) but not greater (gt == 0) means left < right, -1.
• Different (eq == 0) and greater (gt == 1) means left > right, 1.
• If eq == 1, no bytes ever differed, so left == right, 0.

A little endian implementation is as follows:

<?phpfunction str_compare(string $left, string $right): int{    $length = mb_strlen($left, '8bit');    if (mb_strlen($right, '8bit') !== $length) {        throw new Exception('ct_select() expects two strings of equal length');    }    $gt = 0;    $eq = 1;    $i = $length;    while ($i > 0) {        --$i;        $leftCharCode = unpack('C', $left[$i])[1];        $rightCharCode = unpack('C', $right[$i])[1];        $gt |= (($rightCharCode - $leftCharCode) >> 8) & $eq;        $eq &= (($rightCharCode ^ $leftCharCode) -1) >> 8;    }    return ($gt + $gt + $eq) - 1;}

Demo for this function is available here.

Constant-Time Integer Multiplication

Multiplying two integers is one of those arithmetic operations that should be constant-time. But on many older processors, it isn’t.

Fortunately, there is a workaround. It involves an algorithm called Ancient Egyptian Multiplication in some places or Peasant Multiplication in others.

Multiplying two numbers and this way looks like this:

1. Determine the number of operations you need to perform. Generally, this is either known ahead of time or .
2. Set to 0.
3. Until the operation count reaches zero:
   1. If the lowest bit of is set, add to .
   2. Left shift by 1.
   3. Right shfit by 1.
4. Return .

The main caveat here is that you want to use bitwise operators in step 3.1 to remove the conditional branch.

Rather than bundle example code in our blog post, please refer to the implementation in sodium_compat (a pure PHP polyfill for libsodium).

For big number libraries, implementing Karatsuba on top of this integer multiplying function should be faster than attempting to multiply bignums this way.

Constant-Time Integer Division

Although some cryptography algorithms call for integer division, division isn’t usually expected to be constant-time.

However, if you look up a division algorithm for unsigned integers with a remainder, you’ll likely encounter this algorithm, which is almost constant-time:

if D = 0 then error(DivisionByZeroException) endQ := 0                  -- Initialize quotient and remainder to zeroR := 0                     for i := n − 1 .. 0 do  -- Where n is number of bits in N  R := R << 1           -- Left-shift R by 1 bit  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator  if R ≥ D then    R := R − D    Q(i) := 1  endend

If we use the tricks we learned from implementing constant-time string inequality with constant-time conditional selection, we can implement this algorithm without timing leaks.

Our constant-time version of this algorithm looks like this:

if D = 0 then error(DivisionByZeroException) endQ := 0                  -- Initialize quotient and remainder to zeroR := 0                     for i := n − 1 .. 0 do  -- Where n is number of bits in N  R := R << 1           -- Left-shift R by 1 bit  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator  compared := ct_compare(R, D) -- Use constant-time inequality    -- if R > D  then compared ==  1, swap = 1  -- if R == D then compared ==  0, swap = 1  -- if R < D  then compared == -1, swap = 0  swap := (1 - ((compared >> 31) & 1))  -- R' = R - D  -- Q' = Q, Q[i] = 1  Rprime := R - D  Qprime := Q  Qprime(i) := 1 -- The i'th bit is set to 1  -- Replace (R with R', Q with Q') if swap == 1  R = ct_select(swap, Rprime, R)  Q = ct_select(swap, Qprime, Q)end

It’s approximately twice as slow as the original, but it’s constant-time.

Constant-Time Modular Inversion

Modular inversion is the calculation of for some prime . This is used in a lot of places, but especially in elliptic curve cryptography and RSA.

Daniel J. Bernstein and Bo-Yin Yang published a paper on fast constant-time GCD and Modular Inversion in 2019. The algorithm in question is somewhat straightforward to implement (although determining whether or not that implementation is safe is left as an exercise to the rest of us).

A simpler technique is to use Fermat’s Little Theorem: for some prime . This only works with prime fields, and is slower than a Binary GCD (which isn’t necessarily constant-time, as OpenSSL discovered).

BearSSL provides an implementation (and accompanying documentation) for a constant-time modular inversion algorithm based on Binary GCD.

(In the future, I may update this section of this blog post with an implementation in PHP, using the GMP extension.)

Constant-Time Null-Byte Trimming

Shortly after this guide first went online, security researchers published the Raccoon Attack, which used a timing leak in the number of leading 0 bytes in the pre-master secret–combined with a lattice attack to solve the hidden number problem–to break TLS-DH(E).

To solve this, you need two components:

1. A function that returns a slice of an array without timing leaks.
2. A function that counts the number of significant bytes (i.e. ignores leading zero bytes, counts from the first non-zero byte).

A timing-safe array resize function needs to do two things:

1. Touch every byte of the input array once.
2. Touch every byte of the output array at least once, linearly. The constant-time division algorithm is useful here (to calculate x mod n for the output array index).
3. Conditionally select between input[x] and the existing output[x_mod_n], based on whether x >= target size.

I’ve implemented this in my constant-time-js library:

• resize.ts
• trim.ts

Further Reading and Online Resources

If you’re at all interested in cryptographic side-channels, your hunger for knowledge probably won’t be sated by a single blog post. Here’s a collection of articles, papers, books, etc. worth reading.

• BearSSL’s Documentation on Constant-Time Code — A must-read for anyone interested in this topic
• Cryptographically Secure PHP Development — How to write secure cryptography in languages that cryptographers largely neglect
• CryptoCoding — A style guide for writing secure cryptography code in C (with example code!)
• CryptoGotchas — An overview of the common mistakes one can make when writing cryptography code (which is a much wider scope than side-channels)
• Meltdown and Spectre — Two vulnerabilities that placed side-channels in the scope of most of infosec that isn’t interested in cryptography
• Serious Cryptography — For anyone who lacks the background knowledge to fully understand what I’m talking about on this page

Errata

• 2020-08-27: The original version of this blog post incorrectly attributed Jacobian coordinate blinding to ECDSA hardening, rather than ECDH hardening. This error was brought to my attention by Thai Duong. Thanks Thai!
• 2020-08-27: Erin correctly pointed out that omitting memory access timing was a disservice to developers, who might not be aware of the risks involved. I’ve updated the post to call this risk out specifically (especially in the conditional select code, which some developers might try to implement with pointer swapping without knowing the risks involved). Thanks Erin!

I hope you find this guide to side-channels helpful.

Follow my blog for more Defense Against the Bark Arts posts in the future.

https://soatok.blog/2020/08/27/soatoks-guide-to-side-channel-attacks/

#asymmetricCryptography #constantTime #cryptography #ECDH #ECDSA #ellipticCurveCryptography #RSA #SecurityGuidance #sideChannels #symmetricCryptography