#hash #hashmap #hashtable #hashset #hashcode
#хэш #hashmap #хэш-таблица #hashset #хэш-код
Вопрос:
Если установить начальное значение хэш-таблицы во время изменения размера или создания таблицы на случайное число, предотвратит ли это DDoS-атаки на такую хэш-таблицу или, зная алгоритм хэширования, злоумышленник все равно легко обойдет начальное значение? Что, если алгоритм использует хэш-функцию Пирсона со случайно сгенерированными таблицами, неизвестными злоумышленнику? Требуется ли для такого хэша таблицы начальное значение или оно достаточно безопасно?
Контекст: я хочу использовать хеш-таблицу на диске для базы данных ключ-значение для моего игрушечного веб-сервера, где ключи могут зависеть от пользовательского ввода.
Комментарии:
1. Пожалуйста, уточните, что вы подразумеваете под «начальным значением» хэш-таблицы. В общих хэш-таблицах нет начальных значений, хотя в некоторых конкретных хэш-функциях есть то, что они называют начальным значением. В любом случае, остальная часть хэш-функции также имеет решающее значение для определения, достаточно ли она устойчива к атакам хэш-флудинга.
2. Обычно большинство хэш-функций имеют начальные значения, как и генераторы случайных чисел. Фактически, вы можете превратить любую хэш-функцию в генератор случайных чисел. И генератор случайных чисел тоже можно превратить в хэш-функцию, если вы вводите значение, которое нужно хэшировать. Под начальным значением хэш-таблицы я подразумевал начальное значение, выбранное при инициализации или во время изменения размера. Т.Е. Можно попробовать несколько начальных значений, выбирая то, которое дает меньше столкновений, на случай, если злоумышленник исследует таблицу.
3. siphash был специально разработан для этого.
Ответ №1:
Существует несколько подходов для защиты вашей хэш-подсистемы от атаки «неблагоприятного выбора», наиболее популярным из них является универсальное хеширование, где хэш-функция или ее свойство выбираются случайным образом при инициализации.
В моем собственном подходе я использую ту же хэш-функцию, где каждый символ добавляется к результату с нелинейным смешиванием, зависящим от случайного массива uint32_t[256] . Массив создается во время инициализации системы, и в моем коде это происходит при каждом запуске, путем чтения /dev/urandom . Смотрите мою реализацию в программе EmerSSL с открытым исходным кодом. Вы можете позаимствовать всю эту реализацию хэш-таблицы или только хэш-функцию.
В настоящее время моя хэш-функция из указанного источника вычисляет два независимых хэша для алгоритма поиска с двойным хешированием.
Существует «уменьшенная» хэш-функция из источника, чтобы продемонстрировать идею нелинейного смешивания с массивом S-блоков «
uint32_t S_block[0x100]; // Substitute block, random contains
#define NLF(h, c) (S_block[(unsigned char)(c h)] ^ c)
#define ROL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
int32_t hash(const char *key) {
uint32_t h = 0x1F351F35; // Barker code * 2
char c;
for(int i = 0; c = key[i]; i ) {
h = ROL(h, 5);
h = NLF(h, c);
}
return h;
}
Комментарии:
1. В чем смысл использования Barker? Разве это не просто для обнаружения ошибок передачи сигнала?
2. Был ли проведен какой-либо анализ, когда кто-то пытался найти атаку на хэш-флуд против этого?
3. О коде Баркера: этот код имеет минимальную самокорреляцию по сравнению с циклическим сдвигом. Поскольку хэш-функция использует циклический сдвиг, мне нужно создать максимальное значение расширения для входных ключей. Как вы видите, код Баркера вернется к самонастроению после 65 итераций (5×13), этого более чем достаточно, в любом случае, после 65 итераций будет добавлено много значений из S-блока.
4. О
hash flooding attackнас. Я думаю, вы предполагаетеmuticollision, правильно? Я разработал эту хэш-функцию для сильного сопротивления этой атаке. Как вы видите, он использует криптографический S-блок, значение которого используется для нелинейного смешивания следующего символа с хеш-значением. Таким образом, чтобы выбрать эффективную мультиколлизию, необходимо знать значение S-блока. Это 2K случайных байтов (в моем коде, считанных из /dev/urandom), так что это невозможно угадать. Если вы не согласны — пожалуйста, попробуйте создать пару сталкивающихся ключей, опубликуйте здесь, и после этого мы запустим хэш (который получает 2K из /dev / urandom), и мы увидим результат.5. Ну, я сравниваю это с siphash и критериями проектирования, используемыми siphash. siphash использует очень консервативное предположение: злоумышленник может наблюдать хэш-выходные данные для любых входных данных, которые он выбирает. siphash, похоже, сохраняется в этом предположении, но ваш хэш-нет, поскольку относительно легко восстановить всю таблицу S-блоков, содержащую не более 256 хэшей. Тем не менее, я немного скептически отношусь к достоверности этой модели. Я хотел бы увидеть объяснение того, почему разумно разрешить злоумышленнику наблюдать за хэш-выводами по его выбору.