Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

My question is related to PBKDF2. I am unsure how to validate user entered password with already existing hashes and salts.

I have heard of the so called "length-constant" comparison which basically ensures that every byte is being compared rather than a simple string comparison. And this is part where I am confused about. When deriving a key using for example "Hello" as password and "Hello2" as salt the output of PBKDF2 will always be the same. So why is there a slow equals (length-constant) comparison method?

What is the correct way of validating passwords in PBKDF2?

share|improve this question
1  
For password hashes a constant time validation isn't that important, especially for attackers who don't know the salt. It's merely good style to use it. For MAC validation it's far more important, since a timing leak would allow construction of a valid MAC. –  CodesInChaos Feb 25 at 13:00

2 Answers 2

up vote 2 down vote accepted

If the resulting hashes were the same, a non length-constant check would compare every byte of the resultant digest. This would take the most time to compare.

Lets say it takes 90.00ms to run the KDF, and 0.90ms to do a full length compare (not real numbers but good enough for the example)

If the password was "hello" instead of "Hello", it is probable that the digest will have a different first or 2nd byte, which means a comparison would determine they are different much faster than if they were the same. Instead of 90.90ms, it may take 90.10ms.

If the attacker is capable of measuring the cpu usage or cpu power draw, they may be able to measure the quantity of keystrokes, giving the attacker the length of the correct password. They may also be able to compare the time it takes between key presses to better determine what combination of key presses was entered. The attacker may be able to get much more information that that, maybe less, but every bit of information the attacker gets will help them attack the KDF and recover the password. Knowing that a specific combination is correct is a huge amount of information.

This is why constant time comparisons are so important, because it is extremely easy to put in bogus passwords and get a timeframe of how long it takes to compare incorrect results, so when the correct result is compared it will take longer, and be detected by whatever mechanism (software or hardware) is measuring them.

share|improve this answer

I would have made this a comment, but I don't have enough reputation points.

I think this is a good question. I don't see how a timing attack could be done in any practical manner. I ran a quick test on two 256 bit/32byte keys I generated. I did a simple "for" over them, comparing each character. Here are the results of my testing.

    LAST BYTE DIFFERENT:
    Comparing hex representations of the keys (64 characters)
        k1:     2F5F587E5057C152F8A0F7CCE30ECDC0B26D45721E6FA538AE6AD0D31D478346
        k2:     2F5F587E5057C152F8A0F7CCE30ECDC0B26D45721E6FA538AE6AD0D31D478340
        The same?:  False
        Start time: 15:18:06.3867623
        End time:   15:18:06.3867623
        duration:   00:00:00 (0ms)

    Comparing byte arrays (32 bytes)
        The same?:  False
        Start time: 15:18:06.3877624
        End time:   15:18:06.3877624
        duration:   00:00:00 (0ms)   


    FIRST BYTE DIFFERENT:
Comparing hex representations of the keys (64 characters)
    k1:     2F5F587E5057C152F8A0F7CCE30ECDC0B26D45721E6FA538AE6AD0D31D478346
    k2:     1F5F587E5057C152F8A0F7CCE30ECDC0B26D45721E6FA538AE6AD0D31D478346
    The same?:  False
    Start time: 15:20:42.1843405
    End time:   15:20:42.1843405
    duration:   00:00:00 (0ms)

Comparing byte arrays (32 bytes)
    The same?:  False
    Start time: 15:20:42.1853406
    End time:   15:20:42.1853406
    duration:   00:00:00 (0ms)

I'm not seeing any difference in compare times. It's instantaneous, as far as I can tell. Even if there was a fraction of a millisecond different, am I wrong in thinking that the normal variance in network response times would nullify the differences in compare times?

Also, each run of PBKDF2 does not take the exact same amount of time, in my testing, even with identical parameters. See the following 4 PBKDF2 runs with identical parameters, and very different calculation times:

SALT:   ndlD7w4CAW1EcoHCLxwhxg==
ITER:   100000
PASS:   v/iFo8ZAjmG3q/9/8/oGwAWCcdY=
START:  10:16:59.2283073
END:    10:16:59.6813526
MS:     453.0453


SALT:   ndlD7w4CAW1EcoHCLxwhxg==
ITER:   100000
PASS:   v/iFo8ZAjmG3q/9/8/oGwAWCcdY=
START:  10:16:58.4052250
END:    10:16:58.8672712
MS:     462.0462

SALT:   ndlD7w4CAW1EcoHCLxwhxg==
ITER:   100000
PASS:   v/iFo8ZAjmG3q/9/8/oGwAWCcdY=
START:  10:16:57.6161461
END:    10:16:58.0771922
MS:     461.0461


SALT:   ndlD7w4CAW1EcoHCLxwhxg==
ITER:   100000
PASS:   v/iFo8ZAjmG3q/9/8/oGwAWCcdY=
START:  10:16:56.7020547
END:    10:16:57.1611006
MS:     459.0459

If you are concerned with these sort of timing attacks, my suggestion would be to do your normal PBKDF2 checking and get the result of the check doing a normal (non-slow) compare. Then generate a pseudo-random number (RN) between 500 and 3000 (for example). Run another PBKDF2 on random data for RN iterations. That would randomize the response times nicely, I think. Does anyone have a different thought on this?

NOTE: All testing done on an i7 processor using standard C#/.NET implementations.

NOTE2: I'm assuming we're talking/concerned about an internet login where the attacker doesn't have physical access to the server to be able to measure power draw somehow.

share|improve this answer
1  
Primary languages where this attack is successful include javascript, php, perl, ruby... especially php. Also in Android/IOS apps where the app actually runs on the device, the cpu is much slower so things are easier to measure. –  Richie Frame Feb 24 at 20:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.