A History of Password Storage

The first time peo­ple at­tempt to de­sign a Web lo­gin sys­tem, they will usu­al­ly de­fault to sim­ply in­sert­ing their users’ pass­words in their data­base. This so­lu­tion is sim­ple, ob­vi­ous, and wrong.

The prob­lem is that data­base stor­age is not near­ly as pri­vate as we would all like it to be. Even the data­bas­es that we’d hope are best de­fend­ed from at­tack keep get­ting dumped, and in al­most all of those the most valu­able thing to an at­tack­er is the list of emails and pass­words in the “users” ta­ble. With that in­for­ma­tion they can ob­vi­ous­ly im­per­son­ate any user to the com­pro­mised web­site and do any­thing that user is able to, but it’s ac­tu­al­ly worse than that: in prac­tice, users reuse pass­words all the time. Steal some­one’s poor­ly-de­fend­ed Twit­ter for Pets pass­word and there’s a dis­tress­ing­ly good chance that same pass­word will work at their bank.

As a rule Web de­vel­op­ers are not stu­pid, and once this prob­lem is point­ed out they’ll gen­er­al­ly try to fix it. Un­for­tu­nate­ly for all of us, any so­lu­tion will re­quire cryp­tog­ra­phy, and like any prob­lem re­quir­ing cryp­tog­ra­phy it turns out to be fiendish­ly com­pli­cat­ed, dif­fi­cult to grasp, and sus­cept­able to get­ting torn down by the tini­est of mis­takes. It doesn’t help at all that the now com­mon wis­dom in cryp­to­graph­ic cir­cles that APIs should be dif­fi­cult to mis­use is an em­bar­rass­ing­ly re­cent de­vel­op­ment—we only have to look at GPG or the OpenSSL com­mand line tools to con­firm that!

It al­most sounds like we could solve our prob­lems by en­crypt­ing pass­words, and some­times a breach an­nounce­ment will say that the stolen pass­words were en­crypt­ed. We can only hope this is a case of in­for­ma­tion get­ting lost in trans­la­tion be­tween the de­vel­op­ers and whomev­er ac­tu­al­ly wrote these an­nounce­ments, be­cause it turns out en­cryp­tion is a dead end for this prob­lem. Leav­ing aside the thorny ques­tion of how you keep the en­cryp­tion key safe, an ap­pli­ca­tion that can be fooled into sim­ply print­ing out a pass­word can sure­ly be asked to do so af­ter it’s de­crypt­ed it.

That is a real con­cern, be­lieve it or not. What we’d like, then, is some way of han­dling pass­words that al­lows us to ver­i­fy that the pass­word we’ve just now been hand­ed is the same as the pass­word we were hand­ed in the past, with­out be­ing able to re­veal even to our­selves what that orig­i­nal pass­word was. This sounds like mes­sage hash­ing; it sounds so much like mes­sage hash­ing that I can’t even be mad at the long line of Web de­vel­op­ers who con­clud­ed a mes­sage hash was the right an­swer and punt­ed their pass­words through the only mes­sage hash they’d heard of, which was gen­er­al­ly MD5. But this is cryp­tog­ra­phy, the land of tiny mis­takes that will ruin your en­tire day.

The first mis­take here is that we’re not pro­tect­ing a sin­gle pass­word. We’re pro­tect­ing an en­tire data­base of pass­words, and if an at­tack­er can see that our CEO has the same pass­word as Bob from Sales, that’s bad. They can phish the less-pro­tect­ed tar­get and im­me­di­ate­ly piv­ot to the big juicy ac­count. Even worse, if our bud­dies at Con­toso got hacked last month, Con­toso used the same hash func­tion, and Con­toso’s CEO hap­pened to use the same pass­word as ours (maybe it’s “golf”, what­ev­er), the at­tack­er might still have that map­ping of hash to pass­word still sit­ting around!

The sec­ond mis­take is that the set of like­ly pass­words isn’t very large. They’re most­ly short—in the bad old days, no more than eight char­ac­ters—and most­ly vari­a­tions on dic­tio­nary words. It’s ab­solute­ly feasable to just try all the like­ly pass­words. In pre­vi­ous years you might use rain­bow ta­bles—clev­er­ly-com­pressed dic­tio­nar­ies of hash val­ues to like­ly pass­words—to speed up this search, but GPUs have be­come fast enough that se­ri­ous at­tack­ers will just plug a bunch of them into each oth­er like they’re try­ing to mine buttcoin.

