TL;DW: Steam accepted blank recovery codes for password resets, enabling passwords to be changed without needing access to the recovery email account.
I hope someone is writing a new test case.
Sample buggy code (that I just made up):
(user_token is user supplied token, token is the correct token)
for(i = 0; i < strlen(user_token); i++) {
if(user_token[i] != token[i]) return false;
}
return true;
I'm trying to think of a bug where blank fails, but truncated versions do not.
But I guess you're right, better safe than sorry.
strcmp() is at least better than a buggy equivalent that doesn’t actually work :)
If this is in fact how how things worked, what a great showstopper bug
if(!check_params()) {
failed = true;
goto fail;
}
if(some_other_check()) {
failed = true;
goto fail;
}
if(token_length == 0) {
goto fail; // oops, forgot to set failed
}
...check the token...
fail:
if(failed) {
return auth_failure;
}
EDIT: Updated explanation of problem because I originally explained it wrong (required omission of the value on submission, not just a blank value).
Similarly most RDBMSs are case insensitive by default while most programming languages are not, which again can lead to problems where different layers in an application disagree about string equality.
It isn't at all unlikely that bugs in naive code (caused by people not being concious and careful of these sorts of differences) can allow attackers to cause useful information to leak.
Anyone who did not have an active password reset token could have their password reset, because it was selecting users based on their username/email and the user not having an active password reset token (token reset to NULL upon successful password reset, so it wasn't just users who had never reset a password, but also any user who had redeemed their most recent password reset request (obviously, this included practically all users)).
Yes, there are things that could've been done to prevent this bug from happening, like using Rails's validation mechanisms to reject any POST that didn't contain the field, but that's not really the point. The point is that simple, subtle bugs can and do sneak into production codebases, and more-exhaustive-than-usual testing is needed for anything used to control account access like password resets.
I mean Laravel is somewhat good. But there wasn't a real mature PHP Framework in the past. Especially not as mature than Rails, Django.
You are using a drastically different version of modern than normal English usage. Where's that Scotsman when you need him?
When designing test cases choose the extreme values, no text, too much text, etc.
Input validation can be made to be machine-verified, and anit-patterns can be learned and avoided. Static analysis tools can raise red and yellow flags.
Finally, frameworks are being built for handling security critical things like account validation, crypto key handling, an related tasks that are important to get right.
As the space continues to evolve, things like this will become less common, and someone who is aware of the trade and is diligent will be less likely to make mistakes.
a spell checker didn't save you from a typo. not nitpicking, just using this example to illustrate a point: for an app to be secure, developers have to be 100% of the time on ball, while an attacker just has to be lucky once.
the weight is so much in favor of attacker than only few of the biggest can afford to pay for a competitive level of security, it being a race: security is effective not when perfect, but when it costs more to attack a site than what you'd gain of it.
Believe this is where parent's preference for high-quality, easy-to-use libraries handling common security operations comes from.
It's a lot easier to make a typo (or logical mistake) in 250 lines of your own code than in (hopefully) <250 lines of a library invocation.
Honestly, library functionality like this in any given language should be thought of as an analog to infrastructure spending. We're finally seeing reinvestment from end-users and value capturers (Facebook, Google, MS, etc) back down the chain to the OSS projects they depend on.
Language guiders (and in some cases the support businesses who are attached to languages) should be equally serious about this. If your language doesn't have high-quality, easy-to-use libraries to mitigate attack surfaces, that's a fundamental weakness in your language eco-system...
(Aka the "Perl+CPAN is better than a lot of more advanced languages, because code" argument)
Could (and should) a safer language pre-empt that you should first check strlen(str) != 0 before doing strcmp? I know of no language which does this.
> Input validation can be made to be machine-verified
Likewise, can you elaborate on this? How does the machine know what type of input this is? If input is tagged by the developer, what's to stop the developer from forgetting to tag the input correctly?
In some languages, you can define a string type that only contains strings of one or more characters. And then you'd need to "convert" a regular string into one of those by using some function that forced you to handle the strlen(str) == 0 case.
I believe you can define that in Idris, for example.
If you are comparing byte by byte the correct code is:
valid = true;
for(i = 0; i < strlen(user_token); i++) {
if(strlen(token) < i || user_token[i] != token[i]) valid = false;
}
if(strlen(token) != strlen(user_token)) valid = false;
return valid; int token_length = strlen(token);
int input_length = strlen(input);
int match_count = 0; // for constant-time comparison...
// Just get this out of the way now; no need to dawdle
// (because the length of a token is generally known)
if (token_length != input_length) {
return false;
}
// No need to worry about mismatched buffer lengths at this point
for(int i=0; i<token_length; i++) {
if (token[i] == input[i]) {
match_count++;
}
}
// if the same number of characters match, voila!
return (match_count == token_length);
if(strlen(token) < i || user_token[i] != token[i]) valid = false; int token_length = strlen(token);
// Just get this out of the way now; no need to dawdle
// (because the length of a token is generally known)
if (token_length != strlen(input)) {
return false;
}
// No need to worry about mismatched buffer lengths at this point
for(int i=0; i<token_length; i++) {
if (token[i] != input[i]) {
return false;
}
}
return true;
You cannot write a constant-time function in portable C / C++, and trying to do so is a fool's game.
Something like this should work:
/* Swap char for uint<register_size> for speed */
#define CMP_TYPE char
/* Assuming char* sha256(char* input); */
CMP_TYPE* input_hash=(CMP_TYPE*) sha256(input);
CMP_TYPE* token_hash=(CMP_TYPE*) sha256(token); /* Precomputed? */
/* max_pos=32 for char on most systems */
int max_pos=256 >> (3 + sizeof(CMP_TYPE));
char cmp=0;
for (int i=0;i<max_pos;i++) {
cmp = cmp | (token_hash[i] ^ input_hash[i]);
}
return (cmp != 0);
For instance, it's legal for the compiler to insert a strcmp fallthrough (`if input == token: return true`, or rather the strcmp equivalent) at the start, I'm pretty sure.
For one thing, you have to assume that the SHA function is data-independent time (which, again, good luck doing in C / C++).
For another thing, noise in timing attacks doesn't prevent them. Even at levels of noise that seemingly obscure everything. And it's a very bad thing to rely on network latency being unpredictable enough.
b) There is no SHA algorithm in the C / C++ standard library (that I know of), muchless a guaranteed constant-time (or rather, data-independent) one.
c) The compiler is well within its rights to insert "busy_loop_for_ms(input_char);" anywhere it wishes. It is unlikely to do so, but it is allowed to. As I said: C and C++ don't have any notion of constant or variable time.
Or rather, it accelerates a dictionary attack from O(sizeof(dictionary)) tries to O(length(hash)) tries.
(Let's suppose you are comparing by hex digits. You try 16 dictionary "words" whose hashes start with 0...f. One of those should take slightly longer. You then try 16 dictionary "words" whose hashes start with the digit found previously with different second digits. (Skip any digits that you don't have a word for.) One of those should take slightly longer... Repeat until found.)
This can be mitigated with a salt - if and only if you manage to prevent the user from figuring out how your salting scheme works.
"You cannot write a constant-time function in portable C / C++..." perhaps you mean that we can't outsmart compiler optimizations. Without optimizations ("Debug" configuration), the code runs exactly as written.
Ultimately, I'm going to prefer code with obvious intent regardless of how the compiler will optimize the thing. We'll just have to find a way around this timing attack business.
That being said, on a simple architecture - namely a shallow pipeline - this sort of thing is an "obvious" optimization.
And w.r.t. "without optimizations" - there is no such thing at the C / C++ level. There are computer architectures where optimizations pretty much have to be done, for instance. (Many architectures with compile-time scheduling, for instance.)
For instance, if you have a dataflow machine it may end up running this in non-constant time. And I'll note that modern x86 processors are looking more and more like dataflow machines.
In theory? The compiler is still free to add data-dependent delays.
For an "evil" example, a compiler could do this:
...
for(int i=0; i<token_length; i++) {
char temp = input[i];
if (token[i] == temp) {
match_count++;
}
wait_for_ns(temp);
}
Currently, CMOV is looking like it could become the same thing. It currently takes data-independent time. But is not guaranteed to do so, and very well may not in the future.
The distinction is that hardware tends to change slower than software. You generally have multiple compiler versions per hardware version (possible exception of embedded processors, but even then...).
One is just relying on adding a positive number never makes a number > 0 0 again. The other is just relying on oring a bit to a non-zero number never makes it zero again.
At first I was thinking you could write the bits out to a separate word, but I think this suffices:
uint result = 0;
for (i = 0; i < length; i++)
result |= notmatch (i);
return result == 0;
But, actually I'm kind of confused about your first point. What optimizations did your compiler use to eliminate the match_count++ and hoist the return into the loop?
But on an architecture with a short pipeline it can be worth it for a compiler to do so.
And it's simple, in theory if nothing else. Note that once result has a bit set, result cannot ever return to zero. Hence, if result has a bit set, one can return false immediately. And all of a sudden you lose the constant-time part.
As for how a current compiler could do so? Look at what happens if/when the loop is unrolled.
That current compilers don't tend to do this sort of optimization makes it only more dangerous - because people do not go back and re-examine old code nearly as often as they should. Much less check the assembly every time they update the compiler.
It's a mitigation but it doesn't prevent the attack.
Not to mention: how exactly will you check that you've compared them all?
I was thinking you could maintain an array of flags to indicate whether you've compared a certain position before, and a count of all the compared positions so far.
Alright, here are my other ideas:
1) Properly chosen 8-character passwords are pretty strong, right? So why not copy all of the 8-bit chars into a u64 and compare that directly? You can treat longer passwords as a series of 8-char passwords. Assumes a machine that won't short circuit on u64_a == u64_b. Less effective for 32-bit. The compiler won't undo this since it's an optimization (1x aligned 64-bit compare is more efficient than 8x 8-bit compares, seven of which are unaligned).
2) Introduce a random delay after the byte-wise comparison is done that is up to 10x the length of the comparison. The comparison variance gets lost in delay variance. I know, a mitigation, but it's effective. Combine with random selection of characters for more effectiveness.
3) Use a perfect hash of the password. You don't need to compare keys after a perfect hash.
Thanks for humoring me.
1) That causes massive problems for people (like me) who use passphrases. (I use diceware passwords for anything I don't use a password manager for. So things like "corn umpire khaki dow heave hiatt sis steal". That's ~103 bits of entropy (massive overkill for most things), and yet is a whole lot easier to remember than, say, "FlyaJdqJW6kvyUQeE" - which is ~101 bits of entropy (17 random upper/lower/digit characters).
It also assumes that the machine doesn't short-circuit, as you say.
And, again, you're assuming that the compiler doesn't undo it. Just because it won't be undone by optimizations on current machines doesn't mean it won't be undone by optimizations on future ones. On a RISC architecture, for instance, a 64-bit compare may not even exist - it may be implemented by 8-bit compares. Or 16, or 32. Whatever.
2) Ever heard of the german tank problem? That will not drown out the comparison, not at all. I can defeat your example (10x noise as comparison time) with >90% accuracy with 100 samples. (Just take samples, and take the mean of the sample minimum and maximum.)
3) Without leaking other people's passwords every time you generate a password for someone?
I find this sort of conversation intriguing. I want things to be more secure, I just don't know of a good way to do so.
But a) pigeonhole principle (you need an output at least as long as the longest string you'll encounter), and b) I was under the impression that perfect hash schemes require you to know the set of strings encountered ahead-of-time.
Could you give me an example of a perfect hash function that is suitable and secure enough for password use? I do not know of any.
All of the perfect hash functions I've found require knowing all of the keys ahead of time. You might not be able to fit 16384 PB on your hard drive or in memory. (Hey, I don't know. You could work at LLNL.) But I think that if you knew you might use any key in the space, and you didn't insist on a minimal perfect hash, i.e. one where there is a 1:1 mapping from hashes back to keys, that you could write such a function without having all of the keys.
If you did this, you'd also need to prove you were generating a unique and effectively random hash. If I was a crypto academic, that might be an interesting line of research. I'd be kind of surprised if nobody ever tried this though, and there's probably a decent amount of literature to pore over. I guess most people use perfect hashes for hashtables and not as a defense against timing attacks.
If you pick a cryptographically secure hash that's long enough, you don't need to worry about collisions. The birthday problem dictates that you start getting collisions after ~sqrt(D) random entries. So if you pick a 128+ bit hash you should be fine on that front (128 bits -> ~2^64 entries before a collision on average, which shouldn't be a problem.)
However, as I've mentioned elsewhere, all this does is punt the constant-time problem off to the hash function.
Anyway, why exactly isn't the hash function constant-time? I don't understand this, the hashes I've played with for hashtables are just a bunch of bit shifts. Is it only message length?
The hashes generally used for things like hash tables don't need to be cryptographically secure, and as such can be substantially simpler. When you start getting into cryptographically secure hashes things get complex enough that you start ending up with timing variations if you're not very careful. Especially once you start talking about table lookups / etc (although that's more common with encryption algorithms than straight hash algorithms).
And the compiler - with C and C++ at least - is free to optimize in ways that introduce timing variations. Which is what sparked this conversation in the first place. So even if your source code doesn't take data-dependent time, the compiler may make the compiled output take data-dependent time. And there's no way around that in pure C / C++.
char[] entered+_hash = ...
char[] password_hash = ...
for (int i = 0; i < entered_hash.length; i++)
if entered_hash[i] != password_hash[i]:
return false;
return true;
I take a standard password dictionary and hash everything. I arrange it into a Trie or somesuch by the hash.
I start trying passwords. Specifically: I try passwords where the first character of the hash is different. So, for instance, with SHA256, I try:
12345 5994471abb01112afcc18159f6cc74b4f511b99806da59b3caf5a9c173cacfc5
abc123 6ca13d52ca70c883e0f0bb101e425a89e8624de51db2d2392593af6a84118090
computer aa97302150fce811425cd84537028a5afbe37e3f1362ad45a51d467e17afdc9c
123456 8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92
1234 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
a1b2c3 4f32044a655f32e8528edea64dbfd11cba810b8790e6e6e23d28ad3a75980734
xxx cd2eb0837c9b4c962c22d2ff8b5441b7b45805887f051d39bf133b583baf6860
test 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
carmen f3c2ce176290b0c384cb4881eb714f2db58f630c33863d91c9bedf58d36007db
mickey 33c614ca3cf78827a85dc0d8d06bfcf8c4d923fd23c813acd50b80ed2d4d4fb3
secret 2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b
summer e83664255c6963e962bb20f9fcfaad1b570ddf5da69f5444ed37e5260f3ef689
ranger dbc4a04327176e6577b4da46df04564150053960eba5d89587dad1f76a818d80
letmein 1c8bfe8f801d79745c4631d09fff36c82aa37fc4cce4fc946683d7b336b63032
mindy 7376c22801fbd6e01009830a70028820f280958165e6d3c2bac9683dab28feb7
bear bc98bb50e8094b2ac3ceb90ba2512587c0513cd294a07efcfdcf467198da6266
Note that this can also turn an online brute-force attack into an offline brute-force attack with a small online component. (The only difference being instead of a password dictionary, you brute-force for hashes with the known bits.)
Note that a salt - if the salt is never leaked - prevents this attack.
(Except that if you have an account yourself you can do a timing attack against your own account to try to figure out the salting scheme!)
--------
If the password hash itself takes data-dependent time... There are plenty of ways to go from that to breaking passwords. I could elaborate if you wish.
Sure, assume that the hash takes data-dependent time, but that's the only vulnerability. I can see that this might reveal password length, but not easily beyond that. How does it work? Does SHA256 with salt take constant time?
In general, what is the most secure password scheme if you're looking to prevent timing attacks? Do you need real-time guarantees? You have enough material for a nice "evolution of secure password authentication" article here, if you ever wanted to write it up.
As long as the salt has sufficient entropy, this isn't a problem. So instead of generating the salt from the username / etc, you use a random salt and store it.
> How does it work?
Effectively, by leaking internal state of the cypher / hash through timing variations. The most common ways of doing so are either through data-dependent table lookups or through operations that may be microcoded or otherwise take variable time (multiplications, rotations sometimes, divisions, modulo, squaring).
See, for instance, http://cr.yp.to/streamciphers/leaks.html - although note that this is dealing with stream cyphers not hash functions. In particular, the linked paper describes an effective timing attack against AES by taking advantage of processor cache effects on a data-dependent table lookup. I'd give it a read - it's quite interesting.
SHA256 is pretty good w.r.t. being close to constant time for a fixed input length. Not perfect, but meh. It uses bitwise xor and and, rotates, shifts, and addition, none of which are generally variable-time (although note that on some platforms rotates are variable-time).
For most things, SHA2, by which I mean the newer variants, works reasonably well. In particular, you store SHA2(password xor random_salt xor pepper) and discard the original password. Store the salt in the database with the user, and if you want to get really fancy you embed a single random value ("pepper") in the application code - this is a kind of last-ditch effort to hopefully prevent user passwords from being leaked even if the database is leaked.
If you really want to get fancy, you also embed a couple "canary" accounts (random made-up accounts) in your database, with a passive device on the network that screams bloody murder if any of those accounts ever get successfully logged in to.
However, that being said, that doesn't really answer your question.
A couple things:
1) You don't want to use SHA, generally. You want to use a proper KDF (key derivation function). Why? Standard hash functions are designed to be fast and not take much memory. Which means it is a whole lot easier to crack.
2) If any of the user authentication is in a language that you cannot disable optimizations in, and you cannot look at the assembly code coming out, you cannot prevent timing attacks. You may be able to mitigate them, but that is all.
3) In general, if a KDF / hash function doesn't use any data-dependent table lookups / pointer chasing / control flow, and doesn't do any complex functions (multiplication, etc), it's probably relatively safe from timing attacks. Otherwise... Not so much.
4) Theoretically, you need cooperation of the kernel, etc, to truly be safe from timing attacks. Among other things, context switches could leak information. In actuality... It's definitely possible but I don't know of anyone who has made it work.
Anyway, my curiosity is satisfied for now, but thanks again for sharing, and keep posting about this stuff.
if userToken != token {
return false
return true
The code is simpler, and the edge case is covered.
Also, unless you're familiar with how Go implements string comparison you don't know if it's exploitable in other ways like timing attacks.
Valve's failure was in testing, not language choice.
Also, why not just return userToken == token?
Expecting the go builtin functions to be correct is a pretty safe bet. Used by thousands of people and built to stop problems like buffer overflows, vs something you wrote yourself.
Using a popular library in a language with unsafe builtin types would achieve a similar effect, as long as the library was code reviewed, etc, but the point is that safer languages don't require you to take that extra step. Use them idiomatically and entire classes of exploits will not be possible through your code.
As for timing attacks, if you are making cryptographically sensitive code you really should be using a crypto library and not anything you made yourself.
Formal code reviews. Longer pipelines between checkin and deployment. Penetration testing during pre-release. Better QA, both manual and automated. Better security policies in general. And so on.
Making a change to security related code should trigger a process that represents and avalanche of attention. There should be a shit-ton of scrutiny on any such change. The fact that something this simple wasn't caught is indicative not that "nothing can be done" but rather that most security related code today is handled in an amateurish way by teams who barely care about the consequences of their actions.
Now I can imagine, if you're not a software-tester by heart, that you'd maybe try to "win" the first or two tries, out of habit. I'm not a professional tester, just a coder, and reading the aforementioned article, I also first tried 3/6/12 and then some arbitrary increasing sequence, before catching myself and realizing if I want to figure out the rule I need some negative examples.
Is this something you need to be a programmer to realize?
Or maybe you need to have a "scientific" mind or something?
I'm going to try this on some of my friends, see if I can figure it out.
I expect a big part of it to be some psychological barrier against "failing" or getting "no" as an answer, especially if you're being put on the spot about some math-related puzzle. Many people feel uncomfortable with maths and perhaps fear giving a "wrong" answer and appearing "stupid".
But "fear of maths" isn't what I'd be testing for, it's "willingness/realization to try an experiment with an (expected) negative outcome".
So I'll make sure to formulate the problem in an appropriate manner, just like the guy in the video did, that the goal is to figure out the rule, not to finish the sequence. Try to make them comfortable, but not as far as saying "It's okay to ask me about a sequence that does not follow my rule", because that would obviously bias the experiment.
Though I wonder now, there's some really interesting studies to be done (probably many already have been done), what if the puzzle is about some other rule for a sequence of three, that doesn't have anything to do with numbers?
Say the rule is "objects of increasing size", but the (similarly misleading) example is bicycle / car / train.
Testing the negative is something that should be fairly routine in a scientific-testing mindset. For instance, medical experiments testing both placebos (negative) and medicine (positive) and looking for differences.
Come to think of it, I might be making this mistake but for non-boolean functions. I try to always have tests that pass in interesting values, but maybe I should consciously also try to have tests that get back interesting values. For example, when testing a classifier I should make sure all the classifications are possible. Or, when testing some mathematical function implementation, I should have tests with inputs that cause the result to be exactly -1, 0, 1, and 2 (if applicable).