Функція губки

В криптографії функція губки (англ. sponge construction або sponge function) належить до класу алгоритмів із кінцевим внутрішнім станом, на вхід якого надходить двійковий рядок довільної довжини, і який повертає двійковий рядок також довільної довжини f:{0,1}^n →{0,1}^*. Губка є узагальненням як геш-функцій, так і потокових і блочний шифрів, генераторів псевдовипадкових чисел, що мають довільну довжину вхідних даних.

Структура

Губка — це ітеративна конструкція для створення функції з довільною довжиною на вході й довільної довжини на виході на основі перетворень f. Губка має внутрішній стан S — з даними фіксованого розміру b (біт). При цьому дані розділені на 2 частини — перша S1 розміру r, а друга S2 — розміру c. Значення r називається бітовою швидкістю, а значення з — потужністю => b = r + c.

На фазі ініціалізації, блок даних розміру b заповнюється нулями, а вхідні дані M розбиваються на блоки розміру r. Подальша робота губки проводиться в 2 етапи:

* У фазі «вбирання» (англ. absorbing), виконується операція XOR чергового блоку вихідного повідомлення з першою частиною стану S1 розміру r (біт), решта S2 стану ємністю c залишається недоторканою. Результат поміщається в S1, а потім стан S обробляється функцією f — багатораундовою безключовою псевдовипадковою перестановкою, і так повторюється до вичерпання блоків вихідного повідомлення.

* У фазі «вичавлювання» (англ. squeezing), стан S подається на функцію f, після чого частина S1 подається на вихід. Ці дії повторюються, поки не буде отримана послідовність потрібної довжини (наприклад, довжини геша).

Останні біти c залежать від вхідних блоків лише опосередковано й не виводяться в ході фази «вичавлювання» (squeezing).

Застосування

Генератор псевдовипадкових чисел, оснований на функції губки.

Моделювання ГПВЧ із змінними вхідними даними

Визначимо ГПВЧ із змінними вихідними даними як об'єкт зі станом, який підтримує два типи запитів, в будь-якому порядку:

• Запит подачі, feed (σ) — подає початкове значення, що складається з непорожніх рядків σ ϵ ${\displaystyle Z_{2}^{+}}$, в стан ГПСЧ;
• Запит прийняття, fetch (l) — доручає ГПСЧ повернути l біт.

Тоді вихідний матеріал (англ. seeding material), що подається на вхід генератора — це конкатенація σ, отриманих у всіх запитах подачі.

Неформально, вимоги до ГПВЧ із змінними вихідними даними можуть бути визначені наступним чином: По-перше, його вихід (тобто відповіді на запити подачі) повинен залежати від усіх вихідних матеріалів. По-друге, для зловмисника, який знає вихідний матеріал, але спостерігав частину виведення, має бути неможливим зробити висновок про решту виходу.

Визначено ідеальну ГПВЧ конструкцію, яка використовує випадковий оракул. Таку конструкцію можна описати наступним чином. Вона зберігає як стан послідовність всіх запитів подачі й прийняття, які вона отримала, складаючи історію h. При отриманні запиту подачі feed (σ), вона оновлює історію підключенням цього запиту. При отриманні запиту прийняття fetch (l), вона подає випадковому оракулу рядок, який своєю чергою шифрує історію рядком і повертає біти від z до z + l-1 своєї відповіді, де z — число запитуваних біт в запиті подачі. Отже, конкатенація відповідей на запити подачі — лише відповідь випадкового оракула на одноразовий запит. Таку конструкцію можна назвати режимом, який зберігає історію, з функцією шифрування e (h). Визначення режиму із збереженням історії, отже, сходиться до визначення цієї функції шифрування.

Так як вихід ГПВЧ повинен залежати від всього отриманого вихідного матеріалу, функція e (h), яка шифрується, повинна бути ін'єктиною із вихідним матеріалом. Іншими словами, для будь-яких двох послідовностей запитів з різним вихідним матеріалом, два відображення e (h) повинні бути різні. Це явище називається повнотою вихідного матеріалу (англ. seed-completeness). У функції шифрування з повним вихідним матеріалом на запит прийняття, будуть видані різні відповіді на різні вхідні рядки. Звідси випливає, що ГПВЧ повертає незалежні біти. Таким чином, пропонується наступне визначення ідеального ГПВЧ із змінними вхідними даними.

