Avainten vaihto

In computer science , ja erityisemmin kryptologian , eli avainten vaihdon protokollaa (tai avaimen neuvottelu tai avain laitoksessa tai avainjakauman ) on mekanismi, jolla useat osallistujat sopia. Salausavaimen . Julkisen avaimen salauksen keksiminen 1970-luvulla tuotti ensimmäisen avaimenvaihtoprotokollan, jonka voidaan osoittaa olevan turvallinen, vaikka viestintä tapahtuu suojaamattomalla kanavalla, ilman luotettavan kolmannen osapuolen käyttöä . Yksi ensimmäisistä tämäntyyppisistä protokollista Whitfield Diffien ja Martin Hellmanin vuoksi on nykyään eniten käytetty Internetissä TLS- protokollan kautta . Tästä keksinnöstä Diffie ja Hellman palkittiin arvostetulla Turing-palkinnolla vuonna 2016.

Historia

Ennen vuotta 1970

Ennen julkisen avaimen salauksen löytämistä ei tiedetty mitään matemaattista menetelmää avainten vaihdon suorittamiseksi, joka perustui täysin operatiiviseen turvallisuuteen: avain oli ilmoitettava jo suojatun kanavan kautta. Sillä punainen puhelin , jota käytetään kertakäyttöisiä maski salausta , tämä tarkoitti fyysisen kuljetuksen diplomaattilaukut sisältävien avaimet (muodossa reikäkortit ) pois Yhdysvaltojen ja Venäjän , ja päinvastoin.

Mutta tunnetuin tapaus on varmasti kuin Enigma koneen , käytetään aikana toisen maailmansodan , jonka Akseli voimat salata radioliikennettä. Saksan armeija vaihtoi päivittäin Enigman salausavaimet, jotka vastaavat yhteysparametreja ja roottoreiden valintaa. Jo ennen sotaa, vuonna 1932, ranskalainen vakooja Hans-Thilo Schmidt onnistui saamaan avaimet saman vuoden syys- ja lokakuussa. Erityisesti näiden tietojen avulla puolalainen Marian Rejewskin joukkue onnistui kehittämään salauksen purkumenetelmän, joka oli automatisoitu vuodesta 1938. Avainta vaihdettiin vain kerran päivässä, kaikki samana päivänä siepatut viestit rikottiin samanaikaisesti. Alan Turing onnistuu organisoimaan Enigman viestinnän salauksen purkamalla Rejewskin työtä ja turvautumalla muihin Saksan joukkojen operatiivisiin virheisiin .

Merkle palapeli

Ensimmäisen avaimenvaihtomekanismin on Ralph Merkle , joka kuvasi sitä vuonna 1974 ja julkaisi vuonna 1976. Ajatuksena on laatia julkinen luettelo ongelmista, "pulmista", joiden ratkaiseminen vaatii jonkin verran ponnisteluja. salaisuudet kerran ratkaistu. Avaimen luomiseksi valitsemme satunnaisesti yhden näistä pulmista, jotka ratkaisemme. Ensimmäinen salaisuus välitetään palapelin omistajalle ja kertoo heille, mikä palapeli on ratkaistu, ja toinen salaisuus toimii salausavaimena.

Keskustelua kuunteleva vastustaja ei a priori tiedä mikä palapeli on valittu. Kahden osanottajan valitseman avaimen löytämiseksi vastustajan on pahimmassa tapauksessa ratkaistava kaikki ehdotetut pulmat. Siksi se kohtaa toisen asteen monimutkaisuuden ongelman.

Vuonna satunnainen oraakkeli mallia , voimme osoittaa, että turvallisuuden, protokolla on käytännössä neliömäinen määrä arvoituksia. Tätä monimutkaisuutta ei pidetä riittävänä nykyaikaisessa salauksessa, mutta Boaz Barakin ja Mohammad Mahmoody-Ghidaryn tulos osoittaa, että tässä mallissa ei voida tehdä paremmin.

