Просмотр кода страницы Skipjack

{{Карточка блочного шифра
|название      = Skipjack
|создатель     = [[Агентство национальной безопасности (США)]]
|опубликован   = [[1998]] г. (рассекречен)
|размер ключа  = 80 бит
|размер блока  = 64 бит
|число раундов = 32
|тип           = [[Сеть Фейстеля]]
}}
'''Skipjack''' — [[блочный шифр]], разработанный [[Агентство национальной безопасности (США)|Агентством национальной безопасности США]] в рамках проекта {{iw|Capstone|||Capstone_(cryptography)}}. После разработки сведения о шифре были засекречены. Изначально он предназначался для использования в [[Микросхема Clipper|чипе Clipper]] для защиты аудиоинформации, передаваемой по сетям правительственной [[Телефония|телефонной связи]], а также по сетям [[Мобильная связь|мобильной]] и [[Радиосвязь|беспроводной]] связи. Позже алгоритм был рассекречен<ref name="capstone_release" />.

== История ==
Skipjack являлся одной из инициатив, предложенных в рамках проекта {{iw|Capstone|||Capstone_(cryptography)}}. Руководили проектом [[Агентство национальной безопасности (США)|Агентство национальной безопасности]] (АНБ) и [[Национальный институт стандартов и технологий]] (НИСТ), финансируемые правительством США. Официальная дата начала инициативы — 1993 год. Алгоритм [[Шифрование|шифрования]] был разработан в 1980 году, а первая его реализация была получена в 1987 году. Шифр был предназначен для использования в [[Микросхема_Clipper|чипе Clipper]], встраиваемом в защищаемое оборудование. При этом Skipjack использовался только для шифрования сообщений, а [[депонирование ключа]]<ref name="key_escrow" /> для возможности последующего использования уполномоченными органами — наиболее обсуждаемый аспект использования шифра — достигалось за счёт отдельного механизма, называемого ''Law Enforcement Access Field''<ref name="capstone_release" />.

Изначально проект был засекречен и по этой причине подвергся огромной критике. Для повышения общественного доверия и оценки алгоритма были призваны несколько академических исследователей. По причине отсутствия времени для самостоятельного тщательного исследования эксперты сконцентрировались на изучении представленного АНБ описания процесса разработки и оценки алгоритма. В дополнение к этому они, в течение месяца, провели ряд небольших тестов. В предварительном отчете об их работе (окончательного отчета так и не последовало) указаны три заключения<ref name="skipjack_review" />:
<blockquote>
# Принимая во внимание, что стоимость [[Вычислительная_мощность_компьютера|вычислительных мощностей]] уменьшается вдвое каждые 18 месяцев, лишь через 36 лет стоимость взлома Skipjack [[Полный_перебор|полным перебором]] сравняется со стоимостью взлома [[DES]] сегодня.
# Риск взлома шифра с помощью более быстрых способов, включая [[дифференциальный криптоанализ]], незначителен. Алгоритм не имеет {{iw|слабый ключ|слабых ключей||Weak_key}} и свойства [[свойство комплементарности ключей|комплементарности]]{{ref+|Существует свойство комплементарности ключей: если <math>E_K(M) = C</math>, то <math>E_{\overline{K}}(\overline{M}) = \overline{C}</math>, где: <math>E_K(M)</math> — зашифровывание алгоритмом DES блока открытого текста <math>M</math>, <math>C</math> — полученный шифротекст, <math>\overline{x}</math> — [[Битовые операции|побитовое]] [[Отрицание|дополнение]] к <math>x</math>.<ref name="complementary" />|К}}.
# Устойчивость Skipjack к [[криптоанализ]]у не зависит от секретности самого алгоритма.
</blockquote>

Шифр был опубликован в открытый доступ 24 июня 1998 года. В августе 2016 года НИСТ принял новые принципы использования [[Федеральные_стандарты_обработки_информации|криптографических стандартов]], в которых отозвал сертификацию алгоритма Skipjack для правительственных целей<ref name="NIST.800-175B" />.

== Описание ==
Skipjack использует 80-битный [[Ключ_(криптография)|ключ]] для шифрования/дешифрования 64-битных блоков данных. Это несбалансированная [[сеть Фейстеля]] с 32 раундами<ref name="skipjack" />.

=== Шифрование ===
[[Файл:Skipjack - Stepping Rules.png|мини|400px|Раунды алгоритма Skipjack]]
Текст разбивается на 4 слова <math>w_i</math> по 2 байта каждое. Начальные данные есть слова, для которых <math>k = 0</math>, где <math>k</math> — порядковый номер раунда. Сначала совершается 8 раундов по правилу А, затем — по правилу Б. Это повторяется дважды, что, в итоге, дает 32 раунда.

Здесь и далее операция <math>x \oplus y</math> есть [[Бинарная операция|бинарная]] операция [[Битовые операции|побитового]] (поразрядного к числам <math>x</math> и <math>y</math> ) [[сложение по модулю 2|сложения по модулю 2]].

