Passphrase FAQ: About this FAQ
This FAQ was written by Randall T. Williams. His last revision occurred on 01-13-1997. The FAQ has been updated and re-arranged by Arnoud Engelfriet in 2005.
Table of contents
This FAQ is under construction (aren't they all?). Changes will be made as I learn about them, generate them or have time. Applied Cryptography (by Bruce Schneier) leads me to believe that there hasn't been much published research in this area. Password cracking is covered, but little is said about passphrases. Some of the math involved is not normally a part of what I do. I'm an electronics engineer by training. Cryptography is just a hobby. Forgive anything that may seem trivial that was overlooked. I created most of this from my head.
Copyright © 1995-97 by Randall T. Williams. This is free to distribute where it might be useful and not for profit as long as this notice remains attached.
The first thing is about the numbers used in this document. Most math here was performed on a Texas Instruments TI-60 pocket calculator and a couple programs on my PC for verification. The number of significant digits is limited to just a few places because a string of almost 40 digits isn't needed and they are really beyond the comprehension of many. Look at section 6.0 for the exact value of some of the big numbers used here. I use the notation where 3.4E38 = 3.4 * 1038 = 2128. This was easier to type and it saves a little space. Also note that log(x) (base 10) is being used here. Since we are just using the exponents, don't worry about using ln(x) (base 2.718 or e) if you don't have log(x).
Rounding where it effects security are rounded up to the next highest whole number to be safe. Other numbers are just rounded to the nearest decimal place. The text should be clear on this in most cases.
These are here to show how big numbers can get in cryptography. They are hard to work with and there is no good reason to use them other than to try and put things into scale. You need more than a pocket calculator to work with them in this form. Take note of the length of 2128. This is the size of a 128 bit number. A 512 bit modulus is about 4 times as long.
1 million = 1,000,000 1 billion = 1,000,000,000 1 trillion = 1,000,000,000,000 3.15576E13 = 31,557,600,000,000 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 74,0008 = 899,194,740,203,776,000,000,000,000,000,000,000,000 9520 = 3,584,859,224,085,422,343,574,104,404,449,462,890,625 2628 = 4,161,536,836,220,038,342,098,551,818,958,537,752,576These are the log(x) numbers used throughout the FAQ. Mostly it is an attempt to make the math easier even if you don't understand what log(x) is.
log(2128) = 38.53183945 log(3.16E13) = 13.49910397 log(74,000) = 4.86923172 log(50,000) = 4.69897004 log(25,000) = 4.397940009 log(10,000) = 4.0 log(95) = 1.977723605 log(26) = 1.414973348
This is to clear up a few things in case the context isn't clear. More definitions will be added as needed.
- attacker = This is anyone who might want your passphrase. It could be your little brother or sister, wife, friends, hacker down the street, law enforcement and many others.
- brute force search = This is a search of the entire key space. Every possible combination will be tried in sequence. Eg. Briefcase combination locks have a key space of 1000 and will be searched (000, 001, 002... 999).
- key size = The actual size of the key. Eg. IDEA has a key size of 128 bits.
- key space = The number of possible combinations a key can have. Key space is sometimes tricky to compute if there are methods of attack other than trying every possible combination. Eg. IDEA has a key space of 2128.
- pseudo-random = a mathematical sequence or other repeatable sequence that appears to be random.
- random = A sequence that can not be reproduced by any means other than replaying a recording of the sequence.
- search space = The size of the search needed to break a key. Sometimes keys have a much smaller search space than the key size might dictate. Eg. A 40 digit/130 bit hard number, (toy RSA), is bigger than the 39 digit key space of IDEA but can be factored in a few minutes or less using one of the faster factoring methods.