1

Jonathan Berger

Introduction to Cyber Security

TA 4 part 2: Intro to Cryptography

Based on slides of Avishay Yanai

​

Cryptographic Hash Function

2

Cryptographic Hash Function

3

4

5

6

7

Application example of cryptographic hash functions

Merkle Trees

Application: File Storage

• Consider a client that uploads a file to a server

​

• After some time, the client would like to retrieve the file

​

• The client would like to make sure that he retrieved the original file that he had stored
• The server might be malicious

8

Application: File Storage – single file

9

Application: File Storage – many files

10

Application: File Storage – many files

11

Application: File Storage – many files

12

Application: File Storage – many files

13

Local storage: Constant.

Communication per file: 2 files + (log n)-1 hashes

Finding Collision

14

The “Birthday” Problem/Paradox

15

The “Birthday” Problem/Paradox (cont.)

16

The “Birthday” Problem/Paradox – Lower bound proof

17

18

A Reminder – Message Authentication Code (MAC)

19

Canonical Verification

20

MAC from Collision Resistant Hash Functions

21

Timing attacks

22

Timing attacks (cont.)

• Consider the following (simplified) code for verification:

​

​

​

​

​

​

• Both memcmp() and python’s ‘==‘ compare the results byte-by-byte
• This comparison does not run in constant time. First byte is different -> immediate return

​

23

Timing attacks (cont.)

• The attack concept:
1. Send a message with a random tag, t
1. Measure the time

​

• Loop over the first byte of the tag
• If verification took longer -> success with the first byte

​

• Repeat until the tag is valid

​

• Used to attack Xbox 360 (2.2 milliseconds difference)

​

• Takeovers:
• (Again) Do not implement your own crypto
• In Python, you can use hmac.compare_digest() to assure constant-time verification

​

24

Attacker

Verifier

(m,t)

0/1

(m,t’)

Data Integrity, Message Authentication

• Risk: an active adversary might change messages exchanged between Alice and Bob

page 25

Alice

Eve

Bob

• Authentication is orthogonal to secrecy. It is a relevant challenge regardless of whether encryption is applied.

M

M

M’

M’

Message Authentication Code (MAC)

26

Requirements

• Security: The adversary,
• Knows the MAC algorithm (but not K).
• Is given many pairs (m_i , MAC_K(m_i)), where the m_i values might also be chosen by the adversary (chosen plaintext).
• Cannot compute (m, MAC_K(m)) for any new m (∀ i m≠m_i).
• The adversary must not be able to compute MAC_K(m) even for a message m which is “meaningless” (since we don’t know the context of the attack).

​

• Efficiency: MAC output must be of fixed length, and as short as possible.
• ⇒ The MAC function is not 1-to-1.
• ⇒ An n bit MAC can be broken with prob. of at least 2^-n.

page 27

The Security of MACs

• Does not prevent “replay attacks”!

28

A Fixed-Length MAC

If F is a PRF, then the above MAC scheme is secure.

29

A Variable-Length MAC (NMAC)

A Variable-Length MAC (NMAC)

State of the art – HMAC

State of the art – HMAC

Exercises

34

​

​

Questions?

35

​

​

(MAC("יאללה עופו הביתה"))

36