OAuth, OpenID Password Crack Could Affect Millions

CWmike writes "Researchers Nate Lawson and Taylor Nelson say they've discovered a basic security flaw that affects dozens of open-source software libraries — including those used by software that implements the OAuth and OpenID standards — that are used to check passwords and user names when people log into websites such as Twitter and Digg. By trying to log in again and again, cycling through characters and measuring the time it takes for the computer to respond, hackers can ultimately figure out the correct passwords. This may all sound very theoretical, but timing attacks can actually succeed in the real world. Three years ago, one was used to hack Microsoft's Xbox 360 gaming system, and people who build smart cards have added timing attack protection for years. The researchers plan to discuss their attacks at the Black Hat conference later this month in Las Vegas."

Comments

Add a random delay

[clone53421]

n/t

Re:Add a random delay

[Enleth]

No, a random delay just makes it harder for an attacker to determine the nect correct character. The exact theory behind eliminating the random factor eludes me, but several smart people found a way and it's supposedly correct.

I think the proper way is to "pad" the time so that it's constant. Say, if the password checking algorithm can take from 50us up to 600us, pad it to 1500us (safety margin!) with as much precision as posiible. There might be other code paths to pad, too, such as the one that fires when there's not even such a user, but you still want to display the "wrong password" message, as some systems do.

Re:Add a random delay

[crow]

Not good enough. A random delay will add noise, increasing the number of attempts required, but will not break the attack vector.

What is needed is to insure that the algorithm will respond in the same time when a match fails, regardless of how close the match is. If this were a simple string comparison, you would need a function that compares every character in the input to a padded version of the password, not one that stops at the first mismatch. In most cases, that same approach can be extended to cover more complicated situations.

Re:Add a random delay

[Anonymous Coward]

will "random delay" improve things much? you'd have to have a small upper bound for the delay (pausing for a year
is not likely to carry much favour) - and on most machines, the granulative of 'delays' is limited to 1/100s or 1/1000s.
Surely, given enough iterations, you could quickly average out the delay factor?
Would it not be better to just return results after a fixed elapsed time from the moment the login attempt began? Then
no information seeps out.

Re:Add a random delay

[Mr. Spontaneous]

What about having a strcmp that compares strings using a randomized series of indexes?

E.g.

compare position 4, then 1, then 3, then 10, etc.

Re:Add a random delay

[wall0159]

exactly. A random delay is merely adding noise to the signal, not removing the signal altogether (in the way that using a consistent delay does)

Re:Add a random delay

[maxume]

That still leaks information about the characters used in the password.

Re:Add a random delay

[betterunixthanunix]

The exact theory behind eliminating the random factor eludes me, but several smart people found a way and it's supposedly correct.

It is fairly basic and necessary to pull off the attack (i.e. because this is being done over a network). Let's simplify things and suppose that the comparison is performed bit-by-bit rather than byte-by-byte; we want to determine if a particular bit is a 0 or a 1. We'll take 1000 measurements when the bit is a 0, and 1000 when it is a 1, and then take the average of the delays in each case. Invoking the law of large numbers, we can conclude that despite random noise, the average of a large number of samples should tend towards the expected value -- effectively, the noise will be removed (or more precisely, the average value of the noise will be added to both the 0 measurement and the 1 measurement, which is no different than just having a slower computer on the other end).

Now, for this to work properly, you need a large enough number of samples. The larger the range of random delays, the larger the number of samples will have to be. This creates a fairly typical security trade-off: too large of a range, and your users will be angry because they have to wait too long to log in, and too small of a range means that attackers have an easy time cracking passwords.

A better solution is to have a constant delay for every password check, regardless of whether the password is correct.

Re:Add a random delay

[something_wicked_thi]

That makes sense. If you have a 300us processing time for a particular incorrect password and you pad by 1000us +- 500us in all cases, with a uniform distribution, then it's relatively easy to guess, with known confidence, how long the real processing took, since the average of multiple attempts will come out to 1300us. moe generally, adding a random sleep with any known distribution is doomed to failure.

The easiest way to do this is to define a time, X, that is longer than all expected processing times. Then you force all operations to take exactly X time.

Re:Add a random delay

[Michael Kristopeit]

uh, the "signal" IS the amount of delay. adding "random delay" is not "merely adding noise"... it IS removing the signal altogether. the amount of delay caused by the password check and the amount of delay randomly added can NOT be differentiated.

i agree that for login, a consistent delay coupled with a delay status screen is the most usable solution.

Re:Add a random delay

[XanC]

No, the signal is the amount of time it takes to do the password comparison, and the noise is the random amount of time on top of it.

To circumvent: try each password 100 times. It'll become clear what the actual time to compare the password is.

Re:Add a random delay

[clone53421]

My idea of a “random delay” isn’t quite a random delay but rather more of a “pad to a random length”. I.e. if the operation takes between 50-600us, pick a random length between 1000-2000us, start the timer at the beginning, call the routine, and when all is said and done just go to sleep until the total elapsed time reaches the random value you initially picked.

You are correct in that simply delaying for a random amount of time merely blurs the window for detection.

I.e. if you simply added 0-1000us and the routine took 50us, it now takes 50-1050us. However, if you repeat the same input a few hundred times, the average time will converge to about 550us, whereas a call that took 500us will converge to 1000us. You only made the attack take longer.

If you pad to a random value between 1000-2000us, no matter how many times the same input is repeated it will just converge to 1500us, giving the attacker no knowledge of the time taken to check the password.

The easiest way to do this would probably be to use two separate threads: one thread delays a random amount of time then return the result, the other thread checks the password and stores the result in a shared memory location. Just ensure that the password-checking thread will always finish before the delay-then-return thread does. This way the amount of time you actually delay will not depend at all on the amount of time taken to check the password. However you would need a fairly good understanding of the architecture so as to make sure that the two threads would not be able to interfere with each other in a way that would contaminate the randomness of the delay length.

Explaining all of that took a while, though, and I needed to hurry to get my first post. ;)

Re:Add a random delay

[Eternauta3k]

the amount of delay caused by the password check and the amount of delay randomly added can NOT be differentiated.

Take a bunch of samples, average them.

Re:Add a random delay

[Anonymous Coward]

what if the delay is a function of the password? though fixed time seems to be a better solution

Re:Add a random delay

[clone53421]

Not just a random delay, per se. You are absolutely right.

To avoid contaminating the random delay with a fixed bias (which can easily be determined by running the same query enough times), the timer has to start at the very beginning, delay for longer than the password-checking algorithm will ever take, then return the result after the preset random length of time has elapsed.

I.e. wrong:

    Verify + Random = Result

Result depends on Verify. You just have to average out Random by repeating it enough times. You’ve contaminated your randomness by biasing it with a fixed number that depended on the input.

but correct, and more easily expressed in a multi-threaded sense,

    Thread 0: Verify
    Thread 1: .....Random..... + Copy result from finished Verify = Result

Result does not depend on Verify. Random just has to be long enough to ensure that Verify will always complete.

Re:Add a random delay

[minor_deity]

In that case you are doing significantly more work then you need to, just to spoof timings so that your attacker will think you are vulnerable to a timing attack. Better just to take constant time and be done with it.

Re:Add a random delay

[clone53421]

Taking a constant amount of time is likely just as hard as taking a random amount of time as I described. The only difference is that you are padding to a fixed number instead of a random one.

Re:Add a random delay

[Michael Kristopeit]

No, once the random amount of time is added, it will never become clear what the actual time to compare the password is.

you're going to run each password 100 times, and then what, average them? i don't think you understand what "random" means. if the person who implemented the added delay always made it 1-2 times the average comparison time, creating maybe only a few 1000 potential measurable delay values, then yes, your simple circumvention might work, but i'm assuming the person who implements the delay to counteract the attack would be smart enough to do it right, in a method that could never be reverse engineered. the delay would have to have significant range relative to the min and max comparison times.

Re:Add a random delay

[micheas]

will "random delay" improve things much? you'd have to have a small upper bound for the delay (pausing for a year
is not likely to carry much favour) - and on most machines, the granulative of 'delays' is limited to 1/100s or 1/1000s.
Surely, given enough iterations, you could quickly average out the delay factor?
Would it not be better to just return results after a fixed elapsed time from the moment the login attempt began? Then
no information seeps out.

A random delay is non-trivial and expensive to implement. (/dev/random is generally blocking, and does run out of entropy)

An approach like the following pseudo code would help:

ReturnErrorTime = now() + 2 seconds;

if FunctionCheckPassword() == false:
    return LoginFunction at ReturnErrorTime;
else:
      continue;

Re:Add a random delay

[Michael Kristopeit]

Take a bunch of samples, average them.

if i make the added delay anywhere from 0 to 100,000 times the average comparison time, and make the delay a function of the comparison time, and create multiple delays for each login attempt, then define "bunch". you'll never be sure of the value, you'll just be getting closer to a value of the function of the comparison time used to create the delay. the original comparison time can NOT be differentiated.

Re:Add a random delay

[clone53421]

Yeah, that was basically my thought, but instead of a constant X you use a random number that’s guaranteed to be longer than all expected processing times.

In my haste to get first post I couldn’t think of any way to express that quickly, but yeah.

Re:Add a random delay

[Anonymous Coward]

Yes, you're going to run each password a bunch of times and average them. Are you completely stupid or what? The average of random data converges to a fixed value. Adding random noise to the same value over and over merely biases the average by the average of the random noise over time.

Open any image in GIMP. Add random RGB noise. Be generous, go for uncorrelated independent RGB at 1.0 (i.e. ±255) on all three channels. Save the picture as noise-1.png.

Open original image and repeat. Save it as noise-2.png. Repeat through noise-5.png.

Now average them: Open noise-1.png. Then open as layers noise-2.png through noise-5.png. Set the opacity on the 2nd bottommost layer to 50%, next up 33.3%, 25%, 20%. Observe.

The result will much better resemble the original image than any one of the noisy image did. You absolutely did not destroy the signal (image), you just added noise to it.

Re:Add a random delay

[Stan Vassilev]

Take a bunch of samples, average them.

Sounds easy. Since the researchers apparently said Python/Perl/scripts and so on are easier to hack than C++, let's take typical factors in script execution.

You have an ASM-level operation that takes nanoseconds, and you have the following factors that take a random amount of milliseconds (millions of nanoseconds):

1) garbage collection 'jitter'
2) dynamic optimization of runtime (tracing, JIT, caching) and so on 'jitter'
3) parallel execution of thousands of tasks per second jitter (you measure just one random call of these at a time, you have no idea how loaded the server is or what's the structure of the tasks queue)
4) I/O calls in parallel delays jitter (same as 2. except much slower)
5) network jitter

Also I'm probably missing another 10 to 20 factors I could list above.

So, how many millions or billion of calls would I have to make to be able to "average" all those, factor them out and time some ASM-level operation in there?

And even once that's done, all I have is whether one character possibility I sent is wrong or not. Repeat for every printable ASCII character, and every single character of the password.

And still, you say, it's possible, though it'll take billions of calls.

Well, most services would deny you further checks after the 10 or so wrong logins and lock the account. Good luck using a timing attack on that service.

Re:Add a random delay

[Michael Kristopeit]

we are not talking about arrays of pixel values in channels of RGB, we are talking about a single value of a measurement of time. "resembling" a single value is not possible.

how about this... create a value. now add a random amount of value significant in range relative to the original value... now add a random amount of value as a function of the original value...

you can't differentiate the original value with ANY certainty.

Re:Add a random delay

[An Onerous Coward]

You're making it a lot harder, true. But you seem to be claiming that it makes it mathematically impossible. Which it doesn't, but it's probably close enough.

According to the article, the attack uses algorithms to weed out network latency. So if you add much of that randomness back in, in a way that they can't factor out, you're probably good.

Still, it seems to make more sense to just require the comparison to always make exactly 64 comparisons. That's faster and more certainly invulnerable than adding between 0 and 100000 comparisons.

Re:Add a random delay

[BitZtream]

I think the proper way is to "pad" the time so that it's constant.

Which is what anyone with half a clue about writing secure authentication systems has done since at least 70s.

When an attempt fails, you pause for a standard amount of time.

The attacker then doesn't know if the password is good or bad until the system tells them. You can't assume a password is bad just because it doesnt' return instantly due to random system load. You also don't get any info from the failed attempt because every failed attempt is at least X seconds long, longer under high load but never shorter.

A failed authentication for ANY REASON behaves THE EXACT SAME as ANY OTHER REASON so attackers get no data from failed attempts.

This isn't a new discovery or anything, its just standard operating procedure for anyone with a clue about authentication systems.

Re:Add a random delay

[PitaBred]

If a single IP is trying a "bunch" of bad passwords, I'd think they'd be a candidate to not let do that. Especially if they're doing it more rapidly than a person could. Depending on the system and users you could set the limits.

Re:Add a random delay

[Michael Kristopeit]

yes, but then you telegraph to the attacker that a time based attack is not possible. it seems to make more sense to require the comparison to always make exactly 64 comparisons, and then also add a random number of additional comparisons to waste more of the attackers resources.

Re:Add a random delay

[Anonymous Coward]

Taking a constant amount of time is likely just as hard as taking a random amount of time as I described. The only difference is that you are padding to a fixed number instead of a random one.

Nuh-uhn.... your way makes you have to run "rand()" and then assign a valuable to a variable. That's more...

just sayin'....

Re:Add a random delay

[Anonymous Coward]

Or measure another side channel (like power draw, cache misses, etc). Random padding indeed isn't a good idea. At all.

Instead, you design the comparison routines (and anything else that touches the secret data) to take constant time and
effort, don't do conditional branching EVER, and have the same cache behavior for match and no-match. OpenSSL does this. SSH does this. Anything written by people with a clue, does this. Web languages cannot do it, because the people writing the underlying engines don't have enough of a clue to do this. C can do it, but only if you *REALLY* know your compiler and what you're doing, or it will optimize away all of your effort or worse, it will do something idiotic that will leak state. Other languages, unless they have secure primitives geared for cryptographic data processing, are simply unable to do it. Bytecode (think JIT) can be just as troublesome to secure as C being compiled by a completely unknown optimizing compiler.

Anyway, XOR can compare for equality in constant time, and the way it is implemented in just about every silicon out there, the power draw signature is well within the noise floor.

Re:Add a random delay

[Michael Kristopeit]