Ідеальний ГПВЧ із змінними вхідними даними — це режим, який зберігає історію, називається випадковим оракулом, з функцією шифрування e (h) з повним вихідним матеріалом.

Створення ГПВЧ з використанням функції губки

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

При побудові функції губки, вхідне повідомлення m ϵ ${\displaystyle Z_{2}^{*}}$ має бути поділено на блоки з r бітів і заповнене. Функція, яка робить це позначається так: p (m) функцію, припускається, що ця функція додає тільки біти після m. Якщо є потреба повторно використовувати стан губки, для якої вхідним рядком було повідомлення m1 і для якої вихідні біти були «вичавлені» при l> 0, то стан функції губки в цій точці такий, якщо б часткове повідомлення m'1 = р(m1) || 0^{r(⌈l/r⌉-1)} було «впитано». Нульові блоки складають додаткові ітерації через фази стиснення. Перезапуск губки з цієї точки означає, що вхідним буде повідомлення m2, для якого m'1 є префіксним.

Щоб визначити ГПСЧ формально, потрібно вказати функцію шифрування e (h) з повним вихідним матеріалом, що відображає послідовність запитів подачі й прийняття. Вихід е (h) використовується в якості входу для функції губки.

На практиці ідея полягає в тому, щоб не викликати функцію губки з усією е (h) кожен раз, як отримуємо запит прийняття. Замість цього, конструкція використовує функцію губки каскадним чином, повторно використовуючи стан, як описано. Щоб дозволити повторне використання стану, функція губки е (h) повинна бути такою, що якщо h’ = h || fetch(l) || feed(σ), то p(e(h)) || 0^{r(⌈l/r⌉-1)} — префікс e(h’).

Щоб зв'язати конструкцію з практичною реалізацією, необхідна конструкція з двома обмеженнями. Перше обмеження — обмеження на довжину запитів вихідного значення. Для фіксованого цілого k вимагається, щоб довжина вихідного матеріалу σв при будь-якому запиті подачі feed (σ) була така, що | p (σ) | = Kr. Іншими словами, після заповнення, вихідний матеріал покриває рівно k блоків по r біт. Друге обмеження в тому, що першим запитом повинен бути запит подачі.

Конструкція є конструкцією з урахуванням станів (stateful), якщо її стан складається з mε N біт, прийнятих з моменту останнього запиту подачі. При започаткування нового виконання функції губки, потрібно задати m = 0. Його позначено, як е рядок, відображення е (h) запитів, доданих до історії h.

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

Значення m змінено: m = m + l.

• Якщо прийшов запит feed (σ): Формально цей запит подачі викликає запит до функції губки з е в якості вхідних даних. Якщо це не перший запит, то е оновлено тільки до останнього запиту подачі. Таким чином, результати запитів отримання з моменту останнього запиту подачі повинні бути включені в е, як якщо б е раніше «вбиралася». Спочатку е стає рівною p (e), щоб імітувати заповнення при перемиканні на фазу «вичавлювання» після попереднього запиту подачі. Тоді ⌈m \ r⌉ -1 блоків по r нулів додаються до e для обліку додаткових викликів функції f на випадок повторних запитів подачі. Тепер m скидається: m = 0. (Це частина впливає тільки на ті — нічого не повинно змінитися у виконанні).

Потім «всотується» σ. Формально це виражається шляхом додавання σ до е.

Нарешті, виконання перемикає функцію губки на фазу «вичавлювання». Це означає, що «ввібрані» дані повинна бути заповнені й перестановка f застосована до стану. (Формально, це не змінює е, бо заповнення за визначенням виконується при перемиканні на фазу віджимання).

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

Обмеження першого запиту, що є запитом подачі, може бути видалено, бо не має сенсу генерувати псевдовипадкові біти без першої подачі вихідного матеріалу. Якщо перший запит — це прийняття, то виконання відразу заповнює (символом нового рядка) вхід, перемикає функції губки на фазу «вичавлювання» і виробляє вихідні біти за допомогою «вичавлювання». Формально в наступному запиті подачі, це повинно бути враховано в е привласненням е значення р (порожній рядок) ||0^r([m=r]-1).

Реалізації алгоритму

• Keccak

Примітки

1. Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007.
2. Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив
3. Boutin, Chad (2 жовтня 2012). NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. Процитовано 4 жовтня 2012.

Посилання

1. Sponge Functions Ecrypt Hash Workshop 2007.
2. Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив
3. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition