Aug 23

CS 591 Monday, August 23 Initial topic: A Survey of Basic Cryptography Peter Gemmell 277-6509 office 280-2557 cellular [email protected]

What is cryptology? • Generalized methods to hide (encrypt) and authenticate information • Generalized methods to expose and substitute information (malicious adversary -- not like that in error-correcting codes)

An Important Distinction Encryption = maintainng information secret/confidential Authentication = proving and maintaining information integrity (sometimes also availability)

Cryptographic work can be at different levels -- algorithms/primitives: e.g. encryption algorithms, signature algorithms, hash algorithms -- protocols between more than 1 party: e.g. threshold sharing -- systems: e.g. electronic cash systems, smartcard systems -- “Attacks” - on all the above

Some applications of cryptography • • • • • • •

network, operating systems security private internet, telephone communications electronic payments database security software protection pay television confidential, authentic military communications

Open system design vs closed system design Open design: the algorithm, protocol, or system design may be public information. The only secret will be the private or symmetric key(s) Closed design: as much information as possible is kept secret

Types of Security -- unconditional or “information theoretic”: the security is provable free of assumptions -- reducible or “provable”: one can prove that the security is as valid as some common unproven assumption -- ad hoc: the security seems good

Types of algorithms

Symmetric (encryption) Alice k

Bob k

sender encryption

M

ciphertext Enck

receiver decryption

ciphertext

M Deck

Types of algorithms

Symmetric (authentication) Alice k

Bob k

sender authentication

M Authk

M, Authk(M)

receiver verification

M,Authk(M)

“OK”

Verifyk

Types of algorithms

Public Key (assymmetric encryption) Alice pubkey

privkey sender

encryption

M

Bob

ciphertext Encpubkey

receiver decryption

ciphertext

M Decprivkey

Types of algorithms

Public Key (assymmetric authentication) Alice privkey

pubkey sender authentication

M

Bob

M, Signprivkey(M) Signprivkey

receiver verification

M, Signprivkey(M)

“OK”

Verifypubkey

Digital Signatures A public key technique to authenticate information in a non-repudiable way may be legally binding Recipient knows: a) that the message is that of the supposed sender b) can prove (a) to a third party

Why Public Key is so important It lessens the number of keys needed in a general purpose virtual private network (VPN) Less reliance on a “trusted center” for system availability and secrecy (e.g. electronic cash) Non-repudiation

Math Background Modular (clock) Arithmetic A mod N = remainder of A divided by N B

A mod N if B mod N = A mod N

A mod N + B mod N

A + B mod N

A mod N * B mod N

A*B mod N

Encryption Algorithms Historical and Toy Caesar Cipher:

{a, b, c … z}

{1, 2, 3, … 26}

Enc(X) = Enc(x1 … xN) = x1 + 3 mod 26 … xN + 3 mod 26 = C1 … CN E.G. Enc(“Security”) = Enc(19,5,3,21,18,9,20,25) = 22,8,6,24,21,12,23,2 = “Vhfxulyb”

Generalizations of Caesar Cipher (all weak security) Shift: Enck(x) = x+k mod 26 Affine: Enck1,k2(x) = k1 *x + k2 mod 26 Substitution: Encperm(x) = perm(x)

Other Historial Ciphers -- WWII American use of Navajo -- WWII German Enigma machine -- WWII Japanese Purple Machine

D. Kahn. The Codebreakers. Macmillan Co., New York, 1967.

Unconditionally Secure Cipher One-time pad key = random* bits message = bits

= 1100010011100100011… = 1110011001100110001…

cipher text = XOR of key, message

= 0010001010000010010...

Problems: number of random bits = length of all messages being encrypted (not reusable), random bits must be known to both sender and recipient.

