Nøkkelutveksling

I datateknikk , og mer spesielt i cryptology , en nøkkelutvekslingsprotokoll (eller nøkkel forhandling , eller nøkkel etablering , eller nøkkelfordelings ) er en mekanisme ved hjelp av hvilken flere deltakere er enige om en. Kryptografisk nøkkel . Oppfinnelsen av offentlig nøkkelkryptografi på 1970-tallet ga den første nøkkelutvekslingsprotokollen som kan demonstreres som sikker, selv om kommunikasjonen går over en ubeskyttet kanal uten bruk av en pålitelig tredjepart . En av de første protokollene av denne typen, på grunn av Whitfield Diffie og Martin Hellman , er i dag den mest brukte på Internett , gjennom TLS- protokollen . For denne oppfinnelsen ble Diffie og Hellman tildelt den prestisjetunge Turing-prisen i 2016.

Historie

Før 1970

Før oppdagelsen av offentlig nøkkelkryptografi, var det ikke kjent noen matematisk metode for å utføre nøkkelutvekslingen, som avhengig av operativ sikkerhet: nøkkelen måtte kommuniseres via en allerede sikker kanal. For den røde telefonen , som brukte engangsmaskekryptering , involverte dette fysisk transport av diplomatiske poser som inneholdt nøklene (i form av hullkort ) fra USA til Russland , og omvendt.

Men det mest kjente tilfellet er absolutt den for Enigma- maskinen , brukt under 2. verdenskrig av Axis-styrkene for å kryptere radiokommunikasjon. Krypteringsnøklene, som for Enigma tilsvarer tilkoblingsparametrene og valget av rotorer, ble endret daglig av den tyske hæren. Allerede før krigen, i 1932, klarte den franske spionen Hans-Thilo Schmidt å skaffe nøklene til månedene september og oktober samme år. Det er spesielt med denne informasjonen det polske teamet til Marian Rejewski lyktes med å utvikle en dekrypteringsmetode, automatisert fra 1938. Nøkkelen ble endret bare en gang om dagen, alle meldingene som ble fanget opp samme dag ble brutt samtidig. Det er ved å foredle arbeidet til Rejewski, og ved å stole på andre operasjonsfeil fra de tyske styrkene, at Alan Turing vil klare å organisere dekrypteringen av Enigmas kommunikasjon.

Merkle-puslespill

Den første nøkkelutvekslingsmekanismen er av Ralph Merkle , som beskrev den i 1974 og publisert i 1976. Tanken er å komme opp med en offentlig liste over problemer, "puslespillene", som krever litt innsats for å løse., Og som avslører to hemmeligheter en gang løst. For å etablere en nøkkel velger vi tilfeldig ett av disse oppgavene vi løser. Den første hemmeligheten sendes videre til pusleinnehaveren og forteller dem hvilket puslespill som ble løst, og den andre hemmeligheten fungerer som en kryptografisk nøkkel.

En motstander som lytter til samtalen, vet ikke på forhånd hvilket puslespill som er valgt. For å finne nøkkelen som er valgt av de to deltakerne, må motstanderen i verste fall løse alle de foreslåtte oppgavene. Det står derfor overfor et problem med kvadratisk kompleksitet.

I den tilfeldige orakelmodellen kan vi vise at sikkerheten til denne protokollen er effektivt kvadratisk i antall gåter. Denne kompleksiteten anses ikke som tilstrekkelig i moderne kryptografi, men et resultat av Boaz Barak og Mohammad Mahmoody-Ghidary viser at det ikke er mulig å gjøre det bedre i denne modellen.

I 1976, basert på konstruksjonen av Merkle, foreslår Whitfield Diffie og Martin Hellman å bruke problemet med den diskrete logaritmen i et endelig felt , et beregningsproblem som anses vanskelig, som grunnlag for å bygge en nøkkelutvekslingsprotokoll.

Prinsippet om operasjonen er som følger: å etablere en nøkkel, Alice og Bob hemmelighet velge et heltall og hhv. Alice beregner og Bob beregner , hvor er en generator av en ganske stor, forhåndsforhandlet undergruppe. Alice sender til Bob, og Bob sender til Alice. Til slutt beregner Alice og Bob beregner ; disse to størrelsene er faktisk like som det fremgår av en rask beregning. $x_ {A}$ $x_ {B}$ ${\ displaystyle y_ {A} = g ^ {x_ {A}}}$ ${\ displaystyle y_ {B} = g ^ {x_ {B}}}$ $g$ $y_ {A}$ $y_ {B}$ ${\ displaystyle y_ {B} ^ {x_ {A}}}$ ${\ displaystyle y_ {A} ^ {x_ {B}}}$

