CS306: Introduction to IT Security Fall 2020
Lecture 8: Crypto Light
Instructor: Nikos Triandopoulos November 3, 2020
2
8.0 Announcements
CS306: Announcements
u HW2 to come out this week
u this time, for real!
u covers MACs, hashing, PK-crypto, honeywords… u due in two weeks
u HW1 grades u talk to TAs
u Midterm grades
u as soon as possible, given that they are graded by your instructor – end of week
u Labs resume this Thursday
3
CS306: Tentative Syllabus
Week
Date
Topics
Reading
Assignment
1
Sep 1
Introduction
Lecture 1
–
2
Sep 8
Symmetric-key encryption
Lecture 2
Lab 1
3
Sep 15
Perfect secrecy
Lecture 3
Lab 2, HW 1
4
Sep 22
Ciphers in practice I
Lecture 4
Lab 3, HW 1
5
Sep 29
Ciphers in practice II
Lecture 5
Lab 4
6
Oct 6
MACs & hashing
Lecture 6
Lab 5
–
Oct 13
No class (Monday schedule)
Lab 6
7
Oct 20
Public-key cryptography
Lecture 7
4
CS306: Tentative Syllabus
(continued)
Week
Date
Topics
Reading
Assignment
8
Oct 27
Midterm
All materials covered
9
Nov 3
Crypto Light: Applications
Lecture 8
Lab 7, HW 2
10
Nov 10
Access Control & User Authentication
11
Nov 17
Web & Network Security
12
Nov 24
Cloud Security & Privacy
13
Dec 1
Software/Database Security
14
Dec 8
Economics, Legal & Ethical Issues
15
Dec 15 (or later)
Final
(closed “books”)
All materials covered*
5
* w/ focus on what covered after midterm
Two weeks ago
u Public-key (PK) cryptography
u Motivation, PK Infrastructure, PK encryption, digital signatures u Discrete log problem & ElGamal encryption, hybrid encryption
u Demo
u The length-extension attack against naïve HMAC…
6
Today
u Crypto Light
u Special topics on message authentication, cryptographic hashing, RSA u Final remarks on crypto tools w/ a focus on practical applications
u Topics
u authenticated encryption, HMAC
u cryptographic hashing in practice & Honeywords u RSA problem & RSA crypto system
7
8
8.1 Authenticated encryption
Recall: Two distinct properties
Secrecy
u sensitive information has value u if leaked, it can be risky
u specific scope / general semantics
u prevention
u does not imply integrity
u e.g., bit-flipping “attack”
Integrity
u correct information has value
u if manipulated, it can harmful
u random Vs. adversarial manipulation
u wider scope / context-specific semantics u source Vs. content authentication
u replay attacks
u detection
u does not imply secrecy
u e.g., user knows cookies’ “contents”
9
Recall: Yet, they are quite close…
Common setting
u communication (storage) over an “open,” i.e., unprotected, channel (medium) Fundamental security problems
u while in transit (at rest)
u no message (file) should be leaked to A
u no message (file) should be modified by A
A
m
m
Core cryptographic protections
u encryption schemes provide secrecy / confidentiality u MAC schemes provide integrity / unforgeability
Can we achieve both at once in the symmetric-key setting? Yes! 10
Authenticated Encryption (AE): Catch 2 birds w/ 1 stone
Cryptographic primitive that realizes an “ideally secure” communication channel u motivation
u important in practice as real apps often need both u good security hygiene
u even if a given app “asks” only/more for secrecy or integrity than the other, it’s always better to achieve both!
11
Three generic AE constructions
Constructions of a secure authenticated encryption scheme ΠAE u they all make use of
u a CPA-secure encryption scheme ΠΕ = (Enc, Dec); and
u a secure MAC ΠM = (Mac, Vrf)
u which are instantiated using independent secret keys ke, km
u …but the order with which these are used matters!
12
Generic AE constructions (1)
1. encrypt-and-authenticate
u Encke(m) → c; Mackm(m) → t; send ciphertext (c, t)
u if Decke(c) = m ≠ fail and Vrfkm(m,t) accepts, output m; else output fail u insecure scheme, generally
u e.g., MAC tag t may leak information about m
u e.g., if MAC is deterministic (e.g., CBC-MAC) then ΠΑΕ is not even CPA-secure u used in SSH
13
Generic AE constructions (2)
2. authenticate-then-encrypt
u Mackm(m) → t; Encke(m||t) → c; send ciphertext c
u if Decke(c) = m||t ≠ fail and Vrfkm(m,t) accepts, output m; else output fail u insecure scheme, generally
u used in TLS, IPsec
14
Generic AE constructions (3)
3. encrypt-then-authenticate (cf. “authenticated encryption”) u Encke(m) → c; Mackm(c) → t; send ciphertext (c, t)
u if Vrfkm(c,t) accepts then output Decke(c) = m, else output fail u secure scheme, generally (as long as ΠM is a “strong” MAC)
u used in TLS, SSHv2, IPsec
15
Application: Secure communication sessions
An AE scheme ΠΑΕ = (Enc, Dec) enables two parties to communicate securely u session: period of time during which sender and receiver maintain state
u idea: send any message m as c = Enck(m) & ignore received c that don’t verify
u security: secrecy & integrity are protected
u remaining possible attacks
u re-ordering attack counters can be used to eliminate reordering/replays u reflection attack directional bit can be used to eliminate reflections
u replay attack
c = Enck(bA→B|ctrA,B||m); ctrA,B++
16
17
8.2 Applications of cryptographic hashing
Recall: Cryptographic hash functions
Basic cryptographic primitive
u maps objects to a fixed-length binary strings
u for all practical purposes, mapping avoids collisions (distinct objects x ≠ y mapped to same value H(x) = H(y))
input
arbitrarily
long string
output
u collision resistance: no distinct inputs can be efficiently found that collide in the hash domain “any object can be securely mapped to a practically-unique short digest”
Collision resistance implies two weaker security properties
u findingacollusionw.r.t.agivenrandomobjectxisalsoinfeasible u findinganypreimageofarandomhashvaluehisalsoinfeasible
77
short digest, fingerprint, “secure”
H
description
Recall: Weaker security notions
Given a hash function H: X ® Y, then we say that H is
u preimage resistant (or one-way)
u given a uniform y Î Y, finding a value x Î X s.t. H(x) = y happens negligibly often
u 2-nd preimage resistant (or weak collision resistant)
u given a uniform x Î X, finding a value x’ Î X, s.t. x’1 x and H(x’) = H(x) happens
negligibly often
u cf. collision resistant (or strong collision resistant)
u finding two distinct values x’, x Î X, s.t. H(x’) = H(x) happens negligibly often 19
Recall: Davies-Meyer & Merkle-Damgård transforms
h(x||k) = Fk(x) XOR x
u h is a CR compression function,
if F is an ideal cipher (a more secure PRF)
u HisaCRhashfunction,hisCR
20
21
Recall: Current hash standards & SHA2-512
Recall: Birthday attacks against collision resistance
Assume a CR function h producing hash values of size n
u brute-force attack
u evaluate h on 2n + 1 distinct inputs
u by the “pigeon hole” principle, at least 1 collision will be found
u birthday attack
u evaluate h on (much) fewer distinct inputs that hash to random values
u by “balls-into-bins” probabilistic analysis, at least 1 collision will likely be found u when hashing only half distinct inputs, it’s more likely to find a collision!
u thus, in order to get n-bit security, we (at least) need hash values of length 2n
22
Recall: Security strength due to birthday attacks
u # hash evaluations for finding collisions on n-bit digests with probability p nm
u for large m = 2n, average # hash evaluations before finding the first collision is 1.25(m)1/2
23
24
8.2.1 Applications of cryptographic hashing in cryptography
[1] “Hash-and-MAC” & “hash-and-sign”
Hash-and-MAC construction based on u aCRhashfunctionH;and
u asecurefixed-messageMAC
Similarly, digital signatures are used with hash functions
u the hash of a message is signed, instead of the message itself
Intuition
u since H is CR:
authenticating digest H(m) is a good as authenticating m itself! 25
m
Mac’ hash
h = H(m)
Mac
t
[2] Hash-based MAC (HMAC): A naïve, insecure, approach
Set tag t as:
Mack(m) = H(k||m)
u intuition: given H(k||m) it should be infeasible to compute H(k||m’), m’ ≠ m
Insecure construction
u practical CR hash functions
employ the Merkle-Damgård design
u length-extension attack
u knowledge of H(m1) makes it feasible to compute H(m1||m2)
u by knowing the length of m1, one can learn internal state zB even without knowing m1!
26
[2] HMAC: Secure design
Set tag t as:
HMACk[m] = H[ (kÅopad) || H[ (kÅipad) || m ] ]
u intuition: instantiation of hash & sign paradigm u two layers of hashing H
u upper layer
u y = H( (k Å ipad) || m ) u y = H’(m), i.e., “hash”
u lower layer ut=H((kÅopad) ||y’)
u t = Mac’(kout, y’), i.e., “sign”
27
28
8.2.2 Applications of cryptographic hashing in security
[1] Digital envelops
Commitment schemes u two operations
u commit(x, r) = C
u i.e., put message x into an envelop (using randomness r)
u e.g., commit(x, r) = h(x || r)
u hiding property: you cannot see through an (opaque) envelop
u open(C, m, r) = ACCEPT or REJECT
u i.e., open envelop (using r) to check that it has not been tampered with u e.g., open(C, x, r): check if h(x || r) =? C
u binding property: you cannot change the contents of a sealed envelop
29
[1] Security properties
Hiding: perfect opaqueness
u similar to indistinguishability; commitment reveals nothing about message
u adversary selects two messages x1, x2 which he gives to challenger
u challenger randomly selects bit b, computes (randomness and) commitment Ci of xi u challenger gives Cb to adversary, who wins if he can find bit b (better than guessing)
Binding: perfect sealing
u similar to unforgeability; cannot find a commitment “collision”
u adversary selects two distinct messages x1, x2 and two corresponding values r1, r2 u adversary wins if commit(x1, r1) = commit(x2, r2)
30
[1] Example 1: Online auctions
Suppose Alice, Bob, Charlie are bidders in an online auction u Alice plans to bid A, Bob B and Charlie C
u they do not trust that bids will be secret
u nobody is willing to submit their bid
u solution
u Alice, Bob, Charlie submit hashes h(A), h(B), h(C) of their bids u all received hashes are posted online
u then parties’ bids A, B and C revealed
u analysis
u “hiding:” hashes do not reveal bids
u “binding:” cannot change bid after hash sent 31
(which property?) (which property?)
[1] Example 1: Online auctions (II)
A general issue with concealing private data via hashing
u due to the small search space, this protocol is not secure! u a forward search attack is possible
u e.g., Bob computes h(A) for the most likely bids A u how to prevent this?
u increase search space
u e.g., Alice computes h(A||R), where R is randomly chosen
u at the end, Alice must reveal A and R
u but before he chooses B, Bob cannot try all A and R combination
32
[1] Example 2: Fair decision via coin flipping
Alice is to “call” the coin flip and Bob is to flip the coin
u to decide who will do the dishes…
u problem: Alice may change her mind, Bob may skew the result u protocol
u Alice “calls” the coin flip but only tells Bob a commitment to her call u Bob flips the coin and reports the result
u Alice reveals what she committed to
u Bob verifies that Alice’s call matches her commitment
u If Alice’s revelation matches the coin result Bob reported, Alice wins
u hiding: Bob does not get any advantage by seeing Alice commitment u binding: Alice cannot change her mind after the coin is flipped
33
[2] Forward-secure key rotation
Alice and Bob secretly communicate using symmetric encryption
u Eve intercepts their messages and later breaks into Bob’s machine to steal the shared key
Alice key k
s1 = k
Bob
key k
h s2
h s3
h …sk
✗
h sk+1 leakage
34
key
[3] Hash values as file identifiers
Consider a cryptographic hash function H applied on a file F u the hash (or digest) H(M) of F serves as a unique identifier for F
u “uniqueness”
u if another file F’ has the same identifier, this contradicts the security of H
u thus
u the hash H(F) of F is like a fingerprint
u one can check whether two files are equal by comparing their digests
Many real-life applications employ this simple idea!
35
Examples
3.1 Virus fingerprinting
u When you perform a virus scan over your computer, the virus scanner application tries to identify and block or quarantine programs or files that contain viruses
u This search is primarily based on comparing the digest of your files against a database of the digests of already known viruses
u The same technique is used for confirming that is safe to download an application or open an email attachment
3.2 Peer-to-peer file sharing
u In distributed file-sharing applications (e.g., systems allowing users to contribute contents that are shared amongst each other), both shared files and participating peer nodes (e.g., their IP addresses) are uniquely mapped into identifiers in a hash range
u When a given file is added in the system it is consistently stored at peer nodes that are responsible to store files those digests fall in a certain sub-range
u When a user looks up a file, routing tables (storing values in the hash range) are used to eventually locate one of the machines storing the searched file
36
Example 3.3: Data deduplication
Goal: Elimination of duplicate data
u Consider a cloud provider, e.g., Gmail or Dropbox, storing data from numerous users.
u A vast majority of stored data are duplicates; e.g., think of how many users store the same email attachments, or a popular video…
u Huge cost savings result from deduplication: u a provider stores identical contents
possessed by different users once!
u this is completely transparent to end users!
Idea: Check redundancy via hashing
u Files can be reliably checked whether they are duplicates by comparing their digests.
u When a user is ready to upload a new file to the cloud, the file’s digest is first uploaded.
u The provider checks to find a possible duplicate, in which case a pointer to this file is added.
u Otherwise, the file is being uploaded literally
u This approach saves both storage and bandwidth!
37
[4] Password hashing
Goal: User authentication Problem: How to protect password files
u Today, passwords are the dominant means for u user authentication, i.e., the process of
verifying the identity of a user (requesting
access to some computing resource).
If password are stored at the server in the clear, an attacker can steal the password file after breaking into the authentication server – this type of attack happens routinely nowadays…
Password hashing involved having the server storing the hashes of the users passwords.
Thus, even if a password file leaks to an attacker, the onewayness of the used hash function can guarantee some protections against user- impersonation simply by providing the stolen password for a victim user.
u This is a “something you know” type of user authentication, assuming that only the legitimate user knows the correct password.
u When you provide your password to a computer system (e.g., to a server through a web interface), the system checks if your submitted password matches the password that was initially stored in the system at setup.
u u
38
[4] Password storage
Plaintext
Concealed via hashing
39
[4] Distribution of password types
Words in dictionaries or lists of names
15%
Four characters, all letters 14%
Other good passwords
14%
One character 0%
Two characters
2% Three characters 14%
Six letters, lowercase
19%
Five letters, all same case
40
22%
[4] Dictionary attacks
u “online” brute-force or dictionary attack against passwords u employs only the authentication system
u the attacker tries to impersonate a victim by trying
u all possible (short length) passwords or
u passwords coming from a known dictionary u “offline” brute-force or dictionary attack
u employs a leaked file of hashed passwords
41
[4] Countermeasures
Password salting
u to slow down dictionary attacks
u a user-specific salt is appended to a user’s password before it is being hashed
u each salt value is stored in the clear along with its corresponding hashed password u if two users have the same password, they will have different hashed passwords
u example: Unix uses a 12 bit salt
Hash strengthening
u to slow down dictionary attacks
u a password is hashed k times before being stored 42
[4] A promising approach: Split verification into two servers
u Key idea: Distribute password verification across two servers
u Red server verifies “half” the credentials; blue server verifies other “half” u Authentication decision relies on both outputs
u Compromise of one server gives no/little advantage to attacker
RED SERVER
candidate passcode P
5. accept/reject
keeps no secret state
2.
P
red processing
Interaction
blue processing
1.
red decision 3. blue decision
2. P
43
Access Control Module
4. 4.
BLUE SERVER
[4] Honeywords
u Based on decoy passwords, aka honeywords
u Red stores user’s i real password Pi and k-1 fake ones in unlabeled set Ci u Blue server stores the index di of Pi in set Ci
u Password verification through sequential verifications
candidate 1. password P’
for user i
2. P’
3. R
if there exists j s.t. P’=Ci[j]
then R=(1,i,j) else R=(0,i,⊥)
ifdi =jthenB=true else B=false
Access Control Module
Auth. Server
4. B,R B=true & R[1]=1
44
accept iff
Honey- checker
[4] Example
u User nikos: hel00w0rld, heloow0rld, hel00w1rld, hel11w0rld
u Red server: nikos, hel00w0rld, heloow0rld, hel00w1rld, hel11w0rld u Blue server: nikos, 2
u User provides hel11w0rld
u Red: if password is contained in list at position 4, then output (nikos, 4)
u Else reject
u Blue: if match, then output OK, else ALERT
45
46
8.3 Number theory background
Multiplicative inverses
The residues modulo a positive integer n comprise set Zn = {0,1,2,…,n – 1} u letxandybetwoelementsinZn suchthatxymodn=1
u we say: y is the multiplicative inverse of x in Zn u we write: y = x-1
u example:
u multiplicative inverses of the residues modulo 11
x
0
1
2
3
4
5
6
7
8
9
10
x-1
1
6
4
3
9
2
8
7
5
10
47
Multiplicative inverses (cont’ed)
Theorem
An element x in Zn has a multiplicative inverse iff x, n are relatively prime u e.g., the only elements of Z10 having a multiplicative inverse are 1, 3, 7, 9
x
0
1
2
3
4
5
6
7
8
9
x-1
1
7
3
9
Corollary
If p is prime, every non-zero residue in Zp has a multiplicative inverse
Theorem
A variation of Euclid’s GCD algorithm computes the multiplicative inverse of an element x in Zn or determines that it does not exist
48
Computing multiplicative inverses
Fact
u given two numbers a and b, there exist integers x, y s.t. x a + y b = gcd(a,b)
which can be computed efficiently by the extended Euclidean algorithm.
Thus
u the multiplicative inverse of a in Zb exists iff gcd(a, b) = 1
u i.e., iff the extended Euclidean algorithm computes x and y s.t. x a + y b = 1 u in this case, the multiplicative inverse of a in Zb is x
49
Euclid’s GCD algorithm
Computes the greater common divisor by repeatedly applying the formula
gcd(a, b) = gcd(b, a mod b)
Algorithm EuclidGCD(a, b) Input integers a and b Output gcd(a, b)
if b = 0 return a
else
return EuclidGCD(b, a mod b)
u example
ugcd(412, 260) = 4
a
412
260
152
108
44
20
4
b
260
152
108
44
20
4
0
50
Extended Euclidean algorithm Theorem
If, given positive integers a and b, d is the smallest positive integer s.t. d = ia + jb, for some integers
i and j, then d = gcd(a, b)
u example
u a=21,b=15
u d=3,i=3,j=-4
u 3=3×21+(-4)×15=63-60=3
Algorithm Extended-Euclid(a, b) Input integers a and b Output gcd(a, b), i and j
s.t. ia+jb = gcd(a,b) if b = 0
return (a,1,0)
(dʹ, xʹ, yʹ) = Extended-Euclid(b, a mod b)
(d, x, y) = (dʹ, yʹ, xʹ – [a/b]yʹ) return (d, x, y)
51
Multiplicative group
A set of elements where multiplicationis defined
u closure, associativity, identity & inverses
u multiplicative groups Z*n, defined w.r.t. Zn (residues modulo n)
u subsets of Zn containing all integers that are relative prime to n
u CASE 1: if n is a prime number, then all non-zero elements in Zn have an inverse
u Z*7 = {1,2,3,4,5,6}, n = 7
u 24=1(mod7),35=1(mod7),66=1(mod7),11=1(mod7) u CASE 2: if n is not prime, then not all integers in Zn have an inverse
u Z*10 = {1,3,7,9}, n = 10
u 37=1(mod10),99=1(mod10),11=1(mod10)
52
Order of a multiplicative group
Order of a group = cardinality of the group
u multiplicative groups for Z*n
u the totient function φ(n) denotes the order of Z*n , i.e., φ(n) = |Z*n|
u if n = p is prime, then the order of Z*p={1,2,…,p-1} is p-1, i.e., φ(n) = p-1 u e.g., Z*7 = {1,2,3,4,5,6}, n = 7, φ(7) = 6
u if n is not prime, φ(n) = n(1-1/p1)(1-1/p2)…(1-1/pk), where n = pe11pe22…pekk u e.g., Z*10 = {1,3,7,9}, n = 10, φ(10) = 4
u if n = p q, where p and q are distinct primes, then φ(n) = (p-1)(q-1) Factoring problem u difficult problem: given n = pq, where p, q are primes, find p and q or φ(n)
53
Fermat’s Little Theorem Theorem
Ifpisaprime,thenforeachnonzeroresiduexinZp,wehavexp-1 modp=1 u example(p=5):
14 mod5=1 24 mod5=16mod5=1 34 mod5=81mod5=1 44 mod5=256mod5=1
Corollary
If p is a prime, then the multiplicative inverse of each x in Z*p is xp – 2 mod p u proof:x(xp-2modp)modp=xxp-2modp=xp-1modp=1
54
Euler’s Theorem Theorem
For each element x in Z*n, we have xφ(n) mod n = 1
u example(n=10)
u Z*10 = {1,3,7,9}, n = 10, φ(10) = 4
u 3φ(10) mod10=34 mod10=81mod10=1
u 7φ(10) mod10=74 mod10=2401mod10=1 u 9φ(10) mod10=94 mod10=6561mod10=1
55
Computing in the exponent
For the multiplicative group Z*n, we can reduce the exponent modulo φ(n) u xy modn=xkφ(n)+r modn=(xφ(n))kxr modn=xr modn=xymodφ(n)modn
Corollary: For Z*p, we can reduce the exponent modulo p-1 u example
u Z*10 = {1,3,7,9}, n = 10, φ(10) = 4
u 31590 mod10=31590mod4 mod10=32 mod10=9 u example
u Z*p ={1,2,…,p-1},p=19,φ(19)=18
u 1539 mod19=1539mod18 mod19=153 mod19=12
56
Powers
Let p be a prime
u the sequences of successive powers of the elements in Z*p exhibit repeating subsequences
u the sizes of the repeating subsequences and the number of their repetitions are the divisors of p – 1
u example, p = 7
x
x2
x3
x4
x5
x6
1
1
1
1
1
1
2
4
1
2
4
1
3
2
6
4
5
1
4
2
1
4
2
1
5
4
6
2
3
1
6
1
6
1
6
1
57
58
8.4 The RSA algorithm
The RSA algorithm (for encryption)
General case
Example
Setup (run by a given user)
u n=p×q,withpandqprimes
u erelativelyprimetoφ(n)=(p-1)(q-1)u e=5,φ(n)=6×16=96
u dinverseofeinZφ(n) Keys
u public key is KPK = (n, e)
u private key is KSK = d Encryption
u C=Me modnforplaintextMinZn Decryption
u M=Cd modn
u d=77 Keys
u public key is (119, 5) u private key is 77
Encryption
u C=195 mod119=66forM=19inZ119
Decryption
u Μ=6677 mod119=19
59
Setup
u p=7, q=17,n=7×17=119
Another complete example
u Setup
up=5,q=11,n=5×11=55
uφ(n) = 4 × 10 = 40
ue=3,d=27 (3×27=81=2×40+1) u Μ=C27 mod55
u Encryption
u C=Μ3 mod55forMinZ55
u Decryption
M
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 8 27 9 15 51 13 17 14 10 11 23 52 49 20 26 18 2
M
C
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
39 25 21 33 12 19 5 31 48 7 24 50 36 43 22 34 30 16
M
C
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
53 37 29 35 6 3 32 44 45 41 38 42 4 40 46 28 47 54
60
*Correctness of RSA
Given Setup
Analysis
Need to show
u Med =Mmodp×q
u n=p×q,withpandqprimes
u erelativelyprimetoφ(n)=(p-1)(q-1) Use(1)andapply(2)forprimep
u dinverseofeinZφ(n) (1) Encryption
u C = Me mod n for plaintext M in Zn Decryption
u Med =Med-1M=(Mp-1)h(q-1) M
u Med = 1h(q-1) M mod p = M mod p Similarly (w.r.t. prime q)
u Med = M mod q
Thus, since p, q are co-primes
u Med=Mmodp×q
u M = Cd mod n Fermat’sLittleTheorem
(2)
u forprimep,non-zerox:xp-1 modp=1 61
A useful symmetry
[1] RSA setting
u modulon=p×q,p&qareprimes,public&privatekeys(e,d):d×e=1mod(p-1)(q-1) [2] RSA operations involve exponentiations, thus they are interchangeable
u C = Me mod n (encryption of plaintext M in Zn)
u M = Cd mod n (decryption of ciphertext C in Zn)
Indeed, their order of execution does not matter: (Me) d = (Md) e mod n
[3] RSA operations involve exponents that “cancel out”, thus they are complementary
u x(p-1)(q-1) mod n = 1 (Euler’s Theorem)
Indeed, they invert each other: (Me) d = (Md) e = Med = Mk(p-1)(q-1)+1 mod n
=(M(p-1)(q-1))k ×M =1k ×M =Mmodn 62
Signing with RSA
RSA functions are complementary & interchangeable w.r.t. order of execution u coreproperty:Med =Mmodp×qforanymessageMinZn
RSA cryptosystem lends itself to a signature scheme
u ‘reverse’ use of keys is possible : (Md)e = M mod p × q
u signing algorithm Sign(M,d,n): σ = Md mod n for message M in Zn u verifying algorithm Vrfy(σ,M,e,n): return M == σe mod n
63
The RSA algorithm (for signing)
General case
Example
Setup (run by a given user)
u n=p×q,withpandqprimes
u erelativelyprimetoφ(n)=(p-1)(q-1)u e=5,φ(n)=6×16=96
u dinverseofeinZφ(n) Keys (same as in encryption)
u d=77 Keys
u public key is (119, 5) u private key is 77
Signing
u σ=6677 mod119=19forM=66inZ119
Verification
u CheckifM=195 mod119=66
u
u
Sign
public key is KPK = (n, e) private key is KSK = d
σ=Md modnformessageMinZn u CheckifM=σe modn
u
Verify
64
Setup
u p=7, q=17,n=7×17=119
Digital signatures & hashing
Very often digital signatures are used with hash functions
u the hash of a message is signed, instead of the message itself
Signing message M
u let h be a cryptographic hash function, assume RSA setting (n, d, e) u compute signature σ on message Μ as: σ = h(M)d mod n
u send σ, M
Verifying signature σ
u use public key (e, n) to compute (candidate) hash value Η = σe mod n u if H = h(M) output ACCEPT, else output REJECΤ
65
Security of RSA
Based on difficulty of factoring large numbers (into large primes), i.e., n = p × q into p, q u note that for RSA to be secure, both p and q must be large primes
u widely believed to hold true
u since 1978, subject of extensive cryptanalysis without any serious flaws found
u best known algorithm takes exponential time in security parameter (key length |n|) u how can you break RSA if you can factor?
Current practice is using 2,048-bit long RSA keys (617 decimal digits)
u estimated computing/memory resources needed
to factor an RSA number within one year
Length (bits) PCs Memory
430
1
128MB
760
215,000
4GB
1,020
342 ́106
170GB
1,620
1.6 ́1015
120TB
66
RSA challenges
Challenges for breaking the RSA cryptosystem of various key lengths (i.e., |n|) u knownintheformRSA-`keybitlength’expressedinbitsordecimaldigits
u provideempiricalevidence/confidenceonstrengthofspecificRSAinstantiations
Known attacks
u RSA-155 (512-bit) factored in 4 mo. using 35.7 CPU-years or 8000 Mips-years (1999) and 292 machines
u 160 175-400MHz SGI/Sun, 8 250MHz SGI/Origin, 120 300-450MHz Pent. II, 4 500MHz Digital/Compaq
u RSA-640 factored in 5 mo. using 30 2.2GHz CPU-years (2005)
u RSA-220 (729-bit) factored in 5 mo. using 30 2.2GHz CPU-years (2005)
u RSA-232 (768-bit) factored in 2 years using parallel computers 2K CPU-years (1-core 2.2GHz AMD Opteron) (2009)
Most interesting challenges
u prizesforfactoringRSA-1024,RSA-2048is$100K,$200K–estimatedat800K,20BMips-centuries 67
Deriving an RSA key pair
u public key is pair of integers (e,n), secret key is (d, n) or d
u the value of n should be quite large, a product of two large primes, p and q u often p, q are nearly 100 digits each, so n ~= 200 decimal digits (~512 bits)
u but 2048-bit keys are becoming a standard requirement nowadays u the larger the value of n the harder to factor to infer p and q
u but also the slower to process messages u a relatively large integer e is chosen
u e.g., by choosing e as a prime that is larger than both (p − 1) and (q − 1) u why?
u dischosens.t.e×d=1mod(p−1)(q−1) u how?
68
Discussion on RSA
u Assumep=5,q=11,n=5×11=55,φ(n)=40,e=3,d=27 u why encrypting small messages, e.g., M = 2, 3, 4 is tricky?
u recall that the ciphertext is C = Μ3 mod 55 for M in Z55
M
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 8 27 9 15 51 13 17 14 10 11 23 52 49 20 26 18 2
M
C
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
39 25 21 33 12 19 5 31 48 7 24 50 36 43 22 34 30 16
M
C
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
53 37 29 35 6 3 32 44 45 41 38 42 4 40 46 28 47 54
69
Discussion on RSA
u Assumep=5,q=11,n=5×11=55,φ(n)=40,e=3,d=27
u why encrypting small messages, e.g., M = 2, 3, 4 is tricky?
u recall that the ciphertext is C = Μ3 mod 55 for M in Z55
u Assume n = 20434394384355534343545428943483434356091 = p × q
u can e be the number 4343253453434536?
u Are there problems with applying RSA in practice?
u what other algorithms are required to be available to the user? u Are there problem with respect to RSA security?
u does it satisfy CPA security?
70
Algorithmic issues
The implementation of the RSA cryptosystem requires various algorithms
u Main issues
u representation of integers of arbitrarily large size; and
u arithmetic operations on them, namely computing modular powers
u Required algorithms (at setup)
u generationofrandomnumbersofagivennumberofbits(tocomputecandidatesp,q)
u primalitytesting(tocheckthatcandidatesp,qareprime)
u computationoftheGCD(toverifythateandφ(n)arerelativelyprime) u computationofthemultiplicativeinverse(tocomputedfrome)
71
Modular powers
Repeated squaring algorithm
u speeds up computation of ap mod n u write the exponent p in binary
u p=pb-1pb-2 …p1p0
u startwithQ1 =apb-1 modn
u repeatedly compute
Qi =((Qi-1)2 modn)apb-i modn
u obtainQb =ap modn
In total O (log p) arithmetic operations
Example
u 318 mod 19 (18 = 10010)
u Q1 =31 mod19=3
u Q2 =(32 mod19)30 mod19=9
u Q3 =(92 mod19)30 mod19=81mod19 =5
u Q4=(52mod19)31mod19=
(25 mod 19)3 mod 19 = 18 mod 19 = 18
u Q5 = (182 mod 19)30 mod 19 = (324 mod 19) mod 19 = 17×19 + 1 mod 19 = 1
72
Pseudo-primality testing
Testing whether a number is prime (primality testing) is a difficult problem
An integer n 3 2 is said to be a base-x pseudo-prime if u xn – 1 mod n = 1 (Fermat’s little theorem)
u Composite base-x pseudo-primes are rare
u a random 100-bit integer is a composite base-2 pseudo-prime
with probability less than 10-13
u the smallest composite base-2 pseudo-prime is 341
u Base-x pseudo-primality testing for an integer n
u checkwhetherxn-1 modn=1
u can be performed efficiently with the repeated squaring algorithm
73
Security properties
u Plain RSA is deterministic u why is this a problem?
u Plain RSA is also homomorphic u what does this mean?
u multiply ciphertexts to get ciphertext of multiplication! u [(m1)e mod N][(m2)e mod N] = (m1m2)e mod N
u however, not additively homomorphic
74
Real-world usage of RSA
u Randomized RSA
u to encrypt message M under an RSA public key (e,n), generate a new
random session AES key K, compute the ciphertext as [Ke mod n, AESK(M)]
u prevents an adversary distinguishing two encryptions of the same M since K is chosen at random every time encryption takes place
u Optimal Asymmetric Encryption Padding (OAEP)
u roughly, to encrypt M, choose random r, encode M as M’=[X=MÅH1(r),Y=rÅH2(X)]whereH1 andH2 arecryptographic hash functions, then encrypt it as (M’) e mod n
75