KASUMI

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи. В UMTS используется в криптографических функциях f8 и f9, в GSM используется в алгоритме A5/3, а в GPRS — в алгоритме GEA/3, причем два последних используют шифр KASUMI с ключом длины 64 бита.

KASUMI
Создатель ETSI
Создан 1999 год
Опубликован 1999 год
Размер ключа 128 бит
Размер блока 64 бит
Число раундов 8
Тип модификация сети Фейстеля

KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI)[1]. За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

Как показали в 2010 году криптоаналитики, в процессе изменений надежность алгоритма MISTY1 была снижена: KASUMI имеет уязвимости для некоторых типов атак, тогда как MISTY1 является стойким по отношению к ним.[2]

Описание

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

Схема шифрования

Основной алгоритм

KASUMI разлагается в набор функций (FL, FO, FI), которые используются вместе со связанными с ними ключами (KL, KO, KI)

Входной блок данных I разделяется на две равные части:

Затем для каждого :

где  — раундовая функция.  — раундовый 128-битный ключ

На выходе

Функция раунда

Вычисляется следующим образом:

Для раундов 1,3,5,7:

Для раундов 2,4,6,8:

Функция FL

На вход функции подается 32-битный блок данных I и 32-битный ключ KLi, который разделяется на два 16-битных подключа:

.

Входная строка I разделяется на две части по 16 бит:

.

Определим:

Где  — циклический сдвиг влево на 1 бит.

На выходе .

Функция FO

На вход функции подается 32-битный блок данных и два ключа по 48 бит: .

Входная строка I разделяется на две части по 16 бит: .

48-битные ключи разделяются на три части каждый:

и .

Затем для определим:

На выходе .

Функция FI

На вход функции подается 16-битный блок данных I и 16-битный ключ KIi, j.

Вход I разделяется на две неравные составляющие: 9-битную левую часть L0 и 7-битную правую R0:

.

Точно так же ключ KIi, j, разделяется на 7-битную компоненту KIi, j,1 и 9-битную компоненту KIi, j,2:

.

Функция использует два S-блока: S7 который отображает 7-битный вход в 7-битный выход, и S9 который отображает 9-битный вход в 9-битный выход.

Также используются еще две функции:

Преобразует 7-битное значение x в 9-битное значение добавлением двух нулей в старшие биты.
Преобразует 9-битное значение x в 7-битное вычеркиванием из него двух старших битов.

Функция реализуется следующим набором операций:

Функция возвращает значение .

S-блоки

S-блоки преобразуют 7 или 9 битный входной блок в соответственно 7 или 9 битный выходной блок, используя таблицы подстановок

Например: S7[30] = 124

Десятичная таблица замены для блока S7:

S7[0-15]5450625622349496386639321812333
S7[16-31]551133911421676512477346272511112481
S7[32-47]539121795260584810112740120104707143
S7[48-63]2012272612310913100771167821010598
S7[64-79]1171167611891060125118998669305712687
S7[80-95]11251175951490849183510332972866
S7[96-111]102312645754859237748049682911544
S7[112-127]64107108241108336784219154188119593

Десятичная таблица замены для блока S9:

S9[0-15]1672391613793913349338382264835845238590397
S9[16-31]1832531473314153405136230650026282216159356177
S9[32-47]17524148937206170333442543785814322081400
S9[48-63]9533152455423521840547226417249437129039976
S9[64-79]16519739512125748042321224028462176406507288223
S9[80-95]5014072492658918622142816474440196458421350163
S9[96-111]2321581343541325049114219169193425152227366135
S9[112-127]3443002762424373201132781124387317369349627
S9[128-143]48744648241681564571313264033392039115442124
S9[144-159]4753845085311217047915112616973268279321168364
S9[160-175]3632924649939332732424456267157460488426309229
S9[176-191]439506208271349401434236162093595256120199277
S9[192-207]4654162522872466833054203451535026561244282
S9[208-223]173222418673863682611014762911954304979166330
S9[224-239]28038337312838240815549536738827410745941762454
S9[240-255]1322252033162341430191503286424211347307140374
S9[256-271]3510312542719214453146498314444230256329198285
S9[272-287]50116784101020551017123145139467298650532
S9[288-303]722634215031349043123841132514947340119174355
S9[304-319]185233389714482733725511017832212469392369190
S9[320-335]1109375137181887530826048498272370275412111
S9[336-351]3363184504492259304773374352135730333248318
S9[352-367]4785254974742891002692964782701063110443384
S9[368-383]4144863949699154511148413361409255162215302201
S9[384-399]26635134314444136510829825134182509138210335133
S9[400-415]31135232814139634612331945028142922844348192404
S9[416-431]485422248297232131304662221728370294360419127
S9[432-447]3123777468194211729546325822444724718780398
S9[448-463]284353105390299471470184572003486320418833451
S9[464-479]97303102199416012949364179263102189207114402
S9[480-495]438477387122192423815145118180449293323136380
S9[496-511]43666045534144520243282371537643646459461

