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

${𝒦}:keyspace{ℳ}:messagespace$

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.