Cryptography 1

Keywords: Crypto Class Coursera Cryptogrophy

Video Lectures

Week 1 : Introduction

Overview

Crypto is everywhere. This course will cover symmetric encryption.

A cipher consists of E and D - the encryption and decryption algorithm. They should be know algorithms, not proprietary.

What is Crypto

Uses:

• Digital signatures
• Mix net - allows anonymous communications
• Digital currency
• Elections
• Private auctions
• Secure multi-party computation
• Privately outsourcing computation
• Zero knowledge: can show proof of having some piece of information without revealing the information

Theorm: Anything that can be done with a trusted authority can also be done without a trusted authority.

Crypto Analysis

1. Precisely specify threat model
2. Propose a construction
3. Prove that breaking construction under threat model will solve an underlying hard problem

History of Crypto

Symmetric ciphers: use the same key for encryption and decryption.

Historic Ciphers

Substitution cipher

Simplest form is the Caesar Cipher which only uses a shift. A substitution cipher uses a random mapping of letters as it's key. The key space is about 2⁸⁸ which is sufficiently large, but the cipher is subject to frequency analysis. It is subject to a cipher-text only attack.

Vigener Cipher

Key is some sequence of letters. Key is repeated until it is the same length as the plain text. Each position is then summed and mod26. If we know the length of the key, we can still use a frequency analysis. If the key length is not known, the same attack can be run for an assumed key size (starting at 1) and incremented. If the key size is wrong, the frequency distribution will be even, when the key size is correct, the frequency distribution will be correct. Again, cipher-text only attack (though a larger sample is needed).

Rotor Machines

Uses substitution ciphers encoded on spinning disks. Changes the cipher based on the last letter used. Still subject to frequency based, cipher-text only attacks. The Enigma machine was the most advanced rotor machine.

DES (1974)

Key space was 2⁵⁶ and the block size was 64.

Today

AES (2001), Salsa20(2008) and others.

Discrete Probability 1

Review of notations and concepts in discrete mathematics and probability. Nothing here that I don't remember.

Discrete Probability 2

More review. Independence of events. XOR.

Given Y with a random distribution over {0,1}ⁿ (though not necessarily uniform) and X with an independent, uniform distribution over {0,1}ⁿ then Z := Y ⊕ X is uniform over {0,1}ⁿ. There is a very cool proof of this.

Week 1 : Stream Ciphers

One Time Pad

A cipher is an "efficient" defined over (K, M, C) is a pair of algorithms (E,D) where

 K: key space
 M: message space
 C: cipher space
 E: K x M → C
 D: K x C → M
 ∀ k∈K, m∈M: D(k, E(k,m)) = m

The term "efficient" refers to either complexity or real world time, though in practice, both end up being equivalent. E is often randomized--the same key and message will not always produce the same cipher, but D is always deterministic.

One Time Pad - Vernam 1917

 c:= E(k,m) = k ⊕ m
 m:= D(k,c) = k ⊕ c

But given m and c

 k:= m ⊕ c

Very fast, but requires very long keys and transmitting the keys becomes it's own problem. Claude Shannon state that given the cipher-text, it should reveal no information about the plain text.