Data Encryption Standard (DES) (symmetric key) Enck(M) = wild permutation, XOR’s of M, S-boxes, and k 16 “rounds,” 64-bit block input and output not clean and concise (like RSA and one-time pad) Standard for encryption of unclassified data since 1977 56 bits (40 bits in exported versions) yield valid concerns about vulnerability to “exhaustive key search”

Extensions to DES that may give a longer effective key Tripe-DES: ciphertext = EncDESk1(EncDESk2(EncDESk3( plaintext))) EncDESk1(DecDESk1 xor k2(EncDESk2( plaintext)))

DESX: ciphertext = k1 xor EncDESk1(message xor k3)

RC5 by Ron Rivest of RSA (symmetric encryption algorithm) Rotations, XOR’s, modular additions With variable key lengths and being more succinct than DES, it is faster and may inspire more confidence

RSA (public key encryption*)

• Public key: (N,e) • Private key: (p,q,d): p,q large primes; e d N = pq; d : (m ) = m mod N

*RSA encryption can be modified easily to work as the RSA signature function

RSA (public key encryption, continued)

• Express message M as a number between 1 and N * • Compute EncRSAN,e(M) = Me mod N e e d Compute DecRSA (M ) = (M ) = M mod N • p,q,d

• Assumed hard: factoring, discrete logs modulo N

Hash functions H • compress length of message 1M bits (any number)

128 or 160 bits

• “collision-free” for any x one can not compute y = x, H(x) = H(y)

• “random-like” behavior E.G. SHA-1, MD5, MD2

Authentication unconditionally secure Alice

Bob

a,b

a,b sender

receiver

authentication

M

M, aM+b

verification

M, aM+b

a,b can be used only once

“OK”

Authentication Keyed hash function (symmetric) Alice k

Bob k

sender

receiver

authentication

M

M, H(k,M,k)

verification

M, H(k,M,k)

H(K XOR opad, H(K XOR ipad, text))

“OK”

Efficiency Considerations and the need for symmetric session keys public key algorithms tend to be slow. E.G. RSA decrypts at the order of 10k bits/second DES encrypts/decrypts at the order of 1Mbit/second

Key Exchange: Establishing a (symmetric) Session Key k Alice

Bob

pubkeyBob privkeyAlice

pubkeyAlice privkeyBob

k

Impersonation Attack Alice pubkeyFakeBob privkeyAlice

“I’m Bob”

important information

pubkeyAlice privkeyFakeBob

Certification Authority (CA) “Bob” PubkeyBob

misc info

CA

“Bob”

misc info CA signature

certificate binds a name to a public key

Open Network

Virtual Private Networks (VPN)

VPN software/hardware Application layer: SSL, Shttp, S/WAN, PCT IP Layer: Netlock, competitors

Electronic Payment Systems “credit card,” “debit card” style Visa, bank, or other

“You have received payment”

Internet payer

Internet payee

Sample Payment Protocols • iKP of IBM • SEPP: IBM, Netscape,GTE,CyberCash, and MasterCard • VISA’s design • First Virtual • Secure Courier, STT

Electronic Payment Systems Chaum-style untraceable Cash The Bank/Mint

Ecash withdrawer/payer The Bank/Mint

SN = 12345 BankSig SN= 12345

BankSig

BankSig

SN = 12345 BankSig

ECash Payee/Depositor

Electronic Payment Systems Trustee-traceable Cash Trustee 1

Trustee 2

The Bank/Mint

Ecash Withdrawer/Payer The Bank/Mint

SN = 12345 BankSig SN= 12345

BankSig

BankSig

SN = 12345 BankSig

ECash Payee/Depositor

Key Escrow, e.g. Clipper ECash User

Trustee 1

escrow key1 escrow key2

Trustee 2

escrow keyL

Trustee L

The Threshold Paradigm is one of

Distributed Trust Secret Information

Threshold Sharing Dealer shares a secret S to L shareholders. Some may be untrustworthy.

Threshold Sharing protects: - Secrecy: no k-1 shareholders can learn the secret - Integrity: no L-k shareholders can destroy the secret

