How to create a truly random and provably secure password

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

Fortunately, it is possible to buy something inexpensive, with a sufficient entropy of a set of probabilities and able to generate 3 bits of information at a time. Without electricity, and reliably enough, allowing hundreds of millions of dollars to change owners every day based on the infallibility of this randomness.
')


Throwing a die gives a random number from 1 to 6, which gives us 2.58 bits of information.

The founder of information theory, Claude Shannon, defined the information as a removed uncertainty. More precisely, obtaining information is a necessary condition for removing uncertainty. Uncertainty arises in a situation of choice. The task that is being solved during the removal of uncertainty is to reduce the number of options considered (decrease diversity), and as a result, select one appropriate option situation from among the possible ones. 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 non-integer ones, so we always round to the nearest bit. In this case, we need 3 bits to store the number from 1 to 6, but in fact we can store from 0 to 7:

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

The number of combinations of 0 and 1 determines how large a number you can store with a certain number of bits. Each time you add another bit, you double the number of combinations. It's simple enough: if you add one more bit to a binary number, you will have all the combinations that you have had twice before: with 0 to the left of them and 1.

In fact, a variable with an n-th number of bits can have 2 ^ n (2 to the power n) possible values. Since a byte consists of 8 bits, it can have 2 ^ 8 (256) possible values.

The size of the variable imposes restrictions on the amount of information 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 there are only a few variables in the program. 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 entropy for picking my password to be at least 128 bits. According to most studies, breaking a 128-bit encryption is almost impossible using brute force methods in less than a few billion years. Using equation 2 ^ n, we can store one of 3.4 * 10³⁸ of 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 it pretty good. A 128-bit password will almost certainly not be the weakest link in your online security chain.

If each of our dice produces 2.58 bits of entropy in one roll, then throwing 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 use Diceware , which is a vocabulary of words indexed using the results of throwing five dice. Each time you roll 5 dice (or one 5 times), the numbers that are produced correspond to the word in the list. For example, if on 5 dice fell 1-4-2-6-3, you need to go to the page with all the words 14xxx and find out that 14263 corresponds to “blab”. Do it ten times and you will get a line of ten words. These ten words are a potential password.

Next, the mnemonics will help us - a set of special techniques and methods that facilitate the memorization of the necessary information and increase the amount of memory through the formation of associations (links). For example, you can use the "plot principle" - to compose a story (plot), in which the memorized words are involved. For example, to memorize the sequence of words: “Elephant, house, TV,” we come up with: “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 versions of the dictionary is available at the link here , and here is the version in Russian.

If all this seems redundant, remember that this is the password behind which your entire financial and online life is stored. If you think it's worth it, go down to the comic book store and buy cubes. Go to a room where there are no cameras, phones or computers, roll the dice 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 log in to the password manager.

Now you know how to get a password that is valid and demonstrably random, which was not controlled or generated for you by a third party 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 have used 10 words, and you know which dictionary you used, they will still have to make their way 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 issue was raised on Habrahabr in posts " Likbez on pseudo-random generators " and " Practical recommendations on the choice of passwords on the results of hacking antichat.ru ".

The main conclusions obtained by the author:

1. It is not so important how the program generator receives passwords, how much - from where it takes the initial data. If there is no interaction at all, you should doubt it.
2. A person can hardly keep track of the absence of statistically popular combinations in the password, which is confirmed by the selection of 31790 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.

To increase security without adding new words, insert one special character or number randomly selected in 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 the dice for the third and fourth time to select the added symbol from the following table:

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

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

PS
I also recommend the Charlie Hoey article " A Eulogy for the Headphone Jack " (Praise Jack), in which he describes how, having no insurance, he saved $ 1000 on checking his own health, collecting an ECG machine, and why it is important for us to keep the connector headphone without losing access to an almost universal and license-free I / O port.

This article translated above is similar in its idea of ​​how important and pleasant it is to understand how everything works in the technological space around us.