Lecture 2 - Message Integrity

Introduction

• cryptography - the study of techniques for communicating securely in the presence of an adversary
• cryptanalysis - the study of techniques for breaking cryptosystems
• gap between cryptographic theory (beautiful, highly rigorous) and cryptographic practice (delicate engineering)
• message integrity - ensures that attackers cannot modify messages without being detected

Scenario

Setup

• Alice wants to send message m to Bob
• they don’t fully trust the messenger
• they want to ensure Bob receives exactly what Alice sent ($m'=m$)

Threat Model

• adversary Mallory can see/modify/forge messages
• Mallory wants to trick Bob into accepting a message Alice didn’t send

flowchart LR
	A[Alice] -- m --> B[Mallory]
	B -- m' --> C[Bob]

Approach: Message Verifier

1. Alice computes verifier $v := f(m)$

   graph LR
   A[Alice] -- m,v --> B[Mallory]
   B -- m',v' --> C[Bob]
   

2. Bob verifies that $v' = f(m')$, accepts message iff this is true

$f()$ is a function that maps every possible input to a pre-computed random output this would require a massive lookup table of size $2^{\text{len of longest m}} \times 2^{256}$ bits

Pseudorandom Functions

Overview

• objective - a function that performs like a random function, but is still within practical constraints

1. start with a family of $2^n$ functions $f_0(), f_1(), \dots, f_{(2^n) - 1}()$, all known to Mallory
2. let our verification function $v() := f_k()$ where $k$ is a secret $n$-bit index known only to Alice and Bob

Security Definition (testing the effectiveness of PRF $f_k()$):

1. choose secret $k$ and an RF $g()$
2. flip a coin to get bit $b$
3. if $b=0$, let $h() := g()$ if $b=1$, let $h() := f_k()$
4. Mallory chooses $x$; we announce $h(x)$ repeat as many times as Mallory likes
5. Mallory guesses $b$ in polynomial time

• in plain english, give Mallory a black box function that is randomly either a RF or PRF. let her run the function on as many functions as she wants, within polynomial time. if she can’t tell the PRF from the RF across multiple runs of this game, then the PRF is secure.

• we say PRF $f()$ is a secure if Mallory can’t do meaningfully better than random at guessing if it’s a PRF or RF

• note that Mallory can always determine if a function is a PRF given infinite time via a brute force attack

Using a PRF for Message Integrity

1. let $f()$ be a secure PRF (public)
2. in advance, choose a random key $k$ known only to Alice and Bob
3. Alice computes $v := f_k(m)

4. graph LR
       A[Alice w/ k] -- m,v --> B[Mallory]
       B -- m',v' --> C[Bob w/ k]
   

5. Bob verifies that $v' = f_k(m')$, accepts message iff they are equal

• if Bob accepts $m'$, then $m'$ is identical to $m$ with chance $1 - 1/2^n$

• Kerckhoff’s Principle - a cryptosystem should remain secure even if attackers know everything but the key

• we don’t know if PRFs actually exist (would imply $P \neq NP$)

Cryptographic Hashes

• cryptographic hash function - fixed function $H()$ with no key, and takes inputs of arbitrary length data and outputs a fixed size digest ($n$ bits)

• properties:

  1. pre-image resistance - for a given output $h$, hard to find any input $m$ such that $h = H(m)$
  2. collision resistance - hard to find any pair of inputs $m_1,m_2 \backepsilon H(m_1) = H(m_2)$
  3. second pre-image resistance - for a given input $m_1$, hard to find $m_2 \neq m_1 \backepsilon H(m_1) = H(m_2)$

• note that there must exist an infinite number of collisions due to the pigeonhole principle; however, hard to find means computing them is intractable

Hashes with Broken Collision Resistance

MD5

• broken in 2004
• now it’s easy to find collisions SHA-1
• broken in 2017
• computing first collision cost > $100,000
• today costs < $10,000

SHA-256

• widely used hash function that is currently thought to be strong

• input: arbitrary length data

• output: 256-bit digest

• built from a c

• uses the Merkle-Damgard (MD) construction to accept arbitrary-length input by repeatedly applying $h()$:

  1. pad the input $m$ to next multiple of 512 bits (adds at least 1 bit, uses fixed algorithm) and split into 512-bit blocks: $b_0,b_1, \dots, b_{n-1}$
  2. $y_0 :=$ <256-bit constant> $y_1 := h(y_0,b_0) \dots y_i := h(y_{i-1},b_{i-1})$
  3. return $y_n$ which is defined to be SHA-256(m)