Just Enough Cryptography — Ciphers

Encryption, Decryption, Initialization Vectors, Symmetric versus Asymmetric Ciphers, Identity-Based Encryption, How RSA Works

Encryption and Decryption

               +---+                      +---+
 plaintext --->| E |--->  ciphertext  --->| D |---> plaintext
               +---+                      +---+
                 ^                          ^
                 |                          |
                 Ke                         Kd

                     ciphertext = E(p, Ke)        plaintext = D(ciphertext, Kd)
                                                            = D( E(plaintext, Ke), Kd)

The process starts with the plaintext that is to be protected. The plaintext was limited to very simple text for most of the history of cryptography. With the creation of electrical machine cryptography, the plaintext was often limited to being expressed in a very constrained alphabet — no digits, just letters, sometimes with relatively unneeded characters left out (Q, or J in some languages), and with no distinction of upper versus lower case. The plaintext alphabet was usually more constrained than the Morse code or other telegraphy used to transmit the ciphertext.

With the cultural shift in the use of computer network communication, the plaintext these days is often non-text data — multimedia such as image, sound, and video files; complex and bulky non-ASCII file formats such as those used by Open Office and Microsoft Office; or even an archive containing an entire directory structure of multiple files of various data types.

However, we do not care about the internal format, if any, and the intended use. It's all simply plaintext to be protected.

The encryption operation uses some cipher algorithm E that always functions with the same general principles. However, its operation in this case is modified by the encryption key, Ke.

The resulting ciphertext is then transmitted across a network or stored on some media, in both cases with the possibility that an attacker will be able to get a copy of the ciphertext.

At the far end of the communication channel, or in the future when we want to recover the plaintext from the stored ciphertext, a corresponding decryption operation D applies the appropriate reverse algorithm, as directed by the decryption key, Kd.

Auguste Kerckhoffs, Dutch linguist and cryptographer

Auguste Kerckhoffs mathematically proved that the security of a cryptosystem must not depend on keeping its algorithm secret [See his article "La cryptographie militaire", in Journal des sciences militaries, vol IX, pp 5-38, Jan 1883]. That means that an attacker will know the details of all the useful ciphers, and will be able to guess which one we are using. If we chose a good cipher algorithm E, we can feel comfortable about the security as long as:

• We choose our keys wisely — an attacker has no advantage beyond simply guessing as to what the needed decryption key Kd might be. The keys would appear to be random strings of bits.
• We maintain the secrecy of keys — the difficulty is getting the decryption key to the remote receiver, or safely storing it until needed to decrypt stored data.
• We realize that we only have security for a limited amount of time — there is a finite number of possible keys, and an attacker could try all possible keys while monitoring the output for data that appears to be plaintext. So:
  • Choose a cipher with a large enough key space (that is, total number of possible keys) to keep an attacker fruitlessly searching until the plaintext is no longer sensitive.
  • Choose a cipher that, as far as we know now, has no flaws leaking partial information about the key or allowing an attacker to eliminate part of the brute-force search through the key space.
  • Realize that captured ciphertext never gets stronger over time, but cryptanalytic knowledge gets better and computers get much faster.

Initialization Vectors

Joseph Rochefort, USN cryptanalyst during WWII.

Let's say that you encrypt some plaintext using today's key. Maybe this is routine report sent on a fixed schedule: ALL QUIET ON THE WESTERN FRONT. Later in the day, therefore using the same key, you need to encrypt the same plaintext message. The problem is that the two ciphertexts will be identical.

An attacker could use traffic analysis to spot the identical ciphertexts and correlate that with observations. This was used by the U.S. Navy cryptanalysis effort during World War II in the Pacific Theater to derive information about planned Japanese ship movements when the cipher or code itself could not yet be broken.

