Categories
Cryptography Software Security Technology

Dead Ends in Cryptanalysis #2: Timing Side-Channels

Previously on Dead Ends in Cryptanalysis, we talked about length-extension attacks and precisely why modern hash functions like SHA-3 and BLAKE2 aren’t susceptible.

The art and science of side-channel cryptanalysis is one of the subjects I’m deeply fascinated by, and it’s something you’ll hear me yap about a lot on this blog in the future.

Since my background before computer security was in web development, I spend a lot of time talking about timing side-channels in particular, as well as their mitigations (see also: constant-time-js).

Pictured: Me, when an interesting attack gets published on ePrint.
(Art by Khia.)

However, timing side-channels aren’t omnipotent. Even if your code isn’t constant-time, that doesn’t mean you necessarily have a vulnerability. Case in point:

Length Leaks Are Usually Nothing-Burgers

If you look closely at a constant-time string equality function, you’ll see some clause that looks like this:

if (left.length !== right.length)
    return false;

A common concern that crops up in bikeshedding discussions about the correct implementation of a constant-time compare is, “This will fail fast if two strings of non-equal length are provided; doesn’t this leak information about the strings being compared?”

Sure, but it won’t affect the security of the application that uses it. Consider a contrived example:

  • You’re encrypting with AES-CTR then authenticating the ciphertext with HMAC-SHA256 (Encrypt then MAC).
    • For added fun, let’s assume you’re using HKDF-HMAC-SHA512 with a 256-bit salt to derive separate a separate encryption keys and MAC keys from the input key. This salt is prepended to the ciphertext and included as an input to the HMAC tag calculation. Now you don’t have to worry about cryptographic wear-out.
  • You’re padding the plaintext to exactly 16 kilobytes prior to encryption, because the exact length of the plaintext is considered sensitive.
  • You remove the padding after decryption.
  • Your constant-time comparison is used to validate the HMAC tags.

Even though the length of your plaintext is sensitive, it doesn’t really matter that length mismatches leak here: The inputs to the constant-time compare are always HMAC-SHA256 outputs. They will always be 32 bytes (256 bits) long. This is public knowledge.

If you’ve somehow managed to design a protocol that depends on the secrecy of the length of a non-truncated HMAC-SHA256 output to be secure, you’ve probably fucked up something fierce.

However, if you were comparing the unpadded plaintexts with this function–or passing the unpadded plaintext to a hash function–you might have cause for concern.

Double HMAC” is a defense against compiler/JIT optimizations, not length leaks.
(Art by Khia.)

When Do Timing Leaks Cause Impact?

Timing side-channels only lead to a vulnerability when they reveal some information about one of the secret inputs to a cryptographic function.

  • Leaking how many leading bytes match when comparing HMACs can allow an attacker to forge a valid authentication tag for a chosen message–which often enables further attacks (e.g. padding oracles with AES-CBC + HMAC). The cryptographic secret is the correct authentication tag for a chosen message under a key known only to the defender.
  • Leaking the number of leading zeroes introduced the risk of lattice attacks in TLS when used with Diffie-Hellman ciphersuites. See also: the Raccoon Attack. The cryptographic secret is the zero-trimmed shared secret, which is an input to a hash function.
  • Leaking the secret number k in the modular inverse step when calculating an ECDSA signature gives attackers enough information to recover the secret key. This can happen if you’re using non-constant-time arithmetic.

Timing attacks can even break state-of-the-art cryptography projects, like the algorithms submitted to NIST’s Post-Quantum Cryptography standardization effort:

Since most PQ Crypto algorithms use the Fujisaki-Okamoto transform, they’re all potentially susceptible to this attack.

However–and this is important–if what leaks is a public input (n.b. something the attackers already knows anyway), then who cares?

(Art by Khia.)

Why Timing Leaks Don’t Break Signature Verification

If you’re reviewing some cryptography library and discovered a timing leak in the elliptic curve signature verification function, you might feel tempted to file a vulnerability report with the maintainers of the library.

If so, you’re wasting your time and theirs, for two reasons:

  1. Signature verification is performed over public inputs (message, public key, signature).
  2. Knowing which byte verification the comparison fails on isn’t sufficient for forging a signature for a chosen message.

The first part is obvious (and discussed above), but the second might seem untrue at first: If HMAC breaks this way, why doesn’t ECDSA also suffer here?

The Anatomy of Elliptic Curve Digital Signatures

Elliptic curve signatures are usually encoded as (r, s). How these numbers are derived and verified depends on the algorithm in question.

In the case of ECDSA, you calculate two numbers (u_1, u_2) based on the hash of the plaintext and r, both multiplied by the modular inverse of s (mod n). You then calculate a curve point based on the public key (Q_{A}). The signature is valid if and only if the x coordinate of that curve point is equal to r from the signature (and isn’t equal to the point at infinity).

Why Don’t Timing Attacks Do Anything Here?

Even with a timing leak on the string compare function in hand, you cannot easily find a valid (r^{\prime}, s^{\prime}) for a chosen message for two reasons:

  1. The derivation of (r, s) is effectively an All-Or-Nothing Transform based on secret inputs.
  2. The curve point equation (x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}) multiplies the ratio r/s by the public key (because u_{2}=rs^{-1}\,{\bmod {\,}}n).

In order to calculate a valid (r, s) pair that will validate r=x_{1}, you’d need to know the secret key that corresponds to Q_{A}.

It’s not impossible to calculate this value, but it’s computationally infeasible, and the difficulty of this problem is approximately one fourth the signature size. That is to say, 512-bit signatures, derived from 256-bit keys, have a security level of 128 bits.

Thus, timing leakage won’t let you perform an existential forgery here.

Aside: Don’t confuse signatures for MACs, as iMessage famously did.
(Art by Khia.)

Under What Conditions Could Timing Side-Channels Matter to ECDSA Verification?

Suppose you have a JSON Web Token library that’s vulnerable to the type confusion attack (wherein you can swap out the "alg":"ES256" with "alg":"HS256" and then use the public key as if it was an HMAC symmetric key).

In this hypothetical scenario, let’s say you’re using this JWT library in an OIDC-like configuration, where the identity provider signs tokens and the application verifies them, using a public key known to the application.

Also assume, for absolutely contrived reasons, that the public key is not known to the attacker.

If you had a timing attack that leaks the public key, that would be a viable (if horrendously slow) way to make the vulnerability exploitable.

However, even in this setup, the timing leak still doesn’t qualify as a real vulnerability. It merely defeats attempts at Security Through Obscurity. The real vulnerability is any JWT library that allows this attack (or alg=none).

Additionally, you can recover the public key if you have sufficient knowledge of the curve algorithm used, message signed, etc.–which you do if the algorithm is ES256–so you don’t really even need a timing leak for this. Consequently, timing leaks would only help you if the original algorithm was something custom and obscure to attackers.

(Aside: there are two possible public keys from each signature, so the signature alone isn’t sufficient for uniquely identifying public keys. If you’re hoping to reduce protocol bandwidth through this trick, it won’t work.)

TL;DR

In order for a timing leak to be useful for cryptanalysis, it cannot leak a publicly-known input to the cryptographic operation.

By Soatok

Security engineer with a fursona. Ask me about dholes or Diffie-Hellman!

One reply on “Dead Ends in Cryptanalysis #2: Timing Side-Channels”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s