CHRIS KULBACKI

chris, 12/05/2010 15:33,

Did you ever wonder how encrypting programs scramble your files and render them unreadable? Let's have a little peek into the fascinating world of cryptography!

Cryptography is almost as old as the history of written communication. One of the earliest known methods of encrypting text was invented by Julius Caesar. It's called the substitution algorithm, and it worked this way: every letter of the text was replaced with a letter situated 3 positions further down the alphabet. In the English alphabet this would mean that A would become D, K would become N etc. Since then, a lot of progress has been made in creating encryption methods.

An encryption algorithm is, simply put, a series of complex mathematical equations working together to confuse the characters in the text and render them unreadable. Picture it as an equation with an unknown variable X intertwined in many places. Without knowing the value of X (which represents your password), it is very difficult, if not impossible, to solve the equation.

A number of encryption algorithms in use today have no known mathematical method of solving them without knowing the password. The only way to "crack" them is to try every possible variation of the password until the correct one is found. That's why the password that you choose for encrypting your files is one of the most important things that ensures your security.

The password that you enter in the form of letters, digits and other characters is later converted to a large number using a complicated mathematical procedure. This is our "X" without which the equation cannot be solved. The larger the number, the more difficult to solve the equation and decipher the encrypted message.

Let's take this equation for an example:

Y = 2 * (X + 2)

Let's say the value of X (our password) is 6. It would be pretty easy to "crack" this equation and find the correct value of Y by trying every possible password.

But say the value of X is

574832879287093870298370451874389237438720874

Now finding the value of Y would be much more difficult.

In cryptographic jargon, finding the password by trying its every possible variation is called a brute-force attack. It's the "last resort" method, used when every other alternative fails. It's very costly and can take an awfully long time.

Let's suppose we have a network of one thousand supercomputers and each one of them can test one million passwords per second.

If our password is:

• 12 characters long (40 bit key), there will be 2^40=1099511627776 possibilities. The theoretical probability of finding the key will be at the (2^40/2)th possibility. The time our computers need to figure it out = 9 minutes.
• 17 characters long (56 bit key) -- 2^56 possibilities, time needed = 416 days = 1.1 year.
• 20 characters long (64 bit key) -- 2^64 possibilities, time needed = 292 years
• 25 characters long (80 bit key) -- 2^80 possibilities, time needed = 38 million years

Technical note: Some algorithms support limited key lengths, so even if your password is very long, it will be automatically shortened to the longest numeric value supported by the algorithm. Also, different algorithms and encrypting programs use different techniques for processing passwords, so the number of characters in the password does not necessarily mean that the same length of key is being used for the actual encryption. The above explanation is only a simplified example for the sake of demonstrating the principle.

Here are some approximate costs for a network of computers that could find a password composed of 17 characters using the brute-force attack (figures taken from the book "Applied Cryptography 1", by Bruce Schneier):

• in one year = $16 million
• in one month = $200 million
• in one week = $850 million
• in one day = $6 billion

The price for the same type of computer network that would be able to find a password composed of 20 characters in one year is $3*10^26, a number way too long include in this article. Since with every additional character in the password the prices grow exponentially, brute-force cracking passwords longer than 18 characters is out of reach of any military budget.

Interesting fact: In theoretical cryptography time is not measured in hours, days or even years. The time needed for some operations is so long that it's often measured in the ages of the universe. So oftentimes you'll come across a cryptographic thesis saying that something would take, say, 16 million ages of the universe to complete.

But there are other, much more effective ways of finding passwords. Let's take a look at a dictionary attack. Dictionary attacks are very cost effective and fast. Their success is not guaranteed, but over 25% are successful. The success of this type of attack is based on the wrong choices of passwords. Here's how it's done (points from the book "A Survey of and Implications to Password Security" by D.V. Klein):

• first of all, variations of names, surnames, initials or other personal information will be checked, with the addition of "! * @ 1 2 3" etc at the beginning, end and middle.
• data bases will be used, containing all existing names, geographical names and their variations, famous people's surnames, movie and cartoon titles and their main characters, sci-fi terminology, mythology characters, sport terminology, teams, nick names of players, strings of letters and digits, Chinese syllables, characters, places or parts of the King James Bible, scientific terms (biology, chemistry etc), historical terms, curse words, keyboard strings ("asdf", "qwerty", "zxcv" etc), computer terminology, names and places of Shakespeare plays, astronomical objects
• permutation of the above words will be checked, for example changing "o" to "0", changing "l" or "I" to "1", swapping lower and upper case, fictional plural cases (like "sphynxs" for "sphynx" instead of "sphynges"), and of course all endings will be checked, "play", "playing", "plays", "played" etc.)
• foreign words will be checked for those speaking foreign languages

So, how do we protect ourselves from dictionary attacks? What's a good and safe password? The best password is, of course, one that is truly random. But it's difficult to remember something like "5)uQ~./a}\1mz^oW#\`r" isn't it?

Here's my suggestion on how to create a safe and usable password using the first letters of the words in a sentence:

Here's the sentence that we'll use: "A person who never made a mistake never tried anything new" (Albert Einstein). That would make the basic "apwnmamntan". Now let's make it sound more like a word by adding or changing some characters to make it easier to type and remember: "apenemamfnan". Now some case changes: "ApenemAmFnan", and finally a few non-alphabetic characters: "-ApenemAmFnan&&".

This would be a fairly good and safe password for everyday use. If you want to make it more secure, add some numbers or other random characters here and there to make it longer.

Remember to take time to create you passwords. It takes time to cook a good meal, clean the house or create a web site. It also takes time to come up with a good password.

Don't miss the second part of "Captivating Cryptography!"

Comments