Aqsa Khalid

Lecturer
School of Computing

CS3002 Information Security

Symmetric
Cryptography

Source: Stallings chap 2

Cryptography: What
• Turning plaintext (an ordinary readable message)
into ciphertext (secret messages that are “hard”
to read)

• The point of cryptography is to send secure

messages over an insecure medium (like the
Internet)
Cryptography: Related Fields
• Cryptography: (“secret writing”)
- Making secret messages

• Cryptanalysis: Breaking secret messages

- Recovering the plaintext from the ciphertext

• Cryptology: The science that studies these both

Cryptography: Related Fields
• Plaintext
– Readable message or data that needs to be protected
• Encryption Algorithm (or Cipher)
– Algorithm to perform various substitutions and
transformations on the plaintext
• Secret key
– Used as input to the algorithm, transformations
depend on the key
• Ciphertext
– Scrambled message produced as output
• Decryption Algorithm (or Cipher)
– Produces the original plaintext
Cryptography: Why

• To achieve important properties of

information security:
– Confidentiality
– Integrity
– Availability
– Authenticity
– Authorization
– Non repudiation
Dramatis Personae
When talking about cryptography, we often use a standard cast of
characters
• Alice, Bob, Carol, Dave
People (usually honest) who wish to communicate
• Eve
A passive eavesdropper, who can listen to any transmitted
messages
• Mallory
An active Man-In-The-Middle, who can listen to, and modify,
insert, or delete, transmitted messages
• Trent
A Trusted Third Party
Cryptography: Major Components

• Confidentiality
- Preventing Eve from reading Alice’s
messages

• Integrity

- Preventing Mallory from modifying Alice’s

messages without being detected

• Authenticity

- Preventing Mallory from impersonating Alice

Kerckhoffs’ Principle
The security of a cryptosystem should not rely on a
secret that’s hard (or expensive) to change
• Don’t have secret encryption methods
- Make the class public information
- Use a secret key to specify which one you’re using
- It’s easy to change the key; it’s usually just a smallish
number
● This has a number of implications:
- The system is at most as secure as the number of
keys
- Eve can just try them all, until she finds the right one
- A strong cryptosystem is one where that’s the best
Eve can do
➢ With weaker systems, there are shortcuts to finding the key
Strong cryptosystems
What information do we assume the attacker
(Eve) has when she’s trying to break our system?
• She may:
- Know the algorithm (the public class of encryption
methods)
- Know some part of the plaintext
- Know a number (maybe a large number) of
corresponding plaintext/ciphertext pairs
- Have access to an encryption and/or decryption oracle
• And we still want to prevent Eve from learning
the key!
Cryptography: Types

Cryptography can be categorized into two main types:

• Symmetric Cryptography:
- Uses the same key for both encryption and decryption
- Only sender and receiver knows the key

• Asymmetric Cryptography:
- Uses different keys for encryption and decryption
- One key is public, while the other is private
Symmetric Cryptography

• AKA conventional or single-key cryptography

• Sender and receiver must both know the secret key
• Uses techniques like confusion and diffusion to
encrypt/decrypt data
Symmetric Cryptography
• Eve, not knowing the key, should not be able to
recover the plaintext

• At worst, Eve tries every key

- How long that takes depends on how long the keys are
- But it only takes this long if there are no “shortcuts”!
Symmetric Crypto Limitations

Pros
• Very fast to compute
• Hardware acceleration available in many cases

Cons
• No mechanism of sharing the key secretly
• Managing separate keys for each pair of users,
otherwise impersonation is possible
– If Alice and Bob share a key. Imagine Trudy shares the
same key with Alice for secure communication. Trudy
may act as Alice and talk to Bob.
Symmetric Encryption

E, D: Algorithms k: secret key

m: plaintext c: ciphertext

Encryption algorithm should be publicly known

Symmetric Crypto: How?

• There are two primary techniques

(1) Substitution – it creates “Confusion”

Replace each character (or bit

string) with another character (or bit
string)

(2) Permutation – it creates “Diffusion”

Change the order of characters or

bit strings.
Symmetric Crypto Limitations

Pros
• Very fast to compute
• Hardware acceleration available in many cases