Be­fore we move on to how the in­dus­try fixed these prob­lems, I should say that I don’t mean to im­ply that they are ob­vi­ous prob­lems. In 2019 the in­dus­try has ac­cu­mu­lat­ed enough scar tis­sue around pass­words that ex­pe­ri­enced pro­fes­sion­als can say im­me­di­ate­ly say “no don’t do that” when some­one comes up with md5(pass­word) as a so­lu­tion, but even Mi­crosoft shipped ba­si­cal­ly that, even as late as Win­dows NT/2000. If Mi­crosoft, a mul­ti-bil­lion dol­lar com­pa­ny that can hire as many pro­fes­sion­al cryp­tog­ra­phers as they please, can ship NTHash in the year 2000 then no­body just con­tem­plat­ing the prob­lem for the first time should feel bad that they fell into the ex­act same trap.

To solve the first prob­lem, where the pass­word pota­to will hash to e561f9248d7563d15dd93457b02ebbb6 every time, we need to in­tro­duce some­thing more to the process, some­thing that can make that hash val­ue wild­ly dif­fer­ent even if we’re hash­ing the same val­ue. Con­ve­nient­ly, high-qual­i­ty cryp­to­graph­ic hash func­tions have the prop­er­ty that any change to their in­puts, even a small one, will re­sult in a wild­ly dif­fer­ent out­put. We can gen­er­ate some ran­dom data every time we store a new pass­word, feed it to the hash func­tion ahead of the pass­word, and we’ll have a scheme where it’s as hard to tell whether two stored pass­words are the same as it is to re­cov­er the orig­i­nal pass­words in the first place.

For ob­scure rea­sons (read that as: I don’t know what they are), that chunk of ran­dom data is re­ferred to as a “salt”. We do need the salt that we used to ob­tain a hash to ver­i­fy a pass­word against it, but there’s no need for elab­o­rate or clever stor­age schemes: as long as the salt is unique, it doesn’t have to be se­cret. Stor­ing it in the same data­base col­umn as the re­sult of the hash func­tion is com­plete­ly ac­cept­able, and near-uni­ver­sal prac­tice. Adding a short hash al­go­rithm iden­ti­fi­er so we can trans­par­ent­ly up­grade users on their next lo­gin if we’ve move to some­thing more se­cure, we might end up with “crypt-style” hash­es, so named be­cause mod­ern ver­sions of the Unix crypt(3) pass­word-hash­ing func­tion uses it: "pota­to" might end up look­ing like "$1$ytW4Uc­Nn$FWkVB­bl6SC6QHID0Ig­buc1" in this scheme.

As a his­tor­i­cal note, salts as used in pass­word hash­ing first evolved as a de­fense against rain­bow ta­bles. Good rain­bow ta­bles re­quired large but fea­si­ble amounts of disk space be­fore the ad­vent of salts, but with even eight-char­ac­ter salts the size of a de­cent ta­ble would be an ex­trav­a­gant waste even in the mod­ern era of gi­ga­bit net­works and ter­abyte dri­ves.

Some sources dis­cuss the use of “pep­pers” in pass­word hash­ing: some­thing sim­i­lar to a salt, gen­er­at­ed per ap­pli­ca­tion rather than per pass­word. The con­cept seems at­trac­tive to some peo­ple be­cause it doesn’t re­quire up­dat­ing the for­mat of the stored hash and there­fore wouldn’t re­quire widen­ing any VAR­CHAR columns. They were al­ways of du­bi­ous use. In the past when rain­bow ta­bles were the dom­i­nant at­tack strat­e­gy they’d have stopped some­one us­ing a gener­ic ta­ble, but the more pop­u­lar an ap­pli­ca­tion be­came the more like­ly some­one would go to the trou­ble of gen­er­at­ing a ta­ble for that ap­pli­ca­tion, and at that point the pep­per in­stant­ly be­comes use­less. In the mod­ern era of hard­ware-ac­cel­er­at­ed pass­word crack­ing they aren’t of any use at all.

Re­sist­ing brute force at­tacks, then. The cen­tral is­sue here is that cryp­to­graph­ic hash func­tions are de­signed to be ef­fi­cient. They have to be; they have to be fast enough to be use­ful for ver­i­fy­ing the in­tegri­ty of mul­ti-terrabyte data­base back­ups. We want an­oth­er kind of func­tion that’s de­lib­er­ate­ly in­ef­fi­cient, so that the ex­er­cise of try­ing all rea­son­able in­puts will take too long or cost too much mon­ey to be of any use.

