KASUMI - KASUMI

KASUMI ist eine Blockverschlüsselung, die in UMTS- , GSM- und GPRS- Mobilkommunikationssystemen verwendet wird. In UMTS wird KASUMI in den Vertraulichkeits- ( f8 ) und Integritätsalgorithmen ( f9 ) mit den Namen UEA1 bzw. UIA1 verwendet. In GSM wird KASUMI im A5 / 3- Schlüsselstromgenerator und in GPRS im GEA3- Schlüsselstromgenerator verwendet.

KASUMI wurde für 3GPP entwickelt , um von der Expertengruppe für Sicherheitsalgorithmen (SAGE), einem Teil des europäischen Normungsgremiums ETSI , in UMTS-Sicherheitssystemen verwendet zu werden . Aufgrund des Zeitplandrucks bei der 3GPP-Standardisierung stimmte SAGE anstelle der Entwicklung einer neuen Verschlüsselung mit der 3GPP Technical Specification Group (TSG) für Systemaspekte der 3G-Sicherheit (SA3) überein, um die Entwicklung auf einen vorhandenen Algorithmus zu stützen, der bereits einer Evaluierung unterzogen wurde. Sie wählten den von der Mitsubishi Electric Corporation entwickelten und patentierten Verschlüsselungsalgorithmus MISTY1 . Der ursprüngliche Algorithmus wurde leicht modifiziert, um die Hardware-Implementierung zu vereinfachen und andere Anforderungen an die Sicherheit der 3G-Mobilkommunikation zu erfüllen.

KASUMI ist nach dem ursprünglichen Algorithmus benannt. MISTY1 - Japanese み (Hiragana か す rom , Romaji Kasumi ) ist das japanische Wort für "Nebel".

Im Januar 2010 veröffentlichten Orr Dunkelman , Nathan Keller und Adi Shamir ein Papier, aus dem hervorgeht, dass sie Kasumi mit einem Angriff mit verwandten Schlüsseln und sehr bescheidenen Rechenressourcen brechen könnten . Dieser Angriff ist gegen MISTY1 unwirksam .

Beschreibung

Der KASUMI-Algorithmus ist in einer technischen 3GPP-Spezifikation angegeben. KASUMI ist eine Blockverschlüsselung mit 128-Bit-Schlüssel und 64-Bit-Ein- und Ausgabe. Der Kern von KASUMI ist ein acht Runden umfassendes Feistel-Netzwerk . Die runden Funktionen im Haupt-Feistel-Netzwerk sind irreversible Feistel-ähnliche Netzwerk-Transformationen. In jeder Runde verwendet die Rundungsfunktion einen Rundungsschlüssel, der aus acht 16-Bit-Unterschlüsseln besteht, die vom ursprünglichen 128-Bit-Schlüssel unter Verwendung eines festen Schlüsselplans abgeleitet wurden.

Schlüsselzeitplan

Der 128-Bit-Schlüssel K ist in acht 16-Bit-Unterschlüssel K _{i unterteilt} :

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

Zusätzlich wird ein modifizierter Schlüssel K 'verwendet , der ähnlich in 16-Bit-Unterschlüssel K' _{i unterteilt} ist. Der geänderte Schlüssel wird vom Originalschlüssel durch XOR-Verknüpfung mit 0x123456789ABCDEFFEDCBA9876543210 (ausgewählt als "Nichts im Ärmel" -Nummer ) abgeleitet.

Runde Schlüssel werden entweder von den Unterschlüsseln durch bitweise Drehung nach links um einen bestimmten Betrag oder von den modifizierten Unterschlüsseln (unverändert) abgeleitet.

Die runden Tasten lauten wie folgt:

${\ 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}}}$

Das Hinzufügen von Unterschlüsselindizes erfolgt zyklisch. Wenn i + j größer als 8 ist, muss 8 vom Ergebnis subtrahiert werden, um den tatsächlichen Unterschlüsselindex zu erhalten.

Der Algorithmus

Der KASUMI-Algorithmus verarbeitet das 64-Bit-Wort in zwei 32-Bit-Hälften, left ( ) und right ( ). Das eingegebene Wort ist die Verkettung der linken und rechten Hälfte der ersten Runde: ${\ displaystyle L_ {i}}$${\ displaystyle R_ {i}}$

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

