Cryptography:

 Cryptography (or cryptology; derived from Greek κρυπτός kryptós "hidden," and the verb γράφω
gráfo "write") is the study of message secrecy. In modern times, it has become a branch of
information theory, as the mathematical study of information and especially its transmission from
place to place.
 The art of protecting information by transforming it (encrypting it) into an unreadable format, called
cipher text. Only those who possess a secret key can decipher (or decrypt) the message into plain text.
 Encrypted messages can sometimes be broken by cryptanalysis, also called codebreaking, although
modern cryptography techniques are virtually unbreakable.
 One of cryptography's primary purposes is hiding the meaning of messages, not usually the existence
of such messages. Cryptography also contributes to computer science, central to the techniques used
in computer and network security for such things as access control and information confidentiality.
 Cryptography is also used in many applications encountered in everyday life; the security of ATM
cards, computer passwords, and electronic commerce all depend on cryptography.
 As the Internet and other forms of electronic communication become more prevalent, electronic
security is becoming increasingly important. Cryptography is used to protect e-mail messages, credit
card information, and corporate data.
 Information Security requirements have changed in recent times
 traditionally provided by physical and administrative mechanisms
 computer use requires automated tools to protect files and other stored information
 use of networks and communications links requires measures to protect data during transmission
Some 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 ciphertext from plaintext
 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
Definitions:

• Computer Security - generic name for the collection of tools designed to protect data and to thwart hackers

• Network Security - measures to protect data during their transmission

• Internet Security - measures to protect data during their transmission over a collection of interconnected networks

Aim of Course:

• our focus is on Internet Security

• which consists of measures to deter, prevent, detect, and correct security violations that involve the transmission &
storage of information

OSI Security Architecture:

 • ITU-T X.800 “Security Architecture for OSI”

• defines a systematic way of defining and providing security requirements

• for us it provides a useful, if abstract, overview of concepts we will study

ITU-T X.800 Aspects of Security

• consider 3 aspects of information security:

– security attack

– security mechanism

– security service

• Security Attack

Any action that compromises the security of information.

• Security Mechanism

A mechanism that is designed to detect, prevent, or recover from a security attack.

• Security Service

A service that enhances the security of data processing systems and information transfers. A security service makes
use of one or more security mechanisms.

Security Attack:

• any action that compromises the security of information owned by an organization

• information security is about how to prevent attacks, or failing that, to detect attacks on information-based systems

• often threat & attack used to mean same thing

• have a wide range of attacks

• can focus of generic types of attacks

– passive

– active
Passive Attacks:

Active Attacks:

Security Attacks:

• Interruption:

This is an attack on availability

• Interception:

This is an attack on confidentiality

• Modification:

This is an attack on integrity

• Fabrication:

This is an attack on authenticity

Security Attacks:
Security Goals:

Cryptanalysis:

• objective to recover key not just message

• general approaches:

– cryptanalytic attack

– brute-force attack

Cryptanalytic Attacks:

• ciphertext only

– only know algorithm & ciphertext, is statistical, know or can identify plaintext

• known plaintext

– know/suspect plaintext & ciphertext

 • chosen plaintext

– select plaintext and obtain ciphertext

• chosen ciphertext

– select ciphertext and obtain plaintext

• chosen text

– select plaintext or ciphertext to en/decrypt

More Definitions:

• unconditional security

– no matter how much computer power or time is available, the cipher cannot be broken since the ciphertext
provides insufficient information to uniquely determine the corresponding plaintext

• computational security

– given limited computing resources (eg time needed for calculations is greater than age of universe), the
cipher cannot be broken

Brute Force Search:

• always possible to simply try every key

• most basic attack, proportional to key size

• assume either know / recognise plaintext

Security Service:

– enhance security of data processing systems and information transfers of an organization

– intended to counter security attacks

– using one or more security mechanisms

– often replicates functions normally associated with physical documents

• which, for example, have signatures, dates; need protection from disclosure, tampering, or
destruction; be notarized or witnessed; be recorded or licensed

Security Services:

• X.800:
“a service provided by a protocol layer of communicating open systems, which ensures adequate security of the systems or of
data transfers”

• RFC 2828:

“a processing or communication service provided by a system to give a specific kind of protection to system resources”

Security Services:

• Confidentiality

Privacy

Reading by authorized parties

• Authentication

Who created or sent the data,

Origin of a message be correctly identified

• Integrity

Data has not been altered

Modification only by authorized parties

• Non-repudiation

The order is final

Neither the sender nor the receiver of a message be able

to deny the transmission

• Access Control

Prevent misuse of resources

Access to information resources be controlled

• Availability (permanence, non-erasure)

Denial of Service Attacks

Virus that deletes files

Security Mechanism:

• feature designed to detect, prevent, or recover from a security attack

• no single mechanism that will support all services required

• however one particular element underlies many of the security mechanisms in use:

– cryptographic techniques

• hence our focus on this topic

Security Mechanisms (X.800):

 • Specific security mechanisms:

– May be incorporated into the appropriate protocol layer in order to provide some of the OSI security
services.

• encipherment, digital signatures, access controls, data integrity, authentication exchange, traffic
padding, routing control, notarization

• Pervasive security mechanisms:

– Mechanisms that are not specific to any OSI security service or protocol layer

• trusted functionality, security labels, event detection, security audit trails, security recovery

Model for Network Security:

• using this model requires us to:

1. design a suitable algorithm for the security transformation

2. generate the secret information (keys) used by the algorithm

3. develop methods to distribute and share the secret information

4. specify a protocol enabling the principals to use the transformation and secret information for a security
service

Model for Network Access Security:

• using this model requires us to:

1. select appropriate gatekeeper functions to identify users

2. implement security controls to ensure only authorised users access designated information or resources
 • trusted computer systems may be useful to help implement this model

Classical Substitution Ciphers

• 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

Caesar Cipher:

• earliest known substitution cipher

• by Julius Caesar

• first attested use in military affairs

• replaces each letter by 3rd letter on

• example:

meet me after the toga party

PHHW PH DIWHU WKH WRJD SDUWB

• can define transformation as:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

DEFGHIJKLMNOPQRSTUVWXYZABC

• mathematically give each letter a number

• then have Caesar cipher as:

c = E(p) = (p + k) mod (26)

p = D(c) = (c – k) mod (26)

Class Activity:

• Write a program in any programming Language, that convert,

• Pi = “a quick brown fox jumps over a lazy dog, which was fast a sleep”

• K = k ( 0 < k <26)

• And

• Ci = Ek(Pi) = (P + k) mod 26

• Display the result on Screen

Cryptanalysis of Caesar Cipher:

• only have 26 possible ciphers

– A maps to A,B,..Z
 • could simply try each in turn

• a brute force search

• given ciphertext, just try all shifts of letters

• do need to recognize when have plaintext

• eg. 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, might think is secure

• but would be !!!WRONG!!!

• problem is language characteristics

Language Redundancy and Cryptanalysis:

• human languages are redundant

• eg "th 1st s m shphrd shll nt wnt"

• letters are not equally commonly 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

• have tables of single, double & triple letter frequencies for various languages

English Letter Frequencies:

Use in Cryptanalysis :

• key concept - monoalphabetic substitution ciphers do not change relative letter frequencies

• discovered by Arabian scientists in 9th century

• calculate letter frequencies for 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 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