En motstander som lytter til samtalen står overfor følgende problem: gitt , beregne . Dette problemet kalles beregningsproblemet Diffie-Hellman . I 2018 er den mest kjente metoden for å angripe den å beregne diskrete logaritmer. ${\ displaystyle g, g ^ {x_ {A}}, g ^ {x_ {B}}}$ ${\ displaystyle g ^ {x_ {A} x_ {B}}}$

Å løse den diskrete logaritmen i en generisk førsteordensgruppe krever innsats , dvs. motstanderen står overfor et problem eksponentielt vanskeligere enn brukere av protokollen. I de endelige feltmultiplikasjonsundergruppene som først ble brukt av Diffie og Hellman, er det faktisk mer effektive algoritmer, spesielt varianter av den generelle tallfeltsilen . I 1984 foreslår Neal Koblitz og Victor S. Miller å bruke i stedet gruppen av rasjonelle punkter i en elliptisk kurve . For velvalgte kurver er det ikke kjent noe klassisk angrep som er mer effektivt enn generiske angrep. $s$ ${\ displaystyle O ({\ sqrt {p}})}$

I praksis er det ikke det direkte resultatet av Diffie-Hellman-protokollen som brukes som en nøkkel: den blir heller brukt som kilde til entropi , levert til en nøkkelavledningsfunksjon .

Autentisert nøkkelutveksling

Diffie-Hellman-protokollen, som beskrevet ovenfor, garanterer bare sikkerhet mot en passiv motstander, som er i stand til å lytte til samtalen, men ikke forstyrre den. Hvis motstanderen er i stand til å fange opp kommunikasjon, er det mulig å montere et menneske-i-midten-angrep . For dette trenger motstanderen bare å late som om han er Alice med Bob, og Bob med Alice. Han vil opprette en nøkkel med hver og en, og kan dermed dekryptere meldingene som Alice sender (og, hvis han ønsker det, overføre dem til Bob, potensielt etter å ha endret dem).

For å beskytte deg mot et slikt scenario, må en utvekslingsprotokoll godkjennes. For dette kan vi bruke en signaturordning , og sikre at hver melding som sendes er signert av forfatteren og bekreftet av mottakeren. Av ytelsesgrunner kan det kun produseres en signatur som dekker hele samtalen: dette er tilnærmingen som TLS bruker . Imidlertid svekker denne forenklingen nøkkelutvekslingen i praksis, siden en angriper har til slutten av samtalen å smi en signatur: det er en av komponentene i Logjam-angrepet .

For å kunne bekrefte gyldigheten til en digital signatur, må mottakeren være klar over den tilsvarende bekreftelsesnøkkelen. Det er en langsiktig offentlig nøkkel, som kan sertifiseres for å garantere herkomst. En autentisert nøkkelutveksling er derfor avhengig av tilgjengeligheten av en offentlig nøkkelinfrastruktur . Sikkerheten til den digitale signaturen som brukes, kan være basert på andre forutsetninger enn Diffie-Hellman-problemet, for eksempel vanskeligheten med å faktorisere store heltall for RSA .

Mengden (eller ) som brukes kan således beregnes ved hver økt med en ny (resp. ). Bruken av en "kortvarig" øktnøkkel gir følgende garanti: Hvis en øktnøkkel blir oppdaget av motstanderen, har sistnevnte ingen informasjon om tidligere eller fremtidige økter. Det sies at en slik mekanisme garanterer perfekt vedvarende konfidensialitet . $y_ {A}$ $y_ {B}$ $x_ {A}$ $x_ {B}$

På den annen side tillater den langsiktige nøkkelen som brukes til å signere meldingene, hvis den blir oppdaget av motstanderen, ham til å overvinne identiteten til en av deltakerne. For visse signaturordninger, spesielt signaturene til Schnorr og dets varianter DSA , ECDSA , EdDSA , kan svakheter i tilfeldig tallgenerator avsløre den hemmelige nøkkelen. I 2004 ble Dual_EC_DRBG- algoritmen standardisert av NIST , som en pseudo-tilfeldig tallgenerator beregnet på bruk spesielt for digitale signaturer. I 2013 bekreftet Edward Snowdens avsløringer at dette var et forsøk på å svekke kryptografi (som en del av NSAs Bullrun- program ), slik at forfatterne kunne forutsi generering av tilfeldige tall gjennom en bakdør . Dual_EC_DRBG ble fjernet i 2014 fra den offisielle NIST-listen.

Innkapsling og utveksling av nøkkel autentisert med passord