so let's say you do it like SSH with an ensured fixed time, and then on top of that add a random delay. could an attacker now determine anything they couldn't have before? obviously, no. but now you've hinted to the would be attacker that a time based attack might be possible. so using a random delay you get the exact same security, and potentially waste more of your would be attackers resources. how is that not better?

Re:Add a random delay

[ChatHuant]

This is not a new attack, nor is this naive suggestion a new (or good) one. It won't work, because the attacker will simply retry a number of times with the same parameters and average the random delay out.

Re:Add a random delay

[ergrthjuyt]

this is purely academic, but said padding would not be entirely consistent across different calls to the sleep() method since the os only guarantees a minimum sleep time, not necessarily an exact sleep time. This can happen if the thread or process is switched out and the thread is not made active again until after the minimum time has already elapsed.

That said, this delay-padding method should effectively reduce the delay to random statistical noise rather than any pattern that can identify the results of the string comparisons, so it should work regardless.

Re:Add a random delay

[clone53421]

GODDAMN. You really ARE that stupid.

We are NOT fucking talking about a SINGLE measurement of time.

We are talking about hundreds - possibly thousands - of "value", plus your random number. Guess what. Your stupid random number averages out to its median over about 1000 attempts. Meanwhile the CONSTANT value remains CONSTANT and as only the RELATIVE position of the values was important, we can compare it to OTHER attempts and determine which was faster REGARDLESS of your stupid random number.

You average it out.

No, I do not expect you to understand that any more than you understood the more helpful (and less insulting) version. You are an idiot.

Re:Add a random delay

[clone53421]

You are talking about speed, which is irrelevant because we are already purposefully slowing it down.

I am talking about programming complexity.

Re:Add a random delay

[tomhudson]

... except that the time to sprintf the string into the buffer is a function of the original string's length ... ditto for the password you want to compare it to. So they can very quickly determine the length of the stored password - not a good thing.

Of course, how long does it take to do a snprintf of '12345'?

Re:Add a random delay

[inflamed]

You are also wasting your own CPU cycles. Just make it constant and lock them out after a set period of time.

Re:Add a random delay

[inflamed]

Wasting your own resources is not better. Just have it slow down the rate of password attempts exponentially as the number of attemps increments.

Re:Add a random delay

[Anonymous Coward]

No, a random delay just makes it harder for an attacker to determine the nect correct character. The exact theory behind eliminating the random factor eludes me, but several smart people found a way and it's supposedly correct.

I think the proper way is to "pad" the time so that it's constant. Say, if the password checking algorithm can take from 50us up to 600us, pad it to 1500us (safety margin!) with as much precision as posiible. There might be other code paths to pad, too, such as the one that fires when there's not even such a user, but you still want to display the "wrong password" message, as some systems do.

Why pad it to 1500us? why not 1503us? or 1567us?
Hell why not pad it to a random time between 1500us and 2000us to fuck with the attacker, after all as long as you are padding the time you are giving nothing away.

Re:Add a random delay

[Michael Kristopeit]

1) submit password
2) measure delay of response.

that's it.... the delay is a single measurement of time that the "timing-based attack" is based on.

if every single individual measurement of time was obfuscated in some way that created a fixed delay plus a random delay as a function of the original delay, then the whole or the average of multiple samples of the whole is irrelevant.

billions of attempts would still not get close enough to an exploitable level of confidence.

if the hidden value is irrelevant, and the averages of samples reveal the hidden value... then the averages of samples is also irrelevant, but you've wasted the stupid attackers time in believing that a timing-based attack might be possible.

you are as dumb as every other youth to attend the kansas bible camp.

completely ignorant.

Re:Add a random delay

[Anonymous Coward]

If just obfuscating values with other random values worked, we wouldn't need to design complex hashes and salts. You are sort of ignorant thinking that a bunch of people who break into computers wouldn't be able to use computers to perform attacks and calculate out an average of random timing (btw what are you going to use to seed them?). You also thing that youre wasting their time, but time for them is infinite and billions of requests are possible.

Juat because it's a "timing attack" doesn't mean they have to rush it. Obviously they had to take some time and calculate the averages just to get the accurate timings for the attack.

Re:Add a random delay

[Anonymous Coward]

You can always use both method. Pad out the time and add a random ammount on top, making attackers scratch their head before they move on to the crowbar.

Re:Add a random delay

[clone53421]

No, you retard, if the fixed delay was identical plus a random delay that wasn’t identical, you wouldn’t even need billions of attempts. You don’t care WHAT the fixed delay is, you only care whether it’s more or less than the fixed delay of another.

I.e.

is A > B?

Is A + random > B + random?

Average it out and the “random” goes to a constant:

Is A + R > B + R?

Yes or no. It’s that simple.

You are an idiot.

Re:Add a random delay

[clone53421]

Yes, that was basically my initial thought when I said make it a “random” delay. If you contaminate the randomness by adding the length of your verification subroutine, it’s no longer random. A good way to describe it, as you stated, is to pad out the time (eliminate the variance of your verification subroutine) and then add a random amount on top (easy enough to do at this point, and making attackers scratch their head a little).

Re:Add a random delay

[Michael Kristopeit]

the constant the averages "goes to" (i'm not familiar with that mathematical phrase from when i earned a mathematics and computer science degree from the university of wisconsin... i assume you mean "approaches") is the fixed delay. the only point of adding the extra random delay was to not telegraph the fact that a time-based attacked might be possible.

you are the worst kind of idiot. an ignorant hypocrite. just like all the other retards at the kansas bible camp, stephen alongi.

stephen alongi makes pedophiliac homoerotic comments about muslims and their beliefs. he is an instigator. an agitator. completely worthless. he doesn't like people to know that clone53421 is him. clone53421 is stephen alongi. a retard who is too stupid to know when he is wrong, and when it is pointed out to him, he is too stupid to acknowledge it. an ignorant hypocrite. a product of the kansas bible camp. a counselor there. do you want to leave your child with someone at the kansas bible camp who spends their time spouting pedophiliac homoeroticism on the internet?

you are NOTHING

Re:Add a random delay

[Michael Kristopeit]

i agree that the most usable solution is a fixed delay, coupled with a delay status splash.

my comment was that an added delay CAN be added in a way that can not be reversed engineered through averaging... and that doing that might tempt a would-be attacker to spend their time attacking a pathway that is exploit proof. attackers may have infinite time, but if they spend most of it on fruitless efforts, then less successful attacks would happen. how is that not more secure? billions of requests are certainly NOT possible. after many failed requests, the attacker should not be allowed to have their passwords checked, or have an exponentially increasing delay between failed attempts. all of this is extremely basic and standard security concepts that have been around for decades. OAuth and OpenID are bad for many other reasons than a claimed vulnerability to timing based attacks that has not been demonstrated, and would not work on any system that limited access after failed login attempts (pretty much everyone).

Re:Add a random delay

[Anonymous Coward]

This is the part where I ask you why I never got any DMCA takedown notice / cease and desist letter in the mail after you clearly indicated that you had mailed one. You do realise that threatening someone with a takedown notice without actually issuing one can be a felony?

Re:Add a random delay

[Michael Kristopeit]

do you own geeknet, inc. or the image hosting company? why would i send the takedown notice to the offender and not the people capable and responsible to take it down?

jesus would be ashamed you act so stupidly. you are NOTHING.

Re:Add a random delay

[Anonymous Coward]

Eh, whatever the shit you said you were sending to me. Remember? And I quote: that it is "in the mail".

Re:Add a random delay

[Anonymous Coward]

stephen alongi makes pedophiliac homoerotic comments about muslims and their beliefs. he is an instigator. an agitator. completely worthless. he doesn't like people to know that clone53421 is him. clone53421 is stephen alongi. a retard who is too stupid to know when he is wrong, and when it is pointed out to him, he is too stupid to acknowledge it. an ignorant hypocrite. a product of the kansas bible camp. a counselor there. do you want to leave your child with someone at the kansas bible camp who spends their time spouting pedophiliac homoeroticism on the internet?

What the hell is this shit? Are you guys two mortal enemies locked in eternal message board battle?

Also, BTW, "goes to" is an often used phrase in math. I guess you didn't make it past undergrad and use that experience to inform your flaming here.

Re:Add a random delay

[Michael Kristopeit]

... it was, retard. the image was removed, retard. message received, retard. remember? the image you stole from my archives and redistributed. you are a thief. you spew pedophiliac homoeroticism on this website. you attempt to hide the fact that clone53421 is you. stephen alongi... a counselor at the kansas bible camp. you agitate the muslims because they ask you not to. you are an ignorant hypocrite. you are also a cowardly idiot. and obviously stupid.

Re:Add a random delay

[Michael Kristopeit]

it would never be used to describe a function that only approaches an average, and never makes it "TO" settling on that value. the averaging function doesn't "goes to" the value... it approaches it.

stephen alongi is a pedophiliac homoerotic anti-muslim agitator. he is only here to spew his ignorance.

i guess you got to 5 letter words and 2 dimensional functions at grad school. i also understand how multiplication works and that the sine function is curvy. if i didn't make it past undergrad, how could i be here to post this? still paying people to explain things to you? for $500 i'll teach you why you're an idiot.

Re:Add a random delay

[Anonymous Coward]

Who clone53421 is in real life is only relevant to bullying assholes such as yourself, as it is useful in your primary argumentative style of bullying and ad-hominem, bringing up completely irrelevant things that you seem to think help to discredit the person you're arguing with.

Looking at the posts here, I notice that your retarded shite was so ridiculous that you actually managed to pick up a Funny moderation. Several of the people who were pointing out that you're wrong, in contrast, were moderated Informative and Insightful. If clone53421 is correct about delays and randomness, his real-life identity, places where he counseled, or any of the other stuff you are claiming is hardly relevant.

Following in line with your theme of stupid ad-hominem and unwarranted bullying and aggressive, asshole-like behavior... how has your dog-fucking slut wife Rachel been lately? Any more farm animals been fucking her? Maybe next you should try for kittens.

You are scum.

Re:Add a random delay

[Anonymous Coward]

This image?

Looks to me like it's still up, good thing the link was still in my web history.

Re:Add a random delay

[Anonymous Coward]

and for $50 your wife will give me a blowjob.

you are NOTHING.

Re:Add a random delay

[Michael Kristopeit]

i am RIGHT.

Re:Add a random delay

[Anonymous Coward]

stephen alongi's mum sucks me dick for free!

go ask her for one: 6136 Rockhill Rd, Kansas City, MO 64110

Re:Add a random delay

[Anonymous Coward]

go back to facebook, dad. nobody invited you.

Re:Add a random delay

[Anonymous Coward]

steven alongi's mum never invites anyone over... they just show up and she sucks them off. big throbbing dicks in her face. she even sucks muslim dick. my muslim friend went over 3 times last week. steven alongi's mum loves to suck on muslim dicks and let them explode in her mouth.

Re:Add a random delay

[Michael Kristopeit]

no, that was the image originally posted here, that you, without being accused, quickly jumped in and pointed out "Those last two pictures were not posted by me, by the way"... BY THE WAY. and now you would insinuate that the exact opposite of what you claimed is true?

the image that you posted under this account, stephen alongi, was originally posted here which includes this link to the offending image which has since been removed by tinypic after receiving the DMCA takedown notice that you dared me to post after claiming did not exist, and yet now the images have been removed... we'll see who the scummy fucking liar was.

omploader has not been as expedient as tinypic in responding to my legal notices, obviously, and with no person to name in the charges, it is much more difficult to proceed with certain other legal options. are you now claiming that the picture you linked to was made by you and uploaded to the omploader service by you? the only image i have ever accused you of creating was the one you created under your clone53421 account.... but now, after you brought up the topic of images you've posted that i've accused you of infringing upon my copyrights, somehow you think that i'm talking about an image that you denied responsibility for, and know that i responded to your out of turn denial? did you forget that you didn't make that image?

OR are you just too big of a kansas bible camper to post another similar image that infringes upon my copyrights in your name and take responsibility for the consequences?

you are NOTHING

OpenID

[Reason58]

Wait, doesn't slashdot use OpenID?

Re:OpenID

[Reason58]

Wait, doesn't slashdot use OpenID?

hahahah

DISREGARD THAT I SUCK COCKS

Re:OpenID

[DocSavage64109]

Wow. Guess it's no longer theoretical...

Re:OpenID

[roman_mir]

No no, it's all good, good thing /. is not US army though, otherwise Reason58 would be 'honorably separated' from this place in a short while.

Re:OpenID

[something_wicked_thi]

I suddenly wish I hadn't posted in this thread so I could mod up you to offset that troll mod someone lacking a sense of humor gave you.

Re:OpenID

[Anonymous Coward]

Caught me off-guard. I scared everyone in the house with the hysterical laughter.

Re:OpenID

[pangu]

So you say we are supposed to take your advice despite your declared homosexuality?

Re:OpenID

[Anonymous Coward]

Wait, doesn't slashdot use OpenID?

Yes.

Every password can be broken

[Some.Net(Guy)]

It's just a matter of time. Anyone seen Swordfish?

Re:Every password can be broken

[Kepesk]

Agreed. I've never completely trusted the various efforts to create online identification systems, though I'll admit that it wasn't because of this possibility. I guess I'll just continue not using them.

yikes!

[Irick]

hope a preventative measure gets added soon, OpenID is a great idea, i really like only having one login, but still, tightening up the corners is important ^^

Re:yikes!

[icebraining]

If this breaks the passwords, maybe https://certifi.ca/ is secure?

With a certifi.ca account, you can log into thousands of sites around the Web without needing a password. We use client-side SSL certificates to give you a secure authentication service based on public-key encryption.

Who doesn't hash/encrypt passwords?

[MankyD]

"On some login systems, the computer will check password characters one at a time, and kick back a "login failed" message as soon as it spots a bad character in the password."

If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point, since the place that fails to match in the string will change. Are there still sites out there that don't do this? Really?

Re:Who doesn't hash/encrypt passwords?

[TubeSteak]

If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point, since the place that fails to match in the string will change.

This might be a stupid question, but how do they check a password one character at a time unless they're saving the password in plaintext or some other reversible method?

Re:Who doesn't hash/encrypt passwords?

[betterunixthanunix]

You'd be surprised. Salting and hashing passwords seems like common practice, but most programmers have minimal security training (yes, even those programmers who implement password based authentication systems) and may fail to realize the significance of not hashing.

Now, the fact that open source projects have this problem is a bit disturbing...

Re:Who doesn't hash/encrypt passwords?

[mattventura]

It could be extended to hashes, to a lesser degree. If you know the hashing algorithm used, you could use it to figure out where the hash does not match and ultimately use it to determine the hash, which can then be cracked easily if the password is weak.

Re:Who doesn't hash/encrypt passwords?

[betterunixthanunix]

They check the hash one character (or word, quadword, whatever) at a time.

Re:Who doesn't hash/encrypt passwords?

[MankyD]

I don't think a reasonable password hashing algorithm works like that. If I change one character in the password (any single character) the entire hash could/should change. You can't look at it and say "well, 90% of the hash matches, let's tweak it a bit more."

Re:Who doesn't hash/encrypt passwords?

[crow_t_robot]

IDWSLFOID (I don't write security libraries for Open ID) but I would guess that it's because they use a stream cipher instead of a block cipher.

Re:Who doesn't hash/encrypt passwords?

[Shimbo]

This might be a stupid question, but how do they check a password one character at a time unless they're saving the password in plaintext or some other reversible method?

I think that's just a slightly sloppy writeup. You probably get to know individual bytes of the hashed password. It's likely that you can vastly reduce the key space for an attack by this method, with carefully chosen plaintext. No, you probably don't get individual plain text characters, one at a time, like in a bad movie.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

here is a solution I implemented a little while ago:

public boolean isUserAuthenticated(User user, String password) throws TCAppException {
    String encryptedPassword = Encryption.encryptString(password, AppConstants.AUTH_KEY);
    if (user.getPassword().equals(encryptedPassword)) {
        return true;
    }
    return false;
}

User object contains password that is encrypted, the password that is passed as 'password' from the login page is also encrypted with the same algorithm Encryption.encryptString(...) the hash values are compared instead of the clear text passwords.

This serves 2 purposes:
1. The password is never actually stored in the system, only its one-way hash.
2. It prevents this particular attack from working.

Re:Who doesn't hash/encrypt passwords?

[EsbenMoseHansen]

No, since A) the hash will be salted and B) changing one character gives a completely different hash result (just try running md5sum on some strings). E.g:
password 286755fad04869ca523320acce0dc6a4
passwore 530bbcd6551386c86cbc0ebc6b007cc4