Playfair Cipher:
 • not even the large number of keys in a monoalphabetic cipher provides security

• one approach to improving security was to encrypt multiple letters

• the Playfair Cipher is an example

• invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair

• https://www.youtube.com/watch?v=QXGYOh2Mgrw

Playfair Key Matrix:

• a 5X5 matrix of letters based on a keyword

• fill in letters of keyword (sans duplicates)

• fill rest of matrix with other letters

• eg. using the keyword MONARCHY

M O N A R

C H Y B D

E F G I/J K

L P Q S T

U V W X Z

Encrypting and Decrypting:

• plaintext is encrypted two letters at a time

1. if a pair is a repeated letter, insert filler like 'X’

2. if both letters fall in the same row, replace each with letter to right (wrapping back to start from end)

3. if both letters fall in the same column, replace each with the letter below it (again wrapping to top from
bottom)

4. otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the
pair

Security of Playfair Cipher:

• security much improved over monoalphabetic

• since have 26 x 26 = 676 digrams

• would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic)

• and correspondingly more ciphertext

• was widely used for many years

 – eg. by US & British military in WW1

• it can be broken, given a few hundred letters

• since still has much of plaintext structure

Polyalphabetic Ciphers:

• polyalphabetic substitution ciphers

• improve security using multiple cipher alphabets

• make cryptanalysis harder with more alphabets to guess and 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 start after end of key is reached

Vigenère Cipher:

• simplest polyalphabetic substitution cipher

• effectively multiple caesar ciphers

• key is multiple letters long K = k1 k2 ... kd

• ith letter specifies ith alphabet to use

• use each alphabet in turn

• repeat from start after d letters in message

• decryption simply works in reverse

Example of Vigenère Cipher:

• 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

Aids:

• simple aids can assist with en/decryption

• a Saint-Cyr Slide is a simple manual aid

 – a slide with repeated alphabet

– line up plaintext 'A' with key letter, eg 'C'

– then read off any mapping for key letter

• can bend round into a cipher disk

• or expand into a Vigenère Tableau

Security of Vigenère Ciphers:

• have multiple ciphertext letters for each plaintext letter

• hence letter frequencies are obscured

• but not totally lost

• start with letter frequencies

– see if look monoalphabetic or not

• if not, then need to determine number of alphabets, since then can attach each

Kasiski Method:

• method developed by Babbage / Kasiski

• repetitions in ciphertext give clues to period

• so find same plaintext an exact period apart

• which results in the same ciphertext

• of course, could also be random fluke

• eg repeated “VTW” in previous example

• suggests size of 3 or 9

• then attack each monoalphabetic cipher individually using same techniques as before

Autokey Cipher:

• ideally want a key as long as the message

• Vigenère proposed the autokey cipher

• with keyword is prefixed to message as key

• knowing keyword can recover the first few letters

• use these in turn on the rest of the message

• but still have frequency characteristics to attack

• eg. given key deceptive

key: deceptivewearediscoveredsav

plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA

One-Time Pad:

• if a truly random key as long as the message is used, the cipher will be secure

• called a One-Time pad

• is unbreakable since 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

• problems in generation & safe distribution of key

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

Rail Fence cipher:

• write message letters out diagonally over a number of rows

• then read off cipher row by row

• eg. write message out as:

mematrhtgpry

etefeteoaat

• giving ciphertext

MEMATRHTGPRYETEFETEOAAT

• Row Transposition Ciphers:

a more complex transposition

• write letters of message out in rows over a specified number of columns

• then reorder the columns according to some key before reading off the rows

Key: 3421567

Plaintext: a t t a c k p

ostpone

duntilt

woamxyz

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
Product Ciphers:

• ciphers using substitutions or transpositions are not secure because of language characteristics

• hence consider using several ciphers in succession to make harder, but:

– two substitutions make a more complex substitution

– two transpositions make more complex transposition

– but a substitution followed by a transposition makes a new much harder cipher

• this is bridge from classical to modern ciphers

Rotor Machines:

• before modern ciphers, rotor machines were most common complex ciphers in use

• widely used in WW2

– German Enigma, Allied Hagelin, Japanese Purple

• implemented a very complex, varying substitution cipher

• used a series of cylinders, each giving one substitution, which rotated and changed after each letter was encrypted

• with 3 cylinders have 263=17576 alphabets

Hagelin Rotor Machine:

Steganography

• an alternative to encryption

• hides existence of message

– using only a subset of letters/words in a longer message marked in some way

– using invisible ink

– hiding in LSB in graphic image or sound file

• has drawbacks

– high overhead to hide relatively few info bits

Summary:

• have considered:
 – classical cipher techniques and terminology

– monoalphabetic substitution ciphers

– cryptanalysis using letter frequencies

– Playfair cipher

– polyalphabetic ciphers

– transposition ciphers

– product ciphers and rotor machines

– stenography

Types of Cryptography:

• Symmetric key Cryptography

• Asymmetric key Cryptography

• Hash Functions

Symmetric Encryption:

• or conventional / private-key / single-key

• sender and recipient share a common key

• all classical encryption algorithms are private-key

• was only type prior to invention of public-key in 1970’s

• and by far most widely used

Symmetric Cipher Model:

• With secret key cryptography, a single key is used for both encryption and decryption. As shown in Figure 1A, the
sender uses the key (or some set of rules) to encrypt the plaintext and sends the ciphertext to the receiver. The
receiver applies the same key (or ruleset) to decrypt the message and recover the plaintext. Because a single key is
used for both functions, secret key cryptography is also called symmetric encryption.

• With this form of cryptography, it is obvious that the key must be known to both the sender and the receiver; that,
in fact, is the secret.

• The biggest difficulty with this approach, of course, is the distribution of the key.

Symmetric (Private Key) Cryptography:

• Examples: DES, RC4, RC5, IDEA, Skipjack

• Advantages: fast, ciphertext secure

• Disadvantages: must distribute key in advance, key must not be divulged

ciphertext = encrypt( plaintext, key )

