КАСУМИ

KASUMI - это блочный шифр используется в системах мобильной связи UMTS, GSM и GPRS . В UMTS KASUMI используется в алгоритмах конфиденциальности (f8) и целостности (f9) с именами UEA1 и UIA1 соответственно. В GSM KASUMI используется в генераторе потока ключей A5 / 3 и в GPRS в генераторе потока ключей GEA3 .

KASUMI был разработан для 3GPP для использования в системе безопасности UMTS (SAGE), частью Европейского органа по стандартизации ETSI. Из-за ограничений графика в стандартизации 3GPP, вместо разработки нового шифра, SAGE согласовала с группой технических спецификаций 3GPP (TSG) системные аспекты безопасности 3G (SA3), чтобы основать разработку на существующем алгоритме, который уже прошел некоторую оценку. Они выбрали алгоритм шифрования MISTY1, разработанный и запатентованный Mitsubishi Electric Corporation. Исходный алгоритм был немного изменен для упрощения аппаратной реализации и соответствия другим требованиям безопасности мобильной связи 3G.

КАСУМИ назван в честь исходного алгоритма MISTY1 — 霞み (хирагана か す み, ромадзи касуми ) - это японское слово для «туман».

В январе 2010 года Орр Дункельман, Натан Келлер и Ади Шамир выпустили документ, в котором показано, что они могут взломать Касуми с помощью атаки с использованием связанных ключей и очень скромных вычислительных ресурсов. ; эта атака неэффективна против MISTY1.

• 1 Описание
  • 1.1 Ключевое расписание
  • 1.2 Алгоритм
    • 1.2.1 Функция FL
    • 1.2.2 Функция FO
    • 1.2.3 Функция FI
    • 1.2.4 Блоки подстановки
• 2 Криптоанализ
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Алгоритм KASUMI определен в Техническая спецификация 3GPP. KASUMI - это блочный шифр со 128-битным ключом и 64-битным вводом и выводом. Ядром KASUMI является восьмиэтапная сеть Фейстеля. Функции раунда в основной сети Фейстеля представляют собой необратимые преобразования сети Фейстеля. В каждом раунде функция раунда использует ключ раунда, который состоит из восьми 16-битных подключей, полученных из исходного 128-битного ключа с использованием фиксированного расписания ключей.

Таблица ключей

128-битный ключ K разделен на восемь 16-битных подключей K i:

$K\; =\; K\; 1\; \Vert \; K\; 2\; \Vert \; K\; 3\; \Vert \; K\; 4\; \Vert \; K\; 5\; \Vert \; К\; 6\; \Vert \; К\; 7\; \Vert \; К\; 8\; \{\backslash \; Displaystyle\; K\; =\; K\_\; \{1\}\; \backslash \; |\; K\_\; \{2\}\; \backslash \; |\; K\_\; \{3\}\; \backslash \; |\; K\_\; \{4\}\; \backslash \; |\; K\_\; \{5\}\; \backslash \; |\; K\_\; \{6\}\; \backslash \; |\; K\_\; \{7\}\; \backslash \; |\; K\_\; \{8\}\; \backslash ,\}$

Дополнительно используется модифицированный ключ K ', аналогично разделенный на 16-битные подключа K' i. Модифицированный ключ получается из исходного ключа путем XOR с 0x123456789ABCDEFFEDCBA9876543210 (выбран в качестве «ничего в рукаве» номер ).

Круглые ключи получаются либо из подключаемых ключей побитовым вращением влево на заданное количество, либо из модифицированных подключаемых ключей (без изменений).

Круглые ключи имеют следующий вид:

$KL\; i,\; 1\; =\; ROL\; (K\; i,\; 1)\; KL\; i,\; 2\; =\; K\; i\; +\; 2\; \prime \; KO\; i,\; 1\; =\; ROL\; (K\; i\; +\; 1,\; 5)\; KO\; i,\; 2\; =\; ROL\; (K\; i\; +\; 5,\; 8)\; KO\; i,\; 3\; =\; ROL\; (K\; i\; +\; 6,\; 13)\; KI\; i,\; 1\; =\; K\; i\; +\; 4\; \prime \; KI\; i,\; 2\; =\; K\; i\; +\; 3\; \prime \; KI\; я,\; 3\; знак\; равно\; К\; я\; +\; 7\; \prime \; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{array\}\; \{lcl\}\; KL\_\; \{я,\; 1\}\; =\; \{\backslash \; rm\; \{ROL\}\}\; (K\_\; \{i\},\; 1)\; \backslash \backslash \; KL\_\; \{\; i,\; 2\}\; =\; K\; \text{'}\_\; \{i\; +\; 2\}\; \backslash \backslash \; KO\_\; \{i,\; 1\}\; =\; \{\backslash \; rm\; \{ROL\}\}\; (K\_\; \{i\; +\; 1\},\; 5)\; \backslash \backslash \; KO\_\; \{i,\; 2\}\; =\; \{\backslash \; rm\; \{ROL\}\}\; (K\_\; \{i\; +\; 5\},\; 8)\; \backslash \backslash \; KO\_\; \{i,\; 3\}\; =\; \{\backslash \; rm\; \{ROL\}\}\; (K\_\; \{i\; +\; 6\},\; 13)\; \backslash \backslash \; KI\_\; \{i,\; 1\}\; =\; K\; \text{'}\_\; \{i\; +\; 4\}\; \backslash \backslash \; KI\_\; \{i,\; 2\}\; =\; K\text{'}\; \_\; \{i\; +\; 3\}\; \backslash \backslash \; KI\_\; \{i,\; 3\}\; =\; K\; \text{'}\_\; \{i\; +\; 7\}\; \backslash \; end\; \{array\}\}\}$

Добавление индекса подключа является циклическим, так что если i + j больше 8, нужно вычесть 8 из результата, чтобы получить фактический индекс подключа.

Алгоритм

алгоритм КАСУМИ обрабатывает 64-битное слово в двух 32-битных половинах, слева ($L\; i\; \{\backslash \; displaystyle\; L\_\; \{i\}\}$) и вправо ($R\; i\; \{\backslash \; displaystyle\; R\_\; \{i\}\}$). Входное слово представляет собой объединение левой и правой половин первого раунда:

$input\; =\; R\; 0\; \Vert \; L\; 0\; \{\backslash \; displaystyle\; \{\backslash \; rm\; \{input\}\}\; =\; R\_\; \{0\}\; \backslash \; |\; L\_\; \{0\}\; \backslash ,\}$.

В каждом раунде правая половина подвергается операции XOR с выходом раундовой функции, после чего половины меняются местами:

$L\; i\; =\; F\; i\; (KL\; i,\; KO\; i,\; KI\; i,\; L\; i\; -\; 1)\; \oplus \; р\; я\; -\; 1\; р\; я\; знак\; равно\; L\; я\; -\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{rcl\}\; L\_\; \{i\}\; =\; F\_\; \{i\}\; (KL\_\; \{i\},\; KO\_\; \{i\},\; KI\_\; \{i\},\; L\_\; \{i-1\})\; \backslash \; oplus\; R\_\; \{i-1\}\; \backslash \backslash \; R\_\; \{i\}\; =\; L\_\; \{i-1\}\; \backslash \; end\; \{array\}\}\}$

где KL i, KO i, KI i - ключи раунда для раунда i.

Функции округления для четного и нечетного округления немного отличаются. В каждом случае функция раунда представляет собой композицию двух функций FL i и FO i. Для нечетного раунда

$F\; i\; (K\; i,\; L\; i\; -\; 1)\; =\; FO\; (KO\; i,\; KI\; i,\; FL\; (KL\; i,\; L\; i\; -\; 1))\; \{\backslash \; displaystyle\; F\_\; \{i\}\; (K\_\; \{i\},\; L\_\; \{i-1\})\; =\; FO\; (KO\_\; \{i\},\; KI\_\; \{i\},\; FL\; (KL\_\; \{i\},\; L\_\; \{i-1\}))\; \backslash ,\}$

и для четного раунда

$F\; я\; (К\; я,\; L\; я\; -\; 1)\; =\; FL\; (KL\; я,\; FO\; (КО\; я,\; KI\; я,\; L\; я\; -\; 1))\; \{\backslash \; Displaystyle\; F\_\; \{я\}\; (K\_\; \{я\},\; L\_\; \{я-1\})\; =\; FL\; (KL\_\; \{i\},\; FO\; (KO\_\; \{i\},\; KI\_\; \{i\},\; L\_\; \{i-1\}))\; \backslash ,\}$.

Результатом является конкатенация результатов последнего раунда.

$output\; =\; R\; 8\; \Vert \; L\; 8\; \{\backslash \; displaystyle\; \{\backslash \; rm\; \{output\}\}\; =\; R\_\; \{8\}\; \backslash \; |\; L\_\; \{8\}\; \backslash ,\}$.

Функции FL и FO делят 32-битные входные данные на две 16-битные половинки. Функция FL - это необратимая битовая манипуляция, тогда как функция FO - необратимая трехэтапная сеть типа Фейстеля.

