Below are my notes from when I originally took the Udacity course Applied Cryptography. At that time, I only took notes in Microsoft Word, so there was a real of lack of gifs. I’d go through and add some, but this is going to be a HUGE post and WordPress is really struggling to function. Honestly, I’m only adding this post for my own reference and to save my notes, so if I were you I’d go watch some Schitts Creek instead or take the class yourself! 🙂
Applied Cryptography
Description: Cryptography is about “secret writing”. In this class, we will introduce the mathematical foundations of cryptography and build programs to perform encryption. We will see how to use cryptography to solve important problem such as how to authenticate users, secure websites, and do computation without exposing up your data. We will also look at the things that can go wrong when cryptography is misused or implemented badly.
WEEK 1:
Symmetric Encryption
Sending messages when two people share a secret
WEEK 2:
Authentication
Using symmetric encryption to manage passwords securely
WEEK 3:
Asymmetric Encryption
Publickey cryptosystems
WEEK 4:
Publickey Protocols
Secure commerce, certificates
WEEK 5:
Digital Cash
How to make money from numbers alone
WEEK 6:
Secure Computation
Computing without exposing data
WEEK 7:
Wrapup
Problems cryptography can and cannot solve
Unit 1: Applied Crytography
Crytpo: secret
Graphy: writing
Cryptology: science of secrets (more appropriate name for course)
Examples:
Opening a door: secret is the shape of the key (can take a picture from several hundred feet away and it’s enough information to recreate key)
Playing poker: hands/cards are secret
Logging into your udacity.com account: email/password (fact you can hear audio of keyboard you can start figuring out password), want to store passwords securely
Doing a search: get redirected to https:// (CLS to encrypt search and protects web traffic)
Symmetric Cryptography and applications (both parties have the same key)
Alice and Bob
use same key for both encryption and decryption
Asymmetric Cryptography and applicationsL “public key cryptography” (keys to encrypt/decrypt can be different), can give away one key
Protocols that use both symmetric and asymmetric cryptography (asymmetric is expensive, uses big keys)
Don’t Implement Your Own Crypto: VERY CHALLENGING
Keys/Message Encryption Program output ciphertext
Can observe sidechannels like timing, power consumption, etc. –hackers would monitor all this and can be used to figure out the key
If you want to implement one, then use one from a library that has been proven correct and secure
Symmetric Cryptosystems: Encryption/Decryption use same key
Plaintext EncryptionCiphertext goes through insecure channel then goes into Decryption Plaintext
Kerckhoff’s Principle (1883)
if encryption and decryption functions are good, then they can be exposed and just need to keep keys secret
will need correctness and security properties
For any message and any key, when you encrypt a message with a key and then decrypt it with the key, you get the message
Problem with the third is that two values map to same message (0) because both use modulo and become 0
OneTime Pad: A Perfect Cipher (but very impractical)
XOR: “exclusive or” (+) + with a circle around it
XOR is basically the ‘odd man out’
Called a onetime pad is because you need a new key for each bit (or message)
Will pad bits with leading 0’s until get to length of pad
So pad length would be same as key value, and you XOR the message with the key to get the cipher
Frank Miller’s Codebook, 1882, onetime pads used in WWI, discovered by Steven Bellovin in 2011
Claude Shannon 19162001, father of information theory, did some of first theoretical work in cryptography: Communication theory of secrecy systems written during WWII (formally released in 1949)
Proving Security:
 Mathematical proof
 Reduction proof: some other problem that we have good reason to believe is hard, and that it’s comparable to that
 Very smart, highly motivated people tried to break it but couldn’t (usually the best we can do)
 Have 834 quadrillion possible keys: worst argument because # of keys is the upper bound but no lower bound on how easy it is to break cipher
Probability:
Omega: set of all possible outcomes (probability space)

Flipping a mathematical coin:
 Omega: Head, Tails
 Uniform distributioneach outcome is equally likely
 P: outcome maps to real number between 0 and 1 [0,1]
 P(H) = ½ P(T) = ½

