MTI protokoller

MTI-protokoller er en familie af nøgledistributionsprotokoller udviklet af T. Matsumoto , Y. Takashita og H. Imai og opkaldt efter deres forfattere. MTI-protokoller er opdelt i tre protokolklasser: MTI/A, MTI/B, MTI/C. [en]

Nøgledistributionsprotokollen løser problemet med at distribuere hemmelige krypteringsnøgler mellem kommunikerende parter. Sættet af sådanne protokoller er opdelt i følgende tre typer: [2]

  1. udveksle protokoller for allerede genererede nøgler;
  2. fælles nøglegenereringsprotokoller (distribution af offentlig nøgle);
  3. præ-nøgle distributionsprotokoller.

MTI-protokollerne er klassificeret som offentlige nøgledistributionsprotokoller.

Protokoller til distribution af offentlige nøgler er baseret på udveksling af meddelelser mellem brugere, som et resultat af hvilke hver bruger beregner en hemmelig sessionsnøgle. I dette tilfælde er det umuligt at beregne sessionsnøglen før udvekslingen af ​​meddelelser. Derfor kaldes disse protokoller også [3] dynamiske nøgledistributionsprotokoller, i modsætning til statiske protokoller, hvor nøglerne er kendt allerede før selve kommunikationssessionen. Derudover kræver oprettelsen af ​​sessionsnøgler i offentlige distributionsprotokoller, at brugerne kun kender de offentlige nøgler, dvs. giver et par systembrugere mulighed for at udvikle en delt hemmelig nøgle uden at udveksle private nøgler. Det er det, der førte til, at sådanne protokoller umiddelbart efter deres fremkomst i 1976 tiltrak det internationale samfunds opmærksomhed.


Historie

Ideen om at bygge åbne nøgledistributionsprotokoller blev først foreslået af Whitfield Diffie og Martin Hellman ved National Computer Conference i juni 1976. Og i november  1976 foreslog de i deres arbejde " New Directions in Cryptography " den første protokol til offentlig nøgledistribution [4] , opkaldt efter navnene på forfatterne (Diffie-Hellman-protokollen).

Den første af sin slags, Diffie-Hellman-protokollen, var sårbar over for visse typer angreb, især man-in-the-middle-angreb [2] . For at løse dette problem var det nødvendigt at give brugerne en godkendelsesmekanisme. Den asymmetriske RSA -krypteringsalgoritme [5] offentliggjort i august 1977 i spalten "Mathematical Games" i magasinet Scientific American blev en sådan mekanisme , som gjorde det muligt at løse kommunikationsproblemet gennem en åben kanal.

I 1984 foreslog Taher El-Gamal en forbedret Diffie-Hellman protokol med mulighed for envejsgodkendelse, når kun en af ​​de kommunikerende parter kan verificere ægtheden af ​​den anden [6] . I modsætning til RSA var ElGamal -protokollen ikke patenteret og blev derfor et billigere alternativ, da der ikke var nogen licensgebyrer at betale. Algoritmen menes at være omfattet af Diffie-Hellman-patentet.

I februar 1986 præsenterede T. Matsumoto, I. Takashima og H. Imai en løsning på problemet med gensidig autentificering uden brug af RSA [7] . I deres MTI-protokoller indeholder det delte hemmelige udtryk både de offentlige og private nøgler fra legitime brugere. Denne løsning gør det muligt at udføre autentificering samtidig med beregningen af ​​den delte hemmelige nøgle (en ulovlig bruger kan ikke beregne værdien af ​​den hemmelige nøgle).

MTI-protokoller er i øjeblikket inkluderet i ISO/IEC 11770-3 [1] -standarden .

Beskrivelse af MTI-protokoller [1]

Overvej processen med informationsudveksling mellem part A og B. Nedenfor er de notationer, der vil blive brugt til at beskrive driften af ​​MTI-protokollerne.

