Applied Cryptography

Cryptographic Protocols

Chapter 2
Classical Encryption Techniques
Chapter 2 – Classical Encryption Techniques

Many savages at the present day regard their names as vital parts of
themselves, and therefore take great pains to conceal their real names,
lest these should give to evil-disposed persons a handle by which to injure
their owners. —The Golden Bough, Sir James George Frazer
Outline
• Overview of Cryptography
• Classical Symmetric Cipher
• Modern Symmetric Ciphers (DES)
Classification of Cryptography
• Based on the number of keys used
• Hash functions: no key
• Secret key cryptography: one key
• Public key cryptography: two keys – (public, private)
• Based on the type of encryption operations used
• substitution/transposition/product
• Based on the way in which plaintext is processed
• block/stream
 Secret Key vs. Secret Algorithm
• Secret algorithm: has an additional hurdle
• Hard to keep secret if used widely:
• Reverse engineering, social engineering
• Commercial: published
• Wide review, trust
• Military: avoid giving the enemy good ideas
• practice of protecting sensitive information that could
be used by adversaries if revealed.
 Unconditional vs. Computational Security
• Unconditional security
• No matter how much computer power is available, the cipher
cannot be broken
• The ciphertext provides insufficient information to uniquely
determine the corresponding plaintext
• Only a one-time pad scheme qualifies
• Computational security
• The cost of breaking the cipher exceeds the value of the encrypted
information
• The time required to break the cipher exceeds the useful lifetime of
the information
 Brute Force Search
• Always possible to simply try every key
• It is the most basic attack, proportional to key size
• Assume either knows/recognises plaintext
Key Size (bits) Number of Time required at 1 Time required at 106
Alternative Keys decryption/µs decryptions/µs
32 232 = 4.3 ´ 109 231 µs = 35.8 minutes 2.15 milliseconds
56 256 = 7.2 ´ 1016 255 µs = 1142 years 10.01 hours
128 2128 = 3.4 ´ 1038 2127 µs = 5.4 ´ 1024 5.4 ´ 1018 years
years
168 2168 = 3.7 ´ 1050 2167 µs = 5.9 ´ 1036 5.9 ´ 1030 years
years
26 characters 26! = 4 ´ 1026 2 ´ 1026 µs = 6.4 ´ 1012 6.4 ´ 106 years
(permutation) years
More Definitions
• Overview of Cryptography
• Classical Symmetric Cipher
• Substitution Cipher
• Transposition Cipher
• Modern Symmetric Ciphers (DES)
Classical Substitution Ciphers
• It is a method where letters of plaintext are replaced by
other letters, or by numbers, or symbols
• Or if plaintext is viewed as a sequence of bits, then
substitution involves replacing plaintext bit patterns with
ciphertext bit patterns
Symmetric Cipher Model
 Requirements
• Two requirements for secure use of symmetric encryption:
• a strong encryption algorithm
• a secret key known only to sender/receiver
Y = EK(X)
X = DK(Y)
• Assume the encryption algorithm is known
• Implies a secure channel to distribute the key
Classical Substitution Ciphers
• Letters of plaintext are replaced by other letters or by numbers or
symbols
• Plaintext is viewed as a sequence of bits, then substitution replaces
plaintext bit patterns with ciphertext bit patterns
Caesar Cipher
• It is the earliest known substitution cipher
• Invented by Julius Caesar
• First attested use in military affairs
• It replaces each letter with 3rd letter on
• example:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
Caesar Cipher
• can define transformation as:
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
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
• mathematically give each letter a number
a b c d e f g h i j k l m
0 1 2 3 4 5 6 7 8 9 10 11 12
n o p q r s t u v w x y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
• then have Caesar cipher as:
C = E(p) = (p + k) mod (26)
p = D(C) = (C – k) mod (26)
Cryptanalysis of Caesar Cipher
• Only have 26 possible ciphers
• A maps to A, B,…, Z
• One can simply try each in turn
• a brute force search can break it
• Given the ciphertext, just try all shifts of letters
• Do need to recognize when we have plaintext
• E.g.: break ciphertext "GCUA VQ DTGCM"
Monoalphabetic Cipher
• Rather than just shifting the alphabet
• Could shuffle (jumble) the letters arbitrarily
• Each plaintext letter maps to a different random ciphertext
letter
• Hence key is 26 letters long
Plain: abcdefghijklmnopqrstuvwxyz
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN
Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
Monoalphabetic Cipher Security
• Now have a total of 26! = 4 x 1026 keys
• With so many keys, you might think it's secure, but would
be !!!WRONG!!!
• The problem is the language characteristics
• Human languages are redundant
• Letters are not equally commonly used
Language Redundancy and Cryptanalysis
• Human languages are redundant
• eg "th lrd s m shphrd shll nt wnt"
• Letters are not equally commonly used
• In English, e is by far the most common letter
• Then T,R,N,I,O,A,S
• Other letters are fairly rare, eg, Z,J,K,Q,X
• Have tables of single, double & triple letter frequencies
English Letter Frequencies

