[cryptography] PBKDF2 + current GPU or ASIC farms = game over for passwords (Re: TLS2)

Adam Back adam at cypherspace.org
Mon Sep 30 11:43:41 EDT 2013

On Mon, Sep 30, 2013 at 02:34:27PM +0100, Wasa wrote:
>On 30/09/13 10:47, Adam Back wrote:
>>Well clearly passwords are bad and near the end of their life-time with
>>GPU advances, and even amplified password authenticated key exchanges like
>>EKE have a (so far) unavoidable design requirement to have the server
>>store something offline grindable, which could be key stretched, but thats
>>it.  PBKDF2 + current GPU or ASIC farms = game over for passwords.
>what about stronger pwd-based key exchange like SRP and JPAKE?

what I mean there is a so far unavoidable aspect of the AKE design pattern
is that the server holds verifier v = PBKDF2(count,salt,password), so the
server if hostile, or of even more concern an attacker who steals the whole
database of user verifiers from the server can grind passwords against it. 
There is a new such server hashed password db attack disclosed or hushed up
every few weeks.

>Passwords don't scale up and are very inconvenient, but are you sure your
>argument "PBKDF2 + current GPU or ASIC farms = game over for passwords"
>really holds?  what about scrypt?  And theoretically, you can always
>increase the number of rounds in the hash...  I refer to this link too:

You know GPUs are pretty good at computing scrypt.  Eg look at litecoin
(bitcoin with hashcash mining changed to scrypt mining, people use GPUs for
~10x speed up over CPUs).  Litecoin was originally proposed as I understood
it to be more efficient on CPU than GPU, so that people could CPU mine and
GPU mine without competing for resources, but they chose a 128kB memory
consumption parameter, and it transpired that GPUs can compute on that
memory size fine (any decent GPU has > 1GB of ram and a quite nice cacheing
hierarchy).  Clearly its desirable to have modest memory usage on a CPU or
if it fill L3 cache the CPU will slow down significantly for other
applications.  Even 128kB is going to fill L1 and half of L2 which has to
cost generic performance.  Anyway in the bitcoin context that coincidentally
was fine because then FPGAs & ASICs became the only way to profitably mine
hashcash based bitcoin, and so GPUs were freed up to mine scrypt based
litecoin.  Also for bitcoin purposes higher memory scrypt parameters
increase the validation phase (where all full nodes check all hashes and
signatures, a double SHA256 is a lot faster than a scrypt at even 128KB,
changing that to eg 128MB will only make it worse.

Also the PBKDF2 / scrypt happens on the client side - how do you think your
ARM powered smart phone will compare to a 9x 4096 core GPU monster.  Not
well :)

So yes I stand by that.  One could use higher memory scrypt parameters, and
so the claim goes with memory bound functions that memory IO is less
dissimilar between classes of machines than CPU speed (smartphone vs GPU).
However you have to bear in mind also that scrypt actually has CPU memory
tradeoffs, known about and acknowledged by its designer.

I believe its realtively easy to construct a tweaked scrypt that doesnt have
this problem.

Also for the bitcoin/litecoin side of things I heard a rumor that there were
people working on a litecoin ASIC.  Bitcoin FTW in terms of proving the
vulnerability of crypto password focussed KDFs to ASIC hardware.  The scrypt
time memory tradeoff issue maybe useful for efficient scrypt ASIC design.

But there is a caveat which is the client/server imbalance is related to the
difference in CPU power between mobile devices and server GPU or ASIC farms. 
While it is true that moore's law seems to have slowed down in terms of
clock rates and serial performance the number of cores and memory
architectures are still moving forward, and for ASICs density, clock rates
and energy efficiency are increasing, and thats what counts for password
cracking.  But yes the longer term picture depends on the trend of the ratio
between server GPU/ASIC performance vs mobile CPU.  Another factor also is
the mobiles are more elastic (variable clock, more cores) but to get full
perf you end up with power drain and people dont thank you for draining
their phone battery.  It is possible for ARM eg to include an scrypt or a
new ASIC unfriendly password KDF on the die perhaps if there was enough
interest.  The ready availability of cloud is another dynamic where you dont
even have to own the GPU farm to use it.  You can rent it by the hour or
even minute, or use paid password cracking services (with some disclaimer
that it better be for an account owned by you).

Anyway and all that because we are seemingly alergic to using client side
keys which kill the password problem dead.  For people with smart phones to
hand all the time eg something like oneid.com (*) can avoid passwords (split
keys between smart phone and server, nothing on server to grind, even stolen
smart phone cant have its encrypted key store offline ground to recover
encrypted private keys (they are also split so you need to compromise the
server and the client simultaneously).  Also the user can lock the account
at any time in event of theft or device loss.


(*) disclaimer I designed the crypto as a consultant to oneid.

More information about the cryptography mailing list