Перестановки

thesz — 14.12.2023 Есть табличное вычисление хэш-функций. Очень простая вещь: для каждого i-го "символа" сообщения (байта, нибла и так далее) используется i-я табличка преобразований из символов в хэши. Таблички строятся случайным образом.

Это позволяет переставлять любые два значения в любой табличке, не меняя свойств алгоритма. Это можно делать неоднократно.

Если мы реализуем табличное вычисление хэшей с помощью побитного разрезания (bit slicing) или анализируем какую-то обратную задачу с помощью преобразования в КНФ (логическую схему), то таблицы "синтезируются" в логические выражения.

Если мы переставляем местами значения в таблицах в процессе вычислений, такой синтез будет весьма затруднён, если вообще останется практичным. Даже одна перестановка и то будет сложна, что уж говорить про несколько.

Однако, перестановки могут влиять на свойства алгоритма. Например, перестановки значений в S-таблицах DES, обычно, приводили к ослаблению его стойкости. Но там довольно интересная структура была - вход был шире выхода и, по своей сути, S-таблицы выполняли ещё и распространение изменений. Если я всё правильно понимаю, то условие "выход так же широк, или шире, чем вход," может быть довольно важным в устойчивости.

PS
Такой трюк может усилить и алгоритмы вычисления криптосумм паролей, основанные на использовании пропускной способности памяти. Поменять два значения из нескольких миллионов ничего не стоит, а размен производительности на память уже будет потерян.

Оставить комментарий

Популярные посты:

• Ранее
• Архив