plaintext = decrypt( ciphertext, key

Attacks on symmetric ciphers:

• Symmetric ciphers have historically been susceptible to known-plaintext attacks, chosen plaintext attacks,
differential cryptanalysis and linear cryptanalysis.

• Careful construction of the functions for each round can greatly reduce the chances of a successful attack.

• When used with asymmetric ciphers for key transfer, pseudorandom key generators are nearly always used to
generate the symmetric cipher session keys.

• However, lack of randomness in those generators or in their initialization vectors is disastrous and has led to
cryptanalytic breaks in the past. Very careful implementation and deployment, with initialization based on high
quality sources of entropy, is essential lest security be lost.

Research Work:
 • Find out the cryptanalysis techniques by which we can crack symmetric key cryptography.

• Note:

– Your wordings must be supported by one or two research papers.

Research Activity
End Time(7:00 PM)

• You have been given a task to Encrypt a document, using Symmetric key algorithm i.e. RC4, used in early versions of
MS Word,

1. Send the encrypted document to the recipient

2. How will you share the key

• Give Solid statements, supported by the IEEE/ACM research articles

Public-Key Cryptography:

• probably most significant advance in the 3000 year history of cryptography

• uses two keys – a public & a private key

• asymmetric since parties are not equal

• uses clever application of number theoretic concepts to function

• complements rather than replaces private key crypto

Why Public-Key Cryptography?

• developed to address two key issues:

– key distribution – how to have secure communications in general without having to trust a KDC with your
key

– digital signatures – how to verify a message comes intact from the claimed sender

• public invention due to Whitfield Diffie & Martin Hellman at Stanford Uni in 1976

– known earlier in classified community

• public-key/two-key/asymmetric cryptography involves the use of two keys:

– a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures

– a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures

• is asymmetric because

– those who encrypt messages or verify signatures cannot decrypt messages or create signatures

Public-Key Cryptography:
Public-Key Characteristics:

• Public-Key algorithms rely on two keys where:

– it is computationally infeasible to find decryption key knowing only algorithm & encryption key

– it is computationally easy to en/decrypt messages when the relevant (en/decrypt) key is known

– either of the two related keys can be used for encryption, with the other used for decryption (for some
algorithms)

Public-Key Cryptosystems:

Public-Key Cryptosystems:

Public-Key Applications:

• can classify uses into 3 categories:

– encryption/decryption (provide secrecy)

– digital signatures (provide authentication)

– key exchange (of session keys)

• some algorithms are suitable for all uses, others are specific to one
Security of Public Key Schemes:

• like private key schemes brute force exhaustive search attack is always theoretically possible

• but keys used are too large (>512bits)

• security relies on a large enough difference in difficulty between easy (en/decrypt) and hard (cryptanalyse)
problems

• more generally the hard problem is known, but is made hard enough to be impractical to break

• requires the use of very large numbers

• hence is slow compared to private key schemes

Confusion and Diffusion:

• cipher needs to completely obscure statistical properties of original message

• a one-time pad does this

• more practically Shannon suggested combining S & P elements to obtain:

• diffusion – dissipates statistical structure of plaintext over bulk of ciphertext

• confusion – makes relationship between ciphertext and key as complex as possible

• confusion refers to making the relationship between the key and the ciphertext as complex and involved as possible;
diffusion refers to the property that redundancy in the statistics of the plaintext is "dissipated" in the statistics of the
ciphertext.

• http://en.wikipedia.org/wiki/Confusion_and_diffusion

Hash algorithm:

• A hash function (or hash algorithm) is a reproducible method of turning data (usually a message or a file) into a
number suitable to be handled by a computer. These functions provide a way of creating a small digital "fingerprint"
from any kind of data. The function chops and mixes (i.e., substitutes or transposes) the data to create the
fingerprint, often called a hash value.

• The hash value is commonly represented in hexadecimal notation. A good hash function is one that yields few hash
collisions in expected input domains. In hash tables and data processing, collisions inhibit the distinguishing of data,
making records more costly to find.

• In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make
it suitable for use as a primitive in various information security applications, such as authentication and message
integrity. A hash function takes a long string (or 'message') of any length as input and produces a fixed length string
as output, sometimes termed a message digest or a digital fingerprint.

• In various standards and applications, the two most-commonly used hash functions are MD5 and SHA-1.

• In 2005, security flaws were identified in both algorithms

Ciphering Mechanisms:

• Stream cipher

• Block cipher

Stream cipher:

• In cryptography, a stream cipher is a symmetric cipher in which the plaintext digits are encrypted one at a time,
and in which the transformation of successive digits varies during the encryption.

• An alternative name is a state cipher, as the encryption of each digit is dependent on the current state. In
practice, the digits are typically single bits or bytes.

Types of stream cipher:

• Synchronous stream ciphers

• Self-synchronizing stream ciphers

• Linear feedback shift register-based stream ciphers

• Non-linear combining functions

• Clock-controlled generators

• Filter generator

Security:

• To be secure, the period of the keystream, that is, the number of digits output before the stream repeats itself,
needs to be sufficiently large. If the sequence repeats, then the overlapping ciphertexts can be aligned against
each other "in depth", and there are techniques which could allow the plaintext to be extracted

• However, for most choices of this parameter, the resulting stream had a period of only 2 32 — for many
applications, this period is far too low. For example, if encryption is being performed at a rate of 1 megabyte per
second, a stream of period 232 will repeat after around 8.5 minutes.
Usage:

• Stream ciphers are often used in applications where plaintext comes in quantities of unknowable length—for
example, a secure wireless connection

• nother advantage of stream ciphers in military cryptography is that the cipher stream can be generated in a
separate box that is subject to strict security measures and fed to other devices, e.g. a radio set, which will
perform the xor operation as part of their function. The latter device can then be designed and used in less
stringent environments.

• RC4 is the most widely used stream cipher in software; others include: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC,
MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 and WAKE. Comparison ….?

• http://en.wikipedia.org/wiki/Stream_cipher

Block cipher:

• In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed
blocks, with an unvarying transformation. When encrypting, a block cipher might take a (for example) 128-bit block
of plaintext as input, and output a corresponding 128-bit block of ciphertext.

• The exact transformation is controlled using a second input — the secret key. Decryption is similar: the decryption
algorithm takes, in this example, a 128-bit block of ciphertext together with the secret key, and yields the original
128-bit block of plaintext.

• An early and highly influential block cipher design was the Data Encryption Standard (DES), developed at IBM and
published as a standard in 1977.

• A successor to DES, the Advanced Encryption Standard (AES), was adopted in

Examples:

• Algorithms: 3-Way | AES | Akelarre | Anubis | ARIA | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 |
CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CMEA | Cobra | COCONUT98 | Crab | CS-Cipher | DEAL | DES |
DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA
NXT | Iraqi | Intel Cascade Cipher | KASUMI | KHAZAD | Khufu and Khafre | KN-Cipher | Libelle | LOKI89/91 |
LOKI97 | Lucifer | M6 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 |
NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent |
SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | UES | Xenon | xmx | XTEA | Zodiac

• http://en.wikipedia.org/wiki/Block_cipher

Hash algorithm:
• A hash function (or hash algorithm) is a reproducible method of turning data (usually a message or a file) into a
number suitable to be handled by a computer. These functions provide a way of creating a small digital "fingerprint"
from any kind of data. The function chops and mixes (i.e., substitutes or transposes) the data to create the
fingerprint, often called a hash value.

• The hash value is commonly represented in hexadecimal notation. A good hash function is one that yields few hash
collisions in expected input domains. In hash tables and data processing, collisions inhibit the distinguishing of data,
making records more costly to find.

• In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make
it suitable for use as a primitive in various information security applications, such as authentication and message
integrity. A hash function takes a long string (or 'message') of any length as input and produces a fixed length string
as output, sometimes termed a message digest or a digital fingerprint.

• In various standards and applications, the two most-commonly used hash functions are MD5 and SHA-1.

• In 2005, security flaws were identified in both algorithms

Ciphering Mechanisms:

• Stream cipher

• Block cipher

Stream cipher:

• In cryptography, a stream cipher is a symmetric cipher in which the plaintext digits are encrypted one at a time,
and in which the transformation of successive digits varies during the encryption.

• An alternative name is a state cipher, as the encryption of each digit is dependent on the current state. In
practice, the digits are typically single bits or bytes.

Types of stream cipher:

• Synchronous stream ciphers

• Self-synchronizing stream ciphers

• Linear feedback shift register-based stream ciphers

• Non-linear combining functions

• Clock-controlled generators

• Filter generator

Security:
 • To be secure, the period of the keystream, that is, the number of digits output before the stream repeats itself,
needs to be sufficiently large. If the sequence repeats, then the overlapping ciphertexts can be aligned against
each other "in depth", and there are techniques which could allow the plaintext to be extracted

• However, for most choices of this parameter, the resulting stream had a period of only 2 32 — for many
applications, this period is far too low. For example, if encryption is being performed at a rate of 1 megabyte per
second, a stream of period 232 will repeat after around 8.5 minutes.

Usage:

• Stream ciphers are often used in applications where plaintext comes in quantities of unknowable length—for
example, a secure wireless connection

• Another advantage of stream ciphers in military cryptography is that the cipher stream can be generated in a
separate box that is subject to strict security measures and fed to other devices, e.g. a radio set, which will
perform the xor operation as part of their function. The latter device can then be designed and used in less
stringent environments.

• RC4 is the most widely used stream cipher in software; others include: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC,
MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 and WAKE. Comparison ….?

• http://en.wikipedia.org/wiki/Stream_cipher

Block cipher:

• In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed
blocks, with an unvarying transformation. When encrypting, a block cipher might take a (for example) 128-bit
block of plaintext as input, and output a corresponding 128-bit block of ciphertext.

• The exact transformation is controlled using a second input — the secret key. Decryption is similar:
the decryption algorithm takes, in this example, a 128-bit block of ciphertext together with the secret
key, and yields the original 128-bit block of plaintext.

• An early and highly influential block cipher design was the Data Encryption Standard (DES), developed at IBM and
published as a standard in 1977.

• A successor to DES, the Advanced Encryption Standard (AES), was adopted in

Examples:

• Algorithms: 3-Way | AES | Akelarre | Anubis | ARIA | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256
| CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CMEA | Cobra | COCONUT98 | Crab | CS-Cipher | DEAL | DES
| DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA |
IDEA NXT | Iraqi | Intel Cascade Cipher | KASUMI | KHAZAD | Khufu and Khafre | KN-Cipher | Libelle | LOKI89/91
| LOKI97 | Lucifer | M6 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 |
 NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent |
SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | UES | Xenon | xmx | XTEA | Zodiac

• http://en.wikipedia.org/wiki/Block_cipher

Chap.7 Confidentiality Using Symmetric Encryption:

• Where should cryptographic functionality be located?

• How can we make communications confidential?

• How do we distribute keys?

• What is the role of random numbers?

Placement of Encryption Function:

• Networks are vulnerable to active and passive attacks

– Many potential locations for confidentiality attacks

• By network tapping or other means

• Passive inductive attacks on electrical signaling

• Phone and wiring closets may be accessible to outsiders

• Satellite links are easy to monitor

• Etc.

Points of Vulnerability

Link vs. End-to-End Encryption:

 • The most powerful and most common approach to securing the points of vulnerability is encryption

• If encryption is to be used to counter these attacks, need to decide what to encrypt and where the encryption
should be located

• Two fundamental alternatives:

– Link encryption

– End-to-end encryption

• Link encryption

– Encryption occurs independently on every link

– Must decrypt traffic between links in order to route the frames

– Requires many devices, but paired keys

• End-to-end encryption

– Encryption occurs between original source and final destination

– Needs devices at each end with shared keys

– Must leave headers in clear so that network correctly routes information

– Contents are protected, but traffic pattern flows are not

• Ideally want both at once

– End-to-end protects data contents over entire path and provides authentication

– Link protects traffic flows from monitoring

Location of Encryption Device:

• Link encryption:

– A lot of encryption devices

– High level of security

– Decrypt each packet at every switch

 • End-to-end encryption

– The source encrypt and the receiver decrypts

– Payload encrypted

– Header in the clear

• High Security: Both link and end-to-end encryption are needed (see Figure 2.9)

Link vs. End-to-End Encryption:

Logical Placement of E2E Encryption Function:

• Link encryption occurs at either the physical or link layers

• For end-to-end encryption, several choices are possible

• At the lowest practical layer, the encryption function could be performed at network layer

• All the user processes and applications within each end system would employ the same encryption scheme with the
same key

• With this arrangement, front-end processor may be used to off-load the encryption function
Logical Placement of E2E Encryption Function:

• X.25 or TCP provide end-to-end security for traffic within a fully integrated internetwork. However, such a scheme
cannot deliver the necessary service for traffic that crosses internetwork boundaries, such as E-Mail, EDI, and file
transfer

• In this case, the only place to achieve end-to-end encryption is at the application layer

• A drawback of application-layer encryption is that the number of entities to consider increases dramatically

• Many more secret keys need to be generated and distributed

Traffic Confidentiality:

• Security from traffic analysis attack

– Knowledge about the number and length of messages between nodes may enable an opponent to
determine who is talking to whom

– Types of information derivable from traffic analysis

– Identities of communicating partners

– Frequency of communication

– Message patterns, e.g., length, quantity, (encrypted) content

– Correlation between messages and real world events

– Can (sometimes) be defeated through traffic padding

Countermeasure to Traffic Analysis:

• Link encryption approach

– Link encryption hides address info., but leaves the amount of traffic

– Traffic padding is very effective

• End-to-End encryption approach

– Leaves addresses in the clear

– Measures available to the defender are more limited

• Pad out data units to a uniform length at either the transport or application level

• Null message can be inserted randomly into the stream

Covert Channel:

• Essentially, the dual of traffic analysis

• A means of communication in a fashion unintended by the designers of the communication facility

• Usually intended to violate or defeat a security policy

• Examples

– Message length

– Message content

– Message presence

Securing a Network:

• Location for Confidentiality Attacks

• Location of Encryption Devices

• Key Distribution
Class Activity: A (Time: 6:15 PM):

• Given:

• P= “Write some text in notepad……!”

• Seek some encryption algorithms on Internet and choose a specific algorithm preferably non classical algorithms

• Given an encryption key and encrypt that text

• Send it to some of your friend through email and let him decrypt using the same key

Activity-1
ResearchTopic
Max Time: 15 Min

• Various techniques are used to Secure a Communication Link, reference to that describe any one method

• Note: Your discussion must be supported by IEEE, or Impact Factor based research Paper

• Next Class Attendance will be on the base of Research paper

Activity-2

• Using Any Programming Language, do the Following:

– A message is displayed: “Please Hit any key on key board.

– Then Press enter Key.

– And display the key you pressed previously and

– display the ASCII code of that text.

– A = 65

– B = 66

Activity-3

• Using Any Programming Language, do the Following:

– A message is displayed: “Please Hit any key on key board:”

– Then Press enter Key.

– Display a message “Please Enter Password:”

– Then display the messaged: “Plaintext = “

– Display “cipher text = “,

– Note: use simple addition with ascii the key.

Key Distribution

• For symmetric encryption to work, the two parties must share the same key and that key must be protected from
access by others

• Alice’s options in establishing a shared secret key with Bob include

– Alice selects a key and physically delivers it to Bob

– Trusted third party key distribution center (T3P or KDC) selects a key and physically delivers it to Alice and
Bob

– If Alice and Bob have previously and recently used a key, it can be used to distribute a new key

– If Alice and Bob have keys with the KDC, KDC can deliver a key on the encrypted links to Alice and Bob

• Manual delivery is a reasonable requirement with link encryption, challenging with end-to-end encryption

– The number of keys grows quadratically with the number of endpoints

• T3P key(s) constitute a rich target of opportunity

• Initial (master) key distribution remains a challenge

Key Distribution

1. A key could be selected by A and physically delivered to B.

2. A third party could select the key and physically deliver it to A and B.

3. If A and B have previously used a key, one party could transmit the new key to the other, encrypted using the old
key.

4. If A and B each have an encrypted connection to a third party C, C could deliver a key on the encrypted links to A and
B.

Session key:

Data encrypted with a one-time session key.At the conclusion of the session the key is destroyed

Permanent key:
 Used between entities for the purpose of distributing session key

Use of a Key Hierarchy:

• Use of a KDC is based on the use of a hierarchy of keys

– Session key : temporary encryption key used between two parties

– Master key : long-lasting key that are used between a KDC and a party for the purpose of encrypting the
transmission of session keys

A Key Distribution Scenario:

• Assume each user shares a unique master key with the KDC

• Alice desires a one-time session key to communicate with Bob

(1) Alice issues a request to the KDC for a session key to be used with Bob. Alice’s request includes a nonce to prevent replay
attack

(2) KDC responds with a message encrypted under Alice’s key. The message contains the session key, the nonce, and the
session key along with Alice’s identity encrypted under Bob’s key

(3) Alice forwards the data encrypted under Bob’s Key to Bob

(4-5) Alice and Bob mutually authenticate under the session key

• (4) Bob sends a nonce to Alice encrypted under the session key

• (5) Alice applies a transformation to the nonce and sends the result back to Bob
A Key Distribution Scenario:

Hierarchical Key Control

• Instead of a single KDC, a hierarchy of KDCs can be established; local KDCs and a golbal KDC

• Local KDCs exchange keys through a global KDC

• Can be extended to three or more layers (hierarchy)

• Hierarchical scheme

– Minimizes the effort involved in master key distribution

– Limits the damage of a faulty or subverted KDC to its local area only

Session Key Lifetime

• Tradeoffs in the session key lifetime

• The more frequent session keys, the more secure, but the less performance (the more network load and delay)

• For connection-oriented protocols, one option is to associate a session with a connection

• For long-lived connections, must periodically rekey

• For connectionless protocols, rekey at intervals

A Transparent Key Control Scheme

 1. A issues a request to B for a session key and includes a nonce, N 1

2. B responds with a message encrypted using the shared master key. Response includes the session key selected by B,
an identifier of B, the value of f(N1), and another nonce, N2

3. Using the new session key, A returns f(N2) to B

Controlling Key Usage

• It is desirable to impose some control on the way in which automatically distributed keys are used

– e.g. we may wish to define different types of session keys on the basis of use, such as

• Data-encrypting key

• PIN-encrypting key

• File-encrypting key

• One technique is to associate a tag with each key

– Tag is a bit-vector representing the key’s usage or type

– e.g. the extra 8 bits in each 56-bit DES key can be used as a tag
 – Limited flexibility and functionality due to the limited tag size

– Because the tag is not transmitted in clear form, it can be used only at the point of decryption, limiting the
ways in which key use can be controlled

• A more flexible scheme is to use a control vector

Control Vector Scheme

• Each session key has an associated control vector

• Control vector consists of a number of fields that specify the uses and restrictions for that session key

• The length of control vector may vary

• Control vector is cryptographically coupled with the at the time of key generation at the KDC

– Hash value = H = h(CV)

– Key input = Km  H

– Encrypted session key = EKm  H [Ks]

When a session key is delivered to a user from the KDC, it is accompanied by the control vector in clear form

Control Vector Scheme

Securing a Network:

• Location for Confidentiality Attacks

• Location of Encryption Devices

– (Discussed Already)

• Key Distribution

Key Distribution:
 • For symmetric encryption to work, the two parties must share the same key and that key must be protected from
access by others

• Alice’s options in establishing a shared secret key with Bob include (Ways for sharing a key):

1. Alice selects a key and physically delivers it to Bob

2. Trusted third party key distribution center (T3P or KDC) selects a key and physically delivers it to Alice and
Bob

3. If Alice and Bob have previously and recently used a key, it can be used to distribute a new key

4. If Alice and Bob have keys with the KDC, KDC can deliver a key on the encrypted links to Alice and Bob

Key Distribution:

• Manual delivery is a reasonable requirement with link encryption, challenging with end-to-end encryption

– The number of keys grows quadratically with the number of endpoints

• T3P key(s) constitute a rich target of opportunity

• Initial (master) key distribution remains a challenge

Key Distribution:

1. A key could be selected by A and physically delivered to B.

2. A third party could select the key and physically deliver it to A and B.

3. If A and B have previously used a key, one party could transmit the new key to the other, encrypted using the old
key.

4. If A and B each have an encrypted connection to a third party C, C could deliver a key on the encrypted links to A and
B.

Key Distribution:

• Session key:
 – Data encrypted with a one-time session key.At the conclusion of the session the key is destroyed

• Permanent key:

– Used between entities for the purpose of distributing session keys

Use of a Key Hierarchy:

• Use of a KDC is based on the use of a hierarchy of keys

– Session key : temporary encryption key used between two parties

– Master key : long-lasting key that are used between a KDC and a party for the purpose of encrypting the
transmission of session keys

A Key Distribution Scenario:

• Assume each user shares a unique master key with the KDC
 • Alice desires a one-time session key to communicate with Bob

(1) Alice issues a request to the KDC for a session key to be used with Bob. Alice’s request includes a nonce to prevent replay
attack

(2) KDC responds with a message encrypted under Alice’s key. The message contains the session key, the nonce, and the
session key along with Alice’s identity encrypted under Bob’s key

(3) Alice forwards the data encrypted under Bob’s Key to Bob

(4-5) Alice and Bob mutually authenticate under the session key

• (4) Bob sends a nonce to Alice encrypted under the session key

• (5) Alice applies a transformation to the nonce and sends the result back to Bob

A Key Distribution Scenario:

Hierarchical Key Control:

• Instead of a single KDC, a hierarchy of KDCs can be established; local KDCs and a golbal KDC

• Local KDCs exchange keys through a global KDC

• Can be extended to three or more layers (hierarchy)

• Hierarchical scheme

– Minimizes the effort involved in master key distribution

– Limits the damage of a faulty or subverted KDC to its local area only

Session Key Lifetime:

• Tradeoffs in the session key lifetime

• The more frequent session keys, the more secure, but the less performance (the more network load and delay)

• For connection-oriented protocols, one option is to associate a session with a connection

• For long-lived connections, must periodically rekey

• For connectionless protocols, rekey at intervals

A Transparent Key Control Scheme:

1. A issues a request to B for a session key and includes a nonce, N 1

2. B responds with a message encrypted using the shared master key. Response includes the session key selected by B,
an identifier of B, the value of f(N1), and another nonce, N2

3. Using the new session key, A returns f(N2) to B

Controlling Key Usage:

• It is desirable to impose some control on the way in which automatically distributed keys are used

– e.g. we may wish to define different types of session keys on the basis of use, such as

• Data-encrypting key

• PIN-encrypting key

• File-encrypting key

• One technique is to associate a tag with each key

– Tag is a bit-vector representing the key’s usage or type

– e.g. the extra 8 bits in each 56-bit DES key can be used as a tag

– Limited flexibility and functionality due to the limited tag size

– Because the tag is not transmitted in clear form, it can be used only at the point of decryption, limiting the
ways in which key use can be controlled
 • A more flexible scheme is to use a control vector

Control Vector Scheme:

• Each session key has an associated control vector

• Control vector consists of a number of fields that specify the uses and restrictions for that session key

• The length of control vector may vary

• Control vector is cryptographically coupled with the at the time of key generation at the KDC

– Hash value = H = h(CV)

– Key input = Km  H

– Encrypted session key = EKm  H [Ks]

• When a session key is delivered to a user from the KDC, it is accompanied by the control vector in clear form

• CV: control vector

• Km: master key

• Ks: session key

Control Vector Scheme:

• The session key can be recovered only by using both the master key and the control vector

– Ks = DKm  H[EKm  H [Ks]]

– Advantages (over the 8-bit tag)

– No restriction on length of control vector (arbitrarily complex controls to be imposed on key use)

– Control vector is available in clear form at all stage of operation  Key control can be exercised in multiple
locations

Control Vector Scheme:

Class Test(1):

• Q.1

– What is the OSI security architecture?

– Explain the difference between an attack surface and an attack tree.

• Q.2

Consider an automated cash deposit machine in which users provide a card or an account number to deposit cash. Give
examples of confidentiality, integrity, and availability requirements associated with the system, and, in each case,
indicate the degree of importance of the requirement

Class Test(2):

• Q.3 For each of the following assets, assign a low, moderate, or high impact level for the loss of confidentiality,
availability, and integrity, respectively. Justify your answers.

a. A student maintaining a blog to post public information.

b. An examination section of a university that is managing sensitive information
about exam papers.
c. An information system in a pathological laboratory maintaining the patient’s data.
d. A student information system used for maintaining student data in a university
that contains both personal, academic information and routine administrative information (not privacy related). Assess
the impact for the two data sets separately and the information system as a whole.
e. A University library contains a library management system which controls the
distribution of books amongst the students of various departments. The library
management system contains both the student data and the book data. Assess the
impact for the two data sets separately and the information system as a whole.

Modern Block Ciphers:

• now look at modern block ciphers

• one of the most widely used types of cryptographic algorithms

• provide secrecy /authentication services

• focus on DES (Data Encryption Standard)

• to illustrate block cipher design principles

Block vs Stream Ciphers:

• block ciphers process messages in blocks, each of which is then en/decrypted

• like a substitution on very big characters

– 64-bits or more

• stream ciphers process messages a bit or byte at a time when en/decrypting

• many current ciphers are block ciphers

• broader range of applications

Block Cipher Principles:

• most symmetric block ciphers are based on a Feistel Cipher Structure

• needed since must be able to decrypt ciphertext to recover messages efficiently

• block ciphers look like an extremely large substitution

• would need table of 264 entries for a 64-bit block

• instead create from smaller building blocks

• using idea of a product cipher

Ideal Block Cipher:

Claude Shannon and Substitution-Permutation Ciphers:

• Claude Shannon introduced idea of substitution-permutation (S-P) networks in 1949 paper

• form basis of modern block ciphers

• S-P nets are based on the two primitive cryptographic operations seen before:

– substitution (S-box)

– permutation (P-box)

• provide confusion & diffusion of message & key

LUCIFER: the first block cipher:

• One could perhaps quarrel with the title of this section. What about Playfair, or the Hill cipher? But LUCIFER, part of
an experimental cryptographic system designed by IBM, was the direct ancestor of DES, also designed by IBM.

• LUCIFER enciphered blocks of 128 bits, and it used a 128-bit key.

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

Feistel Cipher Design Elements:

• block size

• key size

• number of rounds

• subkey generation algorithm

• round function

• fast software en/decryption

• ease of analysis

FC Structure:

• Multiple rounds

– Round function (based on the round key)

– Substitution (XOR)
 – Permutation (Exchange of halves)

• Parameters

– Block size (64 bits)

– Key size (128 bits)

– Number of rounds (16)

– Sub-key generation algorithm

– Round function

Feistel Cipher Decryption:

Conventional Encryption Algorithms:

• IDEA (International Data Encryption Algorithm)

• The block cipher IDEA (for International Data Encryption Algorithm).

• The plaintext and the ciphertext are 64 bit blocks, while the secret key is 128 bits long.

Data Encryption Standard (DES):

 • The most widely used encryption scheme

• adopted in 1977 by NBS National Bureau of Standards (now NIST)

• as FIPS PUB 46 (FEDERAL INFORMATION. PROCESSING STANDARDS PUBLICATION. )

• The algorithm is reffered to the Data Encryption Algorithm (DEA)

• DES is a block cipher

• The plaintext is processed in 64-bit blocks

• The key is 56-bits in length

• has been considerable controversy over its security

DES History:

• IBM developed Lucifer cipher

– by team led by Feistel in late 60’s

– used 64-bit data blocks with 128-bit key

• then redeveloped as a commercial cipher with input from NSA National Security Agency 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 DES standard is public

• was considerable controversy over design

– in choice of 56-bit key (vs Lucifer 128-bit)

– and because design criteria were classified

• subsequent events and public analysis show in fact design was appropriate

• use of DES has flourished

– especially in financial applications

– still standardised for legacy application use

DES Implementation:

• DES C#

• https://www.youtube.com/watch?v=cYLX94DR8_Q&t=249s

• https://www.youtube.com/watch?v=iAYI-Xcd3Kk&list=PLrC9eiFFYSvXITUSFDIao2hsyTHsfa_lh

• DES Python

• https://www.youtube.com/watch?v=lSrrhP2vFS8&t=353s
Initial Permutation (IP):

Inverse Initial Permutation (IP-1):

Expansion Permutation(E):

Permutation Function(P):

DES S-Box(S1):
Permuted Choice One (PC-1):

Permuted Choice Two (PC-2):

Schedule of Left Shifts:

S-Boxes:

DES:
• The overall processing at each iteration:

Li = Ri-1

Ri = Li-1  f(Ri-1, Ki)

• Concerns about:

The algorithm and the key length

(56-bits)
Mangler Function:

• 1.     The mangler function first expands Rn (the right half of the input) from a 32-bit value into a 48-bit value, by
breaking Rn into eight 4-bit chunks and expanding each of those chunks into 6-bits.

• 2.     The 48-bit key Kn is broken down into eight 6-bit chunks and Xor'ed with each Rn 6-bit chunk.

• 3.     This 6-bit output is then fed into one of eight S-boxes, which produces a 4-bit output. Each set of 6-bits has its
own S-box. For example the 6-bit string 101101 uses its first 1 and last 1 to determine the row and the 2nd through
5th symbols to determine the column within the S-box table.

• 4.     All eight 4-bit outputs are combined into a 32-bit quantity whose bits are then permuted to ensure good
diffusion and the avalanche affect.

Time to break a code (106 decryptions/µs):

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 of 4

– inner bits 2-5 (col bits) are substituted

– result is 8 lots of 4 bits, or 32 bits

• row selection depends on both data & key

– feature known as autoclaving (autokeying)

• example:

– S(18 09 12 3d 11 17 38 39) = 5fd25e03

DES Key Schedule:

• forms subkeys used in each round

– initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves

– 16 stages consisting of:

• rotating each half separately either 1 or 2 places depending on the key rotation schedule K

• selecting 24-bits from each half & permuting them by PC2 for use in round function F

• note practical use issues in h/w vs s/w

DES Decryption:

• decrypt must unwind steps of data computation

• with Feistel design, do encryption steps again using subkeys in reverse order (SK16 … SK1)

– IP undoes 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 initial encryption IP

– thus recovering original data value

Avalanche Effect:

• key desirable property of encryption alg

• where a change of one input or key bit results in changing approx half output bits

• making attempts to “home-in” by guessing keys impossible

• DES exhibits 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 Internet in a few months

– in 1998 on dedicated h/w (EFF) in a few days

– in 1999 above combined in 22hrs!

• still must be able to recognize plaintext

• must now consider alternatives to DES

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

Strength of DES – Timing Attacks

• attacks actual implementation of cipher

• use knowledge of consequences of implementation to derive information about some/all subkey bits

• specifically use fact that calculations can take varying times depending on the value of the inputs to it

• particularly problematic on smartcards

Differential Cryptanalysis:

• one of the most significant recent (public) advances in cryptanalysis

• known by NSA in 70's cf DES design

• Murphy, Biham & Shamir published in 90’s

• powerful method to analyse block ciphers

• used to analyse most current block ciphers with varying degrees of success
 • DES reasonably resistant to it, cf Lucifer

Differential Cryptanalysis:

• a statistical attack against Feistel ciphers

• uses cipher structure not previously used

• design of S-P networks has output of function f influenced by both input & key

• hence cannot trace values back through cipher without knowing value of the key

• differential cryptanalysis compares two related pairs of encryptions

Differential Cryptanalysis Compares Pairs of Encryptions:

• with a known difference in the input

• searching for a known difference in output

• when same subkeys are used

Differential Cryptanalysis:

• have some input difference giving some output difference with probability p

• if find instances of some higher probability input / output difference pairs occurring

• can infer subkey that was used in round

• then must iterate process over many rounds (with decreasing probabilities)
 • perform attack by repeatedly encrypting plaintext pairs with known input XOR until obtain desired output XOR

• when found

– if intermediate rounds match required XOR have a right pair

– if not then have a wrong pair, relative ratio is S/N for attack

• can then deduce keys values for the rounds

– right pairs suggest same key bits

– wrong pairs give random values

• for large numbers of rounds, probability is so low that more pairs are required than exist with 64-bit inputs

• Biham and Shamir have shown how a 13-round iterated characteristic can break the full 16-round DES

Linear Cryptanalysis:

• another recent development

• also a statistical method

• must be iterated over rounds, with decreasing probabilities

• developed by Matsui et al in early 90's

• based on finding linear approximations

• can attack DES with 243 known plaintexts, easier but still in practise infeasible

• find linear approximations with prob p != ½

P[i1,i2,...,ia]  C[j1,j2,...,jb] = K[k1,k2,...,kc]

where ia,jb,kc are bit locations in P,C,K

 • gives linear equation for key bits

• get one key bit using max likelihood alg

• using a large number of trial encryptions

• effectiveness given by: |p–1/2|

DES Design Criteria:

• as reported by Coppersmith in [COPP94]

• 7 criteria for S-boxes provide for

– non-linearity

– resistance to differential cryptanalysis

– good confusion

• 3 criteria for permutation P provide for

– increased diffusion

Block Cipher Design:

• basic principles still like Feistel’s in 1970’s

• number of rounds

– more is better, exhaustive search best attack

• function f:

– provides “confusion”, is nonlinear, avalanche

– have issues of how S-boxes are selected

• key schedule

– complex subkey creation, key avalanche

Summary:

• have considered:

– block vs stream ciphers

– Feistel cipher design & structure

– DES

• details

• strength

– Differential & Linear Cryptanalysis

– block cipher design principles

Research Work (6:50 PM):

• You have been given a task to select one on the research paper and submit on LMS

• Keeping in view:

• Write down the keywords used in that paper

• Summary of the first two paragraphs of the Introduction Part.

Diffie-Hellman Key Exchange

• first public-key type scheme proposed

• by Diffie & Hellman in 1976 along with the exposition of public key concepts

• note: now know that Williamson (UK CESG) secretly proposed the concept in 1970

• is a practical method for public exchange of a secret key

• used in a number of commercial products

• Self

• https://www.youtube.com/watch?v=ESPT_36pUFc

• a public-key distribution scheme

• cannot be used to exchange an arbitrary message

• rather it can establish a common key

• known only to the two participants

• value of key depends on the participants (and their private and public key information)

• based on exponentiation in a finite (Galois) field (modulo a prime or a polynomial) - easy

• security relies on the difficulty of computing discrete logarithms (similar to factoring) – hard

Diffie-Hellman Setup

• all users agree on global parameters:

• large prime integer or polynomial q

• a being a primitive root mod q

• each user (e.g A) generates their key

• chooses a secret key (number): xA < q

• compute their public key: yA = axA mod q

• each user makes public that key yA

Diffie-Hellman Key Exchange

• shared session key for users A & B is KAB:

KAB = axA.xB mod q

= yAxB mod q (which B can compute)

= yBxA mod q (which A can compute)

• KAB is used as session key in private-key encryption scheme between Alice and Bob

• if Alice and Bob subsequently communicate, they will have the same key as before, unless they choose new public-
keys

• attacker needs an x, must solve discrete log

Diffie-Hellman Example

• users Alice & Bob who wish to swap keys:

• agree on prime q=353 and a=3

• select random secret keys:

• A chooses xA=97, B chooses xB=233

• compute respective public keys:

• yA=397 mod 353 = 40 (Alice)

• yB=3233 mod 353 = 248 (Bob)

• compute shared session key as:

• KAB= yBxA mod 353 = 24897 mod 353= 160(Alice)

• KAB= yAxB mod 353 = 40233 mod 353= 160 (Bob)

Hashes and Message Digests:

Hash:

• Also known as

– Message digest

– One-way function

• Function: input message -> output

• One-way: d=h(m), but not h’(d) = m

– Computationally infeasible find the message given the digest

• Cannot find m1 and m2, where d1 = d2

• Randomness:

– Any bit in the output ‘1’ half the time

– Each output: 50% ‘1’ bits

How many bits for hash?

• m bits, takes 2m/2 to find two with the same hash

• 64 bits, takes 232 messages to search (doable)

• Need at least 128 bits

• Example use

– Fingerprint a program/document: attackers cannot find a different program with the same message digest

Hash used for Authentication

• Alice and Bob share a secret KAB

Computing a MAC with a HASH

• Cannot just compute MD(m)

– Anyone can compute MD(m)

• MAC: MD(KAB|m)

– Allows concatenation with additional message: MD(KAB|m|m’)

• MD through chunk n depends on MD through chunks n-1 and the data in chunk n

• 512-bit blocks, append (message length, pad)

• How to solve?

– Put secret at the end of message:

• MD(m| KAB)

– Use only half the bits of the message digest as the MAC

– Concatenate the secret to both the front and the back of the message
Encryption with a Message Digest

• One-time pad:

– compute bit streams using MD, K, and IV

• b1=MD(KAB|IV), bi=MD(KAB|bi-1), …

–  with message blocks

• Mixing in the plaintext

– similar to cipher feedback mode (CFB)

• b1=MD(KAB|IV), c1= p1  b1

• b2=MD(KAB| c1), c2= p2  b2

Modern Hash Functions

• MD5

– Previous versions (MD2, MD4) have weaknesses

• SHA-1, SHA-2

– Secure Hash Algorithms

MD2

• 128-bit message digest

– Arbitrary number of octets

– Message is padded to be a multiple of 16 octets

– Append MD2 checksum (16 octets) (a strange function of the padded message) to the end

– Process the whole message 16 octets (16 x 8) at a time

• Each intermediate value depends on

– Previous intermediate value

– The value of the 16 octets of the message being processed

MD2 Padding
MD2 Checksum

MD2  Substitution Table

MD2 Checksum

• One byte at a time, k  16 steps

• mnk: byte nk of message

• cn=(mnk  cn-1)  cn

•  : 0  41, 1  46, …

– Substitution on 0-255 (value of the byte)

MD2 Final Pass

MD2 Final Pass

• Operate on 16-byte chunks

• 48-byte quantity q:

– (current digest|chunk|digestchunk)

• 18 passes of massaging over q, and one byte at a time:

– cn=(cn-1)  cn for n = 0, … 47; c-1 = 0 for pass 0; c-1 = (c47 + pass #) mod 256

• After pass 17, use first 16 bytes as new digest

– 16  8 = 128

Overview of MD4, MD5, and SHA-1

Padding for MD4, MD5, and SHA-1

MD4

• Rivest, RFC 1320

• Fast in software

• Simple to program

• Memory efficient - no large data structures

MD4 Notation

• word = 32 bits

• Message m

• XY = X AND Y

• X v Y = X OR Y

MD4

• m’ = m100 … 0

– Pad m until it is 64 bits short of a multiple of 512

– Message is always padded (i.e. even 448 bits are padded)

– Append a 1 followed by 0’s :

 • M[0 ... N-1] = m’ with low order 64 bits of m appended to it

– N is a multiple of 16

• Four-word buffer (A,B,C,D) initialize to:

– A: 01 23 45 67

– B: 89 ab cd ef

– C: fe dc ba 98

– D: 76 54 32 10

MD4 – Internal Functions

• F(X,Y,Z) = XY v not(X) Z

– Bitwise conditional: if X then Y else Z.

• G(X,Y,Z) = XY v XZ v YZ

– Bitwise majority function: bit positions in which 2 or more bits are 1, output has a 1, else output has a 0

• H(X,Y,Z) = X  Y  Z

– Bit positions with odd number of 1’s are 1, rest are 0

• Note: if bits of X, Y, and Z are independent and unbiased, each bit of F(X,Y,Z) and each bit of G(X,Y,Z) also will be
independent and unbiased.

MD4

for (i = 0 to N/16-1) {

/* Copy block i into X. */

For (j = 0 to 15) { X[j] = M[i*16+j] }

/* Save A, B, C,D */

AA = A BB = B CC = C DD = D

/* Combine Message blocks with A,B,C,D */

Round 1

Round 2

Round 3

Increment A,B,C,D by their values (AA,BB,CC,DD) at start of iteration} /* end for i */

Output A,B,C,D

A,B,C,D is chaining variable

compression function
MD4 Round 1

Function operates on chaining variable,

adds in message block

/* [abcd k s] denotes a = (a + F(b,c,d) + X[k]) <<< s. */

/* 16 operations. */

[ABCD 0 3]; [DABC 1 7]; [CDAB 2 11] ; [BCDA 3 19];

[ABCD 4 3]; [DABC 5 7] ; [CDAB 6 11]; [BCDA 7 19];

[ABCD 8 3]; [DABC 9 7]; [CDAB 10 11]; [BCDA 11 19]

[ABCD 12 3]; [DABC 13 7]; [CDAB 14 11]; [BCDA 15 19];

Note: each word rotates through each of the four positions for each value of s

X[k] (M) combined with A,B,C,D

Words sequential in round 1 (i.e. k = 1,2,3,…. 15 in order)

MD4 Round 2

/* [abcd k s] denotes

a = (a + G(b,c,d) + X[k] + 0x5A827999) <<< s. */

/* 16 operations. */

[ABCD 0 3]; [DABC 4 5]; [CDAB 8 9]; [BCDA 12 13];

[ABCD 1 3]; [DABC 5 5]; [CDAB 9 9]; [BCDA 13 13];

[ABCD 2 3]; [DABC 6 5]; [CDAB 10 9]; [BCDA 14 13];

[ABCD 3 3]; [DABC 7 5]; [CDAB 11 9]; [BCDA 15 13];

Word ordering altered from round 1

MD4 Round 3

/* Let [abcd k s] denotes

a = (a + H(b,c,d) + X[k] + 0x6ED9EBA1) <<< s. */

/* 16 operations. */

[ABCD 0 3]; [DABC 8 9]; [CDAB 4 11]; [BCDA 12 15]

[ABCD 2 3]; [DABC 10 9]; [CDAB 6 11]; [BCDA 14 15]

[ABCD 1 3]; [DABC 9 9]; [CDAB 5 11]; [BCDA 13 15];

[ABCD 3 3]; [DABC 11 9]; [CDAB 7 11]; [BCDA 15 15]

Word ordering partially altered from round 2

MD4 – End of Loop Addition

/* increment each of A,B,C,D by the value it had before this block was started. */

A = A + AA

B = B + BB

C = C + CC

D = D + DD

MD4 Constants

• 5A827999: 32-bit constant, represents the square root of 2. The octal value is 013240474631.

6ED9EBA1: 32-bit constant, represents the square root of 3. The octal value is 015666365641

MD-5

• Self

MD5 Process

• As many stages as the number of 512-bit blocks in the final padded message

• Digest: 4 32-bit words: MD=d0|d1|d2|d3

• Every message block contains 16 32-bit words: m 0|m1|m2…|m15

– Digest MD0 initialized to: d0=67452301,d1=efcdab89,d2=98badcfe, d3=10325476

– Every stage consists of 4 passes over the message block, each modifying MD

• Operations

Constants of MD5
MD5 Message Digest Pass 1

• For each integer i from 0 through 15

MD5 Message Digest Pass 2

• For each integer i from 0 through 15

 MD5 Message Digest Pass 3

• For each integer i from 0 through 15

MD5 Message Digest Pass 4

• For each integer i from 0 through 15

SHA-1

• Developed by NIST

• SHA is specified as the hash algorithm in the Digital Signature Standard (DSS), NIST

• Take a message of length at most 264 bits and produces a 160-bit output.

• SHA design is similar to MD5, but a lot stronger

• Make five passes over each block of data

• Step 1: Message Padding – same as MD5

• Step 2: Initialize MD buffer 5 32-bit words

A|B|C|D|E
A = 67452301

B = efcdab89

C = 98badcfe

D = 10325476

E = c3d2e1f0

SHA-1 operation on a 512-bit Block

• Step 3: the 80-step processing of 512-bit blocks – 4 rounds, 20 steps each.

Each step t (0 <= t <= 79):

– Input:

• Wt – a 32-bit word from the message

• Kt – a constant.

• ABCDE: current MD.

– Output:

• ABCDE: new MD

• Only 4 per-round distinctive additive constants

0 <=t<= 19 Kt = 5A827999

20<=t<=39 Kt = 6ED9EBA1

40<=t<=59 Kt = 8F1BBCDC

60<=t<=79 Kt = CA62C1D6

• Only 3 different functions

Round Function ft(B,C,D)

0 <=t<= 19 (BC)(~B D)

20<=t<=39 BCD

40<=t<=59 (BC)(BD)(CD)

60<=t<=79 BCD
 Inner Loop of SHA-1 – 80 Iterations per Block

HMAC