I stedet for en protokoll der begge parter får en nøkkel, er det mulig at en av partene bestemmer seg for en nøkkel, som den videreføres til den andre. For at denne overføringen skal være sikker, blir nøkkelen som sendes kryptert: dette kalles nøkkelinnkapsling .

En nøkkelinnkapslingsmekanisme kan bruke hvilken som helst offentlig nøkkelkryptering, for eksempel RSA : Alice publiserer sin offentlige nøkkel, Bob velger tilfeldige data som han krypterer med Alice's nøkkel. Disse dataene vil bli brukt til å utlede en nøkkel av begge parter.

Et ekstremt tilfelle av innkapsling består i å bruke symmetrisk kryptering for å sende en nøkkel, noe som krever at de to partene tidligere har koordinert på en hemmelighet. Denne hemmeligheten kan for eksempel være et passord : man snakker om utveksling av nøkkel autentisert med passord (PAKE), hvorav de første versjonene ble foreslått i 1992, som raskt ble ødelagt. De første konstruksjonene med bevis på sikkerhet ble oppnådd i 2000, i modellen av det tilfeldige oraklet . Det første beviset i standardmodellen dateres tilbake til 2001.

Flerpartis nøkkelutveksling

I 2002 viser Antoine Joux hvordan du bruker Weil-koblinger på elliptiske kurver for å utføre, i en sving, en treveis nøkkelutveksling. Hvis Diffie-Hellman-protokollen brukes, vil det kreve etablering av en sikkerhetskanal mellom hvert par.

I 2003 foreslo Dan Boneh og Alice Silverberg å generalisere denne konstruksjonen, for å utveksle en nøkkel mellom et vilkårlig antall deltakere, ved hjelp av en kryptografisk multilinær applikasjon. Dette er en effektivt beregningsbar algoritme som tilfredsstiller spesielt at for alle heltall og alle , vi har , som verifiserer en utvidelse av koblingens sikkerhetsegenskaper. Det var først i 2013 å se de første kandidatene dukke opp, som siden har blitt brutt. ${\ displaystyle e: G_ {1} \ times \ cdots \ times G_ {n} \ rightarrow G_ {T}}$ ${\ displaystyle a_ {1}, \ dotsc, a_ {n}}$ ${\ displaystyle g_ {i} \ i G_ {i}}$ ${\ displaystyle e (g_ {1} ^ {a_ {1}}, \ ldots, g_ {n} ^ {a_ {n}}) = e (g_ {1}, \ ldots, g_ {n}) ^ { \ prod _ {i = 1} ^ {n} a_ {i}}}$

Konstruksjonen av en effektiv nøkkelutvekslingsprotokoll med flere partier, og utformingen av en kryptografisk flerlinjeapplikasjon, er fremdeles åpne forskningsspørsmål i 2018.

Det diskrete logaritmeproblemet, som Diffie-Hellman-protokollen er basert på, kan løses effektivt på en kvantecomputer ved hjelp av Shors algoritme . I tillegg er signaturen som brukes til å autentisere en økt også i fare.

Det er derfor foreslått flere erstatningsprotokoller som ikke lider av slike svakheter. Blant forslagene teller vi spesielt Jao-De Feo-algoritmen, basert på isogenier av supersingulære elliptiske kurver, og New Hope-algoritmen, basert på korte vektorproblemer i euklidiske nettverk. New Hope ble implementert og brukt eksperimentelt i Google Chrome- nettleseren i 2016.

Uavhengig av forrige avsnitt ble det foreslått å bruke fysikkens egenskaper i stedet for matematiske og beregningsmessige garantier for å sikre sikkerheten til nøkkelutvekslingen. Mer spesifikt gjør observasjonen av de statistiske egenskapene til en strøm av sammenfiltrede partikler , assosiert med ikke-kloningssatsen, det mulig å oppdage en motstander som lytter, og å "kaste" en del av bitene som er avslørt ved å korrigere støy (som korrigerer også feil som ligger i målene). Dette forsoningstrinnet resulterer i en sekvens av biter som er felles for de to partene som ønsker å utveksle en nøkkel. Et ekstra forsterkningstrinn er nødvendig for å kunne utlede en nøkkel fra den felles sekvensen.

Flere av disse protokollene er implementert og validert eksperimentelt, over avstander på flere hundre kilometer.

