CRYPTOGRAPHY

Cryptography

The study of mathematical techniques for securing digital information, systems, and distributed computations against adversarial attacks.

A private-key encryption scheme is specified by a message space M and three

algorithms:

ˆ Key Generation: KGen is a probabilistic algorithm that outputs a key k according to some

distribution

ˆ Encryption: Enc takes as input a key k and a message m, and outputs a ciphertext c

ˆ Decryption: Dec takes as input a key k and a ciphertext c, and outputs a message m

Kerckhoffs’ Principle

The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.

which means key must be the o ly thing that remains secret.

Caesar’s cipher

Letters were shifted 3 places forward.

ROT-13 shift 13 places forward. type of caesar’s cipher.

Problems with Caesar’s Cipher

• cipher method is fixed;

• there is no key;

• fails to achieve Kerckhoffs principle

Shift Cipher

keyed variant of Caesar Cipher.

enc= shift k places forward'

dec= shift k places backward

is shift cipher secure? why or why not?

it is not restitant to brute force attacks

Sufficient Key-Space Principle

Any secure encryption scheme must have a key space that is sufficiently large to make an exhaustive-search attack infeasible

Mono alphabetic substituition

Key is an arbitary mapping of letters in the alphabet, ensuring each letter is consistently replaced by a specific letter throughout the message.

brute force attack is infeasibale due to the vast number of possible key combinations.

Is mono alphabetic substituition secure?

Attack possible using statistical properties of the English language

shift attack

compute Ij for all j and output the value k for

which Ik is closest to 0.065

vigenere

Key is a string of letters,

brute force prob

statistical approach works

vignere attack

unknown key lentgh is ok

Kasiski’s method

• indentify repeated pattern of length 3 in the ciphertext

• Greatest common divisor of the distance between repeated sequences will yield the key length

  (or a multiple of it)

Index of coincedonce

security definitions’ two components:

1. A security guarantee (from view of the attacker an attacker’s goal that constitutes a break

of the scheme)

2. A threat model (describing what the adversary is capable of)

attackers’ goal

a ciphertext should leak no additional information about the underlying plaintext

threat models

• Ciphertext-only attack: The adversary just observes ciphertexts. This is the threat model we have been implicitly assuming thus far

• Known-plaintext attack: The adversary can learn some plaintext-ciphertext pairs and aims to deduce information of a plaintext underlying some other ciphertext

• Chosen-plaintext attack: The adversary can obtain plaintext-ciphertext pairs, as above, for plaintexts of its choice

• Chosen-ciphertext attack: The adversary is additionally able to obtain the decryption of ciphertexts of its choice

Principles of Modern Cryptography

1. definitions

2. precise assumptions

3. proofs of security

An encryption scheme is defined by?

three algorithms KGen, Enc, and Dec, as well as a specification of a message space M with |M| > 12, a (finite) key space K, and a ciphertext space C

perfect correctness?

for all k ∈ K and m ∈M, we have:

Pr[Dec(k, Enc(k,m)) = m] = 1

Perfect correctness implies that decryption is deterministic (without loss of generality), as Dec(k, c) must return the same output every time

Perfect Secrecy?

“Regardless of any prior information the attacker has about the plaintext, the ciphertext should leak no additional information about the plaintext”

For every m,m′ ∈M, and every c ∈ C, we have

Pr[Enc(k,m) = c] = Pr[Enc(k,m′) = c].

perfectly indistinguishable

if perf indist=> perf secret

One Time Pad

is perf secret

Limitations of the OTP?

ˆ key is as long as the message

ˆ only secure if the key is used once

perf secret encyrytion when?

Theorem 2.11

If (KGen, Enc, Dec) is a perfectly secret encryption scheme with message space M and key space K, then |K| ≥ |M|.

Shannon theorem

Message Integrity In block vs stream

Stream: flipping 1 bit results in whole message change

block: flipping one only affects that bit

MAC Defin?

A message authentication code (or MAC) consis of three probabilistic polynomial-time algorithms (KGen, Mac, Vrfy) such that:

1. The key-generation algorithm KGen takes as input the security parameter 1n and outputs a key k with |k| ≥ n.

2. The tag-generation algorithm Mac and a message m ∈ {0, 1}∗, and outputs a tag t. Since this algorithm may be randomized, we write this as t ← Mack (m).

3. The deterministic verification algorithm Vrfy takes as input a key k, a message m, and a tag t. It outputs a bit b, with b = 1 meaning valid and b = 0 meaning invalid. We write this as b := Vrfyk (m, t).

It is required that for every n, every key k output by KGen(1n), and every m ∈ {0, 1}∗, it holds that Vrfyk (m, Mack (m)) = 1.

