A beginner's guide to constant-time cryptography (2017)

https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html

by histories • 2 years ago

119 62 2 years ago

chosenplaintext.ca

bananaflag• 2 years ago

Can't you just hash the keys before comparing them?

histories3• 2 years ago

What's the difference between a plaintext key and a hash in this context?

The attacker can crack the first byte of the key by trying all 256 possibilities, and observing which one caused the comparison to take longer.

It means that at the end you get the hash and not the key, but it is still a vulnerability

yellow_lead• 2 years ago

If you check hash(a) == hash(b), the attacker cannot produce a valid hash, because cryptographic hash functions are one way. This assumes you use a secure hash function, like not md5.

Even if they discover hash(b), they can't produce b.

Epa095• 2 years ago

Yeah, I (but I am not not OP) agree that hashing is not absolutely perfect, but it's still much much better than leaking the actual password, and it would be cool to at least compare it as a feasible solution.

Getting the first character of the hash is trivial, but as you get further and further out you need to do more and more computational work locally to guess a string which will hash to the prefix you already know (given that your hash is secure against Preimage attack). And then at the end you end up with the complete hash, which itself is extremely hard to get anything useful out of. (all of this is given that you use a hash that is resistant to Preimage attack, and preferably salting as well).

jackjeff2• 2 years ago

Basically you can figure out the hash using the aforementioned timing attack.

You can now perform an offline attack against the password that produced the hash.

It’s like you hacked into the database and got the password hashes.

Then, you fall back to something like hashcat.

If with a bit of luck you just hashed your password with a single round of SHA and did not use something cool like Argon2id then you’re toast. If your password is simple you’re toast too.

On the other hand, if you hashed a totally random key, the safety will rely on whether the hashing algorithm itself is constant time or not. You just moved the needle.

Nursie2• 2 years ago

What's the difference between a plaintext key and a hash in this context?
The attacker can crack the first byte of the key by trying all 256 possibilities, and observing which one caused the comparison to take longer.

OK as a thought experiment, the algorithm is passed plaintext data A (the input that the hacker is trying to guess) and hashed data B.

It hashes A before starting a comparison and then does a naive check, an we have code like-

  function checkApiKey(inputKey, correctHashedKey) {
    inputHashedKey=sha256(inputKey)
    if (inputHashedKey !== correctHashedKey) {
      throw new Error("wrong key");
    }
  }

If we're using a decently secure hash algorithm, for every bit that changes in the input, we will create (indistinguishable from) random changes throughout the output. An attacker on this system can't just continually tweak the first byte of input to figure out when a longer comparison takes place, because there's no guarantee that doing that will ever result in the first byte of the hash matching the first byte of the stored hash. And in theory that doesn't actually give away any information about the full password, because if you've matched byte one, adding the next byte to your guess changes the whole hash in unpredictable ways.

Constant time still removes this sort of avenue entirely, but this would seem to confound the attack (or at least make it much harder problem to solve).

Happy to be educated otherwise if someone that's actually an expert would like to chime in?

dspillett2• 2 years ago

You could use a non-constant salt for the hash, for instance use a sufficiently random number or start with one and increment it, so the comparison is hash(input+salt)==hash(secret+salt), that way each attempt gets the attacker at best a part of a different hash.

This is also assuming the secret is know in plain text – for properly stored passwords you now have hash2(hash1(input+salt1)+salt2)==hash2(prehashed-secret+salt2) with salt2 changing on each attempt.

Of course this is a more computationally expensive than a more direct time-invariant string compare such as bitwise-xor-secret-with-guess-then-bitwise-or-all-bytes-in-result-and-compare-that-to-0, so messing around with hashes & salts is probably not what you would do. The XOR-the-OR method isn't perfect, it will still at least leak the length of the secret if it is unhashed (hashing just before the comparison won't save this because the hashing itself is not time invariant).

tzs2• 2 years ago

You can use a hash where the supplier of inputKey is not able to know the hash value. E.g.,

  function checkApiKey(inputKey, correctKey) {

    r = randomString()
    inputHash = hash(r + inputKey)
    correctHash = hash(r + correctKey)
    
    if (inputHash !== correctHash) {
      throw new Error("wrong key");
    }
  }

adrian_b3• 2 years ago

Hashing is not a good solution.

There are various methods for comparing two long strings in constant time.

For instance, you can compute a bitwise XOR of the two strings, then a bitwise OR of the words of the result.

Whether the final result is null or not shows whether the strings are equal or not, without providing any information about which are the differences, like in the standard scanning method.

This is the general method, all the operations required in the worst case must be executed always, without attempting to use clever tricks, which for certain particular inputs may skip some operations as unnecessary, thus providing information that those inputs have been encountered.

The kind of key comparison that has been given as an example of a mistake was already forbidden by Shannon's principle of confusion (published in a classified paper in 1945, declassified in 1949).

Many people claim to speak about Shannon's "diffusion and confusion", but they have not actually read Shannon's paper, so they guess wrong what Shannon has written. What Shannon has named "confusion" was that in any operation where a secret key or any other secret value is involved, any part of the result or any other observable property must depend equally of all the bits of the secret value (i.e. the bits of the secret value must be confused), so that the enemy is not able to extract any kind of information that applies to a part of the secret value, instead of to the whole secret value.