{{столбцы|width=60em}}
{{столбец}}
''Правило А''
:<math>w_1^{k+1} = G^k(w_1^k) \oplus w_4^k \oplus counter^k</math>
:<math>w_2^{k+1} = G^k(w_1^k)</math>
:<math>w_3^{k+1} = w_2^k</math>
:<math>w_4^{k+1} = w_3^k</math>
{{столбец}}
''Правило Б''
:<math>w_1^{k+1} = w_4^k</math>
:<math>w_2^{k+1} = G^k(w_1^k)</math>
:<math>w_3^{k+1} = w_1^k \oplus w_2^k \oplus counter^k</math>
:<math>w_4^{k+1} = w_3^k</math>
{{столбцы/конец}}

После завершения алгоритма [[шифротекст]]ом будут являться слова <math>w_i^{32},\ 1 \leqslant i \leqslant 4</math>.

=== Дешифрование ===
Начальные данные есть слова, для которых <math>k = 32</math>. Сначала совершается 8 раундов по правилу Б<math>^{-1}</math>, затем — по правилу А<math>^{-1}</math>. Повторяется дважды.
{{столбцы|width=60em}}
{{столбец}}
<center>''Правило А<math>^{-1}</math>''</center>
:<math>w_1^{k-1} = [G^{k-1}]^{-1}(w_2^k)</math>
:<math>w_2^{k-1} = w_3^k</math>
:<math>w_3^{k-1} = w_4^k</math>
:<math>w_4^{k-1} = w_1^k \oplus w_2^k \oplus counter^{k-1}</math>
{{столбец}}
<center>''Правило Б<math>^{-1}</math>''</center>
:<math>w_1^{k-1} = [G^{k-1}]^{-1}(w_2^k)</math>
:<math>w_2^{k-1} = [G^{k-1}]^{-1}(w_2^k) \oplus w_3^k \oplus counter^{k-1}</math>
:<math>w_3^{k-1} = w_4^k</math>
:<math>w_4^{k-1} = w_1^k</math>
{{столбцы/конец}}
После завершения алгоритма [[Открытый_текст|открытым текстом]] будут являться слова <math>w_i^{0},\ 1 \leqslant i \leqslant 4</math>.

=== Блок перестановок G ===
[[Файл:Skipjack - G-permutation diagram.png|мини|400px|Схематическое представление блока перестановок G в шифре Skipjack]]
{{iw|Блок перестановок|||Permutation_box}} <math>G</math> действует на 16-битное число и представляет собой четырёхуровневую сеть Фейстеля. Функция <math>F</math>, действующая на число размером в 8 бит, есть [[S-блок (информатика)|блок подстановок]], который в спецификации алгоритма называется <math>F</math>-''таблицей''. Математически действие блока <math>G</math> можно описать так:
{{столбцы|width=60em}}
{{столбец}}
*<math>G^k(w) = g_5 \| g_6</math>
*:где: <math>w = g_1 \| g_2</math>
*:<math>g_i = F(g_{i-1} \oplus cv_{4k+i-3}) \oplus g_{i-2} </math>
*:<math>cv_{4k+i-3}</math> — это <math>(4k+i-3)</math> байт ключа
*:<math>k</math> — порядковый номер раунда
*:<math>x \| y</math> — операция [[Конкатенация|конкатенации]] (объединения) байтов
{{столбец}}
*<math>[G^k]^{-1}(w) = g_1 \| g_2</math>
*:где: <math>w = g_5 \| g_6</math>
*:<math>g_{i-2} = F(g_{i-1} \oplus cv_{4k+i-3}) \oplus g_i</math>
{{столбцы/конец}}