Note that all human languages have varying letter frequencies, though the number
of letters and their frequencies varies.
Use in Cryptanalysis
• Key concept - monoalphabetic substitution ciphers do not
change relative letter frequencies
• Discovered by Arabian scientists in the 9th century
• Calculate letter frequencies for the ciphertext
• Compare counts/plots against known values
• If Caesar cipher, look for common peaks/troughs
• peaks at: A-E-I triple, NO pair, RST triple
• troughs at: JK, X-Z
• For a monoalphabetic must identify each letter
• Tables of common double/triple letters help
Example Cryptanalysis
• given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
• Count relative letter frequencies (see text)
• Guess P & Z are e and t
• Guess ZW is th and hence ZWP is the
• Proceeding with trial and error finally get:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow
Polyalphabetic Ciphers
• Another approach to improving security is to use multiple cipher
alphabets, called polyalphabetic substitution ciphers
• Makes cryptanalysis harder with more alphabet to guess and a
flatter frequency distribution
• Use a key to select which alphabet is used for each letter of the
message
• Use each alphabet in turn
• Repeat from the start after the end of the key is reached
Vigenère Cipher
• The simplest polyalphabetic substitution cipher is the
Vigenère Cipher
• It effectively uses multiple Caesar ciphers
• Key is multiple letters long K = k1 k2 ... kd
• The ith letter specifies ith alphabet to use
• Use each alphabet in turn
• Repeat from the start after d letters in the message
• Decryption simply works in reverse
• Encryption: Ci = (Pi + Ki mod m ) mod 26
• Decryption: Pi = (Ci – Ki mod m) mod 26
Example
• Write the plaintext out
• Write the keyword repeated above it
• Use each key letter as a Caesar cipher key
• Encrypt the corresponding plaintext letter
• Eg. using keyword deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ
 One-Time Pad
• If a truly random key is used as long as the message is used,
the cipher will be secure
• It is unbreakable since the ciphertext bears no statistical
relationship to the plaintext
• Since for any plaintext & any ciphertext there exists a key
mapping one to other can only use the key once, though we
have a problem of safe distribution of the key
Rail Fence Cipher
• Write message letters out diagonally over a number of rows
• Then read off the cipher row by row
• E.g., write the message out as:
m e m a t r h t g p r y
e t e f e t e o a a t
• Giving ciphertext
MEMATRHTGPRYETEFETEOAAT
Product Ciphers
• Ciphers using substitutions or transpositions are not
secure because of language characteristics
• Hence, consider using several ciphers in succession to
make it harder, but:
• Two substitutions make another substitution
• Two transpositions make a more complex transposition
• But a substitution followed by a transposition makes a new,
much harder cipher
• This is a bridge from classical to modern ciphers
Transposition Ciphers
• Now consider classical transposition or permutation ciphers
• These hide the message by rearranging the letter order
• Without altering the actual letters used
• Can recognise these since have the same frequency distribution as the
original text
Row Transposition Ciphers
• A more complex scheme
• Write letters of the message out in rows over a specified number of
columns
• Then reorder the columns according to some key before reading off the
rows
Key: 4 3 1 2 5 6 7
Plaintext: a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
Modern Symmetric Ciphers (DES)
•Data Encryption Systems (DES)
Modern Block Ciphers
• Will now look at modern block ciphers
• One of the most widely used types of cryptographic algorithms
• Provide secrecy and/or authentication services
• In particular will introduce DES (Data Encryption Standard)
 Block vs Stream Ciphers
• Block ciphers process messages into blocks, each of which is
then encrypted/decrypted
• Like a substitution of very big characters
• 64 bits or more
• Stream ciphers process messages a bit or byte at a time when
encrypting/decrypting
• Many current ciphers are block ciphers, one of the most
widely used types of cryptographic algorithms
 Block Cipher Principles
