Какую криптографическую хэш-функцию я должен выбрать?

.NET framework поставляется с 6 различными алгоритмами хеширования:

MD5: 16 байт (время до хэша 500 МБ: 1462 мс)
SHA1: 20 байт (1644 мс)
SHA256: 32 байта (5618 мс)
SHA384: 48 байт (3839 мс)
SHA512: 64 байта (3820 мс)
RIPEMD: 20 байт (7066 мс)

Каждая из этих функций выполняется по-разному; MD5 является самым быстрым, а RIPEMD является самым медленным.

MD5 имеет то преимущество, что он вписывается во встроенный тип Guid. Это делает его очень простым в использовании для идентификации.

Однако MD5 уязвим для коллизионных атак, SHA1 также уязвим, но в меньшей степени.

В каких условиях следует использовать алгоритм хеширования?

Частные вопросы, на которые мне действительно интересно посмотреть:

Нельзя ли доверять MD5? В нормальных ситуациях, когда вы используете алгоритм MD5 без злонамеренных намерений, и у какой-либо третьей стороны нет злонамеренных намерений, вы ожидаете ЛЮБЫЕ столкновения (что означает два произвольных байта [], производящих один и тот же хэш)
Насколько лучше RIPEMD, чем SHA1? (если он лучше), в 5 раз медленнее вычислять, но размер хэша совпадает с SHA1.
Каковы шансы на получение нездоровых коллизий при хэшировании имен файлов (или других коротких строк)? (Например, 2 случайных имени файла с одним и тем же MD5-хешем) (с MD5/SHA1/SHA2xx) В общем, каковы шансы на нездоровые столкновения?

Это контрольный показатель, который я использовал:

    static void TimeAction(string description, int iterations, Action func) {
        var watch = new Stopwatch();
        watch.Start();
        for (int i = 0; i < iterations; i++) {
            func();
        }
        watch.Stop();
        Console.Write(description);
        Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds);
    }

    static byte[] GetRandomBytes(int count) {
        var bytes = new byte[count];
        (new Random()).NextBytes(bytes);
        return bytes;
    }


    static void Main(string[] args) {

        var md5 = new MD5CryptoServiceProvider();
        var sha1 = new SHA1CryptoServiceProvider();
        var sha256 = new SHA256CryptoServiceProvider();
        var sha384 = new SHA384CryptoServiceProvider();
        var sha512 = new SHA512CryptoServiceProvider();
        var ripemd160 = new RIPEMD160Managed();

        var source = GetRandomBytes(1000 * 1024);

        var algorithms = new Dictionary<string,HashAlgorithm>();
        algorithms["md5"] = md5;
        algorithms["sha1"] = sha1;
        algorithms["sha256"] = sha256;
        algorithms["sha384"] = sha384;
        algorithms["sha512"] = sha512;
        algorithms["ripemd160"] = ripemd160;

        foreach (var pair in algorithms) {
            Console.WriteLine("Hash Length for {0} is {1}", 
                pair.Key, 
                pair.Value.ComputeHash(source).Length);
        }

        foreach (var pair in algorithms) {
            TimeAction(pair.Key + " calculation", 500, () =>
            {
                pair.Value.ComputeHash(source);
            });
        }

        Console.ReadKey();
    }

Ответы

Ответ 1

В криптографии хеш-функции предоставляют три отдельные функции.

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

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

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

SHA1 имеет недостаток, который позволяет обнаруживать столкновения теоретически намного меньше, чем шаги 2 ^ 80, для чего потребуется безопасная хэш-функция его длины. Атака постоянно пересматривается и в настоящее время может выполняться в ~ 2 ^ 63 шагах - только в пределах текущей области вычислимости. По этой причине NIST прекращает использование SHA1, заявляя, что семейство SHA2 должно использоваться после 2010 года.

SHA2 - новое семейство хеш-функций, созданных после SHA1. В настоящее время нет известных атак на функции SHA2. SHA256, 384 и 512 являются частью семейства SHA2, просто используя разные длины клавиш.

RIPEMD Я не могу комментировать слишком много, кроме как отметить, что он не так часто используется как семьи SHA, и поэтому не был тщательно изучен криптографическими исследователями. По этой причине я бы рекомендовал использовать функции SHA над ним. В реализации, которую вы используете, она кажется довольно медленной, что делает ее менее полезной.

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

Ответ 2

Все хеш-функции "сломаны"

принцип пигментной дыры говорит, что старайтесь изо всех сил, как вы, вы не сможете поместить больше двух голубей в 2 отверстия (если вы не разрезаете голубей вверх). Аналогично, вы не можете вместить 2 ^ 128 + 1 номеров в 2 ^ 128 слотах. Все хеш-функции приводят к хешу конечного размера, это означает, что вы всегда можете найти столкновение, если будете искать последовательности "конечного размера" + 1. Это просто невозможно. Не для MD5, а не для Skein.

MD5/SHA1/Sha2xx не имеют случайных столкновений

Все хэш-функции имеют коллизии, это факт жизни. Появление этих столкновений случайно является эквивалентом выигрыша межгалактической лотереи. То есть никто не выигрывает межгалактическую лотерею, ее просто не так, как работает лотерея. Вы не столкнетесь с случайным хешем MD5/SHA1/SHA2XXX, КОГДА-ЛИБО. Каждое слово в каждом словаре, на каждом языке, хеши имеет другое значение. Каждое имя пути на каждой машине на всей планете имеет другой хеш MD5/SHA1/SHA2XXX. Откуда я знаю это, спросите вы. Ну, как я уже говорил, никто не выигрывает межгалактическую лотерею.