According to Shannon, a cipher (E,D) over (K, M, C) has perfect secrecy if

 ∀m0, m1, ∈M where
 (len(m0) == len(1) and ∀c ∈ C
 And k is uniform in K
 Pr[ E(k, m0) == c] == Pr[E(k, m1) == c]

Pr is probability.

Here is a proof that OTP has perfect secrecy. I am not copying it here.

Bad news, Shannon also showed that perfect secrecy requires that the number of keys is greater than or equal to the number of messages. So the key must be as long as the message for perfect secrecy.

Pseudo Random

Pseudo Random Generator (PRG): G(s) → r where s:={0,1}^m and r:={0,1}ⁿ and n >> m. Also G is deterministic.

Using G, k becomes the seed so:

 c = E(k,m) := m ⊕ G(k)
 m = D(k,c) := c ⊕ G(k)

G (the PRG) must be unpredictable, otherwise the whole system is insecure.

G is predictable if ∃ efficient algorithm A that given the first i digits (for any i) from a random key, make a better than even prediction (even .5 + 1/1E9) of what the next digit will be.

We consider an event at a probability of 1/2³⁰ to be non-negligible because it could happen in 1GB of data. But 1/2⁸⁰ is considered negligible. In formal systems (theory) negligibility is a function of the constraints of the system.

Attacks on OTP

Two Time Pad

Given C₁ and C₂, both ciphers from the same OTP.

 C1 ⊕ C2 = m1 ⊕ m2

It is possible to recover both messages from their plain text. Project Venona was an instance where the USA intercepted messages from the USSR. MS-PPTP on Windows NT also was subject to this attack. This is also one of the (many) weakness in WEP.

No Integrity (Malleability)

It is possible to predictably alter the plain-text without decoding it, particularly if part of (or the format of) the plain-text is known.

Real-World Stream Ciphers

RC4

Takes a variable key, expands it to a 2048b key and feeds that into a PRG. Used in HTTPS and WEP. The first few bytes are biased, so it is recommended to ignore the first 256 bytes. After a few gigs of data, it becomes slightly bias towards "00". It is also subject to related key attacks.

CSS

Content Scrambling System, used on DVDs. Based on a "linear feedback shift register" (LFSR). Requires a maximum of 2¹⁷ attempts to break.

Salsa20

One of the cipher from the eStream project in 2008. Easy to implement on both hardware and software. Takes a key and a nonce--a non-repeating value for a given key. The key is 128 or 256 bits and the nonce is 64 bits.

PRG

For any key in K we want the generator G to output bits that are indistinguishable from random. The problem is that the the key size is n and the output size is m and n<<m, then G can only select from a small section of it's total possible space.

We will use statistical tests to check if the output is random. Statistical test (for some reason) output 0 for not random and 1 for random. In these formulas x is the binary string and n is the length of the binary string.

Test 1) Same number of 1s and 0s

 |#0(x) - #1(x)| ≤ 10*n0.5

Test 2) The number of '00' is about 1/4

 |#00(x) - n/4| ≤ 10*n0.5

Test 3) The max-run-of-0 is where we expect

 max-run-of-0(x) ≤ 10*log2(n)

