Skipjack

Skipjack
Skipjack
Создатель	Агентство национальной безопасности (США)
Создан	1980-е
Опубликован	1998г. (рассекречен)
Размер ключа	80 бит
Размер блока	64 бит
Число раундов	32
Тип	Сеть Фейстеля

Skipjack—блочный шифр,разработанныйАгентством национальной безопасности СШАв рамках проектаCapstone^[англ.].После разработки сведения о шифре были засекречены. Изначально он предназначался для использования вчипе Clipperдля защиты аудиоинформации, передаваемой по сетям правительственнойтелефонной связи,а также по сетяммобильнойибеспроводнойсвязи. Позже алгоритм был рассекречен^[1].

История

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 слова $w_{i}$ по 2 байта каждое. Начальные данные есть слова, для которых $k=0$ ,где $k$ — порядковый номер раунда. Сначала совершается 8 раундов по правилу А, затем — по правилу Б. Это повторяется дважды, что, в итоге, дает 32 раунда.

Здесь и далее операция $x\oplus y$ естьбинарнаяоперацияпобитового(поразрядного к числам $x$ и $y$ )сложения по модулю 2.

Правило А

w_{1}^{k+1}=G^{k}(w_{1}^{k})\oplus w_{4}^{k}\oplus counter^{k}

w_{2}^{k+1}=G^{k}(w_{1}^{k})

w_{3}^{k+1}=w_{2}^{k}

w_{4}^{k+1}=w_{3}^{k}

Правило Б

w_{1}^{k+1}=w_{4}^{k}

w_{2}^{k+1}=G^{k}(w_{1}^{k})

w_{3}^{k+1}=w_{1}^{k}\oplus w_{2}^{k}\oplus counter^{k}

w_{4}^{k+1}=w_{3}^{k}

После завершения алгоритмашифротекстомбудут являться слова $w_{i}^{32},\ 1\leqslant i\leqslant 4$ .

Дешифрование

Начальные данные есть слова, для которых $k=32$ .Сначала совершается 8 раундов по правилу Б $^{-1}$ ,затем — по правилу А $^{-1}$ .Повторяется дважды.

Правило А $^{-1}$

w_{1}^{k-1}=[G^{k-1}]^{-1}(w_{2}^{k})

w_{2}^{k-1}=w_{3}^{k}

w_{3}^{k-1}=w_{4}^{k}

w_{4}^{k-1}=w_{1}^{k}\oplus w_{2}^{k}\oplus counter^{k-1}

Правило Б $^{-1}$

w_{1}^{k-1}=[G^{k-1}]^{-1}(w_{2}^{k})

w_{2}^{k-1}=[G^{k-1}]^{-1}(w_{2}^{k})\oplus w_{3}^{k}\oplus counter^{k-1}

w_{3}^{k-1}=w_{4}^{k}

w_{4}^{k-1}=w_{1}^{k}

После завершения алгоритмаоткрытым текстомбудут являться слова $w_{i}^{0},\ 1\leqslant i\leqslant 4$ .

Блок перестановок G

Блок перестановок^[англ.] $G$ действует на 16-битное число и представляет собой четырёхуровневую сеть Фейстеля. Функция $F$ ,действующая на число размером в 8 бит, естьблок подстановок,который в спецификации алгоритма называется $F$ -таблицей.Математически действие блока $G$ можно описать так:

$G^{k}(w)=g_{5}\|g_{6}$
где: $w=g_{1}\|g_{2}$

$g_{i}=F(g_{i-1}\oplus cv_{4k+i-3})\oplus g_{i-2}$

$cv_{4k+i-3}$ — это $(4k+i-3)$ байт ключа

$k$ — порядковый номер раунда

$x\|y$ — операцияконкатенации(объединения) байтов

$[G^{k}]^{-1}(w)=g_{1}\|g_{2}$
где: $w=g_{5}\|g_{6}$

$g_{i-2}=F(g_{i-1}\oplus cv_{4k+i-3})\oplus g_{i}$

$F$ -таблица
	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].

↑Существует свойство комплементарности ключей: если $E_{K}(M)=C$ ,то $E_{\overline {K}}({\overline {M}})={\overline {C}}$ ,где: $E_{K}(M)$ — зашифровывание алгоритмом DES блока открытого текста $M$ , $C$ — полученный шифротекст, ${\overline {x}}$ —побитовое дополнениек $x$ .^[4]

Примечания