The fix to this is to add an initialization vector or IV to the plaintext to randomize the input to the encryption operation. Ciphers can be used in various chaining modes, where the operation applied to some block of input depends not only on the key but also on the preceding block of input (plaintext) or output (ciphertext). The IV therefore primes the cipher, getting it into some random state before encrypting that identical plaintext with today's fixed key.

The IV needs to be different for every message sent, but it does not need to be kept secret in a well-designed cryptosystem. So, if messages need to be sent no more often than once per second, a useful IV might be the number of seconds elapsed since some epoch, perhaps 00:00:00 UTC 1 January 1970 (as time is reckoned in Unix), or 00:00:00 UTC 1 January 2000. Or, if the messages to be protected are rapidly streamed network packets, the number of microseconds elapsed since midnight today.

Symmetric vs Asymmetric Cryptography

Symmetric means "the same on both sides", while asymmetric means, well, the opposite.

For symmetric cryptographic algorithms, Ke = Kd. You are free to pick any appropriately long string of bits to function as the single key for an encryption and the following decryption.

However, beware: some keys might be obvious guesses, and some algorithms have "weak keys", certain types of key patterns that allow enough information to leak into the ciphertext to make it easier to guess the key. Weak keys are often those with regular patterns — lots of consecutives 1s or 0s, or a repeated pattern like 0101010101. The keys need to be hard to guess, and so they should look very random.

For asymmetric cryptographic algorithms, when you encrypt with some Ke you must decrypt with a completely different Kd You must use the correct math trick to generate a key pair: Ke,Kd.

For useful asymmetric cipher algorithms, it is extremely difficult to derive one key from the other.

Asymmetric-Key Cryptography

We can quit worrying about the encryption key versus the decryption key, and just think of a pair of keys, K1 and K2. Arbitrarily pick one and encrypt with it. Then the only thing that can be used for decryption is the other key in the pair.

                 +---+                       +---+
plaintext  -+--->| E |---> ciphertext1 --+-->| D |--->  plaintext      = D(ciphertext1, K2)
            |    +---+                   |   +---+                     = D(E(plaintext, K1), K2)
            |      ^                     |     ^
            |      |                     |     |
            |      K1                    |     K2
            |                            |
            |                            |   +---+    Meaningless Output
            |                            +-->| D |--->  ????
            |                                +---+
            |                                  ^
            |                                  |
            |                               any key other than K2
            |
            |
            |    +---+                       +---+
            +--->| E |---> ciphertext2 --+-->| D |--->  plaintext      = D(ciphertext2, K1)
                 +---+                   |   +---+                     = D(E(plaintext, K2), K1)
                   ^                     |     ^
                   |                     |     |
                   K2                    |     K1
                                         |
                                         |   +---+    Meaningless Output
                                         +-->| D |--->  ????
                                             +---+
                                               ^
                                               |
                                            any key other than K1

Using Asymmetric-Key Cryptography

Let's say you have a sender and a receiver, and each has a pair of keys. For each person, they call one the "public key" and they tell the world, and they call the other the "private key" and they keep it a secret. So, each of them knows three keys — their pair, and the public key of the other.

Method 1 — Sender's private key only — Since the sender's public key is the only thing producing a coherent message, the receiver can trust that the sender sent it. Since slight changes in input make big changes in output, this also must have been the same message originally sent. But anyone can read it.

Method 2 — Receiver's public key only — Since the receivers's public key is the only thing producing a coherent message, the receiver can trust that no one else could have read it. But anyone could have sent it.

Method 3 — Sender's private key, and receiver's public key — The receiver can trust that no one else could read it, that the sender must have sent it, and that it wasn't altered in transit.

Using Asymmetric-Key Cryptography, Reworded

Identity-Based Encryption

Identity-Based Encryption (IBE) is asymmetric cryptography where the public key is based on some unique public information about the user. Perhaps an electronic mail address, or a telephone number including country code.

There is a completely trusted third party called the Private Key Generator (PKG). The PKG has published a master public key and retained the corresponding master private key, also called simply the master key.

