Encryption

This a Useful Notes page.

In cryptography, encryption is the process of transforming information (the plaintext) using an algorithm (the cipher) and a secret (the key) into something unreadable to anyone except those possessing the key (the ciphertext).

What it comes down to is that information is scrambled and that some other person can only unscramble it if he/she knows the key uised to scramble it. Cracking the encryption is figuring out how the information was scrambled. Encryption can be done both by hand and with a computer. Note that doing encryption by hand has some limitations, it is impossible to encrypt large amounts of information due to the time it would take and one could not use every encryption, because some calculations might be too difficult to do by head.

Symmetric vs. asymmetric encryption

There are two main forms of encryption today: symmetric and assymetric.

Symmetric encryption is the classic form of encryption as is known today. The plaintext is encoded into ciphertext using a secret key; the recipient, to decode the message, must know the secret key that was used to encode it. The name refers to the fact that encryption and decryption are inverse functions and both use the same key to work (thus symmetrical). This was the first form devised (even before WW 2).

Asymmetric encryption is a newer form of encryption, devised in The Seventies; in this form, the key used to encrypt the message and the one used to decrypt it are not the same. In an asymmetric cipher, each party has a pair of keys: a public key and a private key. If Alice wants to send Bob a message, she uses Bob's public key to encrypt the plaintext, and Bob uses his private key to decrypt it. Public keys, as the name indicates, are not required to be secret; private keys are. In short, encryption and decryption are not inverse to each other in asymmetric encryption schemes, hence the name.

The advantage of asymmetric encryption is that there is no need for the sender and recipient to know a shared secret key. Suppose you wanted to send an encrypted message to somebody, and you tried to do so using a symmetric cipher. How would you send them the secret key if you're concerned that somebody might eavesdrop? To send them the key, you need to use a special, secure channel that is resistant to eavesdropping—for example, an in-person meeting.

The biggest practical disadvantage of asymmetric encryption is that you need to "trust" that what you think is the recipient's public key really is theirs, and that their private key has not been disclosed; I can pretend to be the President of the United States and send you a public key, and if you mistakenly believe me, you might unwittingly send your top secret messages to me instead of the President. This leads to complicated "web of trust" scenarios that are used in order to determine whether the person or entity behind a public key really is who they claim to be. They're also more computationally expensive than symmetric systems, which is why most secure encrypted channel schemes use the asymmetric encryption solely to create a secure channel to pass a one time symmetric key, then switch to symmetric encryption for the bulk of the transaction.

Security certificates - the bits of bits that tell us that individuals online are who they say they are - use asymmetric encryption in their manufacture, but in an inverse manner to the normal scheme (so the public key is what would normally be the private key and vice versa.) The result is a cyphertext that can be read by everyone, but only manufactured by the issuing authority.

One-time pad

The one-time pad is a special kind of cipher that is completely unbreakable if used correctly—but very weak if used incorrectly, and also very impractical. The trick is that the secret key must be as long as the plaintext, must be completely random, and must never ever be reused.

The reason one-time pads are unbreakable is that for any conceivable plaintext, there exists a possible key that would produce that plaintext from the encrypted message. This means that if you try to guess what the key is, there are exponentially many more false positives than the real message, and no way to tell a false positive from a true positive.

But if the users of a one-time pad get sloppy and reuse a key for more than one message, it becomes trivial to break. If the keys are not truly randomly generated, it can be broken too. A number of historical codebreaking successes resulted because somebody tried to use one-time pads but either reused the keys or generated them in a non-random fashion.

Then there is also the problem of communicating the keys, which is even harder than in the normal case because (a) you need as many keys as messages, (b) the keys are as long as the messages.

Cryptanalisis

The act of analyzing the cipher and the ciphertext in order to retrieve the original plaintext. It is not true that any ciphertext can be cracked. Using a wrong key can sometimes result in a valid-looking plaintext that is in fact not the correct plain text (one-time pads work this way).

To recover a plaintext from a ciphertext, the key and the algorithm used are required. Having only the ciphertext is the hardest problem: the cryptanalist must guess both the algorithm and the key. This is called a ciphertext-only attack and it requires the experience and the intuition of the analyst, knowledge of the circumstances, the sender, the receiver, current events, etc... While statistical analysis of the ciphertexts could provide information about the algorithm, it requires plenty of ciphertexts or it doesn't give any meaningful information.

If the algorithm is known, the recovery can be easier: only the key (usually a password, though other things can be considered as keys) is required.

The simplest method of cracking a password is known as brute force: trying every possible password. The problem with this is that it can take a very long time to find the right password. The number of possibilities for a password increases with every length added to the password and every character that could possibly be used. For example, if you wanted to to find a password that was 6 characters long, and could be composed of any letter between A and Z, you might have to try 26^6 = 308.915.776 possible passwords. If you could try one password every second it would take almost 10 years to try every password. Trying every password of 7 letters would takes over 254 years.

A quicker method would be to try every word in the dictionary as a password, instead of using methods that try random letter combinations as passwords alongside words, but this is still not guarantied to work; especially if the password consists of "leetspeak", which is becoming increasingly common these days. Also, informal words may not be included in any dictionary you choose to use.

As mentioned above, the key doesn't have to be a password. For example, in Cryptonomicon two people communicate using the "Solitaire cypher". The cypher uses a deck of cards; their initial arrangement is the key leaving 54! (54 factorial, 54×53×52×...×2×1) possible keys and no dictionary to use.

The knowledge of the plaintext or parts of the plaintext (so-called cribs) can make a cryptanalisis problem exponentially easier. The plaintext - or parts of - could be acquired by old-fashioned spying or, more inventively, by feeding the mole. This is called a known plaintext attack and was used extensively during WW 2, but is mostly of only historical interest in modern times.

And then (as the xkcd comic at the top of the page illustrates) there's the age-old standby of rubber hose cryptoanalysis - beating/torturing the key out of a holder. (The name comes from the rather vivid image of the keyholder being beaten across their bare feet with a rubber hose). This does not have a direct counter, but many applications (such as Truecrypt) allow a defence based on plausible deniability for an encrypted volume to decrypt to a 'decoy', which hides a second encrypted volume with a different key. The interrogator may suspect the presence of a hidden inner volume, but its existence can not be proved or disproved.

Of course, no encryption could protect you from stupidity. If you ever find yourself in a situation where the secret service is digging through your trash and anything you say might spell your doom if it ever gets in the wrong hands (because, be honest, who doesn't get into situations like this?), remember the following:

• Keep the keys secret! This is pretty obvious, if someone knows the key, your encryption is fucked.
• Cycle the keys and the algorithms! It can be quite an annoyance for the Secret Service if they have to spend days on recovering your key every week or so.
• Choose the algorithm carefully! Don't use any algorithm that has been cracked (such as the Enigma)! However, don't go overboard and use the same, brutal algorithm for all of your messages! If the message won't be interesting after a week or so, don't use an algorithm that takes three million years to break with brute force - the more encrypted messages they have, the easier they can break even the best cypher.
• Trust no one! Use a different key (and algorithm, if possible) with everyone. This way, if anyone is a traitor, you can minimize the damage.

Wait, they are after me... IBUDHRYKPSSRCGCSXDHGRECTRHNZMFZUMLPOAPUNPBXHJFIIMKQMQDLPRVEXYUXKOKJJATCNHTTJOLPBXCEYNYITDZWFHXHJ