Но... MD5 сломан

Иногда тот факт, что его сломанный не имеет значения.

В его нынешнем виде нет известных предварительных изображений или вторых предварительных изображений на MD5.

Итак, что так нарушено о MD5, вы можете спросить? Третьему лицу может быть создано 2 сообщения, одним из которых является EVIL, а другой из которых является ХОРОШИМ, что оба хэша равны одному значению. (Атака на столкновение)

Тем не менее, настоящая рекомендация RSA не должна использовать MD5, если вам требуется предварительное изображение. Люди склонны ошибаться с осторожностью, когда речь идет о алгоритмах безопасности.

Итак, какую функцию хеша использовать в .NET?

Используйте MD5, если вам нужна скорость/размер, и не заботятся о атаках на день рождения или атаках с предварительным изображением.

Повторите это после меня, нет случайных столкновений MD5, злонамеренные столкновения могут быть тщательно спроектированы. Несмотря на то, что на MD5 не существует известных предварительных атак, линия от экспертов по безопасности заключается в том, что MD5 не следует использовать там, где вам нужно защищаться от атак с предварительным изображением. SAME идет для SHA1.

Имейте в виду, что не все алгоритмы должны защищаться от атак с предварительным изображением или столкновениями. Возьмите тривиальный случай поиска первого прохода для дубликатов файлов на вашем HD.

Используйте функцию на основе SHA2XX, если вы хотите использовать криптографически защищенную функцию хэш-функции.

Никто никогда не обнаружил столкновения SHA512. КОГДА-ЛИБО. Они очень старались. В этом отношении никто никогда не встречал никаких столкновений SHA256 или 384.,

Не используйте SHA1 или RIPEMD, если только для сценария совместимости.

RIPMED не получил такого же объема проверки, что и SHAX и MD5. Оба SHA1 и RIPEMD уязвимы для атак на день рождения. Они медленнее, чем MD5 на .NET, и попадают в неудобный 20-байтовый размер. Бессмысленно использовать эти функции, забыть о них.

Атаки на столкновение SHA1 уменьшаются до 2 ^ 52, это не будет слишком долго, пока столкновения SHA1 не исчезнут в дикой природе.

Для актуальной информации о различных хэш-функциях смотрите хэш-функцию zoo.

Но подождите больше

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

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

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

Ответ 3

Update:

Времена изменились, у нас есть победитель SHA3. Я бы рекомендовал использовать keccak (aka SHA3) победитель конкурса SHA3.

Исходный ответ:

В порядке наименьшего значения я бы сказал:

RIPEMD BROKEN, никогда не следует использовать как видно из этого pdf
MD-5 BROKEN, никогда не должен использоваться, можно сломать через 2 минуты с ноутбуком
SHA-1 BROKEN, никогда не должен использоваться, нарушается в принципе, атаки улучшаются на неделю
SHA-2 WEAK, вероятно, будет разбит в ближайшие несколько лет. Несколько недостатков найдено. Обратите внимание, что, как правило, более высокий размер ключа, тем сложнее хэш-функция должна сломаться. Хотя размер ключа = сила не всегда истинна, это в основном верно. Таким образом, SHA-256, вероятно, слабее, чем SHA-512.
Skein NO KNOWN WEAKNESSES, является кандидатом на SHA-3. Это довольно новый и, следовательно, непроверенный. Он был реализован на множестве языков.
MD6 NO KNOWN WEAKNESSES, является еще одним кандидатом на SHA-3. Вероятно, сильнее Skien, но медленнее на одноядерных машинах. Как и Skien, он не проверен. Некоторые разработчики, ориентированные на безопасность, используют его в критически важных ролях.

Лично я бы использовал MD6, потому что никогда не мог быть слишком параноидальным. Если скорость будет реальной проблемой, я бы посмотрел на Skein или SHA-256.

Ответ 4

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

Ответ 5

Я хотел бы прослушивать (до того, как md5 разрывается), что я все еще использую md5 широко, несмотря на его подавляющую разбитость для большого количества криптова.

Пока вы не хотите защищать от коллизий (вы все еще можете использовать md5 в hmac, а также), и вам нужна скорость (иногда вам нужен более медленный хеш), тогда вы все равно можете использовать md5 уверенно.

Ответ 6

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

Ответ 7

Было бы хорошим идеей взглянуть на BLAKE2 algorythm.

Как описано выше, он быстрее MD5 и, по крайней мере, безопасен как SHA-3. Это также реализовано несколькими программными приложениями, включая WinRar.

Ответ 8

Я не эксперт в таких вещах, но я не отстаю от сообщества безопасности, и многие люди считают, что хеш md5 сломан. Я бы сказал, что тот, который нужно использовать, зависит от того, насколько чувствительны данные и какое конкретное приложение. Вы можете уйти со слегка менее безопасным хэшем, если ключ хороший и сильный.

Ответ 9

Вот мои предложения для вас:

Вероятно, вам следует забыть о MD5, если вы ожидаете атаки. Есть много радужных таблиц для них в Интернете, и такие корпорации, как RIAA, могут создавать последовательности с эквивалентными хэшами.
Используйте salt, если сможете. Включение длины сообщения в сообщение может затруднить полезную хэш-коллизию.
Как правило, большее количество бит означает меньшее количество столкновений (по принципу pigeonhole) и более медленное и, возможно, более безопасное (если вы не математический гений, который может найти уязвимости).

См. здесь документ, в котором подробно описывается алгоритм создания столкновений md5 через 31 секунду с компьютером Intel P4 для настольных ПК.

http://eprint.iacr.org/2006/105