Imidlertid gir kvantenøkkelutveksling en rekke teknologiske og operasjonelle utfordringer, som for øyeblikket begrenser distribusjonen: spesielt må det opprettes en spesifikk kommunikasjonskanal mellom deltakerne. For eksempel, for BB84 , B92 eller SARG04 protokoller , er det nødvendig å være i stand til å sikre transporten av lavenergifotoner samtidig bevare sin polarisasjon til tross for de fenomener av decoherence over hele lengden av kanalen.

Merknader og referanser

Merknader

Siden dette er en enkelt nøkkel, snakker vi om nøkkelutveksling, i entall, og ikke om nøkkelutveksling.

Referanser

(in) " Cryptography Pioneers Receive ACM AM Turing Award " på www.acm.org (åpnet 20. september 2018 )
Se http://www.merkle.com/1974/ og http://www.merkle.com/1974/Puzzles1975.12.07.pdf .
(i) RC Merkle, "Sikker kommunikasjon over usikre kanaler", Kommunikasjon av ACM 21 (4), s. 294-299 (april 1978).
(in) Boaz Barak og Mohammad Mahmoody-Ghidary , Merkle Puzzles are Optimal - An O (n ²) -Query Attack on Any Key Exchange from a Random Oracle, Advances in Cryptology - CRYPTO 2009 , Springer, Berlin, Heidelberg, al. "Forelesningsnotater i informatikk",2009( ISBN 9783642033551 og 9783642033568 , DOI 10.1007 / 978-3-642-03356-8_22 , les online ) , s. 374–390
(i) Steven M. Bellovin og Michael Merritt , " Kryptert Key Exchange: passordbaserte protokoller sikre contre ordbok angrep " , Proceedings 1992 IEEE Computer Society Symposium on Research in Sikkerhet og personvern ,Mai 1992, s. 72–84 ( DOI 10.1109 / risp.1992.213269 , lest online , åpnet 17. mars 2018 )
(i) Steven M. Bellovin og Michael Merritt , " Augmented kryptert nøkkel utveksling: en passordbaserte sikker protokoll contre ordbokangrep og passordfilen kompromittert " , Proceedings of første ACM konferanse om Computer og kommunikasjon sikkerhet (CCS '93) , ACM,1 st desember 1993, s. 244–250 ( ISBN 0897916298 , DOI 10.1145 / 168588.168618 , lest online , åpnet 17. mars 2018 )
(i) Mihir Bellare David Pointcheval og Phillip Rogaway , " Godkjente Key Exchange-Secure contre ordbokangrep " , Advances in Kryptologi - EUROCRYPT 2000 , Springer, Berlin, Heidelberg, lese noter i Computer Science,14. mai 2000, s. 139–155 ( ISBN 3540455396 , DOI 10.1007 / 3-540-45539-6_11 , leses online , åpnes 17. mars 2018 )
(i) Victor Boyko , Philip MacKenzie og Sarvar Patel , " beviselig sikker passordautentisert nøkkelutveksling ved bruk av Diffie-Hellman " , Fremskritt innen kryptologi - EUROCRYPT 2000 , Springer, Berlin, Heidelberg, les Notater i datavitenskap,14. mai 2000, s. 156–171 ( ISBN 3540455396 , DOI 10.1007 / 3-540-45539-6_12 , leses online , åpnes 17. mars 2018 )
(in) Oded Goldreich og Yehuda Lindell , " Session-Key Generation Using Only Human Passwords " , Journal of Cryptology , vol. 19, n o 3,1 st juli 2006, s. 241–340 ( ISSN 0933-2790 og 1432-1378 , DOI 10.1007 / s00145-006-0233-z , les online , åpnet 17. mars 2018 )
(i) Jonathan Katz , Rafail Ostrovsky og Moti Yung , " Effektiv passordautentisert nøkkelutveksling ved hjelp av menneskelige minneverdige passord " , Fremskritt i kryptologi - EUROCRYPT 2001 , Springer, Berlin, Heidelberg, les Notater i datavitenskap,6. mai 2001, s. 475–494 ( ISBN 3540449876 , DOI 10.1007 / 3-540-44987-6_29 , leses online , åpnes 17. mars 2018 )
(in) Antoine Joux , " The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems " , Algorithmic Number Theory , Springer, Berlin, Heidelberg, les Notes in Computer Science,7. juli 2002, s. 20–32 ( ISBN 3540454551 , DOI 10.1007 / 3-540-45455-1_3 , leses online , åpnes 17. mars 2018 )
(i) Dan Boneh og Alice Silverberg, "Applications of Multilinear Forms to Cryptography" Contemporary Mathematics Vol. 324, American Mathematical Society, s. 71-90, 2003
(in) Sanjam Garg , Craig Gentry og Shai Halevi , " Candidate Multilinear Maps from Ideal Lattices " , Fremskritt innen kryptologi - EUROCRYPT 2013 , Springer, Berlin, Heidelberg, les Notater i datavitenskap,26. mai 2013, s. 1–17 ( ISBN 9783642383472 , DOI 10.1007 / 978-3-642-38348-9_1 , lest online , åpnet 17. mars 2018 )
(en) Jean-Sébastien Coron , Tancred Lepoint og Mehdi Tibouchi , Advances in Cryptology - CRYPTO 2013 , Springer, Berlin, Heidelberg, al. "Forelesningsnotater i informatikk",2013( ISBN 9783642400407 og 9783642400414 , DOI 10.1007 / 978-3-642-40041-4_26 , les online ) , s. 476-493
(no) Jung Hee Cheon , Kyoohyung Han , Changmin Lee og Hansol Ryu , " Cryptanalysis of the over-the Multilinear Map Integers " , Advances in Cryptology - EUROCRYPT 2015 , Springer, Berlin, Heidelberg, les Notes in Computer Science,26. april 2015, s. 3–12 ( ISBN 9783662467992 , DOI 10.1007 / 978-3-662-46800-5_1 , lest online , åpnet 17. mars 2018 )
(no) Jung Hee Cheon , Pierre-Alain Fouque , Changmin Lee og Brice Minaud , " Cryptanalysis of the New CLT Multilinear Map over the Integers " , Fremskritt innen kryptologi - EUROCRYPT 2016 , Springer, Berlin, Heidelberg, les Notes in Computer Science ,8. mai 2016, s. 509-536 ( ISBN 9783662498897 , DOI 10.1007 / 978-3-662-49890-3_20 , leses online , åpnes 17. mars 2018 )
(i) Eric Miles , Amit Sahai og Mark Zhandry , " Annihilation Attacks for Multilinear Maps: Cryptanalysis of indistinguishability Obfuscation over GGH13 " , Advances in Cryptology - CRYPTO 2016 , Springer, Berlin, Heidelberg, les Notes in Computer Science,14. august 2016, s. 629–658 ( ISBN 9783662530078 , DOI 10.1007 / 978-3-662-53008-5_22 , leses online , åpnes 17. mars 2018 )
(en) Jean-Sébastien Coron , Moon Sung Lee , Tancred Lepoint og Mehdi Tibouchi , " Cryptanalysis of GGH15 Multilinear Maps " , Fremskritt innen kryptologi - CRYPTO 2016 , Springer, Berlin, Heidelberg, les Notater i informatikk,14. august 2016, s. 607-628 ( ISBN 9783662530078 , DOI 10.1007 / 978-3-662-53008-5_21 , leses online , åpnes 17. mars 2018 )
(i) David Jao og Luca De Feo , " Mot kvantebestandige kryptosystemer fra supersingular isogenies elliptisk kurve " , post-kvante kryptografi , Springer, Berlin, Heidelberg, les Notes in Computer Science,29. november 2011, s. 19–34 ( ISBN 9783642254048 , DOI 10.1007 / 978-3-642-25405-5_2 , leses online , åpnes 17. mars 2018 )
(i) Erdem Alkım Leo Ducas, Pöppelmann Thomas og Peter Schwabe, "Post-Quantum Key Exchange - A New Hope," USENIX Security Symposium , 2016, s. 327-343
(in) Matt Braithwaite, " Eksperimentere med kvantum etter kvante " på security.googleblog.com ,7. juli 2016
(in) Boris Korzh , Charles Ci Wen Lim , Raphael Houlmann og Nicolas Gisin , " beviselig sikker kvantenøkkelfordeling og praktisk over 307 km optisk fiber " , Nature Photonics , Vol. 9, n o 3,mars 2015, s. 163–168 ( ISSN 1749-4893 , DOI 10.1038 / nphoton.2014.327 , lest online , åpnet 17. mars 2018 )
(i) Charles H. Bennett , " Quantum cryptography using any two nonorthogonal states " , Physical Review Letters , vol. 68, n o 2125. mai 1992, s. 3121–3124 ( DOI 10.1103 / PhysRevLett.68.3121 , lest online , åpnet 17. mars 2018 )
(i) Valerio Scarani , Antonio Acín Grégoire Ribordy og Nicolas Gisin , " Quantum Cryptography Protokoller Robust contre Photon Antall angrep som splitter for svake laser puls implementeringer " , Physical Review Letters , vol. 92, n o 5,6. februar 2004, s. 057901 ( DOI 10.1103 / PhysRevLett.92.057901 , lest online , åpnet 17. mars 2018 )