If there is a function ℓ such that for every key k output by KGen(1n), algorithm Mack is only defined for messages m ∈ {0, 1}ℓ(n), then we call the scheme a fixed-length MAC for messages of length ℓ(n).

The adversarial indistinguishability experiment Mac-ForgeA,Π(n):

1. A key k is generated by running KGen(1n).

2. The adversary A is given input 1n and oracle access to Mack (·). The adversary eventually outputs (m, t). Let Q denote the set of all queries that A submitted to its oracle.

3. A succeeds if and only if

(1) Vrfy(k,m, t) = 1 and

(2) m /∈ Q.

In that case the output of the experiment is defined to be 1.

A message authentication code Π = (KGen, Mac, Vrfy) is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all probabilistic polynomial-time adversaries A there is a negligible function negl such that

Pr[Mac-ForgeA,Π(n) = 1] ≤ negl(n) .

Replay Attacks

an adversary sends again (“replays”) previously authenticated messages.

Prevention: use timestamps

Mac -s Forge

define the experiment Mac-sForgeA,Π similar to Mac-ForgeA,Π with the difference that Q stores pairs of oracle queries and responses and the final check is modified to (m, t) /∈ Q, for (m, t) the output of A

A message authentication code Π = (KGen, Mac, Vrfy) is strongly secure, if for all probabilistic polynomial-time adversaries A there is a negligible function negl such that

Pr[Mac-sForgeA,Π(n) = 1] ≤ negl(n) .

Macs Pseudorandom Fnc

Limitation of Construction 4.5: only messages of fixed-length can be handled, which is unacceptable for most applications

Secure Message Authentication Codes

add a random “message identifier” r in each block to prevent the“mix-and-match” attack

Let Π′ = (Mac′, Vrfy) be a fixed-length MAC for messages of length n. Define a MAC as

follows:

ˆ Mac: on input a key k ∈ {0, 1}n and a message m ∈ {0, 1}∗ of (nonzero) length ℓ < 2n/4, parse m as d blocks m1, . . . ,md , each of length n/4. (The final block is padded with 0s if necessary.) Choose a uniform message identifier r ∈ {0, 1}n/4.

For i = 1, . . . , d, compute ti ← Mac′ k (r ∥ ℓ ∥ i ∥ mi ), where i , ℓ are encoded as strings of length n/4. Output the tag t := ⟨r , t1, . . . , td ⟩.

ˆ Vrfy: on input a key k ∈ {0, 1}n, a message m ∈ {0, 1}∗ of nonzero length ℓ < 2n/4, and a tag t := ⟨r , t1, . . . , td′ ⟩, parse m as d blocks m1, . . . ,md , each of length n/4. (The final block is padded with 0s if necessary.) Output 1 if and only if d′ = d and Vrfy′ k (r ∥ ℓ ∥ i ∥ mi , ti ) = 1 for 1 ≤ i ≤ d.

CBC-MAC

Let F be a pseudorandom function, and fix a length function ℓ(n) > 0. The basis CBC-MAC construction is as follows:

ˆ Mac: on input a key k ∈ {0, 1}n and a message m of length ℓ(n) · n, do the following (set ℓ = ℓ(n) in what follows):

1. Parse m and m = m1, . . . ,mℓ where each mi is of length n.

2. Set t0 := 0ⁿ. Then, for i = 1 to ℓ, set ti := F_k (ti−1 ⊕ mi )

Output tℓ as the tag.

ˆ Vrfy: on input a key k ∈ {0, 1}n, a message m, and a tag t, do: If m is not of length ℓ(n) · n then output 0. Otherwise, output 1 if and only if t ?= Mac_k (m).

Theorem 4.10

Let ℓ be a polynomial. If F is a pseudorandom function, then Construction 4.9 is a secure MAC for messages of length ℓ(n) · n.

Basic CBC-MAC vs. Construction 4.5 and Construction 4.7

Compared to Construction 4.5, basic CBC-MAC can handle longer messages (though still fixed-length)

Compared to Construction 4.7, basic CBC-MAC is much more efficient: only d block-cipher evaluations for a message of length dn and a tag of length n (compared to 4d block cipher evaluations and tags of length more than 4dn)

CBC-MAC vs. CBC-mode encryption

Basic CBC-MAC is similar to the CBC mode of operation but there are crucial differences:

1. CBC-mode encryption uses a random IV, which is crucial for security. CBC-MAC uses no IV (can be viewed as constant IV iv = 0n), which is also crucial for security.

2. In CBC-mode encryption the intermediate values (ti in CBC-MAC) are output as part of the ciphertext. CBC-MAC only outputs the final value tℓ.