Fortezza, Capstone, and Skipjack Skipjack:

a classified NSA-designed symmetric encryption algorithm

Capstone:

suite of crypto functions for govt-related use bulk data encryption algorithm: Skipjack digital signature algorithm: DSA key exchange protocol: not published hash function: SHA

Fortezza:

a tamper-resistant PCMCIA card, implementing Capstone algorithms

Man-in-the-Middle Attack Alice

Bob “I’m Bob”

“I’m Alice”

Crypto Information Resources • RSA FAQ (http://www.rsa.com/rsalabs/newfaq/) • Handbook of Applied Cryptography Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (http://www.dms.auburn.edu/hac/) • B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons, New York, 2nd Edition • D.R. Stinson. Cryptography - Theory and Practice. CRC Press, Boca Raton, 1995 http://bibd.unl.edu/~stinson/CTAP.html • D. Kahn. The Codebreakers. Macmillan Co., New York, 1967

Homework 1. Decipher this Caesar Text: “Wklv lv d whvw” 2. Decipher this shift Text: “Bqrairaijibnabiqjmibqraiwxbiknnwijibnabibqraivnaajpniexcumi qjdniknnwimroon nwb” hint: including a space character, there are 27 letters. 3. What is a CAPI and why is it important? 4. What is FIPS140 and why is it important? e.c. What are Alice and Bob’s real names?

Block Ciphers • Iterated • Key Schedule • Feistel -- e.g. DES

Modes of DES Encryption DES is a block cipher, encryptions of the same block repeated might yield the same cipher text

• • • •

Electronic Code Book (ECB) Cipher Block Chaining (CBC) Cipher Feedback Mode (CFM) Output Feedback Mode (OFM)

Electronic Code Book mode (ECB) M1-64 DES

C1-64

M65-128 k

DES

C65-128

k

Cipher Block Chaining mode (CBC) M65-128 M1-64 DES

C1-64

XOR

k

DES

C65-128

k

Attacks -- characterized by needs of the attacker • Known Plaintext • Chosen Plaintext • Chosen Ciphertext Also -- number of plaintext, ciphertext pairs

The birthday paradox Any random set of 23 people probably shares a birthday

A birthday attack If hash function H maps into message digests of length 60 bits, then an adversary can find a collision using only 230 inputs

Meet in the middle attack on symmetric encryption functions (known plain text attack) key k = k1,k2 Enck(M) = Enck1(Enck2(M)) Known Plain text P, Cipher text C = Enck(P)

Meet in the middle technique k2 = 000..0

P

k1 = 000..0 Enck2(P) = Deck1(C)

k2 = 11….1

C k1 = 11….1

Homework 2 • Why do people not advocate “double DES” ? • Why do people not use error correcting codes for encryption? • Why do people not use error correcting codes for authentication?

Using CBC DES for authentication (symmetric) M1-64

DES

k

M65-128

Mlast block

XOR

XOR

DES

k

DES

Authk(M)

k

RSA (public key signatures)

• Public key: (N,e) • Private key: (p,q,d): p,q large primes; e d N = pq; d : (x ) = x mod N

RSA (public key signatures, continued)

• Hash message M to a number H(M) • Compute SignRSAp,q,d(M) = H(M)d mod N • VerifyRSAN,e(M, SignRSA(M)) = “OK” iff SignRSA(M)e = H(M) mod N

The Digital Signature Algorithm DSA/DSS set-up Public verification key • p prime • q prime (160 bits), q divides p-1 • g generator • y = gx mod p Private signing key • x random number between 1 and q

The Digital Signature Algorithm signing M: message to be signedprocess H:

hash function such as SHA or MD5 or MD2 k: a random one-time signing key

r =(gk mod p) mod q s = k-1(H(M) + xr) mod q

Sigx(M) = (r,s)

The Digital Signature Algorithm signature verification process Given: M, (r,s) compute u1 = s-1 H(M) mod q u2 = s-1 r mod q v = (gu1 yu2 mod p) mod q

accept

v=r

Primality Testing For security and general fault-tolerant reasons, need to know if p is really prime (divisible only by 1 and p) Probabilistic: Miller-Rabin Solovay-Strassen … 100% guaranteed: Atkins …

Strong primes

p

• p+1 has a large prime factor • p-1 has a large prime factor r • r-1 has a large prime factor foils factoring, discrete log, RSA attacks

Elliptic Curve Algorithms public key encryption/authentication Issue: the public and private keys and signatures of assymmetric encryption encryption and signatures are too big and slow Solution?: Instead of operating on the numbers 1 … N or 1 … p, operate on eliptic curve elements: (x,y) such that y2 = x3 + ax + b (mod p)

Factoring Techniques • • • • • •

Try all primes <= squareroot(p) Pollard’s rho method Elliptic curve methods Quadratic sieve Number field sieve ….

discrete logs: index calculus ... Best current algorithms can factor, take discrete logs of roughly 400 bits.

Pseudo-random number generators Problems: • getting many truly random bits is slow • getting many shared truly random bits is more awkward • getting “good randomness” is important for many crypto algorithms Solution: • theory: pseudo-random strings that are “polynomial time indistinguishable” from truly random strings • practice: use DES, hash functions generate bits from a random seed (FIPS 186)

Stream Ciphers (example -- binary cipher) key: k input: M1M2 M3 M4… key stream: k1 k2 k3 k4… cipher stream: C1 C2C3 C4… Ci = ki xor Mi key stream ki depends on k and possibly M1M2 ... Mi-1

Zero-knowledge proofs (crypto tools) Prover

Verifier (Interactive proofs)

Zero knowledge proofs are simulateable (conversation distributions are indistinguishable)

Prover

Verifier conversation 1

Simulator

Verifier conversation 2

Complexity Theory P:

problems that can be solved in polynomial time, I.e. problems that can be solved “efficiently”

NP: broad set of problems that includes P NP-complete: the hardest problems in NP, they appear to have no efficient solution Factoring, discrete log are in NP, not known to be NP-

complete or in P

Quantum Computation Radically new machine design can factor, compute discrete logarithms, and compute other things it is believed conventional machines can not.

Can a quantum machine be built?

More Notation One-way function: a function that is easy to compute in one direction, but hard to invert, e.g. a hash function

Trap-door one-way function: a function that is easy to compute in one direction, but hard to invert … unless one knows the key, e.g. the RSA encryption function

Some security partners for crypto (Crypto can not solve all security problems) • Secure operating system/network security • Tamper-resistant hardware -- e.g. prevent adversary from learning keys of his own smart card. -- e.g. detect tampering in smartcard • Proper personal management of passwords -- e.g. non-dictionary words -- sufficiently many characters -- not written down -- limitted number of tries -- one-time passwords

3rd Homework • What is wrong with making RSA more efficient by letting one prime be smaller -- say of only 30 bits. • How many bits should an RSA/DSA modulus / DES key have … -- for personal email? -- for business email? -- for military/classified data? -- for a CA’s signature key? • How could one authenticate a small message … say of 50 bits using a symmetric one-time key? • Which is a better way for Alice to send Bob an authenticated and encrypted message M?: -- EncpubkeyBob(M, SignprivkeyAlice(M)) -- EncpubkeyBob(M),SignprivkeyAlice(EncpubkeyBob(M))

Extra questions • What about the case y = (-1)x mod p ? Isn’t it easy to find a value x that maps to y? Doesn’t this put a damper on the idea that discrete log is hard? • What sort of a function is f(x,y) = gxhy mod p? ( … assuming g and h are generators of Zp) • What is PGP? • What are Montgomery Multiplication, Brickell-McCurley fast modular exponentation? • What is a group? … a field? • What is a knapsack system?