As a first at­tempt, we might take the out­put of our salt­ed hash and feed it back into the hash func­tion, then feed that back into the hash func­tion again, … un­til we have spent as much time reap­ply­ing the hash as we are will­ing to spend. This scheme is called PBKDF1 (Pass­word-Based Key De­riva­tion Func­tion ver­sion 1), and its use­ful life­time was rel­a­tive­ly short. Its suc­ces­sor PBKDF2 uses a more so­phis­ti­cat­ed con­struc­tion, but the core idea is es­sen­tial­ly the same; to­day PBKDF2 is the al­go­rithm of choice when an ap­pli­ca­tion re­quires NIST-stan­dard­ized cryp­tog­ra­phy, and is not rec­om­mend­ed oth­er­wise.

Around the time PBKDF2 was be­ing stan­dard­ized, an­oth­er group of cyp­tog­ra­phers study­ing the Blow­fish sym­met­ric en­cryp­tion al­go­rithm no­ticed that its key sched­ule was strange­ly in­ef­fi­cient. Aware of the prob­lems of pass­word stor­age, they ex­tract­ed and light­ly mod­i­fied that por­tion of the al­go­rithm and pub­lished it in the Usenix se­cu­ri­ty jour­nal. Their EKS­Blow­fish (Ex­pen­sive Key Sched­ule Blow­fish) be­came the core of the bcrypt pass­word hash­ing rou­tine, which has been the rec­om­mend­ed pass­word hash for most of my ca­reer.

At­tacks, un­for­tu­nate­ly, only ever get more ef­fec­tive. PBKDF2 and bcrypt fo­cus en­tire­ly on re­quir­ing more com­pu­ta­tion, and cryp­tog­ra­phers have watched the march of progress in GPUs and ASICs some­what ner­vous­ly. If there were an al­go­rithm that was fun­da­men­tal­ly in­ef­fi­cient in its mem­o­ry re­quire­ments as well com­pu­ta­tion, that would re­sist the new mas­sive­ly-par­al­lel at­tack­ers quite hand­i­ly.

The first such al­go­rithm to gain wide promi­nence was scrypt in 2009, de­signed to pro­tect en­crypt­ed back­ups by re­quir­ing much mem­o­ry to com­pute the en­cryp­tion key. Al­though scrypt is well known, as these things go, it’s not used much for lo­gins. I’m not com­plete­ly sure why but at a guess it was slight­ly ahead of its time, an­tic­i­pat­ing a prob­lem that wasn’t yet quite a prac­ti­cal con­cern for com­mon ap­pli­ca­tions. It’s also more com­pli­cat­ed to use; PBKDF2 or blow­fish have one tun­able pa­ra­me­ter, the “work fac­tor”, whose ef­fect is eas­i­ly un­der­stood. Scrypt has three pa­ra­me­ters, whose ef­fects are slight­ly more ob­scure.

By 2013 the fun­da­men­tal prim­i­tives for high-qual­i­ty pass­word stor­age had been wide­ly avail­able for years, but high pro­file pass­word stor­age dis­as­ters con­tin­ued to hit the news. In or­der to con­sol­i­date any re­cent ad­vance­ments and raise aware­ness of the is­sue, a group of cryp­tog­ra­phers or­ga­nized a Pass­word Hash­ing Com­pe­ti­tion mod­eled af­ter the com­pe­ti­tions that re­sult­ed in AES and SHA3. In 2015 they an­nounced Ar­gon2 as the win­ner.

The goals of Ar­gon2 aren’t too dif­fer­ent from scrypt. It’s still in­tend­ed to re­quire lots of time and lots of mem­o­ry; also like scrypt, it takes three tun­able pa­ra­me­ters. Un­like scrypt, whose mem­o­ry re­quire­ments are a func­tion of all three pa­ra­me­ters, Ar­gon2 sim­ply takes the amount of mem­o­ry it should use as one of its pa­ra­me­ters and is thus much eas­i­er for de­vel­op­ers to un­der­stand.

To­day Ar­gon2 is the state of the art and rec­om­mend­ed for new ap­pli­ca­tions. It’s the pass­word hash in lib­sodi­um fol­low­ing ver­sion 1.0.9, and in all ap­plic­a­ble cas­es I can think of the cor­rect an­swer to a cryp­to­graph­ic ques­tion is “what­ev­er the lat­est re­lease of lib­sodi­um does.” That’s the point of lib­sodi­um: af­ter far too many years, de­vel­op­ers don’t even real­ly need to care.