[148583] in cryptography@c2.net mail archive
Re: [Cryptography] Why don't we protect passwords properly?
daemon@ATHENA.MIT.EDU (Bill Cox)
Sun Dec 22 16:48:45 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <D6366674-E210-45CD-B2C4-D23ECB15C6E5@lrw.com>
Date: Sun, 22 Dec 2013 16:42:33 -0500
From: Bill Cox <waywardgeek@gmail.com>
To: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============6853323393286379339==
Content-Type: multipart/alternative; boundary=089e0116167e954a6a04ee2663fb
--089e0116167e954a6a04ee2663fb
Content-Type: text/plain; charset=ISO-8859-1
There were some very informative statements in the replies. Thanks for all
the history and background, and pointers to some cool technologies. Some
comments:
Jerry wrote: "That makes no sense. If you transmit the derived key, *it*
becomes the "real" key. "
There are several advantages over just sending the user's password to the
server. It offloads the server enabling more compute intensive KDFs. The
client side software is auditable by users, so we can verify the KDF is
done well, unlike the situation with servers like LinkedIn. Also, anyone
seeing a user's passwords in plain text is going to gain a great advantage
when trying to crack those passwords for other sites. They are often the
same, or only slightly different. This is how so many LinkedIn users had
their Google accounts hacked.
Still, those were some great links you and the others pointed out. Your
link to Secure Remote Password Protocol is very cool. It does KDF in the
client also. This is better than sending any password every time to the
server.
I'm just noodling, but could we enhance SRP to not rely only on the
discrete logarithm problem? I'm looking at SRP on wikipedia. They
describe the secret stored on the server is "v", which is computed by Carol
as g^x, where x is Carols derived key. V is essentially Carol's public
key, and x is her private key, enabling Steve to securely send a session
key to Carol even if a MITM attacker has Steve's hashed password file.
That's very cool, but if a MITM attacker doesn't have the hashed password
file, but does have a silly amount of compute power for computing discrete
logs, couldn't we thwart them simply by using v as a shared private key
during the session key exchange? When Steve sends his info to Carol, why
not AES encrypt it with v? That's all it would take.
On Sun, Dec 22, 2013 at 11:26 AM, Jerry Leichter <leichter@lrw.com> wrote:
> On Dec 21, 2013, at 11:46 PM, Bill Cox wrote:
>
> I don't understand why servers do the KDF rather than the client.
>
> There's an old joke: How could God create the entire universe in only six
> days? No installed base!
>
> It's also *so* easy to criticize yesterday's decisions based on today's
> knowledge and capabilities.
>
> KDF's used specifically to strengthen weak user passwords against
> brute-force attack were introduced as a quick way to strengthen *existing*
> systems with immense numbers of already-fielded clients. Requiring that
> the clients all change would be a perfect way to make sure nothing got
> improved.
>
> Keep in mind that the *original* purpose of "key hashing" was rather
> different: It was to keep passwords secure even when the password file (or
> logical equivalent) was leaked. Password hashing was introduced in early
> versions of Unix with exactly this primary purpose - and the secondary
> purpose of allowing anyone to verify a password by reading the public value
> from the file, hashing an incoming alleged password, and comparing. It
> took a number of years to learn that making even the hashed passwords
> public was a bad idea - and every Unix system in decades has had shadow
> password files. Web servers and such simply followed (often badly)
> existing "best practice": Unix password hashing was based on DES; they
> moved to more recent crypto standards. Of course, then they (the Web
> server community as a whole) screwed up the entire ecosystem by
> implementing such poor security that they repeatedly managed to lose huge
> databases full of millions of hashed passwords.
>
> The ability to do mass off-line attacks wasn't anticipated. Its success
> was based on the combination of several things that would have been hard to
> predict: Clever fast implementations of some of the primitives optimized
> for the purpose of password cracking rather than ordinary cryptography -
> e.g., doing encryption in bit-wise parallel; the ability to utilize large
> numbers of machines for password cracking purpose, whether on a service
> like AWS or through botnets of ever growing size; the wide deployment of
> graphics cards, which it turned out could be used to implement cracking
> algorithms very quickly - and of course the availability of all those
> databases of encrypted passwords, some of which didn't even bother to use
> salts, which was best practice by the late 1970's.
>
> All this didn't come together until the last 2-3 years or so. There
> simply were no plausible, much less *demonstrated*, large scale attacks
> against encrypted passwords until not long before that. bcrypt was first
> published in 1999 specifically to protect against rainbow tables - a neat
> theoretical attack that may never have actually been used in practice
> anywhere. (The newer brute force techniques are much more practical than
> rainbow tables in today's environment; if you hear someone talking about
> using rainbow tables today, it probably means they don't know what they are
> talking about.) scrypt is 10 years more recent - the paper defining it was
> only published in 2009, and a (since-expired) draft RFC dates to 2012.
> Most cryptographers would probably be leery of scrypt: It simply hasn't
> been around long enough, and survived enough concerted attacks by those who
> are really good at such attacks, to form a good judgement as to its
> strength. Just because all publicly known implementations are slow doesn't
> mean there aren't fast ones waiting to be found.
>
> Using a strong key hashing function (I hesitate to say KDF because KDF's
> have other purposes as well) on the server as a replacement for its
> existing hash function is a quick fix that doesn't require any changes to
> clients and minimal changes to servers (of which there are quite a few as
> well). There are no other measures that could be applied in anything less
> than years. (And, in practice, even this substitution is moving rather
> slowly.)
>
> It's also worth pointing out that strong hashing on the client is a
> non-starter for another reason: Not all clients are fast workstations. In
> fact, increasing they are mobile phones and tablets, which have limited
> computing capability and, more to the point, are heavily power constrained.
> I'm not aware of any measurements, but I'd guess that bcrypt - and
> especially scrypt, which by design hits memory very hard - use a *lot* of
> power.
>
> The current system requires that the password be transmitted to the
> server, and users have to trust the service provider to be honest. This
> provides a couple ways for attackers to compromise the password. Just pay
> off the guys running the server ($10M anyone?), issue them a court order of
> some sort, or override the CA and do the man-in-the-middle thing. As soon
> as you transmit your password to the server, security is already broken.
>
> That makes no sense. If you transmit the derived key, *it* becomes the
> "real" key. The server has to know it - either all the time (if service
> providers decide that since clients are doing the hashing they don't need
> to bother) or, as now, every time you log in. The only difference is that
> if you re-use a password across sites, currently you may be handing server
> A your password to server B. To which the answer, as always, is "don't do
> that". If you're assuming significant changes on the client side, you
> would do better "assuming in" an already-well-developed technology:
> Password managers, which make it trivial to generate different passwords
> for every site.
>
> Alternatively, if you're assuming the whole system changes, PAKE schemes
> like EKE(1992!) or SPF(RFC2945, 2000!) - are better anyway.
>
> The guys in charge of mainstream crypto algorithms don't seem to be doing
> KDFs very well. It's not just the lame server-side KDFs. The one that
> really bothers me is TrueCrypt, which in user-land is more popular than all
> the rest combined by a factor of several. About 90% of all file encryption
> in user-land (not corporate or server side) is done in TrueCrypt.
>
> TrueCrypt was released in 2004, well before the style of attack you're so
> concerned about was known. Hey, guess what: TrueCrypt is open source. If
> you think you can improve it by adding a better "password stretcher" - by
> all means do so. You can even do it without touching the main TrueCrypt
> code by adding a wrapper around the code that reads the password. There
> are no magic "guys in charge" to tell you not to do it.
>
> In addition to a weak KDF, users are encouraged to use weak passwords.
> For example, https://howsecureismypassword.net/ says that "dogs
> breakfast" would take a desktop PC a million years to crack.
>
> Someone is wrong on the Internet! Where will it end?
>
> I'm suspicious there may be some cash being paid to the right people to
> make sure TrueCrypt key stretching stays weak. If RSA got $10M, what did
> the TrueCrypt guys get?
>
> And a new conspiracy theory!
>
> Simply adding an option for user-selectable rounds of key stretching would
> take about 10 minutes of coding.
>
> a) So do it! I'll bet writing your email took longer than that.
> b) It's been shown repeatedly that adding options - especially options
> that people won't even understand - doesn't help. Almost everyone will
> choose the default. You have to make the default "right". In the world of
> crypto, "right" today almost always becomes "wrong" a couple of years down
> the road as attacks keep getting better.
> -- Jerry
>
>
>
--089e0116167e954a6a04ee2663fb
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">There were some very informative statements in the replies=
. =A0Thanks for all the history and background, and pointers to some cool t=
echnologies. =A0Some comments:<div><br></div><div><span style=3D"font-famil=
y:arial,sans-serif;font-size:19.200000762939453px">Jerry wrote: "That =
makes no sense. =A0If you transmit the derived key, *it* becomes the "=
real" key. "</span><br>
</div><div><br></div><div>There are several advantages over just sending th=
e user's password to the server. =A0It offloads the server enabling mor=
e compute intensive KDFs. =A0The client side software is auditable by users=
, so we can verify the KDF is done well, unlike the situation with servers =
like LinkedIn. =A0Also, anyone seeing a user's passwords in plain text =
is going to gain a great advantage when trying to crack those passwords for=
other sites. =A0They are often the same, or only slightly different. =A0Th=
is is how so many LinkedIn users had their Google accounts hacked.</div>
<div><br></div><div>Still, those were some great links you and the others p=
ointed out. =A0Your link to Secure Remote Password Protocol is very cool. =
=A0It does KDF in the client also. =A0This is better than sending any passw=
ord every time to the server.</div>
<div><br></div><div>I'm just noodling, but could we enhance SRP to not =
rely only on the discrete logarithm problem? =A0I'm looking at SRP on w=
ikipedia. =A0They describe the secret stored on the server is "v"=
, which is computed by Carol as g^x, where x is Carols derived key. =A0V is=
essentially Carol's public key, and x is her private key, enabling Ste=
ve to securely send a session key to Carol even if a MITM attacker has Stev=
e's hashed password file. =A0That's very cool, but if a MITM attack=
er doesn't have the hashed password file, but does have a silly amount =
of compute power for computing discrete logs, couldn't we thwart them s=
imply by using v as a shared private key during the session key exchange? =
=A0When Steve sends his info to Carol, why not AES encrypt it with v? =A0Th=
at's all it would take.</div>
</div><div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Sun,=
Dec 22, 2013 at 11:26 AM, Jerry Leichter <span dir=3D"ltr"><<a href=3D"=
mailto:leichter@lrw.com" target=3D"_blank">leichter@lrw.com</a>></span> =
wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-word"><div><di=
v class=3D"im"><div>On Dec 21, 2013, at 11:46 PM, Bill Cox wrote:</div><blo=
ckquote type=3D"cite">
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div=
>I don't understand why servers do the KDF rather than the client.</div=
></div></div></div></blockquote></div><div>There's an old joke: =A0How =
could God create the entire universe in only six days? =A0No installed base=
!</div>
<div><br></div><div>It's also *so* easy to criticize yesterday's de=
cisions based on today's knowledge and capabilities.</div><div><br></di=
v><div>KDF's used specifically to strengthen weak user passwords agains=
t brute-force attack were introduced as a quick way to strengthen *existing=
* systems with immense numbers of already-fielded clients. =A0Requiring tha=
t the clients all change would be a perfect way to make sure nothing got im=
proved.</div>
<div><br></div><div>Keep in mind that the *original* purpose of "key h=
ashing" was rather different: =A0It was to keep passwords secure even =
when the password file (or logical equivalent) was leaked. =A0Password hash=
ing was introduced in early versions of Unix with exactly this primary purp=
ose - and the secondary purpose of allowing anyone to verify a password by =
reading the public value from the file, hashing an incoming alleged passwor=
d, and comparing. =A0It took a number of years to learn that making even th=
e hashed passwords public was a bad idea - and every Unix system in decades=
has had shadow password files. =A0Web servers and such simply followed (of=
ten badly) existing "best practice": =A0Unix password hashing was=
based on DES; they moved to more recent crypto standards. =A0Of course, th=
en they (the Web server community as a whole) screwed up the entire ecosyst=
em by implementing such poor security that they repeatedly managed to lose =
huge databases full of millions of hashed passwords.</div>
<div><br></div><div>The ability to do mass off-line attacks wasn't anti=
cipated. =A0Its success was based on the combination of several things that=
would have been hard to predict: =A0Clever fast implementations of some of=
the primitives optimized for the purpose of password cracking rather than =
ordinary cryptography - e.g., doing encryption in bit-wise parallel; the ab=
ility to utilize large numbers of machines for password cracking purpose, w=
hether on a service like AWS or through botnets of ever growing size; the w=
ide deployment of graphics cards, which it turned out could be used to impl=
ement cracking algorithms very quickly - and of course the availability of =
all those databases of encrypted passwords, some of which didn't even b=
other to use salts, which was best practice by the late 1970's.</div>
<div><br></div><div>All this didn't come together until the last 2-3 ye=
ars or so. =A0There simply were no plausible, much less *demonstrated*, lar=
ge scale attacks against encrypted passwords until not long before that. =
=A0bcrypt was first published in 1999 specifically to protect against rainb=
ow tables - a neat theoretical attack that may never have actually been use=
d in practice anywhere. =A0(The newer brute force techniques are much more =
practical than rainbow tables in today's environment; if you hear someo=
ne talking about using rainbow tables today, it probably means they don'=
;t know what they are talking about.) =A0scrypt is 10 years more recent - t=
he paper defining it was only published in 2009, and a (since-expired) draf=
t RFC dates to 2012. =A0Most cryptographers would probably be leery of scry=
pt: =A0It simply hasn't been around long enough, and survived enough co=
ncerted attacks by those who are really good at such attacks, to form a goo=
d judgement as to its strength. =A0Just because all publicly known implemen=
tations are slow doesn't mean there aren't fast ones waiting to be =
found.</div>
<div><br></div><div>Using a strong key hashing function (I hesitate to say =
KDF because KDF's have other purposes as well) on the server as a repla=
cement for its existing hash function is a quick fix that doesn't requi=
re any changes to clients and minimal changes to servers (of which there ar=
e quite a few as well). =A0There are no other measures that could be applie=
d in anything less than years. =A0(And, in practice, even this substitution=
is moving rather slowly.)</div>
<div><br></div><div>It's also worth pointing out that strong hashing on=
the client is a non-starter for another reason: =A0Not all clients are fas=
t workstations. =A0In fact, increasing they are mobile phones and tablets, =
which have limited computing capability and, more to the point, are heavily=
power constrained. =A0I'm not aware of any measurements, but I'd g=
uess that bcrypt - and especially scrypt, which by design hits memory very =
hard - use a *lot* of power.</div>
<div class=3D"im"><div><br></div><blockquote type=3D"cite"><div dir=3D"ltr"=
><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div> =A0The current=
system requires that the password be transmitted to the server, and users =
have to trust the service provider to be honest. =A0This provides a couple =
ways for attackers to compromise the password. =A0Just pay off the guys run=
ning the server ($10M anyone?), issue them a court order of some sort, or o=
verride the CA and do the man-in-the-middle thing. =A0As soon as you transm=
it your password to the server, security is already broken.</div>
</div></div></div></blockquote></div>That makes no sense. =A0If you transmi=
t the derived key, *it* becomes the "real" key. =A0The server has=
to know it - either all the time (if service providers decide that since c=
lients are doing the hashing they don't need to bother) or, as now, eve=
ry time you log in. =A0The only difference is that if you re-use a password=
across sites, currently you may be handing server A your password to serve=
r B. =A0To which the answer, as always, is "don't do that". =
=A0If you're assuming significant changes on the client side, you would=
do better "assuming in" an already-well-developed technology: =
=A0Password managers, which make it trivial to generate different passwords=
for every site.</div>
<div><br></div><div>Alternatively, if you're assuming the whole system =
changes, PAKE schemes like EKE(1992!) or SPF(RFC2945, 2000!) - are better a=
nyway.</div><div><br></div><div><div class=3D"im"><blockquote type=3D"cite"=
>
<div dir=3D"ltr"><div class=3D"gmail_extra">The guys in charge of mainstrea=
m crypto algorithms don't seem to be doing KDFs very well. =A0It's =
not just the lame server-side KDFs. =A0The one that really bothers me is Tr=
ueCrypt, which in user-land is more popular than all the rest combined by a=
factor of several. =A0About 90% of all file encryption in user-land (not c=
orporate or server side) is done in TrueCrypt.</div>
</div></blockquote></div>TrueCrypt was released in 2004, well before the st=
yle of attack you're so concerned about was known. =A0Hey, guess what: =
=A0TrueCrypt=A0is open source. =A0If you think you can improve it by adding=
a better "password stretcher" - by all means do so. =A0You can e=
ven do it without touching the main TrueCrypt code by adding a wrapper arou=
nd the code that reads the password. =A0There are no magic "guys in ch=
arge" to tell you not to do it.</div>
<div><br></div><div><div class=3D"im"><blockquote type=3D"cite"><div dir=3D=
"ltr"><div class=3D"gmail_extra">In addition to a weak KDF, users are encou=
raged to use weak passwords. =A0For example,=A0<a href=3D"https://howsecure=
ismypassword.net/" target=3D"_blank">https://howsecureismypassword.net/</a>=
=A0says that "dogs breakfast" would take a desktop PC a million y=
ears to crack.</div>
</div></blockquote></div>Someone is wrong on the Internet! =A0Where will it=
end?</div><div><br></div><div><div class=3D"im"><blockquote type=3D"cite">=
<div dir=3D"ltr"><div class=3D"gmail_extra">I'm suspicious there may be=
some cash being paid to the right people to make sure TrueCrypt key stretc=
hing stays weak. =A0If RSA got $10M, what did the TrueCrypt guys get?</div>
</div></blockquote></div><div>And a new conspiracy theory!</div><div class=
=3D"im"><br><blockquote type=3D"cite"><div dir=3D"ltr"><div class=3D"gmail_=
extra">Simply adding an option for user-selectable rounds of key stretching=
would take about 10 minutes of coding.</div>
</div></blockquote></div>a) =A0So do it! =A0I'll bet writing your email=
took longer than that.</div><div>b) =A0It's been shown repeatedly that=
adding options - especially options that people won't even understand =
- doesn't help. =A0Almost everyone will choose the default. =A0You have=
to make the default "right". =A0In the world of crypto, "ri=
ght" today almost always becomes "wrong" a couple of years d=
own the road as attacks keep getting better.</div>
<span class=3D"HOEnZb"><font color=3D"#888888"><div><div>=A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0=
=A0 =A0 =A0 =A0 =A0 -- Jerry</div><div><br></div></div><br></font></span><=
/div></blockquote></div><br></div>
--089e0116167e954a6a04ee2663fb--
--===============6853323393286379339==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============6853323393286379339==--
