CLASSICAL ENCRYPTION

TECHNIQUES

INFORMATION SECURITY
BS_CS 6TH 1
 MULTI-LEVEL SECURITY (MLS)

 There are security classifications or security levels

 Users/principals/subjects have security clearances
 Objects have security classifications
 Example of security levels
 Top Secret
 Secret
 Confidential
 Unclassified
 In this case Top Secret > Secret > Confidential > Unclassified
 Security goal (confidentiality): ensures that information do not flow
to those not cleared for that level
2
MULTI-LEVEL SECURITY (MLS)

 The capability of a computer system to carry information

with different sensitivities (i.e. classified information at
different security levels), permit simultaneous access by
users with different security clearances and needs-to-know,
and prevent users from obtaining access to information for
which they lack authorization.
 Discretionary access control fails to achieve MLS

 Typically use Mandatory Access Control

 Primary Security Goal: Confidentiality
3
MANDATORY ACCESS CONTROL(MAC)

 Mandatory access controls (MAC) restrict the

access of subjects to objects based on a
system-wide policy
 Denying users full control over the access to
resources that they create. The system security
policy (as set by the administrator) entirely
determines the access rights granted

4
WHAT IS A SECURITY MODEL?

 A model describes the system

 e.g., a high level specification or an abstract machine
description of what the system does
 A security policy
 defines the security requirements for a given system

 Verification techniques that can be used to show that

a policy is satisfied by a system
 System Model + Security Policy = Security Model
5
 BELL-LAPADULA MODEL(BLP): A MAC MODEL
FOR ACHIEVING MULTI-LEVEL SECURITY

 Introduce in 1973
 Air-Force was concerned with security in time-sharing systems
 Many OS bugs
 Accidental misuse
 Main Objective:
 Enable one to formally show that a computer system can securely process classified
information

6
 THE BLP SECURITY MODEL

 A computer system is modeled as a state-transition system

 There is a set of subjects; some are designated as trusted.
 Each state has objects, an access matrix, and the current access
information.
 There are state transition rules describing how a system can go from
one state to another
 Each subject s has a maximal sec level Lm(s), and a current sec level Lc(s)
 Each object has a classification level

7
 ELEMENTS OF THE BLP MODEL
Lm: Max Lc: Current L: Class.
Sec. Level Sec. Level Level

Subjects Objects
Current
Accesses
Trusted
Subjects

Access Matrix 8

Security levels, e.g.: {TS, S, C, U}

CLASSICAL ENCRYPTION TECHNIQUES

 As opposed to modern cryptography

 Goals:
 to introduce basic concepts & terminology of encryption
 to prepare us for studying modern cryptography

9
BASIC TERMINOLOGY

 Plaintext: original message to be encrypted

 Ciphertext: the encrypted message

 Enciphering or encryption: the process of converting plaintext into ciphertext

 Encryption algorithm: performs encryption

 Two inputs: a plaintext and a secret key

10
 Deciphering or decryption: recovering plaintext from ciphertext

 Decryption algorithm: performs decryption

 Two inputs: ciphertext and secret key

 Secret key: same key used for encryption and decryption

 Also referred to as a symmetric key

11
 Cipher or cryptographic system : a scheme for encryption and decryption

 Cryptography: science of studying ciphers

 Cryptanalysis: science of studying attacks against cryptographic systems

 Cryptology: cryptography + cryptanalysis

12
 Cryptography
Basics

 Cryptography is the science of secret, or hidden

writing
 It has two main Components:
1. Encryption
– Practice of hiding messages so that they can not be read by
anyone other than the intended recipient
2. Authentication & Integrity
– Ensuring that users of data/resources are the persons they claim
to be and that a message has not been surreptitiously altered
CIPHERS
 Symmetric cipher: same key used for encryption
and decryption
 Block cipher: encrypts a block of plaintext at a time
(typically 64 or 128 bits)

 Stream cipher: encrypts data one bit or one byte at a

time

 Asymmetric cipher: different keys used for

encryption and decryption 14
 Encryption
Symmetric Algorithms

 Algorithms in which the key for encryption and

decryption are the same are Symmetric
 Example: Caesar Cipher
 Types:
1. Block Ciphers
– Encrypt data one block at a time (typically 64 bits, or 128 bits)
– Used for a single message
2. Stream Ciphers
– Encrypt data one bit or one byte at a time
– Used if data is a constant stream of information
SYMMETRIC ENCRYPTION

 or conventional / secret-key / single-key

 sender and recipient share a common key
 all classical encryption algorithms are symmetric
 The only type of ciphers prior to the invention of asymmetric-key ciphers in
1970’s
 by far most widely used

16
 Encryption
Cipher

Plain Text Encryption Cipher Text Decryption Plain Text

Algorithm Algorithm

 Cipher is a method for encrypting messages

Key A Key B

 Encryption algorithms are standardized & published

 The key which is an input to the algorithm is secret
 Key is a string of numbers or characters
 If same key is used for encryption & decryption the algorithm is called symmetric
 If different keys are used for encryption & decryption the algorithm is called asymmetric
Symmetric Encryption
Key Strength

 Strength of algorithm is determined by the size of the key

 The longer the key the more difficult it is to crack
 Key length is expressed in bits
 Typical key sizes vary between 48 bits and 448 bits
 Set of possible keys for a cipher is called key space
 For 40-bit key there are 240 possible keys
 For 128-bit key there are 2128 possible keys
 Each additional bit added to the key length doubles the security
 To crack the key the hacker has to use brute-force
(i.e. try all the possible keys till a key that works is found)
 Super Computer can crack a 56-bit key in 24 hours
 It will take 272 times longer to crack a 128-bit key
(Longer than the age of the universe)
SYMMETRIC CIPHER MODEL

19
 SYMMETRIC ENCRYPTION

 Mathematically:
Y = EK(X) or Y = E(K, X)
X = DK(Y) or X = D(K, Y)
 X = plaintext
 Y = ciphertext
 K = secret key
 E = encryption algorithm
 D = decryption algorithm
 Both E and D are known to public

20
 Secure Communication
Needs and Requirements

 Well-established needs for secure communication

 Wartime communication
 Business transactions
 Illicit Love Affairs
 Requirements of secure communication
1. Secrecy
– Only the intended receiver understands the message
2. Authentication
– Sender and receiver need to confirm each other’s identity
3. Message Integrity
– Ensure that their communication has not been altered, either maliciously or by
accident during transmission
CRYPTANALYSIS

 Objective: to recover the plaintext of a ciphertext or,

more typically, to recover the secret key.
 Kerkhoff’s principle: the adversary knows all details
about a cryptosystem except the secret key.

 Two general approaches:

 brute-force attack
 non-brute-force attack (cryptanalytic attack)

22
BRUTE-FORCE ATTACK
 On average, need to try half of all possible keys
 Time needed proportional to size of key space

 Try every key to decipher the ciphertext.

Key Size (bits) Number of Alternative Time required at 1 Time required at 106
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 years 5.4  1018 years

168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years

26 characters 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years
(permutation) 23
BRUTE-FORCE ATTACK

 A brute force attack is a hacking method that uses trial

and error to crack passwords, login credentials, and
encryption keys. It is a simple yet reliable tactic for
gaining unauthorized access to individual accounts and
organizations’ systems and networks.
 The hacker tries multiple usernames and passwords,
often using a computer to test a wide range of
combinations, until they find the correct login
information.

24
BRUTE-FORCE ATTACK

 The name "brute force" comes from attackers

using excessively forceful attempts to gain
access to user accounts. Despite being an old
cyberattack method, brute force attacks are
tried and tested and remain a popular tactic
with hackers.

25
SIMPLE BRUTE FORCE ATTACKS

 A simple brute force attack occurs when a hacker attempts to

guess a user’s login credentials manually without using any
software. This is typically through standard password
combinations or personal identification number (PIN) codes.
 These attacks are simple because many people still use weak
passwords, such as "password123" or "1234," or practice poor
password etiquette, such as using the same password for multiple
websites. Passwords can also be guessed by hackers that do
minimal reconnaissance work to crack an individual's potential
password, such as the name of their favorite sports team.

26
DICTIONARY ATTACKS

 A dictionary attack is a basic form of brute force hacking in which

the attacker selects a target, then tests possible passwords against
that individual’s username. The attack method itself is not
technically considered a brute force attack, but it can play an
important role in a bad actor’s password-cracking process.
 The name "dictionary attack" comes from hackers running
through dictionaries and amending words with special characters
and numbers. This type of attack is typically time-consuming and
has a low chance of success compared to newer, more effective
attack methods.

27
HYBRID BRUTE FORCE ATTACKS

 A hybrid brute force attack is when a hacker combines a

dictionary attack method with a simple brute force attack. It
begins with the hacker knowing a username, then carrying out a
dictionary attack and simple brute force methods to discover an
account login combination.
 The attacker starts with a list of potential words, then
experiments with character, letter, and number combinations to
find the correct password. This approach allows hackers to
discover passwords that combine common or popular words with
numbers, years, or random characters, such as "SanDiego123" or
"Rover2020."

28
REVERSE BRUTE FORCE ATTACKS

 A reverse brute force attack sees an attacker begin

the process with a known password, which is
typically discovered through a network breach. They
use that password to search for a matching login
credential using lists of millions of usernames.
 Attackers may also use a commonly used weak
password, such as "Password123," to search
through a database of usernames for a match.
29
CREDENTIAL STUFFING

 Credential stuffing preys on users’ weak password

etiquettes. Attackers collect username and
password combinations they have stolen, which
they then test on other websites to see if they can
gain access to additional user accounts. This
approach is successful if people use the same
username and password combination or reuse
passwords for various accounts and social media
profiles.
30
CRYPTANALYTIC ATTACKS

 May be classified by how much information needed

by the attacker:
 Ciphertext-only attack

 Known-plaintext attack

 Chosen-plaintext attack

 Chosen-ciphertext attack
31
CIPHERTEXT-ONLY ATTACK

 Given: a ciphertext c
 Q: what is the plaintext m?
 An encryption scheme is completely insecure if it
cannot resist ciphertext-only attacks.

32
KNOWN-PLAINTEXT ATTACK

 Given: (m1,c1), (m2,c2), …, (mk,ck) and a new

ciphertext c.

 Q: what is the plaintext of c?

 Q: what is the secret key in use?

33
CHOSEN-PLAINTEXT ATTACK

 Given: (m1,c1), (m2,c2), …, (mk,ck), where m1,m2, …, mk are chosen by the

adversary; and a new ciphertext c.

 Q: what is the plaintext of c, or what is the secret key?

34
EXAMPLE: CHOSEN-PLAINTEXT ATTACK

 In 1942, US Navy cryptanalysts discovered that Japan was

planning an attack on “AF”.
 They believed that “AF” means Midway island.
 Pentagon didn’t think so.
 US forces in Midway sent a plain message that their
freshwater supplies were low.
 Shortly, US intercepted a Japanese ciphertext saying that
“AF” was low on water.
 This proved that “AF” is Midway. 35
CHOSEN-CIPHERTEXT ATTACK

 Given: (m1,c1), (m2,c2), …, (mk,ck), where c1,c2, …, ck are chosen by the

adversary; and a new ciphertext c.

 Q: what is the plaintext of c, or what is the secret key?

36
CLASSICAL CIPHERS

 Plaintext is viewed as a sequence of elements (e.g.,

bits or characters)
 Substitution cipher: replacing each element of the
plaintext with another element.
 Transposition (or permutation) cipher: rearranging
the order of the elements of the plaintext.
 Product cipher: using multiple stages of
substitutions and transpositions
37
 CAESAR CIPHER

 Earliest known substitution cipher

 Invented by Julius Caesar
 Each letter is replaced by the letter three positions further down the alphabet.
• Plain: 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
Cipher: 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
 Example: ohio state → RKLR VWDWH

38
CAESAR CIPHER
 Mathematically, map letters to numbers:
a, b, c, ..., x, y, z
0, 1, 2, ..., 23, 24, 25
 Then the general Caesar cipher is:
c = EK(p) = (p + k) mod 26
p = DK(c) = (c – k) mod 26
 Can be generalized with any alphabet.

39
 Substitution Ciphers
Caesar Cipher

 Caesar Cipher is a method in which each letter in the alphabet is rotated by

three letters as shown
ABCDEFGHIJKLMNOPQRSTUVWXYZ

DEFGHIJKLMNOPQRSTUVWXYZABC

• Let us try to encrypt the message

– Attack at Dawn
Assignment: Each student will exchange a secret message with
his/her closest neighbor about some other person in the class
and the neighbor will decipher it.
 Substitution Ciphers
Caesar Cipher
Encryption
Plain Text Cipher Text
Cipher:
Message: Caesar Cipher Message:
Attack at Dawn Algorithm Dwwdfn Dw Gdyq

Decryption
Key (3)

Cipher Text Plain Text

Cipher:
Message: Caesar Cipher Message:
Dwwdfn Dw Gdyq Algorithm Attack at Dawn

Key (3)
How many different keys are possible?
CRYPTANALYSIS OF CAESAR CIPHER

 Key space: {0, 1, ..., 25}

 Vulnerable to brute-force attacks.
 E.g., break ciphertext "UNOU YZGZK“

 Need to recognize it when have the plaintext

 What if the plaintext is written in Swahili?

42
 MONO-ALPHABETIC SUBSTITUTION CIPHER
 Shuffle the letters and map each plaintext letter to a
different random ciphertext letter:

Plain letters: abcdefghijklmnopqrstuvwxyz

Cipher letters: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

 What does a key look like?

43
MONO-ALPHABETIC CIPHER SECURITY

 Now we have a total of 26! = 4 x 1026 keys.

 With so many keys, it is secure against brute-force attacks.

 But not secure against some cryptanalytic attacks.

 Problem is language characteristics.

44
 Mono-alphabetic Cipher Security

ABCDEFGH I JKLMNOPQRSTUVWXYZ

MNBVCXZASDFGHJ KLPO IUYTREWQ

 Any letter can be substituted for any other letter
 Each letter has to have a unique substitute
 There are 26! pairing of letters (~1026)
 The Brute Force approach would be too time-consuming
 Statistical Analysis would make it feasible to crack the key
Message: Encrypted
Cipher: Message:
Bob, I love you. Monoalphabetic Nkn, s gktc wky.
Alice Cipher mgsbc

Key
LANGUAGE STATISTICS AND
CRYPTANALYSIS
 Human languages are not random.

 Letters are not equally frequently used.

 In English, E is by far the most common letter, followed by T,

R, N, I, O, A, S.

 Other letters like Z, J, K, Q, X are fairly rare.

 There are tables of single, double & triple letter frequencies

for various languages

46
ENGLISH LETTER FREQUENCIES

47
STATISTICS FOR DOUBLE & TRIPLE LETTERS

 In decreasing order of frequency

 Double letters:
th he an in er re es on, …

 Triple letters:
the and ent ion tio for nde, …

48
USE IN CRYPTANALYSIS

 Key concept: monoalphabetic substitution does not

change relative letter frequencies

 To attack, we
 calculate letter frequencies for ciphertext
 compare this distribution against the known one

49
EXAMPLE CRYPTANALYSIS

 Given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

 Count relative letter frequencies (see next page)

 Guess {P, Z} = {e, t}
 Of double letters, ZW has highest frequency, so guess ZW = th and
hence ZWP = 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

50
LETTER FREQUENCIES IN CIPHERTEXT

P 13.33 H 5.83 F 3.33 B 1.67 C 0.00

Z 11.67 D 5.00 W 3.33 G 1.67 K 0.00
S 8.33 E 5.00 Q 2.50 Y 1.67 L 0.00
U 8.33 V 4.17 T 2.50 I 0.83 N 0.00
O 7.50 X 4.17 A 1.67 J 0.83 R 0.00
M 6.67

51