Главная

Адаптивное хеширование

2014-11-21 в 8:34, admin, рубрики: информационная безопасность, криптоанархизм, криптография, хеш-функции, хеширование

Preview. Эта идея уже очень давно мучала мой воспаленный криптограффией мозг.
TL;DR идея хеш функции которая генерируется на основе входных данных

Для начала стоит разобратся с базовыми понятиями.

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

Хеш-функция – необратимая функция преобразования входных данных в результате которой для всех входных параметров(ключей) создается множество хеш-код(значений), которое не является линейным (т.е. значения хеш-кодов для разных аргументов может быть одинаково). Такая функция подразумевает потерю входных данных, тем самым образуя нелинейность множества хеш-кодов.

Обратимая функция — это функция, которая принимает каждое своё значение в единственной точке области определения. Необратимая же принимает несколько значений в точке области определения.

Пример простой необратимой функции:

Mark. Эта функция является обратимой на отрезке [0, +inf]

Криптографическая хеш-функция – это хеш-функция удовлетворяющая трем требованиям:

Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти аргумент x, для которого HASH (x) = m.
Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого HASH(N) = HASH(M).
Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений (M,M′), имеющих одинаковый хеш.

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

uint8_t const shift = 3;
uint8_t const addition = 7;
uint8_t i = 0;
for(; i < 255; ++i) {
    printf("%d;%d n", i , (unsigned char)(((i << shift) + addition) ^ (i >> shift)) );
}
printf("%d;%d n", i , (unsigned char)(((i << shift) + addition) ^ (i >> shift)) );

Коллизией хеш-функции называю набор аргументов x, y, при которых HASH(x) = HASH(y)
У приведенной выше функции можно увидеть множество коллизий. (Если провести мысленную горизонтальную линию на графике, аргументы соответсвующие точкам пересечения этой мысленной линии с кривой функции и будут коллизиями, и их в среднем будет 17, т.е. одному значению хеша соответсвует 17 аргументов, это и есть коллизии)

Обычно в криптографии из-за очень большой области значений 2^128 – 2^512(и более). долго построить такой график, т.е. долго найти полную таблицу функций, и тем самым долго найти коллизии после сопоставления значений таблицы. Отсюда в правильно математически-построенных хеш функциях и появляется стойкость к трем требованиям такой функции.
Например для 65536 значений график также отсанется пилообразным, т.е коллизий станет больше, но они будут более сложными.

Mark. Если бы возможно было за довольно малое время (хотя бы жизни человека) с существующим конечным автоматом найти таблицы соответствий довольно больших входных данных и результатов функций (2^512 и более) и сохранить их, то криптография умерла бы как наука, и тут бы на ее место пришла чистая статистика. Т.е. любые данные после шифрования или хеширования можно было бы угадать из возможных множеств с определенной вероятностью, а иногда и точно, зная например, что это должны быть ascii слова. Поэтому все выводы о стойкости современных криптоалгоритмов – это умозрительные выводы криптографов (математиков) о характере функций.

Адаптивное хеширование - 4

Универсальным хешированием (англ. Universal hashing) называется хеширование, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму.

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

Допустим в хеш-функции существует подпрограмма(блок функции) подстановки/перестановки отвечающий за однозначную/неоднозначную подмену байта или полубайта. Также любые константные таблицы или отдельные константы. Идея в том, чтобы изменять константы или таблицы в зависимости от данных (а в идеале хранить отдельно сгенерированные и выбирать между ними).

Допустим храним все таблицы подстановки байт – это 256 возможных значений функции, т.е. это таблица 256 х 256 = 65536 байт (64 kb), допустим в исходном значении есть байт, который отвечает какую таблицу выбрать, это 256 возможных таблиц и 256 х 65536 – 16 777 216 (16 Mb) (для таблиц полу-байтов или октетов это значение будет в n раз меньше). Это довольно много, например на старых машинах такую штуку не запустишь с сохраненными таблицами. Зато это быстро. Для старых машин – вариант генерировать таблицу, если она генерируема.

Для пущей неопределенности добавим пункт о том, что байт выбора таблицы тоже будет выбиратся. Например первый байт функции отвечает за то, какой байт будет выбран в качетсве порождающего байта для таблицы (тут маленький казус, по факту получается два порождающих байта – отступ от начала сообщения, плюс значение байта)

Mark. Более изысканные схемы генерации алгоритма или его частей можно отнести к вопросам самомодификации и колмогоровской сложности, о чем можно написать не одну статью а целые полки книг.