Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ConstantTimeCompare uses less time when length differs and no longer suggests equal length slices #47075

Closed
krolaw opened this issue Jul 7, 2021 · 5 comments

Comments

@krolaw
Copy link

krolaw commented Jul 7, 2021

What version of Go are you using (go version)?

master

Does this issue reproduce with the latest release?

yes

https://github.com/golang/go/blame/master/src/crypto/subtle/constant_time.go#L12

ConstantTimeCompare used to panic when len(x) != len(y), now it simply returns zero. Documentation no longer suggests that it be called with two equal length byte slices. Therefore, a dev may expect this function to always take constant time regardless of whether len(x) != len(y), and may provide an attack vector. i.e. an attacker may be able to find the length of the key/password/etc reducing the amount of work required to break in.

@randall77
Copy link
Contributor

Dup of #31355, closing.

The panic -> return 0 behavior changed in 2014.

@krolaw
Copy link
Author

krolaw commented Jul 16, 2021

It is literally impossible to make such a function constant time across all possible lengths (assuming lengths are unbounded).

What about something like: krolaw@eb2cea3?branch=eb2cea3005b63eafc2a098667b9484bde689f6c0&diff=split

@randall77
Copy link
Contributor

@krolaw Not sure what that's trying to fix. Sure, we could make ConstantTimeCompare take longer when len(x)!=len(y). Even take time O(len(x)). But what does that solve? Timing still leaks the length of x, which contains more info than the bit len(x)==len(y). Unless you're presupposing that only y is secret? Even in that case, the fact that y is a different length than x is still detectible by timing, as the memory access pattern is different in the len(x)==len(y) and len(x)!=len(y) cases.

@krolaw
Copy link
Author

krolaw commented Jul 17, 2021

@randall77 Thank you for your enlightening response. I hadn't considered different memory locations to have different timing. I had only presumed that making the number of memory accesses constant (or proportional to attack input) would be sufficient. However, wouldn't the changes to the count of memory accesses be far easier to detect than changes in memory access locations?

Ignoring memory pattern access timing differences, I'm not sure how the length of x is leaked by timing. If x is the secret trying to be broken, then isn't the number of accesses constant as the same x is used every time?

@randall77
Copy link
Contributor

However, wouldn't the changes to the count of memory accesses be far easier to detect than changes in memory access locations?

Sure.

Ignoring memory pattern access timing differences, I'm not sure how the length of x is leaked by timing.

There's a loop in your code that runs len(x) times. The running time of ConstantTimeCompare is proportional to len(x). Measuring the time and dividing by an estimate of the host's speed gives you len(x).

If x is the secret trying to be broken, then isn't the number of accesses constant as the same x is used every time?

Why is the same x used every time? Maybe in your application, but that's not something the Go standard library can assume.

@golang golang locked and limited conversation to collaborators Jul 19, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants