In the FAQ, certain statements have been made. In this document, the rationale behind these statements is made explicit.
For the purpose of comparison, the Bit Rating (or the Effective Bit Rating) is:
log(Total Possibilities)÷log(2), or log2(Total Possibilities)
For example, a 40 bit encryption has:
It has 5 (40÷8) characters in the password.
This assumes that every possible character (256) might be used. If users enter only letters or numbers, then only 64 possible characters are used for each Windows character. The possiblities are:
It is hard to compare this with 240 so we find what the possibilities are to base 2:
log(625) ÷ log(2), or approximately:
Note that the difference between a 29 and 30 bit password is a factor of 2 (a 30 bit password is twice as strong as a 29 bit one).
This means that most 40 bit encryption (using only letters and numbers) is effectively only a little more than 29 bit encryption!
How are Password "bit ratings" related to Password Length?
Each character needs 8 bits. So a 128 bit password has 128/8 characters, or 16.
So password length=bit rating/8
How Many Passwords Can a 128 bit password hold?
A bit can hold a 0 or 1.
So for each bit there are 2 options.
For 128 bits there are 2128 possibilities
So 128 bit password can hold that number of different passwords.
How Many Different Passwords can be entered in a 128 bit Password Box?
The assumption of the previous section is that every Windows' character can be entered as a password. Each character needs 8 bits. There are 256 different characters in 8 bits (23). However, not all the 256 different characters in Windows can be typed. About 94 characters are printable (or typable) so if an encryption program does not have the option of entering all of these, then the full capacity cannot be utilised.
How does using Only Typable Characters affect the Number of Possibilities?
A 128 bit password has 128/8 characters, or 16 characters. If each of these 16 characters can be selected from the 256 available (28), then the number of possibilities is:
25616. Or (28)16. Or 2128 Or:
340,282,366,920,939,000,000,000,000,000,000,000,000 possibilities (approximately 3x1038)
On the other hand, if only the 96 typable characters are used, the number of possibilities is:
52,040,292,466,647,300,000,000,000,000,000 different possibilities.
The equivalent of this in bits is:
log(possibilities)/log(2) Or approximately:
(The decimal part makes a big difference here).
So, if only typable characters are used 128 bit encryption becomes a little more than 105 bit encryption.
Similarly, if only the letters and the numbers (62 possible characters) were used then the equivalent in bits would be:
95.2671 bits. (The number of possibilities is about 5x1028)
This has reduced the possibilities by a factor of 7,137,932,110 (about 7x109), making it thousands of millions less effective. It would take a Super Computer only (!) 15,116,390 years to crack.
How Many Passwords Can a Computer Process Every Second?
This is equal to the length of a piece of string (sic) ...
The answer depends, at least, on the computer and the program testing the passwords. It is less than the clock speed of the processor.
Ian Goldberg of Berkeley cracked the 40 bit RSA code using 250 computers checking at 100 billion key combinations an hour (in 1997).
I assume that 100 billion means 100x109.
At the moment, pcs may run at about 109 hertz or at megahertz, but this is based on clock rates of the processor, which do not really relate clearly to the speed at which the computer can process information. This figure means that the clock speeds of a modern computer is 3,600 x 109 cycles per hour, which seems faster than the 250 computers in 1997.
At the moment, 2010, the fastest computer for general scientific use is BlueGene/L which computes at 478.2 trillion floating operations per second (FLOPS), or 4.782 x 1014 FLOPS. So in about 13 years, a single computer dwarfs a network of 250 computers in 1997!
Regular computers probably work at about 1012 floating operations per second (FLOPS). It is possible that with a suitable video card, this rate can be increased 20 times.
What this means isn't THAT clear, but because we are interested in worst case scenarios (for the security), we may assume that a modern computer (2010) can check 1012 passwords per second.
I assume that each processor in the Super Computer can check passwords at a million million per second. The Super Computer can check 100 million million (1014) passwords per second. These figures are likely to be exceeded quite quickly as technology develops!
A realistic figure is probably about 500,000 passwords per second for a single computer (written a decade ago), but a safe figure is to use 1014.
The time figures to illustrate the effectiveness of a problem are probably extremely misleading. Bit Ratings are much more meaningful. .
How Long Would It Take To Crack 128 bit Encryption?
Assuming that the imaginary Super Computer is used, then the time taken in seconds is:
(Number of Possible Passwords)/(1014 passwords per second)
Because this will be a large figure (even though the super computer may be more powerful than anything in existence), we will divide the figure by the number of seconds in a year, to get a result in years:
(Number of Possible Passwords)/(1014 passwords per second)/(Number of seconds in a year)
(2128)/(1014)/(Number of Seconds in a year)
The number of seconds in a year is:
31,557,600 seconds in a year.
The number of years to cover every possibility in a 128 bit password using the Super Computer is:
This is roughly 107,829 (about 1015 ) billion years.
The sun will go nova before an attacker could test every password in a 128 bit algorithm
Assume the sun will die in 7.5 billion years (7.5x109).
Compare the above figure with the time a Super Computer would take to cover all possibilities. The time to cover all possible password would be about ten million times the time taken for the sun to die!
What is the Minimum Bit Size to resist a Super Computer for One Year?
The Super Computer can test 100 billion passwords every second. So in one year, it would test:
1014 passwords/second* Number of Seconds in a Year
The number of seconds in one year is:
The bit rating is:
So you would need about 79 bit encryption (or a 10 character [each character randomly using one of the 256 possible characters] password) to resist a super computer for one year. If only alpha-numeric characters were used, you would need the following bit rating:
This means that a 12 character password, each character randomly using one of the alpha-numeric characters is required, as a minimum.
If only the letters were used, you would need:
100.217372937876 bits, or
104 bits (because computers require the password size to be a multiple of 8)
Requiring a minimum password length of 13 letters.
How long could a Complete Password resist a Super Computer?
Number of seconds in a year:
A super computer can test 100 billion passwords every second.
It can therefore test, in one year:
3,155,760,000,000,000,000,000 possibilities in one year.
There are the following possibilities in an 160 bit algorithm:
The number of years to examine every possibility is:
463,121,922,240,887,000,000,000,000 years. (Which is about 463 quadrillion years- 463x1024).
How many randomly chosen words are needed to resist a Super Computer?
You could make a password from randomly generated words. Remembering whole words is easier than remembering Complete Passwords. .
The user can select the number of words to generate. The number of possibilities is 25,000n where n is the number of words.
The number of possibilities that can be checked by a Super Computer is:
So we want n so that:
4 words would resist a Super Compute for about an hour. 5 words would resist a super computer for about 3 years. So the answer is 5 or more words chosen from a 25,000 world list.
The above assumes the attacker knows the words in the list. If the attacker did not know them, then it would take considerably longer.
The default number of words is 4. This compromises the ease of remembering the words (thus keeping the password in your head) with possible attacks. A single computer processing passwords at 10 million per second would cover all possibilities in 4 words in about 26 years, and 1000 of them would take about 9 days. While the Super Computer would cover 4 possible words in about an hour.
Four Random Words - Possibilities
Suppose a user chooses to generate four random words from the list of 25,000 words. The program has chosen the four words from a possible:
This means that the "resistance" of 4 words chosen as above is equivalent to a password containing every possible bit (0 or 1) in 59 bits.
The Equivalent Bit Rating
Because the password does not use all of the possibilities, the length of the password to hold only letters must be longer. In such a password, each character occupies one byte in a real computer. If only 52 of the possible 256 possible characters are used (upper and lower case letters) then a password of length n, would have the following possibilities:
This is the same as the number of possibilites in choosing the password. That is:
Four Words Selected at Random are Much More Effective than 56 Bit Encryption
While choosing 4 words appears to be slightly than a 56 bit password, it is, in fact, much more effective than using 56 bit encryption using only letters. A 7-character password (56 bit) has the following possibilities, when the user enters only text:
The above number is much less than the number of possibilities using 4 random words (390,625,000,000,000,000)
The maximum bit rating that 56 encryption can attain with this method is:
The following table summarises this information. The number of characters required in rounded up, because you cannot enter a fraction of a character!