Lecture 3: Cryptography
Fundamentals
CS 3923/6813: Computer Security
Summer 2017
[*] Slides based upon materials maintained by Justin
Cappos at NYU
Cryptography
●Etymology: Secret (Crypt, from Greek ‘κρύπτος’)
Writing (Graphy)
●Study of mathematical techniques to achieve various
goals in information security, such as confidentiality,
authentication, integrity, non-repudiation, etc.
●Not the only means of providing information security,
rather a subset of techniques.
●Quite an old field!
Cryptography: Cast of Characters
●Alice (A), Bob (B), Charlie (C): communicating
parties
●Eve (E): Eavesdropping (or passive) adversary
●Mallory (M): Man-in-the-Middle (or active)
adversary
○People often use Eve for this as well
●Trent (T): a trusted third party (TTP)
Common Terminologies
●Plaintext
●Key
●Encrypt (encipher)
●Ciphertext
●Decrypt (decipher)
●Cryptanalysis (codebreaking)
Open vs Closed Design
● Closed Design (as was followed in military
communication during the World War I/II)
○ Keep the cipher secret
○ Also sometimes referred to as the “proprietary design”
● Open Design (Kerckhoffs' principle)
○ Keep everything public, except the key
○ Good practice – this is what we focus upon!
Brute Force Attacks: Key Recovery
● Since the key space is finite, given a pair of plaintext and
ciphertext, a cryptanalyst can try and check all possible
keys.
● For above to be not feasible, key space should be large!!
○ How large?
○ Large enough to make it impractical for an adversary. But what
is impractical today, may not be so tomorrow. At least 280 – see
this paper on “selecting cryptographic key sizes”
■ http://www.win.tue.nl/~klenstra/key.pdf
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Private Key/Public Key Cryptography
●Symmetric Key / Private Key: Sender and
receiver share a common (private) key
○ Encryption and Decryption is done using the private key
○ Also called conventional/shared-key/single-key cryptography
●Asymmetric Key / Public Key: Every user has a
private key and a public key
○ Encryption is done using the public key and Decryption using
private key
○ Also called two-key cryptography
Symmetric / Private key model
Private Key Encryption: Main Functions
1.Generate a key: KeyGen(L) -> K
○ (L is a security parameter that represents
the length of the key)
2.Encrypt: Enc(K,M) -> C
3.Decrypt: Dec(K,C) -> M
Caesar Cipher (or Shift Cipher)
●Substitution cipher
●Replace each letter in the plaintext by a letter some
fixed number of positions down the alphabet
●Example - left shift of 3/right shift of 23:
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW
Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY
DOG
Caesar Cipher (or Shift Cipher)
●Substitution cipher
●Let messages be all lower case from a through z (no
spaces or punctuation).
●Represent letters by numbers from 0 to 25.
●Encryption function:
Ci = E(Pi ) = Pi + K (mod 26), where K is secret key
●Decryption is:
Pi = D(Ci ) = Ci - K (mod 26)
Security of Caesar Cipher
●Easy to brute force: size of key-space is 26
One Time Pad – Unconditional
Security.
● Plaintext is binary string and key is binary string of equal length then encryption
can be done by a simple xor operation.
Plaintext: 01010000010001010011
Key: 11010101001001100111
Ciphertext: 10000101011000110100
● If the key is random and is not re-used, then such a system offers
unconditional security – perfect secrecy!
● Intuitively perfect secrecy can be seen from the fact that given any plaintext and
ciphertext, there is a key which maps the selected plaintext to the selected
ciphertext. So given a ciphertext, we get no information whatsoever on what
key or plaintext could have been used.
● How do we obtain “random” bit-strings for shared secret keys?
● System is not practical.
● Interesting point in the design space
DES – Data Encryption Standard
● Encrypts by series of substitution and transpositions.
● Based on Feistel Structure
● Worldwide standard for more than 20 years.
● Has a history of controversy.
● Designed by IBM (Lucifer) with later help (interference?)
from NSA.
● No longer considered secure for highly sensitive
applications.
● Replacement standard AES (advanced encryption standard)
DES – Overview (Block Operation)
(skip)
DES – Each Round
(skip)
DES – Function F
(skip)
(skip)
Operation Tables of DES (Key Schedule,
PC-1, PC-2)
(skip)
Operation Tables (IP, IP-1, E and P)
(skip)
S-boxes: S1 (as an example)
1000 1001 1010 1011 1100 1101 1110 111101110110010101000011001000010000
Is the table entry from
11
10
01
00
(skip)
S(011001) XOR 6d XOR 0110
DES Decryption
Same as the encryption algorithm with the
“reversed” key schedule – NEXT!
(skip)
(skip)
(skip)
DES Security
●S-Box design not well understood (secret).
●Has survived some recent sophisticated attacks
(differential cryptanalysis)
●Key is too short. Hence is vulnerable to brute
force attack.
●1998 distributed attack took 3 months.
●$1,000,000 machine will crack DES in 35 minutes
– 1997 estimate. $10,000 – 2.5 days.
DES Cracking machine
Triple-DES
●Applies DES three times to each block.
● “Key bundle”: 3 DES keys K1, K2, K3
● Decryption is the reverse
● Security:
○ if all three keys are independent → 168-bit long
key → brute-force attacks more difficult
Advanced Encryption Standard
(AES)
● National Institute of Science and Technology
○ DES is an aging standard that no longer addresses today’s needs for
strong encryption
○ Triple-DES: Endorsed by NIST as today’s de-facto standard
● AES: The Advanced Encryption Standard
○ Finalized in 2001
○ Goal – To define Federal Information Processing Standard (FIPS) by
selecting a new powerful encryption algorithm suitable for encrypting
government documents
○ AES candidate algorithms were required to be:
■ Symmetric-key, supporting 128, 192, and 256 bit keys
■ Royalty-Free
■ Unclassified (i.e. public domain)
■ Available for worldwide export
Symmetric / Private key Ciphers and their
applications
●IDEA (used in PGP)
●Blowfish (password hashing in OpenBSD)
●RC4 (used in WEP), RC5
●Double DES, Triple DES
●SAFER (used in Bluetooth)
●AES (pervasive)
Private Key Encryption: Key Points
1.KeyGen: KeyGen(L) -> K
○(L is a security parameter that represents
the key length)
2.Encrypt: Enc(K,M) -> C
3.Decrypt: Dec(K,C) -> M
Also know one time pad!
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Symmetric key cryptography revisited
● Good: Efficient
● Bad: Key distribution and management is a serious problem
– for N users O(N2) keys are needed
Asymmetric cryptography model
● Good: Key management problem potentially simpler
● Bad: Much slower than symmetric / private key crypto
Public Key Encryption
● Two keys:
○ public encryption key e
○ private decryption key d
● Encryption easy when e is known
● Decryption easy when d is known
● Decryption infeasible when d is not known
“Textbook” RSA: KeyGen
● Alice wants people to be able to send her encrypted messages.
● X mod Y
● She chooses two (large) prime numbers, p and q and computes
n=pq and \phi(n). [“large” >= 512 bits]
● She chooses a number e such that e is relatively prime to and
computes d, the inverse of
e in (i.e., ed =1 mod \phi(n))
● She publicizes the pair (e,n) as her public key.(e is called RSA
exponent, n is called RSA modulus). She keeps d secret and
destroys p and q.
● Plaintext and ciphertext messages are elements of Zn and e is
the encryption key.
RSA: Encryption
●Bob wants to send a message x (an element of
Zn
*) to Alice.
●He looks up her encryption key, (e,n), in a
directory.
●The encrypted message is:
y = E(x) ≡ xe mod n
●Bob sends y to Alice.
(skip)
RSA: Decryption
●To decrypt the message:
she’s received from Bob, Alice computes:
D(y) ≡ yd mod n
Claim: D(y) = x
(skip)
y = E(x) ≡ xe mod n
RSA example.
●Let p = 47, q = 71. Then n = 3337 and
(pq) ≡ 46*70 = 3220
●Choose e = 79. Then d = 79-1 mod 3220 = 1019.
●Let message = 688232… Break it into 3 digit
blocks to encrypt.
●E(688) = 68879 mod 3337 = 1570.
E(232) = 23279 mod 3337 = 2756
●D(1570) = 15701019 mod 3337 = 688.
D(2756) = 27561019 mod 3337 = 232.
(skip)
Security of RSA: RSA assumption
●Suppose Eve intercepts the encrypted message y
that Bob has sent to Alice.
●Eve can look up (e,n) in the public directory (just as
Bob did when he encrypted the message)
● If Eve can compute d = e-1 mod n then she can use it
to recover the plaintext x.
● If Eve can compute factor n into p and q, she can
compute d (the same way Alice did).
○Factoring large numbers is hard.
How big should n be?
●Today we need n to be at least 2048-bits
○ This is equivalent to security provided by 160-bit long keys in
private-key crypto
●RSA (and other asymmetric crypto)
is comparatively slow
Asymmetric / Public key crypto
algorithms
●RSA
●DSA
●ElGamal
●Pailliar (Homomorphic)
●Cramer-Shoup
Asymmetric / Public key crypto
summary
Key Points
● Keygen(L) -> Kpub, Kpriv
● E(Bpub, M) -> C
● D(Bpriv, C) -> M
● Can't compute Bpriv given Bpub!!!
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Cryptographic Hash Functions
●Requirements of cryptographic hash functions:
○ Can be applied to data of any length.
○ Output is fixed length
○ Relatively easy to compute h(x), given x and
deterministic
○ Infeasible to get x, given h(x). One-wayness property
○ Given x, infeasible to find y such that h(x) = h(y).
Weak-collision resistance property.
○ Infeasible to find any pair x and y such that h(x) = h(y).
Strong-collision resistance property.
Hash Output Length
● How long should be the output (n bits) of a cryptographic hash function?
● To find collision - randomly select messages and check if hash matches
any that we know.
● Throwing k balls in N = 2n bins. How large should k be, before probability
of landing two balls in the same becomes greater than ½?
● Birthday paradox - a collision can be found in roughly sqrt(N) = 2(n/2)
trials for an n bit hash
○ In a group of 23 (~ sqrt(365)) people, at least two of them will have the
same birthday (with a probability > ½)
● Hence n should be at least 160
Generic Hash Function
(skip)
(skip)
(skip)
(skip)
(skip)
(skip)
(skip)
(skip)
(skip)
(skip)
Other Hash Functions
●Many other hash functions
○SHA-2 (SHA-256)
○MD5 – Message Digest algorithm 5
■Very similar to SHA
○MD4
○MD6
○..
Current Security of MD5 and SHA-1
● SHA-1
○ B’day attack requires 280 calls
○ Faster attacks 269 calls
http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf
● MD5
○ Output is 128-bits, so B’day attack requires 264 calls only
○ Faster attacks to find a collision:
http://eprint.iacr.org/2004/199.pdf
● Better use stronger versions, such as SHA-256
● Although, these attacks are still not practical – they only find
two random messages that collide
Cryptographic Hash Functions
Key Points
●h(x) -> hash
○hash is fixed length (16,20,32 bytes)
○h(x) is fast / cheap
●given hash, cannot compute x
●Given x, cannot find y so that h(x) == h(y)
●Cannot find any x,y so that h(x) == h(y)
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Random Number Generation
● Could be as simple as dice, coin flipping, the shuffling of
playing cards etc.
● A sequence of random numbers, R1, R2, R3, must have
two important properties:
Uniformity, i.e. they are equally probable everywhere
○ Independence, i.e. the current value of a random
variable has no relation with the previous values
● Problem - Most methods fail to produce true random
numbers
● Solution- Pseudorandom number generator
Pseudorandom number generator
● An algorithm for generating a sequence of numbers that
approximates the properties of random numbers.
● The sequence is not truly random in that it is completely
determined by a relatively small set of initial values, called
the PRNG's state, which includes a truly random seed
● A PRNG suitable for cryptographic applications is called a
cryptographically secure PRNG (CSPRNG).
● A requirement for a CSPRNG is that an adversary not
knowing the seed has only negligible advantage in
distinguishing the generator's output sequence from a
random sequence.
Random Number Generation
Key Point:
●Given a sequence of values from the
CSRNG, cannot guess the next value!
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Ensuring Integrity+Authentication
through Digital Signatures
●Message Integrity
○ Detect if message is tampered with while in the transit
●Source/Sender Authentication
○ No forgery possible
●Non-repudiation
○ If I sign something, I can not deny later
○ A trusted third party (court) can resolve dispute
Public Key Signatures
●Signer has public key, private key pair
●Signer signs using its private key
●Verifier verifies using public key of the signer
RSA Signatures
●Key Generation: same as in encryption
●Sign(m, kpriv): s = m
d mod N
○"Encrypt" with a private key
●Verify(m, s, kpub): (s
e == m mod N)
○Conceptually, just decrypt / compare
●The above text-book version is insecure
● In practice, we use a randomized version of RSA
○ Hash the message and then sign the hash
Simplified Digital Signature Example
●Alice wants to send a message M to Bob.
●Alice will compute the secure hash of M
○ hash(M) -> h
●Alice encrypts this hash with her private key
○ sign(h, Apriv) -> s
●Alice sends M and s to Bob
●Bob computes the secure hash of M
○ hash(M) -> h
●Bob verifies the signature
○ verify(M, s, Apub)
■ assert dec(s, Apub) == h
Further reading: MAC / HMAC
●Developed as part of IPSEC - RFC 2104. Also
used in SSL etc.
●Key based hash but almost as fast as non-key
based hash functions.
●Avoids export restrictions unlike DES based MAC.
●Provable security
●Can be used with different hash functions like
SHA-1,MD5, etc.
Digital Signatures Summary
●Uses the constructs before
●Sign(m, kpriv): s = m
d mod N
○"Encrypt" with a private key
●Verify(m, s, kpub): (s
e == m mod N)
○Conceptually, just decrypt / compare
●Provides non-repudiation, integrity
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Classic cryptography
● Encryption algorithm is known
○ keys are kept secret
● Breaking the system is hard due to large number of
possible keys
● For a key 256 bits long there are 2256 = 1076 keys to
check for brute force.
Elements of the Quantum Theory
● Light waves are propagated as discrete quanta
called photons.
● They are massless and have energy, and angular
momentum called spin (diagonal, vertical and
horizontal).
● Spin carries the polarization.
● If on its way we put a polarization filter a photon
may pass through it or may not.
● We can use a detector to check of a photon has
passed through a filter.
Photon polarization
Binary Information
● Each photon carries one qubit of information
● Polarization can be used to represent a 0 or 1.
● In quantum computation this is called qubit.
● To determine photon’s polarization the recipient
must measure the polarization by passing it
through a filter.
Binary Information
● A user can suggest a key by sending a stream of
randomly polarized photons.
● This sequence can be converted to a binary key.
● If the key was intercepted it could be discarded
and a new stream of randomly polarized photons
sent.
Main Contribution
● Unconditionally secure key distribution method
proposed by: Charles Bennett and Gilles Brassard in
1984.
● The method is called BB84.
● Once a key is securely received it can be used to
encrypt messages transmitted by conventional
channels
Quantum key distribution (QKD)
(a) Alice communicates with Bob via a quantum
channel sending him photons.
(b) Then they discuss results using a public
channel.
(c) After getting an encryption key Bob can encrypt
his messages and send them by any public
channel.
Example of key distribution
Security of quantum key distribution
● Quantum cryptography obtains its fundamental
security from the fact that each qubit is carried by a
single photon, and each photon will be altered as
soon as it is read. This makes impossible to
intercept message without being detected.
● Since physics is used to create the key, there's little
chance it can be cracked using mathematics.
Read more here:
http://science.howstuffworks.com/science-vs-myth/everyday-myths/quantum-cryptology.htm
Another Emerging Topic:
Homomorphic Encryption
● Allows specific types of operations Op on ciphertext
and obtain an encrypted result which decrypted
matches the result of operations performed on the
plaintext P:
○ Op(P) = D(Op’(E(P)))
● With AND and XOR we can represent any operation
● In RSA, multiplication is accidentally a
homomorphism:
Homomorphic Encryption
Application - Cloud:
○ Encrypt my data before sending to the cloud
○ While still allowing the cloud to search/sort/edit/…
this data on my behalf
○ Keeping the data in the cloud in encrypted form
○ Without needing to ship it back and forth to be
decrypted
○ Encrypt my queries to the cloud
○ While still allowing the cloud to process them
○ Cloud returns encrypted answers - that I can decrypt
Outline
● Symmetric / Private Key cryptography
● Asymmetric / Public Key cryptography
● Hash functions
● Cryptographically suitable pseudorandom number generation
● Putting it all together
● Advanced Topics
● Private information retrieval
Private Information Retrieval: Motivation
Are Mirrors Trustworthy?
● No.
● We set up a fake administrator / company and rented
hosting
● We registered as an official mirror for five of the most
popular distributions
● All five accepted our registration and started forwarding
clients, including banks and government / military
computers
● We could have rooted essentially all machines that
contacted our mirror.
[Cappos CCS 08]
Goal - Hide What Is Retrieved
Retrieve one piece of content out of a "database" without
disclosing which piece is retrieved.
Example:
- Give me one of ~1K security updates
- Give me info from WebMD without disclosing which
page
- Tell me about a stock, but don't know what I'm looking at
- Give me a news article, but don't disclose whether I'm
reading NY Times, Huffington Post, Fox News, etc.
Is this possible?
Trivial solution:
Download the entire database
How much data is there?
Is this possible?
Trivial solution:
Download the entire database
Impractical
Typical Software Update
Configuration
Let's be more efficient
Results
Overall performance
Limitations of XOR scheme
● Require non-colluding mirrors.
What about a snooping access point / ISP?
Encrypt connections to mirrors
How can we find / quantify diverse mirrors?
● What if a mirror provides bogus data?
● What can be done to speed up this process?
Is it useful to do so?
● How should files be organized into blocks?
What are the privacy / performance tradeoffs?
These are just examples. Think of your own too!
Reading
Read:
● http://en.wikipedia.org/wiki/Public_key_infrastructure
● http://www.openca.org/
● http://web.securityinnovation.com/blog/bid/61466/How-Threat-M
odeling-Saved-My-Life

Watch:
● https://media.torproject.org/video/tor-internet-days-2010.mp4