Chapter 1: Introduction
Fall 2021
Cp 633
Slide #9-*
Chapter 10: Basic Cryptography
Classical Cryptography (symmetric)
This lecture is made by combining materials from:
M. Bishop : Computer Security the art and science, second edition (Chapter 10)
J.F. Kurose, K.W.Ross: Computer networking
Cp 633
*
Fall 2021
Cp 633
Slide #9-*
Overview
Classical Cryptography
Cæsar cipher, substitution, transposition ciphers
DES, AES
Cp 633
*
Fall 2021
Cp 633
Slide #9-*
The language of cryptography
symmetric key crypto: sender, receiver keys identical
public-key crypto: encryption key public, decryption key secret (private)
plaintext
plaintext
ciphertext
encryption
algorithm
decryption
algorithm
Alice’s
encryption
key
Bob’s
decryption
key
K
A
K
B
Cp 633
Fall 2021
Cp 633
Slide #9-*
Who might Bob, Alice be?
… well, real-life Bobs and Alices!
Web browser/server for electronic transactions (e.g., on-line purchases)
on-line banking client/server
DNS servers
routers exchanging routing table updates
other examples?
Cp 633
Fall 2021
Cp 633
Slide #9-*
Cryptosystem
Quintuple (E, D, M, K, C)
M set of plaintexts
K set of keys
C set of ciphertexts
E set of encryption functions e: M x K -> C
D set of decryption functions d: C x K -> M
Cryptography mainly provides confidentiality
It can also be used to provide integrity of data and origin (against changing of message)
It can provide non-repudiation.
Cp 633
Fall 2021
Cp 633
Slide #9-*
Example – up to here 23 Sept.
Example: Cæsar cipher
M = { sequences of letters } stored in the array in the range (0..25)
E.g M[0]=A, M[1]=B,….M[25]=Z
K = { i | i is an integer and 0 ≤ i ≤ 25 }
E = { Ek | k K and for all letters m,
Ek(m) = (m + k) mod 26 }
D = { Dk | k K and for all letters c,
Dk(c) = (26 + c – k) mod 26 }
C = M
E.g. HELLO WORLD encrypted with key E3=3 usually written as ‘D’ gives KHOOR ZRUOG
Cp 633
Fall 2021
Cp 633
Slide #9-*
Cryptographic Attacks
Opponent whose goal is to break cryptosystem is the adversary
We assume adversary knows the algorithm used (public), but not key
Three types of attacks in decreasing order of difficulty:
ciphertext only: adversary has only ciphertext; goal is to find plaintext and possibly key
known plaintext: adversary has ciphertext and corresponding plaintext; goal is to find key
chosen plaintext: adversary may supply plaintexts and obtain corresponding ciphertext; goal is to find key
Pangram: a quick brown fox jumps over the lazy dog
Cp 633
Fall 2021
Cp 633
Slide #9-*
Basis for Attacks
Real attacks generally don’t break cryptography! Don’t pick the lock, tunnel into the vault.
Mathematical attacks
Based on analysis of underlying mathematics (crypto algorithms are public, keys are secret).
Statistical attacks
Make assumptions about the distribution of letters, pairs of letters (digrams), triplets of letters (trigrams), in plaintext.
This is a model of particular language, e.g. English
Assumption is that cipher text will have same statistical behavior as the particular language.
Cp 633
Fall 2021
Cp 633
Slide #9-*
Classical (Symmetric) Cryptography
Sender and receiver share common key for encryption and decryption (keys are the same, or trivial to derive from one another)
Dk = E(-1)k or m = Dk (Ek (m))
There are two basic types of symmetric ciphers
Transposition ciphers (rearrange characters in message)
The key is some permutation function over the message
Substitution ciphers (change one character with another), e.g Caesar cipher
There should be table of mapping as a key
Both ciphers can be attacked by statistical method e.g. by analyzing 1-gram and 2-gram occurrence of letters in the message.
Combinations are called product ciphers
Cp 633
Fall 2021
Cp 633
Slide #9-*
Symmetric key cryptography
substitution cipher : substituting one thing for another
monoalphabetic cipher: substitute one letter for another
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
E.g.:
Q: How hard to break this simple cipher?:
brute force by permutations or by statistics
Encryption key: mapping from set of 26 letters to set of 26 letters
Cp 633
Vigenere cipher (section 10.2.2.1)
In order to mitigate statistical attacks on substitution ciphers Vigenere cipher uses a sequence of keys represented by a string (poly-alphabetic cypher).
The length of the key is called the period of the cipher.
Example of key BENCH shifts by (B-A,1), (E-A,4), (N-A,13), (C-A,2), (H-A,6).
Letter repetitions open a possibility to attack Vigenere cipher if key is short.
One time pad is a variant of Vigenere cipher where key is used only once.
Key string is chosen at random and has at least the length of the message.
Fall 2021
Cp 633
Slide #9-*
Key B ENCHBENC HBENC HBENCH
Plaintext A LIMERICK PACKS LAUGHS
Ciphertext B PVOLSMPM WBGXU SBYTJZ
Cp 633
Let the message be “THE BOY HAS THE BAG” and key to be VIG. Then the letters THEB appear twice in cipher text as OPKW
*
A more sophisticated encryption approach coming from Vigenere cypher
n substitution ciphers, M1,M2,…,Mn
cycling pattern of substitution ciphers:
e.g., n=4: M1,M3,M4,M3,M2; M1,M3,M4,M3,M2; .
for each new plaintext symbol, use subsequent substitution pattern in cyclic pattern
dog: d is encrypted using cypher M1, o using M3, g using M4
Encryption key in this case is composed of : n substitution ciphers, and cyclic pattern
key need not be just n-bit pattern
There are stream ciphers where each letter is independently enciphered
and block ciphers where whole message is enciphered as stream of bits.
Fall 2021
Slide #9-12
Cp 633
Cp 633
Actually, in block cipher stream of bits is chopped into blocks which are further encrypted.
*
Fall 2021
Cp 633
Slide #9-*
Symmetric key cryptography
symmetric key crypto: Bob and Alice share same (symmetric) key: K
e.g., key is known substitution pattern in mono-alphabetic substitution cipher
Q: how do Bob and Alice agree on key value?
plaintext
ciphertext
encryption
algorithm
decryption
algorithm
A-B
plaintext
message, m
K (m)
A-B
K
A-B
K
A-B
K (m)
A-B
m = K ( )
A-B
Cp 633
We will look into key distribution protocols a bit later.
*
Fall 2021
Cp 633
Slide #9-*
Data Encryption Standard DES , section 10.2.3
Today is not much used but it laid the theoretical and practical groundwork for may other ciphers.
A block cipher (there are also stream cyphers):
encrypts blocks of 64 bits using a 64 bit user’s key
outputs 64 bits of ciphertext
A product cipher, i.e. contains transpositions and substitutions.
basic unit of encryption is the bit
performs both substitution and transposition (permutation) on the bits
Cipher consists of 16 rounds (iterations)
User’s key is reduced to 56 bits after dropping the parity bits.
Each round has a 48 bit key generated from the user’s key
Cp 633
Fall 2021
Cp 633
Slide #9-*
Generation of 16 Round Keys
Initial key has 56 bits (64bits – 8 bits of parity)
Round keys are obtained by permuting 56 bits and extracting 48 bits each time
PC-1 and PC-2 are permutation tables (known).
LSH is table of left shifts (one or two bit shifts depending on round).
Ci and Di are registers which hold 28 bits of the perms. each. Their content is concatenated, permuted and cut to 48 bits.
56bits
Cp 633
Fall 2021
Cp 633
Slide #9-*
DES Encipherment – there are 16 round of encipherment with different key Ki
Function f on the next slide: the right half of the input is expanded to 48 bits and this is xor-ed with the round key.
Then 48 bits are split in 8 sets of six bits, and each set is put through the substitution table called S-box.
All S-boxes are known.
Each S-box produces 4 bits of output.
Those bits are concatenated into 32 bits entity which is permutated.
Decryption
Encryption
Input: 64 bits of data
Li, Ri have 32 bits each.
Initial perm.
Inverse Initial perm.
+
Cp 633
Function f is considered to be strength of the encryption. Decisions how S boxes were made were classified.
*
Fall 2021
Cp 633
Slide #9-*
The f Function strength of DES
Expansion 32 to 48 bits
Cp 633
Major criticism is that design decisions behind S boxes are not known.
*
Fall 2021
Cp 633
Slide #9-*
DES Modes
Direct use of DES is known as Electronic Code Book Mode (ECB)
Encipher each block of 64 bits independently – rarely used and was considered weak.
Cipher Block Chaining Mode (CBC) (on the next slide).
Xor each block with previous ciphertext block
Requires an initialization vector for the first one
Encrypt-Decrypt-Encrypt Mode (2 keys: k, k’) used in financial institutions
c = DESk(DESk’–1(DESk(m)))
Encrypt-Encrypt-Encrypt Mode (3 keys: k, k’, k’’)
c = DESk(DESk’ (DESk’’(m)))
Cp 633
Fall 2021
Cp 633
Slide #9-*
CBC Mode Encryption
init. vector
m1
DES
c1
m2
DES
c2
sent
sent
…
…
…
Cp 633
Fall 2021
Cp 633
Slide #9-*
Current Status of DES
DES design decisions not public
Design for computer system, associated software that could break any DES-enciphered message in a few days was published in 1998
Several challenges to break DES messages were solved using distributed computing
NIST selected Rijndael as Advanced Encryption Standard (AES), successor to DES in 2001.
Designed to withstand attacks that were successful on DES
DES was officially withdrawn in 2005
Only approved implementation of DES is triple DES.
Cp 633
Fall 2021
Cp 633
Slide #9-*
AES: Advanced Encryption Standard
Relatively new symmetric-key NIST standard, replacing DES
processes data in 128 bit blocks
AES can have 128, 192, or 256 bit keys
Number of rounds is function of the key length.
Data block is depicted as square matrix of bytes.
The 128 bit key is also depicted as square matrix of bytes.
There are 10 rounds, including round keys, substitution of bytes, shifting of rows and mixing of columns.
brute force decryption (try each key) taking 1 sec on DES, takes 149 trillion years for AES
Cp 633
Overview of the AES
A block cipher:
encrypts blocks of 128 bits using a 128, 192, or 256 bit key
outputs 128 bits of ciphertext
A product cipher
basic unit is the bit
performs both substitution and transposition (permutation) on the bits
Cipher consists of rounds (iterations) each with a round key generated from the user-supplied key
If 128 bit key, then 10 rounds
If 192 bit key, then 12 rounds
If 256 bit key, then 14 rounds
Fall 2021
Cp 633
Slide 10-*
Cp 633
Structure of the AES: Encryption
Input is placed into a state array, which is then combined with zeroth round key, each key has 16 bytes (128b).
Treat state array as a 4×4 byte matrix,
Round begins
In the first step only input is combined with zeroth round key AddRoundKey
New values substituted for each byte of the state array using S-box –SubBytes
Contents of rows are then cyclically shifted – ShiftRows
Each column independently altered – MixColumns
– Not done in last round
Result of previous step is then xor’ed with round key – AddRoundKey
After last round, state array is the encrypted input
Fall 2021
Cp 633
Slide 10-*
Cp 633
Structure of the AES: Decryption
In decryption round key schedule is reversed
Input is placed into a state array, which is then combined with zeroth round key (of reversed schedule)
Round begins for Inverse (note that InvShiftRows and InvSubBytes have commutative property in the algorithm)
Rows cyclically shifted, in inverse rotation – InvShiftRows
InvSubBytes reverses SubBytes using S-boxes that are inverse to one used in SubBytes.
Result xor’ed with round key (of reversed schedule) – AddRoundKey
Each column independently altered in – InvMixColumns
– Inverse of MixColumn; this is not done in last round
After last round, state array is the decrypted input
Fall 2021
Cp 633
Slide 10-*
Cp 633
Analysis of AES
Designed to withstand attacks that the DES is vulnerable to
All details of design decions are made public, unlike with the DES
In particular, those of the substitutions (S-boxes) were described
After 2 successive rounds, every bit in the state array depends on every bit in the state array 2 rounds ago
No weak, semi-weak keys like in DES
Fall 2021
Cp 633
Slide 10-*
Cp 633
AES Modes
DES modes also work with AES
EDE and “Triple-AES” not used
Extended block size makes this unnecessary
New counter mode CTR added
Fall 2021
Cp 633
Slide 10-*
Cp 633
Alternatives to DES and AES
Blowfish is developed by B. Schneier in 1993.
It has dynamic S boxes and XOR function but also uses binary addition.
Fits in 5Kbytes of memory and needs 521 rounds for subkey generation.
Not suitable for frequent key change.
Key length is 128 bit and can be increased to 448 bits.
RC4 is a stream cypher which operates on bytes.
Key is input in random number generator and outputs is XOR-ed with each byte.
Runs quickly in software
Fall 2021
Cp 633
Slide #9-*
Cp 633
Fall 2021
Cp 633
Slide #9-*
Cp 633
key
PC-1
C0
D0
LSH
LSH
D1
PC-2
K1
K16
LSH
LSH
C1
PC-2
input
IP
L
0
R
0
Å
f
K
1
L
1
= R
0
R
1
= L
0
Å
f
(R
0
, K
1
)
R
16
= L
15
f
(R
15
, K
16
)
L
16
= R
15
IP
–1
output
R
i
–1
(32 bits)
E
R
i
–1
(48 bits)
K
i
(48 bits)
Å
S1
S2
S3
S4
S5
S6
S7
S8
6 bits into each
P
32 bits
4 bits out of each