PBKDF2 iterations need to be far higher

[theontho]

I first ran into this issue investigating arq's crypto here: arqbackup/arq_restore#7

Currently we have iterations = 100000 (see key.py) , which is a pretty low number. According to my tests with a calibration function, that number should be x7.8 to x78 times higher.

I would suggest immediately raising the number of iterations to be around 1'000'000 times initially and giving an option to make the number of iterations to be 100'000'000, and then storing that generated key somewhere so people don't have to wait 7s for every borg command to execute.

I made a bit of test code to figure out what the number of iterations should be on a macbook pro 13" (2.6 GHz Intel Core i5) :

#import <CommonCrypto/CommonCrypto.h>

- (void) testSuite
{
    [self testForMsec:500];
    [self testForMsec:1000];
    [self testForMsec:2000];
    [self testForMsec:5000];
}

- (void) testForMsec:(uint32_t)msec
{
    NSString* strongPassword = @"I make aodso f  sadfoijo###ijfoj oiwej foawejf oiawe 28";
    NSString* password = @"weakPassword393";
    NSLog(@"msec: %d",msec);
    NSLog(@"strong:\t%d",[self roundsForPassword:strongPassword forMilliseconds:msec]);
    NSLog(@"weak:\t\t%d",[self roundsForPassword:password forMilliseconds:msec]);
}

- (uint) roundsForPassword:(NSString*)password forMilliseconds:(uint32_t)msec
{
    NSString* saltStr = @"01bd79c7219926ecad1216a224ee0fe77c82a3ea4addb7a18ad12009166d0e1e"; //a repo id
    NSData* salt = [saltStr dataUsingEncoding:NSUnicodeStringEncoding];
    uint rounds = CCCalibratePBKDF(kCCPBKDF2,
                                   [password length],
                                   [salt length],
                                   kCCPRFHmacAlgSHA256,
                                   CC_SHA256_DIGEST_LENGTH,
                                   msec);
    return rounds;
}

I got these results:

 msec: 500
 strong:    781250
 weak:      769230
 msec: 1000
 strong:    1587301
 weak:      1515151
 msec: 2000
 strong:    3030303
 weak:      3174603
 msec: 5000
 strong:    7812500
 weak:      7812500

[ThomasWaldmann]

Well, I basically agree with what you're saying, so just some additional comments:

a) We need to redo your performance tests in python 3.2+ / with the python stdlib calls as used by borg.

b) I think this is yet another case of a hardcoded value that does not fit everybody's needs. With a recent i5, you'ld want much more than the hardcoded value, while on an old machine or on a raspberry pi, 100.000 might already mean the maximum of an appropriate wait time (and more might be too slow for interactive use).

c) Storing the pbkdf2 output somewhere is as bad as storing the password somewhere.

d) Having a configurable value for the iterations first and a calibration function later might be a good idea.

e) We can not change the iterations for the passphrase-only mode [at least not for existing repos], it would break existing repositories. But I'm going to deprecate this mode anyway, you also can not ever change the passphrase. Both is just crap.

[ThomasWaldmann]

On my machine, using the pbkdf2_sha256 from openssl (as borg does), the current iterations count (100.000) takes approximately 0.1s, so yes, 1.000.000 would be better for this machine.

I tried it on a raspberry pi2 also - there 100.000 iterations take 1.4s. So, 100.000 is fine for there, from a usability standpoint.

So, what's left as an option is to make it configurable for the users who want to deviate from the default.

About auto-calibration: the user of a fast machine could say "I want to waste 3s for pbkdf2" and it could automatically adjust iterations so it is about 3s. BUT: that's only true for this machine. If you backup to same encrypted repo with a much slower machine, you might also wait 100s for pbkdf2 to compute.

[ThomasWaldmann]

Note: using bcrypt or scrypt might be another option.

[ThomasWaldmann]

e) might be solved when dropping passphrase mode (see #97). So reconsider this ticket when we do that.

[Safari77]

Instead of scrypt, I'd like to see Argon2
https://github.com/P-H-C/phc-winner-argon2.git

[ThomasWaldmann]

@Safari77 interesting, they even have a python binding and a pypi package:

https://pypi.python.org/pypi/argon2

but we have to be careful about dependencies - if we can't get what we need as dependency from existing (linux or other) packages, that will block us having a package until the dependency is resolved also. This is especially a problem with brand new stuff.

[theontho]

1password has a great article on pbdkf2:
https://support.1password.com/defense-against-crackers/

They have several other good articles on other security engineering topics on their support pages.  I suggest checking it out.

[ThomasWaldmann]

@mahyar citing from the article:

"Once you reach a certain number of PBKDF2 iterations, you get much more bang for your buck from a small improvement in your Master Password than from a large increase in PBKDF2 iterations."

That sounds very reasonable. Especially when considering that using a high value (no matter whether determined by calibration or configuration) might be unsuitable for much slower machines accessing the same repository, rendering any calibration rather useless.

So, considering we are already at 100.000, how about users who want more security against brute force cracking just use a longer/better passphrase and do not crank up the iterations?

[jungle-boogie]

I like the idea of bcrypt and perhaps 500,000 iterations?

[ThomasWaldmann]

@jungle-boogie I know bcrypt, scrypt and meanwhile also argon2, but such a change won't happen for 1.0 (which is rather soon).

So the question, as the ticket title says, is for now just whether we keep 100.000 pbkdf2 iterations or do increase the number. I currently tend to keep it (see above), as a big increase would be an annoyance on slow machines and a small increase (like 2x) might be a bit pointless.

[ThomasWaldmann]

closing this. we keep pbkdf2 iteration count as is for now.

if you want better security / stronger defence against brute force attacks, use a longer passphrase as suggested in one of the articles linked aboved.