KASUMI - KASUMI

KASUMI er en blokkryptering som brukes i UMTS- , GSM- og GPRS- mobilkommunikasjonssystemer . I UMTS brukes KASUMI i henhold til konfidensialitet ( f8 ) og integritetsalgoritmer ( f9 ) med navnene UEA1 og UIA1. I GSM brukes KASUMI i A5 / 3- nøkkelstrømgeneratoren og i GPRS i GEA3- nøkkelstrømgeneratoren.

KASUMI ble designet for 3GPP som skal brukes i UMTS sikkerhetssystem av Security Algorithms Group of Experts (SAGE), en del av det europeiske standardiseringsorganet ETSI . På grunn av tidsplanstrykk i 3GPP-standardisering, i stedet for å utvikle en ny kryptering, ble SAGE enig med 3GPP teknisk spesifikasjonsgruppe (TSG) for systemaspekter av 3G-sikkerhet (SA3) for å basere utviklingen på en eksisterende algoritme som allerede hadde gjennomgått en viss evaluering. De valgte krypteringsalgoritmen MISTY1 utviklet og patentert av Mitsubishi Electric Corporation . Den opprinnelige algoritmen ble litt modifisert for enklere implementering av maskinvare og for å oppfylle andre krav som er satt for 3G mobilkommunikasjonssikkerhet.

KASUMI er oppkalt etter den opprinnelige algoritmen MISTY1 - 霞 み (hiragana か す み , romaji kasumi ) er det japanske ordet for "tåke".

I januar 2010 ga Orr Dunkelman , Nathan Keller og Adi Shamir ut et papir som viste at de kunne bryte Kasumi med et beslektet nøkkelangrep og svært beskjedne beregningsressurser; dette angrepet er ineffektivt mot MISTY1 .

Beskrivelse

KASUMI-algoritmen er spesifisert i en 3GPP teknisk spesifikasjon. KASUMI er en blokkryptering med 128-biters nøkkel og 64-biters inngang og utgang. Kjernen i KASUMI er et åtte-runde Feistel-nettverk . De runde funksjonene i det viktigste Feistel-nettverket er irreversible Feistel-lignende nettverkstransformasjoner. I hver runde bruker rundefunksjonen en rund nøkkel som består av åtte 16-biters undernøkler hentet fra den opprinnelige 128-bits nøkkelen ved hjelp av en fast nøkkelplan.

Nøkkelplan

128-bit nøkkel K er inndelt i åtte 16-bit undernøkler K _i :

${\ displaystyle K = K_ {1} \ | K_ {2} \ | K_ {3} \ | K_ {4} \ | K_ {5} \ | K_ {6} \ | K_ {7} \ | K_ {8 } \,}$

I tillegg brukes en modifisert nøkkel K ' , tilsvarende delt inn i 16-biters undernøkler K' _i . Den modifiserte nøkkelen er hentet fra den opprinnelige nøkkelen av XORing med 0x123456789ABCDEFFEDCBA9876543210 (valgt som "ingenting i ermet" -nummeret ).

Runde taster er enten avledet fra undernøklene ved bitvis rotasjon mot venstre med et gitt beløp og fra de modifiserte undernøklene (uendret).

De runde tastene er som følger:

${\ displaystyle {\ begin {array} {lcl} KL_ {i, 1} & = & {\ rm {ROL}} (K_ {i}, 1) \\ KL_ {i, 2} & = & K '_ { i + 2} \\ KO_ {i, 1} & = & {\ rm {ROL}} (K_ {i + 1}, 5) \\ KO_ {i, 2} & = & {\ rm {ROL}} (K_ {i + 5}, 8) \\ KO_ {i, 3} & = & {\ rm {ROL}} (K_ {i + 6}, 13) \\ KI_ {i, 1} & = & K ' _ {i + 4} \\ KI_ {i, 2} & = & K '_ {i + 3} \\ KI_ {i, 3} & = & K' _ {i + 7} \ end {array}}}$

Subnøkkelindeks-tillegg er sykliske slik at hvis i + j er større enn 8, må man trekke 8 fra resultatet for å få den faktiske undernøkkelindeksen.

Algoritmen

KASUMI-algoritmen behandler 64-bitersordet i to 32-biters halvdeler, venstre ( ) og høyre ( ). Inngangsordet er sammenkobling av venstre og høyre halvdel av første runde: ${\ displaystyle L_ {i}}$${\ displaystyle R_ {i}}$

${\ displaystyle {\ rm {input}} = R_ {0} \ | L_ {0} \,}$ .

I hver runde XOR'es den høyre halvdelen med utgangen fra den runde funksjonen, hvoretter halvdelene byttes ut:

${\ displaystyle {\ begin {array} {rcl} L_ {i} & = & F_ {i} (KL_ {i}, KO_ {i}, KI_ {i}, L_ {i-1}) \ oplus R_ {i -1} \\ R_ {i} & = & L_ {i-1} \ end {array}}}$

hvor KL _jeg , KO _jeg , KI _jeg er runde taster for jeg ^th runde.

