[Improvement] More secure key derivation function

Issue 119 by zaolin.dais... on 2012-01-11 07:47:05:

Hi developers,

i know that cryptsetup uses PBKDF2 as key derivation function.
What is about the scrypt algorithm ? It uses two times PBKDF2 and a mixing function. It is more secure against bruteforce but a little bit slower as plain PBKDF2.

www.tarsnap.com/scrypt.html

I will implement it in cryptsetup if it is in demand.

Regards Zaolin

Comment by gmazyl... on 2012-01-11 08:08:00:

Owner: gmazyland

I have nothing against it but please first write to the dmcrypt mailing list and explain why do you think PBKDF2 is not secure (in the cryptsetup case)

Please note the specific use case in LUKS vs plain crypt.

I would like to also see some formal analysis for this use case.

Do you mean it is as alternative to plain crypt (IOW real key derivation function) or also for LUKS (here it is used also for key digest)?

LUKS spec is here
http://code.google.com/p/cryptsetup/wiki/Specification
some visual schema of PBKDF2 use is here
http://mbroz.fedorapeople.org/talks/Europen2011/img21.jpg

Comment by gmazyl... on 2012-01-11 08:08:38:

Labels: Type-Defect, Type-Enhancement

(No comment has been entered for this change)

Comment by Yas... on 2012-01-20 07:55:47:

Even wikipedia points out that you can create a system for around $5000 (cheap if you are a big company or maybe a government) that can try 300,000 keys/second on a PBKDF2 function that has been applied 65536 times, and that that same system on can try 20,000,000,000 keys/second on a straight (non-PBKDF2) SHA-1 hash! That is ridiculous!

And then it goes on to say "In 2009, a new key strengthening algorithm, scrypt, was introduced that demands large amounts of memory to evaluate, limiting the use of custom, highly parallel hardware to speed up key testing."

The article is here: https://en.wikipedia.org/wiki/Key_stretching

To me, it sounds like this is going to become a necessary thing to implement in to LUKS. It makes it feel like PBKDF2 isn't really strong at all in some cases. Or am I over-reacting?

Comment by gmazyl... on 2012-01-20 09:20:28:

Please send it to list for discussion, not here.

Comment by hvtaifwkbgefb... on 2013-04-24 22:21:16:

LUKS2 spec needs to have field for specifying the algorithm used for password-based key derivation function, then. I can't edit the wiki page.

This competition is supposed to end in 2015..:
https://password-hashing.net/

Comment by gmazyl... on 2013-04-25 05:36:23:

Yes, adding field for KDF in future it the plan. (I will update LUKS2 page some day, there is more features.)

Comment by gmazyl... on 2013-06-28 18:44:55:

Issue #163 (closed) has been merged into this issue.

Comment by cales... on 2013-06-28 19:17:55:

One idea would be to combine both methods to use then strengths of each of them.

Comment by WaywardG... on 2015-02-22 15:44:02:

I support going with the PHC winner, assuming the PHC is reasonable and picks either Lyra2 or Yescrypt, which I think they will. However, in the meantime, I think it would be great to upgrade LUKS to support Scrypt. The code required changes are not substantial, and the benefit is great. This would put LUKS in a good position to adopt the PHC winner in 2016.

On my laptop, LUKS uses 200 ms of PBKDF2-SHA1(39,500). For GPU defense, this isn't bad, but against an ASIC attack, I estimate that an attacker would have to pay about 3,600 times more to guess a 200 ms Scrypt hash, and the difference is proportional to the runtime. A 2 second Scrypt hash would be about 36,000 more expensive to crack.

This is a bit of a WAG, but an advanced ASIC with 350 GiB/s bandwidth to GDDR5 memory is close to state of the art. The ASIC wont be cheap, nor the memory, so I guestimate $1,000 per guessing unit with a 4 year useful life. Scrypt does roughly 1 GiB/s hashes on current machines, or about 2 GiB/s of DRAM bandwidth. A 200 ms hash would use about a 200 MiB of memory and 400 MiB of bandwidth (one write, one read). This ASIC could do about 875 guesses per second.

In contrast, PBKDF2-SHA256(39,500) is crackable with BitCoin mining-like hardware, which can do 1 GH/s for $1 in hardware. Power dominates the cost by maybe 3X, so call it $4 per GH/s for a 4-year life. For $1,000 like above, we can do 250 GH/s over 79,000 (2 hashes per HMAC) = 3,616 times faster for the same money.

If you like, I would be happy to provide an Scrypt patch. It looks pretty straight forward to me.

Comment by gmazyl... on 2015-02-22 18:13:51:

Hi Bill,

I plan to run some comparison of PHC 2nd round candidates soon (maybe directly with cryptsetup example use case). And yescrypt can be run in scrypt compatible mode so it covers it as well.

I do not think implementing solely scrypt for cryptsetup now helps anything. I would definitely prefer that someone will push PHC winner implementation(s) into crypto libraries - at least to gcrypt and openssl.

Anyway, the change will not reach stable cryptsetup until we have some kind of standard (in the form of PHC winner at least). Also there is a lot of compatibility issues when changing KDF (actually the side issues are much more problematic than writing patch:-).

But I will definitely welcome code review when we have some code!
(I guess KDF testing branch will appear during next few months.)

For others not familiar with PHC: I played with PHC candidates here, plan is to continue with this effort, see http://htmlpreview.github.io/?https://github.com/mbroz/PHCtest/blob/master/output/index.html

Comment by waywardg...@google.com on 2015-02-23 16:02:15:

I remember your excellent work on automated testing and benchmarking of PHC
candidates. I have to say, I feel better knowing you're in the loop on
this with LUKS.

The side-issues always seem to be the biggest problem. Are they mostly
upgrade issues, or also format issues? TrueCrypt does not encode the
format in their header (on purpose), so adding Scrypt is problematic in
that they have to try all legal hashing combos, and if Scrypt, Yescrypt,
and other very compute intensive hashes become legal, they would slow down
too much.

One reason I am asking is that we may not have these side issues in
Goobuntu. I would like to know if it might make more sense to move ahead
to more modern hashes in Goobuntu now, or if there are good reasons to hold
back.

Very nice to see you here!

mentioned in issue #1 (closed)

Reassigned to @mbroz

mentioned in issue #253 (closed)

mentioned in issue #263 (closed)

Argon2 which is the winner of the PHC should be used.

+1 for Argon2.

https://github.com/P-H-C/phc-winner-argon2

Or you could port libsodium's code: https://github.com/jedisct1/libsodium/tree/master/src/libsodium/crypto_pwhash

Cryptsetup2 (LUSK2) now have Argon2i/Argon2id support, please try it. Testing release release notes: https://www.kernel.org/pub/linux/utils/cryptsetup/v2.0/v2.0.0-rc0-ReleaseNotes

closed