И, в принципе, это правда. Если количество этих вариантов изначально было большим.
А если нет?
Предположим, что речь идёт о паролях. Из-за них и возник весь сыр-бор — я хочу повысить безопасность тех наивных польователей, которые используют один и тот же пароль на нескольких сайтах. Сделать же это я намерелся с помощью хеширования пароля на клиентской стороне. В таком случае и в открытый канал, и, соответственно, на сервер уйдёт уже солёный хеш секретной фразы.
Но хранить этот хеш — пароль, по сути — в «чистом» виде для проверки тоже нельзя, ведь если «утечёт» база — залогиниться сможет каждый, кто посмотрит на «утёкшие» данные. Отсюда выходит, что его тоже надо хешировать.
Начитавшись вдоволь мнений «хешировать хеш — фе, так делают только непрофессионалы, ибо брутфорсом поломают!!!», я задумался: а был ли мальчик? а действительно ли это ухудшит стойкость к подбору? А может ли быть такое, что даже улучшит?
И решил это проверить.
Что такое брутфорс? (для тех, кто не в курсе)
Перебирать пароли можно по-разному.
Например, можно составить список наиболее часто употребляемых в качестве пароля комбинаций, таких как «1234567890», «qwerty», «пароль» и пробовать выдать их поочерёдно система авторизации. По-сути, это будет словарный перебор.
Ещё можно перебирать с более умным использованием большого, заранее сгенерированного словаря слов для данного языка, используя слова как символьную единицу. То есть, пароль «КвартирныйГрудь» с точки зрения такого перебора состоит не из пятнадцати символов, а всего лишь из двух.
Ещё использование словаря можно улучшить, если учитывать популярные варианты замены букв (leet, ошибки, etc: «haxor» => «hax0r»; «жираф» => «}|{UPAф») и, например, ранжировать слова по частоте употребления (слово «квартирный» встретится в пароле с большей вероятностью, чем «лаптевидный»).
Такой перебор усложняется количеством вариантов, но всё равно лучше, чем перебор «в лоб» — брутфорс. При этом варианте происходит полный перебор всех возможных комбинаций. Так, например, для цифренного пароля с минимальной длиной в четыре символа и максимальной в пять будут перебираться такие комбинации:
0000 0001 0002 ... 9999 00000 ... 99999
Брутфорс — самый долгий вид перебора, но он гарантирует нахождение комбинации. Если вы до этого доживёте.
Множество вариантов
Итак, будем считать, что мы не перебираем по словарю, а именно брутфорсим.
Я написал небольшой скрипт на PHP (да простят меня за выбор языка), который подсчитывает максимальное количество комбинаций для разных паролей.
Подсчитываю я по простой формуле из комбинаторики — (n)^i + (n)^(i — 1) +… + (n)^1, где n — размер используемого набора символов. Я взял три набора: один (Hex, 0-f, 16 символов) для хеша и два (типичные символы, 70 штук, и такой же, но добавил туда ещё 70 символов кирилицы) для паролей.
<?php function maxPossibleVariants($length, $symbolVariantsCount, $minLength = 1) { $variantsCount = 0; for ($i = $minLength; $i <= $length; $i++) { $variantsCount += pow($symbolVariantsCount, $i); } return $variantsCount; } $latinAlphpabetSymbols = 25; $cyrillicAlphabetSymbols = 35; // 33 + 2 extra ukrainian, for example. $typicalPasswordNonletters = array( // Really typical symbols '-', '_', ',', ' ', '.', '\'', '`', '@', '?', '!', '*', '&', '$', // + some crazy staff =) '+', '=', '(', ')', '^', '[', ']', ); $typicalPasswordSymbolsCount = ($latinAlphpabetSymbols * 2 /* UC + LC */) + count($typicalPasswordNonletters); $typicalCyrillicPasswordSymbolsCount = $typicalPasswordSymbolsCount + ($cyrillicAlphabetSymbols * 2 /* UC + LC */); echo 'Typical password symbols count: ' . "\t\t" . $typicalPasswordSymbolsCount . PHP_EOL; echo 'Typical password symbols count (+cyrillic): ' . "\t" . $typicalCyrillicPasswordSymbolsCount . PHP_EOL . PHP_EOL; echo '128-hex-symbol hash:' . "\t" . maxPossibleVariants(128, 16, 128) . PHP_EOL; echo '(sha-512 or whirpool)'. PHP_EOL . PHP_EOL; echo 'Passwords:' . PHP_EOL; foreach (array(84, 80, 72, 70, 60, 50, 40, 20, 10,) as $length) { echo $length . ' symbols: ' . "\t\t" . maxPossibleVariants($length, $typicalPasswordSymbolsCount) . PHP_EOL; echo $length . ' symbols (+cyr): ' . "\t" . maxPossibleVariants($length, $typicalCyrillicPasswordSymbolsCount) . PHP_EOL . PHP_EOL; } ?>
dfyz@alice ~/work/hash.test $ php ./test.php Typical password symbols count: 70 Typical password symbols count (+cyrillic): 140 128-hex-symbol hash: 1.3407807929943E+154 (sha-512 or whirpool) Passwords: 84 symbols: 9.8737996455247E+154 // Сравнимый порядок для первого набора; 84 symbols (+cyr): 1.8961305363181E+180 80 symbols: 4.112369698261E+147 80 symbols (+cyr): 4.9357833619277E+171 72 symbols: 7.13358483365E+132 72 symbols (+cyr): 3.3445046511631E+154 // Сравнимый порядок для второго набора; 70 symbols: 1.4558336395204E+129 70 symbols (+cyr): 1.7063799240628E+150 60 symbols: 5.1538449640252E+110 60 symbols (+cyr): 5.8992306423017E+128 50 symbols: 1.8245297534104E+92 50 symbols (+cyr): 2.0394591896166E+107 40 symbols: 6.4590783081686E+73 40 symbols (+cyr): 7.0507393901259E+85 20 symbols: 8.0948675954099E+36 20 symbols (+cyr): 8.4270185320431E+42 10 symbols: 2865690931884057970 10 symbols (+cyr): 2.9133562371683E+2
То есть, сравнимое количество комбинаций находится где-то в районе 72-символьного пароля для набора из 140 символов и 84-символьного пароля для набора из 70 символов. Перенос границы минимального размера пароля с 1 символа до, скажем, 8, хоть и влияет на результат, но не особо.
Иными словами: хеширование уменьшает количество возможных комбинаций только для строк длиннее 72-80 символов с достаточно большим (70+) набором вариантов каждого символа.
Теперь давайте взглянем на эти данные с учётом реальной обстановки: я считаю, что перебрать обычный пароль проще, чем хеш. Почему? Вот список причин:
- Видели ли вы пользователя, который сделал бы себе действительно разнообразный пароль из 70 символов? Я, например, не генерирую пароли больше 64-х символов.
- Видели ли вы пользователя, который бы настолько извращался с паролем и использовал бы те символы, которые я указал в примере?
- Распределение в хеше, всё-таки, лучше, так что мы более защищены от слабого и глупого пароля вроде «1234567890», который будет подобран ну очень быстро. SHA-512 хеш этого пароля с солью «hax0r» (просто добавленной в конец) — «5a2b2bfad9e0a8f25cde91849f8c5ce8a3795f2296a0bca3f0b75835a77b039c80a0c1532db8d7ce6012aa306967f8297f4e4ae2e72be3bf9d05cb140f1ce849». Согласитесь ли вы, что прямым перебором подобрать такое труднее?
- Словарный перебор хеша невозможен. Вариант с радужными таблицами отметается использованием хорошей соли.
А если?..
Возможно ли ускорить перебор при помощи такой хитрой комбинации: перебираем известные комбинации, хешируем их с солью, сверяем? В этом случае, каждая операция занимает на столько больше времени, на сколько долго выполняется хеширование выбранным алгоритмом. Таким образом, чем «тяжелее» алгоритм — тем лучше.
В комментариях к описанию функции hash() на php.net есть код для проверки скорости генерации хеша для килобайта случайных данных.
<?php echo 'Building random data ...' . PHP_EOL; @ob_flush();flush(); $data = ''; for ($i = 0; $i < 64000; $i++) $data .= hash('md5', rand(), true); echo strlen($data) . ' bytes of random data built !' . PHP_EOL . PHP_EOL . 'Testing hash algorithms ...' . PHP_EOL; @ob_flush();flush(); $results = array(); foreach (hash_algos() as $v) { echo $v . PHP_EOL; @ob_flush();flush(); $time = microtime(true); hash($v, $data, false); $time = microtime(true) - $time; $results[$time * 1000000000][] = "$v (hex)"; $time = microtime(true); hash($v, $data, true); $time = microtime(true) - $time; $results[$time * 1000000000][] = "$v (raw)"; } ksort($results); echo PHP_EOL . PHP_EOL . 'Results: ' . PHP_EOL; $i = 1; foreach ($results as $k => $v) foreach ($v as $k1 => $v1) echo ' ' . str_pad($i++ . '.', 4, ' ', STR_PAD_LEFT) . ' ' . str_pad($v1, 30, ' ') . ($k / 1000) . ' microseconds' . PHP_EOL; ?>
Results: 1. md4 (hex) 3335.952 microseconds 2. adler32 (raw) 3376.007 microseconds 3. md4 (raw) 3383.874 microseconds 4. adler32 (hex) 3409.862 microseconds 5. md5 (hex) 3690.004 microseconds 6. md5 (raw) 3738.88 microseconds 7. fnv132 (hex) 4028.081 microseconds 8. crc32 (raw) 4812.955 microseconds 9. crc32 (hex) 4904.985 microseconds 10. crc32b (hex) 4914.999 microseconds 11. fnv132 (raw) 4935.026 microseconds 12. tiger160,3 (raw) 5802.154 microseconds 13. tiger160,3 (hex) 5859.136 microseconds 14. tiger192,3 (hex) 5931.854 microseconds 15. fnv164 (hex) 6034.135 microseconds 16. tiger192,3 (raw) 6039.857 microseconds 17. tiger128,3 (raw) 6604.909 microseconds 18. joaat (hex) 6613.016 microseconds 19. tiger128,3 (hex) 6810.903 microseconds 20. tiger192,4 (raw) 7117.986 microseconds 21. tiger160,4 (raw) 7128 microseconds 22. tiger192,4 (hex) 7206.916 microseconds 23. tiger128,4 (hex) 7232.904 microseconds 24. tiger128,4 (raw) 7272.958 microseconds 25. tiger160,4 (hex) 7367.134 microseconds 26. fnv164 (raw) 7812.023 microseconds 27. joaat (raw) 7821.083 microseconds 28. crc32b (raw) 8275.032 microseconds 29. sha1 (raw) 8594.989 microseconds 30. sha1 (hex) 8599.996 microseconds 31. ripemd128 (raw) 11169.91 microseconds 32. ripemd256 (raw) 11229.991 microseconds 33. ripemd256 (hex) 11245.965 microseconds 34. ripemd128 (hex) 11436.939 microseconds 35. sha512 (raw) 15016.078 microseconds 36. sha384 (raw) 15047.073 microseconds 37. sha384 (hex) 15048.027 microseconds 38. sha512 (hex) 15092.134 microseconds 39. haval160,3 (raw) 15184.879 microseconds 40. haval224,3 (raw) 15221.118 microseconds 41. haval256,3 (raw) 15257.835 microseconds 42. haval192,3 (hex) 16965.866 microseconds 43. haval224,3 (hex) 17545.938 microseconds 44. haval192,3 (raw) 17798.9 microseconds 45. ripemd320 (raw) 18279.79 microseconds 46. ripemd160 (raw) 18393.039 microseconds 47. ripemd160 (hex) 18426.179 microseconds 48. ripemd320 (hex) 18468.856 microseconds 49. haval256,3 (hex) 21245.956 microseconds 50. haval256,4 (raw) 22063.97 microseconds 51. haval128,4 (raw) 22157.192 microseconds 52. haval160,4 (raw) 22488.117 microseconds 53. haval160,4 (hex) 22527.933 microseconds 54. haval256,4 (hex) 22544.145 microseconds 55. haval224,4 (hex) 22716.999 microseconds 56. haval224,4 (raw) 22732.019 microseconds 57. haval192,4 (hex) 22818.088 microseconds 58. haval192,4 (raw) 22866.964 microseconds 59. haval128,3 (raw) 23015.975 microseconds 60. sha256 (raw) 23026.943 microseconds 61. sha224 (raw) 23036.003 microseconds 62. sha224 (hex) 23122.072 microseconds 63. sha256 (hex) 23164.987 microseconds 64. haval160,3 (hex) 24441.957 microseconds 65. haval128,4 (hex) 25613.069 microseconds 66. haval256,5 (raw) 26602.029 microseconds 67. haval224,5 (raw) 26610.136 microseconds 68. haval224,5 (hex) 26697.874 microseconds 69. haval192,5 (raw) 26725.053 microseconds 70. haval256,5 (hex) 26987.075 microseconds 71. haval128,5 (hex) 27288.913 microseconds 72. haval128,3 (hex) 32751.083 microseconds 73. haval192,5 (hex) 35580.158 microseconds 74. haval160,5 (raw) 36442.995 microseconds 75. haval128,5 (raw) 37140.13 microseconds 76. haval160,5 (hex) 39947.986 microseconds 77. whirlpool (raw) 46053.886 microseconds 78. whirlpool (hex) 47896.862 microseconds 79. gost (raw) 53829.908 microseconds 80. gost (hex) 66866.874 microseconds 81. snefru (hex) 96088.886 microseconds 82. snefru (raw) 96105.098 microseconds 83. snefru256 (hex) 96953.868 microseconds 84. snefru256 (raw) 98623.991 microseconds 85. md2 (raw) 218511.819 microseconds 86. md2 (hex) 219610.929 microseconds
На моей машине whirlpool выполняется дольше большинства других и имеет при этом хорошую длину результата. То есть, для хеширования пароля это вполне подходящий вариант.
Вывод
Если вы хешируете «Войну и мир» или пароли с минимальной длиной в 50-60 символов на международном сайте, в котором допустимы все символы юникода — хеш от хеша действительно может подпортить вам стойкость к брутфорсу.
В случае типичных же паролей, количество оригинальных входных комбинаций меньше, чем количество выходных комбинаций достаточно длинной хеш-функции — смело используйте хеширование хеша. Даже если оно не улучшит ситуацию — то уж точно не ухудшит.
ссылка на оригинал статьи http://habrahabr.ru/post/158491/
Добавить комментарий