↑¹ ²Стенограмма пресс-релиза в Белом Доме по проекту Capstone(англ.).Пресс-служба Белого Дома^[англ.](1993). Дата обращения: 29 ноября 2016. Архивировано изоригинала7 августа 2011 года.
↑Депонирование ключей (key escrow)(неопр.).Словарь терминов по информационной безопасности.www.glossary.ib-bank.ru. Дата обращения: 16 ноября 2016.Архивировано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.Архивировано23 ноября 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(англ.)//Electronics Letters—IEEE,2002. — Vol. 38, Iss. 2. — P. 69—71. — ISSN0013-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. PhanAdvanced Differential-Style Cryptanalysis of the NSA's Skipjack Block Cipher(англ.)//Cryptologia— United States of America:Taylor & Francis,2009. — Vol. 33. — P. 246—270. — ISSN0161-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.

[5] Существует свойство комплементарности ключей: если $E_{K}(M)=C$ ,то $E_{\overline {K}}({\overline {M}})={\overline {C}}$ ,где: $E_{K}(M)$ — зашифровывание алгоритмом DES блока открытого текста $M$ , $C$ — полученный шифротекст, ${\overline {x}}$ —побитовое дополнениек $x$ .^[4]

[capstone_release-1] ¹ ²Стенограмма пресс-релиза в Белом Доме по проекту Capstone(англ.).Пресс-служба Белого Дома^[англ.](1993). Дата обращения: 29 ноября 2016. Архивировано изоригинала7 августа 2011 года.

[key_escrow-2] Депонирование ключей (key escrow)(неопр.).Словарь терминов по информационной безопасности.www.glossary.ib-bank.ru. Дата обращения: 16 ноября 2016.Архивировано16 ноября 2016 года.

[skipjack_review-3] E.F. Brickell;D.E. Denning^[англ.],S.T. Kent,D.P. Maher^[англ.],W. Tuchman.:Skipjack review. Interim report.(англ.)(1993). Архивировано изоригинала8 июня 2011 года.

[complementary-4] Панасенко С. П.Алгоритмы шифрования. Специальный справочник—СПб.:BHV-СПб,2009. — С. 170. — 576 с. —ISBN 978-5-9775-0319-8

[NIST.800-175B-6] Guideline for using cryptographic standards in the Federal Government: Cryptographic mechanisms(англ.).НИСТ(2016). Дата обращения: 29 ноября 2016.Архивировано23 ноября 2016 года.

[skipjack-7] Skipjack and KEA algorithm specifications(англ.).НИСТ(1998). Дата обращения: 29 ноября 2016. Архивировано изоригинала21 октября 2011 года.

[31round-attack-8] 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

[truncated_diff-9] 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

[attack_full_cipher-10] Chung-Wei Phan R.Cryptanalysis of full Skipjack block cipher(англ.)//Electronics Letters—IEEE,2002. — Vol. 38, Iss. 2. — P. 69—71. — ISSN0013-5194;1350-911X—doi:10.1049/EL:20020051

[no_attack_up_to_date-11] «an attack on the full 32-round Skipjack remains elusive until now» —Kim J.,Raphael C.-W. PhanAdvanced Differential-Style Cryptanalysis of the NSA's Skipjack Block Cipher(англ.)//Cryptologia— United States of America:Taylor & Francis,2009. — Vol. 33. — P. 246—270. — ISSN0161-1194;1558-1586—doi:10.1080/01611190802653228

[1]

[2]

[3]

[К 1]

[5]

[6]

[7]

[8]

[9]

[10]

[4]

Симметричные криптосистемы
Потоковые шифры	A3 A5 A8 Decim F-FCSR Grain HC-256 KCipher-2 MICKEY MUGI PIKE Phelix RC4 Rabbit SEAL SNOW SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Сеть Фейстеля	ГОСТ 28147-89(Магма) Blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Cobra DEAL DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NewDES NDS RC5 RC6 SEED Simon Sinople Skipjack SM4 Speck TEA XTEA XXTEA Raiden RTEA Triple DES Twofish
SP-сеть	Кузнечик 3-WAY ABC ARIA AES(Rijndael) Akelarre Anubis BaseKing BassOmatic BelT CRYPTON Diamond2 Grand Cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer Present Rainbow SAFER SHARK SQUARE Serpent Threefish
Другие	FROG NUSH REDOC SC2000 SHACAL CS-Cipher

Skipjack

Содержание

История