Cons
• No mechanism of sharing the key secretly
• Managing separate keys for each pair of users,
otherwise impersonation is possible
– If Alice and Bob share a key. Imagine Trudy shares the same
key with Alice for secure communication. Trudy may act as
Alice and talk to Bob.
Classical Ciphers

• We will start with studying classical

ciphers – those used before the of
computer era.
• These ciphers became obsolete
because they could be easily broken by
a computer.
Substitution ciphers
Classical Substitution Ciphers

• Replace plaintext characters according to a

translation table.
• Substitution rules become the secret key

Most well known example: Rotate the inner

Caesar Cipher alphabet disk to
change the key

When key=13,
cipher is called
ROT-13
Attacking the Ceaser cipher

• Ceaser cipher can be quite easily broken by a

brute-force attack: The attacker tries every
possible key on a piece of ciphertext until an
intelligible translation into plaintext is
obtained.
• On average, half of all possible keys must be
tried to achieve success.
– if there are X different keys, on average an attacker
would discover the actual key after X/2 tries.
Attacking the Ceaser cipher

ciphertext
PHHW PH DIWHU WKH WRJD SDUWB

KEY
1 oggv og chvgt vjg vqic rctva 14 btti bt puitg iwt idvp epgin
2 nffu nf bgufs uif uphb qbsuz 15 assh as othsf hvs hcuo dofhm
3 meet me after the toga party 16 zrrg zr nsgre gur gbtn cnegl
4 ldds ld zesdq sgd snfz ozqsx 17 yqqf yq mrfqd ftq fasm bmdfk
5 kccr kc ydrcp rfc rmey nyprw 18 xppe xp lqepc esp ezrl alcej
6 jbbq jb xcqbo qeb qldx mxoqv 19 wood wo kpdob dro dyqk zkbdi
7 iaap ia wbpan pda pkcw lwnpu 20 vnnc vn jocna cqn cxpj yjach
8 hzzo hz vaozm ocz ojbv kvmot 21 ummb um inbmz bpm bwoi xizbg
9 gyyn gy uznyl nby niau julns 22 tlla tl hmaly aol avnh whyaf
10 fxxm fx tymxk max mhzt itkmr 23 skkz sk glzkx znk zumg vgxze
11 ewwl ew sxlwj lzw lgys hsjlq 24 rjjy rj fkyjw ymj ytlf ufwyd
12 dvvk dv rwkvi kyv kfxr grikp 25 qiix qi ejxiv xli xske tevxc
13 cuuj cu qvjuh jxu jewq fqhjo
Brute forcing in general

• Preceding example shows that there is more to

brute-force than simply running through all possible
keys.
• The analyst must be able to recognize plaintext as
plaintext.
– If the message is just plain text in English (or another
language), then the result is easily understood by a human
reader, but the task of recognizing the language would have
to be automated.
– If the text message has been compressed before encryption,
then recognition is more difficult.
– And if the message is some more general type of data, such
as a word document or image or audio, the problem
becomes even more difficult to automate.
Monoalphabetic substitution

• Caesar cipher is actually a special case of

more general monoalphabetic substitution
cipher
Classical Substitution Ciphers

Question
What is the size of ‘key space’ in the monoalphabetic
substitution cipher assuming 26 letters?

a. 26
b. 26!
c. 226
d. 262 Key space = set of all possible
keys
Cryptanalysis

• For such large key spaces brute forcing is no

longer practical
– Note: it is unfeasible, not impossible
• Cryptanalysis is the process of trying to work
out the encryption key from a given ciphertext.
– This type of attack exploits the characteristics of
the algorithm (cipher) to attempt to deduce a
specific plaintext or key
– Attacker will analyze the ciphertext using different
statistical tests – they must have prior knowledge
of the nature of plaintext (plain English, photo, exe
file etc.)
Cryptanalysis Techniques

Frequency Analysis
• Compute frequencies of letters in ciphertext
and compare with the typical frequencies in
the target language.
– e.g. in English texts, most frequent letters are
E (13%), T (9.1%), A (8.2%), O (7.5%)

• Can also find frequency of groups of letters

(di‑grams and tri‑grams): an, in, the
Cryptanalysis Techniques

Frequency Analysis Example 1

Plaintext
(English)

