Skipjack
Skipjack — блочный шифр, разработанный Агентством национальной безопасности США в рамках проекта Capstone. После разработки сведения о шифре были засекречены. Изначально он предназначался для использования в чипе Clipper для защиты аудиоинформации, передаваемой по сетям правительственной телефонной связи, а также по сетям мобильной и беспроводной связи. Позже алгоритм был рассекречен[1].
Skipjack | |
---|---|
Создатель | Агентство национальной безопасности (США) |
Создан | 1980-е |
Опубликован | 1998 г. (рассекречен) |
Размер ключа | 80 бит |
Размер блока | 64 бит |
Число раундов | 32 |
Тип | Сеть Фейстеля |
История
Skipjack являлся одной из инициатив, предложенных в рамках проекта Capstone. Руководили проектом Агентство национальной безопасности (АНБ) и Национальный институт стандартов и технологий (НИСТ), финансируемые правительством США. Официальная дата начала инициативы — 1993 год. Алгоритм шифрования был разработан в 1980 году, а первая его реализация была получена в 1987 году. Шифр был предназначен для использования в чипе Clipper, встраиваемом в защищаемое оборудование. При этом Skipjack использовался только для шифрования сообщений, а депонирование ключа[2] для возможности последующего использования уполномоченными органами — наиболее обсуждаемый аспект использования шифра — достигалось за счёт отдельного механизма, называемого Law Enforcement Access Field[1].
Изначально проект был засекречен и по этой причине подвергся огромной критике. Для повышения общественного доверия и оценки алгоритма были призваны несколько академических исследователей. По причине отсутствия времени для самостоятельного тщательного исследования эксперты сконцентрировались на изучении представленного АНБ описания процесса разработки и оценки алгоритма. В дополнение к этому они, в течение месяца, провели ряд небольших тестов. В предварительном отчете об их работе (окончательного отчета так и не последовало) указаны три заключения[3]:
- Принимая во внимание, что стоимость вычислительных мощностей уменьшается вдвое каждые 18 месяцев, лишь через 36 лет стоимость взлома Skipjack полным перебором сравняется со стоимостью взлома DES сегодня.
- Риск взлома шифра с помощью более быстрых способов, включая дифференциальный криптоанализ, незначителен. Алгоритм не имеет слабых ключей и свойства комплементарности[К 1].
- Устойчивость Skipjack к криптоанализу не зависит от секретности самого алгоритма.
Шифр был опубликован в открытый доступ 24 июня 1998 года. В августе 2016 года НИСТ принял новые принципы использования криптографических стандартов, в которых отозвал сертификацию алгоритма Skipjack для правительственных целей[5].
Описание
Skipjack использует 80-битный ключ для шифрования/дешифрования 64-битных блоков данных. Это несбалансированная сеть Фейстеля с 32 раундами[6].
Шифрование
Текст разбивается на 4 слова по 2 байта каждое. Начальные данные есть слова, для которых , где — порядковый номер раунда. Сначала совершается 8 раундов по правилу А, затем — по правилу Б. Это повторяется дважды, что, в итоге, дает 32 раунда.
Здесь и далее операция есть бинарная операция побитового (поразрядного к числам и ) сложения по модулю 2.
Правило А |
Правило Б |
После завершения алгоритма шифротекстом будут являться слова .
Дешифрование
Начальные данные есть слова, для которых . Сначала совершается 8 раундов по правилу Б, затем — по правилу А. Повторяется дважды.
|
|
После завершения алгоритма открытым текстом будут являться слова .
Блок перестановок G
Блок перестановок действует на 16-битное число и представляет собой четырёхуровневую сеть Фейстеля. Функция , действующая на число размером в 8 бит, есть блок подстановок, который в спецификации алгоритма называется -таблицей. Математически действие блока можно описать так:
|
|
x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | xA | xB | xC | xD | xE | xF | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0x | a3 | d7 | 09 | 83 | f8 | 48 | f6 | f4 | b3 | 21 | 15 | 78 | 99 | b1 | af | f9 |
1x | e7 | 2d | 4d | 8a | ce | 4c | ca | 2e | 52 | 95 | d9 | 1e | 4e | 38 | 44 | 28 |
2x | 0a | df | 02 | a0 | 17 | f1 | 60 | 68 | 12 | b7 | 7a | c3 | e9 | fa | 3d | 53 |
3x | 96 | 84 | 6b | ba | f2 | 63 | 9a | 19 | 7c | ae | e5 | f5 | f7 | 16 | 6a | a2 |
4x | 39 | b6 | 7b | 0f | c1 | 93 | 81 | 1b | ee | b4 | 1a | ea | d0 | 91 | 2f | b8 |
5x | 55 | b9 | da | 85 | 3f | 41 | bf | e0 | 5a | 58 | 80 | 5f | 66 | 0b | d8 | 90 |
6x | 35 | d5 | c0 | a7 | 33 | 06 | 65 | 69 | 45 | 00 | 94 | 56 | 6d | 98 | 9b | 76 |
7x | 97 | fc | b2 | c2 | b0 | fe | db | 20 | e1 | eb | d6 | e4 | dd | 47 | 4a | 1d |
8x | 42 | ed | 9e | 6e | 49 | 3c | cd | 43 | 27 | d2 | 07 | d4 | de | c7 | 67 | 18 |
9x | 89 | cb | 30 | 1f | 8d | c6 | 8f | aa | c8 | 74 | dc | c9 | 5d | 5c | 31 | a4 |
Ax | 70 | 88 | 61 | 2c | 9f | 0d | 2b | 87 | 50 | 82 | 54 | 64 | 26 | 7d | 03 | 40 |
Bx | 34 | 4b | 1c | 73 | d1 | c4 | fd | 3b | cc | fb | 7f | ab | e6 | 3e | 5b | a5 |
Cx | ad | 04 | 23 | 9c | 14 | 51 | 22 | f0 | 29 | 79 | 71 | 7e | ff | 8c | 0e | e2 |
Dx | 0c | ef | bc | 72 | 75 | 6f | 37 | a1 | ec | d3 | 8e | 62 | 8b | 86 | 10 | e8 |
Ex | 08 | 77 | 11 | be | 92 | 4f | 24 | c5 | 32 | 36 | 9d | cf | f3 | a6 | bb | ac |
Fx | 5e | 6c | a9 | 13 | 57 | 25 | b5 | e3 | bd | a8 | 3a | 01 | 05 | 59 | 2a | 46 |
Криптоанализ
Эли Бихам и Ади Шамир произвели криптографическую атаку против 16 из 32 раундов в течение одного дня после рассекречивания алгоритма. Вместе с Алексом Бирюковым они, используя невозможный дифференциальный криптоанализ, всего в течение нескольких месяцев раскрыли 31 из 32 его раундов[7]. Позже были опубликованы статьи атакующие 28 раундов шифра с использованием усеченных дифференциалов[8].
В 2002 году Рафаэлем Фаном была опубликована статья, анализирующая возможные атаки на полные 32 раунда[9]. Позднее, в 2009 году, в статье, соавтором которой тоже являлся Фан, указано, что на тот момент не существовало атаки на полный алгоритм шифра Skipjack[10].
Комментарии
- Существует свойство комплементарности ключей: если , то , где: — зашифровывание алгоритмом DES блока открытого текста , — полученный шифротекст, — побитовое дополнение к .[4]
Примечания
- Стенограмма пресс-релиза в Белом Доме по проекту Capstone (англ.) (недоступная ссылка). Пресс-служба Белого Дома (1993). Дата обращения: 29 ноября 2016. Архивировано 7 августа 2011 года.
- Депонирование ключей (key escrow) . Словарь терминов по информационной безопасности. www.glossary.ib-bank.ru. Дата обращения: 16 ноября 2016.
- E.F. Brickell; D.E. Denning, S.T. Kent, D.P. Maher, W. Tuchman. Skipjack review. Interim report. (англ.) (недоступная ссылка) (1993). Архивировано 8 июня 2011 года.
- Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — С. 170. — 576 с. — ISBN 978-5-9775-0319-8
- Guideline for using cryptographic standards in the Federal Government: Cryptographic mechanisms (англ.). НИСТ (2016). Дата обращения: 29 ноября 2016.
- Skipjack and KEA algorithm specifications (англ.) (недоступная ссылка). НИСТ (1998). Дата обращения: 29 ноября 2016. Архивировано 21 октября 2011 года.
- Biham E., Biryukov A., Shamir A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials (англ.) // Advances in Cryptology — EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings / J. Stern — Berlin, Heidelberg: Springer Science+Business Media, 1999. — P. 12—23. — ISBN 978-3-540-65889-4 — doi:10.1007/3-540-48910-X_2
- Knudsen L. R., Robshaw M., Wagner D. A. Truncated Differentials and Skipjack (англ.) // Advances in Cryptology — CRYPTO’ 99: 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings / M. Wiener — Springer Berlin Heidelberg, 1999. — P. 165—180. — ISBN 978-3-540-66347-8 — doi:10.1007/3-540-48405-1_11
- Chung-Wei Phan R. Cryptanalysis of full Skipjack block cipher (англ.) // Electron. Lett. — IEEE, 2002. — Vol. 38, Iss. 2. — P. 69—71. — ISSN 0013-5194; 1350-911X — doi:10.1049/EL:20020051
- «an attack on the full 32-round Skipjack remains elusive until now» — Kim J., Raphael C.-W. Phan Advanced Differential-Style Cryptanalysis of the NSA's Skipjack Block Cipher (англ.) // Cryptologia — USA: Taylor & Francis, 2009. — Vol. 33. — P. 246—270. — ISSN 0161-1194; 1558-1586 — doi:10.1080/01611190802653228
Ссылки
- Шнайер Б. Глава 13. Другие блочные шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
- Эли Бихам; Алекс Бирюков, Ади Шамир, E. Richardson, O. Dunkelman. Initial observations on Skipjack (англ.) (1998). Дата обращения: 29 ноября 2016.
- Брюс Шнайер. Declassifying Skipjack (англ.). Crypto-Gram Newsletter (1998). Дата обращения: 29 ноября 2016.