Introduction to Cryptography

--- Foundations of information security --Lecture 7

Outline

Why study cryptology? Basic terms, notations and structure of cryptography Private & public key cryptography examples Modern secret key ciphers : usage and methodology Encryption and possible attacks Secret key ciphers design Slides 23 to 26 for additional information (and reading)
2

CSE2500 System Security and Privacy

Why Study cryptology(1)

Intruder

Communications security

CSE2500 System Security and Privacy

Why Study cryptology(2)

Customer

Merchant

TTP

Electronic Commerce Security

CSE2500 System Security and Privacy

Why Study cryptology(3)

LEA

Law enforcement

CSE2500 System Security and Privacy

The Basic Problem

We consider the confidentiality goal:

Alice and Bob are Friends Marvin is a rival Alice wants to send secret messages (M1,M2,) to Bob over the Internet Rival Marvin wants to read the messages (M1,M2,) - Alice and Bob want to prevent this! Assumption: The network is OPEN: Marvin is able to eavesdrop and read all data sent from Alice to Bob. Consequence: Alice must not send messages (M1,M2,) directly they must be scrambled or encrypted using a secret code unknown to Marvin but known to Bob. CSE2500 System Security and Privacy

Cryptography
plaintext (data file or messages)
encryption

ciphertext (stored or transmitted safely)

decryption

plaintext (original data or messages)

CSE2500 System Security and Privacy

Private key cipher

Encryption

Encrypted message (ciphertext)

Decryption

Alice

E
key

Bob

Message (cleartext,plaintext)

Message (cleartext, plaintext)

CSE2500 System Security and Privacy

Basic terms

Cryptology (to be very precise) Cryptography --- code designing Cryptanalysis --- code breaking Cryptologist: Cryptographer & cryptanalyst Encryption/encipherment Scrambling data into unintelligible to unauthorised parties Decryption/decipherment Un-scrambling

CSE2500 System Security and Privacy

Types of ciphers

Private key cryptosystems/ciphers

The secret key is shared between two parties

Public key cryptosystems/ciphers

The secret key is not shared and two parties can still communicate using their public keys

CSE2500 System Security and Privacy

10

Examples of Messages

Types of secret Messages Alice might want to send Bob (in increasing length):
Decision (yes/no), eg. as answer to the question Are we meeting tomorrow? Numerical Value, eg. as answer to the question at what hour are we meeting? Document Software, Images etc.

CSE2500 System Security and Privacy

11

Concepts

A private key cipher is composed of two algorithms

encryption algorithm E decryption algorithm D

The same key K is used for encryption & decryption K has to be distributed beforehand

CSE2500 System Security and Privacy

12

Notations
Encrypt a plaintext P using a key K & an encryption algorithm E C = E(K,P) Decrypt a ciphertext C using the same key K and the matching decryption algorithm D P = D(K,C)

Note: P = D(K,C) = D(K, E(K,P))

13

CSE2500 System Security and Privacy

The Caesar cipher (e.g)

The Caesar cipher is a substitution cipher, named after Julius Caesar. Operation principle: each letter is translated into the letter a fixed number of positions after it in the alphabet table. The fixed number of positions is a key both for encryption and decryption.

CSE2500 System Security and Privacy 14

The Caesar cipher (cntd)

K=3
Outer: plaintext Inner: ciphertext

CSE2500 System Security and Privacy

15

An example

For a key K=3, plaintext letter: ABCDEF...UVWXYZ ciphtertext letter: DEF...UVWXYZABC Hence TREATY IMPOSSIBLE is translated into WUHDWB LPSRVVLEOH

CSE2500 System Security and Privacy

16

Breaking classic ciphers

With the help of fast computers, 99.99% ciphers used before 1976 are breakable by using one of the 4 types of attacks (described later). Modern cluster computers and future quantum computers can break several existing ciphers due to the power of such computers.

CSE2500 System Security and Privacy

17

Breaking the Caesar cipher

By trial-and error By using statistics on letters

frequency distributions of letters letter percent A 7.49% B 1.29% C 3.54% D 3.62% E 14.00% ..................................
CSE2500 System Security and Privacy 18

Toy example of private key cryptography (TPC)

Assume that a message is broken into 64-bit blocks and each 64-bit block of plaintext is encrypted separately: Key space are combinations of numerical digits max: 7 digits (eg: key = [1]; or key = [1,3], or key = [1,4,2]).

Assume that all 8 bits of a byte is used and key digits start from left to right. Encryption: Each plaintext block is first shifted by the number of binary digits before the last non-zero digit of the key. It is then exclusive-ored with the key starting from the first byte of the block, repeatedly to the end of the block (the key moves a distance of its size from left to right of the plaintext block). Decryption: do the reverse of encryption: the cipher-text is exclusive-ored and then shifted.

0 1 0 1
CSE2500 System Security and Privacy

0 1 1 0

= = = =

0 0 1 1

: exclusive or

19

