Secure Design: Encryption

CS 493/693 Lecture, Dr. Lawlor, 2006/02/22

Encryption is just the use of two functions E (for encryption) and D (for decryption) where
    ciphertext = E(plaintext,keyE)
    plaintext = D(ciphertext,keyD)
The idea is once you've get the keys settled, you can send the ciphertext across an untrusted network without revealing anything about the secret plaintext.

Symmetric or Secret-Key Encryption

In a symmetric cipher, the encryption and decryption keys are the same: keyE==keyD.  This means the key has to be kept secret like a password.  In other words, secret-key encryption is "secrecy amplification", and is hence subject to all the usual secrecy problems as passwords. 

The oldest cipher by far is the "substitution cipher", where one letter is replaced by another.  The oldest and simplest of these is the "caesar cipher", ROT13:
    ciphertext = (plaintext + 13 mod 26)
    plaintext = (ciphertext + 13 mod 26)

So 
    "foobar" becomes
    "sbbone", and
    "abcdefghijklmnopqrstuvwxyz" becomes
    "nopqrstuvwxyzabcdefghijklm".
In general, replacing one letter by another fixed letter is not a good idea.  Note how both 'o's translated into 'b's.  These duplications (and in general letter frequencies and interrelationships) are the reason substitution ciphers are printed in the newspaper (google: "cryptoquote") and regularly broken by ordinary folks, even when the substitution is an arbitrary table.

Suprisingly, all modern symmetric ciphers are just substitution ciphers with a twist--in addition to substitutions, mix subsequent letters together.  So instead of just
    for (i=0;i<message_length;i++)
       out[i] = table [ in[i] ^ key[i%keylen] ];
you do
    temp = 0;
    for (i=0;i<message_length;i++) {
      temp = in[i] ^ table [ temp ^ key[i%keylen] ]; /* should be way more thorough mixing */
      out[i] = temp;
    }
This "chaining" mixes together information from the past (in temp) with the present (in[i]), which completely screws up the letter frequencies and statistical relationships, making it much tougher to crack. 

The oldest useful symmetric cipher is the venerable 56-bit "DES" (the Data Encryption Standard) and the stopgap 112-bit "triple-DES" or "3DES".   The new standard symmetric cipher is "AES" (the Advanced Encryption Standard) which can use a key length of 128, 256, or 512 bits.

Asymmetric/Public-Key Encryption

With this form of encryption, the encryption and decryption keys are different.  This lets you give away one key, and keep the other (e.g., in a vault).  If you keep the encryption key and publish the decryption key, you can make unforgeable messages that anybody can decrypt, but nobody else can forge.  If you keep the decryption key and publish the encryption key, you can decrypt messages that people send you, but nobody else can read.

There's a beautiful Java implementation of RSA public-key encryption here.  Sun's "java.math.BigInteger" class is tailor-made for RSA: it's got arbitrary precision, prime finding, and modular exponentiation.

You can win cash prizes for factoring really long integers with the RSA prizes, since the security of RSA rests in part of the difficulty of factoring large composite numbers.

US Export Controls on Encryption

Prior to 1996, encryption with a key length of over 40 bits was considered "munitions-grade", and exporting any encryption software capable of using more than 40 bits required a very difficult to obtain license.

In 1996 President Clinton increased the free-export limit to 56 bits (standard DES).  You can apply for a license from the Department of Commerce to export stronger encryption.  However, certain countries are still embargoed: "Applicants may submit license applications for exports and reexports of certain encryption commodities and software in unlimited quantities for all destinations except Cuba, Iran, Iraq, Libya, North Korea, Syria, and Sudan."

Because of these legal restrictions, most encryption software is hosted outside the US.  OpenBSD and Libtomcrypt are hosted in Canada.  OpenSSL is hosted in Germany.  Apache-SSL is hosted in the UK.