Стаття присвячена багатопоточне виконання криптоперетворень з точки зору використання паралелізму в алгоритмічних конструкціях шифрів.
Все криптоперетворень використовувані в даній статті не більше ніж демонстрація можливих підходів до побудови паралельних криптографічних алгоритмів.
Якщо в результаті цього вийшло щось варте уваги криптографа, то це виключно випадково ...

Автор: R_T_T

Стаття присвячена багатопоточне виконання криптоперетворень з точки зору використання паралелізму в алгоритмічних конструкціях шифрів.
Все криптоперетворень використовувані в даній статті не більше ніж демонстрація можливих підходів до побудови паралельних криптографічних алгоритмів.
Якщо в результаті цього вийшло щось варте уваги криптографа, то це виключно випадково ...

Публічна інформація про квантові методах криптоаналізу

Вже давно не секрет, що розроблені алгоритми криптоаналізу симетричного, і асиметричного шифрування спеціально для квантових комп'ютерів. Алгоритми були, не було комп'ютерів, тепер вони з'явилися.

http://www.securitylab.ru/news/448779.php

Незалежні (академічні) криптоаналитики повинні мати свій інструмент для публічних досліджень, і він вже теж з'явився. http://www.pcweek.ru/idea/article/detail.php?ID=185415

До недавнього часу вважалося, що симетричне шифрування погано піддається методам квантового криптоанализа, але ось новина стосується злому блокових шифрів новим (добре забутим старим) методом. http://www.securitylab.ru/news/301779.php?pagen=3&el_id=301779

На перший погляд не зрозуміло про що йде мова, спробую пояснювати «на пальцях» ...

По-перше, це повернення до стародавнього аналоговому вирішувачі.

Були такі раніше обчислювальні установки, тоді вони були «електричними», а ось тепер стали «квантовими». Але суть від цього не змінюється.

По-друге, в описуваної установці використовується нова техніка квантового криптоанализа вимагає пояснень.

Візьмемо простий випадок генерації гами, що виробляється наприклад, на основі алгоритму ГОСТ 28147-89. Оціфруем вийшла послідовність гами як хвилю, за допомогою перетворення Фур'є, розклавши на гармонійні складові.

В результаті отримаємо класичну і дуже стабільну картину псевдослучайного «рожевого» шуму, там буде стабільний і обмежений набір частот модульованих по амплітуді і фазі.

Тепер накладемо на гаму шіфруемий текст, у нас вийде зашифрований текст, його теж можна представити у вигляді оцифрованої хвильової функції. Фактично шифрування, це процес тотожний радіопередачі, коли модулюється високочастотне випромінювання низькочастотних сигналом. Гамма це високочастотний сигнал, а шіфруемий текст, це низькочастотний модулятор.

Злом за допомогою квантової криптографії по суті тотожний роботі детекторного приймача, відсікається вихідна хвильова функція і виділяється низькочастотна модулирующая складова.

Якщо шіфруемий текст повністю позбавлений внутрішніх закономірностей (в найпростішому випадку містить випадкові числа) то ми отримаємо вже не «рожевий», а класичний «білий» шум. Такий шифротекст квантової криптографії складно розколоти, потрібно мати для криптоаналізу вихідний і зашифрований текст, тоді обчислити ключі реально.

Але зазвичай шифруються тексти з внутрішніми взаємозв'язками (повторами в найпростішому випадку), там де є повторюваність (навіть не явна), картина зміниться, в спектрі з'являться специфічні низькочастотні складові (пучности).

В цьому випадку, навіть вихідний текст хакерам стає не потрібен.

Висновок з вище викладеного очевидний, крім алгоритмічної складності алгоритм шифрування повинен ще й забезпечувати статистичні параметри шифротекста максимально наближені до випадкового розподілу.

Як з цим боротися?

АНБ ввела в публічний обіг поняття «ПостКвантовая криптографія», скористаємося нею і ми. Поява цього терміна символічно і означає, що старі методи шифрування вже не придатні.

Для початку АНБ пропонує збільшувати довжину ключа, це не вирішення проблеми, але істотне утруднення процесу злому. В подальшому взагалі пропонується переходити на більш стійкі алгоритми.

Вектор спрямування в розробках нових блокових шифрів очевидний, це наближення шифрованого тексту до параметрів випадкової послідовності, зашифрований текст повинен бути максимально статистично схожий з даними одержуваними на генераторах випадкових чисел.

У Росії на даний момент офіційно існує два блочних шифру, новий «Коник» не придатний для швидкісного шифрування, його доля спеціальні прискорювачі типу вбудованого в Інтел спец / обчислювача AES шифру.

Старий ГОСТ 28147-89 (Магма) ідеально лягає на систему команд х86-84 в частині паралельних обчислень (AVX розширення). Взявши нове ім'я, він, на жаль не пройшов «рестайлінгу», який йому вже давно необхідний.

Тому, фантазувати і вигадувати нові стійкі алгоритми, не будемо. Замість цього займемося пошуком «краси» в паралельній реалізації ГОСТ 28147-89, а краса страшна сила, вона перемагає все, в тому числі і квантові методи злому ...

Що зробити конкретно?

По-перше, потрібно статистичні параметри «Магми» максимально наблизити до характеристик випадкової послідовності (білого шуму). Це зробиться «чесним» підбором блоків замін.

По-друге, «Магма» потребує збільшення розрядності ключів і блоків даних. Потрібно йти від схеми чотирьох повторів 8 ключів і переходити до схеми без повторів. При цьому потрібно збільшувати розмірність блоків даних.

По-третє, з урахуванням специфіки квантових методів злому, простого збільшення довжини ключа і розмірності блоків мало, потрібен глибокий «тюнінг».

Перерахую головне:

- шіфруемоготексту попередньо пропускати через процедуру видалення надмірності, простіше кажучи, компресувати з максимальною ретельністю.

- Чи не використовувати алгоритми володіють оборотністю, відповідно працювати в режимі гамування, або, що ще краще в режимі прямої заміни + гамування.

- Ввести в алгоритм операції по «заплутування» стану.

- Ввести операції по формуванню «невизначеності» стану накопичувачів.

- Чи не використовувати лінійних «зацеплений» між суміжними блоками, тобто відмовитися від лінійних перетворень при формуванні первинних заповнень.

Техніка паралельних раундів

З моєї легкої руки зараз все перейшли на паралельну реалізацію ГОСТ 28147-89 , Поки паралелізм використовується тільки для збільшення швидкості, за рахунок одночасного розрахунку до 16 блоків. Раніше апаратура дозволяла ефективно вести розрахунки тільки на 8 блоках (на ХММ регістрах), зараз можна вже використовувати регістри подвоєною довжини (YMM регістри).

Єдино можливим (з точки зору оптимізації) розміщенням накопичувачів N1 і N2 по регістрах довгою 256 біт є така схема, для рахунку в 16 потоків:

Як видно, ця схема передбачає роздільне зберігання накопичувачів N1 і N2 (так було і раніше, на регістрах довжиною 128біт

Використання YMM регістрів робить старші і молодші половинки регістрів незалежними для блоків підстановок. Це дозволяє створити два незалежних потоку розрахунків на різних блоках замін і різних ключах. Раніше так робити було не можна.

Можливості паралельного рахунку збільшенням швидкості не обмежуються, перерахую основне, що можна використовувати в чисто алгоритмічних цілях:

- По-перше, поки паралельний рахунок йде на одних і тих же ключах і блоках замін, але це не обов'язкова обмеження, можна шифрувати на унікальних ключах і блоках замін для кожного блоку.

- По-друге, у нас з'являється за один раунд одночасно 16 незалежних результатів, це еквівалентно проведення 16 раундів над одним блоком.

- По-третє, алгоритм ГОСТ 28147-89 не використовує в перетворенні накопичувач N2, його можна теж модифікувати, але не проводячи над ним математичні перетворення, а «заплутуючи» його стан в залежності від стану суміжних паралельно працюють перетворень.

Тепер спробуємо ці нові можливості надаються паралельним шифруванням 16 блоків на 16 незалежних перетворювачах реалізувати в модифікованому алгоритмі ГОСТ 28147-89.

початкові заповнення

Найкращим серед режимів шифрування є режим гамування. З точки зору паралельного рахунку він вкрай незручно реалізований в стандартах (новому і старому), тому почнемо з нього.

З 16 паралельно працюючих перетворювачів сформуємо дві абсолютно незалежні групи (потоку) по 8 перетворювачів. Незалежність досягається використанням в них різних ключів і блоків підстановки.

Відповідно у нас з'являється два різних блоку замін по 64 байта і шістнадцять чотирибайтових ключів.

На основі цих груп будемо формувати незалежні початкові заповнення перехресним методом, коли вихідна стан однієї групи стає вхідним станом для іншої групи в наступному циклі формування гами.

Найперше заповнення для груп перетворювачів, щоб не плодити нових «сутностей», будемо формувати з значень 8 ключів шифрування різних груп, відмовившись від концепції «сінхропосилкі». Будемо їх просто підставляти, кожному з 8 перетворювачів по ключу з іншої групи. Так щоб номер (n = 1 ... 8) перетворювача відповідав ключу з номером 9-n. Цими значеннями заповняться накопичувачі N1, в кожному з 16 перетворювачів.

Другий накопичувач N2 можна заповнювати номером блоку гами, відповідно він буде для всіх перетворювачів пов'язаний лінійною функцією. Номер блоку гами необхідний для того, щоб на одних і тих же ключах отримувати різні гами, що важливо для каналів передачі даних і шифрування дисків.

У цій схемі блоків даних може бути не більше 232, але розмірність самого блоку не обмежена, так що розмірність гами без повторів теж не обмежена.

Ось як це виглядає на блок схемою:

Захист від диференціального криптоаналізу

З метою захисту від диференціальних методів криптоаналізу «заплутаємо» гаму. Для цього, перед тим як стан накопичувачів виводити в гаму, виконаємо операції «перетасовки» байт накопичувачів. Щоб результат такої перетасовки не був відомий заздалегідь, будемо її виконувати в залежності від значень відповідних байт в накопичувачах. Найпростіше виконати операції зборки мінімальних і максимальних значень відповідних байт в першому і другому потоці.

Ось як це виглядає на блок схемою:

Начебто громіздко на схемах, але в коді все просто, ось як формуються початкові заповнення і заплутується гамма коді:

; ///////////// початкові заповнення і запис результату в буфер гами

vperm2i128 ymm6, ymm6, ymm6,001h; обміняти верхні і нижні блоки N1
vperm2i128 ymm7, ymm7, ymm7,001h; обміняти верхні і нижні блоки N2
vpminsb ymm8, ymm6, ymm7; зібрати мінімальні значення
vpmaxsb ymm9, ymm6, ymm7; зібрати максимальні значення
vmovupd [rsp + 040h], ymm8; в гаму
vmovupd [rsp + 060h], ymm9; в гаму

У цьому коді спочатку міняються місцями значення в групах накопичувачів з верхньої та нижньої частини 256бітних регістрів. Потім виконується заплутування на командах виділення мінімальних і максимальних байт в еквівалентних позиціях гами обох потоків. В кінці отримані значення записуються в буфер гами.

Схему формування початкового заповнення і видачі даних в гамму можна звичайно ускладнювати і модифікувати. Дана схема описана виключно для демонстрації самого принципу використання паралельності в криптоалгоритм.

Ключова схема.

Можна ускладнити ключову схему в рамках вже існуючої архітектури перетворення. Зараз в кожному раунді подаються на перетворювачі (їх 8 штук у кожному з двох потоків) однакові ключі.

Для ускладнення можна:

- У кожному потоці мати власний набір з 8ключей.

- Подавати в перетворювачі ключі відповідно до номером перетворювача і перебирати їх потім циклічно.

Ось як це виглядає на схемі:

Ця схема перетворює кожен з 16 перетворювачів в повністю автономний функціональний блок, що видає свій унікальний результат навіть на однакових початкових заповненнях і однакових ключах.

Для цієї операції ніяких нових процесорних команд при реалізації вводити не треба, просто змінювати порядок структури блоків ключів в оперативній пам'яті.

Введення операції «невизначеності» стану накопичувачів

І так, для посилення схеми формування первинних заповнень, з 16 паралельно працюючих перетворювачів зроблені два незалежних потоку по 8 паралельно працюють перетворювачів.

Далі будемо розглядати роботу тільки однієї з цих груп по 8 перетворювачів, маючи на увазі, що обидві групи працюють однаково, тільки використовують різні ключі, блоки замін і початкові заповнення.

У нас в результаті одного раунду в групі з 8 перетворювачів обчислюються відразу 8 нових значень накопичувачів N1 і N2, їх можна «перетасувати». Придумувати нових операцій не будемо, є перевірена підстановка в блоках замін, її і використовуємо.

Зробимо частина підстановок не статичною, а динамічними. Іншими словами, самі накопичувачі N1 і N2 стануть динамічними блоками замін. Блоки накопичувачів N1 і N2 при паралельному рахунку займають чотири регістри по 128 біт. Саме стільки ж регістрів використовується для блоків замін в основному циклі.

Для реалізації динамічних блоків замін потрібно підставити в перетворення замість регістрів зі статичними блоками замін, регістри зберігання значень накопичувачів N1, N2 попереднього раунду. Будемо цю операцію робити через раз, в одному раунді будемо використовувати штатні статичні блоки замін, а в наступному будемо використовувати динамічні блоки замін.

Таким чином у нас з'являється операція яка підставляє в тетради восьми накопичувачів N1 абсолютно непередбачуваними значення, ця операція незворотна, таким перетворенням можна тільки гамміровать і обчислювати Хеш функцію.

Якщо залишатися в рамках оборотності алгоритму, то в динамічних замінах потрібно використовувати тільки накопичувачі N2.

ефект синергетики

Реалізація динамічних блоків замін крім задоволення вимог постквантовой криптографії має ще одну позитивну властивість. Вона інтегрує методом нелінійної заміни 8 циклів шифрування на різних ключах.

Це еквівалентно тому, що за один раунд виконується відразу дев'ять незалежних раундів перетворень ...

Для виконання умови еквівалентності, потрібно в кожному перетворювачі використовувати різні ключі, у нас їх 8, стільки ж перетворювачів. Отже, перетворювачі повинні виконувати тотожні раунди на різних ключах і перебирати їх послідовно.

Це вимагає застосування ключовий схеми, про яку вже йшлося вище.

Виконання одного раунду, на динамічних блоках підстановок еквівалентно, 9 раундів вихідного перетворення, тому можна зменшити кількість раундів в операції гамування. Розмінюватися на дрібниці не будемо, зменшимо їх в чотири рази, до 8, це буде в еквівалентній схемі дорівнює 40 раундів послідовного рахунки початкового варіанту.

В результаті, підвищуючи криптостойкость ми ще в чотири рази збільшуємо швидкість перетворення, на мій погляд це і є «красиве» рішення.

Використання накопичувачів N2 для «заплутування» стану статичним методом

Але навіть це не межа, зробимо не просто «красиво», а «дуже красиво» ...

У нас простоюють під час перетворень заміни і зсуву накопичувачі N2, і є незадіяні виконавчі пристрої в складі процесора. Цей потенційний ресурс теж можна використовувати.

Введемо ще одну нелінійну операцію перетворення накопичувачів N2, і будемо її виконувати на тлі перетворення накопичувачів N1, це не призведе до збільшення часу виконання.

Найпростішим перетворенням, може бути (як приклад), така статична перестановка:

Тут «збирати заново» байти накопичувачів N2 двох незалежних потоків на статичній схемою перестановки. У кожному з потоків власна схема збірки. Для цієї операції потрібно всього одна процесорна команда.

У першому потоці збираються байти відповідно до номерами накопичувачів.

У другому потоці суміжні накопичувачі обмінюються відповідними байтами.

Статичні заміни можна використовувати в оборотних алгоритмах, але в більш складному (динамічному) варіанті, оборотність втрачається.

Використання накопичувачів N2 для «заплутування» стану динамічним методом

Ускладнимо операцію, будемо виконувати динамічні перестановки, з двома відмінностями від статичного перетворення:

- Використовувати в якості індексу перестановки будемо тетради з кожного байта накопичувачів N2.

- Індекси кожного з накопичувачів N2 використовуються для перестановок байт в іншому накопичувачі.

Цю операцію будемо проводити під час раунду зі статичними блоками замін, які описані раніше, щоб не дублювати динамічні підстановки в накопичувачах N1.

Ось як реалізація цього перетворення виглядає на командах процесора:

; ////////// модифікація накопичувачів N2
vpand ymm5, ymm1, [rbx + 40h]; скинути старші тетради в байтах
vpand ymm8, ymm7, [rbx + 40h]; скинути старші тетради в байтах
vpshufb ymm7, ymm7, ymm5; перемішати байти 1блок накопичувачів
vpshufb ymm1, ymm1, ymm8; перемішати байти 2блока накопичувачів

В еквівалентній схемі введення такої операції відповідає 6 раундів вихідного перетворення. Відповідно на 8 раундів в еквівалентній схемі виходить 24 раундів вихідного перетворення. Сумарно обидва методи дають 36 + 24 = 60 раундів, це більш ніж достатньо для стійкості проти традиційних методів криптоаналізу, і досить для вимог криптостойкости постквантовой криптографії, при цьому швидкість гамування на стенді виходить 3.8Гбайт / сек для одного процесорного ядра частотою 4гГерца.

Куди більше?

Інжекція випадкових байт

Більше не треба, краще менше, але краще.

Зробимо так, щоб недолік динамічних блоків підстановок (їх статистична слабкість) компенсувалася инжекцией випадкових байт. Це до речі частково усуне «ахіллесову п'яту» Магми, - зошитів підстановки.

Суть операції проста, перед операцією підстановки запам'ятаємо значення накопичувачів N1, а після підстановки і зсуву порівняємо отримане значення зі збереженим.

Якщо якісь байти збіглися (через слабкість поточної підстановки) то замінимо цей байт на взятий з рандомних байтового блоку випадковим чином.

Рандомних блоком буде спеціальний стандартизований блок розміром в 256 байт, підготовлений заздалегідь.

Випадковість вибірки з нього організуємо через зсув, величина якого залежить від попереднього накопиченого числа збігів.

Ось як це реалізується в коді:

; ///////// видалення повторів
vpcmpeqb ymm3, ymm3, ymm7; порівняти запомненное і поточний стан
vpblendvb ymm7, ymm7, [rcx + r14], ymm3; замінити збіглися байти
vpmovmskb r15, ymm3; маска збігів для 32байт
popcnt r15, r15; число збігів
add r14, r15; накопичити число збігів
and r14,0ffh; закільцювати адресацію буфера

Даний варіант операції не застосовний до оборотним алгоритмам, але змінивши порядок вибірки випадкових байт можна сконструювати і оборотний алгоритм.

Зрозуміло що ця операція збільшує час виконання (близько 15%), але при досягнутих швидкостях це вже не суттєво. «Ціна питання», - в середньому виходить інжекція одного випадкового байта на 128 байт гами, на мій погляд це те, що треба ...

На завершення

В автомобілебудування є поняття «концепт», це щось таке, що увібрало в себе суму інноваційних рішень і використовується для їх обкатки в тестовому режимі.

Ось і в ПостКвантовой криптографії з'явився такий «концепт», поки він працює в вигляді тестового прикладу, але це тільки поки ...

Ще раз перелічу інновації цього «концепту»:

- Введено динамічні блоки замін, що складаються з раундовий значень накопичувачів N1 і N2.

- Введена схема компенсації слабкості блоків динамічних замін і інжекції випадкових байт.

- Введена нелінійна функція перетворення значень накопичувачів N2.

- Введена нелінійна функція формування початкового заповнення накопичувачів N1 і N2.

- Введена операція захисту від диференціальних методів криптоаналізу.

В результаті, практично не змінивши принципів самого алгоритму вдалося перейти на збільшену в два рази розмірність ключів (16 чотирибайтових ключа) і збільшену в шістнадцять разів розмірність вхідних векторів (128 байт замість 8).

Криптографи і криптоаналитики ідеї використання паралелізму в криптоперетворень сприйняли м'яко кажучи прохолодно ...

Причини очевидні.

Але вони нам не указ, і концепт ПостКвантового шифратора не залишиться тільки на папері. В даний час розробляється повнофункціональна програма з його реалізацією (система архівації).

Так що їжа для розуму принаймні у «практикуючих» криптоаналітиків скоро з'явиться в примусовому порядку ...