Хеш от хеша уменьшает стойкость к брутфорсу — так ли это?

в 12:26, , рубрики: hash, php, sha512, брутфорс, Веб-разработка, информационная безопасность, пароли, хеширование, метки: , , , , ,

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

И, в принципе, это правда. Если количество этих вариантов изначально было большим.

А если нет?

Предположим, что речь идёт о паролях. Из-за них и возник весь сыр-бор — я хочу повысить безопасность тех наивных польователей, которые используют один и тот же пароль на нескольких сайтах. Сделать же это я намерелся с помощью хеширования пароля на клиентской стороне. В таком случае и в открытый канал, и, соответственно, на сервер уйдёт уже солёный хеш секретной фразы.

Но хранить этот хеш — пароль, по сути — в «чистом» виде для проверки тоже нельзя, ведь если «утечёт» база — залогиниться сможет каждый, кто посмотрит на «утёкшие» данные. Отсюда выходит, что его тоже надо хешировать.

Начитавшись вдоволь мнений «хешировать хеш — фе, так делают только непрофессионалы, ибо брутфорсом поломают!!!», я задумался: а был ли мальчик? а действительно ли это ухудшит стойкость к подбору? А может ли быть такое, что даже улучшит?

И решил это проверить.

Что такое брутфорс? (для тех, кто не в курсе)

Перебирать пароли можно по-разному.

Например, можно составить список наиболее часто употребляемых в качестве пароля комбинаций, таких как «1234567890», «qwerty», «пароль» и пробовать выдать их поочерёдно система авторизации. По-сути, это будет словарный перебор.

Ещё можно перебирать с более умным использованием большого, заранее сгенерированного словаря слов для данного языка, используя слова как символьную единицу. То есть, пароль «КвартирныйГрудь» с точки зрения такого перебора состоит не из пятнадцати символов, а всего лишь из двух.
Ещё использование словаря можно улучшить, если учитывать популярные варианты замены букв (leet, ошибки, etc: «haxor» => «hax0r»; «жираф» => &laquo}|{UPAф&raquo) и, например, ранжировать слова по частоте употребления (слово «квартирный» встретится в пароле с большей вероятностью, чем «лаптевидный»).

Такой перебор усложняется количеством вариантов, но всё равно лучше, чем перебор «в лоб» — брутфорс. При этом варианте происходит полный перебор всех возможных комбинаций. Так, например, для цифренного пароля с минимальной длиной в четыре символа и максимальной в пять будут перебираться такие комбинации:

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: ' . "tt" .  $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: ' . "tt" . 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;

?>

Результаты для AMD E-450, php 5.4.8, Arch Linux, x86_64, ядро 3.6.5-1-ARCH

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 символов на международном сайте, в котором допустимы все символы юникода — хеш от хеша действительно может подпортить вам стойкость к брутфорсу.
В случае типичных же паролей, количество оригинальных входных комбинаций меньше, чем количество выходных комбинаций достаточно длинной хеш-функции — смело используйте хеширование хеша. Даже если оно не улучшит ситуацию — то уж точно не ухудшит.

Автор: ivan_kolmycheck

Источник

Поделиться

* - обязательные к заполнению поля