<div dir="ltr">There were some very informative statements in the replies. Thanks for all the history and background, and pointers to some cool technologies. Some comments:<div><br></div><div><span style="font-family:arial,sans-serif;font-size:19.200000762939453px">Jerry wrote: "That makes no sense. If you transmit the derived key, *it* becomes the "real" key. "</span><br>
</div><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Dec 22, 2013 at 11:26 AM, Jerry Leichter <span dir="ltr"><<a href="mailto:leichter@lrw.com" target="_blank">leichter@lrw.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div class="im"><div>On Dec 21, 2013, at 11:46 PM, Bill Cox wrote:</div><blockquote type="cite">
<div dir="ltr"><div class="gmail_extra"><div class="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: How could God create the entire universe in only six days? No installed base!</div>
<div><br></div><div>It's also *so* easy to criticize yesterday's decisions based on today's knowledge and capabilities.</div><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</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 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.)</div>
<div><br></div><div>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.</div>
<div class="im"><div><br></div><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div> 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.</div>
</div></div></div></blockquote></div>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.</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 anyway.</div><div><br></div><div><div class="im"><blockquote type="cite">
<div dir="ltr"><div class="gmail_extra">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.</div>
</div></blockquote></div>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.</div>
<div><br></div><div><div class="im"><blockquote type="cite"><div dir="ltr"><div class="gmail_extra">In addition to a weak KDF, users are encouraged to use weak passwords. For example, <a href="https://howsecureismypassword.net/" target="_blank">https://howsecureismypassword.net/</a> says that "dogs breakfast" would take a desktop PC a million years to crack.</div>
</div></blockquote></div>Someone is wrong on the Internet! Where will it end?</div><div><br></div><div><div class="im"><blockquote type="cite"><div dir="ltr"><div class="gmail_extra">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?</div>
</div></blockquote></div><div>And a new conspiracy theory!</div><div class="im"><br><blockquote type="cite"><div dir="ltr"><div class="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) So do it! I'll bet writing your email took longer than that.</div><div>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.</div>
<span class="HOEnZb"><font color="#888888"><div><div> -- Jerry</div><div><br></div></div><br></font></span></div></blockquote></div><br></div>