stort primtal (mindst 1024 bit).
et primtal (i størrelsesordenen 160 bit), der er en divisor af .
undergruppe af en gruppe (normalt af orden , men falder nogle gange sammen med )
genererende element i en undergruppe
, private nøgler fra part A og B
, offentlige nøgler for part A og B  : , .
, tilfældige heltal, sædvanligvis af samme størrelse som rækkefølgen af ​​gruppen , valgt af henholdsvis parterne A og B .
, beskeder sendt fra henholdsvis A til B og fra B til A .
hemmelig sessionsnøgle beregnet af part A og B
den største fælles divisor af tal og

Alle beregninger i fremtiden udføres i gruppen .

MTI/A(0) [8]

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender en besked
  2. Part vælger et tilfældigt tal og sender en besked
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

MTI/B(0)

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender en besked
  2. Part vælger et tilfældigt tal og sender en besked
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

MTI/C(0) [8]

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender B en besked
  2. Part vælger et tilfældigt tal og sender besked A
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

MTI/A(k)

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender B en besked
  2. Part vælger et tilfældigt tal og sender besked A
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

MTI/B(k)

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender en besked
  2. Part vælger et tilfældigt tal og sender en besked
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

MTI/C(k)

Arbejdsalgoritme

  1. Part vælger et tilfældigt tal og sender en besked
  2. Part vælger et tilfældigt tal og sender en besked
  3. Parten beregner sessionsnøglen:
  4. Parten beregner sessionsnøglen:

Udførte beregninger

Analyse af MTI-protokoller [3]

MTI protokol tabel
Protokol
MTI/A(0)
MTI/B(0)
MTI/C(0)
MTI/A(k)
MTI/B(k)
MTI/C(k)
  1. MTI/A- og MTI/B-protokollerne kræver, at hver bruger beregner tre eksponenter, mens MTI/C-protokollerne kun kræver to eksponenter, der skal beregnes. MTI/C(1)-protokollen har også den ekstra fordel, at den ikke skal beregne inverserne af og . På den anden side ændres disse værdier ikke under hele kommunikationssessionen og kan derfor beregnes på forhånd.
  2. Alle parter i MTI-protokollerne udfører lignende operationer, og driften af ​​protokollerne afhænger ikke af rækkefølgen, hvori beskeder sendes fra den ene side til den anden.
  3. MTI/B- og MTI/C-protokollerne kræver viden om de andre parters offentlige nøgler, hvilket kan kræve yderligere meddelelser (hvis den offentlige nøgleinformation ikke passer i meddelelser sendt over netværket). MTI/A-protokoller kræver ikke kendskab til offentlige nøgler, hvilket undgår yderligere transmissioner og tidsforsinkelser.
  4. Alle tre protokolklasser giver gensidig implicit nøglegodkendelse, men giver ikke nøglebekræftelse eller enhedsgodkendelse.
Sammenligning af nøgledistributionsprotokoller
Protokol Nøglegodkendelse Kildegodkendelse Nøglebekræftelse Antal beskeder
Diffie-Hellman protokol mangler mangler mangler 2
ElGamal-protokollen ensidigt mangler mangler en
MTI/A gensidig implicit mangler mangler 2
MTI/B,C gensidig implicit mangler mangler 2
STS gensidig eksplicit gensidig mangler 3

Angreb på MTI-protokoller

MTI-protokoller modstår passive angreb, men er sårbare over for aktive angreb [3] . Nedenfor er eksempler på aktive angreb på MTI-protokoller.

Lille undergruppeangreb på MTI/C-protokoller [1]

Et lille undergruppeangreb anvendes på MTI/C-protokolklassen, hvis gruppen matcher gruppen , som forventet i den originale protokol. Det antages, at kryptoanalytikeren kender faktoriseringen af ​​et tal til primfaktorer. Lad være den mindste primfaktor i udvidelsen af ​​tallet . Lad os betegne . Angrebet består i at hæve alle beskeder til en magt , som oversætter de transmitterede elementer til en lille undergruppe af gruppen .

