Protokoly MTI

Protokoly MTI jsou rodinou klíčových distribučních protokolů vyvinutých T. Matsumotem , Y. Takashitou a H. Imai a pojmenovaných po jejich autorech. Protokoly MTI jsou rozděleny do tří tříd protokolů: MTI/A, MTI/B, MTI/C. [jeden]

Protokol distribuce klíčů řeší problém distribuce tajných šifrovacích klíčů mezi komunikujícími stranami. Sada takových protokolů je rozdělena do následujících tří typů: [2]

  1. výměnné protokoly pro již vygenerované klíče;
  2. společné protokoly generování klíčů (distribuce veřejného klíče);
  3. předklíčové distribuční protokoly.

Protokoly MTI jsou klasifikovány jako protokoly distribuce veřejného klíče.

Protokoly distribuce veřejného klíče jsou založeny na výměně zpráv mezi uživateli, v důsledku čehož každý uživatel vypočítá tajný klíč relace. V tomto případě je výpočet klíče relace před výměnou zpráv nemožný. Proto se tyto protokoly také nazývají [3] protokoly dynamické distribuce klíčů, na rozdíl od statických protokolů, ve kterých jsou klíče známy ještě před samotnou komunikační relací. Navíc vytváření klíčů relace ve veřejných distribučních protokolech vyžaduje, aby uživatelé znali pouze veřejné klíče, tzn. umožňuje dvojici systémových uživatelů vyvinout sdílený tajný klíč bez výměny soukromých klíčů. To vedlo k tomu, že tyto protokoly ihned po svém objevení v roce 1976 upoutaly pozornost mezinárodního společenství.


Historie

Myšlenku vytvoření otevřených distribučních protokolů poprvé navrhli Whitfield Diffie a Martin Hellman na National Computer Conference v červnu 1976. A v listopadu  1976 ve své práci „ New Directions in Cryptography “ navrhli první protokol pro distribuci veřejného klíče [4] , pojmenovaný podle jmen autorů (protokol Diffie-Hellman).

První svého druhu, protokol Diffie-Hellman, byl zranitelný vůči určitým typům útoků, zejména útokům typu man-in-the-middle [2] . K vyřešení tohoto problému bylo nutné poskytnout uživatelům autentizační mechanismus. Takovým mechanismem , který umožnil řešit problém komunikace otevřeným kanálem, se stal asymetrický šifrovací algoritmus RSA [5] publikovaný v srpnu 1977 v rubrice „Mathematical Games“ časopisu Scientific American .

V roce 1984 navrhl Taher El-Gamal vylepšený protokol Diffie-Hellman s možností jednosměrné autentizace, kdy pouze jedna z komunikujících stran může ověřit pravost té druhé [6] . Na rozdíl od RSA nebyl protokol ElGamal patentován, a proto se stal levnější alternativou, protože nebylo třeba platit žádné licenční poplatky. Předpokládá se, že algoritmus je pokryt patentem Diffie-Hellman.

V únoru 1986 představili T. Matsumoto, I. Takashima a H. Imai řešení problému vzájemné autentizace bez použití RSA [7] . V jejich protokolech MTI obsahuje sdílený tajný výraz veřejný i soukromý klíč legálních uživatelů. Toto řešení umožňuje provádět autentizaci současně s výpočtem sdíleného tajného klíče (nelegální uživatel nemůže vypočítat hodnotu tajného klíče).

Protokoly MTI jsou v současnosti součástí normy ISO/IEC 11770-3 [1] .

Popis protokolů MTI [1]

Zvažte proces výměny informací mezi stranami A a B. Níže jsou uvedeny zápisy, které budou použity k popisu činnosti protokolů MTI.

velké prvočíslo (alespoň 1024 bitů).
prvočíslo (řádově 160 bitů), které je dělitelem .
podskupina skupiny (obvykle řádu , ale někdy se shoduje s )
generující prvek podskupiny
, soukromé klíče stran A a B
, veřejné klíče stran A a B  : , .
, náhodná celá čísla, obvykle stejné velikosti jako pořadí skupiny , zvolená stranami A a B , v tomto pořadí
, zprávy odeslané z A do B a z B do A .
tajný klíč relace vypočítaný stranami A a B
největší společný dělitel čísel a

Veškeré budoucí výpočty jsou prováděny ve skupině .

MTI/A(0) [8]

Pracovní algoritmus

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Strana vybere náhodné číslo a odešle zprávu
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

MTI/B(0)

Pracovní algoritmus

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Strana vybere náhodné číslo a odešle zprávu
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

MTI/C(0) [8]

Pracovní algoritmus

  1. Strana vybere náhodné číslo a pošle B zprávu
  2. Strana vybere náhodné číslo a odešle zprávu A
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

MTI/A(k)

Pracovní algoritmus

  1. Strana vybere náhodné číslo a pošle B zprávu
  2. Strana vybere náhodné číslo a odešle zprávu A
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

MTI/B(k)

Pracovní algoritmus

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Strana vybere náhodné číslo a odešle zprávu
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

MTI/C(k)

Pracovní algoritmus

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Strana vybere náhodné číslo a odešle zprávu
  3. Strana vypočítá klíč relace:
  4. Strana vypočítá klíč relace:

Provedené výpočty

Analýza protokolů MTI [3]