{| class="wikitable"
|+ <math>F</math>-таблица
!
!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 раундов в течение одного дня после рассекречивания алгоритма. Вместе с [[Алекс Бирюков|Алексом Бирюковым]] они, используя {{iw|невозможный дифференциальный криптоанализ|||Impossible_differential_cryptanalysis}}, всего в течение нескольких месяцев раскрыли 31 из 32 его раундов<ref name="31round-attack" />. Позже были опубликованы статьи атакующие 28 раундов шифра с использованием {{iw|усеченных дифференциалов|||Truncated_differential_cryptanalysis}}<ref name="truncated_diff" />.

В 2002 году Рафаэлем Фаном была опубликована статья, анализирующая возможные атаки на полные 32 раунда<ref name="attack_full_cipher" />. Позднее, в 2009 году, в статье, соавтором которой тоже являлся Фан, указано, что на тот момент не существовало атаки на полный алгоритм шифра Skipjack<ref name="no_attack_up_to_date" />.

== Комментарии ==
{{примечания|group=К}}

== Примечания ==
{{примечания|2|refs=
<ref name="capstone_release">{{cite web
 |url         = https://w2.eff.org/Privacy/Key_escrow/Clipper/wh_crypto_original.announce
 |title       = Стенограмма пресс-релиза в Белом Доме по проекту Capstone
 |publisher   = {{iw|Пресс-служба Белого Дома|||White House Office of the Press Secretary}}
 |date        = 1993
 |accessdate  = 2016-11-29
 |lang        = en
 |archiveurl  = https://web.archive.org/web/20110807055459/http://w2.eff.org/Privacy/Key_escrow/Clipper/wh_crypto_original.announce
 |archivedate = 2011-08-07
 |deadlink    = yes
}}</ref>
<ref name="complementary">{{source|Q27942699|pages=170|ref=Панасенко|ref-year=2009}} <!-- Алгоритмы шифрования. Специальный справочник --></ref>
<ref name="skipjack_review">
{{cite web
 |author      = E.F. Brickell
 |coauthors   = {{iw|D.E. Denning|||Dorothy E. Denning}}, S.T. Kent, {{iw|D.P. Maher|||David Maher}}, W. Tuchman
 |url         = http://www.cs.georgetown.edu/~denning/crypto/clipper/SKIPJACK.txt
 |title       = Skipjack review. Interim report.
 |date        = 1993
 |archiveurl  = https://web.archive.org/web/20110608020227/http://www.cs.georgetown.edu/~denning/crypto/clipper/SKIPJACK.txt
 |archivedate = 2011-06-08
 |lang        = en
 |deadurl     = yes
}}</ref>
<ref name="NIST.800-175B">{{cite web
 |url = http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-175B.pdf
 |title = Guideline for using cryptographic standards in the Federal Government: Cryptographic mechanisms
 |publisher = [[Национальный институт стандартов и технологий|НИСТ]]
 |accessdate = 2016-11-29
 |date = 2016
 |lang = en
 |archive-date = 2016-11-23
 |archive-url = https://web.archive.org/web/20161123072949/http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-175B.pdf
 |deadlink = no
 }}</ref>
<ref name="attack_full_cipher">{{source|Q27942583|ref=Chung-Wei Phan|ref-year=2002}} <!-- Cryptanalysis of full Skipjack block cipher // Electron. Lett. --></ref>
<ref name="no_attack_up_to_date">«an attack on the full 32-round Skipjack remains elusive until now» — {{source|Q27942687|ref=Kim, Phan|ref-year=2009}} <!-- Advanced Differential-Style Cryptanalysis of the NSA's Skipjack Block Cipher // Cryptologia --></ref>
<ref name="skipjack">{{cite web
 |url         = http://csrc.nist.gov/groups/ST/toolkit/documents/skipjack/skipjack.pdf
 |title       = Skipjack and KEA algorithm specifications
 |publisher   = [[Национальный институт стандартов и технологий|НИСТ]]
 |date        = 1998
 |accessdate  = 2016-11-29
 |lang        = en
 |archiveurl  = https://web.archive.org/web/20111021070535/http://csrc.nist.gov/groups/ST/toolkit/documents/skipjack/skipjack.pdf
 |archivedate = 2011-10-21
 |deadlink    = yes
}}</ref>
<ref name="truncated_diff">{{source|Q27942617|ref=Knudsen, Robshaw, Wagner|ref-year=1999}} <!-- Truncated Differentials and Skipjack // Advances in Cryptology — CRYPTO’ 99: 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings --></ref>
<ref name="31round-attack">{{source|Q27942592|ref=Biham, Biryukov, Shamir|ref-year=1999}} <!-- 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 --></ref>
<ref name="key_escrow">{{cite web
 |url = http://www.glossary.ib-bank.ru/solution/212
 |title = Депонирование ключей (key escrow)
 |work = Словарь терминов по информационной безопасности
 |publisher = www.glossary.ib-bank.ru
 |accessdate = 2016-11-16
 |archive-date = 2016-11-16
 |archive-url = https://web.archive.org/web/20161116022314/http://www.glossary.ib-bank.ru/solution/212
 |deadlink = no
 }}</ref>
}}

== Ссылки ==
* {{Книга:Шнайер Б.: Прикладная криптография|часть=Глава 13. Другие блочные шифры}}
* {{cite web
 |url = http://www.cs.technion.ac.il/~biham/Reports/SkipJack/note1.html
 |author = [[Эли Бихам]]
 |coauthors = [[Алекс Бирюков]], [[Ади Шамир]], E. Richardson, O. Dunkelman
 |title = Initial observations on Skipjack
 |date = 1998
 |accessdate = 2016-11-29
 |lang = en
}}
* {{cite web
 |url = http://www.schneier.com/crypto-gram-9807.html#skip
 |author = [[Брюс Шнайер]]
 |title = Declassifying Skipjack
 |work = Crypto-Gram Newsletter
 |date = 1998
 |accessdate = 2016-11-29
 |lang = en
}}

{{симметричные криптоалгоритмы}}

[[Категория:Сеть Фейстеля]]
{{Добротная статья|Теория информации и криптография}}