Vuonna 1976, nojaten rakentaminen Merkle, Whitfield Diffie ja Martin Hellman ehdottaa käyttämään ongelma diskreetti logaritmi on äärellisessä kentässä , laskennallinen ongelma pitää vaikeaa, koska perustana rakentaa avaintenvaihtoprotokollaa.

Toimintaperiaate on seuraava: avaimen luomiseksi Alice ja Bob valitsevat salaa kokonaisluvun ja vastaavasti. Alice laskee ja Bob laskee , missä on melko suuren, etukäteen neuvoteltujen alaryhmien generaattori. Alice lähettää Bobille ja Bob Alicelle. Lopuksi Alice laskee ja Bob laskee  ; nämä kaksi määrää ovat itse asiassa yhtä suuret, mikä voidaan nähdä nopeasta laskelmasta.

Keskustelua kuunteleva vastustaja kohtaa seuraavan ongelman: annettu , laskettu . Tätä ongelmaa kutsutaan Diffie-Hellmanin laskennalliseksi ongelmaksi . Vuonna 2018 tunnetuin tapa hyökätä siihen on laskea erilliset logaritmit.

Diskreetin logaritmin ratkaiseminen geneerisessä ensimmäisen kertaluvun ryhmässä vaatii ponnistelua , eli vastustaja kohtaa eksponentiaalisesti vaikeampaa ongelmaa kuin protokollan käyttäjät. Diffien ja Hellmanin alun perin käyttämissä äärellisissä kenttien multiplikatiivisissa alaryhmissä on itse asiassa tehokkaampia algoritmeja, varsinkin muunnelmia yleistetystä lukukenttäseulasta . Vuonna 1984 Neal Koblitz ja Victor S. Miller ehdottavat käyttää sen sijaan elliptisen käyrän järkevien pisteiden ryhmää . Hyvin valituille käyrille ei tunneta klassista hyökkäystä, joka olisi tehokkaampi kuin yleiset hyökkäykset.

Käytännössä avaimena ei käytetä Diffie-Hellman -protokollan suoraa tulosta: sitä käytetään pikemminkin entropian lähteenä , joka toimitetaan avaimen johtamisfunktiolle .

Todennettu avaimenvaihto

Edellä kuvattu Diffie-Hellman-protokolla takaa vain turvallisuuden passiivista vastustajaa vastaan, joka pystyy salakuuntelemaan keskustelua, mutta ei häiritse sitä. Jos vastustaja pystyy sieppaamaan viestinnän, on mahdollista järjestää mies keskelle -hyökkäys . Tätä varten vastustajan on vain esitettävä olevansa Alice Bobin kanssa ja Bob Alicen kanssa. Hän muodostaa avaimen jokaisen kanssa ja voi siten purkaa Alicen lähettämät viestit (ja haluttaessa lähettää ne Bobille mahdollisesti muutettuaan ne).

Tällaisen tilanteen estämiseksi vaihtoprotokolla on todennettava. Tätä varten voimme käyttää allekirjoitusjärjestelmää ja varmistaa, että kukin lähetetty viesti on sen kirjoittajan allekirjoittama ja vastaanottajan vahvistama. Suorituskyvyn vuoksi vain koko keskustelun kattava allekirjoitus voidaan tuottaa: tämä on TLS : n omaksuma lähestymistapa . Tämä yksinkertaistaminen kuitenkin heikentää avaimenvaihtoa käytännössä, koska hyökkääjällä on keskustelun loppuun asti väärennettävä allekirjoitus: se on yksi Logjam-hyökkäyksen komponentteista .

Digitaalisen allekirjoituksen oikeellisuuden varmistamiseksi vastaanottajan on oltava tietoinen vastaavasta vahvistusavaimesta. Se on pitkäaikainen julkinen avain, joka voidaan sertifioida sen alkuperän takaamiseksi. Todennettu avaintenvaihto perustuu siten julkisen avaimen infrastruktuurin saatavuuteen . Turvallisuus digitaalisen allekirjoituksen käytetään, voi perustua muihin olettamuksiin kuin Diffie-Hellman ongelma, kuten vaikeus factoring suuret kokonaislukuja varten RSA .