• Most symmetric block ciphers are based on a Feistel
Cipher Structure
• Needed since it must be able to decrypt ciphertext to
recover messages efficiently
• Block ciphers look like an extremely large substitution
• Would need a table of 264 entries for a 64-bit block
• Instead, create from smaller building blocks
• Using the idea of a product cipher
Confusion and Diffusion
• Cipher needs to completely obscure the statistical properties of
the original message
• A one-time pad does this
• More practically, Shannon suggested S-P networks to obtain:
• Diffusion – dissipates the statistical structure of plaintext over
the bulk of the ciphertext
• Confusion – makes the relationship between the ciphertext and
the key as complex as possible
Feistel Cipher Structure
• Horst Feistel devised the Feistel cipher
• based on the concept of an invertible product cipher
• partitions the input block into two halves
• process through multiple rounds, which
• perform a substitution on the left data half
• based on the round function of the right half & subkey
• Then, have a permutation swapping halves
• implements Shannon’s substitution-permutation network
concept
Ideal Block Cipher
Substitution-Permutation Ciphers
• Substitution-permutation (S-P) networks [Shannon, 1949]
• modern substitution-transposition product cipher
• These form the basis of modern block ciphers
• S-P networks are based on the two primitive cryptographic
operations
• substitution (S-box)
• permutation (P-box)
• provide confusion and diffusion of the message
Feistel
Cipher
Structure
Feistel
Cipher
Decryption
Feistel Cipher Design Principles
• block size
• increasing size improves security, but slows the cipher
• key size
• increasing size improves security, makes exhaustive key searching harder, but may slow the
cipher
• number of rounds
• An increasing number improves security, but slows the cipher
• subkey generation
• Greater complexity can make analysis harder, but it slows the cipher
• round function
• Greater complexity can make analysis harder, but it slows the cipher
• fast software encryption/decryption & ease of analysis
• There are more recent concerns for practical use and testing
Data Encryption Standard (DES)
• The most widely used block cipher in the world
• Also known as the Data Encryption Algorithm.
• adopted in 1977 by NBS (now NIST)
• as FIPS PUB 46
• DES encrypts 64-bit data using a 56-bit key
• It has widespread use
• There has been considerable controversy over its security
• Replaced by the Advanced Encryption Standard (AES) in 2001
 DES History
• IBM developed Lucifer cipher
• by team led by Feistel
• used 64-bit data blocks with 128-bit key
• then redeveloped as a commercial cipher with input from NSA
and others
• in 1973 NBS issued request for proposals for a national cipher
standard
• IBM submitted their revised Lucifer which was eventually
accepted as the DES
DES Design Controversy
• Although the DES standard is public
• There was considerable controversy over the design
• in the choice of a 56-bit key (vs Lucifer 128-bit)
• and because design criteria were classified
• Subsequent events and public analysis show, in fact design was
appropriate
• DES has become widely used, especially in financial applications
 DES (Data Encryption Standard)
• Published in 1977, standardized in 1979.
• Key: 64-bit quantity = 8-bit parity + 56-bit key
• Every 8th bit is a parity bit.
• 64-bit input, 64-bit output.

64-bit M 64-bit C
DES
Encryption

56 bits
DES
Encryption
Initial Permutation IP
• First step of the data computation
• IP reorders the input data bits
• Even bits to the LH half, odd bits to the RH half
• See text Table 3.2 (a and b) on the next page
• The input to a table consists of 64 bits numbered from 1 to 64.
• The 64 entries in the permutation table contain a permutation of the
numbers from 1 to 64.
• Each entry in the permutation table indicates the position of a numbered
input bit in the output, which also consists of 64 bits.
Permutation Tables for DES
DES Round Structure
• Uses two 32-bit L & R halves
• As for any Feistel cipher can be described as:
Li = Ri–1
Ri = Li–1 xor F(Ri–1, Ki)
• takes 32-bit R half and 48-bit subkey and:
• expands R to 48 bits using permutation E
• adds to subkey
• passes through 8 S-boxes to get a 32-bit result
• Finally, permutes this using 32-bit perm P
A Single
Round DES
Algorithm
 Per-Round Key Generation
Initial Permutation of DES key

C i-1 28 bits D i-1 28 bits

Circular Left Shift Circular Left Shift

One
round Permutation Round 1,2,9,16:
with Discard single shift
Others: two bits
48 bits
Ki
Ci 28 bits Di 28 bits
 A DES Round
32 bits Ln 32 bits Rn

E
One Round 48 bits
Mangler
Encryption Function 48 bits
S-Boxes Ki

32 bits

32 bits Ln+1 32 bits Rn+1

 Mangler Function
4 4 4 4 4 4 4 4

6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6

+ + + + + + + +

S1 S2 S3 S4 S5 S6 S7 S8 The permutation produces

