Лучший алгоритм для хеширования числовых значений?
В Вашем файле меню или w/e Вы помещаете:
<? require 'auth.php' ?>
<ul>
<li><a href="">Home</a></li>
<li><a href="">Products</a></li>
<? if( loggedin() ): ?><li><a href="">Secret area</a></li><? endif; ?>
</ul>
Затем на страницах, которые требуют, автор просто делает это:
<?php
require 'auth.php';
require_login();
?>
Где auth.php может содержать:
<?php
function loggedin(){
return isset( $_SESSION['loggedin'] );
}
function require_login(){
if( !loggedin() ){
header( 'Location: /login.php?referrer='.$_SERVER['REQUEST_URI'] );
exit;
}
}
?>
8 ответов
На вопросы безопасности все ответы лежат в континууме от наиболее безопасного до наиболее удобного . Я дам вам два ответа, один очень надежный и один очень удобный. Учитывая это и объяснение каждого из них, вы можете выбрать лучшее решение для вашей системы.
Вы заявили, что вашей целью было сохранить это значение вместо фактической кредитной карты, чтобы вы могли позже узнать, используется ли тот же номер кредитной карты. еще раз. Это означает, что он должен содержать только номер кредитной карты и, возможно, единообразную соль. Включение CCV, даты истечения срока действия, имени и т. Д. Сделает его бесполезным, поскольку его значение может отличаться с тем же номером кредитной карты. Таким образом, мы предположим, что вы добавляете ко всем номерам своих кредитных карт одно и то же значение соли, которое останется единым для всех записей.
Удобное решение - использовать FNV (As Предложили Зебрабокс и Ник). В результате будет получено 32-битное число, которое будет быстро индексироваться для поиска. Обратной стороной, конечно же, является то, что он позволяет использовать не более 4 миллиардов различных чисел, и на практике конфликты будут происходить намного быстрее. Поскольку у нее такой высокий уровень столкновений, атака грубой силой, вероятно, сгенерирует достаточно недействительных результатов, чтобы сделать ее бесполезной.
Безопасное решение заключается в использовании хеш-функции SHA (чем больше, тем лучше), но с несколькими итерациями. Я бы предложил порядка 10 000 штук. Да, я знаю, 10 000 итераций - это много и потребуется время, но когда дело доходит до силы против грубой силы, враг - это скорость атаки. Если вы хотите быть в безопасности, вы хотите, чтобы это было МЕДЛЕННО. SHA разработан таким образом, чтобы не иметь коллизий при любом размере ввода. Если обнаружена коллизия, хеш считается нежизнеспособным. AFAIK семейство SHA-2 все еще жизнеспособно.
Теперь, если вам нужно безопасное и быстрое решение для поиска в БД, я бы предложил использовать безопасное решение (SHA-2 x 10 КБ), а затем сохранить полный хэш в одном столбце. , а затем берем первые 32 бита и сохраняем их в другом столбце с индексом во втором столбце. Сначала выполните поиск 32-битного значения. Если это не дает совпадений, значит, у вас нет совпадений. Если он действительно дает совпадение, вы можете сравнить полное значение SHA и посмотреть, совпадает ли оно. Это означает, что вы выполняете полное двоичное сравнение (хеши на самом деле являются двоичными, но представлены только в виде строк для удобства чтения человеком и для передачи в текстовых протоколах) на гораздо меньшем наборе.
Если вас действительно беспокоит скорость, вы можете уменьшить количество итераций. Честно говоря, даже после 1000 итераций это будет быстро. Вам нужно будет сделать некоторые реалистичные выводы о том, насколько большой вы ожидаете получить базу данных, и о других факторах (скорость связи, отклик оборудования, нагрузка и т. Д.), Которые могут повлиять на продолжительность. Вы можете обнаружить, что вы оптимизируете самую быструю точку в процессе, что практически не повлияет на процесс.
Кроме того, я бы рекомендовал вам протестировать поиск по полный хэш по сравнению с 32-битным подмножеством. Большинство современных систем баз данных довольно быстрые, содержат ряд оптимизаций и часто оптимизируют для нас, делая что-то простым простым способом. Когда мы пытаемся стать умнее, мы иногда просто замедляем его. Что это за цитата о преждевременной оптимизации. . . ?
Если вам нужна безопасность, используйте криптографически безопасный хеш, например SHA-256.
Если производительность является важным фактором, я предлагаю взглянуть на запись CodeCentral Питера Ниже. Он очень хорошо работает с большим количеством элементов.
По умолчанию он использует хеш-функцию PJ Weinberger ELF . Но есть и другие.
По определению, криптографический хеш отлично подойдет для вашего случая использования. Даже если символы близки, хэш должен быть хорошо распределен.
Поэтому я советую вам использовать любой криптографический хеш (например, SHA-256) с солью.
Для некриптографического подхода вы можете взглянуть на хэш FNV , он быстрый с низкой частотой конфликтов.
В качестве очень быстрой альтернативы я также использовал этот алгоритм в течение нескольких лет и имел несколько проблем с коллизиями, однако я не могу дать вам математический анализ присущей ему надежности, но для чего он здесь стоит
= Изменить - Мой образец кода был неправильным - теперь исправлено =
В c / c ++
unsigned int Hash(const char *s)
{
int hash = 0;
while (*s != 0)
{
hash *= 37;
hash += *s;
s++;
}
return hash;
}
Обратите внимание, что «37» - это магическое число, выбранное потому, что оно простое
Лучшая хеш-функция для натуральных чисел let
f(n)=n
Нет конфликтов;)
Это похоже на случай функций деривации ключей . Взгляните на PBKDF2 .
Простое использование криптографических хэш-функций (таких как семейство SHA) даст вам желаемое распределение, но для очень ограниченного пространства ввода (например, номеров кредитных карт) их можно легко атаковать с использованием грубой силы, потому что эти хеш-алгоритмы обычно разрабатываются как можно более быстрыми.
ОБНОВЛЕНИЕ
Хорошо, безопасность не касается вашей задачи. Поскольку у вас уже есть числовой ввод, вы можете просто использовать этот номер (учетной записи) по модулю размера вашей хеш-таблицы. Если вы обрабатываете его как строку, вы действительно можете столкнуться с плохим распределением, потому что десять цифр образуют лишь небольшое подмножество всех возможных символов.
Другая проблема, вероятно, состоит в том, что числа образуют большие кластеры присвоенных (учетных) номеров с большими областями неназначенных номеров между ними. В этом случае я бы предложил попробовать сильно нелинейную хеш-функцию для распространения этих кластеров. И это возвращает нас к криптографическим хеш-функциям. Может старый добрый MD5. Просто разделите 128-битный хэш на четыре группы по 32 бита, объедините их с помощью XOR и интерпретируйте результат как 32-битное целое.
Хотя это напрямую не связано, вы также можете взглянуть на закон Бенфорда ] - это дает некоторое представление о том, почему числа обычно не распределяются равномерно.
Несколько месяцев назад мне нужно было глубоко изучить хэш-функции. Вот кое-что, что я нашел.
Вы хотите, чтобы хэш распределял попадания равномерно и случайным образом по всему целевому пространству (обычно 32 бита, но может быть 16 или 64 бита). Вы хотите, чтобы каждый символ ввода имел одинаково большое влияние на вывод .
ВСЕ простые хэши (например, ELF или PJW), которые просто перебирают строку и xor в каждом байте со сдвигом или модом, не соответствуют этому критерию по простой причине: последние добавленные символы имеют наибольший эффект.
Но есть несколько действительно хороших алгоритмов, доступных в Delphi и asm. Вот некоторые ссылки:
См. Статью доктора Доббса 1997 года по адресу burtleburtle.net/bob/hash/doobs.html
код на burtleburtle.net/bob/c/lookup3.c
Функция SuperFastHash c2004-2008, Пол Хси (он же HsiehHash)
www.azillionmonkeys.com/qed/hash.html
Исходный код Delphi (с необязательным asm) можно найти по этой ссылке:
http://landman-code.blogspot.com/2008/06/superfasthash- from-paul-hsieh.html
13 июля 2008 г.
"Более года назад Юхани Сухонен попросил быстрый хэш для его
хеш-таблица. Я предложил старый, но хорошо работающий эльфийский хеш, но также отметил
гораздо лучшая хэш-функция, которую я недавно нашел. Он назывался SuperFastHash (SFH).
и был создан Полом Хси для преодоления его «проблем» с хэш-функциями.
от Боба Дженкинса. Джухани спросил, может ли кто-нибудь написать функцию SFH на basm.
Несколько человек работали над реализацией basm и опубликовали ее ».
Сага о хешировании продолжается:
2007-03-13 Эндрю: Когда плохое хеширование означает хорошее кеширование
www.team5150.com/~andrew/blog/2007/03/hash_algorithm_attacks.html
2007-03-29 Эндрю: Нарушение SuperFastHash
floodyberry.wordpress.com/2007/03/29/breaking-superfasthash/
2008-03-03 Остин Эпплби: MurmurHash 2.0
murmurhash.googlepages.com/
SuperFastHash - 985,335173 МБ / с
lookup3 - 988,080652 МБ / с
MurmurHash 2.0 - 2056,885653 МБ / сек
Предоставляет код на C ++ MurmurrHash2.cpp и реализацию выровненной версии только для чтения -
MurmurHashAligned2.cpp
// ================================================ ========================
// Вот MurmurHash2 Ландмана в C #
// 25 февраля 2009 г. Дэви Лэндман реализует C # SuperFashHash и MurmurHash2
//landman-code.blogspot.com/search?updated-min=2009-01-01T00%3A00%3A00%2B01%3A00&updated-max=2010-01-01T00%3A00%3A00%2B01%3A00&max-results=2
//
// Landman использует SuperFastHash и MurmurHash2 4 способами в C #:
// 1: управляемый код 2: встроенный битовый преобразователь 3: Int Hack 4: небезопасные указатели
// SuperFastHash 1: 281 2: 780 3: 1204 4: 1308 МБ / с
// MurmurHash2 1: 486 2: 759 3: 1430 4: 2196
Извините, если все вышеперечисленное выглядит беспорядочно. Мне пришлось просто вырезать и вставить его.
По крайней мере, одна из приведенных выше ссылок дает вам возможность получить 64-битный хэш, который определенно не будет иметь коллизий в пространстве номеров кредитных карт и может быть легко сохранен в поле bigint в MySQL.
Вам не нужен криптографический хеш. Они намного интенсивнее загружают процессор. А цель «криптографии» - остановить взлом, а не избежать коллизий.