Re:Who doesn't hash/encrypt passwords?

[Abcd1234]

If that's true, a timing attack is useless, as the place where the comparison would fail is random, and certainly doesn't provide information about how to tune the input to get closer to the "correct" answer.

Re:Who doesn't hash/encrypt passwords?

[Stewie241]

http://www.computerworld.com/comments/node/9179224#comment-588733

That comment there is insightful. This has nothing to do with passwords, it has to do with SSO keys. I was confused originally because OpenID says nothing about how systems store or verify passwords, so it wouldn't make sense to check in that manner.

Re:Who doesn't hash/encrypt passwords?

[Qzukk]

If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point,

You risk making the problem WORSE, especially if you compare the ASCII (hexadecimal) representation of your hashes. If I know what hash algorithm you use, I can produce a rainbow table, and attempt to log in 16 times to determine the first hexadecimal character of the hash, 16 more times to determine the second and so on. For md5 (128 bits, 32 nibbles) it would take 512 (16*32) login attempts to find a password from my rainbow table that hashes to the same thing your account did.

If you have a basic (A-Za-z0-9) plaintext password that's at least 9 letters long, it's "stronger" (62*9=558 attempts), and that's without punctuation.

It's true that bytewise comparison of a 128bit hash would take 4096 attempts (256*16) but if you're not going to block me after 100 failed logins, it's unlikely that you're going to stop me after 4000, either.

The answer is either random delay or not short-circuiting test logic anywhere in a login routine. Blocking login attempts after N failures is another good idea.

Re:Who doesn't hash/encrypt passwords?

[betterunixthanunix]

However, it could allow an attacker to determine some part of the hashed password, which the attacker might then be able to crack using his own computers (which can just sit there trying to crack the password without dealing with any other work). This depends on the attacker's ability to do two things:

1. Compute the salt; this is not trivial, and a long enough salt should make this infeasible
2. Compute hashes that begin with a particular sequence; this is not necessarily difficult (certainly not as difficult as computing a collision), but should not be an easy thing to do

Of course, a simpler solution that does not even require those two conditions is to have the delay from a password check be constant (for a given password). Hashing and salting should be a second line of defense, for when a user manages to download the password database.

Re:Who doesn't hash/encrypt passwords?

[mattventura]

changing one character gives a completely different hash result

That's the point. You could theoretically get find out the MD5 assuming it wasn't salted by computing md5's yourself and finding one with the characters you need. For example, I would test md5's with all the possible first characters and find the one that is fastest, then generate a list of password and hash pairs with every possible second character and the first character we found earlier, and repeat for every character thereon. It would be a stretch, and the original password would not be revealed, just a hash, but in theory such an attack could work.

Re:Who doesn't hash/encrypt passwords?

[Bert64]

Windows doesn't bother to salt its hashes either...

What open source systems don't do hashing? Must be pretty niche applications or someone would have contributed a patch by now.

Re:Who doesn't hash/encrypt passwords?

[betterunixthanunix]

It seems that the systems described in TFA were open source, and that they checked plaintext passwords. Maybe I misread something (the article is full of inaccuracies anyway; timing attacks go back much further than 25 years, and reducing the noise added by a computer network is not ground breaking at all).

Re:Who doesn't hash/encrypt passwords?

[adonoman]

Good job not storing the plain text. But there are still problems with your code.

First, if two users have the same password, they will have the same hash stored in the db. If an attacker gets a hold of the list of hashes, it's trivial to generate hashes of a few million common passwords and compare them to the list. In any moderately sized user list, you'll get hundreds of matches. The trick is to also generate a random string of "salt" for each user. Append the salt to the password before hashing, and store the salt alongside the hashed password. Now if two users have the same password, the hashes will still be different, and the attacker will have to run his attack against each user individually instead of against the whole DB. See wikipedia

String encryptedPassword = Encryption.encryptString(password + user.GetSalt(), AppConstants.AUTH_KEY);

Secondly, if your String.equals() function is returning immediately on compare failure, the attacker can still use the timing method to reconstruct the hash of the password without gaining access to your database. Not the worst of attacks, but it does give the attacker more information to work with.

Even better than trying to fix your solution, though, would be to use an authentication library where someone else is handling the crypto and the protocols. It's brutally tough to get right - as evidenced by the fact that libraries built by experts are still having issues.

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

Encryption and hashing are not the same thing. Your statement is confusing the two.

The code snippet you posted would be good if you were using hashing (although it would be better to use a salt as well, instead of hashing just the password).

You seem to be using encryption. The issue with this is that, assuming this is symmetric encryption, anyone who has access to AppConstants.AUTH_KEY can also decrypt your password store. (And if it's asymmetric encryption--which I doubt--and that's the encryption key you're using, are you sure you threw away the corresponding decryption key?)

Bottom line: Your system is better than storing the password in clear text, I'll give it that--but there are flaws that don't exist in the more common salted-hash model. Security Is Hard, and we should encourage use of the more-tested, more-reviewed solutions rather than ad-hoc ones.

Re:Who doesn't hash/encrypt passwords?

[ironicsky]

I'm pretty sure this is easily fixed... Any authentication system I write queries the database for both the username and password at the same time(all passwords stored as MD5 hashes) and only checks to see if a row was returned. If it is, the credentials are correct. If nothing is returned, the credentials are wrong. I never tell the user which was wrong, thats up to them to figure out.

$query = "SELECT uid from users where username='" . $_POST['username'] . "' AND password=MD5('" . $_POST['password'] . "') limit 0,1";

Of course if something is returned I write to another table a session ID and the user's unique ID (uid) which is simply an auto_incrementing # which is row in the DB the info is found.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

That is a terrible auth function. Where is the randomly-generated salt? Where is the expensive hash function, like bcrypt?

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Salt, you are looking right at it.

AppConstants.AUTH_KEY

Somebody getting a copy of my DB and getting the hash keys? That means they have access to my production server and I have bigger issues than some silly thing like them signing in as some user.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

You 'doubt' it's a hash?

public static String encryptString(String toHash, String key) throws TCAppException {
    if (toHash==null || toHash.length()==0) {
        throw new TCAppException("Invalid parameter toHash.");
    }
    if (key==null || key.length()==0) {
        throw new TCAppException("Invalid auth key.");
    }
    String result = null;
    try {
        String s = toHash + key;
        MessageDigest m = MessageDigest.getInstance("MD5");
        m.update(s.getBytes(),0,s.length());
        result = new BigInteger(1,m.digest()).toString(16);
        result = new String(Base64.encodeBase64(result.getBytes()));
    } catch (NoSuchAlgorithmException e) {
        throw new TCAppException(e.getMessage());
    }
}

it's all it does. The 'key' is not really a key, I agree, it's a misnomer.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

As I replied, the AUTH_KEY is actually salt, if you care you can check my reply above to some other doubter.

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

I'm pretty sure you're talking out of your ass. Not to be a prick, but if you're just MD5 your passwords and storing them in the DB, you might as well be storing them plaintext. Yes, MD5 will stop the casual observer who runs a query against your DB (which would be quite easy given your sql-injection friendly coding style - watch out for little Bobby Tables). You're not using salt, you're not using a real hash algorithm (at the minimum it shouldn't be possible to google passwords), but you really should be using something that takes a long time, and isn't easy to crack. MD5 was specifically designed to be blindingly fast to calculate.

Don't roll your own authentication. Just don't. Find a library that's been reviewed and tested, read the documentation carefully, and follow the directions. Crypto is Hard, leave it to people who have nothing better to do than make sure their library can't be broken.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Oh, it obviously returns the result, I cut that out and cut out some test code and added the closing brace by hand here rather than copying all the code.

Re:Who doesn't hash/encrypt passwords?

[EsbenMoseHansen]

Yeah, but the IDEA of using a hash is that it is inreversible, so getting the hash out gives you nothing. Notes that this only works if it is salted.

The attack could still be valid, though, if the hashing occurs client side. I'm guessing that this is what the attack requires (it sound quite plausible that openid involves some kind of cryptographic hash that needs to match something).

Re:Who doesn't hash/encrypt passwords?

[ArsonSmith]

Or a junior admin gave your your /etc/shadow file to a 3rd party compliance auditor who then didn't treat this file with the security it needs.

Re:Who doesn't hash/encrypt passwords?

[adonoman]

1. That's not salt. Yes, it prevents the google attack, but two users with the same password still have the same hash.
2. MD5 is just about the worst hash algorithm you could be using for this purpose.
3. It's not just people outside your firewall you need to worry about. Getting someone's password is a great way to do stuff without getting caught. If you hack a system, and get caught right away, not much damage can be done. If you get a bunch of passwords, you can work all you want for a long time before getting caught.

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

This has another advantage in that its not pulling passwords from the database into the authenticating application's address space. Rather, it allows the database to validate the computed password hash against the user's actual password hash, where it has no choice but to be in memory.

There are some corner cases where this is a real win!

Re:Who doesn't hash/encrypt passwords?

[Pootie Tang]

More specifically "AppConstants.AUTH_KEY" is the salt. But that doesn't appear to be a *random* salt.

Re:Who doesn't hash/encrypt passwords?

[An Onerous Coward]

It looks like you're not salting your passwords. Each user should have a unique salt, which means you'd have to pull them up by username, add the salt to the password, then do the hash.

At that point, you *could* do a second SQL query to check the password. But you already have the user's entry.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

1. That's salt, I am obviously not showing to you how this is formed.

2. MD5 is fine here, there is no security problem with MD5 and the salt that's really different from other hash algorithms.

3. My system has other measures, settings for who is allowed to work from the outside and who is only allowed to work inside the office, only the top management is allowed to work from the outside. Everybody in the office has an account, the difference is in privileges, some people are allowed to modify certain data, some are not.

4. The firewall settings only allow specific IP addresses to connect from the outside.

Re:Who doesn't hash/encrypt passwords?

[An Onerous Coward]

No, but you could send passwords whose hashes match the first n bits of the hash. Use this knowledge to decide which passwords you're going to try. It should reduce the search space tremendously.

Now, if the passwords are being salted, you can't use this technique either, since the hash it's matching isn't the hash you think it's matching.

I guess another approach might be to check the bytes in some random order.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

And you have deducted what the constants file looks like?
Try guess.

It has defaults, but the defaults are overloaded during the start-up of the application from a property file. The property file is placed into the file system and after the start of the application, it is removed from the file system. What is inside the property file obviously is more interesting, thus it is secured physically.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

I obviously meant 'deduced' not deducted.

My constants files are the same always, they have defaults but also search for a specific file on the file system and overwrite itself with that data by reflection (just because it was fun to do).

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

all sorts of things are possible, but what good would /etc/shadow file do, they'd have to have physical access to that database, which is not on the Internet, besides which, /etc/shadow has nothing to do with the application passwords stored in the database.

Re:Who doesn't hash/encrypt passwords?

[bmckeever]

I assume that you can copy and paste, so apparently the article has been updated. It now reads: "On some systems, the server will check a cryptographic signature on a token...".

But the answer to your question is yes, it matters. When the place it fails to match changes, this information is leaked by the response time. This is how an attacker extracts information from random guesses.

Re:Who doesn't hash/encrypt passwords?

[adonoman]

It doesn't matter what the constants file looks like. It doesn't matter if you sample cosmic background radiation to get a random number. It matters that you are using the same salt for everybody.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

True, it is the same for everybody, and that is the only way to keep the passwords stored in the database without having to decode them to compare to the passwords from the sign on screen. You suggest different salt for every different password, then every salt has to be stored as well, it makes no sense.

However you are wrong, it does matter where the salt comes from. It comes from a file that exists only during the start-up of the application and then it disappears.

Re:Who doesn't hash/encrypt passwords?

[jeremyp]

I admire your bravery, posting that on Slashdot.

My username is robert';drop table users;--

http://xkcd.com/327/

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

That you implemented? More like, that you and every moderately experienced programmer's dog has implemented.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

The more I know people, the more I am happy to qualify as a dog.

Re:Who doesn't hash/encrypt passwords?

[Luke Wilson]

AppConstants.AUTH_KEY ? A salt that is Constant through out the App? That is not the same thing as a Random salt for every User.

