Lecture 19: Introduction to Encryption

Network Monitoring

In most multiaccess networks, it is trivially easy for a host to set its network interface into "promiscuous mode", and copy all data frames which pass across the network.

This is called eavesdropping or (in some circles) packet snarfing. Once the host has copies of all the frames it desires, it can then analyse them to discover the data they contain.

Most data transfers across the Internet are not encoded (or encrypted) in any way Ð the data is simply sent as plain text. Thus it is simple to observe messages transmitted by others. This is the origin of the (oft repeated, and generally true) assertion that "The Internet is insecure".

An area where this insecurity can present a serious problem is password authentication. Many protocols (eg Telnet) send the username and password across the network as plain text. This information can be observed, under certain conditions, by another user. You need to always be aware of this!

The solution is encryption - encoding the message so that it is unintelligible to the intruder.

Encryption is a vast technical, scientific and political topic. We will look briefly at a few aspects.

Cryptography Basics

A message to be encrypted (known as plaintext) is transformed by the use of a function parameterised by a key, thus:

The security of the ciphertext depends on:

The nature of the encryption method, or algorithm. It is nowadays generally agreed that open publication of details of the algorithm is a Good Thing.
The secrecy of the key. Current opinion is that, given a suitably powerful encryption algorithm, the security of the system should depend entirely on:
1. keeping the key secret and
2. the length (usually measured in bits) of the key itself, which is usually a very good indicator of the work factor required to crack the ciphertext.

Substitution Ciphers

This is the simplest technique, whereby each character in the message is replaced by another using some rule. The order of the encrypted characters is the same as in the plaintext.

There are many examples of this technique. Most fall into the general category of monoalphabetic substitution, where the output alphabet is the same as the input. For example, in the classic Caesar Cipher, letters of the alphabet were shifted by 3 positions, hence a becomes D, b becomes E, etc. A more complex example:

plaintext:  a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

hence bad is encrypted as WQR.

This type of cipher turns out to be relatively easy to break, despite the huge (26!) keyspace, by using known statistical characteristics of English (or other languages), eg:

letter frequencies - e is most common, then t, etc.
trigrams (eg the, and) are common.
Some words may be more likely in the particular context.

Transposition Ciphers

In this system, the order of the plaintext characters is changed, but the characters themselves are not - that is, the encrypted message contains all the same characters as the plaintext. For example, a simple columnar cipher looks like:

Hence, the ciphertext is:

eatitnihmexnetmgmedt

Neither substitution nor transposition ciphers are regarded as secure for any serious use. The modern approach is to use basically the same ideas, but with much more complex algorithms (see DES, later).

One-Time Pads

Another approach (although rarely used) is the one-time pad, (or Vernam Cipher) where a simple algorithm is used in conjunction with a key of the same length as the message, and employing a brand new key for every message transmitted.

For example, convert both the plaintext and the key to bit strings (which will be, necessarily, of the same length). Apply the XOR (Exclusive OR) function bitwise between the strings, giving the ciphertext. The recipient can then apply the same key to the ciphertext using XOR and thus recover the original plaintext.

This is, in every respect, unbreakable, but rather impractical for real-world use in most cases. Some reasons:

The key is the same length as the message, which means that it will probably be too long to memorise, hence a written copy is needed, which is potentially dangerous.
The length of the message is limited by the amount of key available.
If synchronisation is lost, subsequent messages will be garbled.

Neverthless, see s/key for a practical, working example of a one-time pad system.

DES - The Data Encryption Standard

DES is a block cipher, which operates on 64-bit data fragments, using a 56-bit key. The basic DES algorithm is described as follows:

Note that DES is designed so that decryption is performed by the exact same algorithm as encryption (using the same key - hence single key), except performed in reverse.

The effectiveness of DES is based on the complexity of the 19 stages. In the above diagram, two identical 64-bit plaintexts will result in identical ciphertexts. This is called the Electronic Code Book (ECB) mode of operation.

DES In Practice

The ECB mode of operation is now rarely used, since it is now generally agreed that it is breakable given sufficient resources.

In the Chain Block Cipher (CBC) mode, each block of plaintext is exclusive-ORed (XOR) with the ciphertext output from the previous encryption operation. Thus, the next block of ciphertext is a function of its corresponding plaintext, the 56-bit key and the previous block of ciphertext. Identical blocks of plaintext no longer generate identical ciphertext, which makes this system much more difficult to break.

The CBC mode of DES is the normal technique used for encryption in modern business data communications.

Cipher Feedback Mode DES, etc

A variation on CBC is used where the message may not be a multiple of 64 bits, or where interactive (character at a time) encryption and decryption is desired. This is called Cypher Feedback Mode (CBM), and uses shift registers to permit one byte at a time to be encrypted or decrypted.

DES has always been controversial:

The original (IBM) algorithm which was the basis of DES used a 128 bit key. The US government changed this to a 56 bit key. This made DES considerably less secure.
Many people believe that the US government has a "backdoor" (or trapdoor) decryption technique which is infeasible at 128 bits, but possible with 56. This has never been confirmed.
56 bit key DES is nowadays regarded as "probably crackable". A variation called triple encryption DES uses two keys (112 bits) and is still considered secure.
The IDEA encryption algorithm, which uses a 128 bit key and did not come out of the US government, is suggested as a more suitable basis for future secure communications.

Some good Internet resources on cryptography are available here

This lecture is also available in PostScript format. The tutorial for this lecture is Tutorial #19.
La Trobe Uni Logo

[Previous Lecture] [Lecture Index] [Next Lecture]