Ciphertext
Cryptanalysis Techniques

Frequency Analysis Example 2

UKBYBIPOUZBCUFEEBORUKBYBHOBBRFESPVKBWFOFERVNBCVBZPRUBOFERVNBCVBPCYY
FVUFOFEIKNWFRFIKJNUPWRFIPOUNVNIPUBRNCUKBEFWWFDNCHXCYBOHOPYXPUBNCU
BOYNRVNIWNCPOJIOFHOPZRVFZIXUBORJRUBZRBCHNCBBONCHRJZSFWNVRJRUBZRPCYZ
PUKBZPUNVPWPCYVFZIXUPUNFCPWRVNBCVBRPYYNUNFCPWWJUKBYBIPOUZBCUIPOUN
VNIPUBRNCHOPYXPUBNCUBOYNRVNIWNCPOJIOFHOPZRNCRVNBCUNENVVFZIXUNCHPCY
VFZIXUPUNFCPWZPUKBZPUNVR

B 3 🡺 E NC 11 🡺 IN UK 6 🡺 THE
6 PU 10 🡺 AT B
N 3 🡺 T UB 10 RV 6
4 N
🡺 A UN 9 Tri-gram
U 3 FZI 4
3 Di-gram s
s
P 3
2
Hardening the Substitution Cipher

• Monoalphabetic ciphers are easy to break because

they reflect the frequency data of the original
alphabet.
• One possible countermeasure is to provide multiple
substitutes, known as homophones , for a single
letter.
– e.g. letter e could be randomly assigned a number of
different cipher symbols, such as 16, 74, 35, and 21
• If the number of symbols assigned to each letter is
proportional to the relative frequency of that letter,
then single-letter frequency information is completely
obliterated.
• What about digram & trigram frequencies?
Hardening the Substitution Cipher

• To create a stronger cipher, we look into

polyalphabetic substitution
• Most well-known example: Vigenère Cipher
• Uses Caesar's cipher with various different
shifts, in order to hide the distribution of the
letters.
• A key defines the shifts used in each letter in
the text
Hardening the Substitution Cipher

Vigenère Cipher
• A key defines the shifts used in each letter in
the text
• The key word is repeated many times to
match the length of plaintext

Keyword = “BOX”
which translates to Ceaser shifts of “1, 14,
23”
plaintext I a t t a c k y o u
key 1 14 23 1 14 23 1 14 23 1
ciphertext J o q u o z l m l v
Cryptanalysis of Vigenère cipher

•
Cryptanalysis of Vigenère cipher

• If key length = 3 is known, attacker can split the

ciphertext in to 3 sections, and apply frequency
analysis on each section separately.

ciphertext J o q u o z l m l v
Section 1 J u l v
Section 2 o o m
Section 3 q z l
Cryptanalysis of Vigenère cipher

Vigenère Cipher – guessing the key length

• Find repeated strings in the ciphertext. Their distance
is expected to be a multiple of the key length.
Compute the gcd of (most) distances.
• Example:
Diagraph First Second Distance Factors
P. Text: TOBENOTORTOBE Position Position
Keyword: 1231231231231
C. Text: UQEFPRUQUUQEF
Cryptanalysis of Vigenère cipher

Vigenère Cipher – guessing the key length

• Find repeated strings in the ciphertext. Their distance
is expected to be a multiple of the key length.
Compute the gcd of (most) distances.
• Example:
Diagraph First Second Distance Factors
P. Text: TOBENOTORTOBE Position Position
Keyword: 1231231231231 UQ 1 7 6 3, 2
C. Text: UQEFPRUQUUQEF
UQ 7 10 3 3
Cryptanalysis of Vigenère cipher

Vigenère Cipher – guessing the key length

• Find repeated strings in the ciphertext. Their distance
is expected to be a multiple of the key length.
Compute the gcd of (most) distances.
• Example:
Diagraph First Second Distance Factors
P. Text: TOBENOTORTOBE Position Position
Keyword: 1231231231231 UQ 1 7 6 3, 2
C. Text: UQEFPRUQUUQEF
UQ 7 10 3 3

EF 3 12 9 3, 3
Cryptanalysis of Vigenère cipher

Vigenère Cipher – guessing the key length

