http://cryptome.org/
∩ - intersection ∪ - union ∀ - for all ∃ - there exists ∋ - contains as element ∈ - element of ≈ - almost equal to
fixed length ciphers
3DES AES
KEY EXpansion
round key
examples - data encryption standard
invertable
pseudo random function permutation
Suppose there are at most a total of n DVD players in the world (e.g. n=232). We view these n players as the leaves of a binary tree of height log2n.
1
K 0101 1101 0001 1100
M 1110 1010 1011 1000
C 1011 0111 1010 0100
Advesary can not distinguish between 2 messages, just guessing which one is which
Adv[A,E]| Pr[A(k xor m0)=1] - Pr[A(k xor m1)=1] | = ?
For b=0,1: Pr[Wb] == Pr[A(k xor m0)=1]
|Pr[R0] - Pr[R1]| = ADVss (A, OTP) = 0
|Pr[Wb] - Pr[Rb]| = ADVprg(B,G);
Short key -> Pseudo Random Generator
RC4 CSS eStream: salsa 20 - hardware and software - Seed - nonce
nonce - unique value never repeats
Books
Web Encryption HTTPS Wireless Encryption 802.11i WPA2, GSM, Bluetooth Disk Encryption EFS, TrueCrypt CD Encryption CSS, AACS
SSL / TLS 1. Handshake Protocol - Establish shared key using public-key cyrptography 2. Record Layer - Ensure confidentiality and integrity
Crypt is not - solution to bugs - solution to social engineering - reliable if its used improperly - something to do yourself
mix net - anonymous communication network
secure multi-party computation
magical applications - send an encrypted search to google, get a response without google knowing what you sent - zero knowledge
anything that can be done with trusted authority can be done without.
Zero knowledge - proof of knowledge - prove that you know the solution without giving knowledge
Anything that can be done with an trusted authority can be done without
Steps of introducing crypto primative 1. Specify threat model 2. propose construction 3. prove that in breaking through this crypto construction, they are solving a "hard problem" (problems that are extremely hard to solve)
Subsitution Cipher - substitute one key for another - caesar cipher (no key, shift by x) - Keyspace: |K| = 26! = 2^88 - Good keyspace, but breakable - vulnerable to Cypher Text Only Attack
one time pad Vernam cipher random numbers the entire length of the message key must be at least the length of the message - really fast - but hard to do, because keys are so long - if you can transfer the key securely, why not transfer the message that way?
Two Time Pad - is insecure - xor both encrypted messages with each other - get m1 xor m2 - MS-PPTP - leaks information, since it encodes one bit at a time - if one item is saved twice you can see what sections have changed
802.11b WEP - WEP sucks - Uses IV and K to create unique pseudo random - Two time pad occurs after 16m frames - reseting sets IV back to 0 - Uses PRG which is predictable if you use the same suffix - After you listen to a million frames you can get the key
Alternate for WEP - Concatinate message 1-3 xor PRG(k) - or - use PRG(k) to generate a series of keys for m1 m2 m3
Vigener Cipher
Rotor Machine
DES - Data Encryption Standard - keyspace 2^56 - blocksize 64 bits (encrypts 8 characters at a time) - 1974 - insecure today
AES - Advanced - 2001 - 128 bit
Salsa20 - 2008
CT (cypher text) should reveal no info about PT (plain text)
Perfect Secrecy Pr[ E(k,m0) = c] = Pr[ E(k,m1) = c]
PRG (Pseudo Random Generator)
Linear cong. generator - Two integers and prime glibc random() - does not produce unpredictable random numbers
Non Negligible
e ≥ 1/2^30 (likely to happen over gig of data)
Negligible e ≤ 1/2^80 (won't happen over life of a key)
U: Universe
n: how many bits
U = {0,1}^n
P: Probability Distribution
P: U -> [0,1]
∑P(x) = 1
Sum of the probability of elements occuring = 1
|U| : Size of the universe
Uniform Distribution
Event - subset of universe
Determanistic Algorythm - same everytime given same input
Random Algorythm - different everytime
Independence - Knowing A tells you nothing about B - Pr(A and B) = Pr(A) * Pr(B)
XOR - Very useful in crypto - Addition Mod 2
The Birthday Parodox
Cipher - Triple(Key, Message, Cypher) - Encryption Decryption Algorythms (algs) - D(k,E(k,m)) = m - Efficient (Runs in polynomial time, or in a certain time period) - E is randomized - D is Determanistic
C := E(k,m) = k XOR m
m: 011010010101 k: 111010110101 ct (cypher text): 100000100000
Both sides use same key
Frequency Letters - e 12.7 % - t 9.1 % - a 8.1 % - beyond that, letters show up roughly the same
Frequency of Pairs (digrams, trigrams) - "he" - "an" - "in" - "th" One Time Key - Email messages
Many Time Key - encrypting multiple files - more difficult to keep secure
prime numbers can not be broken down into equal pieces unbreakable
composite numbers can be broken down into equal pieces greater than 1
prime factorization find all prime numbers that can make up a number each number can be broken down to primes no two numbers share a factorization
probability divide the number of ways an event can occur, by all possible outcomes
sample space all possible outcomes
frequency stability found in random generation, not human generation means that 000 111 is just as likely at 010 101,
frequency analysis fingerprint of a language is the frequency of each letter
caesar cipher shift letters over by x 3 was the original rotation 1 out of 26 possibilities
rot (rotation) letter substitution rot13 - replace letter with the letter 13 letters later rot 13 can undo itself using the same rotation (reciprocal cypher / involution)
rot13 tr 'A-Za-z' 'N-ZA-Mn-za-m'
mod modulus - wrapping a ruler around a clock
polyslphabetic cipher shift letters based on a code word to break, figure out the length of the word, and find the frequency which matches the language
information leak repetition non uniform frequency distribution
stream cipher based on one time pad but generates numbers to the length of the message based on pseudorandom numbers, from a seed of a fixed length (128 bits for example)
perfect secret encryption is perfect if you can do no better than a guess
pseudo random instead of sharing the random sequence of numbers, share the seed middle squares method seed
period length before sequence repeats
one way function
modular arithmetic
Whitfield Diffie and Martin Hellman 1976 public-key asymmetric key 1978 - RSA (Ron Rivest, Shamir, Adleman)
ECDHE Elliptic Curve Diffie-Hellman Key Agreement Protocol
128 bit encryption 128 binary digit key
RC4 Ron's Code / Rivest Cipher Stream Cipher Algorithm
md5 by Rivest 32 character hexadecimal number 128 bits subject to collision
SHA1 by nsa 40 character hexadecimal number 160 bits
BCRYPT
Cypher Text Only Attack