Käytetty määrä (tai ) voidaan siten laskea jokaisessa istunnossa uudella (tai vastaavalla ). Käytön, "lyhytaikainen" istuntoavainta tarjoaa seuraavat takuu: Jos istunto avain huomaa vastustaja, jälkimmäinen ei ole tietoa menneisyydessä tai tulevaisuudessa istuntoja. Sanotaan, että tällainen mekanismi takaa täydellisen jatkuvan luottamuksellisuuden .

Toisaalta viestien allekirjoittamiseen käytetty pitkäaikainen avain, jos vastustaja havaitsee sen, antaa hänelle mahdollisuuden anastaa yhden osanottajan henkilöllisyyden. Tietyissä allekirjoitusjärjestelmissä, erityisesti Schnorrin ja sen muunnelmien DSA , ECDSA , EdDSA , allekirjoituksissa satunnaislukugeneraattorin heikkoudet saattavat paljastaa salaisen avaimen. Vuonna 2004 NIST standardisoi Dual_EC_DRBG- algoritmin näennäissatunnaislukugeneraattorina, joka on tarkoitettu käytettäväksi erityisesti digitaalisissa allekirjoituksissa. Vuonna 2013 Edward Snowden n paljastuksia vahvisti, että tämä oli yritys heikentää kryptografia (osana on NSA: n Bullrun ohjelma ), joiden avulla sen laatijat ennustaa sukupolven satunnaislukuja läpi takaoven . Dual_EC_DRBG poistettiin vuonna 2014 virallisesta NIST-luettelosta.

Salasanalla todennettu avaimen kapselointi ja vaihto

Sen sijaan, että protokolla, jossa molemmat osapuolet hankkivat avaimen, on mahdollista, että toinen osapuolista päättää avaimen, jonka se välittää toiselle. Jotta tämä lähetys olisi turvallista, lähetetty avain salataan: tätä kutsutaan avainkapseloinniksi .

Avainten kapselointimekanismi voi käyttää mitä tahansa julkisen avaimen salausta, esimerkiksi RSA  : Alice julkaisee julkisen avaimensa, Bob valitsee satunnaiset tiedot, jotka hän salaa Alice-avaimella. Näitä tietoja käytetään molempien osapuolten avaimen johtamiseen.

Äärimmäinen kapselointitapaus koostuu symmetrisen salauksen käytöstä avaimen lähettämiseen, mikä edellyttää, että molemmat osapuolet ovat aiemmin koordinoineet salaisuuden. Tämä salaisuus voi olla esimerkiksi salasana  : puhutaan salasanalla todennetusta avaimen vaihdosta (PAKE), josta ensimmäisiä versioita ehdotettiin vuonna 1992 ja jotka hajotettiin nopeasti. Ensimmäiset rakenteet, joilla oli todiste turvallisuudesta, saatiin vuonna 2000, satunnaisen oraakelin mallina . Ensimmäinen malli vakiomallissa on vuodelta 2001.

Monen osapuolen avainten vaihto

Vuonna 2002 Antoine Joux osoittaa, kuinka Weil-kytkimiä käytetään elliptisillä käyrillä kolmitoimisen avaimenvaihdon suorittamiseksi yhdessä käännöksessä. Diffie-Hellman -protokolla edellyttäisi turvakanavan perustamista jokaisen parin välille, jos sitä käytettäisiin.

Vuonna 2003 Dan Boneh ja Alice Silverberg ehdottivat tämän rakenteen yleistämistä, jotta avain voidaan vaihtaa mielivaltaisen määrän osallistujia varten kryptografisen monirivisen sovelluksen avulla. Tämä on tehokkaasti laskettavissa oleva algoritmi, joka tyydyttää erityisesti sen, että kaikki kokonaisluvut ja kaikki meillä on , mikä vahvistaa kytkinten turvallisuusominaisuuksien laajentumisen. Ensimmäiset ehdokkaat, jotka on sittemmin hajonnut, näkyi vasta vuonna 2013.

