Security considerations about subtle.ConstantTimeCompare

[imk...@gmail.com]

Hi there,

First time participating in this group.

Lately I have been taking a look at subtle.ConstantTimeCompare and how it is being used out there, and to my surprise, many many people are using it incorrectly (I think).

The following search on github will highlight many of these cases.

https://github.com/search?l=go&q=ConstantTimeCompare&type=Code&utf8=%E2%9C%93

Namely this kind of piece of code I found a lot:

https://play.golang.org/p/NU5uTaB-sp

Several problems I found here, but the one that strikes me mostly as deceptively dangerous is the use of "actual, actual" in the else branch.

Not only this, but the if/else branch and the && false thing, are also not good imho.

Wouldn't it be good if subtle could provide an implementation that does a ConstantTimeEq+ConstantTimeCompare combo in a secure way?

Maybe this also has some problems but, something like:

https://play.golang.org/p/pICufdp1zA

Best regards,

Mario

[Tamás Gulácsi]

Sorry, but what's the problem with the first example? This code ensures a constant comparison time both with correct and uncorrect password.

[Mário Freitas]

Hi Tamás,

My first instinct was that it was wrong.

After a while, I had the same thought you just did.

But then again, after some consideration, I came to my first conclusion.

Here's why.

Assume you have this black box.

You throw it some input and you always get a true/false response. This takes O( n ) where n is the length of the secret.

That sounds safe enough, because like you said, it ensures constant comparison time in all cases.

I don't think this is safe enough, and I will give another example.

Assume now, that, you're somehow able to replicate this box, let's call it white box. (Say for instance, that you're able to set up a machine that has the same hardware and configuration of black box which runs this program managing the secret).

I called this second box "white" on purpose: you are able to reconfigure its secret.

So, you try with password length n=1 and you measure the time it takes if you give it an input with different length.

You measure the time it takes to process a wrong password for this n.

Now you increase n by 1.

You repeat this process until you get the same response time as the black box.

When you have a similar response time, you have guessed the right length of the black box.

Yes we can say it is constant time between runs against the same secret, but the problem is, this time changes depending on the length of the secret.

I know this is all tricky to guess it right, but from the point of view of timing attacks, I guess it makes sense?

So in my second example I changed the question to: instead of taking O ( n ) with n being the length of the secret, I think it's safer to take O ( i ) where i is the length of the input. This shouldn't be a problem, since i is already a given (it's the size of the input!). If and only if i = n, then it will go the normal comparison against the secret, and that should take O ( n ) = O ( i ). Therefore there is no leakage of n nor its contents.

There is also the if/else branching problem and the && false, like I said but I guess that is kind of minimal compared to the problem I outlined before. 

Best,

Mario

[Donovan Hide]

I guess the if-else will cause branch prediction to kick in on the CPU, which can potentially be timed by an attacker providing various inputs. It's subtle, and can probably be better explained by Adam Langley than myself :-) 

[Mário Freitas]

Yeah.

I tried to tackle that by getting rid of the if/else branch, by using the 1 (true) / 0 (false) return value from ConstantTimeEq and use it as an index into an array that has the target byte slice (0: input or 1:secret).

If it is 1 (meaning both strings have the same length), I test the input against secret. If it is 0, I test the input against input (itself).

I'm not exactly sure how is go translating my second example into machine code (and for each supported architecture), but if I were to guess I would say it uses some kind of operation for memory addressing the array@index to get the value of the element (the target byte slice), and that would take constant time.

I am not sure about cpu cache effect prediction, though.

[Caleb Spare]

ConstantTimeCompare does not try to hide length information, and attempting to do so is probably doomed. For passwords, for instance, you shouldn't be comparing (or even storing) raw password values; you're comparing the (fixed length) hashes.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Matt Silverlock]

> ConstantTimeCompare does not try to hide length information, and attempting to do so is probably doomed. For passwords, for instance, you shouldn't be comparing (or even storing) raw password values; you're comparing the (fixed length) hashes.

Agree. Things to note:

1. If the security of your application absolutely relies on hiding the length of values, you're probably doomed. The password example is a good one; TLS doesn't hide length information either.

2. In many cases, you're comparing a fixed hash or HMAC (see how crypto/hmac.Equals uses it https://golang.org/src/crypto/hmac/hmac.go?s=2437:2471#L87), where the length is known or within a range of typical values

3. Pulling off a timing attack over the Internet that results in a practical attack is really, really hard.

[James Bardin]

On Friday, November 20, 2015 at 5:58:59 PM UTC-5, Matt Silverlock wrote:

3. Pulling off a timing attack over the Internet that results in a practical attack is really, really hard.

Not really *that* hard. Remote timing attacks have been proven practical for a long time

A few examples off the top of my head:

"Remote Timing Attacks are Practical": https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

Coda Hale commenting on a timing issue found in keyczar: http://codahale.com/a-lesson-in-timing-attacks/

"Lucky Thirteen" from a couple years ago: https://en.wikipedia.org/wiki/Lucky_Thirteen_attack

[Mário Freitas]

I completely agree with that.

Either way, putting the usage apart, I think it should be safer in any situation to compare the strings up to the input size.

Why? Because it costs the same, and because you're not giving away anything (including the size of the hash you're system is using).