The whole point of not storing plain text passwords is if somebody gets access to your DB. And in that case the only advantage of using one salt through out is that the attacker can't use a precomputed rainbow table for your hash function with out a salt. Instead they will have to compute ONE rainbow table for the one salt you used. When many salts are used rainbow tables are no longer useful. Just like GP said, two users with the same password will have the same hashed passwords in your DB, because they all use the same salt.

Again, if your not concerned about "Somebody getting a copy of my DB and getting the hash keys," then why are you bothering to hash the passwords?

Re:Who doesn't hash/encrypt passwords?

[spongman]

Secondly, if your String.equals() function is returning immediately on compare failure, the attacker can still use the timing method to reconstruct the hash of the password without gaining access to your database.

i don't think this is true for most (read: any half-decent) hash functions. changing a single bit in the input will radically change the output, and therefore radically change the length of the common prefix.

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

Yes, each user's salt needs to be stored in your authentication store.
This is the correct way to do things.

man 3 crypt

Re:Who doesn't hash/encrypt passwords?

[Anonymous Coward]

Yes, each salt needs to be stored. A salt requires an attacker to brute-force each password individually, so each salt need to be different.

The salt being read from a file doesn't stop it from being the same for each user, so it still doesn't matter where it comes from.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

If 'attacker' got the file with the salt (a physically secured file, that is not stored on the network and that only one admin has) then this attacker is way beyond our normal security procedures.

Salt is USELESS by itself and if attacker got a useful way to use it, it means he is in the app at the code level. If he is that deep, he just as well would be able to see the salt if that was stored in the database, so this entire exercise is stupid.

You either have nothing or you have everything.

If you have the salt, it means you need to be able to use it. The only way to use it is by modifying the production code. If you are that deep, you have access to the database and you'd be able to read the salt from the database if it was stored there.

My way of providing salt at the start of the application and then removing the file is MORE SECURE!

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Yes, but the point is (and I replied below to another AC) is that to be able to USE salt you have to be at the code level, you can't use it at the level of an outside intruder without having access to the installed code.

If you are that deep, in the code in the app server, then you have access to the database server anyway, and if salt was stored in the database, you could then just read it.

This is stupid and less secure than reading salt from a file during application start up and then removing the file and physically protecting it. You think there is only one way to use salt securely, that's because you don't understand how it would have to be used actually to form an attack.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

What's funny is how many comment in this thread that salt should be all different for each password and stored with password information, they comment on this without understanding the purpose of salt at all.

Salt is only useful to protect the encrypted passwords, so if someone got the database and wants to decrypt the passwords. If salt is stored there as well, then how does that make it less difficult to decrypt the password? It makes it easier than what I do: store salt separately in a file and keep the file safe physically outside of the systems.

Salt is like the least useful feature out of all other security features in a system, it helps if someone stole your database, but if that happened in the first place, you have a more serious security breach.

Re:Who doesn't hash/encrypt passwords?

[nahdude812]

Even still, if you can test individual characters of the hash, and can choose passwords with known hashes meant to resolve each subsequent byte, you could reverse engineer the hash in this way - or at least some portion of it before a rainbow table of likely password possibilities allows you to complete the password.

Re:Who doesn't hash/encrypt passwords?

[h4rr4r]

and that kids is why we salt our hashes.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

That is the wrong way to do it. You need to generate a random salt for every single user on the system. Otherwise, someone could generate hash tables to attack it.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

You are confused. The salt is not supposed to be a secret. The purpose of the salt is to make it extremely expensive to crack the passwords.

Re:Who doesn't hash/encrypt passwords?

[JesseMcDonald]

I'm afraid it is you who does not understand the purpose of salt, nor the concept of hashed passwords in general.

The reason that you and the other commentators in this thread cannot see eye-to-eye is that what you are calling "salt" is not salt at all, but rather a private encryption key. You are not storing password hashes in your database, where salt would be relevant. You are storing the actual passwords, albeit encrypted. If anyone were to get the private key you're using—which is relatively trivial if they've already broken into your system, even if the original file is no longer present—they could trivially decrypt all the passwords. The security risk is that many of these passwords will be used for the same account names at other sites, so breaking into one weakly secured system can potentially provide login details to user accounts on many other systems. This is why every book on security tells you to never store the actual password, and rely on hashing instead.

The point of storing hashed passwords is that even knowing the hash (and the salt, if present) will not get you the original password, as the hash is a one-way function. You can check whether the provided password is the one that was originally hashed by repeating the process, but nothing in the database will tell you what the password actually is. However, one weakness is that, without salt, an attacker can precalculate huge tables of common passwords and their hash values, at great expense, and thus map hash values back to the original passwords without actually brute-forcing the hash function for each password. Since unsalted hashes are static these tables can be reused over and over again. The solution is to add unique random data ("salt") to each password before hashing; every salt + password pair will have a unique hash, making such tables impractical. There is no need for the salt to be kept private, but it does need to be different for every account to be effective. The salt has to be stored so that you can later check whether a given password, plus the known salt for the account, hashes to the same value as the correct password.

Re:Who doesn't hash/encrypt passwords?

[tomhudson]

if you're not going to block me after 100 failed logins, it's unlikely that you're going to stop me after 4000, either.

Todays attacks use many computers, making many attempts with a longish interval between attempts. They don't care if they make 2 attempt every 15 minutes per host - this lets them attack hundreds of thousands of accounts simultaneously, and over the course of a year, they'll get into many boxes, without ever being locked out for too many attempts, since the REAL owner will successfully log in, and reset any "bad login attempts" count.

Re:Who doesn't hash/encrypt passwords?

[tomhudson]

My user name is " or uid=1; -- you ignorant clod!

Re:Who doesn't hash/encrypt passwords?

[Ja'Achan]

Since it doesn't need to be private, but only different for each user, can you use the user name or email for it?

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

As I replied in this thread a few times, my way is more secure than yours.

There is no one right way to do this, and I don't believe your way is better, here is why:

The salt only helps to slow down or make it impractical to try and attack the encrypted passwords, this means someone got their hands on those encrypted passwords. If they did that, that means that read my database. If I stored the salt for each password in my database, then they have the hash and the salt, much good does that do to slow down their attack, it makes their attack more likely to succeed.

On the other hand if they know the salt but have no access to my database, then they can't use salt for anything (specifically to 'decrypt' passwords by dictionary or brute force analysis.)

If they have access to my database, my problems are much worse than someone having a password.

The single salt I use works better, because it is not in the servers, it is physically set and removed after the application starts and reads file with settings.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

I am confused? :)

The only thing that salt does (try following this) is prevent an attacker who already has the ENCRYPTED passwords in his hands. It does nothing to make actual passwords more secure.

Here is the use-case I:

1. Application user A has a password: stupid-password-1
2. Application adds salt to it (in this case same salt for all passwords): stupid-password-1-yy3RD4%
3. Application hashes the password and converts it to Base64: YmJmN2IwNWY0OTkwNDUwNmNjZDY4NjdmY2FhMDE0Yzk=
4. Application stores the password in the database, but salt is NOT stored in the database.

5. Attacker X wants to break into the application by brute forcing the password, so he uses dictionary attack (never mind that in my case he won't access the app due to the firewall only letting certain IP addresses, but let's say the attacker is on one of the allowed IP addresses.)
6. Attacker X spends enough time to brute-force/dictionary attack this password: stupid-password-1 and he is in the application.
Attacker X is in the application and he does not need the salt.

7. Attacker Y got access to my database and he read the encrypted passwords and now he wants to know what they are, so he runs a brute-force/dictionary attack on them, but he does NOT have the salt, so he can't use that to reduce the complexity, so his attack is unlikely to succeed.
Attacker Y got access to my database. What does he need the passwords for? He already has the data that is stored there anyway.

----

Use case II:

1. Application user A has a password: stupid-password-1
2. Application adds RANDOM salt to it: stupid-password-1-yy3RD4%
3. Application hashes the password and converts it to Base64: YmJmN2IwNWY0OTkwNDUwNmNjZDY4NjdmY2FhMDE0Yzk=
4. Application stores the password in the database in the user table, the salt is also stored there.

This changes nothing for attacker X.

For attacker Y the life is simpler now, if he already has the database table, he probably even has the source code to look at (why would he have access to the database but not to the application?) Now his attack is against passwords and a known way to apply KNOWN salt to those passwords, and humans are not very good at creating truly random passwords, thus he is very likely to succeed breaking at least some of the passwords.

--

Yeah, people who believe that them storing a random salt alongside the hashed password is more secure, they are the confused ones.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Dude, I am storing hashed passwords. MD5 may not be the best hash algorithm, but I don't care, if you got that far as to read my database and get the encrypted passwords, then I have problems much bigger than you finding out what the passwords are.

Where did you get the idea that I am storing encrypted passwords, which part of this thread told you that, the multiple commentators who didn't see some of the thread where I posted the code for hashing the passwords? Check it out.

As to what is more secure, storing salt in the database for each password or having one salt that is loaded during the application start-up and then removing the file so that it does not exist on the system, here is my answer to that.

Read the entire thread before answering, ok?

Re:Who doesn't hash/encrypt passwords?

[Timmmm]

Yeah I can't count the number of times I've signed up to some web site, only to be emailed my password.

Re:Who doesn't hash/encrypt passwords?

[John Hasler]

Unless the hashing is done on the client.

Re:Who doesn't hash/encrypt passwords?

[John Hasler]

That doesn't tell you that they don't use hashing, just that they create an initial password and mail it to you (unless what they send you is a password that you typed in when you signed up).

Re:Who doesn't hash/encrypt passwords?

[Timmmm]

(unless what they send you is a password that you typed in when you signed up).

Yeah I was referring to this.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

You must have a random per-account salt to stop brute-force attacks of your entire password database. Doing so multiplies the cost of cracking the passwords by the number of accounts.

Someone who has your password database probably has your system salt. They can generate a hashtable from that and crack a good number of your passwords very quickly. When using random per-account salts, however, they can't use a hash table or rainbow table. They have to perform a complete brute-force against every single hash.

It is also a mistake to use a cheap hash function, like SHA. You should use an expensive one, like bcrypt.

http://www.usenix.org/event/usenix99/provos/provos_html/index.html

(ps: you are not talking to just another programmer. you are talking to an infosec specialist.)

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

The entire exercise is a ruse, if someone has already access to my database, they'll get the information they came for without cracking the passwords, so that's a bunch of crap.

But more to the point: storing salt in the database with the user name and the hashed password reduces the complexity of the attack, it does not increase the complexity. You have access to my database, then you can get my source probably as well, then you'll know exactly what to do with the salt you just found, how to append it or XOR it or pre-pend it, or mix it with the rest of the password and now you are just attacking the password itself without the salt.

My system is more secure by not storing the salt anywhere on the servers, but I don't even care about somebody's password stolen to this app because we monitor usage and restrict IP addresses. I am more concerned with somebody being able to directly access the database server/app server, so that's my primary concern.

I don't who you are, you got this thing into your head that there is only one way to do salt: random number/string stored together with the hashed password. But you can only use salt to attack HASHED passwords, so you got the access to my database then and I should be worried about you cracking a password? This is nonsense.

AND my way is more secure: I put the file with initialization settings onto the system before starting the application and then I kill the file after the app is running. Now to get the salt you have to not only be able to access the database, you have to get into the RAM of the server somehow, good luck with that.

When you say: YOU MUST have a random salt per account, I tell you: you are stuck in your head.

As to the hashing algorithm, that I agree, MD5 is not good in itself, but that's not what I am basing the security on.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

The entire exercise is a ruse, if someone has already access to my database, they'll get the information they came for without cracking the passwords, so that's a bunch of crap.

That is not correct. Example 1: A stolen backup tape to a stock trading system won't allow a hacker to enter new trades. Reversed passwords from the system, however, will allow him to do so. Example 2: A hacked web portal contains no sensitive data, however, if its passwords can be reversed, some of those username/password combos can be used to access far more sensitive applications.

Information security is a complex and subtle game. It requires a different mindset from programming. Programmers who assume they can anticipate all possible security faults nearly always get it wrong, as you have just demonstrated. Furthermore, they tend to be handicapped by egos that prohibit them from admitting their mistakes, perpetuating the problem.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

You are wrong when you simply pile every possible application in the world into the same category.

Beside which, you are wrong about my assumptions: I assume that my application users come up with passwords that are weak or that they by mistake/any other reason give their passwords away or simply are not careful and somebody reads their password.

You are wrong when you think that password is more difficult to steal from a user than it is from any system/backup/whatever, you are demonstrating a flaw in thinking insisting that password itself is secure.

I don't assume any of that, in fact I assume my users share their passwords because I know that they do and I can't do much about that. So instead of relying on weak ass assumptions about security of application passwords, I assume the worst and do more important stuff to secure the application - monitoring, constant logging of data and comparing usage patterns. The application prevents most users (except for 4 people) to access it from outside of the office, so then it also becomes a physical security issue - who has access to our office. We look at anomalies in usage with more attention than bothering with the passwords themselves, because we KNOW that passwords are not safe.

Cheers to your high-tower there.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Oh, and you still are repeating the same idiocy as everybody else here saying that storing salt with hashed passwords is more secure than not.

Can you count numbers? Count this: what's the difference between knowing the hash value of a password without salt and knowing hash value of a password that has salt AND knowing the salt? Do that math, you'll figure it out eventually that there those values are the same.

Re:Who doesn't hash/encrypt passwords?

[pssldt]

No. No. I'll say it again. No. The purpose of the salt is to vastly increase the difficulty of pre-computing the password hashes. If you use no salt -- an attacker who has your database can compare against precomputed hashes very, very easily. If you use the same salt for everything -- an attacker only needs one precomputed set of hashes. If you use a unique salt for every password -- an attacker has to have a separate set of hashes for every password he wishes to attack. Yes, if your database is compromised you have a serious problem. But then, if you're database security is infallible, why bother to encrypt at all? Defense in depth is key.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

Furthermore, they tend to be handicapped by egos that prohibit them from admitting their mistakes, perpetuating the problem.

Good day.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Count the numbers, you know, digits 1 to many.

Good day.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

You are a snake oil salesman who stairs at the obvious truth and refuses to admit being wrong and you are projecting this trait onto me.

Re:Who doesn't hash/encrypt passwords?

[JesseMcDonald]

Where did you get the idea that I am storing encrypted passwords...?

Well, let's see. There's the part where your original code calls "Encryption.encryptString"; it appears that this was simply misnamed. I didn't see the other comment where you posted the detailed code, as it wasn't scored as highly. There's also the part of the comment I was replying to which said:

Salt is only useful to protect the encrypted passwords, so if someone got the database and wants to decrypt the passwords.

Apparently you were just being (extremely) imprecise. Encryption and decryption are two-way operations; transformation from plaintext to cyphertext and back is meant to be easy provided you have the key. Properly speaking, you can't decrypt a hash value, and hashing is not a type of encryption.

I freely admit that I drew the wrong conclusion, though that was hardly unreasonable considering the evidence presented presented to me. I apologize for incorrectly disparaging your understanding of this aspect of cryptography. In the future I will seek more information before responding.

As for the difference between a constant "salt" which must be kept in the application's memory (even if the physical disk it was loaded from is removed) and a unique, random salt value stored in a database, it should be obvious which is more secure—but this thread is too long already. Suffice it to say that the problem with your scenario #7 is that the attacker will have the salt, having read it from the running application with a debugger (for example), and thus can perform all the attacks possible in the properly-salted configuration (case II) with the added advantage that the hashes will not vary between accounts, requiring only a single look-up table. Removing the input file does little to keep the salt value hidden compared to storing it in the database.

Re:Who doesn't hash/encrypt passwords?

[JesseMcDonald]

I don't see why not, but you should bring that up with a full-time cryptographer before implementing it. Just because I can't see a weakness doesn't mean there isn't one. :)

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

You're right. The entire field of cryptography is a sham. You have singlehandedly put us all to shame. Any minute now, some men in black suits will arrive at your door to invite you to the NSA so that your amazing insight can give them an edge over the rest of the human race.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Right, that's why I am running OpenBSD, using open SSL, hashing the passwords.
--

I know types like you, whenever you see a project you must force it to be exactly like the model you have in your head, any deviation from your model is obviously wrong, no matter how useless and redundant the stuff is.

More importantly, you are the kind of guy who is impossible to convince of anything and you believe that anybody not seeing it your way is wrong. You would force any project into a specific pattern, you'd force any project into frameworks you personally approve of, anything else is absolutely intolerable for you. Anything that does not correspond to your view is wrong.

You know, I have seen enough of this. If you were serious, you'd display a modicum of common sense and would admit the simple truth:

1. If anyone has my database table with the hashes of the passwords, then they would have the salt data right in front of them.
2. If they have the hashes and they have the salt in front of them, then it is exactly the same if the hashes were of actual passwords without any salt on them in the first place.

It's either that or

3. If I am storing salt so secure that nobody can get them, then I am storing hashes so secure that nobody can get them.

--
So storing salt is as secure as storing hashes of passwords.
If storing hashes of passwords is insecure, then storing salt is insecure.
--

Given all of that, it only means this: either don't bother with salt at all, because the hashes are stored so secure that nobody can get them and there is no problem and salt is pointless OR do not store salt, only store hashes because obviously this data can be somehow retrieved.

Given these choices, I chose to store hashes only and to load salt once and remove it from the system so nobody has it except for me and it is physically impossible to get from the servers / systems / company actually.

If given all of these conditions, you still insist that your way is more secure - you are a snake oil salesman and I personally prefer not to deal with you in business.

People like that are recognizable easily by pushing forward ideas that are so contradictory and really pointless and often expensive and in reality add nothing of value at all.

Finally, here is a piece of real world, it's funny how xkcd gets this stuff so right and you don't, except that we know that our users share their passwords and generally do not care much about security of these passwords, thus relying on passwords for security would be totally insane, that's another reason why I see you the way I see you.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

Looks like you're having a breakdown. Chill. You haven't reinvented authentication in the worst possible way, but you must admit that it's flawed. Listen: when it comes to crypto, just don't reinvent the wheel. Really. Use something written by a cryptographer.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

But at any rate, I'm a little tired of explaining, so I'll give you this:

The system you reinvented could be reversed under some conditions. A properly-designed system, like bcrypt, could not be reversed under any conditions. By reinventing an authentication system rather than simply using an existing, secure one, you sacrificed both dollars and security, while gaining nothing.

If you think you have found a flaw in bcrypt or have designed something substantially better, write it up and publish it. You may get invited to speak at BlackHat. Otherwise, don't waste your breath.

When I'm on a pen test, I can generally reverse part of any password database I come across, except for one that uses per-account random salts (as is the case with most unix systems and with bcrypt). What you call "snake oil" I call "a dead end in a pen test."

But by all means, never consult with a security expert. You don't want any of that snake oil in your systems.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Passwords are useless in the first place, and that is what you can't understand. If I relied on passwords for security, I wouldn't have any security at all. My users don't care about passwords so I can't rely on them to keep them secret because they don't.

Thus the argument that I have to invest more time into a password protecting mechanism is stupid and someone making it to me is a snake oil salesman. Twice so, for insisting that storing hashes cannot be secure but storing salt is.

If anybody wanted a password for an account of any of my users (except for 2 people), all they'd have to do is ask them, and most likely they'd get them. They don't have to steal anything to get those passwords.

Thus my systems have to take that into account, and that is an architectural problem, not a problem of encryption, so I don't need to find flaws in any encryption mechanisms, that's a theoretical problem, I need to solve practical ones, and that is a third reason you are a snake oil salesman.

Re:Who doesn't hash/encrypt passwords?

[Lord Ender]

"That's a theoretical problem" is one of the funniest and most ignorant comments I've ever hear in response to a security evaluation. It is often followed-up by somebody's systems getting owned up and down in a pen test. It's a phrase only the most inept admins use. Congrats.

And so it remains: you wasted company time and sacrificed security by reinventing a reversible password system when one that cannot be practically reversed is already in wide use. No amount of name-calling will change that fact. Give yourself a pat on the back for that, too.

Re:Who doesn't hash/encrypt passwords?

[roman_mir]

Once again you are avoiding to answer this simple question, because you know there lies the truth and you can't have it.

Why is storing a hash of a password less secure than storing a hash of a password and storing a salt for it?

Don't answer, you can't, you are programmed not to be able to answer this, in the face of the obvious inconsistency you shy away from thinking about it falling onto a pre-programmed reaction.

It is also funny how you believe that this specific issue is going to lead to my systems 'getting owned' without knowing anything about my systems. Thus another pre-programmed reaction, which is also nonsense and it leads me to conclude that you are useless and I wouldn't have you anywhere near my systems.

Or...

[hypergreatthing]

they could just impliment a simple
if passwordcheck(password)=false then
wait random(15)
end if

OMG so very hard!

Re:Or...

[Stewie241]

The point isn't that it is hard to do... the point is that it isn't being done. The other point is that it wasn't being done because of the contention that the exploit was so unfeasible it wasn't worth it. The research demonstrates that the exploit is more feasible than people thought.

Re:Or...

[Carnildo]

This doesn't fix the problem, it just slows down the attacker. Statistical analysis of the delay will still tell the attacker exactly how long it took to check the password.

The correct fix is:

if passwordcheck(password)=false then
run_a_delay_loop_until_it_takes_as_long_as_a_success()

Re:Or...

[Anonymous Coward]

start = time.time()
authenticate = passwordCheck(password)
wait_until(time.time() > start+timeDelay)

Re:Or...

[something_wicked_thi]

Congratulations. You've just implemented a system that is exactly no more secure. See posts above for why.

Re:Or...

[An Onerous Coward]

It is more secure. These attacks wouldn't work over a network at all, except they found a way to subtract network latency. You might have to put back in a large amount of random delay, but eventually the noise should swamp the signal and make the attack infeasible.

It's not the best approach, I know.

Re:Or...

[something_wicked_thi]

Fair enough. It is more secure. I was simply trying to illustrate that the original poster's snarky attitude is misplaced since his solution sucks, too.

Re:Or...

[Spykk]

string password = '\0';

while(true)
{
if(CheckPassword(password))
return password;

total = 0;

for(int index = 0;index < 1000;index++)
{
total += TimePasswordRejection(password);
}

if(SignficantlyDifferentThenPreviousAverages(total / 1000))
password += '\0';
else
password[password.length() - 1]++;
}

Or do not have variable delays at all

[betterunixthanunix]

This is neither a new problem nor an unsolved problem. This problem stems from using functions like strcmp, which return as soon as a difference is detected, and are thus unsuitable for password checks. Solution? Set a flag when the first difference is found, and continue checking subsequent characters.

Re:Or do not have variable delays at all

[Anonymous Coward]

Which is just a waste of CPU resources. It's better to use the function that returns immediately, and sleep briefly instead. At least then you're freeing up the CPU for other processes that may have real work to do.

I know, I know, you'll say it's "not a big deal", but you probably just don't deal with real servers that experience heavy load.

Re:Or do not have variable delays at all

[betterunixthanunix]

I presume this is the same sort of logic that lead to the decision to use plaintext passwords, rather than salted and hashed passwords.

Re:Or do not have variable delays at all

[something_wicked_thi]

But if you sleep, you may not wake up for a long time. Processes that relinquish the cpu could take a while to schedule again on machines with heavy load. When you're talking just a few dozen instructions for the additional compares, since most strings ought to be short, it's far better to finish the comparison.

I know, I know, you'll say it's "not a big deal", but you probably just don't deal with real users that expect to have low latency responses to their requests.

Re:Or do not have variable delays at all

[natehoy]

Excellent idea, but if you institute a random delay you might actually make your system more secure (and you use less CPU doing it because you're not walking through the entire checking algorithm, thereby making yourself less susceptible to CPU overload DOS attacks).

A fixed-time-to-answer would quickly tell the time-based algorithm that it was not dealing with something that is susceptible to it, and the attacker would immediately move on to a dictionary attack or some other method.

If you institute a random delay, a time-checking algorithm would interpret that delay as meaning it got part of the answer correct, where in reality it might have gotten another part of the answer correct (or none of it). A few thousand random-delay hits would have the cracking algorithm thinking that it was simultaneously getting the same bits of the key right and wrong, but still convinced that it was dealing with a time-attack-sensitive system. The attacker might even interpret it as some form of rotating key and give up.

In other words, you are fooling the decryption algorithm down a blind alley of inquiry, and wasting its time. That's far more secure than telling it that you are not subject to time-based attacks right up front. You want to waste as much of your attacker's time and effort as you possibly can.

And, sure, the attacker is probably using multiple simultaneous attacks, but the more obviously impossible attacks you can convince them to try, the more likely it is they'll trip some form of DOS detection.

Actually, the ideal would be to tune the timing to infer to the attacker something utterly unlike the actual password, and if someone sends in the password you are inferring by your timing you are now aware that a time-based attack is underway, and you can stop trying to check passwords sent by that connection entirely - just keep replying "access denied" with the delay continuing to infer the same key. Puts a lot less load on your system, and keeps the attacker busy and armed with lots of incorrect information.

Re:Or do not have variable delays at all

[Trepidity]

It's really hard to get that perfect, though. If you're actually doing the same work, it's harder to accidentally leak information than if you're doing less work but trying to fake the equivalent amount. In the case of using a sleep, you're vulnerable to the particular scheduling implementation; it's pretty hard to make it so there's no visible timing differences between the sleep-using and non-sleep-using code paths.

There are cases where it's worth the effort, but I don't think strcmp() is one of them. When an attacker can gain information by detecting that you took different code paths, it's worth being somewhat conservative in unnecessarily introducing branching paths.

Re:Or do not have variable delays at all

[Anonymous Coward]

Absolutely not. There is valuable computation done when hashing passwords. There isn't when you continue comparing passwords well after you know they don't match, when you could just as easily yield the CPU to other processes.

You've been proved wrong. Try to argue the point next time, rather than throwing up strawmen.

Re:Or do not have variable delays at all

[betterunixthanunix]

but if you institute a random delay you might actually make your system more secure

Random delays are easy to filter out. In fact, given that the authors performed this attack over a network (which will add random delays anyway), you should already know that they are capable of doing that.

Re:Or do not have variable delays at all

[kyrio]

It's you who is sounding like a troll. The AC is correct, you are not.

Re:Or do not have variable delays at all

[Galestar]

Considering that passwords are generally 8-12 characters long, I'd think yielding the CPU would take more resources then just checked the remaining x characters.

Re:Or do not have variable delays at all

[kyrio]

He is correct about everything. You are just a troll.

Re:Or do not have variable delays at all

[JackDW]

That's interesting. For the benefit of other readers, it should be clarified that this attack is still possible even if the password is hashed, because a given hash value must be compared to the known correct value (as you stated below).

However the situation may be even worse than you suggest. The behaviour of the CPU may change as a result of setting that flag, perhaps causing its timing to change. For instance a cache miss may (or may not) occur, or memory accesses may be reordered, or a branch might be mispredicted.

From what you are saying, it sounds as if all of the password-related software needs to be very carefully designed to avoid any data dependent timing, because data dependence might expose information about the correct password (or password hash). This is difficult to do; even if a minimum execution time is enforced in some way, there will still be timing jitter, and that could also be data dependent.

Intuitively, I wouldn't think differences of a few hundred clock cycles would be detectable over the Internet, but maybe if you gather enough measurements... Interesting stuff anyway.

Re:Or do not have variable delays at all

[mandelbr0t]

Actually, the ideal would be to tune the timing to infer to the attacker something utterly unlike the actual password, and if someone sends in the password you are inferring by your timing you are now aware that a time-based attack is underway, and you can stop trying to check passwords sent by that connection entirely - just keep replying "access denied" with the delay continuing to infer the same key. Puts a lot less load on your system, and keeps the attacker busy and armed with lots of incorrect information.

Now that's just spiteful! Remind me never to piss you off...

Re:Or do not have variable delays at all

[betterunixthanunix]

The behaviour of the CPU may change as a result of setting that flag, perhaps causing its timing to change. For instance a cache miss may (or may not) occur, or memory accesses may be reordered, or a branch might be mispredicted.

We can actually prevent cache timing attacks somewhat by aligning the flag to a cache line boundary, and writing the password exactly one byte ahead of the flag. Thus, to compare the password at all, the flag will have to be cached, and so setting/checking the flag should not create a cache miss. This assumes that the password will not be too huge (i.e. a long enough password could "wrap around" and evict the line with the flag on it), but I think that it is fairly safe to assume that passwords are not megabytes in length.

As for branch predictions, we can always use a logical OR operation. So, for example, consider this:

flag = flag | (passwd[i] - submitted[i]);

Thus we do not actually need a branch in the inner loop. Note that this is overkill in the case of a network based attack, since a branch miss will not change the total delay (in theory), but this technique is useful for systems where an attacker may have the ability to measure power consumption (branches often cause changes in the power consumption of a system; this has been used to attack embedded systems in the past).

As you stated, the implication in all of this is that authentication systems need to be carefully designed to ensure that side channels are difficult to exploit (you cannot truly remove them). Usually that is not what happens, although the most basic timing attacks such as what TFA describes and not so common anymore (since they are so basic).

Re:Or do not have variable delays at all

[An Onerous Coward]

Hashing should make a huge difference, though. If you're comparing the passwords themselves, it's pretty straightforward. To crack the hash, you have to find an acceptable-length string that hashes to each subset of the target hash (a..., a0..., a0f..., a0f4..., a0f49..., etc.) I don't know if there is a way to do that other than brute force, and toward the end the search space is prohibitive.

I think the best you could to would be to get the first several digits of the hash, then use it to prefilter the guesses you're sending to the service.

Re:Or do not have variable delays at all

[Michael Kristopeit]

i agree with you completely. i'd go one step further and make the random delay added on top of a fixed time so that any averaging attack would also lead to an answer that was ultimately incorrect.

sad that your comment is scored 1, and people suggesting these ideas are completely pointless are being scored 4+. this site no longer functions properly.

Re:Or do not have variable delays at all

[moderatorrater]

Nevermind that hashing will take a hell of a lot longer than check the entire plaintext password. Nevermind that checking the entire plaintext password is valuable if security matters

Yes, but there is an acceptable alternative to checking the entire plaintext password while there is no acceptable alternative to hashing the password. If there's an equally secure alternative that requires less computation, why not use it?

Re:Or do not have variable delays at all

[doublebackslash]

Sure thing.
# openssl speed sha1
Doing sha1 for 3s on 16 size blocks: 4925162 sha1's in 3.00s
Doing sha1 for 3s on 64 size blocks: 3460802 sha1's in 2.99s
Doing sha1 for 3s on 256 size blocks: 1972423 sha1's in 3.00s
Doing sha1 for 3s on 1024 size blocks: 722903 sha1's in 3.00s
Doing sha1 for 3s on 8192 size blocks: 104552 sha1's in 2.99s
OpenSSL 0.9.8g 19 Oct 2007
built on: Mon Jun 7 19:28:26 UTC 2010
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cisc,16,int) aes(partial) blowfish(ptr2)
compiler: gcc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wa,--noexecstack -g -Wall -DMD32_REG_T=int -DMD5_ASM
available timing options: TIMES TIMEB HZ=100 [sysconf value]
timing function used: times
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
sha1 26267.53k 74077.37k 168313.43k 246750.89k 286451.50k

