Information Systems
Security
Symmetric Encryption and
Message Confidentiality
Overview
• Conventional Encryption Principles
• Conventional Encryption Algorithms
• Cipher Block Modes of Operation
• Location of Encryption Devices
• Key Distribution
2
Basic Terminology
• plaintext - original message
• ciphertext - coded message
• cipher - algorithm for transforming plaintext to ciphertext
• key - info used in cipher known only to sender/receiver
• encipher (encrypt) - converting plaintext to ciphertext
• decipher (decrypt) - recovering plaintext from ciphertext
• cryptography - study of encryption principles/methods
• cryptanalysis (codebreaking) - study of principles/ methods of
deciphering ciphertext without knowing key
• cryptology - field of both cryptography and cryptanalysis
3
Encryption
• The most important automated tool for
network and communication security is
encryption.
• The most common forms of encryption
are:
1. conventional or symmetric
encryption
2. public-key or asymmetric encryption.
4
Symmetric Encryption
• Called conventional/private-key single-
key encryption
• Sender and recipient share a common key
• All classical encryption algorithms are
private-key
• Symmetric Encryption was the only type
prior to invention of public-key in 1970’s
and is most widely used
5
Conventional Encryption
Principles
• An encryption scheme has five ingredients
• Plain text
• Encryption algorithm
• Secret key
• Cipher text
• Decryption algorithm
• Security depends on the secrecy of the key,
not the secrecy of the algorithm
6
Conventional Encryption
Algorithm Components:
• Plain Text- original data or input
• Encryption Algorithm- performs substitiutions
or transformations on the plaintext
• Secret key-Input to the encryption algorithm.
Also determines the substitutions/
transpositions to be made
• Cipher Text- scrambled message or output
• Decryption Algorithm- encryption algorithm run
backward, taking the cipher text and producing
the plain text.
7
Conventional Encryption
Principles
8
Conventional Encryption
• More rigorous definition
• Five components to the algorithm
– A Plaintext message space, M
– A family of enciphering transformations, EK:M ® C,
where KÎK
– A key space, K
– A ciphertext message space, C
– A family of deciphering transformations, DK: C ® M,
where KÎK
9
Conventional Encryption
M EK C DK M
EK defined by an encrypting algorithm E
DK defined by an decrypting algorithm D
For given K, DK is the inverse of EK, i.e.,
DK(EK(M))=M for every plain text message M
10
Requirements
• Two requirements for secure use of
symmetric encryption:
– a strong encryption algorithm
– a secret key known only to sender / receiver
• Mathematically have:
Y = E(K, X)
X = D(K, Y)
• Assume encryption algorithm is known
• Implies a secure channel to distribute key
11
Symmetric Encryption
• Security depends on the secrecy of the
key, NOT the secrecy of the algorithm
• Do not need to keep the algorithm
secret- only the key
• This feature makes symmetric
encryption feasible for widespread use.
12
Cryptography
• Classified according to three independent dimensions:
1. The type of operations used for transforming
plaintext to ciphertext
i. Substitution
ii. Transposition
iii. Product
2. The number of keys used
• Symmetric (single key or secret- key or private-key)
• Asymmetric (two-keys, or public-key encryption)
3. The way in which the plaintext is processed
• Block- a block at a time
• Stream- one element at a time
13
Cryptanalysis
• Process of attempting to discover the
plaintext or key
• An encryption scheme is computationally
secure if the ciphertext meets one of
these criteria:
– cost of breaking the cipher exceeds the
value of the information
– time required to break the cipher exceeds
the useful lifetime of the information
14
Cryptanalysis
• The process of attempting to discover the
plaintext or key
Alan Turing broke the
Enigma Code in WWII
http://www.secretcodebreaker.com/SCB&CipherMachines.wmv
15
Enigma
The Enigma was a wooden box
with a keyboard and a bank of
lettered lights corresponding to
the keys. To encrypt a message,
a plaintext character was typed
in, and after scrambling, the
appropriate light was turned on
to give the ciphertext character.
See http://www.vectorsite.net/ttcodep.html#m9
Full video: (45 minutes)
http://www.youtube.com/watch?v=XMK2U3xQQ8A
&feature=related
Simulation:
http://www.enigmaco.de/enigma/enigma.html
16
Cryptanalysis
• Objective to recover key not just
message
• General approaches:
– cryptanalytic attack
– brute-force attack
• If either succeeds all key use
compromised
17
Techniques
• When only ciphertext is known:
– Most difficult problem
– Brute force – using all possible keys
– Easiest to defend against, since opponent
hast least amount of information
• When some plain-text is known:
– Opponent may identify word patterns, type
of file, some context, enabling decoding
18
Cryptanalysis
• A brute force approach involves trying
every possible key until the translation is
obtained.
• Some new low cost chips have made this
approach more reasonable.
• Greatest security problem is maintaining
the security of the key
• See types of attacks in Stallings
summarized on next slides.
19
Cryptanalytic Attacks
Ø ciphertext only
l only know algorithm & ciphertext, is statistical,
know or can identify plaintext
Ø known plaintext
l know/suspect plaintext & ciphertext
Ø chosen plaintext
l select plaintext and obtain ciphertext
Ø chosen ciphertext
l select ciphertext and obtain plaintext
Ø chosen text
l select plaintext or ciphertext to en/decrypt
20
Types of Attacks
21
Average time required for
exhaustive key search
Key Size Number of Time required at Time required
(bits) Alternative 1 decryption/µs at 106
Keys decryptions/µs
32 232 = 4.3 ´ 231 µs = 35.8 2.15
109 min. milliseconds
56 256 = 7.2 ´ 255 µs = 1142 10.01 hours
1016 years
128 2128 = 3.4 ´ 2127 µs = 5.4 ´ 5.4 ´ 1018 years
1038 1024 years
168 2168 = 3.7 ´ 2167 µs = 5.9 ´ 5.9 ´ 1030 years
1050 1036 years 22
Computationally Secure
An encryption scheme is said to be
computationally secure if:
• The cost of breaking the cipher
exceeds the value of the encrypted
information or
• The time required to break the
cipher exceeds the useful lifetime of
the information.
23
Classical ciphers
• Substitution- “units” of plain text are
replaced with cipher text
– Polyalphabetic substitution- different for
each character
• Transposition- “unit” of plaintext are
rearranged, usually in complex order
• See (http://en.wikipedia.org/wiki/Cipher)
24
Caesar Cipher
plain: abcdefghijklmnopqrstuvwxyz
key: defghijklmnopqrstuvwxyzabc
cipher: PHHW PH DIWHU WKH ELUWKGDB SDUWB
plain: MEET ME AFTER THE BIRTHDAY PARTY
25
“Rail-Fence” Cipher
DISGRUNTLED EMPLOYEE
D R L E O
I G U T E M L Y E
S N D P E
DRLEOIGUTE MLYESNDPE
26
Stream and Block Ciphers
• Stream Ciphers and block ciphers are two
categories of ciphers used in classical
cryptography.
• Stream and Block Ciphers differ in how large a
piece of the message is processed in each
encryption operation.
• Stream ciphers encrypt plaintext one byte or
one bit at a time.
• Block ciphers encrypt plaintext in chunks.
Common block sizes are 64 and 128 bits.
27
Stream Cipher
• Stream Cipher – encryption of bits
– Often pseudorandom generators
– Simple and fast
– Not very secure
– RC4, SEAL
– Inspired by the one time pad (OTP)
– A one-time pad uses a keystream of
completely random digits. The keystream is
combined with the plaintext digits one at a
time to form the cipher text.
– http://en.wikipedia.org/wiki/Stream_cipher 28
Block Ciphers
• Block Cipher is a symmetric key cipher operating
on fixed-length groups of bits, called blocks,
with an unvarying transformation. A block cipher
encryption algorithm might take (for example) a
128-bit block of plaintext as input, and output a
corresponding 128-bit block of cipher text. The
exact transformation is controlled using a
second input — the secret key.
• Short explanation
– DES, 3DES, AES, IDEA
29
Feistel Cipher
• Horst Feistel devised the Feistel Cipher
– based on concept of invertible product cipher
• Partitions input block into two halves
– process through multiple rounds which
– perform a substitution on left data half
– based on round function of right half & subkey
– then have permutation swapping halves
• Implements Shannon’s S-P net concept
30
Claude Shannon and Substitution-
Permutation Ciphers
• Claude Shannon introduced idea of
substitution-permutation (S-P) networks in
1949
• form basis of modern block ciphers
• S-P nets are based on the two primitive
cryptographic operations:
– substitution (S-box)
– permutation (P-box)
• provide confusion & diffusion of message &
key
31
Diffusion and Confusion…
• Diffusion:
“The statistical structure of the plaintext is
spread (dissipated) into long-range statistics of
the ciphertext.”
• Achieved by having each plaintext digit affect
the value of many ciphertext digits.
• Objective is to globalize the local affects.
32
Diffusion and Confusion…
• Confusion:
“Attempts to make the relationship between the
ciphertext and the encryption key as complex as
possible.”
• Achieved by using a complex substitution algorithm.
• Even if an attacker can have some handle on the
statistics of the ciphertext, it is very difficult to
deduce the key.
33
Feistel Cipher Structure
• Virtually all conventional block
encryption algorithms, including DES
have a structure first described by
Horst Feistel of IBM in 1973
• The realization of a Feistel Network
depends on the choice of the following
parameters and design features:
(see next slide)
• http://www.youtube.com/watch?v=ySZvE9vOfEQ
34
Feistel Cipher Structure
• Block size: larger block sizes mean greater
security
• Key Size: larger key size means greater
security
• Number of rounds: multiple rounds offer
increasing security
• Subkey generation algorithm: greater
complexity will lead to greater difficulty of
cryptanalysis.
• Fast software encryption/decryption: the
speed of execution of the algorithm becomes a
concern 35
Feistel Cipher
• The plain text block is divided into two
halves Lo and Ro
• The two halves pass through n rounds of
processing and then combine to produce
the cipher text block.
• At each round a substitution is performed
on the left half of the data by applying a
round function F to the right half of the
data and then XORing it with the left half
36
37
Feistel Structure
• The Feistel Structure is a general
example used by all symmetric block
ciphers:
• It is a series of rounds, each performing
substitutions and permutations using a
secret key value
38
Feistel Cipher Design
Elements
Øblock size Increasing size means greater
Økey size security, but slows
cipher
Ønumber of rounds
Øsubkey generation algorithm Greater complexity,
harder to decrypt
Øround function
Other Considerations
Øfast software en/decryption
Øease of analysis
39
Feistel Cipher Structure
Encryption
Decryption
40
Feistel Algorithms
• Encryption and decryption algorithms are
essentially the same
• To decrypt:
– Use the ciphertext as input
– Use the sub-keys in reverse order (Kn, Kn-1…)
• Advantage:
– Only one algorithm is needed for encryption
and decryption
41
Symmetric Block Encryption
Algorithms
• Most common symmetric encryption
algorithms are block ciphers.
• Block Ciphers process plaintext input in
fixed size blocks and produce a block of
equal size cipher text.
– DES - Data Encryption Standard
– 3DES – Triple DES
– AES – Advanced Encryption Standard
42
Conventional Symmetric
Encryption Algorithms
• Data Encryption Standard (DES)- 1977
– The most widely used encryption scheme
– The algorithm is reffered to the Data Encryption
Algorithm (DEA)
– DES is a block cipher
– Variation of Feistel Cipher
– The plaintext is processed in 64-bit blocks
– The key is 56-bits in length
– 16 subkeys used in 16 rounds
– No longer used for government transmissions
– Controversy over security
43
44
45
DES
• The overall processing at each iteration:
– Li = Ri-1
– Ri = Li-1 F(Ri-1, Ki)
• Concerns about:
– The algorithm ( since the design criteria
were classified)
– and the key length (56-bits) vs 128 bits
46
Time to break a code
(106 decryptions/µs)
47
DES Concerns
• Although there are concerns about the
DES design- no weakness has yet been
discovered.
• With 56 bit keys- brute force is possible
as demonstrated by “DES Cracker” in
1998 and machine speeds and costs will
continue to improve.
• A 128 bit key is guaranteed to be
unbreakable by brute force.
48
DES Alternatives
• A replacement for DES was needed
• Use multiple encryption with DES
implementations – 3DES
• Design a new alternative- AES is a new
cipher alternative
49
3DES with 2 Keys
• Use 3 encryptions
• Can use 2 keys with E-D-E sequence
– C = EK1(DK2(EK1(P)))
– if K1=K2 then can work with single DES
• Standardized in ANSI X9.17 & ISO8732
• No current known practical attacks
– several proposed impractical attacks might
become basis of future attacks
– Brute force search about 2112
50
Triple DES
• Use 3 keys and 3 executions of the DES
algorithm (encrypt-decrypt-encrypt)
C = EK3[DK2[EK1[P]]] encrypt
• C = ciphertext
• P = Plaintext
• EK[X] = encryption of X using key K
• DK[Y] = decryption of Y using key K
P = DK1[EK2[DK3[C]]] decrypt
• Effective key length of 168 bits
51
Triple DES
52
Triple DES
• 3 Key 3DES is the preferred alternative
• Approved for use in financial applications
• Adopted by some Internet applications,
(eg. PGP, S/MIME)
• High level of confidence that 3DES is
secure and resistent to cryptanalysis.
• Disadvantage – slow, small block size
53
Advanced Encryption Standard
AES (2001)
• Can use TripleDES – but slow, has small
blocks
• AES increased block size from 64 bits to
128 bits and allows for keys of 128,192 or
256 bits
• 128 bit key is most common
• Not a Feistel structure- operates on
entire block instead of halves
54
AES Algorithm
• Input is a single 128 bit block (square matrix)
• Block is copied into the STATE array
• At each stage the STATE array is modified by
encryption or decryption
• After the final stage the STATE array is copied
to an output matrix.
• The key is also a square matrix of 128 bits
55
AES Cipher
• An iterative rather than feistel cipher
– Operates on entire block in every round rather than
halves
– Processes data as block of 4 columns of 4 bytes
• Design Criteria:
– Resistant against known attacks
– Speed and code compactness on many CPUs
– Design simplicity
56
AES Cipher Stages
4 Stages are used (1 permutation, 3
substitution):
1. Substitute bytes (S-box)
2. Shift rows (row-by-row permutation)
3. Mix columns (substitution using function
of all bytes in the column)
4. Add Round Key ( bitwise XOR with key)
57
AES
Encryption
Process
58
AES Structure
• Cipher consists of N rounds depending
on key length
• Round 0 – add round key ( XOR with Key)
• Next rounds use all 4 stages
• Final round N -1 uses only 3 stages (not
mix columns)
• Each stage is reversible -based on:
(A B B=A)
59
AES
Structure
60
Other Symmetric Block
Ciphers
• International Data Encryption Algorithm (IDEA)
– 128-bit key
– Used in PGP
• Blowfish
– Easy to implement
– High execution speed
– Run in less than 5K of memory
• CAST-128
– Key size from 40 to 128 bits
– The round function differs from round to round
61
Random Numbers
• There are many uses of random numbers in
cryptography
– nonces in authentication protocols to prevent replay
– session keys
– public key generation
– keystream for a one-time pad
• It is Critical that these values be:
– statistically random, uniform distribution,
independent (e.g. Same number of 0’s and 1’s)
– unpredictability of future values from previous values
• True random numbers provide this
• Care needed with generated random numbers 62
Pseudo Random Number
Generators ( PRNGs)
• Often use deterministic algorithmic
techniques to create “random numbers”
– although are not truly random
– can pass many tests of “randomness”
• Known as “pseudorandom numbers”
• Created by “Pseudorandom Number
Generators (PRNGs)”
63
True and Pseudo Random
Numbers
• TRNG – true random number generator
– Takes a source that is random, entropy
source, such as the system clock
• PRNG – pseudorandom number generator
– Takes a fixed value called the seed
– Produces output using a deterministic
algorithm
• PRF - pseudorandom function
– takes as input a seed plus some context specific
values, such as a user ID or an application ID.
True and Pseudo Random
Numbers
65
Stream Cipher
• A key is input to a pseudorandom bit
generator that produces an apparently
random keystream of bits.
• These bits are XOR’d with message to
encrypt it,
• They are XOR’d again to decrypt it by the
receiver.
66
Block and Stream Ciphers
• A block cipher inputs a block of elements
and produces an output block for each
input block.
• A stream cipher processes the input
elements continuously, producing output
one element at a time.
• Block ciphers are more common, but
there are applications which use stream
ciphers.
67
Stream Cipher Structure
68
Stream Cipher Properties
• Some design considerations are:
• long period with no repetitions
• statistically random
• depends on large enough key
• large linear complexity
• If properly designed, can be as secure as
a block cipher with same size key
• Usually simpler & faster
69
RC4
• A proprietary cipher owned by RSA Security
• A Ron Rivest design, simple but effective, based on
random permutation
• Variable key size, byte-oriented stream cipher
• Widely used
• SSL/TLS web security protocol
• Wireless WEP/WPA LAN security protocols
• Key forms random permutation of all 8-bit values
• Uses that permutation to scramble input info processed
a byte at a time
• Kept secret until anonymously posted on the Internet 70
RC4 Algorithm
• The RC4 algorithm is remarkably simple.
• It uses a variable-length key of from 1
to 256 bytes.
• The RC4 key schedule initializes the
state S to the numbers 0..255
• Then it walks through each entry in turn,
using its current value plus the next byte
of key to pick another entry in the array,
and swaps their values over.
71
RC4 Algorithm
Ø Starts with an array S of numbers 0..255
• Use key to shuffle array
• S forms internal state of the cipher
for i = 0 to 255 do // Initialization
S[i] = i
T[i] = K[i mod keylen]
j=0 // Initial permutation of S
for i = 0 to 255 do
j = (j + S[i] + T[i]) (mod 256)
swap (S[i], S[j])
• Total number of possible states is 256! 72
RC4 Encryption
• Encryption continues shuffling array values
• Sum of shuffled pair selects "stream key" value from
permutation
• XOR S[t] with next byte of message to en/decrypt
i = j = 0; //Stream Generation
while (true) //for each message byte Mi
i = (i + 1) (mod 256);
j = (j + S[i]) (mod 256);
swap(S[i], S[j]);
t = (S[i] + S[j]) (mod 256);
k= S[t];
Ci = Mi XOR S[t] or Mi = Ci XOR S[t]; (to
Encrypt/Decrypt) 73
RC4 Overview
74
RC4 Security
• Claimed secure against known attacks
• have some analyses, none practical
• Result is very non-linear
• Since RC4 is a stream cipher, must never
reuse a key
• Concern with WEP, but due to key handling
rather than RC4 itself
• Secure with key length of at least 128 bits
75
RC5
• RC5 – designed by Ron Rivest (1994)
– Block cipher
– Suitable for hardware and software
– Fast, simple
– Adaptable to processors of different word
lengths
– Variable block size ( 32, 64, 128 bits)
– Variable number of rounds ( 0 to 255)
– Variable-length key ( 0 to 2040 bits)
– Low memory requirement,High security
– Data-dependent rotations
– Modulo additions and exclusive ORs (XOR)
– Feistel-like structure 76
RC5
Two half- rounds of
RC5
See http://en.wikipedia.org/wiki/RC5 for details 77
Modes of Operation
• The different ways an encryption algorithm can
be used are modes of operation
• NIST SP 800-38A defines 5 modes:
1. Electronic codebook (ECB) mode
2. Cipher Block Chaining (CBC) mode
3. Cipher Feedback (CFB) mode
4. Output Feedback (OFB) mode
5. Counter (CTR) mode
78
Modes of Operation
• Block ciphers encrypt fixed size blocks
– eg. DES encrypts 64-bit blocks with 56-bit key
– AES uses 128 bit blocks
– For larger sizes, break plain text into blocks
• Need some way to en/decrypt arbitrary amounts
of data in practice
• have block and stream modes
• Cover a wide variety of applications
• Can be used with any block cipher
79
Electronic Codebook Mode
• Message is broken into independent
blocks which are encrypted
• Each block is a value which is
substituted, like a codebook, hence name
• Each block B is encoded or decoded
independently of the other blocks:
Ci = EK(Pi) Bi= DK(Ci)
• Uses: secure transmission of single values
80
Electronic Codebook Mode
• Codebook- for a given key there is a unique
ciphertext for every b-bit block of plaintext.
• Advantages:
– Simplicity
– Tolerates block loss (eg. over network)
– Used to send a few block of data
• Disadvantage:
– ECB mode may reveal pattern in text, i.e.
blocks that are identical, will be encrypted in
the same way
81
Cipher Block Chaining
Mode of Operation
• Message is broken into blocks
• Linked together in encryption operation
• Each previous cipher block is chained with
current plaintext block, hence name
• Use Initial Vector (IV) to start process
• Input to encryption algorithm bears no
relationship to plaintext block
• Uses: bulk data encryption, authentication
82
Cipher Block Chaining
Mode of Operation
• Cipher Block Chaining Mode (CBC)
– The input to the encryption algorithm is the XOR of
the current plaintext block and the preceding
ciphertext block.
– Repeating pattern of 64-bits are not exposed
Ci = E k [Ci -1 Å Pi ]
D K [Ci ] = D K [E K (Ci -1 Å Pi )]
D K [Ci ] = (Ci -1 Å Pi )
Ci -1 Å D K [Ci ] = Ci -1 Å Ci -1 Å Pi = Pi
83
84
Cipher Feedback (CFB)
Mode
• Message is treated as a stream of bits
• Added to the output of the block cipher
• Result is feed back for next stage (hence name)
• Standard allows any number of bits (1, 8, 64 or
128, etc.) to be feed back
– denoted CFB-1, CFB-8, CFB-64, CFB-128 etc.
• Most efficient to use all bits in block (64 or 128)
Ci = Pi XOR EK(Ci-1)
Ci-1 = IV
• Uses: stream data encryption, authentication
85
S-bit Cipher
Feedback
CFB-s
86
Advantages and Limitations
of CFB
• Appropriate when data arrives in bits/bytes
• Most common stream mode
• Limitation -there is a need to stall while doing
block encryption after every n-bits
• Note that the block cipher is used in encryption
mode at both ends
• Errors propagate for several blocks after the
error
• Not good for “noisy” links – requires reliable
transport 87
Outback Feedback (OFB)
Mode
• A sequence of block is encrypted with a
sequence of blocks generated with the
block cipher.
• It begins with an initialization vector and
generates a series of pad vectors.
• This mode can tolerate block losses
• It can be performed in parallel, both for
encryption and decryption
88
Counter (CTR)
• A “new” mode, though proposed earlier
• Similar to OFB but encrypts a counter
value rather than any feedback value
• Must have a different key & counter
value for every plaintext block (never
reused)
Oi = EK(i)
Ci = Pi XOR Oi
• uses: high-speed network encryptions
89
Advantages and Limitations
of CTR
• Efficiency
– can do parallel encryptions in h/w or s/w
– can preprocess in advance of need
– good for bursty high speed links
• Random access to encrypted data blocks
• Provable security (good as other modes)
• Must ensure never reuse key/counter
values, otherwise could break, like OFB
90
Recommended Reading
• Stallings, W. Cryptography and Network
Security: Principles and Practice, 5th
edition. Prentice Hall, 2011
• Scneier, B. Applied Cryptography, New
York: Wiley, 1996
• Mel, H.X. Baker, D. Cryptography
Decrypted. Addison Wesley, 2001
• Simon Singh, The Code Book, (on-line)
• http://simonsingh.net/books/the-code-book/the-book/
91