Flipping a real coin:
 Omega: {H,T,E} (heads, tails, edge)
 P(H) = .49999
 P(T) = .49999
 P(E) = .00002

Sum of all probabilities in the probability space must be 1
 P(w) = 1
Event: A subset of outcomes from the distribution
Heads = {H}
Valid = {H,T}
P(A) = sum of P(w) probability of event “A” is the sum of all the outcomes in A of that set
1 – P(E) probability of valid events
Complementary Event Probability
Probability of event happening + Probability of event not happening = 1
Conditional Probability:
Definition: Given two events, A and B, in the same probability space, the conditional probability of B given that A occurred is:
P(BA)= P(AintersectedB)/P(A)
Use conditional Probability formula:
A = Valid, P(A) = .99998
B= Heads P(B) = 0.49999
P(A∩B) = .4999/P(A) .99998 = .5 P(A∩B) is probability of subset happening within probability space A
A ∩ B = {H, T} ∩ {H} = {H}
Perfect Cipher:
The ciphertext provides an attacker with NO additional information about the plaintext
One key for one ciphertext/message pair
P(m=m*) probability of picking message
P(k=k*) probability of picking key this is 1/k (or, one out of total size of k)
So P(m=m*) * P(k=k*) can be reduced to P(m=m*)/k
P(Ek(m) = c) = 1/k
P(m=m*Ek(m)=c)=p(mm*)/k
This is the proof showing that the onetime pad cipher does not give away ANY clues to original message, can’t learn anything new about message of c, but could modify it (active attacker) and turn it into c’ (c prime) and it would decrypt into m’
Problems:
Malleable (active attackers)
Impractical: need a new key for each message k = m
Shannon’s Theorem: If a cipher is perfect, it must be impractical: k >= m, need at least as many keys as messages
Proof by contradiction:
Suppose E is a perfect cipher where M > k (number of possible messages is greater than number of possible keys)
Let C0EC (c0 is an element of possible ciphertexts) with P(Ek(m)=C0) >0 (probability that a message and key get encrypted to this ciphertext is greater than 0)
Decrypt C0 with all kEK (all keys in possible keys)
D is the decryption function
Dk(Ek(m)) = m
M0=Union set of all possible keys Dk(c0) brute force
M0<=k (could map to all possible keys, but might not be equal)
M0 < M know that size of M0 must be under size of M
Some message (m*) in M that can’t be in M0
Reached a contradiction, thus, there exists no perfect ciphers where M > k
Meaning even if attackers know nothing about key, there are some possibilities that can eliminate some of the possible messages, every cipher that’s practical must be imperfect
Breaking Lorenz: How allies were able to break Lorenz cipher that was used by Nazis to communicate between cities
5 bits can encode 32 symbols
Used paper tapes to have the keys (difficult to transport this amount of tape)
Lorenz Cipher Machine, instead of having paper tape with all the keys, you have a machine that would attempt to produce a good sequence of key bits (impossible for machine to produce random)
Since used in the capitals and not in field (like Enigma machines), didn’t feel like allies would ever get ahold of the machine (started to be used in August 1941)
Col John Tiltman – Determined 4000letter key intercepts
Able to determine how the key was created by the machine (took 6 months)
K wheels turned every bit (every character was turned into 5 bits), but S wheels would only turn based on M2 value is a 1 (all S would turn at same time)
M1 turned every time, M2 turned depending on result of XOR
Zc,i (c= channel, i=letter)
Probability of the Delta is equal to 0
Delta S is 0 when S wheels don’t advance, and when they do advance half the time they will advance to 0, meaning will be .73 0
Delta M message letters are the same which make them not advance, 3.3% are diagraphs are repeated, .61 to be 0
Delta K advances each time regardless so it will be ½ (as long as keys have equal 0’s and 1’s)
41 positions for fist wheel and 31 for second, meaning 1271 configurations for K wheels
5000 letters X 1271 configurations x 7 XORS for Delta Z0,I XOR Delta Z1,I = 44.5 million (at most), probably 25 Million XORS for one cipher text on average
Modern processors can do multiple instructions at one time, running at GHz, can process up to 32/64 XORs at once
Heath Robinson—named after British Cartoonist (18721944):
August 1941 –first operator mistake intercepted
December 1942decide to build machine (enough to learn structure of machine)
April 1943first machine delivered
2000 characters per second (20 km per hour)
7 XOR operations each ½ ms
Built faster machine by January 1944 called Colossus:
Electronic Keytext Generator replaced paper tape, ciphertext was still on paper tape
Military cryptography is different than academic, don’t want enemy to know you cracked their cipher so they keep using it so you don’t publicize that you cracked the code
Learned locations of enemies for DDay
Goal of cipher: hide statistical properties of message and key (generated key, want it to be “perfectly random”)
Goal of cryptanalyst: find statistical properties in ciphertext and use those to break key/message (found this by looking across channels due to mechanical weakness of all S wheels moving or not moving, found patterns of 1271 characters instead of millions of random patterns—considered a mathematical weakness, lots of hard work to figure this out, motivation helps like fear country is under attack)
Modern Symmetric Ciphers:
Very few need to implement a cipher, should use library ciphers
 Stream – stream of data and cipher can encrypt small parts at a time (1 bit)

Block – data in larger chunks is encrypted at once (64/128/256 bits is standard block size)

AES: Advanced Encryption Standard (128 bits)
 US National Institute of Standards and Technology (1997) winner of contest to replace DES as previous recommended cipher

15 submissions, some broken or rejected, 5 finalists and winner was AES
 Security of cipher: actual # of rounds / max # “breakable” (anything that showed you could reduce the search space for that round was viewed as unsecure)
 Speed –ease of implementation
 Simplicity
 Rinjdael, called AES because hard to say Rijndael
 128bit keys = 2^127 bruteforce attack and best known in 2012 is 2^126.1 (removes less than 1 bit)

How it works
 Shifts data

Sboxes (nonlinearly)
 Takes in 8 bits, and has a lookup table (256 entries) mapping each set of 8 bits to another and make sure there are no patters
 XORs using round key
 Basically scramble data using Shifts/Sboxes, then XOR and repeat this as many times as the round key specifies

AES: Advanced Encryption Standard (128 bits)
Perfectly random key that is longer than message size, then you get a perfect cipher (one time pad), which is impractical
Cryptanalysis of Lorenz able to break
Modern take advantage of computing power and new ideas of how to scramble data to create more confusion to make it more difficult for cryptanalysts from breaking code
C1: 1010110010011110011111101110011001101100111010001111011101101011101000110010011000000101001110111010010111100100111101001010000011000001010001001001010000000010101001000011100100010011011011011011010111010011000101010111111110010011010111001001010101110001111101010000001011110100000000010010111001111010110000001101010010110101100010011111111011101101001011111001101111101111000100100001000111101111011011001011110011000100011111100001000101111000011101110101110010010100010111101111110011011011001101110111011101100110010100010001100011001010100110001000111100011011001000010101100001110011000000001110001011101111010100101110101000100100010111011000001111001110000011111111111110010111111000011011001010010011100011100001011001101110110001011101011101111110100001111011011000110001011111111101110110101101101001011110110010111101000111011001111
C2: 1011110110100110000001101000010111001000110010000110110001101001111101010000101000110100111010000010011001100100111001101010001001010001000011011001010100001100111011010011111100100101000001001001011001110010010100101011111010001110010010101111110001100010100001110000110001111111001000100001001010100011100100001101010101111000100001111101111110111001000101111111101011001010000100100000001011001001010000101001110101110100001111100001011101100100011000110111110001000100010111110110111010010010011101011111111001011011001010010110100100011001010110110001001000100011011001110111010010010010110100110100000111100001111101111010011000100100110011111011001010101000100000011111010010110111001100011100001111100100110010010001111010111011110110001000111101010110101001110111001110111010011111111010100111000100111001011000111101111101100111011001111