[Improvement] More secure key derivation function

[GoogleCodeExporter]

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

Original issue reported on code.google.com by zaolin.d...@googlemail.com on 11 Jan 2012 at 7:47

[GoogleCodeExporter]

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

Original comment by gmazyl...@gmail.com on 11 Jan 2012 at 8:08

[GoogleCodeExporter]

Original comment by gmazyl...@gmail.com on 11 Jan 2012 at 8:08

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

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?

Original comment by Yas...@gmail.com on 20 Jan 2012 at 7:55

[GoogleCodeExporter]

Please send it to list for discussion, not here.

Original comment by gmazyl...@gmail.com on 20 Jan 2012 at 9:20

[GoogleCodeExporter]

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/

Original comment by hvtaifwk...@gmail.com on 24 Apr 2013 at 10:21

[GoogleCodeExporter]

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

Original comment by gmazyl...@gmail.com on 25 Apr 2013 at 5:36

[GoogleCodeExporter]

Issue 163 has been merged into this issue.

Original comment by gmazyl...@gmail.com on 28 Jun 2013 at 6:44

[GoogleCodeExporter]

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

Original comment by calestyo@gmail.com on 28 Jun 2013 at 7:17

[GoogleCodeExporter]

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.

Original comment by WaywardG...@gmail.com on 22 Feb 2015 at 3:44

[GoogleCodeExporter]

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/outpu
t/index.html

Original comment by gmazyl...@gmail.com on 22 Feb 2015 at 6:13

[GoogleCodeExporter]

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!

Original comment by waywardg...@google.com on 23 Feb 2015 at 4:02