Using TPC
Use TPC to encrypt the plaintext 12345, key = [1,4,2] Use TPC to encrypt the plaintext TREATY IMPOSSIBLE; key = [4]; Use TPC to encrypt the plaintext 100 dollars, key = [2,4];

CSE2500 System Security and Privacy

20

Principles of Private Key Encryption

Devise cryptographic algorithms:

a set of fast functions (E1, E2, E3, ..En) that when in turn applied to an input (initial or intermediate input) will produce a more potentially scrambled output. and a set of functions (D1,D2,D3, .. Dn) that when in turn applied to the cipher text (final or intermediate) will produce the original input text.

Devise algorithms, tests and proofs to validate your cryptographic algorithms

Analysing algorithms. Tests with powerful computers such as specialised, parallel, cluster, or quantum computers. Mathematical proofs.

CSE2500 System Security and Privacy

21

Toy example of public key cryptography

Definition: The multiplicative inverse of x with modulo n is y such that (x*y) mod n = 1 E.g:x=3; n=10, => y=7; since (3*7) mod 10 = 1 The above multiplicative inverse can be used to create a simple public key cipher: either x or y can be thought of as a secret key and the other is the public key. Let x = 3, y = 7, n = 10, and M be the message: M = 4 ;
3*4 mod 10 = 2; (ciphertext) - encrypting 2*7 mod 10 = 4 = M ; (message) - decrypting

M =6 ;
3*6 mod 10 = 8; 8*7 mod 10 = 6 = M (message)

CSE2500 System Security and Privacy

22

What is PKE used for?

Private Key Encryption (PKE) can be used:
Transmitting data over an insecure channel Secure stored data (encrypt & store) Provide integrity check:
(Key + Mes.) -> MAC (message authentication code)

CSE2500 System Security and Privacy

23

Morden Cryptography applications

Not just about confidentiality! Integrity

Digital signatures Hash functions

Fair exchange
Contract signing

Anonymity
Electronic cash Electronic voting

Etc.
24

CSE2500 System Security and Privacy

Modern private key ciphers

DES (US, 1977) (3DES)

key -- 56 bits, plaintext/ciphertext -- 64 bits

LOKI (ADFA, Australia, 1989)

key, plaintext/ciphertext -- 64 bits

FEAL (NTT, Japan, 1990)

key -- 128 bits, plaintext/ciphertext -- 64 bits

IDEA (Lai & Massey, Swiss, 1991)

key -- 128 bits, plaintext/ciphertext -- 64 bits

SPEED (Y Zheng in 1996)

Key/(plaintext/ciphertext) -- 48,64,80,,256 bits

AES (Joan Daemen & Vincent Rijmen 2000)

Key/(plaintext/ciphertext) -- 128, 192 and 256 bits

CSE2500 System Security and Privacy

25

General approaches to Cryptography

There are two general encryption methods: Block ciphers & Stream ciphers Block ciphers
Slice message M into (fixed size blocks) m1, , mn
Add padding to last block

Use Ek to produce (ciphertext blocks) x1, , xn Use Dk to recover M from m1, , mn E.g: DES, etc.

Stream ciphers
Generate a long random string (or pseudo random) called one-time pad. Message
E.g: EC4

one-time pad (exclusive or)

CSE2500 System Security and Privacy

26

Design of Private Key Ciphers(1)

A Cryptographic algorithm should be efficient for good use

It should be fast and key length should be of the right length e.g.; not too short

Cryptographic algorithms are not impossible to break without a key

If we try all the combinations, we can get the original message

The security of a cryptographic algorithm depends on how much work it takes for someone to break it
E.g If it takes 10 mil. years to break a cryptographic algorithm X using all the computers of a state, X can be thought of as a secure one reason: cluster computers and quantum computers are powerful enough to crack many current cryptographic algorithms.

CSE2500 System Security and Privacy

27

Design of Private Key Ciphers(2)

Encryption Algorithm Design

Should the strength of the algorithm be included in the implementation of the algorithm? Should we hide the algorithm? Should the block size be small or large? Should the keyspace be large? Should we consider other search rather than brute-force search? Should we consider the hardware technology?

CSE2500 System Security and Privacy

28

4 types of cryptanalysis

Depending on what a cryptanalyst has to work with, attacks can be classified into
ciphertext only attack known plaintext attack chosen plaintext attack chosen ciphertext attack (most severe)

CSE2500 System Security and Privacy

29

4 types of attacks

Ciphertext only attack

the only data available is a target ciphertext

Known plaintext attack

a target ciphertext pairs of other ciphertext and plaintext (say, previously broken or guessing)

CSE2500 System Security and Privacy

30

4 types of attacks

Chosen plaintext attacks

a target ciphertext can feed encryption algorithm with plaintexts and obtain the matching ciphertexts

Chosen ciphertext attack

a target ciphertext can feed decryption algorithm with ciphertexts and obtain the matching plaintexts

CSE2500 System Security and Privacy

31