1 of 45

Introduction to Cyber Security

TA 4 part 1 – Intro to Cryptography

Jonathan Berger

Based on slides of Benny Pinkas and Avishay Yanai

​

2 of 45

 

Can we guarantee “” while avoiding these limsecurityitations?

2

3 of 45

Computational Security

Two realistic relaxations:

  1. Security is preserved only against efficient adversaries
  2. Adversaries can potentially succeed with some very small probability

E.g., 200 years using current technology

Small enough such that will essentially never happen

 

3

4 of 45

The Asymptotic Approach

“A scheme is secure if every probabilistic polynomial-time (PPT) adversary

succeeds in breaking the scheme with only negligible probability”

 

 

 

4

5 of 45

OTP without a zero key

  •  

page 5

6 of 45

OTP without a zero key – Intuition + refutation

  •  

page 6

7 of 45

OTP without a zero key – A note

  • Note that OTP without a zero key, means that |K| < |M|
    • You have seen in the lecture a proof that such schemes do not achieve perfect secrecy (Shannon’s theorem).

​

​

​

page 7

8 of 45

Indistinguishability and Perfect Secrecy

  •  

page 8

9 of 45

Proof

  • Note that the proof cannot assume that the encryption scheme is the one-time-pad – we assume a general encryption scheme.

page 9

10 of 45

Proof (one direction, perfect secrecy ⇒ indistinguishability)

  •  

page 10

Bayes’ theorem

Due to perfect secrecy

11 of 45

Proof (cont.)

  •  

page 11

12 of 45

PRG – recall definition

  •  

page 12

13 of 45

Pseudo-random generator

Slide from Introduction to Cryptography, Benny Pinkas

u

Distinguisher

D

random

????

G

s

G(s)

seed

(random, |s|=n)

​

output

|u|= 2n

​

Deterministic function of s, publicly known

∀ D

|G(s)| = 2n

​

page 13

Pseudo-random

​

generator

14 of 45

Pseudorandom Generators (PRGs)

 

 

14

15 of 45

 

  •  

16 of 45

 

  •  

17 of 45

 

  •  

18 of 45

G’(s) = ¬G(s) is a PRG (pseudorandomness proof)

  •  

19 of 45

 

  •  

20 of 45

Pseudorandom Generator (PRG)

Seed

…

21 of 45

A Reminder - Pseudorandom Function (PRF) - definition

  •  

22 of 45

Pseudorandom Function (PRF)

Key

…

23 of 45

Pseudorandom Function (PRF)

Key

F(k,X)

…

Location X

24 of 45

PRF 🡪 PRG?

 

25 of 45

PRF 🡪 PRG?

 

 

 

 

 

 

…

 

 

 

 

 

26 of 45

Encryption

 

27 of 45

Chosen-Plaintext Security

  •  

28 of 45

Modes of Operation

 

29 of 45

Mode 1: Electronic Codebook (ECB)

 

 

30 of 45

ECB mode is not CPA-secure

  •  

 

or

 

31 of 45

Insecurity of ECB…

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

32 of 45

Mode 2: Counter Mode (CTR)

 

 

33 of 45

Mode 3: Cipher Block Chaining (CBC)

 

 

34 of 45

CBC with non-random IV

  • Consider an encryption scheme that increases the IV by one for every message

​

  • Is it CPA-secure?
    • No. Why?

​

35 of 45

CBC with non-random IV (cont.)

  • Consider an encryption scheme that increases the IV by one for every message
  • Is it CPA-secure?
    • No. Why?

 

 

or

 

36 of 45

CBC with non-random IV (cont.)

  • Consider an encryption scheme that increases the IV by one for every message
  • Is it CPA-secure?
    • No. Why?

 

37 of 45

CCA Security

  •  

38 of 45

CBC mode is not CCA secure

 

39 of 45

CTR mode is not CCA secure

 

40 of 45

AES-CTR mode example in python

41 of 45

Study Case - BEAST Attack

  • BEAST - Browser Exploit Against SSL/TLS
    • We are not going to present that attack itself -- we will see the idea behind the attack

​

  • Recall CBC:

​

Encryption 1

Encryption 2

New random IV

42 of 45

Study Case - BEAST Attack (cont.)

  • CBC “Optimization”:

​

Encryption 1

Encryption 2

Previous last ciphertext block is used as IV

43 of 45

Study Case - BEAST Attack (cont.)

Some Data

“Password:1456”

We Control

We see

C1

C2

C3

IV = C3

C4

C5

IV = C5

We Control

C6

The Setting

​

P0

P1

 

 

 

44 of 45

Study Case - BEAST Attack (cont.)

P0

Some Data

“Password:1456”

We Control

We see

C1

C2

C3

IV = C3

C4

C5

IV = C5

We Control

C6

 

P1

 

 

 

45 of 45

​

​

Questions?