Функция FL

32-битный вход x из $FL\; (KL\; i,\; x)\; \{\backslash \; displaystyle\; FL\; (KL\_\; \{i\},\; x)\}$делится на две 16-битные половины $x\; =\; l\; \Vert \; r\; \{\backslash \; displaystyle\; x\; =\; l\; \backslash \; |\; r\}$. Сначала левая половина ввода $l\; \{\backslash \; displaystyle\; l\}$обрабатывается побитовым AND с круглым ключом $KL\; i,\; 1\; \{\backslash \; displaystyle\; KL\_\; \{i,\; 1\}\}$и повернут влево на один бит. В результате выполняется операция XOR с правой половиной ввода $r\; \{\backslash \; displaystyle\; r\}$, чтобы получить правую половину вывода $r\; \prime \; \{\backslash \; displaystyle\; r\; \text{'}\}$.

$r\; \prime \; знак\; равно\; ROL\; (l\; \wedge \; KL\; я,\; 1,\; 1)\; \oplus \; r\; \{\backslash \; displaystyle\; r\; \text{'}=\; \{\backslash \; rm\; \{ROL\}\}\; (l\; \backslash \; wedge\; KL\_\; \{i,\; 1\},\; 1)\; \backslash \; oplus\; r\}$

Затем правая половина вывода $r\; \prime \; \{\backslash \; displaystyle\; r\; \text{'}\}$обрабатывается поразрядным OR с ключом раунда $KL\; i,\; 2\; \{\backslash \; displaystyle\; KL\_\; \{i,\; 2\}\}$и повернут влево на один бит. В результате выполняется операция XOR с левой половиной ввода $l\; \{\backslash \; displaystyle\; l\}$, чтобы получить левую половину вывода $l\; \prime \; \{\backslash \; displaystyle\; l\; \text{'}\}$.

$l\; \prime \; =\; ROL\; (r\; \prime \; \vee \; KL\; i,\; 2,\; 1)\; \oplus \; l\; \{\backslash \; displaystyle\; l\; \text{'}=\; \{\backslash \; rm\; \{ROL\}\}\; (r\text{'}\; \backslash \; vee\; KL\_\; \{i,\; 2\},\; 1)\; \backslash \; oplus\; l\}$

Результатом функции является объединение левой и правой половин $x\; \prime \; =\; l\; \prime \; \Vert \; r\; \prime \; \{\backslash \; displaystyle\; x\; \text{'}=\; l\text{'}\; \backslash \; r\; \text{'}\}$.

Function FO

32-битный вход x $FO\; (KO\; i,\; KI\; i,\; x)\; \{\backslash \; displaystyle\; FO\; (KO\_\; \{i\},\; KI\_\; \{i\},\; x)\}$делится на два 16- бит половинки $x\; =\; l\; 0\; \Vert \; r\; 0\; \{\backslash \; displaystyle\; x\; =\; l\_\; \{0\}\; \backslash \; |\; r\_\; \{0\}\}$и прошел через три цикла сети Фейстеля.

В каждом из трех раундов (индексированных j, который принимает значения 1, 2 и 3) левая половина модифицируется, чтобы получить новую правую половину, а правая половина становится левой половиной следующего раунда.

$rj\; =\; FI\; (KI\; i,\; j,\; lj\; -\; 1\; \oplus \; KO\; i,\; j)\; \oplus \; rj\; -\; 1\; lj\; =\; rj\; -\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{lcl\}\; r\_\; \{j\}\; =\; FI\; (\; KI\_\; \{i,\; j\},\; l\_\; \{j-1\}\; \backslash \; oplus\; KO\_\; \{i,\; j\})\; \backslash \; oplus\; r\_\; \{j-1\}\; \backslash \backslash \; l\_\; \{j\}\; =\; r\_\; \{j-1\}\; \backslash \; end\; \{array\}\}\; \}$

Результатом функции будет $x\; \prime \; =\; l\; 3\; \Vert \; r\; 3\; \{\backslash \; displaystyle\; x\; \text{'}=\; l\_\; \{3\}\; \backslash \; |\; r\_\; \{3\}\}$.

Функция FI

функция FI представляет собой нерегулярную сеть типа Фейстеля.

16-битный ввод $x\; \{\backslash \; displaystyle\; x\}$функции $FI\; (K\; i,\; x)\; \{\backslash \; displaystyle\; FI\; (Ki,\; x)\}$делится на две половины $x\; =\; l\; 0\; \Vert \; r\; 0\; \{\backslash \; displaystyle\; x\; =\; l\_\; \{0\}\; \backslash \; |\; r\_\; \{0\}\}$из которых $l\; 0\; \{\; \backslash \; displaystyle\; l\_\; \{0\}\}$имеет ширину 9 бит, а $r\; 0\; \{\backslash \; displaystyle\; r\_\; \{0\}\}$имеет ширину 7 бит.

Биты в левой половине $l\; 0\; \{\backslash \; displaystyle\; l\_\; \{0\}\}$сначала перетасовываются 9-битным блоком подстановки (S-блок) S9, и результат подвергается операции XOR с расширенной нулевой правой половиной $r\; 0\; \{\backslash \; displaystyle\; r\_\; \{0\}\}$, чтобы получить новую 9-битную правую половину $r\; 1\; \{\backslash \; displaystyle\; r\_\; \{1\}\}$.

$r\; 1\; =\; S\; 9\; (l\; 0)\; \oplus \; (00\; \Vert \; r\; 0)\; \{\backslash \; displaystyle\; r\_\; \{1\}\; =\; S9\; (l\_\; \{0\})\; \backslash \; oplus\; (00\; \backslash \; |\; r\_\; \{0\}))\; \backslash ,\}$

Биты правой половины $r\; 0\; \{\backslash \; displaystyle\; r\_\; \{0\}\}$перетасовываются 7-битным S-блоком S7, и результат подвергается операции XOR с семь младших значащих битов (LS7) новой правой половины $r\; 1\; \{\backslash \; displaystyle\; r\_\; \{1\}\}$, чтобы получить новую 7-битную левую половину $l\; 1\; \{\backslash \; displaystyle\; l\_\; \{\; 1\}\}$.

$l\; 1\; =\; S\; 7\; (r\; 0)\; \oplus \; LS\; 7\; (r\; 1)\; \{\backslash \; displaystyle\; l\_\; \{1\}\; =\; S7\; (r\_\; \{0\})\; \backslash \; oplus\; LS7\; (r\_\; \{1\})\; \backslash ,\}$

Промежуточное слово $x\; 1\; =\; l\; 1\; \Vert \; r\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\; =\; l\_\; \{1\}\; \backslash \; |\; r\_\; \{1\}\}$подвергается операции XOR с круглым ключом KI, чтобы получить $x\; 2\; =\; l\; 2\; \Vert \; r\; 2\; \{\backslash \; displaystyle\; x\_\; \{2\}\; =\; l\_\; \{2\}\; \backslash \; |\; r\_\; \{2\}\}$из которых $l\; 2\; \{\backslash \; displaystyle\; l\_\; \{2\}\; \}$имеет ширину 7 бит, а $r\; 2\; \{\backslash \; displaystyle\; r\_\; \{2\}\}$имеет ширину 9 бит.

$x\; 2\; =\; KI\; \oplus \; x\; 1\; \{\backslash \; displaystyle\; x\_\; \{2\}\; =\; KI\; \backslash \; oplus\; x\_\; \{1\}\}$

биты в правой половине $r\; 2\; \{\backslash \; displaystyle\; r\_\; \{2\}\}$Затем перетасовываются 9-битным S-блоком S9, и результат подвергается операции XOR с расширенной нулевой левой половиной $l\; 2\; \{\backslash \; displaystyle\; l\_\; \{2\}\}$для получения новая 9-битная правая половина вывода $r\; 3\; \{\backslash \; displaystyle\; r\_\; \{3\}\}$.

$r\; 3\; =\; S\; 9\; (r\; 2)\; \oplus \; (00\; \Vert \; l\; 2)\; \{\backslash \; displaystyle\; r\_\; \{3\}\; =\; S9\; (r\_\; \{2\})\; \backslash \; oplus\; (00\; \backslash \; |\; l\_\; \{2\})\; \backslash ,\}$

Наконец, биты левой половины $l\; 2\; \{\backslash \; displaystyle\; l\_\; \{2\}\}$перетасовывается 7-битным S-блоком S7, и результат объединяется с помощью XOR с семью младшими битами (LS7) правой половины вывода $r\; 3\; \{\backslash \; displaystyle\; r\_\; \{3\}\}$, чтобы получить 7-битную левую половину $l\; 3\; \{\backslash \; displaystyle\; l\_\; \{3\}\}$вывода.

$l\; 3\; =\; S\; 7\; (l\; 2)\; \oplus \; LS\; 7\; (r\; 3)\; \{\backslash \; displaystyle\; l\_\; \{3\}\; =\; S7\; (l\_\; \{2\})\; \backslash \; oplus\; LS7\; (r\_\; \{3\})\; \backslash ,\}$

вывод - это конкатенация последних левой и правой половин $x\; \prime \; =\; l\; 3\; \Vert \; r\; 3\; \{\backslash \; displaystyle\; x\; \text{'}=\; l\_\; \{3\}\; \backslash \; |\; r\_\; \{3\}\}$.

Блоки подстановки

Блоки подстановки (S-блоки) S7 и S9 определяются как побитовыми выражениями И-ИСКЛЮЧАЮЩЕЕ ИЛИ, так и справочными таблицами в спецификации. Побитовые выражения предназначены для аппаратной реализации, но в настоящее время принято использовать справочные таблицы даже в HW-дизайне.

S7 определяется следующим массивом:

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 определяется следующим массивом:

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,24100,262, 82,216,159,356,177, 175,24100,489, 82,216,159,356,177, 175,24100,489,, 95, 3315245, 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, 501407249265, 89.186.221.428.164, 74.440.196.458.421.350.163, 232158134354, 13.250.491.142.191, 69.193.425.152.227.366.135, 344.300.276.242.437.320.113.278, 11243, 87317, 36, 93496, 27, 487446482, 41, 68.156.457.131.326.403.339, 20, 39115442124, 475384508, 53.112.170.479.151.126.169, 73.268.279.321.168.364, 363292, 46.499.393.327.324, 24.456.267.157.460.488.426.309.229, 439.506.208.271.349.401.434.236, 16209359, 52, 56120199277, 465.416.252.287.246, 6, 83.305.420.345.153.502, 65, 61244282, 173222418, 67.386.368.261.101.476.291.195.430, 49, 79166330, 280.383.373.128.382.408.155.495, 367.388.274.107.459.417, 62454, 132.225.203.316.234, 14301, 91.503.286.424.211.347.307.140.374, 35103125427, 19.214.453.146.498.314.444.230.256.329.198.285, 50116, 78410, 10.205.510.171.231, 45139467, 29, 86505, 32, 72, 26.342.150.313.490.431.238.411.325.149.473, 40119174355, 185233389, 71448273372, 55110178322, 12.469.392.369.190, 1.109.375.137.181, 88, 75308260484, 98.272.370.275.412.111, 336318, 4.504.492.259.304, 77337435, 21.357.303.332.483, 18, 47, 85, 25.497.474.289.100.269.296.478.270.106, 31104433, 84, 414486394, 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, 92404, 485422248297, 23213130466, 22217283, 70.294.360.419.127, 312377, 7468194, 2.117.295.463.258.224.447.247.187, 80398, 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, 4 38,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, 15376,436,464, 59,461};

В 2001 году невозможная дифференциальная атака на шесть раундов KASUMI была представлена ​​Кюн (2001).

В 2003 году Элад Баркан, Эли Бихам и Натан Келлер продемонстрировали атаки типа «человек посередине» против протокола GSM, которые избегали шифра A5 / 3 и тем самым нарушали протокол. Однако этот подход не атакует шифр A5 / 3. Полная версия их статьи была опубликована позже в 2006 году.

В 2005 году израильские исследователи Эли Бихам, Орр Дункельман и Натан Келлер опубликовали связанный ключ атака прямоугольником (бумерангом) на КАСУМИ, которая может разбить все 8 раундов быстрее, чем перебор. Атака требует 2 выбранных открытых текстов, каждый из которых зашифрован одним из четырех связанных ключей, и имеет временную сложность, эквивалентную 2 шифрованию KASUMI. Хотя это, очевидно, не практическая атака, она сводит на нет некоторые доказательства безопасности протоколов 3GPP, которые полагались на предполагаемую силу KASUMI.

В 2010 году Дункельман, Келлер и Шамир опубликовали новую атаку, которая позволяет злоумышленнику восстановить полный ключ A5 / 3 с помощью атаки с использованием связанных ключей. Сложность атаки по времени и пространству настолько мала, что авторы провели атаку за два часа на настольном компьютере Intel Core 2 Duo даже с использованием неоптимизированной эталонной реализации KASUMI. Авторы отмечают, что эта атака может быть неприменима к способу использования A5 / 3 в системах 3G; их главная цель заключалась в том, чтобы опровергнуть заверения 3GPP в том, что их изменения в MISTY не окажут существенного влияния на безопасность алгоритма.

• A5 / 1 и A5 / 2
• MISTY1
• SNOW

• домашняя страница Натана Келлера