zimmerfrei3• 2 years ago

You assume that boolean operations are constant time, and whether that holds depends on the uarchitecture and how sophisticated the optimization layers are (e.g. nothing prevents the compiler or even the CPU from short-circuiting the OR as soon as the first XOR is non-zero).

Computing a MAC of the two input values under a once-off random key is actually much stronger.

As a matter of that, this highlights that the goal is to lower the SNR for the attacker, and constant time computation is only one of the two non-exclusive ways to achieve that, the other being adding sufficient noise to their measurements.

Anotheroneagain• 2 years ago

Why not lock the account for 30 minutes after 6 failed attempts?

metafunctor• 2 years ago

That would make it quite easy to maliciously lock someone out.

Instead locking accounts, appropriate throttling might be a better idea.

dspillett2• 2 years ago

Throttling can still result in an effective DoS for the affected user, as they get stuck in the queue behind the brute force attempts. Throttling based on source address is not practical either given many brute force attempts use many hacked hosts as their sources to get around this very sort of limit.

bluGill4• 2 years ago

Which is a big concern for internet accassable things. However if you password entry is a physical device it works great.

mratsim3• 2 years ago

I've written and given a lot of references to attacks, countermeasures, fighting the compilers and even non-cryptographic side-channel attacks to uncover someone's Twitter identity:

- https://github.com/mratsim/constantine/wiki/Constant-time-ar...

cipherboy• 2 years ago

Kyber Slash (and Kyber Slash II) is a recent one in a very modern, PQC finalist algorithm that is missing from the list if you're looking to expand! This was caused by an integer division by a known constant (KYBER_Q = 3329) under a sensitive numerator, with some optimizing compilers not emitting a regular idiv instruction.

https://kyberslash.cr.yp.to/faq.html

mratsim3• 2 years ago

idiv is not constant-time on any ISA anyway ;)

makira• 2 years ago

Do any of these attacks matter for single-tenant computers where all network packets are sent on a hardware timer (say, 10 kHz) independent of crypto computing? Doesn't that mitigate any side-channel timing attacks from the start?

Zamicol2• 2 years ago

I noticed in July of 2022 that Go did exactly the vulnerable example and reported it to the security team.

https://github.com/golang/go/issues/53849

It was fixed as of Go 1.21 https://go.dev/doc/go1.21

---

The article cites JavaScript, which is not constant time. There's no sure way to do constant time operations in JavaScript and thus no secure way to do crypto directly in Javascript. Browsers like Firefox depend on low level calls which should be implemented in languages that are constant time capable.

JavaScript needs something like constant time WASM in order to do crypto securely, but seeing the only constant time WASM project on GitHub has only 16 stars and the last commit was 2 years ago, it doesn't appear to have much interest. https://github.com/WebAssembly/constant-time

However, for JavaScript, I recommend Paul's library Noble which is "hardened to be algorithmically constant time". It is by far the best library available for JavaScript. https://github.com/paulmillr/noble-secp256k1

gmac2• 2 years ago

In JS you’d use SubtleCrypto, (as long as it implements what you need), right?

Zamicol2• 2 years ago

Yes, SubtleCrypto is preferred when usable.

There's two main issues with SubtleCrypto, a minor problem and a major problem. The minor problem is that it doesn't support much. 13 year old modern algorithms like Ed25519 and Ed25519ph are largely unsupported and browser support moves at glacial speed. Ed25519ph isn't supported by any, even though it's been adopted by NIST (see FIPS 186-5). This is where libraries like Paul's must be used. For browser support see https://caniuse.com/mdn-api_subtlecrypto_sign_ed25519

The major problem with SubtleCrypto is that it requires the original message to sign and verify. SubtleCrypto.sign(algorithm, key, data) and SubtleCrypto.verify(algorithm, key, signature, data)

This is contrasted to Go's ECDSA package which expects a digest to sign and verify. See https://pkg.go.dev/crypto/ecdsa#PrivateKey.Sign

This means that if signing a 2 GB document, Go can easily verify the signature using the 256 bit digest, while Javascript would require the whole 2 GB document to be loaded into SubtleCrypto.verify before verification and is an enormous waste of resources.

If it isn't clear from the above what the problem is, let me rephrase: SubtleCrypto's sign and verify always rehashes, so a developer cannot give it the digest. Instead, developers are forced to give it the whole document so it can rehashed by SubtleCrypto. This is a significant design blunder that others, like Go, avoided and will motivate developers to use less constant time safe libraries like Paul's.

hasoleju• 2 years ago

The article briefly mentions the possibility to access secrets on a hardware level by monitoring the ressources of other threads. I have no idea if this is only possible in theory but completely impractical becauste it takes so much effort. Have there been attacks like that in the past?

mratsim3• 2 years ago

Percival cache attacks on Hyperthreading.

I go over some examples here: https://github.com/mratsim/constantine/issues/358#issuecomme...

