Get Even More Visitors To Your Blog, Upgrade To A Business Listing >>

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 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 . How these numbers are derived and verified depends on the algorithm in question.

In the case of ECDSA, you calculate two numbers (, ) based on the hash of the plaintext and , both multiplied by the modular inverse of (mod ). You then calculate a curve point based on the public key (). The signature is valid if and only if the x coordinate of that curve point is equal to 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 for a chosen message for two reasons:

  1. The derivation of is effectively an All-Or-Nothing Transform based on secret inputs.
  2. The curve point equation ) multiplies the ratio r/s by the public key (because ).

In order to calculate a valid pair that will validate , you’d need to know the secret key that corresponds to .

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.)

TL;DR

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



This post first appeared on Dhole Moments - Software, Security, Cryptography, And The Furry Fandom, please read the originial post: here

Share the post

Dead Ends in Cryptanalysis #2: Timing Side-Channels

×

Subscribe to Dhole Moments - Software, Security, Cryptography, And The Furry Fandom

Get updates delivered right to your inbox!

Thank you for your subscription

×