Rundfunksjonene for jevne og odde runder er litt forskjellige. I begge tilfeller er den runde funksjonen en sammensetning av to funksjoner FL _i og FO _i . For en merkelig runde

${\ displaystyle F_ {i} (K_ {i}, L_ {i-1}) = FO (KO_ {i}, KI_ {i}, FL (KL_ {i}, L_ {i-1})) \, }$

og for en jevn runde

${\ displaystyle F_ {i} (K_ {i}, L_ {i-1}) = FL (KL_ {i}, FO (KO_ {i}, KI_ {i}, L_ {i-1})) \, }$ .

Utgangen er sammenkoblingen av utgangene fra den siste runden.

${\ displaystyle {\ rm {output}} = R_ {8} \ | L_ {8} \,}$ .

Både FL- og FO- funksjonene deler 32-biters inngangsdata i to 16-biters halvdeler. Den FL -funksjonen er en irreversibel bit manipulering mens FO -funksjonen er en irreversibel tre runde Feistel-lignende nettverk.

Funksjon FL

Den 32-bits inngang x på som delt i to 16-bit halvdeler . Først blir venstre halvdel av inngangen ANDed bitvis med rund tast og rotert til venstre med en bit. Resultatet av det blir XOR'et til høyre halvdel av inngangen for å få den høyre halvdelen av utgangen . ${\ displaystyle FL (KL_ {i}, x)}$${\ displaystyle x = l \ | r}$${\ displaystyle l}$${\ displaystyle KL_ {i, 1}}$${\ displaystyle r}$${\ displaystyle r '}$

${\ displaystyle r '= {\ rm {ROL}} (l \ wedge KL_ {i, 1}, 1) \ oplus r}$

Deretter ORDERes høyre halvdel av utgangen bitvis med den runde tasten og roteres til venstre med en bit. Resultatet av det blir XOR'et til venstre halvdel av inngangen for å få venstre halvdel av utgangen . ${\ displaystyle r '}$${\ displaystyle KL_ {i, 2}}$${\ displaystyle l}$${\ displaystyle l '}$

${\ displaystyle l '= {\ rm {ROL}} (r' \ vee KL_ {i, 2}, 1) \ oplus l}$

