class: big, middle # ECE 7420 / ENGI 9823: Security .title[ .lecture[Lecture 13:] .title[Passwords] ] --- # Recall: hash functions -- ### _Diffusion:_ small changes ⇒ large effects -- ### All values should be equally likely -- ### Should resist: Collision attack ??? ### Collision attack Finding **any two messages** that hash to the same value. When we get to digital signatures, we'll see that collision attacks can be quite important: if you can generate two messages with different meanings but the same hash, you can cause a lot of trouble! However, such attacks aren't so useful for password security. Even with the strongest hash function, collisions are **easier to find than you might think** due to the [birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem). However, "easier" doesn't have to be "easy": if the hash output is large, you can still have a lot of work to do! $\sqrt{2^n}$ can still be a large number if $n$ is big enough... -- : find $X_1, X_2$ s.t. $h(X_1) = h(X_2)$ -- Preimage attack ??? ### Preimage attack Finding an input that hashes to the same value as a given hash. This could be the same input that was originally used to generate the hash or a different one. -- : given $h(X_1)$, find $X_2$ s.t. $h(X_1) = h(X_2)$ -- 2nd preimage attack ??? ### Second preimage attack Finding a **different** input that will hash to the same value as a given input. This is like a collision attack, but much harder: instead of generating lots of messages and finding two that hash to the same value, you have to find one that hashes to the same value **as a specific input**. -- : given $X_1$, find $X_2 \neq X_1$ s.t. $h(X_1) = h(X_2)$ --- # MAC generalization ### Can we MAC without a block cipher? -- ### HMAC: hash-based message authentication code* .footnote[ * Bellare, Canetti and Krawczyk, "Keying Hash Functions for Message Authentication", [CRYPTO 1996](https://link.springer.com/chapter/10.1007/3-540-68697-5_1), 1996. Standardized by NIST ([FIPS 198-1](https://csrc.nist.gov/publications/detail/fips/198/1/final)) and the IETF ([RFC 2104](https://datatracker.ietf.org/doc/html/rfc2104)). ] -- $$ h\left((k \oplus p_o) || h((k \oplus p_i) || text) \right) $$ ??? An HMAC uses a hash function _with_ a key. This provides the same security properties as a block-cipher–based MAC, just with a different underlying cryptographic algorithm. HMACs are pretty popular in circumstances where you'd be doing a bunch of hashing anyway (e.g., Transport Layer Security cipher suites, which we'll talk about later). --- # Password hashing -- ### Resisting *offline* dictionary attacks* .footnote[ * see, e.g., <a href="https://www.openwall.com/john/">John the Ripper</a> ] ??? We don't need _any_ cryptography to resist an online dictionary attack. Protecting password databases is, instead, all about resisting **offline attack**, where an adversary has gained access to a password database and they want to get passwords from it. Without any cryptography, they can simply do a database lookup. With cryptography, however, we can make things much harder for them. --- # Password hashing ### Resisting *offline* dictionary attacks* ### Rainbows† and salt .footnote[ * see, e.g., <a href="https://www.openwall.com/john/">John the Ripper</a> † Oeschslin, "Making a Faster Cryptanalytic Time-Memory Trade-Off", CRYPTO 2003: Advances in Cryptology - CRYPTO 2003, 2003. DOI: [10.1007/978-3-540-45146-4_36]( https://dx.doi.org/10.1007/978-3-540-45146-4_36). ] ??? We don't need _any_ cryptography to resist an online dictionary attack. Protecting password databases is, instead, all about resisting **offline attack**, where an adversary has gained access to a password database and they want to get passwords from it. Without any cryptography, they can simply do a database lookup. With cryptography, however, we can make things much harder for them. As a (very bad!) alternative to password hashing, check out [this analysis](https://nakedsecurity.sophos.com/2013/11/04/anatomy-of-a-password-disaster-adobes-giant-sized-cryptographic-blunder) of a major password database breach at Adobe. -- ### Iterative password hashing (KDFs) ??? Tools like GPUs are really good at parallel computation. Attackers can use them to try lots and lots of passwords concurrently to see if they can find the correct one (a bit like the Bombes in Bletchley Park!). **Key Derivation Functions** (KDFs) make life harder for an attacker by forcing computation to be **serial**. There is a cost for the user, too, but it's insignificant compared to the benefit of not having your password cracked when a business suffers a data breach! --- # What makes a good password? -- ### Hard to guess ??? Fundamentally, it should be hard for an attacker to guess a password. -- ### Complex? ??? Q: what's some common password guidance you've been given over the years? -- .centered[ <img src="https://assets.amuniversal.com/a11b6e70a0a0012f2fe600163e41dd5b" width="900"/> ] ??? We have ideas about what makes guessing harder: not using common words, maybe making passwords long, maybe using funny symbols. Some of these ideas are intuitive, others have been **drilled into us through repetition**. But _why_ would those things make it harder to guess a password? Before talking about sensible password policies, we need to understand just a little bit of information theory. One way of describing hard-to-guess-ness — but one which is often misunderstood — is the information-theoretic concept of _entropy_. --- # Entropy ### A measure of information --- <img src="https://i.pinimg.com/originals/2b/24/22/2b2422be536bd0e2d360afb61ff51d9e.jpg" align="right" height="600"/> # Entropy ### A measure of information * or disorder, or chaos... ??? The concept of entropy is much older than computing: entropy has been used for a long time in thermodynamics to describe the disordered-ness of systems. In a closed system, entropy is a monotonically non-decreasing quantity, i.e., left alone, a closed system will become less ordered and more chaotic. The "heat death of the universe" doesn't refer to things getting really hot, it refers to an increase of random motion to the point that there is no structure, no separation between hot and cold, so no useful work can be done. -- * thermodynamics: [Maxwell's demon](https://en.wikipedia.org/wiki/Maxwell%27s_demon) ??? <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Maxwell%27s_demon.svg/800px-Maxwell%27s_demon.svg.png" align="right" width="300"/> _Maxwell's demon_ refers to a theoretical idea that links thermodynamics and information theory. Normally, if you bring hot and cold things together, their temperature evens out. However, if you could control the interface between two chambers of gas such that you open the door for faster molecules going right and slower molecules going left, but close the door for other molecules, you could make lukewarm gas turn into hot gas in one chamber and cold in the other. Would this violate the second law of thermodynamics? No, because the **information required to do this** affects the entropy! -- * units: _Shannons_ -- (a.k.a., bits!) --- # Measuring entropy -- ### Shannon entropy: -- $$ H(\textbf{X}) = - \sum_{i=0}^n P(x_i) \log_b P(x_i) $$ -- .footnote[ _Guessing entropy_, which is more directly relevant to password guessing, is a bit harder to calculate, but it is bounded by Shannon entropy. See: [Massey, "Guessing and Entropy", _Proc. IEEE Int. Symp. on Info. Th._, 1994](https://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI633.pdf). ] ??? Claude Shannon defined one way of measuring entropy, based on how **surprising** specific values in a distribution are. In this definition, a distribution that includes only equally-likely values will have higher entropy than a distribution that has a different distribution. Important note: **the values themselves don't matter!** -- ### Hartley function: $$ H_0(\textbf{X}) = \log_b |\textbf{X}| $$ ??? The Hartley function can be used to compute Shannon entropy **when all values have the same probability**. --- # Estimating password entropy -- #### Eight random alphanumeric characters: ??? In this example, we're using 26 possible letters plus 10 digits, so a total of 36 symbols that can be used. Eight of these symbols means that there are $36^8$ possible passwords that can be formed with this scheme; if they are all **equally-likely**, we can use the Hartley function to calculate the entropy of this **distribution**. -- $H_0(\textbf{X})$ -- $ = \log_b |\textbf{X}|$ -- $ = \log_2 \left| 36^8 \right|$ -- $ = 41.6 \textrm{ Sh (bits)}$ -- #### Four diceware* words + two numbers: .footnote[ * See [EFF instructions](https://www.eff.org/dice) plus [Bonneau, "Deep Dive: EFF's New Wordlists for Random Passphrases", EFF, 2016]( https://www.eff.org/deeplinks/2016/07/new-wordlists-random-passphrases). ] -- $ H_0(\textbf{X}) = \log_2 \left| \left(6^4\right)^4 \times 10^2 \right| = 4 \times \log_2 \left| 6^4 \right| + \log_2 \left| 10^2 \right| = 48.0 \textrm{ Sh} $ ??? These calculations show how we can work with distributions that contain multiple components, e.g., multiple words or multiple classes of characters. It's worth noting, however, that the entropy of the distribution of passwords derived from just four diceware words would be: $$ H_0(\textbf{X}) = \log_2 \left| \left(6^4\right)^4 \right| = 4 \times \log_2 \left| 6^4 \right| = 41.4 \textrm{ Sh} $$ So, four diceware words will stand up to a brute-force attack about as well as a random eight-character alphanumeric password. But which will be easier for a human to remember? -- ### But people don't choose random passwords! ??? Calculating the entropy of random distributions isn't so hard. Unfortunately, however, people typically don't use randomly-generated passwords (although they should!). --- # Actual password entropy <img src="https://wpengine.com/wp-content/uploads/2020/11/password-length-breakdown.png.webp" align="right" height="350"/> ## People don't choose random passwords! .footnote[ Source: <a href="https://wpengine.com/unmasked"> Unmasked: What 10 million passwords reveal about the people who choose them </a> ] --- # Actual password entropy <img src="../images/rockyou-pins.png" height="350" align="right"/> ### People don't choose random passwords! ### Or even random PINs! .footnote[ Wang et al., "Understanding Human-Chosen PINs: Characteristics, Distribution and Security", in _ASIA CCS '17_, 2017. DOI: <a href="https://doi.org/10.1145/3052973.3053031">10.1145/3052973.3053031</a>. ] ??? This graphic was taken from PINs that were found as a subset of the password in the original RockYou data set. For those curious about "RockYou 2021": [here's a nice writeup](https://chris.partridge.tech/2021/rockyou2021.txt-a-short-summary). -- * diagonal line: repetition -- * lots of `19xx` and even `20xx` --- .centered[ <img src="https://imgs.xkcd.com/comics/password_strength.png"/> ] .footnote[ Source: <a href="https://xkcd.com/936">XKCD 936</a> ] ??? XKCD, although it's a web comic, often has spot-on analysis. Comedy and satire can make a point in a punchier way than a prosey explanation, and this is no exception! --- # Entropy vs password strength -- * Shannon, Hartley entropies have clear definitions -- * Other entropies: min-entropy, guessing entropy... -- * Entropy a measure of a _distribution_, not a single password -- * Can estimate password entropy **assuming random selection** ??? If we assume that **a password was generated randomly**, we can compute the entropy of **the distribution that password was drawn from**. You should note that's exactly how I've phrased one of the questions in Assignment 2! -- * One website with one breach... -- [haveibeenpwned.com](https://haveibeenpwned.com) ??? We can learn things about actual user password choices, etc., from password databases that have been leaked. We can also learn whether or not particular passwords have been compromised! TODO: show https://pics.me.me/create-a-new-account-spacemoses1337-password-is-being-used-by-53149196.png -- ## What can we learn from this? ??? If a password has been leaked in the clear, **the site must've been doing something wrong**! Perhaps they weren't hashing, perhaps they weren't salting, perhaps they were allowing terrible password hints, but whatever it was, somebody should lose their Internet License! --- # Password guidance | (Modern) NIST guidance | Common guidance | |---------------|-----------------| | Minimum length >= 8 | Min length 8 | Maximum length >= 64 | Max length 16 | Pick and stick* | Change frequently | No algorithmic complexity | Character classes .footnote[ * See <a href="https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/florencio"> Florêncio, Herley and Oorschot, "Password Portfolios and the Finite-Effort User: Sustainably Managing Large Numbers of Accounts", in _USENIX Security 2014_. </a> ] ??? Some of these pieces of folk wisdom came from the previous NIST password guidance publication, others are accretions of myth on top of legend. The previous version of NIST's guidance was based on a very specific set of assumptions about the environment they'd be used: classified data that needs to be protected for a specific period of time (e.g., 15 years) against a dedicated cracker **with people who could be forced to use a random password**. The new guidance reflects reality for more general computer security uses. --- # More password guidance | (Modern) NIST guidance | Common guidance | |---------------|-----------------| | No hints | Allow <a href="https://nakedsecurity.sophos.com/2013/11/04/anatomy-of-a-password-disaster-adobes-giant-sized-cryptographic-blunder">"rhymes with assword"</a> | No KBA | Non-password passwords | Screen for compromises | ??? | Careful about 2FA | SMS FTW -- #### ... which will be the topic of our next lecture (2FA) --- class: big, middle The End.