In evaluating statistical test we talk about advantage (there was a big formula around 9:39 I didn't write down). An advantage close to 1 can distinguish G from random and an advantage close to 0 does not have much distinction value. So 0 is good.

It cannot be shown that a PRG is secure, it's only possible to show that it's not secure.

Semantic Security

We can reduce Shannons concept of perfect secrecy where the ciphers reveals no information, to semantic security where the cipher reveals no computable information.

The test for this is setup between a challenger and an adversary. The adversary chooses two messages and the challenger chooses a key. The challenger then encrypts one of the messages and sends it to the adversary. If the adversary can identify the messages with greater than even odds, the system is considered broken.

SCs are Semantically Secure

Since we defined the output of G as indistinguishable from true random, we can show that OTP with PRG is as strong as OTP if G is truly indistinguishable from random.

Week 2 : Block Ciphers

What Are Block Ciphers

Takes n-bits of input and outputs n-bits and takes a key of k-bits.

Takes a key and produces round keys with a round function; R(k,m).

Block ciphers are slower than stream ciphers, but can be parallelized.

• PRF: pseudo random function
• PRP: pseudo random permutation

DES

DES Core Idea: Feistel Network

Given f₁,...,f_n: {0,1}ⁿ → {0,1}ⁿ

Our goal is to build invertible function F: {0,1}²ⁿ → {0,1}²ⁿ

R_i = F_i(R_i-1) ⊕ L_i L_i = R_i-1 Where R and L are the left and right bits

for all sets of functions, a Feistel network is invertible. In hardware, the same circuits can do encryption and decryption. Feistel networks are not used in AES.

DES uses the same function for all 16 functions, but with a different round key each time.

The S-Boxes are the only non-linear part of DES, so they must be non-linear or the standard would be easy to break.

Exhaustive Search Attacks

In 1999 DES could be broken in 22-hours (using a $250k machine). In 2006, a $10k machine was able to break it in 7 days.

The solution was 3DES, simply using 3 different keys to successively encrypt a message. As a hack, rather than triple encrypting, it actually did EDE, using the D as E. This way, if you set k1=k2=k3 then 3DES = DES, allowing hardware manufacturers to make dual purpose machines.

Any thing over 2^90 is considered secure.

More Attacks

Never design your own block cipher. Use the standard ones.

Side Channel Attacks

Measure time or power to do enc/dec. This may reduce the keyspace to a reasonable size or even reveal the key. Even attempting to mask it is difficult because you can the attack many times and see if a pattern emerges. An even more advanced version looks at cache misses.

Fault Attacks

Inducing errors in hardware (overclock, heat, voltage) can expose information about the key.

Linear and Differential Attacks

By xoring a known encryption against an unknown encryption a very small bias arises (~1/1E7). But through repeating the attack you can boost the probability to something meaningful and reveal the key.

Quantum Attacks

It's very difficult to simulate quantum mechanics on a classic (Turing) computer. So quantum mechanics may be performing calculations that are very difficult to perform on classic computer. In the example, a problem goes from taking time X on a classic computer to X^0.5 on a quantum computer. This destroys DES and bring AES-128 into a reasonable attack (but AES-256 is still safe).

AES

Choosen by NIST in 2000 as a new standard. Originally called Rijndael (rine-dall).

Key sizes: 128, 192, 256. Block size 128 bits.

AES is not a Feistel network, it is a Substitution-Permutation network. Key expansion maps a 16 byte key to 176 bytes.

It is possible to exchange size and speed by precomputing lookup tables.

AES is hardwired into most Intel and AMD chips.

There is a related key attack, but it's still impractical and you shouldn't use related

AES blocks are 16 bytes.

PRGs

Can we build a PRF from a PRG? Yes.

Week 2 : Using Block Ciphers

Review: PRPs and PRFs

• PRF: pseudo random function. F(K,X) → Y
• PRP: pseudo random permutation F(K, X) → X and there exists and efficient inversion

We are again try to show something along the lines of: a random choice from a smaller set is indistinguishable from a random choice in a much larger set.

Modes of Operation : OTK

Do not use a block cipher directly on data. If two blocks are the same in the message, they will be the same in the cipher. Add some reversible noise, by xoring of course.

Security for Many-Time key

A system that always produces the same cipher for a given key and message, that system cannot be semantically secure. So we add some random bits, which increases the cost.

One simple solution is to encrypt a random key and tack it on to the front of the message and use that for xoring.

Another solution is to include a nonce for both encryption and decryption. But we need to make sure it's never reused. The nonce can be transmitted in the open. We can also use a counter as a nonce, but if separate systems share a key, counters can result in collision.

Systems should be secure when nonce are chosen by the adversary, but the adversary must comply with whatever nonce standard is in place (for instance that all nonce be distinct).

Modes of Operation: MTK (CBC)

• CBC: cipher block chaining
• IV: initial value

We set IV (IV is not encrypted) and then use each the encryption of each block to mask the next block using xor. Note that xor happens inside E and outside D.

It is not secure if the attacker can predict IV. This was a bug in SSL/TLS1.1.

Another technicality is what to do if the last block isn't long enough. You need to pad the last block. We pad by repeating the number of bytes we padded. So if we had to pad 5 bytes, the padding is "55555". If the data does come out to end exactly on a block, we just add one more block.

CBC cannot be parallelized.

Modes of Operation: MTK (CTR)

CTR: Randomized Counter Mode (ctr=counter)

Again, IV is affixed to the front of the message. Each block (block n) is xor'd agains F(k,IV+n) where F is a PRF. This can be parallelized.

Counter mode only needs a PRF where CBC needs a PRP (more processing, more hardware). It has better security (can safely encrypt more blocks with the same key).

Week 3 : Message Integrity

Message Authentication Codes

 S(k,m) → tag
 V(k, m, tag) → bool
 V(k, m, S(k,m)) → true

CRC is designed to detect random, not malicious errors.

MAC is secure when an attacker cannot produce a valid tag for a new message, or a new tag for a previously signed message.

MACs based on PRFs

Self-evident theory about MACs

CBC-MAC and NMAC

Because AES is a PRF, we can use it generate a MAC.

Break the message down into AES sized blocks. Encrypt each block and XOR the output of the first block with the value of the second block, then encrypt that. And so on down the chain. This is a raw CBC, it is not secure. To make it secure we do an addition encryption at the end with an independent key.

For NMAC (nested MAC) we need a PRF whose output is in K (keyspace). We start with a predetermined key and input the key and first block of the message into F which gives us the key we use for the second block, and so on. Again, at the end we encrypt with and independent key. Because the key is generally smaller than the block, we append a fixed-pad to the output and do our final encryption.

MAC padding

Padding function must be invertible. We can do this by adding /10*/ to the end. Now we just read backwards until we hit the first 1 and remove that whole thing. If the message is a multiple of the block length, we need to add a block length.

An alternate (that avoids the dummy block) is to use 3 keys and having the last block encoded with a different key.

PMAC and the Carter-Wegman MAC

Same idea as sequential block encoding. Every block is XOR'd with P(k,i) where i is the block index. All the outputs are XOR'd and that final output is run through a PRF. The index is required, otherwise, order will not matter. And of course this can be done in parallel.

We need to keep the number of blocks encoded less than 1/|L|^.5 where L is the keyspace.

This also has the advantage that if only a few blocks in the message change, we can very quickly recompute the tag. We don't even need to keep the old block values around, using some XOR magic we can just decode the existing tag and compute the value of the new tags.

We can also do one-time MACs. These have similar advantage and disadvanges to a OTP. They are faster and more secure, but require a large key.

Carter-Wegman takes the OTM and converts it to a MTM. We take the OTM (very fast computation) then add a nonce and encrypt the output with a slower, more secure method. But the OTM was used against a large message and the encryption was used against the much smaller tag for an overall gain.

 CW( (k1,k2), m) = (r, F(k1, r) ⊕ S(k2,m))
 S: OTM
 r: nonce

Note that output is (r,t), not just the tag.

Week 3 : Collision Resistance

Intro

For any hash function where |M| >> |T| (via the pigeon hole principle) there will be many collisions. A collision resistant hash function says that for a given m, there is no efficient algorithm for finding another message that collides.

There's a proof showing that if a hash is collision resistant for small messages, it can be expanded to be collision resistant for larger messages.

Generic birthday attack

Let r0 to rn in {1 to B} be independent, identically distributed integers. Then

 n = 1.2 B^0.5 Pr[i != j, ri = rj] > .5

At as little as 2*B^0.5, we get into the range 90% chance of collision. And even at 0.5*B^0.5, we see collision rates of about 10%.

So there will always be an attack that runs in O(2^(n/2)).

The Merkle-Damgard Paradigm

Fixed IV. Cascade through a series of H (compression) functions, combining with one message block at each step. The padding is 100000... || message length, with 64 bits reserved for message length. We can show that if the small h functions are collision resistant, than the whole chain is collision resistant.

Constructing Compression Function

Davies-Meyer compression function: h(H,m) = E(m,H) ⊕ H

HMAC

Simply using S(k,m) = H(k||m) is not secure because it is subject to an extension attack.

We construct a MAC using H. It will be SHA256, as a bonus, it is a PRF.

 S(k,m) = H( k⊕opad, H(k⊕ipad||m) )

So it ends up looking a lot like NMAC.

Timing Attacks on MAC verification

When the == goes through and does bit-by-bit comparison, you can tell by timing how far in before the attack is incorrect. The simple solution is to make sure the compare always takes the same amount of time. One way to do this is to xor the messages byte-by-byte and collect the results (r) with r |= a ^ b. Then at the end compare result to 0. Be careful though, because an optimizing compiler, could unwire the whole thing.

We can also do a second hash operation and compare those two.

Don't write crypto yourself.

Week 4: Authenticated Encryption

Active attacks on CPA-secure encryption

Without integrity, you can't guarantee confidentiality. Goes through an example of changing the destination port of a web packet.

Definitions

An authenticated encryption system in decryption mode outputs plaintext as well as a symbol indicating if the message should be rejected.

Chosen ciphertext attacks

Very powerful adversary.

Constructions from ciphers and MACs

There are three obvious methods; encrypt-then-mac, mac-then encrypt and encrypt-and-mac. Of these, encrypt-and-mac is considered insecure and encrypt-then-mac is considered most secure. This also works well with network data because data can be encrypted, and the header can be plain-text, but still authenticated.

OCB is a method that allows encryption and mac to be combined in a single step, but is currently protected by patents.

The three current standards are GCM, CCM and EAX.

Case Study: TLS

Unidirectional keys (one for up, one for down) each with a counter (to prevent replay).

• CBC-AES 128
• HMAC-SHA1

When decryption fails, do not report why. This often leads to attack.

CBC Padding Attacks

By guessing the last block you can see if you're right based on what error you get.

Problem Sets

Week 2

In problem 3, "F'((k1,k2), x) = F(k1,x) when x != 0^n, k2 otherwise" is considered secure. I don't understand. I'm also confused about the problem. Does the attacker get to know X? Also, intuitively it seems that revealing any part of the key is insecure?

There was a problem about a 2-step Feistel network, I understood how to solve it, but not why the solution worked.

And question 5 I ended up making an educated guess. It involved a CBC where the nonce was encoded with the same key as the message and how to exploit this.