Cryptografie is overal
Cryptografie: van discrete wiskunde tot veilige betalingen Prof. Dr. Ir. Bart Preneel Dept. Elektrotechniek-COSIC
[email protected]
1
2
Geheime communicatie
De Hagelin C38
?
bericht
CRY PTO BOX
%^C& @&^(
%^C& @&^(
CRY PTO BOX
bericht
4
3
Ontcijferd (2001)
Een Belgisch voorbeeld 14 januari 1961 11u00
OUXBD GEDBE MEVGS ZWVVV PAWSV QDYEL SHXRR
DOFGD VISWA WVISW OWMIS SIONW BOMBO EWSUJ ETWAM BABEL BISEC TWTRE SECVX WXXWP RIMOW RIENW XWPOU VEZWR EGLER RENDR EWDUR GENCE
LQWDB HGMPS ANLLB LDQNI Q CHTYN FUVOA MLQOK
5
JOSEP HWXXW TERTI KOWVO IRWTE LEXWC GEWXX WJULE SWXXW XWRWV WMWPR INTEX ENVOY EWRUS URWWX WXXWS ECUND OWREP WPLAN WBRAZ ZAWWC
6
1
Ontcijferd en herschikt
Advanced Encryption Standard (AES) bericht
• Belgisch algoritme Rijndael
ronde 1
• Opeenvolging van 10/12/14 ronden • Elke ronde bevat – Substituties sleutel – Mengtransformaties – Sleutel-afhankelijke operaties
Sleutelexpan nsie
TRESECV. R V M PRINTEX. PRIMO RIEN ENVOYE RUSUR. POUVEZ REGLER. SECUNDO REPRENDRE DURGENCE PLAN BRAZZA VIS A VIS JOSEP H. H TERTIO MISSION BOMBOKO VOIR TELEX CE SUJET AMBABELGE. JULES.
ronde 2 ronde 3
.. . ronde R
• Sleutel van 128, 192 of 256 bits
cijfertekst8
7
Publieke sleutel encryptie
Fundamenteel probleem van symmetrische cryptografie: hoe kunnen alle gebruikers met elkaar een sleutel afspreken?
?
bericht
CRY PTO BOX
%^C& @&^(
%^C& @&^(
CRY PTO BOX
bericht
9
10
Publieke sleutel encryptie
Vercijferen met RSA
Publieke sleutel • gebruikt voor encryptie • zo wijd mogelijk bekend gemaakt
• • • • • •
Private sleutel • gebruikt voor decryptie • aan niemand bekend gemaakt
Kies 2 grote priemgetallen p, q Bereken n = p x q Kies r met ggd(r, (p-1) x (q-1)) = 1 Bereken s zodat r x s = 1 mod ((p-1) x (q-1)) Publieke sleutel: (r,n) Private sleutel: (s,n)
• Encryptie: c = mr mod n • Decryptie m = cs mod n 11
12
2
Veiligheid van RSA
Hoe moeilijk is n te factoriseren?
• s mag niet eenvoudig volgen uit (r,n)
The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers
• s wordt berekend uit s x r = 1 mod ((p-1)x(q-1)) p q • Vereist p, • Factoriseer n • Moeilijk! (?)
Gates, The Road Ahead, 1995
13
Factorisatie records
14
Picture of the lab 4-channel Varian
2009: 768 bits of 232 decimalen
spectrometer
11.7 T Oxford magnet, room temperature bore
# cijfers
1 decimaal cijfer ~3.3 bits 250
768 bits
200
512 bits
15 5 3 15=5x3
150 100 50
grad students in sunny California...
0 64
68
72
76
80
84
88
92
96 1002000 104 2009 108 15
Quantum computers
2001
16
In praktijk vaak r = 3. Waarom?
• 2001: 7-bit quantum computer factoriseert 15 • 2007: twee nieuwe 7-bit quantum computers factoriseren 15 • 2012: 143 wordt gefactoriseerd • 2011: grote quantum computer kan men binnen 10 jaar verwachten
Quantum Computing: An IBM Perspective [2011] Steffen, M.; DiVincenzo, D. P.; Chow, J. M.; Theis, T. N.; Ketchen, M. B. \. The implementation of a functioning quantum computer poses tremendous scientific and technological challenges, but current rates of progress suggest that these challenges will be substantively addressed over the next ten years. We provide a sketch of a quantum computing system based on superconducting circuits, which are the current focus of our research. A realistic vision emerges concerning 17 the form of a future scalable fault-tolerant quantum computer.
Snelheid !!!
10-100 cycli
AES (16 blokken = 1024 bytes)
1500 cycli
1.2 miljoen cycli
RSA 1024 RSA 1024 (r=3)
6000 cycli
6 miljoen cycli
RSA 2048 RSA 2048 (r=3)
24000 cycli
32 miljoen cycli
RSA 4096 RSA 4096 (r=3)
Haswell (306c3); 2013 Intel Core i5-4570S; 4 x 2900MHz
18
3
Hybride vercijfering
Veilige communicatie naar een site met TLS
• Vercijfering met publieke sleutels (RSA)
• Prentje van https site
– eenvoudig sleutelbeheer
• Klassieke vercijfering (AES) – snel
• Combinatie: 1. 2. 3. 4.
genereer een sleutel voor AES vercijfer de (lange) boodschap met AES vercijfer de AES-sleutel met RSA verstuur alles
19
20
Veilige communicatie naar een site met TLS
Authenticatie van een bericht (is het bericht correct?)
21
22
Authenticatie van een bericht (is het correct?)
Authenticatie van een bericht (is het correct?)
?
Blijf maar gas kopen van Putin
CRY PTO BOX
%^C& @&^(
%^C& @&^(
Van wie zou dit bericht zijn?
CRY PTO BOX
Blijf maar gas kopen van Putin
Bericht
handteken
Bericht
Bericht
verifieer
Bericht
Probleem in digitale wereld: 23
• Copiëren van handtekening • Wijzigen van bericht
24
4
Vereisten voor digitale handtekening
Digitale handtekening
• Gemakkelijk verifieerbaar • Uniek verbonden aan een persoon • Niet overdraagbaar van een document op een ander • Wordt ongeldig als document gewijzigd wordt Bericht
handteken
Bericht
Bericht
verifieer
Bericht
25
26
Digitale handtekening met RSA
This is an input to a cryptographic hash function. The input is a very long string, that is reduced by the hash function to a string of fixed length.
This is an input to a cryptographic hash function. The input is a very long string, that is reduced by the hash function to a string of fixed length.
hash
hash Private sleutel s
Publieke sleutel r, n
y= h(m)s mod n
s=4F80DFD41A198FB3CA3459
Ja
h(m)=yr mod n
Nee
s=4F80DFD41A198FB3CA3459 28
27
De elektronische identiteitskaart
Veilig inloggen op een website
Voor elke Belgische burger van 12 jaar en ouder • RSA sleutelpaar 1 om berichten te handtekenen • RSA sleutelpaar 2 om in te loggen op een website
Challenge response protocol s, r, n
r, n willekeurig getal x [0,n-1]
y= h(x)s mod n 1 2
veel veiliger dan een wachtwoord 30 29
5
Home pagina
Hoe vind ik de publieke sleutel van een gebruiker?
31
Certificaat
32
Certificaat op je computer
De heer Stefaan Vaes heeft publieke sleutel: D6AC3672242A...56F82
Getekend: Luc Vanneste Rijksregister
• Inhoud: – naam + publieke sleutel van burger – digitale handtekening met private sleutel van rijksregister
• Verificatie – met publieke sleutel van rijksregister – hoe vind ik deze sleutel?
33
Certificaten-boom: eID • Hoe kan je de handtekening van het certificaat verifiëren?
34
Certificaten-boom: kredietkaart • Hoe kan je de handtekening van het certificaat verifiëren?
Publieke sleutel zit in browser
Publieke sleutel zit in elke betaalterminal
Globalsign
Visa
Rijksregister
Stefaan Vaes
Bank: KBC
Stefaan Vaes
6
EMV: Europay, MasterCard en Visa • • • •
Elektronische betalingen
sinds 1995 1.5 miljard kaarten (10% van alle bankkaarten) meer dan 20 miljoen terminals specificaties: meer dan 5000 blz
37
38
Zeven manieren om EMV te breken
EMV betaling (vereenvoudigd) r, n, #
s, r, n, #
•
r, n Bedrag b=100 EUR. Enter PIN
RSA(PIN) = (PIN)r mod n
• •
|| u
Verifieer PIN PIN = 4321
PIN OK (9000)
•
Sommige van de aanvallen hier beschreven hebben ooit gewerkt De meeste aanvallen worden verhinderd door bijkomende beveiligingsoplossingen j ook heel wat niet-cryptografische yp g Er zijn verdedigingsmechanismen, zoals het strafrecht Don’t try this at home
y1= h(# || b || u)s mod n Transactie OK
Verifieer handtekening 40 39
Hoe kan je EMV breken?
Hoe kan je EMV breken?
1. Steel een kaart
2. Steel een kaart
•
• •
Je hebt ook de PIN nodig – – – –
raad de PIN (1234, 0000, 1111) “over de schouder meekijken” j micro camera aftappen van terminal
•
geef een willekeurige PIN in onderschep de PIN voor ze de kaart bereikt stuur zelf een PIN OK bericht –
41
de EMV kaarten van sommige banken merkten dit niet op
42
7
Hoe kan je EMV breken?
EMV betaling (vereenvoudigd) r, n, #
s, r, n, #
3. Factoriseer de modulus n: vind p en q en dan s
r, n
– PIN ontcijferen – handtekening vervalsen
Bedrag b=100 EUR. Enter PIN
RSA(PIN) = (PIN)r mod n
• Vandaag: g 1536..2048 bits
|| u
Verifieer PIN PIN = 4321
• Wat als er een wiskundige doorbraak komt?
PIN OK (9000)
– alle EMV terminals vervangen duurt 5-10 jaar y1= h(# || b || u)s mod n Transactie OK
Verifieer handtekening 44 43
Hoe kan je EMV breken?
Intermezzo: RSA voor kleine getallen
4. Factoriseer de modulus n: vind p en q en dan s • boodschap m=0 dan c = (0)r mod n = ? • boodschap m=1 dan c = (1)r mod n = ?
– PIN ontcijferen – handtekening vervalsen
• Dit is g gemakkelijk j als p en q niet helemaal willekeurig g zijn j • • • • •
0 1
• stel r = 3 – cijfertekst c = 8 = m3 mod n; m =? – cijfertekst c = 27 = m3 mod n; m =? – cijfertekst c = 125 = m3 mod n; m =?
Verzamel groot aantal (10 miljoen) publieke sleutels ni Bereken ggd(ni ,nk) i, k Als je geluk hebt: ni = pi .qi en nk = pk .qk met qi = qk Dan geldt dat ggd(ni ,nk) = qi Dit probleem blijkt in praktijk helaas voor te komen
2 3 5
• Het berekenen van een 3de wortel mod n is moeilijk, maar het berekenen van een 3de wortel over de gehele getallen is vrij eenvoudig 45
Implicaties op PIN encryptie
Implicaties op PIN encryptie (2)
5. Vind de PIN zonder n te factoriseren
• Oplossing: RSA(PIN): (111…….111 || 00 || PIN)r mod n
• Wat met (PIN)r mod n met r=3? – PIN < 104 – (PIN)r < 1012 dus als n > 1012 (40 bits) geldt dat (PIN)r mod n = (PIN)r • Het is dus eenvoudig om de PIN terug te vinden
• Aanval: bereken een tabel met 10.000 elementen – PIN, RSA(PIN) • dat d t duurt d t een paar seconden d en vraagtt 2.5 2 5 Mbyte Mb t • Je kan nu de PIN opzoeken in de tabel
• Oplossing: (111…….111 || 00 || PIN)r mod n • Nu geldt dat het argument groot is • Is dit veilig?
46
• Betere oplossing: (111…….111 || u || 00 || PIN)r mod n • Probleem in praktijk: sommige terminals genereren waarden van u die voorspelbaar zijn… 47
48
8
Veiligheid RSA
Hoe kan je EMV breken?
• Bewezen is: Factoriseer(n) RSA “gebroken” • Wat betekent “RSA gebroken”?
6. Vervang in de terminal de publieke sleutel van Visa door jouw publieke sleutel
– RSA breken is het vinden van een een r-de machtswortel modulo n
– Je kan nu eigen kaarten maken met valse certicaten – alle betalingen worden aanvaard
• Wat met ? belangrijk g j open p p probleem in de cryptografie yp g • De RSA-veronderstelling: het vinden van een r-de machtswortel van een getal willekeurig gekozen in [0,n-1] is moeilijk – merk op dat het vinden van een r-de machtswortel voor kleine getallen gemakkelijk is – maar als je een willekeurig getal kiest in [0,n-1] is de kans verwaarloosbaar dat het een heel klein getal is
• Oplossing: het moet moeilijk zijn om de publieke sleutel van Visa in een terminal aan te passen
49
50
Slotopmerking
Hoe kan je EMV breken? 7. Fysica
• Informatie wordt de olie van de digitale maatschappij genoemd • Enige mogelijke bescherming tegen massale verzameling g van informatie is cryptografie yp g en verwerking • Cryptografie steunt in sterke mate op wiskunde – maar ook computerwetenschappen, elektrotechniek
51
52
9