another-dave4• 2 years ago

Could you just iterate through the entire key even if you know it's not a match after 1 byte?

Then it would always take the same amount of time to return `true/false`, even if you knew this value earlier in the loop.

sjducb2• 2 years ago

What’s the exact algorithm you would write for that?

Let’s say you have a bool, $is_match then whenever two chars of the string don’t match you write false to it.

It takes slightly longer to write false than do nothing. You’re still leaking the total number of matching characters.

I think speculative execution on the CPU would amplify this effect. For example:

aaaaaaaaa != ccccccccc will be much faster than ababababa != aaaaaaaaa because in the first example the cpu will correctly guess and speculatively execute that the two characters are different. They were different last time. They’ll probably be different again.

continuational• 2 years ago

Quick take, assuming equal length of a and b:

For each byte index i:

x[i] = a[i] XOR b[i]

return sum(x) == 0

another-dave4• 2 years ago

As a naive approach something like this:

    // Throw an error if inputKey is not correct.
    // inputKey and correctKey are both strings
    function checkApiKey(inputKey, correctKey) {
      var isMatch = true;
      for (var i = 0; i < inputKey.length; i++)
        if (inputKey.charAt(i) !== correctKey.charAt(i)) {
          isMatch = false;
        }
      }
      if (!isMatch) {
        throw new Error("wrong key");
      }
    }

So what I meant is, don't return early when isMatch = false, instead walk the entire key regardless.

femto• 2 years ago

So "constant time" is another way of saying "Every secret bit should be treated the same"?

cosmolev• 2 years ago

Why should it be constant-time, by the way? Wouldn't random-time suffice?

DexesTTP• 2 years ago

There's a good chunk of the article about that. "Constant-tile" is a bit of a misnomer, "secret-independent resource consumption" is a better way to say it. If you just add a "sleep(rand)" or equivalent then you can still break the secret using statistics or sidechannel attacks.

123yawaworht4562• 2 years ago

If you didn’t, here’s how the exploit works. The comparison operator, “!==”, is vulnerable to a timing attack. The string comparison compares the two keys one byte at a time, stopping as soon as it finds an offset where the two strings do not match. As a result, checkApiKey will take longer if the two keys start with the same bytes. It’s sort of like if the error message itself said “wrong key, but you got the first 2 bytes right!”.

I understand that it is technically a vulnerability, but you will not be able to measure these nanosecond fluctuations over network. hell, you wouldn't even be able to measure them with direct physical access to the machine. even if you sample every attempt a trillion times.

chowells• 2 years ago

And yet, it's been demonstrated to work in practice. How do you square this apparent contradiction?

mecsred• 2 years ago

Thanks to thinking like that, many a system has been hacked. I can't think of any statistical methods that would recover this information, therefore they don't exist.

foobarian• 2 years ago

The fun thing about physical systems is that in spite of complexity in the stack, there are a lot of Gaussian processes in play which are very easy to clean up with some processing.

123yawaworht4562• 2 years ago

all I know is that it doesn't take even one microsecond to compare 32 bytes - it takes nanoseconds. and yes, I can't think of a way to meaningfully measure that delta over a real network, where every packet passes through dozens of switches and routers, each one of which introduces enough entropy to completely drown out any attempt to measure things with such precision.

but more importantly, what kind of system allows itself to be pounded with thousands or millions of requests to the authentication endpoint?

tzs2• 2 years ago

If you didn’t, here’s how the exploit works. The comparison operator, “!==”, is vulnerable to a timing attack. The string comparison compares the two keys one byte at a time, stopping as soon as it finds an offset where the two strings do not match. As a result, checkApiKey will take longer if the two keys start with the same bytes. It’s sort of like if the error message itself said “wrong key, but you got the first 2 bytes right!”.

There was a similar vulnerability but using space instead of time on TOPS-10 on the DEC PDP-10. That was back in the day when passwords were stored in plain text. When the operating system had to check a password it just did a string compare of the string supplied by the caller and the plain text string.

Crucially, it did not copy the caller's string into kernel memory before comparing. It compared the plain text in kernel memory with the caller string in user memory.

The trick then to password cracking was to start by guessing first characters. To test a first character you place it at some memory address where the next address is invalid, and you install a handler for access faults. Then check the password, telling the kernel your guess is longer than 1 character.

If you get an access fault you know that first character was right and the string comparison continued on into the invalid address. So try first characters until you get an access fault.

Once you have the first character, repeat but now starting the guess 2 characters before the invalid memory, with the right first character and you guess for the second character, and tell the kernel the password is at least 3 characters. Same for the rest of the characters.

(I don't remember if the kernel's string compare checked length first. If it did, add a first step above of determining the password length. Same idea...start near invalid memory, and guess lengths until you find the one that gives an access fault).

theK2• 2 years ago

What Situation would a computation like in that article actually happen in?

All key checking procedures I have ever encountered either depended on hash comparisson or asymetric crypto (or a combination of them) both of which are mostly immune to pragmati timing attacks as far as I know.

A beginner's guide to constant-time cryptography (2017)

Related Stories