Skein

Skein
Загальні
РозробникиБрюс Шнайер, Стефан Лакс, Нільс Фергюсон, Даг Вайтінг, Міхір Белларе, Тадайоші Кохно, Джон Каллас, Джессі Вокер
ПопередникиThreefish
Сертифікаціяфіналіст SHA-3
Деталі
Раундів72
Функція змішування Skein

Skein (від англ. моток) — криптографічна хеш-функція змінної розрядності, розроблена в 2008 році групою вчених під керівництвом Брюса Шнаєра, разом з Нільсом Фергюсоном, Стефаном Лаксом, Дугом Уайтінгом, Мічіхіро Белларе, Тадайоші Коно, Джоном Калласом і Джессі Уокером. Алгоритм ґрунтується на конструкції Меркла-Дамгарда, з використанням в якості функції стиснення настроюваного блокового шифру Threefish за схемою Матіса-Мейєра-Осеаса[1].

Історія

Skein був розроблений групою авторів: Брюс Шнайер, Нільс Фергюсон, Стефан Лакс, Даг Вайтінг, Міхір Белларе, Тадайоші Коно, Джон Каллас і Джессі Вокер.

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

Skein був кандидатом на конкурс майбутнього стандарту SHA-3, дійшовши до фінального етапу в грудні 2010 року.

Алгоритм Skein та його еталонна реалізація були надані у відкритий доступ[2].

Функціональність

Skein засновано на налаштовуваному блоковому шифрі Threefish, стиснутому за допомогою режиму ланцюгових ітерацій з єдиними блоками (UBI), варіанту хеш-функції Матьяса-Мейєра-Осеаса, з використанням додаткової системи аргументів для забезпечення гнучкості при знижених накладних витратах. Спеціально для Skein було розроблено метод побудови унікальної блокової ітерації (UBI), який замінив раніше поширену конструкцію Меркла-Дамгарда. UBI функціонує аналогічно до конструкції HAIFA. Повідомлення розширюється та розділяється на блоки, які обробляються послідовно. Кожен блок повідомлення разом зі значенням конкатенації та деякими даними управління, включаючи лічильник для вже оброблених бітів повідомлення, подається у функцію стиснення, яка надає наступне значення конкатенації. Остаточне значення конкатенації фіналізується ще одним викликом функції стиснення, що призводить до хеш-значення.

Threefish, що лежить в основі Skein має дуже просту структуру і може бути використаний для заміни алгоритмів блочного шифрування, будучи швидким і гнучким шифром, що працює в довільному режимі шифрування. Сам Threefish не використовує S-блоки, натомість покладається на комбінації інструкцій XOR, складання і циклічного зсуву. Нелінійність Threefish повністю зумовлена комбінацією операцій додавання та виключаючих АБО; вона не використовує S-блоки. Функція оптимізована для 64-бітних процесорів, а в статті Скейна визначено додаткові функції, такі як рандомізоване хешування, паралелізуване деревоподібне хешування, потоковий шифр, персоналізація та функція виведення ключа.

Блок повідомлення вводиться як відкритий текст, а значення конкатенації, що містить дані управління, вводиться як ключ/налаштування. Наступне значення конкатенації генерується шляхом XOR між відкритим текстом і шифротекстом. Threefish шифрує за 72 раунди з розміром блоку 256 або 512 бітів. Для розміру блоку 1024 біти використовується 80 раундів.

Хеш функція Skein виконана як універсальний криптографічний примітив, на основі блочного шифру Threefish, що працює в режимі UBI-хешування[2]. Ядро Threefish базується на функції MIX, яка перетворює 2 64-бітних слова за допомогою одного додавання, обертання на константу та XOR. Режим ланцюжка UBI поєднує вхідне значення ланцюжка з вхідним рядком довільної довжини та створює вихідний результат фіксованого розміру. Skein підтримує розміри внутрішнього стану 256, 512 і 1024 біт і розмір вихідного блоку до 2 64 −1 біт. Автори стверджують, що на ПК з 64-бітним процесором Intel Core 2 Duo потрібно 6.1 тактів на байт для будь-якого розміру вихідного блоку[3][2].

З числа кандидатів на SHA-3 Skein входить в п'ятірку найшвидших, проте є лідером лише в 64-розрядному варіанті, який перевершує за швидкісними характеристика 32-розрядний у більш ніж чотири рази. Це пояснюється тим, що автори спочатку орієнтувалися на оптимізацію під 64-розрядні процесори[4].

Skein-512 може бути реалізована з використанням всього 200 байт пам'яті, Skein-256 — 100 байт, що оптимально для апаратної реалізації алгоритму в смарт-картах[5].

Як заявляють автори, хеш-функція Skein на поширених процесорах працює в середньому вдвічі швидше SHA-512, Threefish вдвічі швидше AES.

Skein захищена від нових видів атак на хеш-функцій — підбору подовжених повідомлень і псевдоколізій.

Криптоаналіз

У жовтні 2010 року було опубліковано атаку, яка поєднує ротаційний криптоаналіз з атакою відскоку. Атака виявляє ротаційні колізії для 53 з 72 раундів у Threefish-256 та 57 з 72 раундів у Threefish-512. Вона також впливає на хеш-функцію Skein[6]. Це продовження попередньої атаки, опублікованої в лютому, яка пробиває 39 та 42 раунди відповідно[7].

Команда Skein змінила ключову константу розкладу для третього раунду змагання хеш-функцій NIST, щоб зробити цю атаку менш ефективною, хоча вони вважають, що хеш все ще був би безпечним без цих налаштувань[2].

На другій конференції SHA-3 Дмитро Ховратович, Івіца Ніколіє та Крістіан Рехбергер продемонстрували потенційну вразливість Threefish та функції стиснення Skein[8]. Згодом автори внесли незначні корективи до алгоритму[9].

Приклади хеш-функцій Skein

Хеш-значення порожнього рядка. 

Skein-256-256("")
c8877087da56e072870daa843f176e9453115929094c3a40c463a196c29bf7ba
Skein-512-256("")
39ccc4554a8b31853b9de7a1fe638a24cce6b35a55f2431009e18780335d2621
Skein-512-512("")
bc5b4c50925519c290cc634277ae3d6257212395cba733bbad37a4af0fa06af41fca7903d06564fea7a2d3730dbdb80c1f85562dfcc070334ea4d1d9e72cba7a

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

Skein-512-256("The quick brown fox jumps over the lazy dog")
b3250457e05d3060b1a4bbc1428bc75a3f525ca389aeab96cfa34638d96e492a
Skein-512-256("The quick brown fox jumps over the lazy dog.")
41e829d7fca71c7d7154ed8fc8a069f274dd664ae0ed29d365d919f4e575eebb
Skein-512-512("The quick brown fox jumps over the lazy dog")
94c2ae036dba8783d0b3f7d6cc111ff810702f5c77707999be7e1c9486ff238a7044de734293147359b4ac7e1d09cd247c351d69826b78dcddd951f0ef912713
Skein-512-512("The quick brown fox jumps over the lazy dog.")
658223cb3d69b5e76e3588ca63feffba0dc2ead38a95d0650564f2a39da8e83fbb42c9d6ad9e03fbfde8a25a880357d457dbd6f74cbcb5e728979577dbce5436

Примітки

  1. ↑ Эдуардовна, Авезова Яна (2015). Современные подходы к построению хеш-функций на примере финалистов конкурса SHA-3. Вопросы кибербезопасности (3 (11)): 60—67. ISSN 2311-3456.
  2. ↑ а б в г Ferguson та ін. (1 жовтня 2010). The Skein Hash Function Family (PDF). Архів оригіналу (PDF; 479 kB) за 24 серпня 2014. Процитовано 15 грудня 2010.
  3. ↑ Now From Bruce Schneier, the Skein Hash Function. Slashdot. 31 жовтня 2008. Процитовано 31 жовтня 2008.
  4. ↑ Engineering comparison of SHA-3 candidates. Архів оригіналу за 27 червня 2012. Процитовано 18 червня 2012. [Архівовано 2012-06-27 у Wayback Machine.]
  5. ↑ info / about About the Skein Hash Function Family[недоступне посилання з червня 2019]
  6. ↑ Dmitry Khovratovich; Ivica Nikolic; Christian Rechberger (20 жовтня 2010). Rotational Rebound Attacks on Reduced Skein. Cryptology ePrint Archive.
  7. ↑ Dmitry Khovratovich & Ivica Nikolić (2010). Rotational Cryptanalysis of ARX (PDF). University of Luxembourg. Архів оригіналу (PDF) за 26 січня 2013. Процитовано 25 жовтня 2010.
  8. ↑ More Skein News. Schneier on Security (амер.). 1 вересня 2010. Процитовано 6 січня 2026.
  9. ↑ Skein News. Schneier on Security (амер.). 15 вересня 2009. Процитовано 6 січня 2026.

Література

Посилання

This article is issued from Вікіпедія. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.