Output av funksjonen er sammenkobling av venstre og høyre halvdel . ${\ displaystyle x '= l' \ | r '}$

Funksjon FO

32-biters inngang x av er delt inn i to 16-biters halvdeler , og går gjennom tre runder av et Feistel-nettverk. ${\ displaystyle FO (KO_ {i}, KI_ {i}, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$

I hver av de tre rundene (indeksert av j som tar verdiene 1, 2 og 3) blir venstre halvdel modifisert for å få den nye høyre halvdelen og høyre halvdel blir til venstre halvdel av neste runde.

${\ displaystyle {\ begin {array} {lcl} r_ {j} & = & FI (KI_ {i, j}, l_ {j-1} \ oplus KO_ {i, j}) \ oplus r_ {j-1} \\ l_ {j} & = & r_ {j-1} \ end {array}}}$

Utgangen av funksjonen er . ${\ displaystyle x '= l_ {3} \ | r_ {3}}$

Funksjon FI

Funksjonen FI er et uregelmessig Feistel-lignende nettverk.

16-biters inngangen til funksjonen er delt inn i to halvdeler som er 9 bits brede og 7 bits brede. ${\ displaystyle x}$${\ displaystyle FI (Ki, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$${\ displaystyle l_ {0}}$${\ displaystyle r_ {0}}$

Bitene i den venstre halvdel blir først blandes med 9-bit substitusjonsboks (S-boks) S9 og resultatet er XOR'ed med null-utvidet høyre halvdel for å få den nye 9-bits høyre halvdel . ${\ displaystyle l_ {0}}$${\ displaystyle r_ {0}}$${\ displaystyle r_ {1}}$

${\ displaystyle r_ {1} = S9 (l_ {0}) \ oplus (00 \ | r_ {0}) \,}$

Biter av høyre halvdel blandes av 7-biters S-boks S7, og resultatet blir XOR'ed med de syv minst signifikante bitene ( LS7 ) på den nye høyre halvdelen for å få den nye 7-biters venstre halvdel . ${\ displaystyle r_ {0}}$${\ displaystyle r_ {1}}$${\ displaystyle l_ {1}}$

${\ displaystyle l_ {1} = S7 (r_ {0}) \ oplus LS7 (r_ {1}) \,}$

Den mellomliggende ord er XORed med rund nøkkel KI for å få av disse er 7 bit bred og er av 9-bits bred. ${\ displaystyle x_ {1} = l_ {1} \ | r_ {1}}$${\ displaystyle x_ {2} = l_ {2} \ | r_ {2}}$${\ displaystyle l_ {2}}$${\ displaystyle r_ {2}}$

${\ displaystyle x_ {2} = KI \ oplus x_ {1}}$

Biter i høyre halvdel blandes deretter av 9-bits S-boks S9, og resultatet blir XOR'ed med den utvidede venstre halvdelen for å få den nye 9-biters høyre halvdel av utgangen . ${\ displaystyle r_ {2}}$${\ displaystyle l_ {2}}$${\ displaystyle r_ {3}}$

${\ displaystyle r_ {3} = S9 (r_ {2}) \ oplus (00 \ | l_ {2}) \,}$

Til slutt blir bitene i venstre halvdel blandet av 7-biters S-boks S7, og resultatet blir XOR'ed med de syv minst signifikante bitene ( LS7 ) på høyre halvdel av utgangen for å få den 7-biters venstre halvdelen av produksjon. ${\ displaystyle l_ {2}}$${\ displaystyle r_ {3}}$${\ displaystyle l_ {3}}$

${\ displaystyle l_ {3} = S7 (l_ {2}) \ oplus LS7 (r_ {3}) \,}$

Resultatet er sammenkoblingen av den siste venstre og høyre halvdelen . ${\ displaystyle x '= l_ {3} \ | r_ {3}}$

Erstatningsbokser

De substitusjon boksene (S-bokser) S7 og S9 er definert av begge bitvis OG-XOR uttrykk og oppslagstabeller i beskrivelsen. De bitvise uttrykkene er ment for implementering av maskinvare, men i dag er det vanlig å bruke oppslagstabellene selv i HW-design.

S7 er definert av følgende matrise:

int S7[128] = {
   54, 50, 62, 56, 22, 34, 94, 96, 38,  6, 63, 93,  2, 18,123, 33,
   55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,
   53,  9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,
   20,122, 72, 61, 23,109, 13,100, 77,  1, 16,  7, 82, 10,105, 98,
  117,116, 76, 11, 89,106,  0,125,118, 99, 86, 69, 30, 57,126, 87,
  112, 51, 17,  5, 95, 14, 90, 84, 91,  8, 35,103, 32, 97, 28, 66,
  102, 31, 26, 45, 75,  4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,
   64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59,  3
};

S9 er definert av følgende matrise:

int S9[512] = {
  167,239,161,379,391,334,  9,338, 38,226, 48,358,452,385, 90,397,
  183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,
  175,241,489, 37,206, 17,  0,333, 44,254,378, 58,143,220, 81,400,
   95,  3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,
  165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,
  501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,
  232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,
  344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,
  
  487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,
  475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,
  363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,
  439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,
  465,416,252,287,246,  6, 83,305,420,345,153,502, 65, 61,244,282,
  173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,
  280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,
  132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374,
  
   35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285,
   50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32,
   72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,
  185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190,
    1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,
  336,318,  4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18,
   47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,
  414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,
  
  266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,
  311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,
  485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,
  312,377,  7,468,194,  2,117,295,463,258,224,447,247,187, 80,398,
  284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451,
   97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,
  438,477,387,122,192, 42,381,  5,145,118,180,449,293,323,136,380,
   43, 66, 60,455,341,445,202,432,  8,237, 15,376,436,464, 59,461
};

Kryptanalyse

I 2001 ble et umulig differensialangrep på seks KASUMI-runder presentert av Kühn (2001).

I 2003 demonstrerte Elad Barkan, Eli Biham og Nathan Keller mann-i-midten-angrep mot GSM- protokollen, som unngikk A5 / 3-kryptering og dermed brøt protokollen. Denne tilnærmingen angriper imidlertid ikke A5 / 3-krypteringen. Den fulle versjonen av papiret ble publisert senere i 2006.

I 2005 publiserte israelske forskere Eli Biham , Orr Dunkelman og Nathan Keller et angrep på BASUMI med relatert nøkkel rektangel (boomerang) som kan bryte alle de 8 rundene raskere enn uttømmende søk. Angrepet krever 2 ^54,6 valgte slettetekster, som hver har blitt kryptert under en av fire relaterte nøkler, og har en tidskompleksitet som tilsvarer 2 ^76,1 KASUMI-kryptering. Selv om dette åpenbart ikke er et praktisk angrep, ugyldiggjør det noen bevis for sikkerheten til 3GPP-protokollene som hadde stolt på den antatte styrken til KASUMI.

I 2010 publiserte Dunkelman, Keller og Shamir et nytt angrep som gjør at en motstander kan gjenopprette en full A5 / 3-nøkkel ved angrep med relatert nøkkel . Tids- og romkompleksiteten til angrepet er lav nok til at forfatterne utførte angrepet på to timer på en Intel Core 2 Duo- stasjonær datamaskin, selv med den uoptimerte referansen KASUMI-implementeringen. Forfatterne bemerker at dette angrepet kanskje ikke gjelder for måten A5 / 3 brukes i 3G-systemer; deres hovedformål var å miskreditere 3GPPs forsikringer om at deres endringer i MISTY ikke ville påvirke algoritmens sikkerhet betydelig.

Se også

• A5 / 1 og A5 / 2
• MISTY1
• SNØ

Referanser

Eksterne linker

• Nathan Kellers hjemmeside