In jeder Runde wird die rechte Hälfte mit der Ausgabe der Rundenfunktion XOR'ed, wonach die Hälften vertauscht werden:

${\ 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}}}$

wobei KL _i , KO _i , KI _i runde Schlüssel für die i- ^te Runde sind.

Die Rundenfunktionen für gerade und ungerade Runden unterscheiden sich geringfügig. In jedem Fall ist die Rundungsfunktion eine Zusammensetzung von zwei Funktionen FL _i und FO _i . Für eine ungerade Runde

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

und für eine gleichmäßige Runde

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

Die Ausgabe ist die Verkettung der Ausgaben der letzten Runde.

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

Sowohl FL- als auch FO- Funktionen teilen die 32-Bit-Eingangsdaten in zwei 16-Bit-Hälften. Die FL- Funktion ist eine irreversible Bitmanipulation, während die FO- Funktion ein irreversibles dreirundiges Feistel-ähnliches Netzwerk ist.

Funktion FL

Der 32-Bit-Eingang x von ist in zwei 16-Bit-Hälften unterteilt . Zuerst wird die linke Hälfte des Eingangs mit einem runden Schlüssel bitweise UND-verknüpft und um ein Bit nach links gedreht. Das Ergebnis davon wird auf die rechte Hälfte der Eingabe XOR-verknüpft, um die rechte Hälfte der Ausgabe zu erhalten . ${\ 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}$

Dann wird die rechte Hälfte des Ausgangs mit der runden Taste bitweise ODER-verknüpft und um ein Bit nach links gedreht. Das Ergebnis davon wird auf die linke Hälfte der Eingabe XOR-verknüpft, um die linke Hälfte der Ausgabe zu erhalten . ${\ displaystyle r '}$${\ displaystyle KL_ {i, 2}}$${\ displaystyle l}$${\ displaystyle l '}$

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

