Password Security Part 1

I will start the blog with a series on passwords. My aim is to cover all aspects of password security, to achieve a deep understanding of how to best secure passwords, and to show why even the best practices are fundamentally limited. If you have specific questions related to password security that you would like me to cover, please let me know and I’ll be happy to relate.

Before beginning, the first thing we have to understand is what a password is, or to be more exact, in what way does a password differ from a key. Simply stated, a password is a string that can be memorized by a human being and as such is “short”. In order to understand what I mean by short, think about a truly random 8 character password (made up of uppercase and lower case letters, digits, and 10 symbols). Few human beings alive are capable of remembering a truly random password this long, and I am no exception. Anyway, there are 72 different possible characters, and thus the total number of possible passwords of length 8 is 72^8 = 2^49. Although this is a very large number, it is possible to carry out 2^49 computations without too much cost. In practice, most passwords are much shorter, and come from a much smaller space. (Even when forced to use a password of “this form” by a strict password policy, most people start with one upper case letter, followed by a few lower case letters, followed by a few digits, and finish with a single symbol. This is a much smaller space and actually contains only 26 x 26^3 x 10^3 x 10 passwords, which comes to just 2^32. In general, the situation is much worse, and according to some studies, 20% of user passwords come from a dictionary of just 5000 possibilities. We will discuss how real user passwords are distributed in more detail later on in this series. ) For now, just remember that passwords are short. In contrast, cryptographic keys are long, and all the computational power in the world does not suffice for trying all keys. For example, consider a 128 bit random key. 2^128 is way beyond any organization’s computing power today. (My personal guess is that big organizations can get to 2^80 and maybe a little more. This is way lower than 2^128. Just to put this in perspective, the number of seconds since the big bang is estimated to be about 2^58.)

Given this distinction, we can already understand why using a password as an encryption key is such a bad idea. For example, consider a password used as a key to encrypt a file (using any encryption algorithm; it doesn’t matter). An attacker can try all possible passwords and try to decrypt. Since only one will encrypt correctly and since the space of all possible passwords can be traversed, the password will be discovered and the file decrypted within reasonable time. This isn’t as easy as it sounds, and to do it effectively a base dictionary has to be used and a method for trying the more common passwords has to be developed. However, this work has been done and is devastatingly effective.

In contrast to using a password to encrypt a file, in some cases very short passwords are actually good enough. For example, have you ever wondered why 4 digits are enough for ATMs? The answer is that it simply isn’t possible to try all possible PINs for an ATM card since the ATM machine will confiscate the card after just a few incorrect entries. This brings us to the important distinction between offline dictionary attacks and online dictionary attacks.

In an offline dictionary attack, the attacker has information that enables it to verify if a password guess is correct or not, and thus it can try all passwords locally on its own powerful machines. In the file encryption example, the encrypted file itself actually contains all the information needed to verify the password (since in practice only the correct password will decrypt to a valid file).

In contrast, in an online attack, the attacker can only verify a password guess by interacting with an external device or machine. Thus, online attacks can be easily thwarted. One method is to lock the account if too many incorrect guesses have been made (i.e., using a so called retry counter). Another method is to exponentially slow down the response every time an incorrect guess is submitted.

In the next post we will talk about how password verification is carried out (on PCs and on remote servers), and what this means regarding the ability to carry out online and offline dictionary attacks.

Prof. Yehuda Lindell

Prof. Yehuda Lindell

Yehuda Lindell is a professor of Computer Science at Bar-Ilan University in Israel. He is an expert on cryptography, has published over 90 scientific articles, and has authored one of the most widely used textbooks on the subject. He has years of industry experience in the application of cryptography to computer security.

Subscribe to BLOG

shares