26 MB/sec on small blocks in sha1sum. String compares I don't have a command handy to time, but I know that they will be in the hundreds of megabytes / sec range. Now this does not cover security concerns at all. I think that, since we are talking about a security system, we should talk about them.

Passwords are salted and hashed because storing a plaintext password is a grave security mistake. Anyone working with the database could grab a single table and know what everyone's passwords were. That is exceptionally bad, even if they only used the password in that one place. Someone could use that knowledge to legitimately log in as a user. Extrapolate from there. Worse still, many people use the same passwords in a few places, perhaps with a few variants.

Without just telling you to Read More Schneier (which would be rude) , I'd like to make you aware that hashing is one of the most amazingly cheap non-arbitrary things one can do on a modern processor, and that all other operations in a useful system take vastly longer (database lookups, disk access, network access, public key cryptography to establish an SSL session which you better hope your password travels over).

Cryptographic hashes are one of the best building blocks for secure systems, and you may find their application interesting. Give it a look-see. I do recommend Schneier, but some free links follow:
http://unixwiz.net/techtips/iguide-crypto-hashes.html (decent primer, little long winded)
http://mathworld.wolfram.com/BirthdayAttack.html (simple explanation of the birthday attack)
http://en.wikipedia.org/wiki/Salt_(cryptography) (I know a wiki link, but this ties in VERY closely with password security)
http://en.wikipedia.org/wiki/Message_authentication_code (another, I know. But it has a lot of titillating links in it that should be followed)

Also for further reading: Package transforms and Schneier's book Applied Cryptography.

Security is important, and I'd think that if you have such strong opinions you could put them to good use. Happy reading!

PS: None of the links I provided talk about timing attacks. That is very important, but once you've got your head around cryptographic hashes you will know that a well salted and properly implemented hash library will not be vulnerable to many timing attacks. Figured I'd warn you.

Re:Or do not have variable delays at all

[natehoy]

Spiteful?

Not at all. If my software comes under attack, its job is to confuse the attacker as much as possible in any way possible, while identifying the nature of the attack and alerting me to it.

The whole point of a good layer of defense is to slow down your attacker as much as possible, and make it obvious that he's an attacker.

Actually, the ideal would probably be to make the inferred password really long and make it take a long time to guess, then make it a perfectly valid one - to a honeypot server.

Re:Or do not have variable delays at all

[rgviza]

Since passwords are usually stored hashed, you need to hash the plaintext input. You can either do it in the database or the front end code, but you still need to do it.

Generally you do a select password, username where username = inputusername and password = password(inputpassword);

where password() is the hashing algorithm. If you get a row, it's a successful login.

The database usually does an indexed lookup against the first 4 (lets assume the index is on 4 characters) characters of the hash so the fails are going to usually be pretty consistent in time unless you get one of the first 4 characters right after hashing. Even then it won't have the timing you'd think it would. You could get the first 4 characters of the password right when inputting it, and it's possible that once hashed, none of the first 4 will match when comparing the hashes against what's in the table.

As well the entire hash result changes when you change just one character on the input if you use a good algorithm (sha2 or rijndael aka AES) so it's difficult, if not impossible to predict what change will happen in the hash by changing the input, if you don't know the secret and initialization vector. Much less how it will affect the timing of the query result.

Maybe I don't understand the problem.

Is this an issue with unhashed passwords? If so it's a non issue for most because anyone with half a brain will be using strong-cryptographically hashed passwords in a production system. The actual article says "some" libraries are vulnerable. I'm betting it's the ones that are set up to use text file databases with unhashed passwords. There are options in some of the servers to use a database like this.

This type of attack is one of the reasons we cryptographically hash passwords and use a good algorithm instead of something like md5.

Re:Or do not have variable delays at all

[KingMotley]

A better solution is to use a pre-defined salt, and md5 hash the input with it. Then generate an appropriate random hash, and re-hash using sha1 both the input and a pre-salt-hashed stored password with it, then compare both with strcmp.

Good luck trying to reverse that. It's not impossible, but it's the best I can come up with, and likely to withstand any (reasonable) attack in the next 50 years on conventional hardware.

Re:Or do not have variable delays at all

[Anonymous Coward]

God I hope you don't design software. Where is this plaintext password stored? Oh, you mean in a database? In plaintext? Think for a moment.

Re:Or do not have variable delays at all

[Wildclaw]

Umm. The AC is plain wrong. If you are comparing two equal length strings (as with hashed values) and expect the result to be true most of the time (as with user supplied passwords), then the secure comparison is faster than the unsecure variation.

The reason for this is simple. A secure comparison is implemented using only logical operators, while the unsecure variation requires a conditional jump for the early break condition.

Re:Or do not have variable delays at all

[Anonymous Coward]

Mmmmmm, salted hash. Yum.

Re:Or do not have variable delays at all

[owlstead]

Although I agree with your stance (I think, it's starting to get confusing what you are both arguing) I don't think it was wise using the word troll.

OTOH, moderators, that does not give you the right to mod him flamebait.

Re:Or do not have variable delays at all

[owlstead]

Are you actually talking about the CPU time of comparing a 16 character string? Do you want to have the times for my 25 year old MSX computer or my 4 core CPU? And YOU are complaining about a Strawmen argument? Are you out of your mind?

Mods, don't mod this kind of thing insightful, even though the hashing is good advice.

Re:Or do not have variable delays at all

[owlstead]

Of course I won't attack your SSL figures (even though they don't include the reference system info, but whatever). Of course, that does not make the GP incorrect in stating that the comparing of the full string will use less cycles. It also leaves out the call to the openssl library, which is probably more costly than the actual hashing of a small string (and salt).

The problem is that the AC is mixing a completely sensible solution (using hashes - introduced by betterunixthanunix nonetheless) to argue a completely idiot point (the amount of CPU power required to fully check passwords). The discussion can only go downwards from there.

Re:Or do not have variable delays at all

[debatem1]

when you change just one character on the input if you use a good algorithm (sha2 or rijndael aka AES) so it's difficult, if not impossible to predict what change will happen in the hash by changing the input, if you don't know the secret and initialization vector.

AES is not a hash. AES is a symmetric block cipher.

Re:Or do not have variable delays at all

[owlstead]

Oh, those interesting discussions when trying to calculate the time for comparing two strings.

We're here in 2010! Half an XML tag will take 10 times more time than comparing two string of 16 characters long (if that).

The AC is wrong alright. He's wrong for even brining it up.

Re:Or do not have variable delays at all

[owlstead]

Depends on where you do the hashing. If you do it on the client then you will just generate the hashes by starting with the first byte (00, 01, 02 hex until you find the correct one). Then the second byte etc. In total, you'll have to try and find 20 bytes (taking that you are using SHA-1 for the hash). For each byte you will find the correct answer after 128 statistical test average. So that's just 2560 statistical tests total. Say that you have to use 100 tests to get to each byte value, then you have 256000 tests total to crack the hash instead of the password. This is way too low.

Of course, you can also hash the password on the server, but then you would still have to send the plain password, which is not a good idea anyway, even when using SSL. The way around this has of course already been discussed, and is bad practice. It's applying a salt to each password before hashing it and sending it from the client.

Re:Or do not have variable delays at all

[mad_minstrel]

Security trumps a few CPU cycles. End of story.

Re:Or do not have variable delays at all

[Anonymous Coward]

my god, you are stupid.

Re:Or do not have variable delays at all

[vux984]

There isn't when you continue comparing passwords well after you know they don't match, when you could just as easily yield the CPU to other processes.

"...well after you know they don't match" ?

If you were comparing strings that might be kilobytes or megabytes in length sure... but passwords? or even pw hashes? Wouldn't you waste more time doing the yeild than you'd ever possibly just finishing the comparison?

Re:Or do not have variable delays at all

[tomhudson]

The AC is wrong alright. He's wrong for even brining it up.

Maybe he thinks he can salt the plain-text password and it will be "as good as" ciphered - like people who renamed their .bat files to .com so they would run faster ...

Re:Or do not have variable delays at all

[ibsteve2u]

Holy cow! All of those links, when all I wanted was an unbreakable solution in 12 words or less?!

Now I must get back to my MegaMillions results predicting code...

Re:Or do not have variable delays at all

[Anonymous Coward]

Yes we all know that storing passwords in the world readable passwd file was pretty stupid but that's just how UNIX used to be.

Re:Or do not have variable delays at all

[Bungie]

Yes you're comparing a string under a single thread in the same memory space. Now multiply the CPU time by the number of requests that probably go across the OpenID servers every second and also take shit like context switching and memory management into account. You can't assume a highly loaded server is the same as your workstation.

For example, on one of our Windows servers someone installed the J2RE which also runs an updater app when you login to your profile. It used 100MB of memory but it was almost entirely paged to disk so he thought it was ok. The problem was that it was a Citrix server which thousands of people logged to every day (each running a copy of the updater app). Pretty soon that 100MB of added up to gigabytes, consumed the entire size of the paging file, and the server started to run out of memory.

Re:Or do not have variable delays at all

[daveime]

Sorry, what ?

A hash is a fixed length representation of some function.

All of the N of characters have to be compared before a match can be declared, so surely every hash comparison should take an identical amount of time ? It doesn't even expose the possible length of the original password via timing attacks, and all hashes are the same length when using the same function.

Re:Or do not have variable delays at all

[owlstead]

And that compares to a 16 character string compare, how?

Re:Or do not have variable delays at all

[Anonymous Coward]

Since the hash comparison is done character by character, they can tell how many match because it will take longer to fail and return. If I don't mstch the first character, it will return instantly. If the first matches, it will take longer as it will compare the second characters of the hashes and return when that fails. If the second characters match it will take even longer to fail and return and so on. Since I can tell when the next character matches, I can bypass the randomness of the hashing and eventually come up with one that matches.

Re:Or do not have variable delays at all

[AdamsGuitar]