Die Ausgabe der Funktion ist die Verkettung der linken und rechten Hälfte . ${\ displaystyle x '= l' \ | r '}$

Funktion FO

Der 32-Bit-Eingang x von ist in zwei 16-Bit-Hälften unterteilt und durch drei Runden eines Feistel-Netzwerks geleitet. ${\ displaystyle FO (KO_ {i}, KI_ {i}, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$

In jeder der drei Runden (indiziert durch j , das die Werte 1, 2 und 3 annimmt) wird die linke Hälfte geändert, um die neue rechte Hälfte zu erhalten, und die rechte Hälfte wird zur linken Hälfte der nächsten Runde gemacht.

${\ 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}}}$

Die Ausgabe der Funktion ist . ${\ displaystyle x '= l_ {3} \ | r_ {3}}$

Funktion FI

Die Funktion FI ist ein unregelmäßiges Feistel-ähnliches Netzwerk.

Der 16-Bit-Eingang der Funktion ist in zwei Hälften unterteilt, von denen 9 Bit breit und 7 Bit breit sind. ${\ displaystyle x}$${\ displaystyle FI (Ki, x)}$${\ displaystyle x = l_ {0} \ | r_ {0}}$${\ displaystyle l_ {0}}$${\ displaystyle r_ {0}}$

Bits in der linken Hälfte werden zuerst durch die 9-Bit- Substitutionsbox (S-Box) S9 gemischt, und das Ergebnis wird mit der nullverlängerten rechten Hälfte XOR-verknüpft , um die neue rechte 9-Bit-Hälfte zu erhalten . ${\ displaystyle l_ {0}}$${\ displaystyle r_ {0}}$${\ displaystyle r_ {1}}$

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

Bits der rechten Hälfte werden von der 7-Bit-S-Box S7 gemischt, und das Ergebnis wird mit den sieben niedrigstwertigen Bits ( LS7 ) der neuen rechten Hälfte XOR-verknüpft , um die neue linke 7-Bit-Hälfte zu erhalten . ${\ displaystyle r_ {0}}$${\ displaystyle r_ {1}}$${\ displaystyle l_ {1}}$

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

Das Zwischenwort wird mit dem Rundenschlüssel KI XORed zu erhalten , von denen 7 Bits breit und ist 9 Bit breit. ${\ 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}}$

Bits in der rechten Hälfte werden dann von der 9-Bit-S-Box S9 gemischt, und das Ergebnis wird mit der nullverlängerten linken Hälfte XOR-verknüpft , um die neue rechte 9-Bit-Hälfte der Ausgabe zu erhalten . ${\ displaystyle r_ {2}}$${\ displaystyle l_ {2}}$${\ displaystyle r_ {3}}$

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

Schließlich werden die Bits von der linken Hälfte werden durch 7-Bit - S-Box gemischt S7 und das Ergebnis ist EXOR'ed mit den sieben am wenigsten signifikanten Bits ( LS7 ) der rechten Hälfte des Ausgangs die 7-Bit - linke Hälfte bekommen von der Ausgabe. ${\ displaystyle l_ {2}}$${\ displaystyle r_ {3}}$${\ displaystyle l_ {3}}$

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

Die Ausgabe ist die Verkettung der letzten linken und rechten Hälfte . ${\ displaystyle x '= l_ {3} \ | r_ {3}}$

Substitutionsboxen

Die Substitutionsfelder (S-Felder) S7 und S9 werden sowohl durch bitweise AND-XOR-Ausdrücke als auch durch Nachschlagetabellen in der Spezifikation definiert. Die bitweisen Ausdrücke sind für die Hardware-Implementierung vorgesehen, aber heutzutage ist es üblich, die Nachschlagetabellen auch im HW-Design zu verwenden.

S7 wird durch das folgende Array definiert:

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 wird durch das folgende Array definiert:

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
};

Kryptoanalyse

Im Jahr 2001 präsentierte Kühn (2001) einen unmöglichen Differentialangriff auf sechs Runden von KASUMI.

Im Jahr 2003 demonstrierten Elad Barkan, Eli Biham und Nathan Keller Man-in-the-Middle-Angriffe gegen das GSM- Protokoll, bei denen die A5 / 3-Verschlüsselung vermieden und damit das Protokoll gebrochen wurde. Dieser Ansatz greift jedoch die A5 / 3-Verschlüsselung nicht an. Die Vollversion ihres Papiers wurde später im Jahr 2006 veröffentlicht.

Im Jahr 2005 veröffentlichten die israelischen Forscher Eli Biham , Orr Dunkelman und Nathan Keller einen verwandten Rechteckangriff (Bumerang) auf KASUMI, der alle 8 Runden schneller als eine umfassende Suche durchbrechen kann. Der Angriff erfordert 2 ^54,6 ausgewählte Klartexte, von denen jeder unter einem von vier verwandten Schlüsseln verschlüsselt wurde und eine Zeitkomplexität aufweist, die 2 ^76,1 KASUMI-Verschlüsselungen entspricht. Dies ist offensichtlich kein praktischer Angriff, macht jedoch einige Beweise für die Sicherheit der 3GPP-Protokolle ungültig, die sich auf die vermutete Stärke von KASUMI gestützt hatten.

Im Jahr 2010 veröffentlichten Dunkelman, Keller und Shamir einen neuen Angriff, mit dem ein Gegner einen vollständigen A5 / 3-Schlüssel durch einen Angriff mit verwandten Schlüsseln wiederherstellen kann . Die zeitliche und räumliche Komplexität des Angriffs ist so gering, dass die Autoren den Angriff in zwei Stunden auf einem Intel Core 2 Duo- Desktop-Computer selbst unter Verwendung der nicht optimierten Referenz-KASUMI-Implementierung durchgeführt haben. Die Autoren stellen fest, dass dieser Angriff möglicherweise nicht auf die Art und Weise anwendbar ist, wie A5 / 3 in 3G-Systemen verwendet wird. Ihr Hauptzweck war es, die Zusicherungen von 3GPP zu diskreditieren, dass ihre Änderungen an MISTY die Sicherheit des Algorithmus nicht wesentlich beeinträchtigen würden.

Siehe auch

• A5 / 1 und A5 / 2
• MISTY1
• SCHNEE

Verweise

Externe Links

• Nathan Kellers Homepage