Generating Secure Passwords
From Wolfekipedia
Contents |
Generating Secure Passwords
I will cut right to the chase and introduce the easiest and safest method first. This method is based on rolling two 6-sided dice.
Method #1
First, take a piece of paper (or open your favorite text editor on the computer) and write down the conversion table. You are going to write the numbers 0 through 35, with a digit or letter next to each number. Start with 0 = 0, 1 = 1... 9 = 9; then write 10 = a, 11 = b, down to 35 = z.
Because I'm so nice, I've already done this for you:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
-----------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z
For each password character, you will need to roll two dice (or one die, two times). The face values on the dice need to be converted, as follows: 1 through 5 = itself. 6 = 0. Now, multiply the first die outcome with 6, and add the second outcome to it. Example: your throw 3 and 6. The converted results are: 3 and 0. You calculate: 3 × 6 + 0 = 18.
Now, look up this number in the conversion table. In our example, this would be the letter "i". This is the first character of the password. Repeat until the password is long enough.
For a password equivalent to 128 random bits, you need 25 throws of the dice (50 throws with a single die), for a total of 25 password characters. Double this for 256 bits. Proof: 6log 2128 = 49.52 (Since we can't throw a die 49.52 times, we round up to 50.)
On the choice of characters
Now for some background. The above method uses a character set that can't be made much simpler. It's just letters and numbers, and we aren't even using mixed case. Nearly all systems will accept a password made of these characters, although in some exceedingly rare cases a system may choke if the password starts with a number. (In that case, simply prepend a random letter.) Why should you worry about character sets? Well, as I just said, not every character is equally well-received. PGP and GPG will pretty much accept any character you can type on the keyboard, while The Mental Militia Forums, to pick a completely random example, has trouble with < or > characters in the password, and it probably won't like the ampersand (&) or a space either. There may be other problem characters. Then there is the matter of password length. The larger your pool of characters, the shorter your password can be. This can be important, because some systems limit the password length to some arbitrary maximum. Some truncate the password without even telling you! I have seen web sites which limit the maximum length to a pitiful 8 characters!
The benefit of increasing the size of the character set is not as substantive as you might expect. This is because the number of choices must be doubled for every extra bit we want to pack into a single character. In the above example, each character packs just over 5 bits. If we were to add a coin to our throw, doubling the size of the table to 72 characters, we'd add exactly one extra bit per character. 6 bits instead of 5. That's "only" 20% extra, and yes, we can expect the password to be 20% shorter. 21 characters instead of 25. Method #5 will bring that down to 20 for a lot of trouble. Not that much saving, huh? So much for “your password must contain mixed case and gobbedlygook weird characters.” Just make your password 20% longer!
But... Sometimes every extra bit counts. Or you just happen to like complicated passwords. Or you want to make the password hard to type, hard to "eyeball", and hard to remember. (“Sorry mr. JBT, I forgot! Honest!”)
On ordering
If you throw more than one die and/or coin at the same time, you need some way to choose the first one, then the next, and so on until you have used every last one. Be careful not to sneak any bias into your throws by looking at the outcomes before choosing dice and/or coins. For example, do NOT always pick the lowest number first! The whole point of throwing dice is to obtain randomness. By ordering them, you defeat the purpose!
Better would be to cup your hand over the thrown dice and line them up from left to right. Then read their values from left to right. Or, if you have colored dice, for example one red and one green, always start with the red one, then the green.
Generate a new symbol table
Now we get to the advanced topics. You may stop reading if you want. First, we're going to build an 89-symbol table. Not every method uses this many symbols, but I don't want to keep creating new tables. So here we go:
We won't duplicate effort, so we start with the table of 36 symbols of method #1. I will assume that you have used lower case letters just as I did. Now we will extend the table by adding the upper case letters A through Z in positions #36 through #61. Well, that's it then. We have run out of "normal" characters, and we'll need to fill up the rest of the positions up to and including #88, with gobbedlygook. By my reckoning, there are 94 "printable" characters on a standard US keyboard. With the space bar, that makes up a total of 95, so you should not have trouble filling up the remainder of the 89 positions. I will leave you to decide which characters to put where, but I recommend dash (-) and dot (.) in positions #62 and #63. If you choose to use the space, put it last in position #88.
Method #2: Conservative, but packs more punch
This method uses 64 symbols of our table, and you need 6 coins. If you followed my suggestions in generating the table, then this set comprises of numbers, upper case, lower case, and the dash and the dot. The dash and the dot are part of normal text, and are unlikely to upset even fickle software. Thus, the whole set should be sufficiently conservative for most uses. Best bits/risk tradeoff.
How many bits do we get per character? 6 coins, so exactly 6 bits. Piece of cake. Then how many characters to the 128 bits? 128/6 = 21. Man, you'd almost think this stuff was easy!
Okay, down to business. First, let's assign some values to our coin flip. If a coin is tails, we assign it a value of zero. For heads, we will assign the following values: 1 for the first coin. 2 for the second. Then 4, 8, 16 and 32 for 3 through 6 respectively. Add all the values together. Choose from table. Rinse, repeat.
| Coin | Heads | Tails | Side | Value | |
|---|---|---|---|---|---|
| 1st | 1 | 0 | T | 0 | |
| 2nd | 2 | 0 | T | 0 | |
| 3rd | 4 | 0 | H | 4 | |
| 4th | 8 | 0 | T | 0 | |
| 5th | 16 | 0 | H | 16 | |
| 6th | 32 | 0 | H | 32 | + |
| | |||||
| 52 | → "Q" |
Method #3: Easy and fuzzy
This is for all you guys who want a secure and scary password without too much math. It is equal to the first method, but you add a coin to your two dice. If the coin is tails, the outcome is exactly the same as Method #1. If the coin is heads, add 36 to the number you got. Look up in table. Profit.
128 bits → 21 characters. 256 bits → 42 characters.
Method #4: Hex
This method is useful if you need to provide a password in hexadecimal format. May look like: ad:25:8c:00:31:0a:f3:65:c6:db:f2:70:5e:d8:7f:11 or ad258c00310af365c6dbf2705ed87f11. This is often used with WiFi access points, and dm_crypt when used "raw". Each character provides 4 bits. Do not count the colons as characters!
This goes much like Method #2. You need four coins, which values are 1, 2, 4 and 8.
Table for this:
Coins Value Symbol Coins Value Symbol Coins Value Symbol Coins Value Symbol TTTT 0 0 THTT 4 4 HTTT 8 8 HHTT 12 c TTTH 1 1 THTH 5 5 HTTH 9 9 HHTH 13 d TTHT 2 2 THHT 6 6 HTHT 10 a HHHT 14 e TTHH 3 3 THHH 7 7 HTHH 11 b HHHH 15 f
Method #5: Fairly complicated
This one uses the full symbol table of 89 characters. You need 5 dice, and for 128 bits, you need to roll them 10 times. (Or 50 single die rolls, total.) Double for 256 bits. We generate two characters for each 5-die roll.
Roll the dice. Convert 6 to 0 as usual. Start with the value of the first die. Multiply by 6. Add the value of the second die. Multiply the outcome by 6 again. Add the third die. Multiply by 6. Add fourth. Multiply by 6. Add fifth. Stop.
Divide the resultant number by 89. Look up the quotient (the outcome, rounded down) in the table → first character. Look up the remainder of the division in the table → second character. Roll again and repeat until satisfied.
With a calculator, this can be done as follows: Key in the number, and divide by 89. Look at the number before the decimal point and find it in the table → first character. Now, from the number on the calculator's display, subtract the number before the decimal point. Multiply the result by 89. Look up this number in the table → second character. Example: your number is 1024. You divide by 89 and the result is 11.505617977528. You find 11 in the table → "b". Subtract 11 from the number in the display. Result: 0.50561797752809. Multiply by 89. Result: 44.9999999999999 → 45 (The result should be a whole number, but due to small inaccuracies of the calculator, the number can be off very slightly. You need to round correctly in this step.) Find in table → "J".