“spread” among the
4 4 4 4 4 4 4 4 chunks/S-boxes!

Permutation
 Bits Expansion (1-to-m)
1 2 3 4 5 32
Input: 0 0 1 0 1……. 1

Output

1 0 0 1 0 1 0 1 …….. 1 0
1 2 3 4 5 6 7 8 48
Substitution Boxes S
• have eight S-boxes which map 6 to 4 bits
• Each S-box is actually 4 little 4-bit boxes
• outer bits 1 & 6 (row bits) select one row
• inner bits 2-5 (col bits) are substituted
• The result is 8 lots of 4 bits, or 32 bits
• row selection depends on both data & key
• A feature known as autoclaving (auto keying)
• example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03
 S-Box (Substitute and Shrink)
• 48 bits ==> 32 bits. (8*6 ==> 8*4)
• 2 bits used to select amongst 4 substitutions for the
rest of the 4-bit quantity

2 bits I1
row I2
I3 Si O1
O2
I4 O3
I5 O4

4 bits I6
column i = 1,…8.
 S-Box Examples
Each row and column contain different numbers.

0 1 2 3 4 5 6 7 8 9…. 15

0 14 4 13 1 2 15 11 8 3

1 0 15 7 4 14 2 13 1 10

2 4 1 14 8 13 6 2 11 15

3 15 12 8 2 4 9 1 7 5

Example: input: 100110 output: ???

 DES Box Summary
• Simple, easy to implement:
• Hardware/gigabits/second, software/megabits/second
• 56-bit key DES may be acceptable for non-critical
applications, but triple DES (DES3) should be secure for most
applications today
• Supports several operation modes (ECB CBC, OFB, CFB) for
different applications
DES Standard
• Cipher Iterative Action : • Key Generation Box :
• Input: 64 bits • Input: 56 bits
• Key: 48 bits • Output: 48 bits
• Output: 64 bits

One round (Total 16 rounds)

DES Key Schedule
• forms subkeys used in each round
• consists of:
• initial permutation of the key (PC1) which selects 56-bits in
two 28-bit halves
• 16 stages consisting of:
• selecting 24 bits from each half
• permuting them by PC2 for use in the function f,
• rotating each half separately, either 1 or 2 places, depending on the
key rotation schedule K
DES Decryption
• Decrypt must unwind the steps of data computation
• With the Feistel design, do the encryption steps again
• using subkeys in reverse order (SK16 … SK1)
• Note that IP undoes the final FP step of encryption
• 1st round with SK16 undoes 16th encrypt round
• ….
• 16th round with SK1 undoes 1st encrypt round
• Then final FP undoes the initial encryption IP
• Thus, recovering the original data value
Avalanche Effect
• Key desirable property of encryption algorithm
• Where a change of one input or key bit results in changing more
than half output bits
• DES exhibits a strong avalanche
Strength of DES – Key Size
• 56-bit keys have 256 = 7.2 x 1016 values
• Brute force search looks hard
• Recent advances have shown is possible
• In 1997, on the Internet, in a few months
• In 1998, on dedicated h/w (EFF), in a few days
• In 1999 above were combined in 22 hours!
• Still must be able to recognize plaintext
• Now considering alternatives to DES
 Strength of DES – Timing Attacks
• Attacks the actual implementation of the cipher
• Use knowledge of the consequences of implementation to
derive knowledge of some/all subkey bits
• Specifically use the fact that calculations can take varying
times depending on the value of the inputs to it
• Particularly problematic on smartcards
 Strength of DES – Analytic Attacks
• Now have several analytic attacks on DES
• These utilise some deep structure of the cipher
• by gathering information about encryptions
• can eventually recover some/all of the sub-key bits
• If necessary, then exhaustively search for the rest
• Generally, these are statistical attacks
• include
• differential cryptanalysis
• linear cryptanalysis
• related key attacks
Block Cipher Design Principles
• basic principles, still like Feistel in the 1970s
• number of rounds
• More is better, exhaustive search best attack
• function f:
• provides “confusion”, is nonlinear, and avalanche
• key schedule
• complex subkey creation, key avalanche
 DES Replacement
• Triple-DES (3DES)
• 168-bit key, no brute force attacks
• Underlying encryption algorithm the same, no effective analytic
attacks
• Drawbacks
• Performance: no efficient software codes for DES/3DES
• Efficiency/security: bigger block size desirable
• Advanced Encryption Standards (AES)
• US NIST issued call for ciphers in 1997
• Rijndael was selected as the AES in Oct-2000
Thank you!