The point is that *both* paths are sleeping, it's just varying the amount. Any modern processor has sub-millisecond timing measurement facilities, so it's trivial enough to time how long the actual "work" takes, then sleep for the difference up to your maximum amount (that's the point of padding an operation that takes a maximum of, say, 100ms to 150ms). Because you're *never* going to take exactly 150ms, it would be virtually impossible (if not outright impossible) to detect the difference.

Re:Or do not have variable delays at all

[John Hasler]

> All of the N of characters have to be compared before a match can be
> declared, so surely every hash comparison should take an identical amount of > time ?

Only successful ones. In much existing software the test exits as soon as a mismatch is found.

Re:Or do not have variable delays at all

[Anonymous Coward]

I find it astounding that your post, which is devoid of content, has been moderated as "interesting", while betterunixthanunix, who actually bothered to offer justification for his point, has been moderated as a "troll".

Me thinks the slashdot moderation system is a bit tendentious.

Re:Or do not have variable delays at all

[Anonymous Coward]

Nice blowhard post where you can trot out your personal library and ability to run openssl speed tests.

Everyone who knows what a hash is knows what it accomplishes. Yet, despite how awesome you've been convinced they are, your example is for a marginal security benefit (mitigating partial break-ins) and ignores cases where plaintext is, for practical purposes, necessary, such as commonly used challenge-response protocols, password verification over the phone, etc.

Also, ironically, you are supporting betterunixthanunix's point, since if we have plenty of CPU power to transform a plaintext password into a hash every time it's checked, we can surely ignore the negligible amount of extra time it takes to use his fixed-time strcmp (which btw might be used to compare hashes, too). Note that since a good password will require checking all characters, anyway, it doesn't "waste" CPU cycles unless a BAD password is entered.

Finally, the time difference, which your long post failed to answer, definitely does matter, since for large-scale users of OAuth, like Google, strong cryptography does impose a noticeable cost. I remember that not too long ago, Yahoo and others implemented a password hashing function in JAVASCRIPT which imposed the CPU cost on the user's browser! Coupled with the fact that they weren't using SSL by default, this made MITM password snatching entirely do-able, if not trivial.

Re:Or do not have variable delays at all

[An Onerous Coward]

I'd never heard of anyone hashing a password on the client side, but I don't see how doing so would provide any security. If an attacker is listening in, he might not be able to recover the original password, but at that point, he doesn't really need to. All he needs to do is send an http request with hashed_password=a40387b0f3aa... as a parameter. And I'm not clear on how you would do the salting on the client side. If it comes from the server, then the attacker can capture the salt with all the other traffic. If it's stored in a cookie client-side, then I'd suppose that clearing cookies from the browser would lock you out of the site.

I'm not saying you're wrong. I've just never heard of it. Typing "client-side password hashing" into Google brought up a few results, but the first hit seems to agree with me.

But I think you're right. If you're doing client-side hashing, then you're effectively doing the described attack, but on the (probably longer) hash string rather than the original password. No need to find strings that hash correctly.

Re:Or do not have variable delays at all

[Bengie]

context switches are expensive. You're better off comparing the whole string to make the times similar than sleeping the thread.

A context switch is typically 1000+ cycles. Those same cycles could've compared a VERY long string.

Slashdot

[ceraphis]

that are used to check passwords and user names when people log into websites such as Twitter and Digg.

You forgot slashdot.

This happened back with WinNT

[Anonymous Coward]

There used to be a similar timing problem in the days of WinNT with account lockouts. An attacker would throw guesses at a target, which would delay its responses slightly while the account wasn't locked out. Once the lockout threshold was reached, the response time dropped significantly. It was obvious, too; a human could easily distinguish between accounts that were and were not locked out.

Welcome back to 1997!

Re:This happened back with WinNT

[betterunixthanunix]

TENEX was found to be vulnerable to this sort of attack; you could guess a password one character, by literally measuring the delay in the password comparison (identical to TFA's attack, really).

Welcome back to the 1960s!

Re:This happened back with WinNT

[Bert64]

Only NT already has RPC functions available remotely by default which let you see the password policy, see accounts that are locked, see what usernames exist, see what groups the accounts are in etc...

Re:This happened back with WinNT

[__aaxtnf2500]

IIRC The delay was not due to the password comparison, but to the fact that the DEC-10 hardware running TENEX would signal the user on the presence of page faults. The attacker could align the tested password in memory along a page boundary and check whether the page fault occurred.

Time for a secure strcmp()?

[Qzukk]

One that will always loop through the longest string (would need to figure out something to compare it to once past the end of the short string), even after it has decided they're not equal.

Re:Time for a secure strcmp()?

[mmkkbb]

Go back to the beginning of the short string. You know the comparison will fail, so it doesn't really matter as long as you don't follow some random pointer.

Re:Time for a secure strcmp()?

[Stewie241]

One that will always loop through the longest string (would need to figure out something to compare it to once past the end of the short string), even after it has decided they're not equal.

That seems like a silly idea to me. Why would you implement it in strcmp() when most of the time you want to maximize performance. The proper place to do this is not in strcmp but in the password verification routine. As noted above also, sleeping is a more efficient use of processor resources than performing non-important calculations.

Re:Time for a secure strcmp()?

[An Onerous Coward]

>> As noted above also, sleeping is a more efficient use of processor resources than performing non-important calculations.

Only if you're doing a large amount of non-important computation, or ignoring the cost of the context switch. Neither is the case here.

Re:Time for a secure strcmp()?

[Anonymous Coward]

Sleeping a random duration is statistically insignificant (though it does raise the aggravation level on the attacker's part, and they'd probably spend their time attacking something else), the attacker could simply try each password N times and compare averages.

You could do something like hand off password verification to a second thread, then sleep for 2 seconds while the second thread does the comparison. You could even have the second thread signal the first when it's done if the password is correct (beware kill) so the user can log in immediately. Otherwise, if the password is incorrect, it always takes exactly 2 seconds.

Does no-one else put a 10-second delay in?

[Xugumad]

Last time I coded a web based auth system, if you failed to log in it would refuse to check your next attempt until 10 seconds after the previous one (blocked by IP and by username). I, apparently foolishly, assumed most people would do the same...

Re:Does no-one else put a 10-second delay in?

[Anonymous Coward]

This isn't about 'try until you succeed', it's about 'measure exactly how long it takes to fail'. So your system, while commended, would not prevent against this unless you put in some sort of padding on the message that returned failure.

For example, if your password is 'password', then if I guess passwoe, it would take longer to fail than if I guessed qassword.

Re:Does no-one else put a 10-second delay in?

[Anonymous Coward]

If it's always sleep(10) seconds, you're only secure by accident (the difference in password comparison timing is probably less than the sleep() clock granularity, which probably wakes it up at the nearest ten microsecond or so mark. For now, anyway. Then someone whines that their video is 0.8% out of sync and the kernel is modified to accommodate a finer-grain clock). If it slept exactly 10 seconds each time, you'd still be leaking "how long did it take to discover the password didn't match", though you'd be slowing down the overall process.

Re:Does no-one else put a 10-second delay in?

[Bert64]

Do you block the combination of IP and user? If so, couldnt an attacker simply cycle through a block of usernames such that each user wasnt tried more than once every 10 seconds?

I like systems which block the user after failed attempts, but leave your IP alone... Makes it absolutely trivial to DoS the system by simply sending invalid auth requests for all the users.

Re:Does no-one else put a 10-second delay in?

[bjourne]

Yes, but you would need tens thousands of attempts to accurately measure the difference. The OP's solution doesn't make it harder, it just makes the process so slow that it won't be worthwhile because you have to wait so much.

Re:Does no-one else put a 10-second delay in?

[AlXtreme]

Doing so means you can DoS user-accounts with a single machine: simply attempt to log in again and again. The real user will now no longer be able to access the system.

No, blocking on IP+username makes more sense, or add a delay that exponentially increases in length based solely on the IP address (NAT notwithstanding).

Personally I like the default denyhosts-approach: Try root? You're out. 3 failed attempts? You're out. Feel free to try again next week. If you need tens of thousands of attempts you're in for quite a bit of work.

Re:Does no-one else put a 10-second delay in?

[Xugumad]

No, it's per user, and per IP, independently. AlXtreme's concern about DoSing an account doesn't apply because it doesn't reject a request, it just slows it (so a valid login may take an extra 9 seconds, but eh).

In terms of trying one account every 10 seconds... yes, they can, but it's dramatically cuts down the number of accounts/passwords they can try, and essentially makes the search time impractical.

Re:Does no-one else put a 10-second delay in?

[John Hasler]

> Yes, but you would need tens thousands of attempts to accurately measure the
> difference.

The attackers have tens of thousands of bots.

Re:Does no-one else put a 10-second delay in?

[Xugumad]

...which is why we time-block on username, not just IP. So even if they have a valid username to start with, they can't test more than one password every 10 seconds for it. Yes, they can test 10,000 usernames every 10 seconds, but cracking any of them is still impractical.

As it happens, we test on password hashes anyway, so work done should be constant, but the original point was I'm shocked such delays aren't normal practice.

Re:Does no-one else put a 10-second delay in?

[Xugumad]

As it happens the implementation is that when a login fails, it makes a note of the current time, plus 10 seconds, for the username and IP. When the next request comes in, it checks it, then holds on to the result until it's after the time recorded earlier.

However, from my understanding of how this works the delay would make the attack be essentially impossible (it would take months or years to get a crack, in which time there's a good chance the user will have changed their password).

lolswordfish

[crow_t_robot]

Just drop a logic bomb through the trap door, right?

That movie makes me cringe.

Re:lolswordfish

[Anonymous Coward]

not nearly as bad as The Net. Glad Sandra is hot...

Re:lolswordfish

[AnonymousClown]

The movie makes me hard....Halle Berry topless and the thought of some hot blond giving a bj while working at the computer.....

Suspension of disbelief, dude.

Re:lolswordfish

[Kaenneth]

Nowdays, I understand how my dad (A Boeing inspector for many years) felt when watching movies with airplanes... pointing out that they took off in a 737, but the landing scene shows a 757!

But, I still recall how annoying it was to have such things pointed out all the time... So I try and keep my mouth shut during the show.

Imagine what it must be like for a real medical doctor to watch 'House', or a real serial killer to watch 'Dexter'.

Re:lolswordfish

[moortak]

We enjoy Dexter quite a bit...

Re:lolswordfish

[h4rr4r]

Dexter does a pretty good job most of the time. His dumping method is not ideal though, you really want to get rid of the bodies not leave them around for someone to find. Or so I hear.

Hashed Passwords??

[neiko]

I thought most of the time just a hash of the password was transmitted, which would not allow this as the hash changes in multiples places when you change a specific location of the original password...

Re:Hashed Passwords??

[Captain Spam]

I thought most of the time just a hash of the password was transmitted, which would not allow this as the hash changes in multiples places when you change a specific location of the original password...

Almost, but using a straight, in-seuqence, string comparison, stop-at-first-difference method, you could work out the hash and check for a collision from there.

Okay, yes, that might be absurdly slow with today's computational power, but it's not quite foolproof.

Re:Hashed Passwords??

[SQLGuru]

If you just transmit the hash, then all I need to do is generate hashes; I don't actually need your password at all. This would be more or less the same as sending the password in clear-text.....it's just that the password is some fixed length string that can't be pronounced.

The server needs to do the hash, not the client.

Re:Hashed Passwords??

[guruevi]

Not necessarily absurdly slow - there are extensive rainbow tables out there that probably cover just about any common password.

First you'll need to use the hash-side of the rainbow table to get about 36 hashes which start with [a-z0-9] and then filter right on down. You might run into some trouble finding matching hashes as you near the end of the hash but it's not impossible.

It will no matter what take long. Given enough time and resources, anyone could crack anything. The only solution for now:

- Use non-dictionary words as passwords
- Do not store/read/handle passwords in plain text form
- Change passwords frequently (more frequent than the time it would take somebody to crack it using the fastest methods available (local attacks) at least >2 times as frequent)
- Use salts when programming
- Do not trust anyone or any system
- Accounts that are not used or that have a number of incorrect logons should be (temporarily or permanently) disabled.

Re:Hashed Passwords??

[Anonymous Coward]

It should use a challenge-response system instead. The server sends random stuff for the client add to the password which completely changes the hash every time. Even though the random stuff is sent in the clear, you can't derive the password since the hash is one-way.

Not affected

[pathological liar]

Looks like I'm safe...

Doesn't MD5 make this hard?

[tthomas48]

I hate this kind of announcement because it usually ends up that they found a hack in a revesion Bozo's poorly constructed library from 5 years ago, but I like this kind of announcement because it makes me consider my security.

I'm using a PHP OpenID library that's using md5 for comparison in the database. I don't really see how that would be feasible, since even if you were cycling through characters you need all characters to make the hash which mysql is making its string comparison based on.

Or am I missing something?

Re:Doesn't MD5 make this hard?

[mandelbr0t]

This reminds me of a similar flaw in Apache HTTPS a while back. It takes considerable timing resolution (i.e. not remote) to accomplish, but the problematic construct looks something like this:

if (!md5match) { return FAIL; } else { // do something long and complicated return SUCCESS; }

Basically, by using enough attacks and cycling through the bits of the calculated hash, you can determine which bits are and aren't in the private key. It takes some time to accomplish, and the network latency must be very low, but it is possible.

Re:Doesn't MD5 make this hard?

[tthomas48]

But in that case the user is supplying the hash, right?

Re:Doesn't MD5 make this hard?

[mandelbr0t]

True, but the basis of the vulnerability is the same: do not provide timing indications of success/failure if its possible to cycle and record to deduce the password. I'm not saying it's not possible to invent a login mechanism that doesn't have this particular vulnerability, just that it's not something even security-concious people immediately think of.

Re:Doesn't MD5 make this hard?

[Anonymous Coward]

You're correct.

I wouldn't be using MD5 though, it's weak and has been "broken" (ie. it can be reversed most of the time). SHA-1 or better is required these days.

Re:Doesn't MD5 make this hard?

[tthomas48]

But the problem isn't success/failure. It's differences of timing in failure, that tell how successful you were. It's basically like that old game of mastermind, but rather than colored pegs you're getting different times for your failure message.

Re:Doesn't MD5 make this hard?

[owlstead]

If the library is not using a salt, you can still retrieve the value of the hash using the exact same method. Furthermore, if the hash is intercepted they can use it for looking up the password in a rainbow table or similar. Just hashing is not enough.

Re:Doesn't MD5 make this hard?

[BitZtream]

Yes, because by knowing you use an MD5 hash, they can start attaching with known 'passwords' that generate 'known hashes'.

Since the check on the hashes by mysql is likely a simple string compare they can effectively compare which parts of the hash match and work backwards, one char at a time to find a matching hash.

Then its nothing more than generating a md5 hash to match the one you now know to work. Its rather complicated, but hashing doesn't make it impossible, just a little slower.

Re:Doesn't MD5 make this hard?

[tthomas48]

Right, but that's only if I'm exposing the hash, correct? My implementation takes the password, encodes it on the server and does a db lookup. The actual md5 hash is not reported to the user or stored in a cookie.

Re:Doesn't MD5 make this hard?

[owlstead]

It hasn't been broken yet for this kind of purpose, but I would go and recommend SHA-2 256 for new protocols, as there is a chance that new attacks may translate to new attacks on SHA-1. SHA-2 is based on similar principles, but it is certainly more complex to crack. Basically many "broken" hash algorithms can still be used for key derivation, password protection (basically any scheme that poses severe restrictions on the input). It is of course much safer not to rely on broken hash functions at all.

Re:Doesn't MD5 make this hard?

[Anonymous Coward]

If you read the article (and the link to the xbox story) you'll see that what this is doing is talking about figuring out auth hashes, not passwords.

A typical OAuth dance goes as such:
1) Get request token
2) Redirect to login page with token + stuff
3) Login
4) Redirect to logged in page (off original host)
5) Send request token and get back and auth token
6) Do whatever you like, sending a signed request using the auth token.

It's the last step you need to worry about; when you send a request you send along a series of params and a magical oauth_signature value.

Now, assume your server does this:

Steps 1-K) Build oauth_signature (takes time T)
Step K+1) Compare oauth_signature to expected oauth_signature (stops on first non-matching char; takes time ? * number of matching characters)

