Montgomery Multiplication

Block Ciphers

Hash Functions

Elliptic Curve Cryptography

Secret Sharing

Broadcast/Multicast Encryption: Naor Pinkas, Logical Key Hierarchy

Side Channels and Fault Injection

Digital Signatures and Message Authentication Codes

Bounds Checking and Buffer Overflows

Definitions of Security

Goal: Reduce time cost for large Modular operations

Speed relies on caching, large number of montgomery operations, and taking modulus with powers of two.

M-Residue

Let \(M\) be a prime n-bit integer \(2^{N-1} < M < 2^N\)

Let \(R = 2^N\)

\(\bar{a} = a*R\) mod \(M\)

Logical Values

\(\bar{z} = \bar{x} + \bar{y}\) mod \(M\)

\(\bar{z} = (x+y)*R\) mod \(M\)\(\bar{z} = \bar{x}*\bar{y}*R^{-1}\) mod \(M\)

Montgomery Reduction: RED(\(T\))

Define RED(\(T\)) \(= TR^{-1}\) mod \(M\)

Let \(M' = -M^{-1}\) mod \(R\)

(i.e \(RR^{-1} - M'M = 1\))

\(m = T*M' mod R\)

\(t = \frac{T+mM}{R}\)

NOTE: this is integer division

\(t \ge M\) return \(t-M\), else return \(t\).

Kirchoff’s Law

Security of algorithm is based on the secret key rather than the algorithm.

Assume nothing about the secrecy of the algorithm

Block Cipher Basics

Block cipher: Plaintext \(\rightarrow\) Ciphertext on a fixed N-bit size.

Symmetric Key cryptography; treat algorithm as a block box

k-bit key, n-bit message, c-bit ciphertext

Brute force key: \(O(2^k)\)

Building a table

\(\sum^k x \sum^n \rightarrow \sum^n\)

Permutations from \(\sum^n \rightarrow \sum^n\)?

\(2^n!\)

Sterling’s Approximation: \(x! = \sqrt{2\pi x}\,(\frac{x}{e})^x \)

How big does a table need to be to map \(\sum^n \rightarrow \sum^n\)? \(log_2(x!)\) where \(x = 2^n\).

If n = 128 bits; \(k = log_2(2^{128}!) = 2^{134} bits.\)

Real-World Block Ciphers

Data Encryption Standard (DES)

NIST Standard

56-bit keys (due to 8th bit of every byte being a parity bit)

64-bit block size

Invented by IBM

Attack: Linear Cryptanalysis - Relationships between plaintext & ciphertext (supposedly NSA improved DES to be resistent to this attack)

Replaced by AES

Advanced Encryption Standard (AES)

Rijndael

128-bit blocksize

128/192/256-bit keysizes

Fast + low gate count

RC5: Ron’s Code 5

Simple, fast

32/64/128-bit block size

0-2040-bit key size

Strength of a block Cipher

Data Complexity: Known-plaintext; how many known-plaintexts does the adversary need to get?

Storage Complexity: How much hard drive space does the adversay need?

Computational Complexity: How much time does it take the adversary to process the key?

Breaking Block Ciphers

Brute Force Guess

What if k is small?

\(O(2^k)\) where k is the bits of the key

Known-plaintext attack: Get plaintext/CT pair

Small block size attack

What if n is small?

Known PT attack: Create a table of PT \(\rightarrow\) CT w/o key

Birthday Paradox: Proportional to the square root of the size of the search space

\(\sqrt(2^n) = 2^{n/2}\) known plaintexts/ciphertext pairs

Put these plaintext/ciphertext pairs in a table

Then you listen to another \(2^{n/2}\) ciphertexts.

High probability that one of the rows will hit (Key-equivalent translation).

Double Encryption: \(E_{k2}(E_{k1}(m))) = c\)

This is not \(O(2^{2k})\) complexity.

Meet in the Middle Attack: \(O(2^k)\) space \(\rightarrow O(2^k)\) time.

Method

Encrypt plaintext with each possible \(k_1\) (\(2^k\) keys).

Decrypt c under all possible \(k_2\)

If we find \(c'\) from decryption, we have found \(k_1\) form the table.

Use Birthday Paradox: Only need \(O(2^{k/2})\) rows.

Block Cipher Modes

Types

Electronic Code Book (ECB)

Cipher Block Chaining (CBC)

Output Feedback (OFB)

Counter Mode (CTR)

Electronic Code Book (ECB)

Use the same key to encode every block of the message

Cipher Block Chaining (CBC)

Start with an initialization vector

\(c_0 =\) initialization vector (public random string to prevent patterns)

\(c_i = E_k(c_{i-1} \oplus p_i)\)

Stream Ciphers

\(C = P \oplus G(s)\) where \(G(s)\) is some function \(G\) with a seed \(s\)

\(G: \sum^k\rightarrow \sum^{poly(k)}\)

Examples

Ron’s Code 4 (RC4): Part of WEP

Blum-Blum-Shub

\(x_0 = \) random initialization vector

\(x_i = (x_{i-1})^2\) mod \(n\) where \(n=pq\)

Random Oracles

Abitrary Length \(\rightarrow\) Fixed Length; \(\sum^* \rightarrow \sum^K\)

To guessing y for a given x takes \(O(2^k)\).

Properties

Pre-Image Resistance (PIR): one-wayness; Difficulty of inversion

A function \(h\) is PIR if no efficient adversary program \(A\) can invert \(h\) on more htan a negligible # of outputs.

\(h(x) = x^b\) mod \(n\); \(n=pq, b>1\). factorization unknown.

Collision Resistance: Hard to find

**any**pair of inputs that share outputs.Second Pre-Image Resistance: Given a message, should be hard to find another input with the same hash.

Attacks

Identical Prefix Collision Attack

Algorithm given prefix P

Produce suffix T and pair of messages (M,M’) s.t. H(P||M||T) = H(P||M’||T)

Chosen Prefix Collision Attack

Given 2 chosen prefixes P, P’

Produces a pair of messages (M,M’) s.t. H(P||M) = H(P’||M’)

Applications

PGP Fingerprints: Collision Resisitance, 2PIR

Signed Software: Collision Resistance, PIR, 2PIR

/etc/passwd: PIR