Получение раундовых ключей

Каждый раунд KASUMI получает ключи из общего ключа K следующим образом:

  • 128-битный ключ K разделяется на 8:
  • Вычисляется второй массив Kj:

где Cj определяются по таблице:

C10x0123
С20x4567
С30x89AB
С40xCDEF
С50xFEDC
С60xBA98
С70x7654
С80x3210
  • Ключи для каждого раунда вычисляются по следующей таблице:
Ключ12345678
K1<<<1K2<<<1K3<<<1K4<<<1K5<<<1K6<<<1K7<<<1K8<<<1
K3'K4'K5'K6'K7'K8'K1'K2'
K2<<<5K3<<<5K4<<<5K5<<<5K6<<<5K7<<<5K8<<<5K1<<<5
K6<<<8K7<<<8K8<<<8K1<<<8K2<<<8K3<<<8K4<<<8K5<<<8
K7<<<13K8<<<13K1<<<13K2<<<13K3<<<13K4<<<13K5<<<13K6<<<13
K5'K6'K7'K8'K1'K2'K3'K4'
K4'K5'K6'K7'K8'K1'K2'K3'
K8'K1'K2'K3'K4'K5'K6'K7'

где X<<<n — циклический сдвиг на n бит влево.

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

В 2001 году была представлена атака методом невозможных дифференциалов. Автор - Ульрих Кён (2001).[3]

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

В 2005 году Эли Бихам, Орр Дункельман и Натан Келлер опубликовали атаку на KASUMI методом бумеранга, которая взламывает шифр быстрее, чем полный перебор.[3] Для атаки требуется выбранных открытых текстов, каждый из которых был зашифрован одним из 4 связанных ключей, и имеет сложность по времени, эквивалентную шифрованиям KASUMI. Эта атака показывает небезопасность шифрования KASUMI в 3G сетях.

В январе 2010 Orr Dunkelman, Nathan Keller и Ади Шамир опубликовали работу, в которой показали уязвимость Kasumi для атаки на основе связанных ключей (Related-key attack). Злоумышленник может восстановить полный ключ A5/3 с использованием незначительного количества вычислительных ресурсов (авторы оценивают их в 226 по данным, 230 по памяти и 232 по времени и смогли реализовать её за 2 часа работы современного персонального компьютера). Авторы также отметили, что атака может быть не применима к тому способу, каким KASUMI используется в сетях 3G. Разработанная ими атака также не применима к оригинальному MISTY, и они ставят под сомнение заявления 3GPP о том, что при создании KASUMI не была снижена защищенность алгоритма.[2]

Примечания

  1. (англ) Universal Mobile Telecommunications System (UMTS); Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification. ETSI (2007). Архивировано 11 апреля 2012 года.
  2.  (англ.) Eli Biham, Orr Dunkelman, Nathan Keller. «A Related-Key Rectangle Attack on the Full KASUMI» (ps) in ASIACRYPT 2005.: 443-461. Дата обращения: 2009-11-27. Архивная копия от 11 октября 2013 на Wayback Machine
  3. (англ) Elad Barkan, Eli Biham, Nathan Keller. «Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication» in CRYPTO 2003.: 600-616.
  4. (англ) Elad Barkan, Eli Biham, Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version). Архивировано 11 апреля 2012 года.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.