Any party can generate any other party's public key using the master public key and the public information about the other party.

Only the PKG can generate the corresponding private keys using the master private key and the public information about parties.

Advantages:

• Parties may encrypt messages or verify signatures without distributing public keys.
• There is inherent key escrow, because any private key can be generated by the PKG.

Disadvantages:

• All security relies on the security of the PKG, because access to the master private key is effectively access to all parties' private keys.
• A secure channel is needed to communicate the private key to each party.
• The single central PKG may be overworked in very large systems.
• There is inherent key escrow, because any private key can be generated by the PKG.
  (Yes, this appears as both an advantage and disadvantage — key escrow can be both)

For more information:

• Adi Shamir's paper, "Identity-Based Cryptosystems and Signature Schemes", Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47-53, 1984.
• Clifford Cocks, "An Identity Based Encryption Scheme Based on Quadratic Residues", Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001.
• The Wikipedia page on IBE.

Getting the Ciphers

For an enormous list, see "Applied Cryptography" by Bruce Schneier, in the "Reference Books" section. The book contains source code for many serious cryptographic algorithms.

For something more mathematically rigorous, see the CRC Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone — a free PDF version can be downloaded for personal use: http://www.cacr.math.uwaterloo.ca/hac/

How AES Works

Jeff Moser has written a great explanation of the history and operation of the Advanced Encryption Standard, A Stick Figure Guide to the Advanced Encryption Standard (AES).

How RSA Works

Setting up the keys

1. Randomly select two distinct large prime numbers p and q.
2. Compute: n = pq
   n will be used as the modulus for both the private and public keys.
   Security comes from:
   • Difficulty of factoring product of two large prime numbers.
   • Ambiguity introduced by modulo function.
3. Compute the least common multiple: λ(n) = lcm(p - 1, q - 1)
4. Choose an integer e such that:
   • 1 < e < λ(n)
   • e and λ(n) share no factors other than 1. That is, so that e and φ(n) are coprime.
     A popular choice is e = 2¹⁶ + 1 = 65537
     Some applications choose smaller e such as 3, 5, 17 or 256 to make encryption and signature verification fast on small devices like smart cards, at the expense of greater security risk.
5. Compute d to satisfy the congruence relation:
   de = 1 + kφ(n)
   for some integer k.

e is the public key.

d is the private key.

As a simple example:

1. p = 5
   q = 11
   
2. n = pq = 55
3. φ(n) = (p - 1)(q - 1) = (4)(10) = 40
   Least common multiple of (p - 1) and (q - 1) is 20 = 2² * 5.
4. e ∈ {3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53}
5. d is defined by:
   (de) mod 20 = 1
   so the possible key pairs are:

   e	d
   3	7
   7	3
   9	9
   11	11
   13	17
   17	13
   19	19

Using the keys for encryption and decryption

1. Sender obtains receiver's public key (n,e).
2. Sender converts message M into a number m < n with an agreed-upon reversible padding scheme.
3. Sender computes ciphertext c using recipient's public key e by:
   c = m^e mod n
4. Sender transmits ciphertext.
5. Receiver calculates cleartext:
   m = c^d mod n
6. Receiver reverses padding function to recover message M from cleartext m.

As a simple example:

• p = 61
  q = 53
• n = 3233
• e = 17 d = 2753
• For message m = 123, sender calculates and sends:
  c = 123¹⁷ mod 3233 = 855
• Receiver then calculates:
  m = 855²⁷⁵³ mod 3233 = 123

All the way back to the start Terminology Symmetric and Asymmetric Ciphers Next — One-Time Pads Cipher Strength and Key Length Diffie-Hellman Key Negotiation and Secret Sharing Cryptographic Hash Functions Digital Signatures and Certificates Cultural Cryptography Further Reading

Back to the Security Index

Home Unix/Linux Networking Cybersecurity Travel Technical Radio Site Map Contact

Tweet