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 <AHQNE XVAZW IQFFR JENFV BXFRZ NJVYB QVGOZ KFYQV GAZJK RDJQC VJTEB XNZZH DQCGF Q PWCVR UOMWW LOGSO YTZAA OIJDR UEAAV RWYXH HSUIY PKFPZ OSEAW SUZMY WLSSD ZVKPU ZSHKK PALWB AHQNE 11205 141100> 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
© Copyright 2024 ExpyDoc