Tabulka protokolu MTI
Protokol
MTI/A(0)
MTI/B(0)
MTI/C(0)
MTI/A(k)
MTI/B(k)
MTI/C(k)
  1. Protokoly MTI/A a MTI/B vyžadují, aby každý uživatel vypočítal tři exponenty, zatímco protokoly MTI/C vyžadují výpočet pouze dvou exponentů. Protokol MTI/C(1) má také další výhodu v tom, že nemusí počítat převrácené hodnoty a . Na druhou stranu se tyto hodnoty během celé komunikační relace nemění a lze je tedy vypočítat předem.
  2. Všechny strany v protokolech MTI provádějí podobné operace a fungování protokolů nezávisí na pořadí, ve kterém jsou zprávy odesílány z jedné strany na druhou.
  3. Protokoly MTI/B a MTI/C vyžadují znalost veřejných klíčů ostatních stran, což může vyžadovat další zasílání zpráv (pokud se informace o veřejném klíči nevejdou do zpráv odesílaných přes síť). Protokoly MTI/A nevyžadují znalost veřejných klíčů, což zabraňuje dalším přenosům a časovým prodlevám.
  4. Všechny tři třídy protokolů poskytují vzájemné implicitní ověřování pomocí klíče, ale neposkytují potvrzení klíče nebo ověřování entity.
Porovnání klíčových distribučních protokolů
Protokol Autentizace klíče Ověření zdroje Potvrzení klíče Počet zpráv
protokol Diffie-Hellman chybějící chybějící chybějící 2
Protokol ElGamal jednostranný chybějící chybějící jeden
MTI/A vzájemné implicitní chybějící chybějící 2
MTI/B,C vzájemné implicitní chybějící chybějící 2
STS vzájemné explicitní vzájemné chybějící 3

Útoky na protokoly MTI

Protokoly MTI odolávají pasivním útokům, ale jsou zranitelné vůči aktivním útokům [3] . Níže jsou uvedeny příklady aktivních útoků na protokoly MTI.

Útok malé podskupiny na protokoly MTI/C [1]

Útok malé podskupiny se použije na třídu protokolu MTI/C, pokud skupina odpovídá skupině , jak se očekává v původním protokolu. Předpokládá se, že kryptoanalytik zná rozklad čísla na prvočinitele. Dovolit být nejmenší prvočinitel v expanzi čísla . Označme . Útok spočívá ve zvýšení všech zpráv na moc , která převede přenášené prvky do malé podskupiny skupiny .

Opravdu, a výměna zpráv formuláře . Povýšení prvku na moc dává generující prvek podskupiny řádu . Navíc je toto pořadí rovno buď tehdy , respektive, nebo když obsahuje číslo v rozkladu na prvočinitele , tzn. . Ve všech ostatních případech bude pořadí podskupiny rovno .

Proces napadení protokolu MTI/C(0) je popsán níže. Kryptanalytik je mezi stranami a ( man-in-the-middle ).

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Kryptanalytik zachytí zprávu od a odešle zprávu
  3. Strana vybere náhodné číslo a odešle zprávu
  4. Kryptanalytik zachytí zprávu od a odešle zprávu
  5. Strana vypočítá klíč relace:
  6. Strana vypočítá klíč relace:

Přijatý tajný klíč relace , stejně jako přijaté zprávy, je prvkem malé podskupiny skupiny . Proto může kryptoanalytik najít klíč vyčerpávajícím hledáním, přičemž kontroluje prvky podskupiny jako klíče v komunikaci mezi a . V tomto případě platí, že čím menší je multiplikátor , tím rychleji útok přejde.

Útoku na podskupinu lze zabránit výběrem podskupiny skupiny prvořadého řádu . Protože zatímco délka je asi 160 bitů, pak se vyčerpávající hledání ukazuje jako příliš obtížný úkol pro kryptoanalytika . Je také nutné zkontrolovat, že prvky přijaté ve zprávách jsou ve skupině a nejsou rovny jedné.

Útok s neznámým sdíleným klíčem [1] [3] [9]

Neznámý útok na veřejný klíč vyžaduje, aby kryptoanalytik získal dlouhodobý certifikát veřejného klíče , který je propojen s veřejným klíčem strany pomocí vzorce . To znamená, že nezná tajný klíč odpovídající veřejnému klíči .

Útok s neznámým sdíleným klíčem se provádí provedením následující sekvence akcí.

  1. Strana vybere náhodné číslo a odešle zprávu
  2. Kryptanalytik přenese zprávu od do do beze změny.
  3. Strana vybere náhodné číslo a odešle zprávu
  4. Kryptanalytik obdrží zprávu od a odešle zprávu
  5. Strana vypočítá klíč relace:
  6. Strana vypočítá klíč relace:

Tajné klíče vypočítané stranami a jsou stejné a rovné . Zároveň se domnívá , že jej sdílí s , zatímco se domnívá , že sdílí klíč s .

Ačkoli není schopna vypočítat tajný klíč relace bez dalších informací, strana přesto vede k chybnému názoru.

Aby se tomuto útoku zabránilo, je nutné vyžadovat od certifikačních autorit, aby ověřily, že strany požadující certifikát pro nějaký veřejný klíč znají odpovídající soukromý klíč .

Poznámky

  1. 1 2 3 4 5 Boyd, Mathuria, 2003 , str. 147-155.
  2. 1 2 Alferov, Zubov, Kuzmin et al., 2002 , str. 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. Přehled protokolů klíčových dohod . - S. 9-10 .
  9. Cheremushkin A.V. Kryptografické protokoly: základní vlastnosti a zranitelnosti  // Applied Discrete Mathematics: Appendix. - 2009. - č. 2 . - S. 115-150 . Archivováno z originálu 3. listopadu 2013.

Literatura