КАСУМИ

КАСУМИ

Общий
Дизайнеры	Митсубиси Электрик
Получено из	MISTY1
Деталь шифрования
Размеры ключей	128 бит
Размеры блоков	64 бита
Структура	Сеть Фейстеля
Раунды	8

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 .

Описание

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

Ключевое расписание

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

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

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

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

Круглые ключи следующие:

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

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

Алгоритм

Алгоритм KASUMI обрабатывает 64-битное слово двумя 32-битными половинами, слева ( $L_{i}$) и правильно( $R_{i}$). Входное слово представляет собой объединение левой и правой половин первого раунда:

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

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

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

где KL _i , KO _i , KI _i — круглые ключи для меня ^й круглый.

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

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

и для равного раунда

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

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

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

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

Функция ФЛ

32-битный x вход $FL(KL_{i},x)$ делится на две 16-битные половины $x=l\|r$. Сначала левая половина ввода $l$ побитовое И с круглым ключом $KL_{i,1}$ и повернут осталось на один бит. Результатом этого является XOR к правой половине ввода. $r$ чтобы получить право половина продукции $r'$.

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

Тогда правая половина вывода $r'$ побитовое ИЛИ с круглым ключом $KL_{i,2}$ и повернут осталось на один бит. Результатом этого является XOR к левой половине ввода. $l$ чтобы получить левую половина продукции $l'$.

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

Результатом функции является объединение левой и правой половин. $x'=l'\|r'$.

Функция ФО

32-битный x вход $FO(KO_{i},KI_{i},x)$ делится на две 16-битные половины $x=l_{0}\|r_{0}$, и прошел через три раунда сети Фейстеля.

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

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

Результат функции: $x'=l_{3}\|r_{3}$.

Функция ФИ

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

16-битный вход $x$ функции $FI(Ki,x)$ делится на две половины $x=l_{0}\|r_{0}$ из которых $l_{0}$ имеет ширину 9 бит и $r_{0}$ имеет ширину 7 бит.

Биты в левой половине $l_{0}$ сначала перемешиваются 9-битным блоком подстановки (S-box) S9 , а результат подвергается операции XOR с помощью расширенная до нуля правая половина $r_{0}$ чтобы получить новую 9-битную правую половину $r_{1}$.

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

Части правой половины $r_{0}$ перемешиваются 7-битным S-box S7 , а результат подвергается операции XOR с помощью семь младших битов ( LS7 ) новой правой половины $r_{1}$ чтобы получить новую 7-битную левую половину $l_{1}$.

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

Промежуточное слово $x_{1}=l_{1}\|r_{1}$ выполняется операция XOR с круглым ключом KI, чтобы получить $x_{2}=l_{2}\|r_{2}$ из которых $l_{2}$ имеет ширину 7 бит и $r_{2}$ имеет ширину 9 бит.

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

Биты в правой половине $r_{2}$ затем перемешиваются 9-битным S-box S9 , и результат подвергается операции XOR с расширенная до нуля левая половина $l_{2}$ чтобы получить новую 9-битную правую половину вывода $r_{3}$.

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

Наконец, кусочки левой половины $l_{2}$ перемешиваются 7-битным S-box S7 , а результат подвергается операции XOR с помощью семь младших битов ( LS7 ) правой половины вывода $r_{3}$ чтобы получить 7 бит слева половина $l_{3}$ вывода.

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

Результатом является объединение последних левой и правой половин. $x'=l_{3}\|r_{3}$.

Коробки замены

Поля подстановки (S-блоки) S7 и S9 определяются как побитовыми выражениями AND-XOR, так и справочными таблицами в спецификации. Побитовые выражения предназначены для аппаратной реализации, но в настоящее время принято использовать справочные таблицы даже в аппаратном обеспечении.

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

Криптоанализ

В 2001 году невозможную дифференциальную атаку на шесть раундов КАСУМИ. Кюн (2001) представил

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

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

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

См. также

• А5/1 и А5/2
• СНЕГ

Внешние ссылки

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