Узагальнена модель стійкого паралельного хешування

Abstract

Одна з вимог, що найбільш часто висувається до процесу обчислення хеш-значення, є його швидкість. Очевидно, що при цьому основна вимога до хешування, стійкість, повинна залишатись сталою. В процесі криптоаналізу хешування була розроблена атака, що базується на "парадоксі дня народження". Відповідно до цього парадоксу знаходження колізій для n-розрядного хеш-значення можливо здійснити за 2 в степені n/2 ітерацій. Для того, щоб досягти бажаної стійкості до цієї атаки, необхідно збільшити розрядність вихідного хеш-значення вдвічі. Остання процедура є незручною з точи зору швидкісних характеристик хешування, тому було запропоноване "каскадування", тобто розпаралелення процесу обчислень хеш-значень та конкатенація результатів на останній ітерації. Такий підхід зняв питання стосовно швидкості хешування до 2004 року, коли Жукс винайшов атаку з використанням мультиколізій . Відповідно актуальною задачею є знаходження конструкції, тобто математичної моделі, хешування, яка б дозволила паралельно обчислювати хеш-значення за допомогою різних процесорів та отримувати результуюче хеш-значення шляхом їх конкатенації.