It's that last step which is the problem; if the the first character of the oauth_signature and expected signature don't match, it'll return a failure straight away. However, if the say, the first ten characters are right, and then one is wrong, it'll return fractionally later.

Now you can iterate over the oauth_signature hash and build up a correct hashed value one character at a time until you have a valid hash. Then the server will accept it and perform the operation.

In this case it doesn't leave you with an oauth_token_secret to make other requests, but the fact remains a bogus request is executed.

The novel thing these guys have done is show that you can use this sort of attack over a network, by somehow predicting network latency or something.

In your case, it depends on what exactly you're library is doing. If it takes a consistent time to perform a request (fetch a db hash) and then it compares it to a cookie or param, you'll find the same issue is present. I'd take a stab in the dark and say php sessions could be hacked pretty easily this way.

Why the fuzz?

[sandertje]

As said, it takes only a few lines of code to fix this "bug". Not really hard. Just set a fixed amount of time for the response. Besides:

The researchers also found that queries made to programs written in interpreted languages such as Python or Ruby -- both very popular on the Web -- generated responses much more slowly than other types of languages such as C or assembly language, making timing attacks more feasible. "For languages that are interpreted, you end up with a much greater timing difference than people thought," Lawson said.

Is there any situation where interpreted languages are actually faster than said other languages? ;-)

Re:Why the fuzz?

[maxume]

The sarcastic answer is development.

Re:Why the fuzz?

[gringer]

Is there any situation where interpreted languages are actually faster than said other languages? ;-)

The sarcastic answer is development.

I'd say that both development and debugging are easier / faster with high[er] level languages — interpreted languages are usually higher level than compiled languages. Therefore, python/ruby should be faster than C (for development/debugging), but something like dylan (both high level and compiled) would be faster than python/ruby.

FUD

[Anonymous Coward]

Move along people there's nothing to see here...

Not like xbox 360

[Anonymous Coward]

There is a difference between this type of timing attack and the timing attack used on the xbox 360/smart cards. In both cases, the attacker is submitting a key, and waiting to see how long it takes to process that key. The xbox 360 is a closed system, and the attacker has control over every aspect of the system (in the sense of a controlled scientific experiment). He can easily do the attack over and over, and be able to make it so that only the key changes. Something like OpenID is on the internet, though, and the attacker can't control every single aspect of the system he's attacking. There are numerous reasons why one key will take a different amount of time, with the server load and network load constantly changing. It is impractical to measure the difference of a couple of cpu cycles when there is so much noise.

The only way this will succeed is if these people have come up with a different technique to do the timing attack, but you still shouldn't compare them to people that are attacking a device sitting on their bench. The only thing that I can think of is submitting the same password hundreds or thousands of times, and averaging the amount of time. I'd think that this would appear to be a denial-of-service attack.

Re:Not like xbox 360

[crow_t_robot]

The only thing that I can think of is submitting the same password hundreds or thousands of times, and averaging the amount of time. I'd think that this would appear to be a denial-of-service attack.

This would be the way to do it. Just spread the attempts out over a week to not DoS and get a good cross-section of different network congestion times. Considering that OpenID is a "single point of failure" spending a week cracking a password is definitely worth it to get access to a ton of sites for one user ID.

Re:Not like xbox 360

[owlstead]

It seems that it is more and more feasible to do time based attacks even over something like the internet. It becomes even easier if such applications are ported over for use in corporate intranet environments of course. Firewalls can be fooled, e.g. by using multiple IP addresses quite easily. It is not very smart (and even dangerous) to rely on other security protection mechanisms if you can quite easily fix it in the application itself anyway.

So don't think that time based attacks are only feasible if you've got the hardware in your hands. They are not, they may not even be harder for the attacker who can simply rely on automation and a good statistical library to do the hard work.

Oldest technique?

[solidex]

Wow, I remember reading something about a similar technique once. In an old text file written by some 80s hacker group. Or maybe it was that awful "Secrets of a Super Hacker" book. Either way, this HAS to be one of the oldest techniques known to anyone.

The researchers plan to discuss their attacks

[countertrolling]

Do they have "permission"? Or will somebody come along and tell them they can't discuss it?

No.

[roguegramma]

Adding a random delay doesn't help. Just send in the request 100 times and take the average time.

Re:No.

[jeremyp]

But the account gets locked after the third wrong attempt to log in.

Re:No.

[roguegramma]

Quoted from the blurb: "By trying to log in again and again, cycling through characters and measuring the time it takes for the computer to respond".

You need more than one attempt to make a timing attack, too.

Seriously?

[FranTaylor]

Are you serious?

In the course of an entire web session's worth of CPU consumption, you are worried about the time taken to compare password characters? Any modern optimized processor should require one clock cycle per character.

Do you actually profile your code or do you just make funny noises? Or maybe you're running your web server on a Commodore 64?

Re:Seriously?

[Galestar]

ditto parent. talking about "wasting" 6 cycles on a one off event (non-loop) is ludicrous.

Re:Seriously?

[disambiguated]

Compiler-optimized code on a 64 bit machine compares 8-bit characters 8 at a time. This guy is trying to force a context switch (upwards of thousands of instructions) to save 4 or 5 instructions. It doesn't save CPU (because of the context switch), it increases the latency, it's harder to code, and may be still vulnerable! sweet.

Re:Seriously?

[Anonymous Coward]

The part that's even more ridiculous then worrying about the amount of time to compare the whole string, (especially when you consider it would be comparing the whole thing anyways were it the correct password) is that he's completely ignored the cost of a context switch. I'd say it's pretty massive compared to comparing a few characters...

Re:Seriously?

[owlstead]

ON MODERN CPU'S THAT ARE RUNNING A COMPLETE WEB-SERVICE, YOU DON'T CARE, NOT EVEN ABOUT THE FUCKING CONTEXT SWITCH. 1990 CALLING, THEY WANT THEIR ASSEMBLY LEVEL OPTIMIZATIONS BACK.

Yea gods, does this hole thread consists or idiots or what?

OpenID, OAuth, and all the rest

[Anonymous Coward]

How secure can any homogenous security system really be? I want to use a different login, password, and backend security mechanism on every single site that I have an account on.

Account lookup attempts?

[Anonymous Coward]

Wouldn't locking out the account after X invalid attempts just block this anyway?

first side channel attack I learned

[owlstead]

This was the first time-based side channel attack I learned. Within Minix you initially could place a password right at a page boundary and try and login. If there was a page fault before the password was rejected, you knew you had the right character right before the page bound. Of course, the solution is very simple: check all the characters for correctness, simply setting a boolean to false each time you find an incorrect character. Probably even better is to pad the input to a maximum length (in a time independent way), use a hash and always test the all the bytes in the hash.

Adding delays is costly and unnecessary, outside the fact that you might still detect something since the average random delay is probably a constant. Don't forget that these attacks already rely strongly on statistics. One thing that you can easily do with an online system is to add a delay after a bad attempt. If you add enough delay, a statistical attack may take simply too long a time (make sure sure you don't aggravate your users until they get a heart attack). Obviously, on an online system, you cannot *just* set a maximum amount of retries without handing a DoS attack to attackers.

Preventing side channels attacks is hard, and don't get illusions that they can be easily discarded because they are impossible to implement. They can be implemented and with the current state of cryptography, they are the one of the weakest points in many security protocols and algorithms. Within the SHA-3 competition it is definitely one area that is getting attention.

Re:first side channel attack I learned

[owlstead]

That's what you get from using an outdated college lecture as starting point. Of course, as already mentioned in the responses, the correct way is to have a full length random salt, XOR the password in it (in case the RNG is broken, possibly use an additional counter or something), hash it and then send the salt & hash to the other side. Sending the password in plain or relying just on SSL is a stupid idea for an online system.

Re:first side channel attack I learned

[Guy Harris]

This was the first time-based side channel attack I learned. Within Minix you initially could place a password right at a page boundary and try and login. If there was a page fault before the password was rejected, you knew you had the right character right before the page bound.

That dates back before Minix - Butler Lampson's Hints for Computer System Design speaks of a similar issue in Tenex. (Look for "Tenex" in that paper for the example.)

Re:first side channel attack I learned

[__aaxtnf2500]

I believe you are confusing MINIX with TENEX due to the fact that the author of MINIX wrote a commonly used text, "Modern Operating Systems", and contains a short section with diagram on the TENEX page faulting password attack.

Re:first side channel attack I learned

[owlstead]

Ah, that could well be, thanks for the correction. My memory is starting to get a bit murky on the details after 15+ years :)

... so?

[Anonymous Coward]

post a news story when an authentication scheme which /doesn't/ invite users to type their usernames and passwords into dozens of random websites is broken.

Re:... so?

[Stewie241]

post a news story when an authentication scheme which /doesn't/ invite users to type their usernames and passwords into dozens of random websites is broken.

The point of OpenID is that you *don't* type your password into dozens of random websites.

For the uninitiated...

[ThoughtMonster]

http://bash.org/?5775

Otherland FTW

[Gothmolly]

Even Dread's killer gear was vulnerable to timing attacks. Of course he had a two-factor text&speech combination that the (arguable) heroine managed to get just by accident, but still - vulnerable to a timing attack.

Facebook

[Sergeant Pepper]

In addition to the listed sites, I believe Facebook's Connect API uses OAuth for authentication... that's a LOT of users...

Xbox 360? A better example!

[VGPowerlord]

A better example from the past of this same sort of attack was back in OpenSSH Portable. Specifically, OpenSSH/PAM timing attack allows remote users identification

Note that this didn't apply to finding passwords, just that invalid users would immediately return an error after the password was entered, while a valid user and incorrect password would have a delay.

Would you ike to play a game?

[damonlab]

I always thought a big flaw in the movie War Games was that the launch code was figured out one character at a time. Now this happens and flips my world upside down.

Re:Would you ike to play a game?

[Anonymous Coward]

This used to be a standard way of cracking Windows shares on a network, circa 1998-1999 and earlier.

Re:Would you ike to play a game?

[omglolbah]

Win98 was vulnerable, and I loved it. I could loot anything I wanted :p

Then winxp came out and wasnt... *pout* ;)

Hm, my BS alarm...

[Stan Vassilev]

The researchers also found that queries made to programs written in interpreted languages such as Python or Ruby -- both very popular on the Web -- generated responses much more slowly than other types of languages such as C or assembly language, making timing attacks more feasible. "For languages that are interpreted, you end up with a much greater timing difference than people thought," Lawson said.

Sure, scripts are slower than C. They're slower in general, but when you compare two binary strings, it's still mostly the same C memcmp call that's being called. You also have semi-random events like mark and swipe garbage collection, dynamic optimizations, I/O delays.

This means scripts may be slower and more random, while the password check call still isn't, how the heck would that make is easier to hack scripted sites?

I'm not even mentioning the fact most web apps don't have passwords hardcoded, but actually do the check in an external agent, say SQL database, making his observation even less logical.

He claims he can filter out all those variables, including network jitter and pinpoint the exact time of some ASM-level operation on a string. I say, show us.

What the heck?

[selven]

On some login systems, the computer will check password characters one at a time, and kick back a "login failed" message as soon as it spots a bad character in the password.

Why the hell are they checking against the password in plaintext, and not some kind of hash?

Re:What the heck?

[bipbop]

The article is bad. They're actually attacking the HMAC, not the cleartext password. http://lists.openid.net/pipermail/openid-security/2010-July/001156.html

Timing attacks have been proved real

[Anonymous Coward]

crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

You only need one

[Rithiur]

Are there still sites out there that don't do this? Really?

Unfortunately, yes.

So a secure comparison algorithm would be..

[droidix55]

Say you have two hashes

1. break each into an array of integers, create a result array with the same size
2. XOR the two arrays containing the hashes into the result array
3. OR all of the ints in the result array together
4. if the result is 0 then the authentication is successful

Would that work?

I don't buy this

[seanadams.com]

but I would love to see their presentation. It kinds of reminds me of people who think the length of their speaker cables is going to affect their sound stage, because they have no concept of the speed of sound vs an electrical field.

If you were comparing plaintext passwords with strcmp you might expect something on the order of one character comparison per instruction cycle, say 1ns. But across the internet latency variance is very noisy and more like 1ms standard deviation, ie a million times larger. I'd expect you'd have to average billions of tests against each attempted character before that one little nanosecond comes out of the noise, if it's even detectable at all. Most likely there are slower clock domains along the way that will gobble it up completely.

I could imagine in a spectacularly well controlled lab environment with no other traffic on the lan and no other activity on the server, this might be demonstrated, but there's just too much jitter in any production system to do this.

Of course none of this excuses such a braindead authentication scheme. Use a hash!

fix:

[hellop2]

sleep(rand());

Oh, another BlackHat story, ahahaha

[X.25]

Hey look, another advertisement for irrelevant business gathering called "Blackhat".

Considering the quality and technical depth of presentations announced so far, I expect next presentation to be a shocking discovery about users choosing weak passwords.

Well done Businesshat.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Answer to brute force attacks

[hicksw]

Three strikes. If the bot can't guess the password in a few attempts, it is not a sober user on a good connection. Lock the account and make them beg for reconnection via their known email address or some such.

This is VERY old technology.
--
The alternative to trial and error is usually error.

Re:Answer to brute force attacks

[Ant P.]

So in your system, I could lock you out of the site simply by doing a bad login on your username three times? Nice.

Re:Answer to brute force attacks

[John Hasler]

The attackers have tens of thousands of bots attacking tens of thousands of accounts. They can afford to wait long enough between attacks on any given account that there is a good chance that the real user will log in and reset the bad login counter. Sure, they'll get locked out of a lot of accounts, but so what? The legit user will just curse and jump through whatever hoops he needs to get it unlocked and in the meantime there's another 9999 accounts to work on. They expect to fail to get into most of the accounts anyway.

Re:Answer to brute force attacks

[ymgve]

Have timing measurements ever been exploited online in practice? I would assume that over the internet, any difference in timing would get drowned out in the timing noise of a dozen routers, switches, heck, even possibly cable quality - making any reliable measurement impossible.

don't want to act picky ...

[freaker_TuC]

But .. get about 100 of such routines, unoptimized, and your program will slow down; for sure when there are multiple users involved with multiple access instances. Code optimizing is still a required part to keep a build clean, reliable and fast.

Comment removed

[account_deleted]

Comment removed based on user account deletion