Мрежа от замествания и пермутации (SPN) — дефиниция и роля в блоковите шифри

SPN: разгадайте ролята на S-box и P-box в блоковите шифри (AES, Kuznyechik) — принципи, архитектура и значение за криптографската сигурност.

В криптографията SP-мрежата (от "substitution–permutation network") или мрежа от замествания и пермутации (SPN) е структуриран начин за изграждане на блокови шифри чрез последователност от взаимосвързани математически операции. Този подход е използван в множество добре познати алгоритми като AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK и Square. SPN приема блок от открит текст и ключ като вход и след няколко редуващи се слоя от S-boxes и P-boxes извежда шифротекста.

Как работи една SP-мрежа

Типичната SPN е организирана в редове (рундове). Всеки рунд съдържа поне три стъпки:

• слой от кутии за заместване (S-box), които прилагат нелинейно едно-към-едно преобразувание върху малки (под)блокове от битове;
• слой за пермутация (P-box), който разпределя и разбърква битовете от изхода на S-boxes, така че следващият рунд да види смесено положение на битовете;
• вместване на рундовия ключ (който е извлечен от основния ключ чрез схема за разширяване), обикновено чрез операцията XOR.

Декриптирането обикновено се извършва, като процесът се обърне: използват се инверсните S-boxes и инверсията на P-box, а рундовите ключове се прилагат в обратен ред. Затова в SPN дизайна S-box-ите трябва да бъдат инвертируеми (биективни).

Какво представлява S-box

S-box замества малък блок от входни битове с друг блок от изходни битове. За целите на декриптиране това заместване обикновено трябва да е едно-към-едно (биективно) и с равна дължина на входа и изхода. На практика добрият S-box:

• е нелинеен — това осигурява устойчивост срещу линейна криптоанализа;
• има висока "непредвидимост" (nonlinearity) и висока степен на алгебрична сложност (algebraic degree);
• има ниска диференциална еднородност (differential uniformity), т.е. малка вероятност за предсказуеми разлики при двоични входове — това повишава устойчивостта срещу диференциална криптоанализа;
• създава лавинообразен ефект — промяна на един входен бит трябва да промени много (приблизително половината) от изходните битове;
• в едни случаи е реализиран като таблица за търсене (lookup table), а в други чрез логически операции, за да се избягват странични канали.

Примери: в AES S-box е 8×8 биективна таблица с внимателно подбрани криптографски свойства; в по-леки шифри като PRESENT S-box-ът е 4×4, за да бъде по-ефективен в хардуер.

Ролята на P-box

P-box е битова пермутация — тя взема всички изходни битове от S-box-овете в един рунд и ги разпределя към входовете на S-box-овете в следващия рунд. Целта на P-box-а е да разпръсне (diffuse) локалните промени, така че зависимостите от отделни битове да се разпространяват широко. Добър P-box гарантира, че изходните битове от един S-box попадат в различни S-box-ове във следващия рунд, което ускорява достигането на лавинен ефект.

Рундови ключове и схема за разширение на ключа

Във всеки рунд към текущото междинно състояние се добавя рундов ключ, получен от основния ключ чрез схема за разширение (key schedule). Тази схема трябва да бъде проектирана така, че малки промени в основния ключ да довеждат до големи промени в рундовите ключове (за да се постигне объркване). В някои конструкции S-box-овете могат да участват и в самата схема за разширение на ключа.

Защо комбинацията S-box + P-box е важна

Един S-box или един P-box сами по себе си не осигуряват достатъчна сигурност: S-box-ът внася нелинейност (объркване), а P-box-ът организира дифузията (разпръскването на битовете). Редуването на няколко слоя от S- и P-boxes води до спазване на принципите на Shannon за объркване и дифузия:

• Дифузия: Промяна в един бит от открития текст преминава през S-box и води до множество променени битове. P-box разпределя тези промени към различни S-boxове в следващия рунд, след което процесът се повтаря — след няколко рунда всяка промяна се разпространява широко и резултатът изглежда псевдослучаен.
• Объркване: Малка промяна в ключа води до значителни и неочаквани промени в рундовите ключове и следователно в целия шифротекст, правейки връзката между ключ и шифротекст сложна за анализ.
• Дори ако нападателят има един или повече двойки открит текст — шифротекст (известен или избран открит текст), доброто объркване и дифузия затрудняват извеждането на ключа или аналитичното проследяване на структурата на шифъра.

Сигурност и възможни атаки

Безопасността на SPN зависи от:

• качество на S-box-овете (нелинейност, диференциална устойчивост, алгебрична сложност);
• характеристики на P-box (как бързо разпространява битовете между S-boxовете);
• брой рундове — повече рундове обикновено означават по-голяма устойчивост срещу диференциална и линейна криптоанализа;
• схемата за разширение на ключа — уязвимости тук могат доведат до атаки със свързан ключ (related-key) или други специализирани атаки.

Чести техники за атаки срещу SPN включват диференциална криптоанализа, линейна криптоанализа, интегрални атаки (особено за някои малко рундови и структурно податливи шифри), както и атаки със свързан ключ. Добрият дизайн избягва известни слаби страни и осигурява достатъчен брой рундове, за да предотврати практическа експлоатация.

Имплементация и оптимизация

SPN шифрите предлагат присъщ паралелизъм: S-box-овете в един рунд могат да се изчисляват едновременно, което ги прави подходящи за хардуерни и паралелни софтуерни реализации. В зависимост от средата има различни техники за реализиране:

• хардуерни реализации — малки S-box-ове и фиксирани P-box-ове дават висока производителност и малка консумация на ресурси (пример: lightweight шифри като PRESENT);
• софтуерни реализации — често се използва таблица за търсене (lookup table) за S-box, но това може да бъде уязвимо на странични канали (cache-timing); алтернативи са bitslicing и константно-времеви реализации;
• защитни методи срещу странични канали — маскиране, дебалансирани инструкции и използване на логически реализации на S-box вместо таблици.

SPN срещу Файстел мрежи

Мрежата на Feistel (използвана в DES и други) също често използва S-box-ове, но структурата й е различна: Feistel разделя блока на две половини и прилага нелинейна функция само върху едната половина, след което ги комбинира. Някои основни разлики и последици:

• в SPN S-box-овете трябва да са инвертируеми, защото целият блок трябва да бъде декриптиран чрез обратен път; във Файстел вътрешните функции не е задължително да са инвертируеми, тъй като обратимостта се постига от самата Файстел конструкция;
• SPN предлага по-голям паралелизъм — множество S-box-ове могат да се изпълнят едновременно, което е предимство при хардуер и модерни процесори;
• Файстел конструкцията може да бъде по-удобна за дизайни, които желаят опростено декриптиране или използване на еднопосочни вътрешни функции.

Заключителни бележки

SP-мрежите са мощен и гъвкав принцип за проектиране на блокови шифри. Добре проектиран SPN комбинира внимателно подбрани S-box-ове, ефективни P-box пермутации и сигурна схема за разширение на ключа, за да осигури висока степен на объркване и дифузия, и следователно — устойчивост срещу основните методи на криптоанализа. При практическата им реализация трябва да се вземат предвид не само теоретичните свойства, но и въпросите за ефективност и защита срещу странични канали.

Търсене по буква