Tehokkaan monen osapuolen avaimenvaihtoprotokollan rakentaminen ja salauksen monirivisen sovelluksen suunnittelu ovat edelleen avoimia tutkimuskysymyksiä vuonna 2018.

Erillinen logaritmiongelma, johon Diffie-Hellman-protokolla perustuu, voidaan ratkaista tehokkaasti kvanttitietokoneella Shorin algoritmia käyttämällä . Lisäksi istunnon todentamiseen käytetty allekirjoitus on myös vaarassa.

Siksi on ehdotettu useita korvausprotokollia, jotka eivät kärsi tällaisista heikkouksista. Ehdotuksista lasketaan erityisesti Jao-De Feo -algoritmi, joka perustuu supersinkulaaristen elliptisten käyrien isogeeneihin, ja New Hope -algoritmi, joka perustuu lyhyisiin vektoriongelmiin Euclidean verkoissa. New Hope otettiin käyttöön ja käytettiin kokeellisesti Google Chrome -selaimessa vuonna 2016.

Edelliseen osaan liittymättä ehdotettiin, että avainten vaihdon turvallisuuden varmistamiseksi matemaattisten ja laskennallisten takuiden sijasta käytettäisiin fysiikan ominaisuuksia. Tarkemmin sanottuna kietoutumattomien hiukkasten virtauksen tilastollisten ominaisuuksien havainnointi , joka liittyy kloonaamattomaan lauseeseen, mahdollistaa kuuntelevan vastustajan havaitsemisen ja "heittämisen" osan näin paljastetuista biteistä korjaamalla melu (joka korjaa myös mittauksiin liittyvät virheet). Tämä sovitteluvaihe johtaa bittisarjaan molemmille osapuolille, jotka haluavat vaihtaa avaimen. Lisävahvistusvaihe on tarpeen avaimen johtamiseksi yhteisestä sekvenssistä.

Useat näistä protokollista on toteutettu ja validoitu kokeellisesti useita satoja kilometrejä pitkin.

Kvanttiavainvaihto aiheuttaa kuitenkin useita teknisiä ja operatiivisia haasteita, jotka tällä hetkellä rajoittavat sen käyttöönottoa: erityisesti osallistujien välille on luotava erityinen viestintäkanava. Esimerkiksi, että BB84 , B92 tai SARG04 protokollia , on välttämätöntä pystyä varmistamaan kuljetuksen matalan energian fotonit säilyttäen niiden polarisaatio huolimatta ilmiöitä decoherence koko kanavan pituudelta.

Huomautuksia ja viitteitä

Huomautuksia

  1. Koska tämä on yksittäinen avain, puhumme avainvaihdosta, yksikkönä, eikä avaimenvaihdosta.

