Python, Udacity Class

Udacity Classes 8: Applied Cryptography

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
Public-key cryptosystems

WEEK 4:

Public-key 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:

Wrap-up
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 side-channels 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

One-Time Pad: A Perfect Cipher (but very impractical)

XOR: “exclusive or” (+) + with a circle around it

XOR is basically the ‘odd man out’

Called a one-time 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, one-time pads used in WWI, discovered by Steven Bellovin in 2011

Claude Shannon 1916-2001, 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:

  1. Mathematical proof
  2. Reduction proof: some other problem that we have good reason to believe is hard, and that it’s comparable to that
  3. Very smart, highly motivated people tried to break it but couldn’t (usually the best we can do)
  4. 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)

  1. Flipping a mathematical coin:
    1. Omega: Head, Tails
    2. Uniform distribution-each outcome is equally likely
    3. P: outcome maps to real number between 0 and 1 [0,1]
    4. P(H) = ½ P(T) = ½
  2. Flipping a real coin:
    1. Omega: {H,T,E} (heads, tails, edge)
    2. P(H) = .49999
    3. P(T) = .49999
    4. P(E) = .00002
  3. Sum of all probabilities in the probability space must be 1
    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(B|A)= 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(m-m*)/|k|

This is the proof showing that the one-time 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 4000-letter 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 (1872-1944):

August 1941 –first operator mistake intercepted

December 1942-decide to build machine (enough to learn structure of machine)

April 1943-first 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 D-Day

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

  1. Stream – stream of data and cipher can encrypt small parts at a time (1 bit)
  2. Block – data in larger chunks is encrypted at once (64/128/256 bits is standard block size)
    1. AES: Advanced Encryption Standard (128 bits)
      1. US National Institute of Standards and Technology (1997) winner of contest to replace DES as previous recommended cipher
      2. 15 submissions, some broken or rejected, 5 finalists and winner was AES
        1. Security of cipher: actual # of rounds / max # “breakable” (anything that showed you could reduce the search space for that round was viewed as unsecure)
        2. Speed –ease of implementation
        3. Simplicity
      3. Rinjdael, called AES because hard to say Rijndael
      4. 128-bit keys = 2^127 brute-force attack and best known in 2012 is 2^126.1 (removes less than 1 bit)
      5. How it works
        1. Shifts data
        2. S-boxes (non-linearly)
          1. 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
        3. XORs using round key
        4. Basically scramble data using Shifts/S-boxes, then XOR and repeat this as many times as the round key specifies

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

Leave a Reply