class: big, middle # ECE 7420 / ENGI 9807: Security .title[ .lecture[Lecture 13:] .title[Password quality] ] --- # Recall ### AAA[A] ### Passwords * "password" files * dictionary attacks: online vs offline ### Cryptographic hash functions --- # Password hashing ### Resisting *offline* dictionary attacks* ### Rainbows† and salt ### Iterative password hashing (KDFs) .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. 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? .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.