Crypto 4

How could you break 2-DES with just 10 plaintext/ciphertext pairs in about 56(2^56) time?
Meet-in-the-Middle!
2-DES key is (k^i, k)
Build a table 2
Sort the table in n log n or in this case 56 2^56
The attack is time efficient but requires about 2^56 of space
"effective" key-length of 2-DES <= 62 bits any key size over 90-bits is considered secure The improvement of sorting in n log n is at the heart of reducing algorithmic time Linear & Differential attacks Basic idea of linear cryptanalysis Probability that a given message bit XOR'd with the ciphertext = 1/2 = some episilon Keep trying to cut an exhaustive search by factors of 2 What is the significance of the 5th S-box beeing chosen poorly? What does this bias allow an attacker to do? You can deduce 14 bits of information about the key 56 -14 = 42 bits of the key left to do an exhaustive search on Anyone releasing a cipher today has to prove it's not vulnerable to linear cryptanalysis Attacks on Implementation Power cryptanalysis What was Paul Kocher's insight around hardware power fluctuations? AES 128-bit block size and variable key sizes of 128, 192, 256-bits How could a quantum computer break a block cipher in 2^(n/2)? 2 4X4 matricies; one for the key and one for the state info AES 4 invertible steps:

1. byte substitution
2. shift row
3. mix columns
4. add key

Iterate 10 times...

2 Theoretical Goals

1. Abstract model for Block Ciphers
2. Argue that CBC and counter-mode are secure

PseudoRandomPermutation (PRP) versus Secure PRP

Assume AES and 3DES are secure and just focus on PRP

Crypto 3

Block Ciphers
Much stronger than stream ciphers
Warning: Don't develop your own ciphers under any circumstance
Encrypts one message block at a time into a same size block as the original message block
Data Encryption Standard (DES) is popular with public sector and FIs
a bit of history...
1967 - Feistel developed Lucifer using a 128-bit key length
1972 - NBS issues RFP
IBM develops DES with a shorter 56-bit key and a 64-bit message block
1979 - DES phased out
2000 - NIST adopts AES
Idea behind DES is the Feistel network
Feistel network also influenced IDEA, RC5, Skipjack...
No swap on the last round
Each round only half of the previous round's plaintext gets encrypted
Write a recursive definition of a Feistel network
Prove that Feistel network is one-to-one, i.e. invertible
Proof: Construct the inverse
Take Fd and derive Ld-1. Rd is already equal to Rd-1
Feistel network inverts itself!!!
DES is a 16 round Feistel network using a 64-bit block so LHS na RHS are 32-bits each
DES was meant to be implemented in hardware, not in software
Most ATMs that FIs use are validate pins using DES
What do the S-boxes in DES signify?
Is there an S-box attack on DES?
What is the madness behind the choice of S-boxes' values?

Algortithm Performance (source Wei Dai)
Environment: Pentium 4, 2.1Ghz running Windows XP SP1
RC4 runs in about 113MB/second
SEAL runs in about 293MB/second
DES runs in about 21MB/second
3DES runs in about 61MB/second
IDEA runs in about 19MB/second
SHACAL-2 runs in about 20MB/second

Electronic Code Book (ECB) - break a message into blocks and encrypt each block separately
Ciphertext will be the same size as the plaintext
Deterministic constructions are problematic
i.e. send the same e-mail message twice and the attacker will see the same ciphertext twice which allows the attacker to learn info
ECB inherently leaks information
Recall Bart Preneel's photo example with a sillohuette revealed in the ciphertext
NEVER USE ECB to do encryption

Cipher Block Chaining (CBC)
CBC is a better method than ECB
DES uses CBC
XOR the Initial Value (IV) with the first block of plaintext
C1 is then XORd with P2...
Ciphertext will be a little longer than the plaintext
IV must be new and random for every message - non-deterministic
CBC encryption is inherently sequential which is problematic for high-end network device implementations i.e. harware VPNs
CBC provides no integrity for the ciphertext
With CBC, decryption is just as easy as encryption
Could use counter-mode to turn block cipher into a stream cipher to solve sequential encryption problem; counter-mode is making the encryption parallel
Still no ciphertext integrity guarantee

Output FeedBack mode (OFB)
Another mode of encryption; don't use it

Attacks on block ciphers
Exhaustive search - try every key
Recall RSA's DES Challenge
1997 Challenged solved in 3 months using distributed.net
1998 EFF paid Paul Kocher to develop DeepCrack. DES broken in 3 days
1999 Combined Search broke DES in 22 hours -- The death of DES
Never use a 56-bit cipher

3-DES uses 186-bit keys
AES uses 128, 143, 256-bit keys
128-bit key would be 2^72 harder to break than a 56-bit key and therefore not subject to exhaustive search attacks

