How to create a truly random and provably secure password

Password managers such as KeePass, 1Password and many others solve this problem to a large extent. With their help, you can generate a unique and secure password for each site that you visit. But such a manager is only as secure as the master password that you use to access it. You must be sure that its sufficient randomness and predictability is confirmed by quantitative measurements, and not only by the fact that you perceive it random due to the presence of several numbers or exclamation marks. If we need true randomness, we will need something special.

Fortunately, there is an opportunity to buy something inexpensive, with sufficient entropy of a set of probabilities and capable of generating 3 bits of information at a time. Without electricity and reliably enough, allowing hundreds of millions of dollars to change owners daily, based on the infallibility of this accident.



Throwing a dice allows you to get a random number from 1 to 6, which gives us 2.58 bits of information.

The founder of the theory of information, Claude Shannon, defined information as filmed uncertainty. More precisely, obtaining information is a prerequisite for removing uncertainty. Uncertainty arises in a situation of choice. The task that is solved in the course of removing uncertainty is to reduce the number of options considered (reduce diversity), and as a result, select one option from the number of possible situations. Removing uncertainty makes it possible to make informed decisions and act. This is the controlling role of information.

Entropy is a measure of uncertainty expressed in bits. Entropy can also be considered as a measure of the uniformity of the distribution of a random variable.



In fact, there are no integers, so we always round to the nearest bit. In this case, we need 3 bits to store a number from 1 to 6, but in fact we can store from 0 to 7: The number of combinations of 0 and 1 determines how large a number you can store using a certain number of bits. Each time you add one more bit, you double the number of combinations. It's simple enough: if you add one more bit to the binary number, you will have all the combinations that you had twice before: with 0 to the left of them and with 1. In fact, a variable with the nth number of bits can have 2 ^ n (2 to the power of n) possible values. Since a byte consists of 8 bits, it can have 2 ^ 8 (256) possible values.

000 - 0
001 - 1
010 - 2
011 - 3
100 - 4
101 - 5
110 - 6
111 - 7





The size of a variable imposes restrictions on the amount of information that it can store - variables that use more bytes, respectively, can store a wider range of values.

Computers have a limited amount of free memory. Each time we declare a variable, a small portion of this free memory is allocated as long as the variable exists. Since modern computers have a lot of memory, in most cases this is not a problem, especially when the program has only a few variables. However, for programs that require a large number of variables (for example, 100,000), the difference between using 1-byte or 8-byte variables can be significant.


So the video game The Legend of Zelda, released in 1987, was 8-bit and had a limit for variable values ​​of 255.

I would like the entropy to select my password to be at least 128 bits. According to most studies, breaking 128-bit encryption is practically impossible using brute force methods in less than a few billion years. Using the 2 ^ n equation, we can store one of 3.4 * 10³⁸ different values ​​using 128 bits. If you could test 100 billion possible values ​​per second, it would still take tens of trillions of years to guess the correct password. I find this good enough. A 128-bit password will almost certainly not be a weak link in your online security chain.

If each of our dice produces 2.58 bits of entropy in one roll, then tossing five will give us 12.9 bits. If we use 5 dice 10 times, then we will get 129 bits of information, and for those who do not know the results, we will create uncertainty or entropy equal to 129 bits.

But how to turn these results into a secure but memorable password?

I am using diceware, which is a dictionary of words indexed by the results of a toss of five dice. Each time you roll 5 dice (or once 5 times), the numbers that come out correspond to the word in the list. For example, if 1-4-2-6-3 fell on 5 dice, you need to go to the page with all the words 14xxx and find that 14263 corresponds to “blab”. Do it ten times and you will get a string of ten words. These ten words are a potential password.

Further, mnemonics will help us - a set of special techniques and methods that make it easier to remember the necessary information and increase the amount of memory by forming associations (connections). For example, you can use the "principle of the plot" - to compose a story (plot) in which memorized words are involved. For example, in order to remember the sequence of words: “Elephant, house, TV”, we think up: “The elephant went to his house to watch TV”. You may feel stupid, but it works and you will be surprised how quickly you can remember things that way.



In PDF format, one of the dictionary versions is available here , and here is the Russian version.

If all this seems redundant, remember that this is the password that stores all your financial and online life. If you think it's worth it, go down to the comic book store and buy the dice. Go into a room where there are no cameras, telephones or computers, roll cubes and write the corresponding words from the dictionary (I would choose 15 words to remove a few that I would not know). Then select ten words and memorize them. This is your password. Keep the record for several days until you are sure to remember the password that you are asked to use to enter the password manager.

Now you know how to get a password that is truly and provably random, that has not been controlled or generated by a third party for you, and that is safely stored in your mind. You can use it for several years, and this is the only password that you will need to know. Even if someone knows that you used 10 words, and you know which dictionary you used, they will still have to “break through” through 129 exhausting bits of entropy.

Remove the foil cap and continue your life. Wearing it from time to time is normal.

Comment Cloud4Y

Earlier this question was raised on Habrahabr in posts " Educational program on pseudo-random generators " and " Practical recommendations for choosing passwords based on the results of the antichat.ru hack ".

The main findings of the author:

1. It is not so important how the program generator receives passwords, how much - from where it takes the initial data. If no interactivity occurs at all, one should doubt it.
2. A person can hardly keep track of the absence of statistically popular password combinations, which is confirmed by the selection of 31,790 passwords from 41037 MD5 hashes in 8 hours.

In this regard, the method described by Charlie Hoey can be useful especially in the absence of two-factor authentication.

For added security without adding new words, insert one special character or number randomly selected into your passphrase. Here's how to do it safely: roll one die to select a word in your phrase, repeat to select a letter in that word. Throw dice a third and fourth time to select the added character from the following table:

1 2 3 4 5 6
1 ~! # $% ^
2 & * () - =
3 + [] \ {}
4 :; "<>
5? / 0 1 2 3
6 4 5 6 7 8 9

Inserting a letter in a random order will add about 10 bits of entropy. All this, of course, implies the secrecy of the code phrase.

PS I
also recommend Charlie Hoey’s article “ A Eulogy for the Headphone Jack ”, in which he describes how, having no insurance, he saved $ 1000 by checking his own health by collecting an ECG apparatus and why it is important for us to save headphone jack and do not lose access to the almost universal and license-free I / O port.

This article and the translation of his articles above are similar in their idea of ​​how important and pleasant it is to understand how everything works in the technological space surrounding us.