Faktisk, og udveksle beskeder i formen . At hæve et element til en potens giver et genererende element af en undergruppe af orden . Desuden er denne rækkefølge ens , enten når og, henholdsvis, eller når den indeholder tallet i sin nedbrydning i primfaktorer , dvs. . I alle andre tilfælde vil rækkefølgen af ​​undergruppen være lig med .

Processen med at angribe MTI/C(0)-protokollen er beskrevet nedenfor. Kryptanalytikeren er mellem parterne og ( man-in-the-midten ).

  1. Part vælger et tilfældigt tal og sender en besked
  2. Kryptanalytikeren opsnapper beskeden fra og sender beskeden
  3. Part vælger et tilfældigt tal og sender en besked
  4. Kryptanalytikeren opsnapper beskeden fra og sender beskeden
  5. Parten beregner sessionsnøglen:
  6. Parten beregner sessionsnøglen:

Den modtagne hemmelige sessionsnøgle er ligesom de modtagne beskeder et element i gruppens lille undergruppe . Derfor kan kryptanalytikeren finde nøglen ved udtømmende søgning, kontrollere elementerne i undergruppen som nøgler i kommunikationen mellem og . I dette tilfælde, jo mindre multiplikatoren er, jo hurtigere går angrebet.

Et angreb på en undergruppe kan forhindres ved at vælge en undergruppe af en gruppe af prime orden . Fordi mens længden er omkring 160 bit, så viser en udtømmende søgning sig at være en for svær opgave for en kryptoanalytiker . Det er også nødvendigt at kontrollere, at de elementer, der modtages i beskeder, er i en gruppe og ikke er lig med én.

Angreb med ukendt delt nøgle [1] [3] [9]

Et ukendt offentlig nøgleangreb kræver, at kryptoanalytikeren opnår et langsigtet offentlig nøglecertifikat , der er knyttet til partens offentlige nøgle med en formel . Det betyder, at den ikke kender den hemmelige nøgle, der svarer til den offentlige nøgle .

Et angreb med en ukendt delt nøgle udføres ved at udføre følgende rækkefølge af handlinger.

  1. Part vælger et tilfældigt tal og sender en besked
  2. Kryptanalytikeren sender beskeden fra til til uændret.
  3. Part vælger et tilfældigt tal og sender en besked
  4. Kryptanalytikeren modtager en besked fra og sender en besked
  5. Parten beregner sessionsnøglen:
  6. Parten beregner sessionsnøglen:

De hemmelige nøgler beregnet af parterne og er de samme og lig med . Samtidig mener den , at den deler den med , mens den mener, at den deler nøglen med .

Selvom den ikke er i stand til at beregne den hemmelige sessionsnøgle uden yderligere information, fører parten alligevel til en fejlagtig mening.

For at undgå dette angreb er det nødvendigt at kræve, at certifikatmyndighederne bekræfter, at parter, der anmoder om et certifikat for en eller anden offentlig nøgle , kender den tilsvarende private nøgle .

Noter

  1. 1 2 3 4 5 Boyd, Mathuria, 2003 , s. 147-155.
  2. 1 2 Alferov, Zubov, Kuzmin et al., 2002 , s. 378, 387-396.
  3. 1 2 3 4 Menezes, Oorschot, Vanstone, 1996, 515-519 .
  4. Diffie, Hellman, 1976 .
  5. Gardner, 1977 .
  6. Elgamal, 1985 .
  7. Matsumoto, Takashima, Imai, 1986 .
  8. 1 2 Ratna Dutta, Rana Barua. Oversigt over nøgleaftaleprotokoller . - S. 9-10 .
  9. Cheremushkin A.V. Kryptografiske protokoller: grundlæggende egenskaber og sårbarheder  // Applied Discrete Mathematics: Appendix. - 2009. - Nr. 2 . - S. 115-150 . Arkiveret fra originalen den 3. november 2013.

Litteratur