Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
Overzicht Bewijsbare veiligheid met RSA: droom of realiteit?
ESATCOSIC
• Inleiding • RSA “volgens het boekje” • Toepassingen van RSA: Proton, EMV, SSL/TLS • Problemen met veiligheid • Bewijsbare veiligheid
Prof. Bart Preneel K.U.Leuven, Dept. Elektrotechniek -ESAT/COSIC e-mail:
[email protected] http://www.esat.kuleuven.ac.be/~preneel
Publieke sleutel cryptografie: encryptie
Informatiebeveiliging ESATCOSIC Audit/logging/ Intrusiedetectie
Netwerkbeveiliging Logische beveiliging
ESATCOSIC
Fysische beveiliging
Beveiligingspolitiek
CRY PTO BO X
Klaar tekst Veilig Beheerssysteem
Organisatorische maatregelen
Publieke sleutel
Publieke sleutel cryptografie: digitale handtekening ESATCOSIC
Klaar tekst
Private sleutel
Klaar tekst
CRY PTO BO X
Klaar tekst
VER IFY
Publieke sleutel
Private sleutel
“Tekstboek” RSA (1978)
ESATCOSIC
SIGN
%^C& @&^(
Personeelsbeheer
Cryptografie
Klaar tekst
%^C& @&^(
Klaar tekst
• • • • •
kies 2 grote priemgetallen p en q (512 bits) modulus n = p.q bereken ?(n) = kgv(p-1,q-1) kies e relatief priem t.o.v. ?(n) bereken d = e-1 mod ?(n) De veiligheid van RSA is
• publieke sleutel = (e,n) • private sleutel = d of (p,q) • encryptie: c = me mod n • decryptie: m = cd mod n
gebaseerd op het “feit” dat het gemakkelijk is om 2 grote priemgetallen te genereren , maar dat het moeilijkis om hun product te factoriseren
voorbeeld 2419
Page 1
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
Proton: statische authenticatie
Toepassingen van RSA ESATCOSIC
ESATCOSIC
CA
?1 laag: Banksys
• Protonkaart • EMV specificaties • Webbeveiliging: SSL/TLS
chipkaart
• Lotus Notes, SSH, IPsec, PGP, S/MIME, WS-Security • Patent vervallen in september 2000
Proton kaart: IDd mod n met d private sleutel van Banksys
Protonkaart met RSA “certificaat” ESATCOSIC
ESATCOSIC 431- 0557891- 55 Serie #: 8391037 Start: 1/3/03 1:00 End: 7/3/05 1:01
rekeningnummer
• RSA handtekening belet het creëren van Protonkaarten met nieuwe (rekening)nummers
uniek serienummer geldigheidsduur
– men kan nog steeds kaarten copiëren, maar dat wordt belet door fysische beveiliging
Versie: 2.0 Naam van CA
• eenvoudig te verifiëren in terminal
RSA Handtekening berekend met private sleutel van CA
Banksys, BE
– vraagt geen geheime informatie – weinig rekenwerk: exponent e=3
Statische Authentisering gebaseerd op een digitale handtekening - initialisatie
EMV: statische authentisering ESATCOSIC ?
IDd mod n
Motivatie
ESATCOSIC
CA
CERT ISS (PISS certified with SCA)
twee lagen: ? Issuers
R TI
FI E
D
Private Key SCA
Public Key EPI
PCA
Private Public Key Key Issuer SISS PISS
? EPI Issuer
Issuer
CE
Acquirer
Issuer Static Card data
Issuer
IC
Distributed to Acquirer (Resides in Terminal)
P CA
IC Card
Source: Mastercard Int.
POS Device
Page 2
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
Certificaat voor dynamische authentisering van kredietkaart
EMV: dynamische authentisering ESATCOSIC ?
ESATCOSIC
CA
drie lagen: ? EPI ? Issuers Issuer
Issuer
? Cards
Unique name owner
DN: cn= Jan Peeters, o=KBC, c=BE Serial #: 8391037 Start: 3/12/03 1:00 End: 4/12/05 12:01 CRL: cn=RVC, o=EMV, c=BE Key:
Issuer Issuer
Unique serial number Validity period Revocation information Public key Name of issuing CA CA’s Digital signature on the certificate
CA DN: o=EMV, c=BE
Dynamische authentisering gebaseerd op een digitale handtekening - Initialisatie ESATCOSIC
CERT ISS (PISS certified with SCA) CERT IC (PIC certified with SISS )
Private Key SIC
CE
R TI
FI E
CE
R TI
FI E
Private Key
Public Key
SCA
PCA
EPI
Public Key PIC
ESATCOSIC
Application Layer Application Data
Handshake
Private Public Key Key Issuer
D
S ISS
IC
D
TLS overzicht
Acquirer
P ISS
Protocol Client/Server Hello
Static Card data
Distributed to Acquirer (Resides in Terminal)
Change Cipher Spec Protocol Change Cipher Spec
Alert Protocol
Application Protocol
Alert
Application Data
Record Layer SSL Record
Authenticate and Sign Transaction with SIC
P CA
IC Card
Transport Layer (TCP/IP)
POS Device
Source: Mastercard Int.
TLS handshake
TLS: protocol (1)
ESATCOSIC
ESATCOSIC CLIENT
SERVER Hello Request
First Client Phase Client Hello
Second Client Phase Certificate* Client Key Exchange Certificate Verify* ?changecipherspec ? Finished
Application Data
First Server Phase Server Hello Certificate* Server Key Exchange* Certificate Request* Server Hello Done
Kies random N1
N1 N2
kies random N2
Second Server Phase ?changecipherspec ? Finished Application Data
Page 3
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
TLS: protocol (2)
TLS: protocol (3)
ESATCOSIC
ESATCOSIC
Exchanged messages
Hash Public Key
Private Key Wrapped Pre-Secret
MAC 1
T1
interchange and check
Hash
T2
MAC 2
This envelope
PreSecret
E
KDF
contains an e n c r y p t e d p r-e secret
C
D
PreSecret
KDF
N1 , N2
Master Secret
Master Secret N1 , N2
Master Secret
Master Secret
Source: RSA Labs
Source: RSA Labs
Overzicht ESATCOSIC
KDF
Session key
KDF
Is RSA veilig? ESATCOSIC
• is factorisatie moeilijk? • is het RSA probleem moeilijk? • is het (wiskundig) vervalsen van een handtekening of het kraken van een cijfertekst moeilijk? • is de implementatie veilig tegen aanvallen gebaseerd op nevenkanalen? • verbergen we alle informatie?
• Inleiding • RSA “volgens het boekje” • Toepassingen van RSA: Proton, EMV, SSL/TLS • Problemen met veiligheid • Bewijsbare veiligheid
Factorisatie van RSA moduli ESATCOSIC
Is factoriseren moeilijk? ESATCOSIC
• Leidt tot het breken van RSA
• Because both the system’s privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. Any person or organization possessing this power could counterfeit money, penetrate any personal, corporate, or government file, and possibly even undermine the security of nations. Bill Gates, The Road Ahead, 1996
Page 4
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
RSA Sleutellengtes ESATCOSIC
• • • • •
Proton: 512 bits EMV: 768-1024 bits Belgische identiteitskaart : 1024 bits Verisign (www.verisign.com): 1024 bits CA voor Belgische identiteitskaart : 2048 bits
• Is 1024 bits voldoende voor 5-10 jaar?
Factorisation records ESATCOSIC
Size (digits) Effort (log)
1 digit ~3 bits
160 140 120 100 80 60
Verdubbelen van modulus vertraagt encryptie met factor 4 ( kleine exponent) en decryptie met factor 8 en verhoogt de veiligheid met een factor 216 (1024 ? 2048 bits) en 2 21 (2048 ? 4096 bits)
40 20 0 64
Gardner’s Column: the $100 RSA challenge
72
76
80
84
88
92
96 100
40000000000000000 ? 17
Scientific American, August 1977 ESATCOSIC
68
ESATCOSIC
n (RSA-129, 425 bits) = 1 1438 1625 7578 8886 7669 2357 7997 6146 6120 1021 8296 7212 4236 2562 5618 4293 5706 9352 4573 3897 8305 9712 3563 9587 0505 8989 0751 4759 9290 0268 7954 3541
Derek Atkins (April 1994): We are happy to announce that RSA-129 = 3490 5295 1084 7650 9491 4784 9619 9038 9813 3417 7646 3849 3387 8439 9082 0577 * 3 2769 1329 9326 6709 5499 6198 8190 8344 6141 3177 6429 6799 2942 5397 9828 8533
e = 9007
C = 9686 9613 7546 2206 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 6951 2093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 9055 1829 9451 5781 5154
Ron Rivest (1977): factoring n (129 digits) would require at least 40 quadrillion years if you could do a * b mod c in one nanosecond.
“The magic words are squeamish ossifrage”
Pollard’s Rho Method
Trial and Error Factoring ESATCOSIC
• Guess x, if 1 < gcd (x, n) < n then x is an interesting factor • If p and q are similar size, lowest factor is around ? n. – Requires O(? n) divisions. – For RSA-129 = 1.1 * 10 64 divisions, 1 per nanosecond = 3.4 * 10 47 years
ESATCOSIC
• Fastest known in 1977 [Pollard75] • To find factor p, requires 4?p modular multiplies • Worst case: lowest p is ?n, we need 4??n multiplies • For RSA-129 = 1.3 * 10 32 = 4 * 1015 years • Rivest probably used this, but made a math error (4 quadrilllion ? 40 quadrilllion)
Page 5
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
Fermat Factoring ESATCOSIC
ESATCOSIC
• Factor 8051 • Hint: (½ (a + b))2 – (½(a – b))2 = ¼ (a 2 + 2ab + b 2) - ¼ (a 2 - 2ab + b 2) = ½ ab + ½ ab = ab • 8051 = 8100 – 49 = 902 – 72 • 8051 = 97 ? 83
• Quadratic Sieve (1981): O(L N [1/2, 1] ) – L N [1/2, 1] = exp((1 + o(1))·(ln N)1/2 )·(ln ln N)1/2 )
• Number field sieve (1993): O(L N [1/3, 1.92] ) – L N [1/3, 1.92] = exp((1.92 + o(1))·(ln N)1/3 )·(ln ln N)2/3 )
• L N [a, b] = exp((b + o(1))·(ln N)a )·(ln ln N) (1-a) ) – a = 0: exp((b + o(1))·(ln ln N) = (ln N) (b + o(1)) polynomial – a = 1: (N) (b + o(1)) exponential
½ (83 + 97) = 90 ½ (83 – 97) = 7
Optical computing for factoring (Shamir/Tromer)
ESATCOSIC
State of the art: factoring is subexponential
What about quantum computers? ESATCOSIC
• exponential parallelism
• Twinkle (2000) • Twirl (2003)
2n degrees of freedom !
– RSA-512: 10 minutes on 10K$ sieving machine – RSA-1024: 1 year on 10M$ sieving machine • http://www.wisdom.weizmann.ac.il/~tromer/papers/twirl.pdf
• Shor 1994: perfect for factoring • But: can a quantum computer be built?
State of the art in coherent qubit control
# gates and gate network
ESATCOSIC
Stanford/IBM 00 NMR, main players Grover search Other NMR 280 2-bit gates non-NMR 99 Oxford 98 Liquid crystals
“Cooling” spins 00 99,01
99,00,01 MIT 98 MIT 99 98 Cambridge 01 NEC 98 Oxford 00,01 02 Sacley* 98 00 98 LANL Deutsch- 00 NIST 99 NEC 95 NIST Jozsa 95 Caltech
1
2
Error correction 00 Order finding
3
4-channel Varian spectrometer
01 LANL
99
Error detection
n coupled quantum bits
4 # qubits
01 Shor 15=3x5
ESATCOSIC
Picture of the lab 11.7 T Oxford magnet, room temperature bore
00 LANL 7-spin coherence
01 Frankfurt
15=5x3
99 Cambridge
grad students in sunny California...
5
6
7 * unpublished
Page 6
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
Zelfs als factoriseren moeilijk is….
Zoeken van ?(n) of f (n)? ESATCOSIC
ESATCOSIC
Definieer: RSA(x) = xe mod n
• Het vinden van ? (n) = (p – 1)(q – 1) is equivalent
aan het factoriseren van n
• RSA(0)=?, RSA(1)=?, RSA(-1)=? – Deze cijferteksten zijn eenvoudig te herkennen – Deze handtekeningen zijn eenvoudig te vervalsen
• Hint: – ? (n) = n – (p + q) + 1 of p+q = n - ? (n) + 1 – p .q = n
• natuurlijke machten: xe < n of xe mod n = xe – Eenvoudig om “:kleine” berichten te decrypteren – Eenvoudig om “kleine” berichten te handtekenen
• Veralgemening: men kan p en q terugvinden als men een veelvoud kent van ?(n) of f (n)
Zelfs als factoriseren moeilijk is…(2) ESATCOSIC
Definieer: RSA(x) = xe mod n
De RSA veronderstelling ESATCOSIC
• het berekenen van willekeurige e-de machtswortels modulo n is moeilijk of RSA(x) is een éénwegsfunctie
• homomorphisme: RSA(x) . RSA(y) = RSA(x.y) – decryptie van 2 cijferteksten leidt tot decryptie van hun product – Handtekenen van 2 berichten leidt tot handtekenen van hun product
Conclusie : RSA “volgens het boekje” is niet veilig!
– ingang x wordt uniform gekozen in het interval [0,n-1]
RSA probleem moeilijk ?
Hoe encrypteren met RSA? ESATCOSIC
Hoe (niet) encrypteren met RSA? ESATCOSIC
• Stel dat het RSA probleem moeilijk is • … dus a fortiori veronderstellen we dat het factorisatie-probleem moeilijk is • Hoe moet ik dan encrypteren met RSA? – Hint: zorg ervoor dat de klaartekst eerst afgebeeld wordt op een willekeurig element van [0,n -1] en dat pas dan de RSA Encryptie Permutatie (RSAEP) wordt toegepast
factorisatie moeilijk
• Niet-hybride schema’s – – – – –
RSA-PKCS-1v1_5 (RSA Laboratories, 1993) RSA-OAEP (Bellare-Rogaway, 1994) RSA-OAEP+ (Shoup, 2000) RSA-SAEP (Johnson et al., 1994) RSA-SAEP+ (Boneh, 2001)
• Hybride schema’s – RSA-KEM (Zheng-Seberry, 1992) • RSA-KEM-DEM (Shoup, 2001) • RSA-REACT (Okamoto-Pointcheval, 2001)
– RSA-GEM (Coron et al., 2002)
Page 7
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
RSA-PKCS-1v1_5 Diagram
RSA PKCS-1v1_5 ESATCOSIC
• Introduced in 1993 in PKCS #1 v1.5. • De facto standard for RSA encryption and key transport
ESATCOSIC Random nonzero bytes
message
padding
– Appears in protocols such as TLS, S/MIME, ... 00 02
00
EM
Source: RSA Labs
RSA-PKCS-1v1_5 Cryptanalysis ESATCOSIC
• Low-exponent RSA when very long messages are encrypted [Coppersmith+ ‘96/Coron ‘00]
RSAEP
Public Key
C
Bleichenbacher’s attack ESATCOSIC
• Goal: decrypt c – – – –
– large parts of a plaintext is known or similar messages are encrypted with the same public key
choose random s, 0 < s < n computer c’ = c se mod n ask for decryption of c’: m’ compute m as m’/s mod n
• but m’ does not have the right format! • idea: try many random choices for s:
• Chosen ciphertext attack [Bleichenbacher ’98] – decryption oracle: ciphertext valid or not?
– if no error message is received, we know that 2B < (m s mod n) < 3B
– 1024-bit modulus: 1 million decryption queries • These attacks are precluded by fixes in TLS
– with B = 28(k-2) (k length in bytes of the modulus)
RSA-OAEP ESATCOSIC
RSA-OAEP Diagram ESATCOSIC
• designers: Bellare and Rogaway 1993 • enhancements by Johnson and Matyas in 1996 (“encoding parameters”) • already widely adopted in standards – – – –
DB =
RNG
pHash
00 ... 01
message
seed
MGF 00
IEEE P1363 draft ANSI X9.44 draft PKCS #1 v2.0 (PKCS #1 v2.1 draft) ISO 18033-2 working draft 2000
MGF
EM
Source: RSA Labs
Public Key
RSAEP
C
Page 8
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
RSA OAEP - security proof ESATCOSIC
RSA OAEP - security goal ESATCOSIC
• What is secure encryption anyway? • Definition: – Security goal – Assumption on opponent – Security assumption
Indistinguishability ESATCOSIC
ESATCOSIC
• Advantage of a distinguisher
• semantic security: adversary with limited computing power cannot gain any extra information on the plaintext by observing the ciphertext • indistinguishability: adversary with limited computing power cannot find m and m’ for which he distinguish the encryption of m and m’ • Indistinguishability ? semantic security
RSA OAEP adversary/assumption • Adaptive chosen ciphertext attack
Adv ENC = Pr[b’=1|b=1] – Pr[b’=1|b=0] m1,m2 x0= C=E K(m1)
• Assumption: – modular exponentiation is a one-way function for an RSA modulus (or extracting random modular eth roots is hard) – hash function (MGF) is random oracle
xb
x1= C=E K(m2)
b=
b’ = 0/1?
RSA OAEP - security ESATCOSIC
Hoe vercijferen met RSA ESATCOSIC
[BR’93] RSA-OAEP is IND-CCA2 secure under RSA assumption in ROM Shoup ‘00: the proof is wrong
• RSA-KEM – Vercijfer 2 sessiesleutels met RSA – Vercijfer en authentiseer gegevens met deze 2 sessiesleutels
[FOPS 01] RSA-OAEP is IND-CCA2 secure under partial domain one-wayness RSA assumption in ROM for RSA: partial domain one-wayness? one-wayness Reduction is very weak
ROM assumption is questionable
Page 9
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
RSA OAEP - security ESATCOSIC
Bewijsbare veiligheid (2) ESATCOSIC
• Improved chosen ciphertext attack [Manger ‘01]
• Complexiteitstheorie: reductionisme – defineer wat veiligheid betekent (moeilijk) – formeel bewijs dat als tegenstrever het systeem kan breken, hij dan een moeilijk probleem kan oplossen
• requires a few thousand queries (1.1 log2n) • opponent needs oracle that tells whether there is an error in the integer-to-byte conversion or in the OAEP decoding
– moeilijke problemen: discreet log, factorisatie, modulaire wortels, dichtste vector in een rooster, PKP, ….
• overall conclusion: RSA Inc. is no longer recommending the use of RSA-OAEP
• Dit vermijdt heel wat problemen
Bewijsbare veiligheid (3) ESATCOSIC
Onveilige implementaties van RSA ESATCOSIC
• (pseudo)-random number generatie • tijdsgebaseerde aanvallen • vermogenmetingen:
maar...wat zijn moeilijke problemen? James L. Massey: A hard problem is one that nobody works on.
– SPA: Simple Power Analysis – DPA: Differential Power Analysis
geen goede ondergrenzen average vs/ worst case
• Elektromagnetische metingen
SPA attack on RSA
Simple Power Analysis (SPA) on RSA ESATCOSIC
• basic “square and multiply” algorithm with scanning of exponents bits from MSB to LSB (left to right) Example :
s = m9 = m 1001b
init (MSB 1)
s=m
Let k = bitsize of d (say 1024) round 2 (bit 0) Let s = m round 1 (bit 0) For i = k-2 down to 0 round 0 (bit 1) Let s = s*s mod n (SQUARE) If (bit i of d) is 1 then Let s = s*m mod n (MULTIPLY) End if End for
Test key value : 0F 00 F0 00 FF 00
ESATCOSIC
s = m2 s = (m2 ) 2 = m4
SMSMSMSMSSSS
SMSMSM
s = (m4 ) 2 * m = m 9
SSSS SSSS 1
1 1 1 1
0F
0000 0000
00
1
1
SMSMSMSMSMSMSMSM SSSS SSSS SSSS SSSS
1 0000
F0
1 1 1 1 1 1 1 1 0000 0000
00
FF
0000 0000
00
Courtesy: Gemplus
Page 10
Seminarie Dept. Computerwetenschappen Bart Preneel
30 oktober 2003
An SPA attack on RSA ESATCOSIC2
E
C
6
9
1
5
B
F
0010 1 1 10 1 1000 1 10100 1000 10 10 1 10 1 11 1 1
9
4
Zelfs als implementatie veilig is… A
100 10 100 10 10
ESATCOSIC
• • • •
TLS lekt lengte van URL DNS spoofing kan certificaten omzeilen Gebruiker klikt alle verwittigingen weg Kredietkaartnummers worden gestolen uit de database van de handelaar
Key value : 2E C6 91 5B F9 4A
Courtesy: Gemplus
Conclusies ESATCOSIC
• Cryptografie evolueert naar bewijsbare veiligheid • Maar beperkingen in modellen en in veronderstellingen (wat is moeilijk? wat is bewijsbaar veilig?) • Informatiebeveiliging blijft een ingenieursdiscipline
Page 11