What attacks would be better for 3-DES?
Why not use 2-DES?

Crypto 2

Stream Ciphers
Why do you replace the "random pad" with a "Pseudo-random pad"?
Why is PRG a deterministic function? Does it have to be deterministic? What if you chose a non-deterministic function.
What is the unpredictability property? Given the first i bits of output, could an adversary guess the next i+1 bit?
What is meant by "semantic security"?
Don't use the UNIX PRG for crypto.
Does SSL give you a new stream cipher key for every connection?
Why are stream ciphers so fast?
What is the difference between a "strong cipher" and a "fast cipher"?
Why do you have to completely re-encrypt a file after making even a small change to the file?
What is meant by "highly malleable"?
How can you guarantee the integrity of your CipherText?

RC4
Simply elegant!!!
How could you predict the next byte given a segment of data?
What RC4 attacks exist?
What is the probability that the second byte of the output is zero?
What other bytes have some inherent bias?
Would there be any bias if you ran the s-array through 256 cycles before using its output for RC4?
What is the probability of seeing two consecutive zeroes in the output?
How is RC4 used in (read incorrectly) 802.11b WEP?
Why shouldn't you use CRC for integrity checking?
Look at Fluhrer-Mantin-Shamir (2001)
Look at WEPCrack
Need to get to 802.11i

Hardware Stream Ciphers
What is an Linear Feedback Shift Register (LFSR)?
How is a single LFSR predictable?
Why is LFSR easy to break given about a kb of plaintext and a kb of ciphertext?

Crypto 1

Chad Salinas Crypto Notes

• If you haven't done so already, take a look at the Java Crypto Extensions (JCE).
• SSL takes about 5 quick round of session setup to produce a shared key.
• Shared key relies upon symmetric ciphers for privacy and integrity.
• DES, AES, RC5... provide confidentiality
• HMAC provides integrity.
• Crypto is used with Windows' Encrypted File System.
• Crypto is used in authorization and password management.
• Wireless, 802.11b, uses the poorly designed WEP for Crypto.
• Avoid "Security by Obscurity".
• Read "The CodeBreakers" by David Kahn to get the history of Crypto.
• Ciphers - i.e. Encryption happens like this C = E(k, m)

Substitution cypher
- is the world's oldest cipher where K = 26!
26! ~= 2^88
Encrypting plaintext with the substitution m = "bcza"
Ciphertext C = E(k, m) ...
Of course, you can break substitution cyphers by noting letter frequecies i.e. "e" occurs 12.7% of the time ., "t" = 9.1%, "a" = 8.1%
By extrapolation, you can look at frequency of doubles, i.e "th", "he", "an",...
The only thing an attacker would need to know is the cyphertext.

Vigener Cipher
Replicate the secret key over the message until the entire message is covered.
Secret Key: CRYPTOCRYPTOCRYPTOCRY
Message: Chad Salinas Tech+Finance Blog
________________________________
CipherText:
Easy to break by looking at the 6th letter in the ciphertext and do the same sort of frequency analysis as with substitution cypher.
Think about the intial configuration of the rotors of an enigma machine.
Natural languages have a fair amount of natural redundancy.

DES
The commercial world needed to wait until DES came out in 1974 for the first "good" crypto.

Cipher is a pair of efficient algorithms takes a key and a message and outputs a CipherText.
Constraint is that encryption and decryption are inverse functions.
nb. Encryption algorithm is often randomized where as decryption algorithm is ALWAYS deterministic.

"Secure" Cipher - One Time Pad (OTP) 1917
C = E(k, m) = m XOR K
D(k, C) = K XOR CT
The problem is that the keys, being comprised of 0's and 1's, are too long.
What is a "good" cipher?
Claude Shannon (1949), the father of information theory, defined what constitutes a "good" cipher. CipherText (CT) does not reveal any information about the PlainText (PT).
Given a CT, no adversary can if the message came from m1 or m2. C is equally likely from m1, m2.
What about length of messages? OTP encrypts fixed-length messages... a bit of a disclaimer.
Lemma: OTP has perfect secrecy.
Proof: Pr[ E(K, M0) = C] = ((# of keys k encrypting to C) / (Total key space))
...
Only 1 key maps m to C!

Does a cipher exist that has smaller keys?
K >= 2^n
key length >= message length

Enter the Stream Cipher!
Leverage a pseudo-random pad as opposed to OTP
Run the key through a pseudo-random-generator (PRG)
PRG(k) => result
XOR the result with the message to get the CT
PRG is a deterministic public function.
You cannot use Two-Time Pad as adversaries can XOR two messages together and recover m1 and m2... completely broken.

Problems with the OTP and Stream Ciphers:
Maleability Attack