Advertisement
Guest User

Untitled

a guest
Feb 27th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 55.65 KB | None | 0 0
  1.  
  2. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
  3. <html xmlns="http://www.w3.org/1999/xhtml" >
  4. <head>
  5. <title>Secure Salted Password Hashing - How to do it Properly</title>
  6. <meta name="description" content="How to hash passwords properly using salt. Why hashes should be salted and how to use salt correctly." />
  7. <meta name="keywords" content="salt, salted hashing, secure password hashing, password hashing, proper way to hash passwords" />
  8. <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  9. <meta name="google-site-verification" content="AeVohZfbCxeMLV4i1tKOdEgAOxhl8JgvNEpi11neLLk" />
  10. <meta name="google-site-verification" content="bJfNsQVzNQLRCAQiZD0kUNF-gFYS16YnaCZDJEX-dLk" />
  11. <link rel="stylesheet" media="all" type="text/css" href="/css/mainmenu2.css" />
  12. <link rel="stylesheet" media="all" type="text/css" href="/css/main.css" />
  13. <link rel="stylesheet" media="all" type="text/css" href="/css/style.css" />
  14. <!--[if !IE 7]>
  15. <style type="text/css">
  16. #wrap {display:table;height:100%}
  17. </style>
  18. <![endif]-->
  19. </head>
  20. <body >
  21. <div id="wrap">
  22.  
  23. <!-- This menuing system was made by Steve Gibson at GRC.COM
  24. see more at http://www.grc.com/menudemo.htm -->
  25.  
  26. <div class="menuminwidth0"><div class="menuminwidth1"><div class="menuminwidth2">
  27. <div id="masthead">
  28. <div style="font-size:30px;"><img src="/images/1by1.gif" alt="CrackStation" /></div>
  29. <div id="sm">
  30. <a href="https://defuse.ca/" title="Defuse Security">Defuse.ca</a>
  31. &nbsp;&middot;&nbsp;
  32. <a href="https://twitter.com/defusesec" title="Follow @DefuseSec on twitter!">
  33. <img id="twitterlogo" src="/images/twitter.png" alt="Follow me on twitter!" height="25" width="30" />
  34. Twitter
  35. </a>
  36. </div>
  37. </div>
  38.  
  39. <div class="menu">
  40.  
  41. <ul>
  42. <li class="headerlink" ><a href="/">CrackStation<img class="downimg" src="/images/downarrow.gif" alt="&#9660;"/><!--[if gt IE 6]><!--></a><!--<![endif]--><!--[if lt IE 7]><table border="0" cellpadding="0" cellspacing="0"><tr><td><![endif]-->
  43. <ul class="leftbutton">
  44. <li><a href="/">&nbsp;Free Hash Cracker</a></li>
  45. <li><a href="crackstation-wordlist-password-cracking-dictionary.htm">&nbsp;Wordlist Download</a></li>
  46. <li><a href="/about-us.htm">&nbsp;About Us</a></li>
  47. <li><a href="/contact-us.htm">&nbsp;Contact Us</a></li>
  48. <li><a href="/legal-privacy.htm">&nbsp;ToS &amp; Privacy Policy</a></li>
  49. </ul>
  50. <!--[if lte IE 6]></td></tr></table></a><![endif]-->
  51. </li>
  52. </ul>
  53.  
  54.  
  55. <ul>
  56. <li class="headerlink" ><a href="/hashing-security.htm">Password Hashing Security<img class="downimg" src="/images/downarrow.gif" alt="&#9660;"/><!--[if gt IE 6]><!--></a><!--<![endif]--><!--[if lt IE 7]><table border="0" cellpadding="0" cellspacing="0"><tr><td><![endif]-->
  57. <!--[if lte IE 6]></td></tr></table></a><![endif]-->
  58. </li>
  59. </ul>
  60.  
  61. <ul>
  62. <li class="headerlink" ><a href="https://defuse.ca/">Defuse Security<img class="downimg" src="/images/downarrow.gif" alt="&#9660;"/><!--[if gt IE 6]><!--></a><!--<![endif]--><!--[if lt IE 7]><table border="0" cellpadding="0" cellspacing="0"><tr><td><![endif]-->
  63. <!--[if lte IE 6]></td></tr></table></a><![endif]-->
  64. </li>
  65. </ul>
  66.  
  67. </div> <!-- close "menu" div -->
  68. <hr style="display:none" />
  69. </div></div></div> <!-- close the "minwidth" wrappers -->
  70. <!-- End of menu -->
  71.  
  72. <!--[if !IE]>-->
  73. <div id="undergrad"></div>
  74. <!--<![endif]-->
  75.  
  76. <!--[If gt IE 6]>
  77. <div id="undergrad"></div>
  78. <![endif]-->
  79.  
  80. <div id="content">
  81. <h1>Salted Password Hashing - Doing it Right</h1>
  82.  
  83. <p>
  84. If you're a web developer, you've probably had to make a user account system.
  85. The most important aspect of a user account system is how user passwords are
  86. protected. User account databases are hacked frequently, so you absolutely must
  87. do something to protect your users' passwords if your website is ever breached.
  88. The best way to protect passwords is to employ <b>salted password hashing</b>.
  89. This page will explain why it's done the way it is.
  90. </p>
  91.  
  92. <p>
  93. There are a lot of conflicting ideas and misconceptions on how to do password
  94. hashing properly, probably due to the abundance of misinformation on the web.
  95. Password hashing is one of those things that's so simple, but yet so many people
  96. get wrong. With this page, I hope to explain not only the correct way to do it,
  97. but why it should be done that way.
  98. </p>
  99.  
  100.  
  101. <div style="background-color: #FFCCCC; border: solid red 1px; padding: 10px;">
  102. <strong>IMPORTANT WARNING:</strong> If you are thinking of writing your own
  103. password hashing code, <strong>please don't!</strong>. It's too easy to screw
  104. up. No, that cryptography course you took in university doesn't make you exempt
  105. from this warning. This applies to everyone: <strong>DO NOT WRITE YOUR OWN
  106. CRYPTO!</strong> The problem of storing passwords has already been solved. Use
  107. either use either <a href="http://www.openwall.com/phpass/">phpass</a>, the PHP,
  108. C#, Java, and Ruby implementations in <a
  109. href="https://github.com/defuse/password-hashing">defuse/password-hashing</a>,
  110. or <a
  111. href="https://download.libsodium.org/doc/password_hashing/index.html">libsodium</a>.
  112. </div>
  113.  
  114. <p>
  115. If for some reason you missed that big red warning note, please go read it now.
  116. Really, this guide is <b>not</b> meant to walk you through the process of
  117. writing your own storage system, it's to explain the reasons why passwords
  118. should be stored a certain way.
  119. </p>
  120.  
  121. <p>You may use the following links to jump to the different sections of this page.</p>
  122.  
  123. <table class="shortcuts">
  124. <tbody><tr>
  125. <td><a href="#normalhashing" class="sca" title="What are hash functions and why are they used?">1. What is password hashing?</a></td>
  126. <td><a href="#attacks" class="sca" title="Methods for making hash cracking more efficient">2. How Hashes are Cracked</a></td>
  127.  
  128. <td><a href="#salt" class="sca" title="Adding salt to render hash cracking attacks less effective">3. Adding Salt</a></td>
  129. </tr>
  130. <tr>
  131. <td><a href="#ineffective" class="sca" title="The wrong way to do password hashing">4. Ineffective Hashing Methods</a></td>
  132. <td><a href="#properhashing" class="sca" title="The right way to do password hashing, with salt">5. How to hash properly</a></td>
  133. <td><a href="#faq" class="sca" title="Frequently asked questions about password hashing and salt">6. Frequently Asked Questions</a></td>
  134. </tr>
  135. </tbody></table>
  136.  
  137. <a name="normalhashing"></a>
  138. <h2>What is password hashing?</h2>
  139. <div class="passcrack" style="text-align: center;">
  140. hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824<br />
  141. hash("hbllo") = 58756879c05c68dfac9866712fad6a93f8146f337a69afe7dd238f3364946366<br />
  142. hash("waltz") = c0e81794384491161f1777c232bc6bd9ec38f616560b120fda8e90f383853542<br />
  143. </div>
  144. <p>
  145. Hash algorithms are one way functions. They turn any amount of data into
  146. a fixed-length "fingerprint" that cannot be reversed. They also have the
  147. property that if the input changes by even a tiny bit, the resulting hash is
  148. completely different (see the example above). This is great for protecting
  149. passwords, because we want to store passwords in a form that protects them even
  150. if the password file itself is compromised, but at the same time, we need to be
  151. able to verify that a user's password is correct.
  152. </p>
  153.  
  154. <p>
  155. The general workflow for account registration and authentication in a hash-based
  156. account system is as follows:
  157. </p>
  158. <ol class="moveul">
  159. <li>The user creates an account.</li>
  160. <li>Their password is hashed and stored in the database. At no point is the plain-text (unencrypted) password ever written to the hard drive.</li>
  161.  
  162. <li>When the user attempts to login, the hash of the password they entered is checked against the hash of their real password (retrieved from the database).</li>
  163. <li>If the hashes match, the user is granted access. If not, the user is told they entered invalid login credentials.</li>
  164. <li>Steps 3 and 4 repeat every time someone tries to login to their account.</li>
  165. </ol>
  166.  
  167. <p>
  168. In step 4, never tell the user if it was the username or password they got wrong. Always display
  169. a generic message like "Invalid username or password." This prevents attackers from enumerating
  170. valid usernames without knowing their passwords.
  171. </p>
  172.  
  173. <p>
  174. It should be noted that the hash functions used to protect passwords are not the
  175. same as the hash functions you may have seen in a data structures course. The
  176. hash functions used to implement data structures such as hash tables are
  177. designed to be fast, not secure. Only <b>cryptographic hash functions</b> may be
  178. used to implement password hashing. Hash functions like SHA256, SHA512, RipeMD,
  179. and WHIRLPOOL are cryptographic hash functions.
  180. </p>
  181.  
  182. <p>
  183. It is easy to think that all you have to do is run the password through a
  184. cryptographic hash function and your users' passwords will be secure. This is
  185. far from the truth. There are many ways to recover passwords from plain hashes
  186. very quickly. There are several easy-to-implement techniques that make these
  187. "attacks" much less effective. To motivate the need for these techniques,
  188. consider this very website. On the front page, you can submit a list of hashes
  189. to be cracked, and receive results in less than a second. Clearly, simply
  190. hashing the password does not meet our needs for security.
  191. </p>
  192.  
  193. <p>The next section will discuss some of the common attacks used to crack plain password hashes.</p>
  194.  
  195. <a name="attacks"></a>
  196. <h2>How Hashes are Cracked</h2>
  197. <ul class="moveul" >
  198. <li>
  199. <h3>Dictionary and Brute Force Attacks</h3>
  200. <table style="margin: 0 auto;">
  201. <tbody><tr>
  202. <td>
  203. <div class="passcrack" title="Cracking a hash with a wordlist">
  204. <center>Dictionary Attack</center><br />
  205. Trying apple &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: failed<br />
  206. Trying blueberry &nbsp;&nbsp;&nbsp;: failed<br />
  207. Trying justinbeiber : failed<br />
  208. <center>...</center>
  209. Trying letmein &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: failed<br />
  210.  
  211. <span style="color: green;">Trying s3cr3t &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: success!</span><br />
  212. </div>
  213. </td>
  214. <td>
  215. <div class="passcrack" title="Cracking a hash by brute force">
  216. <center>Brute Force Attack</center><br />
  217. Trying aaaa : failed<br />
  218. Trying aaab : failed<br />
  219. Trying aaac : failed<br />
  220. <center>...</center>
  221. Trying acdb : failed<br />
  222. <span style="color: green;">Trying acdc : success!</span><br />
  223. </div>
  224. </td>
  225. </tr>
  226. </tbody></table>
  227. <p>
  228. The simplest way to crack a hash is to try to guess the password, hashing each guess, and checking if the guess's hash equals the hash being cracked. If the hashes are equal, the guess is the password.
  229. The two most common ways of guessing passwords are <b>dictionary attacks</b> and <b>brute-force attacks</b>.
  230. </p>
  231.  
  232. <p>
  233. A dictionary attack uses a file containing words, phrases, common passwords,
  234. and other strings that are likely to be used as a password. Each word in the
  235. file is hashed, and its hash is compared to the password hash. If they
  236. match, that word is the password. These dictionary files are constructed by
  237. extracting words from large bodies of text, and even from real databases of
  238. passwords. Further processing is often applied to dictionary files, such as
  239. replacing words with their "leet speak" equivalents ("hello" becomes
  240. "h3110"), to make them more effective.
  241. </p>
  242.  
  243. <p>
  244. A brute-force attack tries every possible combination of characters up to a
  245. given length. These attacks are very computationally expensive, and are
  246. usually the least efficient in terms of hashes cracked per processor time,
  247. but they will always eventually find the password. Passwords should be long
  248. enough that searching through all possible character strings to find it will
  249. take too long to be worthwhile.
  250. </p>
  251.  
  252. <p>
  253. There is no way to prevent dictionary attacks or brute force attacks. They
  254. can be made less effective, but there isn't a way to prevent them
  255. altogether. If your password hashing system is secure, the only way to crack
  256. the hashes will be to run a dictionary or brute-force attack on each hash.
  257. </p>
  258. </li>
  259.  
  260. <li>
  261. <h3>Lookup Tables</h3>
  262. <center>
  263. <div class="passcrack" style="text-align: center;" title="Cracking many hashes with a pre-computed lookup table">
  264. <span style="color: green;">Searching: 5f4dcc3b5aa765d61d8327deb882cf99: FOUND: password5</span><br />
  265. Searching: 6cbe615c106f422d23669b610b564800: &nbsp;not in database<br />
  266. <span style="color: green;">Searching: 630bf032efe4507f2c57b280995925a9: FOUND: letMEin12 </span><br />
  267. <span style="color: green;">Searching: 386f43fab5d096a7a66d67c8f213e5ec: FOUND: mcd0nalds</span><br />
  268. <span style="color: green;">Searching: d5ec75d5fe70d428685510fae36492d9: FOUND: p@ssw0rd!</span><br />
  269. </span>
  270. </center>
  271.  
  272. <p>
  273. Lookup tables are an extremely effective method for cracking many hashes of
  274. the same type very quickly. The general idea is to <b>pre-compute</b> the
  275. hashes of the passwords in a password dictionary and store them, and their
  276. corresponding password, in a lookup table data structure. A good
  277. implementation of a lookup table can process hundreds of hash lookups per
  278. second, even when they contain many billions of hashes.
  279. </p>
  280.  
  281. <p>
  282. If you want a better idea of how fast lookup tables can be, try cracking the
  283. following sha256 hashes with CrackStation's <a href="/">free hash
  284. cracker</a>.
  285. </p>
  286.  
  287. <div class="passcrack" style="text-align: center;" title="Example hashes to be cracked">
  288. c11083b4b0a7743af748c85d343dfee9fbb8b2576c05f3a7f0d632b0926aadfc<br />
  289. 08eac03b80adc33dc7d8fbe44b7c7b05d3a2c511166bdb43fcb710b03ba919e7<br />
  290. e4ba5cbd251c98e6cd1c23f126a3b81d8d8328abc95387229850952b3ef9f904<br />
  291. 5206b8b8a996cf5320cb12ca91c7b790fba9f030408efe83ebb83548dc3007bd<br />
  292. </div>
  293.  
  294. </li>
  295.  
  296. <li>
  297. <h3>Reverse Lookup Tables</h3>
  298. <center>
  299. <div class="passcrack" style="text-align: left;" title="Cracking many hashes with a pre-computed lookup table">
  300. <span style="color: green;">Searching for hash(apple) in users' hash list... &nbsp;&nbsp;&nbsp;&nbsp;: Matches [alice3, 0bob0, charles8]</span><br />
  301. <span style="color: green;">Searching for hash(blueberry) in users' hash list... : Matches [usr10101, timmy, john91]</span><br />
  302. <span style="color: green;">Searching for hash(letmein) in users' hash list... &nbsp;&nbsp;: Matches [wilson10, dragonslayerX, joe1984]</span><br />
  303. <span style="color: green;">Searching for hash(s3cr3t) in users' hash list... &nbsp;&nbsp;&nbsp;: Matches [bruce19, knuth1337, john87]</span><br />
  304. <span>Searching for hash(z@29hjja) in users' hash list... &nbsp;: No users used this password</span><br />
  305. </span>
  306. </center>
  307. <p>
  308. This attack allows an attacker to apply a dictionary or brute-force attack to many hashes at the same time, without having to pre-compute a lookup table.
  309. </p>
  310.  
  311. <p>
  312. First, the attacker creates a lookup table that maps each password hash from
  313. the compromised user account database to a list of users who had that hash.
  314. The attacker then hashes each password guess and uses the lookup table to
  315. get a list of users whose password was the attacker's guess. This attack is
  316. especially effective because it is common for many users to have the same
  317. password.
  318. </p>
  319. </li>
  320.  
  321. <li>
  322. <h3>Rainbow Tables</h3>
  323. <p>
  324. Rainbow tables are a time-memory trade-off technique. They are like lookup
  325. tables, except that they sacrifice hash cracking speed to make the lookup
  326. tables smaller. Because they are smaller, the solutions to more hashes can
  327. be stored in the same amount of space, making them more effective. Rainbow
  328. tables that can crack any md5 hash of a password up to 8 characters long <a
  329. href="http://www.freerainbowtables.com/en/tables2/">exist</a>.
  330. </p>
  331. </li>
  332. </ul>
  333.  
  334. <p>
  335. Next, we'll look at a technique called salting, which makes it impossible to use
  336. lookup tables and rainbow tables to crack a hash.
  337. </p>
  338.  
  339. <a name="salt"></a>
  340. <h2>Adding Salt</h2>
  341. <div class="passcrack" style="text-align: center;" title="Salt example">
  342. hash("hello") &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824<br />
  343. hash("hello" + "QxLUF1bgIAdeQX") = 9e209040c863f84a31e719795b2577523954739fe5ed3b58a75cff2127075ed1<br />
  344.  
  345. hash("hello" + "bv5PehSMfV11Cd") = d1d3ec2e6f20fd420d50e2642992841d8338a314b8ea157c9e18477aaef226ab<br />
  346. hash("hello" + "YYLmfY6IehjZMQ") = a49670c3c18b9e079b9cfaf51634f563dc8ae3070db2c4a8544305df1b60f007
  347. </div>
  348.  
  349. <p>
  350. Lookup tables and rainbow tables only work because each password is hashed the
  351. exact same way. If two users have the same password, they'll have the same
  352. password hashes. We can prevent these attacks by randomizing each hash, so that
  353. when the same password is hashed twice, the hashes are not the same.
  354. </p>
  355.  
  356. <p>
  357. We can randomize the hashes by appending or prepending a random string, called a
  358. <b>salt</b>, to the password before hashing. As shown in the example above, this
  359. makes the same password hash into a completely different string every time. To
  360. check if a password is correct, we need the salt, so it is usually stored in the
  361. user account database along with the hash, or as part of the hash string itself.
  362. </p>
  363.  
  364. <p>
  365. The salt does not need to be secret. Just by randomizing the hashes, lookup
  366. tables, reverse lookup tables, and rainbow tables become ineffective. An
  367. attacker won't know in advance what the salt will be, so they can't pre-compute
  368. a lookup table or rainbow table. If each user's password is hashed with a
  369. different salt, the reverse lookup table attack won't work either.
  370. </p>
  371.  
  372. <p>
  373. In the next section, we'll look at how salt is commonly implemented incorrectly.
  374. </p>
  375.  
  376. <a name="ineffective"></a>
  377. <h2>The <span style="color: red;">WRONG</span> Way: Short Salt &amp; Salt Reuse</h2>
  378.  
  379. <p>
  380. The most common salt implementation errors are reusing the same salt in multiple
  381. hashes, or using a salt that is too short.
  382. </p>
  383.  
  384. <h3>Salt Reuse</h3>
  385.  
  386. <p>
  387. A common mistake is to use the same salt in each hash. Either the salt is
  388. hard-coded into the program, or is generated randomly once. This is ineffective
  389. because if two users have the same password, they'll still have the same hash.
  390. An attacker can still use a reverse lookup table attack to run a dictionary
  391. attack on every hash at the same time. They just have to apply the salt to each
  392. password guess before they hash it. If the salt is hard-coded into a popular
  393. product, lookup tables and rainbow tables can be built for that salt, to make it
  394. easier to crack hashes generated by the product.
  395. </p>
  396.  
  397. <p>
  398. A new random salt must be generated each time a user creates an account or changes their password.
  399. </p>
  400.  
  401. <h3>Short Salt</h3>
  402.  
  403. <p>
  404. If the salt is too short, an attacker can build a lookup table for every
  405. possible salt. For example, if the salt is only three ASCII characters, there
  406. are only 95x95x95 = 857,375 possible salts. That may seem like a lot, but if
  407. each lookup table contains only 1MB of the most common passwords, collectively
  408. they will be only 837GB, which is not a lot considering 1000GB hard drives can
  409. be bought for under $100 today.
  410. </p>
  411.  
  412. <p>
  413. For the same reason, the username shouldn't be used as a salt. Usernames may be
  414. unique to a single service, but they are predictable and often reused for
  415. accounts on other services. An attacker can build lookup tables for common
  416. usernames and use them to crack username-salted hashes.
  417. </p>
  418.  
  419. <p>
  420. To make it impossible for an attacker to create a lookup table for every
  421. possible salt, the salt must be long. A good rule of thumb is to use a salt that
  422. is the same size as the output of the hash function. For example, the output of
  423. SHA256 is 256 bits (32 bytes), so the salt should be at least 32 random bytes.
  424. </p>
  425.  
  426. <h2>The <span style="color: red;">WRONG</span> Way: Double Hashing &amp; Wacky Hash Functions</h2>
  427.  
  428. <p>
  429. This section covers another common password hashing misconception: wacky
  430. combinations of hash algorithms. It's easy to get carried away and try to
  431. combine different hash functions, hoping that the result will be more secure. In
  432. practice, though, there is very little benefit to doing it. All it does is
  433. create interoperability problems, and can sometimes even make the hashes less
  434. secure. Never try to invent your own crypto, always use a standard that has
  435. been designed by experts. Some will argue that using multiple hash functions
  436. makes the process of computing the hash slower, so cracking is slower, but
  437. there's a better way to make the cracking process slower as we'll see later.
  438. </p>
  439.  
  440. <p>Here are some examples of poor wacky hash functions I've seen suggested in forums on the internet.</p>
  441.  
  442. <ul>
  443. <li><span class="ic">md5(sha1(password))</span></li>
  444. <li><span class="ic">md5(md5(salt) + md5(password))</span></li>
  445. <li><span class="ic">sha1(sha1(password))</span></li>
  446. <li><span class="ic">sha1(str_rot13(password + salt))</span></li>
  447. <li><span class="ic">md5(sha1(md5(md5(password) + sha1(password)) + md5(password)))</span></li>
  448. </ul>
  449.  
  450. <p>
  451. Do not use any of these.
  452. </p>
  453.  
  454. <p>
  455. Note: This section has proven to be controversial. I've received a number of
  456. emails arguing that wacky hash functions are a good thing, because it's better
  457. if the attacker doesn't know which hash function is in use, it's less
  458. likely for an attacker to have pre-computed a rainbow table for the wacky hash
  459. function, and it takes longer to compute the hash function.
  460. </p>
  461.  
  462. <p>
  463. An attacker cannot attack a hash when he doesn't know the algorithm, but note <a
  464. href="https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle"> Kerckhoffs's
  465. principle</a>, that the attacker will usually have access to the source code
  466. (especially if it's free or open source software), and that given a few
  467. password-hash pairs from the target system, it is not difficult to reverse
  468. engineer the algorithm. It does take longer to compute wacky hash functions, but
  469. only by a small constant factor. It's better to use an iterated algorithm that's
  470. designed to be extremely hard to parallelize (these are discussed below). And,
  471. properly salting the hash solves the rainbow table problem.
  472. </p>
  473.  
  474. <p>
  475. If you really want to use a standardized &quot;wacky&quot; hash function like HMAC, then it's OK.
  476. But if your reason for doing so is to make the hash computation slower, read the section below about key stretching first.
  477. </p>
  478.  
  479. <p>
  480. Compare these minor benefits to the risks of accidentally implementing a
  481. completely insecure hash function and the interoperability problems wacky hashes
  482. create. It's clearly best to use a standard and well-tested algorithm.
  483. </p>
  484.  
  485. <h2>Hash Collisions</h2>
  486.  
  487. <p>
  488. Because hash functions map arbitrary amounts of data to fixed-length strings,
  489. there must be some inputs that hash into the same string. Cryptographic hash
  490. functions are designed to make these collisions incredibly difficult to find.
  491. From time to time, cryptographers find "attacks" on hash functions that make
  492. finding collisions easier. A recent example is the MD5 hash function, for which
  493. collisions have actually been found.
  494. </p>
  495.  
  496. <p>
  497. Collision attacks are a sign that it may be more likely for a string other than
  498. the user's password to have the same hash. However, finding collisions in even a
  499. weak hash function like MD5 requires a lot of dedicated computing power, so it
  500. is very unlikely that these collisions will happen "by accident" in practice. A
  501. password hashed using MD5 and salt is, for all practical purposes, just as
  502. secure as if it were hashed with SHA256 and salt. Nevertheless, it is a good
  503. idea to use a more secure hash function like SHA256, SHA512, RipeMD, or
  504. WHIRLPOOL if possible.
  505. </p>
  506.  
  507. <a name="properhashing"></a>
  508. <h2>The <span style="color: green;">RIGHT</span> Way: How to Hash Properly</h2>
  509.  
  510. <p>
  511. This section describes exactly how passwords should be hashed. The first
  512. subsection covers the basics&mdash;everything that is absolutely necessary. The
  513. following subsections explain how the basics can be augmented to make the hashes
  514. even harder to crack.
  515. </p>
  516.  
  517. <h3>The Basics: Hashing with Salt</h3>
  518.  
  519. <p>
  520. <b>Warning: Do not just read this section. You absolutely must implement the
  521. stuff in the next section: "Making Password Cracking Harder: Slow Hash
  522. Functions".</b>
  523. </p>
  524.  
  525. <p>
  526. We've seen how malicious hackers can crack plain hashes very quickly using
  527. lookup tables and rainbow tables. We've learned that randomizing the hashing
  528. using salt is the solution to the problem. But how do we generate the salt, and
  529. how do we apply it to the password?
  530. </p>
  531.  
  532. <p>
  533. Salt should be generated using a <b>Cryptographically Secure Pseudo-Random
  534. Number Generator</b> (CSPRNG). CSPRNGs are very different than ordinary
  535. pseudo-random number generators, like the "C" language's
  536. <span class="ic">rand()</span> function. As the name suggests, CSPRNGs are
  537. designed to be cryptographically secure, meaning they provide a high level of
  538. randomness and are completely unpredictable. We don't want our salts to be
  539. predictable, so we must use a CSPRNG. The following table lists some CSPRNGs
  540. that exist for some popular programming platforms.
  541. </p>
  542.  
  543. <table id="rnglist">
  544. <tr><th>Platform</th><th>CSPRNG</th></tr>
  545. <tr><td>PHP</td><td><a href="http://php.net/manual/en/function.mcrypt-create-iv.php">mcrypt_create_iv</a>, <a href="http://php.net/manual/en/function.openssl-random-pseudo-bytes.php">openssl_random_pseudo_bytes</a></td></tr>
  546. <tr><td>Java</td><td><a href="http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html">java.security.SecureRandom</a></td></tr>
  547. <tr><td>Dot NET (C#, VB)</td><td><a href="http://msdn.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider.aspx">System.Security.Cryptography.RNGCryptoServiceProvider</a></td></tr>
  548. <tr><td>Ruby</td><td><a href="http://rubydoc.info/stdlib/securerandom/1.9.3/SecureRandom">SecureRandom</a></td></tr>
  549. <tr><td>Python</td><td><a href="http://docs.python.org/library/os.html">os.urandom</a></td></tr>
  550. <tr><td>Perl</td><td><a href="http://search.cpan.org/~mkanat/Math-Random-Secure-0.06/lib/Math/Random/Secure.pm">Math::Random::Secure</a></td></tr>
  551. <tr><td>C/C++ (Windows API)</td><td><a href="http://en.wikipedia.org/wiki/CryptGenRandom">CryptGenRandom</a></td></tr>
  552. <tr><td>Any language on GNU/Linux or Unix</td><td>Read from <a href="http://en.wikipedia.org/wiki//dev/random">/dev/random</a> or /dev/urandom</td></tr>
  553. </table>
  554.  
  555. <p> The salt needs to be unique per-user per-password. Every time a user creates an account or
  556. changes their password, the password should be hashed using a new random salt. Never reuse a salt.
  557. The salt also needs to be long, so that there are many possible salts. As a rule of thumb, make your
  558. salt is at least as long as the hash function's output. The salt should be stored in the user
  559. account table alongside the hash. </p>
  560.  
  561. <h4>To Store a Password</h4>
  562.  
  563. <ol>
  564. <li>Generate a long random salt using a CSPRNG.</li>
  565. <li>Prepend the salt to the password and hash it with a <b>standard</b> password hashing function like Argon2, bcrypt, scrypt, or PBKDF2.</li>
  566. <li>Save both the salt and the hash in the user's database record.</li>
  567. </ol>
  568.  
  569. <h4>To Validate a Password</h4>
  570.  
  571. <ol>
  572. <li>Retrieve the user's salt and hash from the database.</li>
  573. <li>Prepend the salt to the given password and hash it using the same hash function.</li>
  574. <li>Compare the hash of the given password with the hash from the database. If they match, the password is correct. Otherwise, the password is incorrect.</li>
  575. </ol>
  576.  
  577.  
  578. <h4>In a Web Application, <b>always</b> hash on the server</h4>
  579. <p>
  580. If you are writing a web application, you might wonder <em>where</em> to hash.
  581. Should the password be hashed in the user's browser with JavaScript, or should
  582. it be sent to the server "in the clear" and hashed there?
  583. </p>
  584.  
  585. <p> Even if you are hashing the user's passwords in JavaScript, you still have
  586. to hash the hashes on the server. Consider a website that hashes users'
  587. passwords in the user's browser without hashing the hashes on the server. To
  588. authenticate a user, this website will accept a hash from the browser and check
  589. if that hash exactly matches the one in the database. This seems more secure
  590. than just hashing on the server, since the users' passwords are never sent to
  591. the server, but it's not. </p>
  592.  
  593. <p>
  594. The problem is that the client-side hash logically <em>becomes</em> the user's
  595. password. All the user needs to do to authenticate is tell the server the hash
  596. of their password. If a bad guy got a user's <em>hash</em> they could use it to
  597. authenticate to the server, without knowing the user's password! So, if the bad
  598. guy somehow steals the database of hashes from this hypothetical website,
  599. they'll have immediate access to everyone's accounts without having to guess any
  600. passwords.
  601. </p>
  602.  
  603. <p>
  604. This isn't to say that you <em>shouldn't</em> hash in the browser, but if you
  605. do, you absolutely have to hash on the server too. Hashing in the browser is
  606. certainly a good idea, but consider the following points for your implementation:
  607. </p>
  608.  
  609. <ul>
  610. <li>
  611. <p>
  612. Client-side password hashing is <b>not</b> a substitute for HTTPS
  613. (SSL/TLS). If the connection between the browser and the server is
  614. insecure, a man-in-the-middle can modify the JavaScript code as it is
  615. downloaded to remove the hashing functionality and get the user's
  616. password.
  617. </p>
  618. </li>
  619.  
  620. <li>
  621. <p>
  622. Some web browsers don't support JavaScript, and some users disable
  623. JavaScript in their browser. So for maximum compatibility, your app
  624. should detect whether or not the browser supports JavaScript and emulate
  625. the client-side hash on the server if it doesn't.
  626. </p>
  627. </li>
  628.  
  629. <li>
  630. <p>
  631. You need to salt the client-side hashes too. The obvious solution is to
  632. make the client-side script ask the server for the user's salt. Don't do
  633. that, because it lets the bad guys check if a username is valid without
  634. knowing the password. Since you're hashing and salting (with a good
  635. salt) on the server too, it's OK to use the username (or email)
  636. concatenated with a site-specific string (e.g. domain name) as the
  637. client-side salt.
  638. </p>
  639. </li>
  640. </ul>
  641.  
  642. <h3>Making Password Cracking Harder: Slow Hash Functions</h3>
  643.  
  644. <p>
  645. Salt ensures that attackers can't use specialized attacks like lookup tables
  646. and rainbow tables to crack large collections of hashes quickly, but it
  647. doesn't prevent them from running dictionary or brute-force attacks on each
  648. hash individually. High-end graphics cards (GPUs) and custom hardware can
  649. compute billions of hashes per second, so these attacks are still very
  650. effective. To make these attacks less effective, we can use a technique
  651. known as <b>key stretching</b>.
  652. </p>
  653.  
  654. <p>
  655. The idea is to make the hash function very slow, so that even with a fast
  656. GPU or custom hardware, dictionary and brute-force attacks are too slow to
  657. be worthwhile. The goal is to make the hash function slow enough to impede
  658. attacks, but still fast enough to not cause a noticeable delay for the user.
  659. </p>
  660.  
  661. <p>
  662. Key stretching is implemented using a special type of CPU-intensive hash
  663. function. Don't try to invent your own&ndash;simply iteratively hashing the
  664. hash of the password isn't enough as it can be parallelized in hardware and
  665. executed as fast as a normal hash. Use a standard algorithm like <a
  666. href="http://en.wikipedia.org/wiki/PBKDF2">PBKDF2</a> or <a href="http://en.wikipedia.org/wiki/Bcrypt">bcrypt</a>.
  667. You can find a PHP implementation of <a href="https://defuse.ca/php-pbkdf2.htm">PBKDF2 here</a>.
  668. </p>
  669.  
  670. <p>
  671. These algorithms take a security factor or iteration count as an argument.
  672. This value determines how slow the hash function will be. For desktop
  673. software or smartphone apps, the best way to choose this parameter is to run
  674. a short benchmark on the device to find the value that makes the hash take
  675. about half a second. This way, your program can be as secure as possible
  676. without affecting the user experience.
  677. </p>
  678.  
  679. <p>
  680. If you use a key stretching hash in a web application, be aware that you
  681. will need extra computational resources to process large volumes of
  682. authentication requests, and that key stretching may make it easier to run a
  683. Denial of Service (DoS) attack on your website. I still recommend using key
  684. stretching, but with a lower iteration count. You should calculate the
  685. iteration count based on your computational resources and the expected
  686. maximum authentication request rate. The denial of service threat can be
  687. eliminated by making the user solve a CAPTCHA every time they log in.
  688. Always design your system so that the iteration count can be increased or
  689. decreased in the future.
  690. </p>
  691.  
  692. <p>
  693. If you are worried about the computational burden, but still want to use key
  694. stretching in a web application, consider running the key stretching
  695. algorithm in the user's browser with JavaScript. The <a href="http://crypto.stanford.edu/sjcl/">Stanford JavaScript Crypto
  696. Library</a> includes PBKDF2. The iteration count should be set low enough
  697. that the system is usable with slower clients like mobile devices, and the
  698. system should fall back to server-side computation if the user's browser
  699. doesn't support JavaScript. Client-side key stretching does not remove the
  700. need for server-side hashing. You must hash the hash generated by the client
  701. the same way you would hash a normal password.
  702. </p>
  703.  
  704. <h3>Impossible-to-crack Hashes: Keyed Hashes and Password Hashing Hardware</h3>
  705.  
  706. <p>
  707. As long as an attacker can use a hash to check whether a password guess is
  708. right or wrong, they can run a dictionary or brute-force attack on the hash.
  709. The next step is to add a <b>secret key</b> to the hash so that only someone
  710. who knows the key can use the hash to validate a password. This can be
  711. accomplished two ways. Either the hash can be encrypted using a cipher like
  712. AES, or the secret key can be included in the hash using a keyed hash
  713. algorithm like <a href="http://en.wikipedia.org/wiki/HMAC">HMAC</a>.
  714. </p>
  715.  
  716. <p>
  717. This is not as easy as it sounds. The key has to be kept secret from an
  718. attacker even in the event of a breach. If an attacker gains full access to
  719. the system, they'll be able to steal the key no matter where it is stored.
  720. The key must be stored in an external system, such as a physically separate
  721. server dedicated to password validation, or a special hardware device
  722. attached to the server such as the <a href="https://www.yubico.com/YubiHSM">YubiHSM</a>.
  723. </p>
  724.  
  725. <p>
  726. I highly recommend this approach for any large scale (more than 100,000
  727. users) service. I consider it necessary for any service hosting more than
  728. 1,000,000 user accounts.
  729. </p>
  730.  
  731. <p>
  732. If you can't afford multiple dedicated servers or special hardware devices,
  733. you can still get some of the benefits of keyed hashes on a standard web
  734. server. Most databases are breached using <a
  735. href="http://en.wikipedia.org/wiki/SQL_injection">SQL Injection Attacks</a>,
  736. which, in most cases, don't give attackers access to the local filesystem
  737. (disable local filesystem access in your SQL server if it has this feature).
  738. If you generate a random key and store it in a file that isn't accessible
  739. from the web, and include it into the salted hashes, then the hashes won't
  740. be vulnerable if your database is breached using a simple SQL injection
  741. attack. Don't hard-code a key into the source code, generate it randomly
  742. when the application is installed. This isn't as secure as using a separate
  743. system to do the password hashing, because if there are SQL injection
  744. vulnerabilities in a web application, there are probably other types, such
  745. as Local File Inclusion, that an attacker could use to read the secret key
  746. file. But, it's better than nothing.
  747. </p>
  748.  
  749. <p>
  750. Please note that keyed hashes do not remove the need for salt. Clever
  751. attackers will eventually find ways to compromise the keys, so it is
  752. important that hashes are still protected by salt and key stretching.
  753. </p>
  754.  
  755. <a name="othersecurity"></a>
  756. <h2>Other Security Measures</h2>
  757.  
  758. <p>
  759. Password hashing protects passwords in the event of a security breach. It does
  760. not make the application as a whole more secure. Much more must be done to
  761. prevent the password hashes (and other user data) from being stolen in the first
  762. place.
  763. </p>
  764.  
  765. <p>
  766. Even experienced developers must be educated in security in order to write secure applications.
  767. A great resource for learning about web application vulnerabilities is
  768. <a href="https://www.owasp.org/index.php/Main_Page">The Open Web Application
  769. Security Project (OWASP)</a>. A good introduction is the
  770. <a href="https://www.owasp.org/images/7/72/OWASP_Top_10-2017_%28en%29.pdf.pdf">OWASP Top Ten Vulnerability List</a>.
  771. Unless you understand all the vulnerabilities on the list, do not attempt to
  772. write a web application that deals with sensitive data. It is the employer's
  773. responsibility to ensure all developers are adequately trained in secure
  774. application development.
  775. </p>
  776.  
  777. <p>
  778. Having a third party "penetration test" your application is a good idea. Even
  779. the best programmers make mistakes, so it always makes sense to have a security
  780. expert review the code for potential vulnerabilities. Find a trustworthy
  781. organization (or hire staff) to review your code on a regular basis. The
  782. security review process should begin early in an application's life and continue
  783. throughout its development.
  784. </p>
  785.  
  786. <p>
  787. It is also important to monitor your website to detect a breach if one does
  788. occur. I recommend hiring at least one person whose full time job is detecting
  789. and responding to security breaches. If a breach goes undetected, the attacker
  790. can make your website infect visitors with malware, so it is extremely important
  791. that breaches are detected and responded to promptly.
  792. </p>
  793.  
  794. <a name="faq"></a>
  795. <h2>Frequently Asked Questions</h2>
  796. <h3>What hash algorithm should I use?</h3>
  797. <span style="color: green;"><b>DO</b></span> use:
  798.  
  799. <ul class="moveul">
  800. <li>Well-designed key stretching algorithms such as <a href="http://en.wikipedia.org/wiki/PBKDF2">PBKDF2</a>, <a href="http://en.wikipedia.org/wiki/Bcrypt">bcrypt</a>, and <a href="http://www.tarsnap.com/scrypt.html">scrypt</a>.</li>
  801. <li>OpenWall's <a href="http://www.openwall.com/phpass/">Portable PHP password hashing
  802. framework</a></li>
  803. <li><a href="https://github.com/defuse/password-hashing">My implementations of PBKDF2 in PHP, C#, Java, and Ruby.</a></li>
  804. <li>Secure versions of <a href="http://en.wikipedia.org/wiki/Crypt_(Unix)#Library_Function_crypt.283.29">crypt</a> ($2y$, $5$, $6$)</li>
  805. </ul>
  806. <br />
  807. <span style="color: red;"><b>DO NOT</b></span> use:
  808.  
  809. <ul class="moveul">
  810. <li>Fast cryptographic hash functions such as MD5, SHA1, SHA256, SHA512, RipeMD, WHIRLPOOL, SHA3, etc.</li>
  811. <li>Insecure versions of crypt ($1$, $2$, $2x$, $3$).</li>
  812. <li>Any algorithm that you designed yourself. Only use technology that is in the public domain and has been well-tested by experienced cryptographers.</li>
  813. </ul>
  814.  
  815. <p>
  816. Even though there are no cryptographic attacks on MD5 or SHA1 that make
  817. their hashes easier to crack, they are old and are widely considered
  818. (somewhat incorrectly) to be inadequate for password storage. So I don't
  819. recommend using them. An exception to this rule is PBKDF2, which is
  820. frequently implemented using SHA1 as the underlying hash function.
  821. </p>
  822. <h3>How should I allow users to reset their password when they forget it?</h3>
  823.  
  824. <p>
  825. It is my personal opinion that all password reset mechanisms in widespread
  826. use today are insecure. If you have high security requirements, such as an
  827. encryption service would, do not let the user reset their password.
  828. </p>
  829.  
  830. <p>
  831. Most websites use an email loop to authenticate users who have forgotten their
  832. password. To do this, generate a random <b>single-use</b> token that is strongly
  833. tied to the account. Include it in a password reset link sent to the user's
  834. email address. When the user clicks a password reset link containing a valid
  835. token, prompt them for a new password. Be sure that the token is strongly tied
  836. to the user account so that an attacker can't use a token sent to his own email
  837. address to reset a different user's password.
  838. </p>
  839.  
  840. <p>
  841. The token must be set to expire in 15 minutes or after it is used, whichever
  842. comes first. It is also a good idea to expire any existing password tokens when
  843. the user logs in (they remembered their password) or requests another reset
  844. token. If a token doesn't expire, it can be forever used to break into the
  845. user's account. Email (SMTP) is a plain-text protocol, and there may be
  846. malicious routers on the internet recording email traffic. And, a user's email
  847. account (including the reset link) may be compromised long after their password
  848. has been changed. Making the token expire as soon as possible reduces the
  849. user's exposure to these attacks.
  850. </p>
  851.  
  852. <p>
  853. Attackers will be able to modify the tokens, so don't store the user account
  854. information or timeout information in them. They should be an unpredictable
  855. random binary blob used only to identify a record in a database table.
  856. </p>
  857.  
  858. <p>
  859. Never send the user a new password over email. Remember to pick a new random
  860. salt when the user resets their password. Don't re-use the one that was used to
  861. hash their old password.
  862. </p>
  863.  
  864. <h3>What should I do if my user account database gets leaked/hacked?</h3>
  865.  
  866. <p>
  867. Your first priority is to determine how the system was compromised and patch
  868. the vulnerability the attacker used to get in. If you do not have experience
  869. responding to breaches, I highly recommend hiring a third-party security firm.
  870. </p>
  871.  
  872. <p>
  873. It may be tempting to cover up the breach and hope nobody notices. However, trying to cover up a breach makes you look worse, because you're putting
  874. your users at further risk by not informing them that their passwords and other
  875. personal information may be
  876. compromised. You must inform your users as soon as possible&mdash;even if you don't yet fully understand what happened. Put a notice on the
  877. front page of your website that links to a page with more detailed information,
  878. and send a notice to each user by email if possible.
  879. </p>
  880.  
  881. <p>
  882. Explain to your users exactly how their passwords were protected&mdash;hopefully
  883. hashed with salt&mdash;and that even though they were protected with a salted
  884. hash, a malicious hacker can still run dictionary and brute force attacks on the
  885. hashes. Malicious hackers will use any passwords they find to try to login to a
  886. user's account on a different website, hoping they used the same password on
  887. both websites. Inform your users of this risk and recommend that they change
  888. their password on any website or service where they used a similar password.
  889. Force them to change their password for your service the next time they log in.
  890. Most users will try to "change" their password to the original password to get
  891. around the forced change quickly. Use the current password hash to ensure that
  892. they cannot do this.
  893. </p>
  894.  
  895. <p>
  896. It is likely, even with salted slow hashes, that an attacker will be able to
  897. crack some of the weak passwords very quickly. To reduce the attacker's window of opportunity to use these passwords, you should require, in
  898. addition to the current password, an email loop for authentication until the
  899. user has changed their password. See the previous question, "How should I allow
  900. users to reset their password when they forget it?" for tips on implementing
  901. email loop authentication.
  902. </p>
  903.  
  904. <p>
  905. Also tell your users what kind of personal information was stored on the
  906. website. If your database includes credit card numbers, you should instruct your
  907. users to look over their recent and future bills closely and cancel their
  908. credit card.
  909. </p>
  910.  
  911. <h3>What should my password policy be? Should I enforce strong passwords?</h3>
  912. <p>
  913. If your service doesn't have strict security requirements, then don't limit your
  914. users. I recommend showing users information about the strength of their
  915. password as they type it, letting them decide how secure they want their
  916. password to be. If you have special security needs, enforce a minimum length of
  917. 12 characters and require at least two letters, two digits, and two symbols.
  918. </p>
  919. <p>
  920. Do not force your users to change their password more often than once every six
  921. months, as doing so creates "user fatigue" and makes users less likely to choose
  922. good passwords. Instead, train users to change their password whenever they feel
  923. it has been compromised, and to never tell their password to anyone. If it is a
  924. business setting, encourage employees to use paid time to memorize and practice
  925. their password.
  926. </p>
  927.  
  928. <h3>If an attacker has access to my database, can't they just replace the hash of my password with their own hash and login?</h3>
  929.  
  930. <p>
  931. Yes, but if someone has accesss to your database, they probably already have
  932. access to everything on your server, so they wouldn't need to login to your
  933. account to get what they want. The purpose of password hashing (in the context
  934. of a website) is not to protect the website from being breached, but to protect
  935. the passwords if a breach does occur.
  936. </p>
  937.  
  938. <p>
  939. You can prevent hashes from being replaced during a SQL injection attack by
  940. connecting to the database with two users with different permissions. One for
  941. the 'create account' code and one for the 'login' code. The 'create account'
  942. code should be able to read and write to the user table, but the 'login' code
  943. should only be able to read.
  944. </p>
  945.  
  946. <h3>Why do I have to use a special algorithm like HMAC? Why can't I just append
  947. the password to the secret key?</h3>
  948.  
  949. <p> Hash functions like MD5, SHA1, and SHA2 use the <a href="http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction">
  950. Merkle–Damgård construction</a>, which makes them vulnerable to what are known
  951. as length extension attacks. This means that given a hash H(X), an attacker can
  952. find the value of H(pad(X) + Y), for any other string Y, without knowing X.
  953. pad(X) is the padding function used by the hash.
  954. </p>
  955.  
  956. <p>
  957. This means that given a hash H(key + message), an attacker can compute H(pad(key +
  958. message) + extension), without knowing the key. If the hash was being used as a
  959. message authentication code, using the key to prevent an attacker from being
  960. able to modify the message and replace it with a different valid hash, the
  961. system has failed, since the attacker now has a valid hash of message +
  962. extension.
  963. </p>
  964.  
  965. <p>
  966. It is not clear how an attacker could use this attack to crack a password hash
  967. quicker. However, because of the attack, it is considered bad practice to
  968. use a plain hash function for keyed hashing. A clever cryptographer may one day
  969. come up with a clever way to use these attacks to make cracking faster, so use
  970. HMAC.
  971. </p>
  972.  
  973.  
  974. <h3>Should the salt come before or after the password?</h3>
  975.  
  976. <p>
  977. It doesn't matter, but pick one and stick with it for interoperability's sake.
  978. Having the salt come before the password seems to be more common.
  979. </p>
  980.  
  981. <h3>Why does the hashing code on this page compare the hashes in
  982. &quot;length-constant&quot;
  983. time?</h3>
  984.  
  985. <p>
  986. Comparing the hashes in &quot;length-constant&quot; time ensures that an
  987. attacker cannot extract the hash of a password in an on-line system using a
  988. timing attack, then crack it off-line.
  989. </p>
  990.  
  991. <p>
  992. The standard way to check if two sequences of bytes (strings) are the same is to
  993. compare the first byte, then the second, then the third, and so on. As soon as
  994. you find a byte that isn't the same for both strings, you know they are
  995. different and can return a negative response immediately. If you make it through
  996. both strings without finding any bytes that differ, you know the strings are the
  997. same and can return a positive result. This means that comparing two strings can
  998. take a different amount of time depending on how much of the strings match.
  999. </p>
  1000.  
  1001. <p>
  1002. For example, a standard comparison of the strings &quot;xyzabc&quot; and
  1003. &quot;abcxyz&quot; would immediately see that the first character is different
  1004. and wouldn't bother to check the rest of the string. On the other hand, when the
  1005. strings &quot;aaaaaaaaaaB&quot; and &quot;aaaaaaaaaaZ&quot; are compared, the
  1006. comparison algorithm scans through the block of "a" before it determines the
  1007. strings are unequal.
  1008. </p>
  1009.  
  1010. <p>
  1011. Suppose an attacker wants to break into an on-line system that rate limits
  1012. authentication attempts to one attempt per second. Also suppose the attacker
  1013. knows all of the parameters to the password hash (salt, hash type, etc), except
  1014. for the hash and (obviously) the password. If the attacker can get a precise
  1015. measurement of how long it takes the on-line system to compare the hash of the
  1016. real password with the hash of a password the attacker provides, he can use the
  1017. timing attack to extract part of the hash and crack it using an offline attack,
  1018. bypassing the system's rate limiting.
  1019. </p>
  1020.  
  1021. <p>
  1022. First, the attacker finds 256 strings whose hashes begin with every possible
  1023. byte. He sends each string to the on-line system, recording the amount of time
  1024. it takes the system to respond. The string that takes the longest will be the
  1025. one whose hash's first byte matches the real hash's first byte. The attacker now
  1026. knows the first byte, and can continue the attack in a similar manner on the
  1027. second byte, then the third, and so on. Once the attacker knows enough of the
  1028. hash, he can use his own hardware to crack it, without being rate limited by the
  1029. system.
  1030. </p>
  1031.  
  1032. <p>
  1033. It might seem like it would be impossible to run a timing attack over a network.
  1034. However, it has been done, and has been
  1035. <a href="https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf">shown to be practical</a>.
  1036. That's why the code on this page compares strings in a way that takes the same
  1037. amount of time no matter how much of the strings match.
  1038. </p>
  1039.  
  1040. <a name="slowequals"></a>
  1041. <h3>How does the SlowEquals code work?</h3>
  1042.  
  1043. <p>
  1044. The previous question explains why SlowEquals is necessary, this one explains
  1045. how the code actually works.
  1046. </p>
  1047.  
  1048. <div class="passcrack">
  1049. 1. &nbsp;&nbsp; &nbsp;private static boolean slowEquals(byte[] a, byte[] b)<br />
  1050. 2. &nbsp;&nbsp; &nbsp;{<br />
  1051. 3. &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;int diff = a.length ^ b.length;<br />
  1052. 4. &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;for(int i = 0; i &lt; a.length &amp;&amp; i &lt; b.length; i++)<br />
  1053. 5. &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;diff |= a[i] ^ b[i];<br />
  1054. 6. &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;return diff == 0;<br />
  1055. 7. &nbsp;&nbsp; &nbsp;}<br />
  1056. </div>
  1057.  
  1058. <p>
  1059. The code uses the XOR "^" operator to compare integers for equality, instead of
  1060. the "==" operator. The reason why is explained below. The result of XORing
  1061. two integers will be zero if and only if they are exactly the same. This is
  1062. because 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1. If we apply that to
  1063. all the bits in both integers, the result will be zero only if all the bits
  1064. matched.
  1065. </p>
  1066.  
  1067. <p>
  1068. So, in the first line, if <code>a.length</code> is equal to
  1069. <code>b.length</code>, the diff variable will get a zero value, but if not, it
  1070. will get some non-zero value. Next, we compare the bytes using XOR, and OR the
  1071. result into diff. This will set diff to a non-zero value if the bytes differ.
  1072. Because ORing never un-sets bits, the only way diff will be zero at the end of
  1073. the loop is if it was zero before the loop began (a.length == b.length) and all
  1074. of the bytes in the two arrays match (none of the XORs resulted in a non-zero
  1075. value).
  1076. </p>
  1077.  
  1078. <p>
  1079. The reason we need to use XOR instead of the "==" operator to compare integers
  1080. is that "==" is usually translated/compiled/interpreted as a branch. For example,
  1081. the C code "<code>diff &amp;= a == b</code>" might compile to the following x86
  1082. assembly:
  1083. </p>
  1084.  
  1085. <div class="passcrack">
  1086. MOV EAX, [A]<br />
  1087. CMP [B], EAX<br />
  1088. JZ equal<br />
  1089. JMP done<br />
  1090. equal:<br />
  1091. AND [VALID], 1<br />
  1092. done:<br />
  1093. AND [VALID], 0<br />
  1094. </div>
  1095.  
  1096. <p>
  1097. The branching makes the code execute in a different amount of time depending on
  1098. the equality of the integers and the CPU's internal branch prediction state.
  1099. </p>
  1100.  
  1101. <p>
  1102. The C code "<code>diff |= a ^ b</code>" should compile to something like
  1103. the following, whose execution time does not depend on the equality of the
  1104. integers:
  1105. </p>
  1106.  
  1107. <div class="passcrack">
  1108. MOV EAX, [A]<br />
  1109. XOR EAX, [B]<br />
  1110. OR [DIFF], EAX <br />
  1111. </div>
  1112.  
  1113. <h3>Why bother hashing?</h3>
  1114.  
  1115. <p>
  1116. Your users are entering their password into your website. They are trusting you
  1117. with their security. If your database gets hacked, and your users' passwords are
  1118. unprotected, then malicious hackers can use those passwords to compromise your
  1119. users' accounts on other websites and services (most people use the same
  1120. password everywhere). It's not just your security that's at risk, it's your
  1121. users'. You are responsible for your users' security.
  1122. </p>
  1123.  
  1124. <div style="text-align: center;">
  1125. <h4>Article written by <a href="https://defuse.ca/">Defuse Security.</a></h4>
  1126. </div>
  1127. </div>
  1128.  
  1129. </div> <!-- Wrap -->
  1130. <div id="footerwrapper">
  1131. <div id="footerborder"></div>
  1132. <div id="footer">
  1133. <table>
  1134. <tr>
  1135. <th>Last Modified: &nbsp;&nbsp;</th>
  1136. <td>July 30, 2018, 2:17am UTC</td>
  1137. </tr>
  1138. <tr>
  1139. <th>Page Hits:</th>
  1140. <td>9216615</td>
  1141. </tr>
  1142. <tr>
  1143. <th>Unique Hits:</th>
  1144. <td>2086972</td>
  1145. </tr>
  1146. </table>
  1147. <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US"><img alt="Creative Commons License" style="border-width:0; vertical-align: bottom;" src="/images/cc-by-sa.png" /></a>
  1148. <a href="https://defuse.ca/">Defuse Security</a> |
  1149. <a href="https://z.cash/">Zcash</a> |
  1150. <a href="https://defuse.ca/pastebin.htm">Secure Pastebin</a> |
  1151. <a href="https://github.com/defuse/crackstation">Source Code</a>
  1152. </div> <!-- end footer -->
  1153. </div> <!-- footerwrapper -->
  1154. <!-- Piwik -->
  1155. <script type="text/javascript">
  1156. var _paq = _paq || [];
  1157. _paq.push(["setDoNotTrack", true]);
  1158. _paq.push(["trackPageView"]);
  1159. _paq.push(["enableLinkTracking"]);
  1160.  
  1161. (function() {
  1162. var u=(("https:" == document.location.protocol) ? "https" : "http") + "://defuse.ca/piwik/";
  1163. _paq.push(["setTrackerUrl", u+"piwik.php"]);
  1164. _paq.push(["setSiteId", "2"]);
  1165. var d=document, g=d.createElement("script"), s=d.getElementsByTagName("script")[0]; g.type="text/javascript";
  1166. g.defer=true; g.async=true; g.src=u+"piwik.js"; s.parentNode.insertBefore(g,s);
  1167. })();
  1168. </script>
  1169. <noscript>
  1170. <img src="https://defuse.ca/piwik/piwik.php?idsite=2&amp;rec=1" style="border:0" alt="" />
  1171. </noscript>
  1172. <!-- End Piwik Code -->
  1173.  
  1174. <!--[if !(lt IE 8)]><!-->
  1175. <script type="text/javascript">
  1176. (function(){var e=document.createElement("script");e.type="text/javascript";e.async=true;e.src=document.location.protocol+"//d1agz031tafz8n.cloudfront.net/thedaywefightback.js/widget.min.js";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)})()
  1177. </script>
  1178. <!--<![endif]-->
  1179. </body>
  1180. </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement