S-box

У криптографії, S-скриня, S-блок (англ. Substitution-box, S-box) — це засаднича складова шифрування з симетричними ключами, яка виконує підстановки. По суті це звичайна таблиця підстановки. У блочних шифрах їх здебільшого використовують для приховування зв'язків між ключем і шифротекстом — властивість плутанини введена Шенноном.

Загалом, S-скриня приймає m біт на вхід і перетворює їх в n біт на виході, де n не завжди дорівнює m.m×n S-скриню можна втілити як таблицю пошуку з 2^m слів n бітів кожне. Сталі таблиці звичайно використовуються в DES, але в деяких шифрах таблиці створюються динамічно як похідні від ключа (наприклад, алгоритми шифрування Blowfish і Twofish).^[]

S-скрині в DES

Одним з добрих прикладів сталої таблиці є ця 6×4-бітів S-скриня з DES (S₅):

S5		Внутрішні 4 біти на вході
		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Зовнішні біти	00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
	01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
	10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

Дані 6 бітів на вході і 4-біти на виході знаходяться через вибір рядка використовуючи зовнішні два біти (перший і останній), а стовпчик знаходиться по чотирьох внутрішніх бітах. Наприклад, вхід "011011" має зовнішні "01" і внутрішні біти "1101"; відповідний вихід "1001".

У своїх коментарях NSA відзначило такі вимоги до дизайну S-скриньок:

1. Жодна S-скриня не є лінійною або афінною функцію від свого входу.

2. Зміна 1 входового біту має як наслідок зміну щонайменше 2 бітів на виході.

3. S(x) і S(x+001100) мусять різнитись не менш як двома бітами.

Наступні, NSA відзначила як «спричинені вимогами до дизайну»:

4. S(x) =/= S(x+11ab00) для будь-якого вибору a і b.

5. S-скрині обирали таким чином, щоб мінімізувати різницю між кількістю 1 і 0 у будь-якому виході S-скрині за умови сталості одного входового біту.

Інший наслідок умов дизайну зауважили Мейєр і Матяс:

6. Зумисно відібрані S-скриньки потребують для втілення значно більше мінтермів ніж довільно обрані.

Після винайдення диференціального криптоаналізу, Дон Копперсміт оприлюднив умови використані при розробці S-скриньок:

1. Кожна S-скринька повинна мати 6 біт на вході і 4 на виході. (У 1974 це був найбільший розмір S-скриньки, який можна була використати так, щоб DES вписувався в один чип.)
2. Жоден виходовий біт S-скриньки не повинен бути занадто близьким до лінійної функції від входових бітів. (S-скриньки єдина нелінійна складова DES. В їхній нелінійності полягає сила алгоритму.)
3. Кожен «рядок» S-скриніьки повинен містити всі можливі виходи. (Це увипадковлює вихід.)
4. Якщо два входи різняться одним бітом, їх виходи мають різнитись не менше ніж двома бітами.
5. Якщо два входи S-скриньки різняться двома середніми бітами, їх виходи повинні різнитися щонайменше двома бітами. (Ця й попередня умови забезпечують певне поширення.)
6. Якщо два входи S-скриньки різняться своїми першими двома бітами й мають однакові останні, виходи мають бути різними.
7. Для будь-якої 6-бітної різниці між входами, не більше ніж 8 з 32 пар входів, що проявляють таку різницю, можуть проявлятись в такій самій різниці виходів.

Копперсміт зауважив, що кращою другою умовою була б:

2’. Жодна лінійна комбінація входових біт для S-скрині не має бути занадто близькою до лінійної функції від входових біт.

8 S-скриньок алгоритму DES були предметом наполегливих досліджень впродовж багатьох років, щоб перевірити, чи не залишили розробники .

Приклад невдалої S-скрині

Розглянемо:

${\displaystyle S_{i}(x_{1},x_{2},...,x_{6})=(x_{2}\oplus x_{3},x_{1}\oplus x_{4}\oplus x_{5},x_{1}\oplus x_{6},x_{2}\oplus x_{3}\oplus x_{6})}$

або тотожно:

${\displaystyle S_{i}(x)=A_{i}\cdot x{\pmod {2}}}$

${\displaystyle {\begin{pmatrix}0&1&1&0&0&0\\1&0&0&1&1&0\\1&0&0&0&0&1\\0&1&1&0&0&1\end{pmatrix}}\times {\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\end{pmatrix}}={\begin{pmatrix}x_{2}\oplus x_{3}\\x_{1}\oplus x_{4}\oplus x_{5}\\x_{1}\oplus x_{6}\\x_{2}\oplus x_{3}\oplus x_{6}\end{pmatrix}}}$
Тоді ${\displaystyle S_{i}}$ є лінійною функцією.

S-скриня в AES

S-скриня утворюється визначанням обернених елементів для входу в ${\displaystyle GF(2^{8})=GF(2)[x]/(x^{8}+x^{4}+x^{3}+x+1),}$ скінченне поле Rijndael (нуль,який не має оберненого, встановлюється в нуль). Обернений елемент потім піддається афінному перетворенню. Зворотна S-скриня є просто S-скриня запущена в протилежному напрямку. S-скриня працює як таблиця пошуку.

Примітки

1. Chandrasekaran, J. та ін. (2011). A Chaos Based Approach for Improving Non Linearity in the S-Box Design of Symmetric Key Cryptosystems. У Meghanathan, N. та ін. (ред.). . Springer. с. 516. ISBN . Архів оригіналу за 11 травня 2016. Процитовано 4 травня 2012.
2. C.H. Meyer, S.M. Matyas, Cryptography: A New Dimension in Data Security, John Wiley & Sons, New-York, 1982.
3. Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, Technical Report RC 18613, IBM T.J. Watson Center, December 1992.
4. Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, Vol. 38, n. 3, pp. 243-250, May 1994.

Посилання

• A literature survey on S-Box design [ 14 квітня 2012 у Wayback Machine.]
• John Savard's "Questions of S-Box Design" [ 16 липня 2012 у Wayback Machine.]
• Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems" [ 20 травня 2012 у Wayback Machine.]