• Find repeated strings in the ciphertext. Their distance
is expected to be a multiple of the key length.
Compute the gcd of (most) distances.
• Example:
Diagraph First Second Distance Factors
P. Text: TOBENOTORTOBE Position Position
Keyword: 1231231231231 UQ 1 7 6 3, 2
C. Text: UQEFPRUQUUQEF
UQ 7 10 3 3

EF 3 12 9 3, 3

More information and worked examples

QE 2 11 9 3, 3
https://crypto.interactive-maths.com/kasiski-
analysis-breaking-the-code.html
Hardening Vigenère Cipher

•
One-Time Pad (OTP)

https://www.cryptomuseum.com/crypto/otp/index.htm
One-Time Pad (OTP)

• To implement OTP, for each message use a random

key that is at least as long as the message itself.
• Combine the key with the plaintext (e.g. similar to
Vigenère cipher) to generate ciphertext.
• Each key is to be used to encrypt and decrypt a
single message, and then is discarded.
– Each new message requires a new key of the same length as
the message.
• Its name comes from the paper-pads on which
random key streams were printed.
– Two copies of each pad had to be created, one for sender
other for receiver.
– Each paper sheet was destroyed after use
OTP Strength

When applied correctly , the OTP provides a

truly unbreakable cipher.

How?
• It produces random output that bears no
statistical relationship to the plaintext.
• Ciphertext contains no information whatsoever
about the plaintext
OTP Practical or not?

OTP implementation rules are very strict. If any one of these rules is
violated, we no longer have the guarantee of unbreakability.
1. The OTP should consist of truly random characters (noise).
2. The OTP (i.e. the key) should have the same length as the plaintext (or
longer).
3. Only two copies of the OTP should exist.
4. The OTP should be used only once.
5. Both copies of the OTP are destroyed immediately after use.

In practice it is extremely challenging to

• Generate large amounts of truly random keys (millions
of characters)
• Securely distribute those random keys
OTP Practical or not?

To illustrate the impracticality of the OTP, consider a

simple example. Suppose Alice wants to send a 100 MB
file to Bob using the OTP. She must first generate a 100
MB random key, which she then uses to encrypt the 100
MB file to produce the ciphertext. This 100 MB key must
be securely transmitted to Bob before he can decrypt
the ciphertext. If Alice and Bob wish to communicate
regularly, they would need a new 100 MB key for each
message, resulting in an enormous amount of key data
that must be securely generated, stored, and
transmitted.
https://eitca.org/cybersecurity/eitc-is-ccf-classical-cryptography-fundamentals/stream-ciphers/stream-ciphers-and-linear
-feedback-shift-registers/examination-review-stream-ciphers-and-linear-feedback-shift-registers/what-are-the-limitations
-of-the-one-time-pad-and-why-is-it-considered-impractical-for-most-real-world-applications/
 Permutation (or
transposition) ciphers

changing order of characters in

plaintext
Railfence cipher

• The plaintext is written down as a sequence of

diagonals and then read off as a sequence of rows.
• e.g. to encipher the message “meet me after the
party” with a rail fence of depth 3, we write the
following

m m t h r
e t e f e t e a t
e a r p y
• The encrypted message is

mmthr etefeteat earpy

Railfence cipher

• The rail fence cipher is not very strong;

the number of practical keys is small
enough that a cryptanalyst can try them
all by hand.
Columnar transposition ciphers

• In this cipher, message is written in a grid row

by row, and read off column by column.
• In addition, order of columns is also
permuted. This order becomes the key of the
cipherMessage:
THIS IS TOP SECRET 3 2 4 1
T H I S
Key:
I S T O
3241
P S E C
Ciphertext: R E T
SOC HSSE TIPR ITET
key defines the order in which we read columns
Security of Permutation Ciphers

Question
• Are permutation ciphers susceptible to
frequency analysis?
Security of Permutation Ciphers

• A transposition cipher is easily recognized because it

has the same letter frequencies as the original
plaintext.
• For the columnar transposition just shown,
cryptanalysis is fairly straightforward and involves
laying out the ciphertext in a matrix and playing
around with column positions.

• The cipher can be made significantly more secure by

performing more than one stage of transposition (i.e.
by re-encryption the ciphertext)