Viitteet

  1. (in) Salauspioneerit saavat ACM AM Turing -palkinnon  " osoitteessa www.acm.org (käytetty 20. syyskuuta 2018 )
  2. Katso http://www.merkle.com/1974/ ja http://www.merkle.com/1974/Puzzles1975.12.07.pdf .
  3. (sisään) RC Merkle, "Suojattu viestintä turvattomilla kanavilla", ACM: n viestintä 21 (4), s. 294--299 (huhtikuu 1978).
  4. (in) Boaz Barak ja Mohammad Mahmoody-Ghidary , Merklen palapelit ovat Optimal - ö (n ²) -query Hyökkäys mille tahansa Key Exchange satunnaisesta Oracle, Ennakot Kryptologia - CRYPTO 2009 , Springer, Berliini, Heidelberg, ai.  "Luentotietoja tietojenkäsittelytieteestä",2009( ISBN  9783642033551 ja 9783642033568 , DOI  10.1007 / 978-3-642-03356-8_22 , luettu verkossa ) , s.  374–390
  5. (in) Steven M. Bellovin ja Michael Merritt , "  Salatut Key Exchange: salasanaan perustuvaa yhteyskäytäntöä turvallista contre sanastohyökkäyksiä  " , Proceedings 1992 IEEE Computer Society Symposium on tutkimus Turvallisuus ja yksityisyys ,Toukokuu 1992, s.  72–84 ( DOI  10.1109 / risp.1992.213269 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  6. (sisään) Steven M. Bellovin ja Michael Merritt , "  Lisätty salattu avainten vaihto: salasanapohjaiset suojatun protokollan vastakirjastohyökkäykset ja salasanatiedostot vaarantuneet  " , 1. ACM-konferenssin tietokone- ja tietoliikenneturvallisuus (CCS '93) toimet , ACM,1. st joulukuu 1993, s.  244–250 ( ISBN  0897916298 , DOI  10.1145 / 168588.168618 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  7. (in) Mihir Bellare David Pointcheval ja Phillip Rogaway , "  Vahvistetut Key Exchange Secure contre sanakirja hyökkäykset  " , Advances in Kryptologia - Eurocrypt 2000 , Springer, Berliini, Heidelberg, lukea Notes in Computer Science,14. toukokuuta 2000, s.  139–155 ( ISBN  3540455396 , DOI  10.1007 / 3-540-45539-6_11 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  8. (in) Victor Boyko , Philip MacKenzie ja Sarvar Patel , "  todistettavasti Secure Password-Vahvistetut Key Exchange käyttäminen Diffie-Hellman  " , Advances in Kryptologia - Eurocrypt 2000 , Springer, Berliini, Heidelberg, lukea Notes in Computer Science,14. toukokuuta 2000, s.  156–171 ( ISBN  3540455396 , DOI  10.1007 / 3-540-45539-6_12 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  9. (sisään) Oded Goldreich ja Yehuda Lindell , "  Session-Key Generation Using Only Human Passwords  " , Journal of Cryptology , voi.  19, n °  3,1. st heinäkuu 2006, s.  241–340 ( ISSN  0933-2790 ja 1432-1378 , DOI  10.1007 / s00145-006-0233-z , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  10. (in) Jonathan Katz , Rafail Ostrovskii ja Moti Yung , "  Efficient Password-Vahvistetut Key Exchange Ihmisperäisiä-Ikimuistoinen Salasanat  " , Advances in Kryptologia - Eurocrypt 2001 , Springer, Berliini, Heidelberg, lukea Notes in Computer Science,6. toukokuuta 2001, s.  475–494 ( ISBN  3540449876 , DOI  10.1007 / 3-540-44987-6_29 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  11. (vuonna) Antoine Joux , "  The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems  " , Algoritminen lukuteoria , Springer, Berliini, Heidelberg, lue muistiinpanoja tietojenkäsittelytieteestä,7. heinäkuuta 2002, s.  20–32 ( ISBN  3540454551 , DOI  10.1007 / 3-540-45455-1_3 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  12. (in) Dan Bonehia ja Alice Silverberg "sovellukset Multilineaarinen lomakkeet Cryptography" Contemporary Mathematics Vol. 324, American Mathematical Society, s. 71-90, 2003
  13. (in) Sanjam Garg , Craig Gentry Shai Halevi , "  Candidate Multilineaarinen Maps Ideal Lattice  " , Advances in Kryptologia - Eurocrypt 2013 , Springer, Berliini, Heidelberg, lukea Notes in Computer Science,26. toukokuuta 2013, s.  1–17 ( ISBN  9783642383472 , DOI  10.1007 / 978-3-642-38348-9_1 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  14. (en) Jean-Sébastien Coron , Tancred Lepoint ja Mehdi Tibouchi , Advances in Cryptology - CRYPTO 2013 , Springer, Berliini, Heidelberg, al.  "Luentotietoja tietojenkäsittelytieteestä",2013( ISBN  9783642400407 ja 9783642400414 , DOI  10.1007 / 978-3-642-40041-4_26 , luettu verkossa ) , s.  476 - 493
  15. (en) Jung Hee Cheon , Kyoohyung Han , Changmin Lee ja Hansol Ryu , "  Cryptanalysis of the over-the Multilinear Map Integers  " , Advances in Cryptology - EUROCRYPT 2015 , Springer, Berliini, Heidelberg, lue tietotekniikan muistiinpanoja,26. huhtikuuta 2015, s.  3–12 ( ISBN  9783662467992 , DOI  10.1007 / 978-3-662-46800-5_1 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  16. (en) Jung Hee Cheon , Pierre-Alain Fouque , Changmin Lee ja Brice Minaud , "  Cryptanalysis of the New CLT Multilinear Map over the Integers  " , Advances in Cryptology - EUROCRYPT 2016 , Springer, Berlin, Heidelberg, lue muistiinpanoja tietojenkäsittelytieteestä ,8. toukokuuta 2016, s.  509-536 ( ISBN  9783662498897 , DOI  10.1007 / 978-3-662-49890-3_20 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  17. (in) Eric Miles , Amit Sahai ja Mark Zhandry , "  Annihilation iskuihin Multilineaarinen Kartat: kryptoanalyysin indistinguishability Salaustaktiikaksi yli GGH13  " , Advances in Kryptologia - CRYPTO 2016 , Springer, Berliini, Heidelberg, lukea Notes in Computer Science,14. elokuuta 2016, s.  629–658 ( ISBN  9783662530078 , DOI  10.1007 / 978-3-662-53008-5_22 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  18. (en) Jean-Sébastien Coron , Moon Sung Lee , Tancred Lepoint ja Mehdi Tibouchi , "  Cryptanalysis of GGH15 Multilinear Maps  " , Advances in Cryptology - CRYPTO 2016 , Springer, Berliini, Heidelberg, lue tietotekniikan huomautuksia,14. elokuuta 2016, s.  607-628 ( ISBN  9783662530078 , DOI  10.1007 / 978-3-662-53008-5_21 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  19. (in) David Jao ja Luca De Feo , "  Kohti kvanttiresistenttejä kryptosysteemejä supersingulaaristen isogeenien elliptisestä käyrästä  " , post-kvanttiteknologia , Springer, Berliini, Heidelberg, lue muistiinpanoja tietojenkäsittelytieteestä,29. marraskuuta 2011, s.  19–34 ( ISBN  9783642254048 , DOI  10.1007 / 978-3-642-25405-5_2 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  20. (in) Erdem Alkim Leo Ducas, Pöppelmann Thomas ja Peter Schwabe, "Post-Quantum Key Exchange - A New Hope", USENIX Security Symposium , 2016, s.   327-343
  21. (sisään) Matt Braithwaite, "  Experimenting with Post-Quantum Cryptography  " osoitteessa security.googleblog.com ,7. heinäkuuta 2016
  22. (sisään) Boris Korzh , Charles Ci Wen Lim , Raphael Houlmann ja Nicolas Gisin , "  todistettavasti turvallinen kvanttiavainjako ja käytännöllinen yli 307 km valokuitua  " , Nature Photonics , Voi.  9, n o  3,maaliskuu 2015, s.  163–168 ( ISSN  1749-4893 , DOI  10.1038 / nphoton.2014.327 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  23. (in) Charles H. Bennett , "  Kvanttisalaus jollakin kaksi epäortogonaaliset valtiota  " , Physical Review Letters , vol.  68, n o  21,25. toukokuuta 1992, s.  3121–3124 ( DOI  10.1103 / PhysRevLett.68.3121 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
  24. (sisään) Valerio Scarani , Antonio Acín Grégoire Ribordy ja Nicolas Gisin , "  Quantum Cryptography Protocols Robust contre Photon Number Splitting Attack for Weak Laser Pulse Implementations  " , Physical Review Letters , voi.  92, n o  5,6. helmikuuta 2004, s.  057901 ( DOI  10.1103 / PhysRevLett.92.057901 , luettu verkossa , käytetty 17. maaliskuuta 2018 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">