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

140

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

  • MD5: 16 байт (время хеширования 500 МБ: 1462 мс)
  • SHA-1: 20 байтов (1644 мс)
  • SHA256: 32 байта (5618 мс)
  • SHA384: 48 байтов (3839 мс)
  • SHA512: 64 байта (3820 мс)
  • RIPEMD: 20 байт (7066 мс)

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

Преимущество MD5 в том, что он подходит для встроенного типа Guid; и это основа UUID типа 3 . Хеш SHA-1 является основой UUID типа 5. Что делает их действительно простыми в использовании для идентификации.

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

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

Мне действительно любопытно получить ответы на следующие конкретные вопросы:

  • Разве нельзя верить 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();
    }
Сэм Шафран
источник
15
Тот факт, что вы упомянули, что md5 подходит для формата GUID (16 байт), предполагает фундаментальное недоразумение. Не гарантируется, что хэш будет уникальным, но он редко (и его трудно подделать, если он используется в криптографическом смысле) и получен из того, хешем он является, в то время как GUID, ну, уникален, но не связан с содержимым вещь, которую он идентифицирует. Они используются для самых разных целей.
Барри Уорк,
1
Исправьте его не связанный, это просто удобный факт реализации. Я так понимаю, что в 16 байт бесконечность не уместить. Вы можете получить коллизии с ЛЮБЫМ алгоритмом хеширования
Сэм Сафрон,
5
Кроме того, Guid просто уникален на практике, теоретически, если вы продолжите создавать Guid, в конечном итоге вы получите дубликаты.
Сэм Саффрон,
3
Вам действительно не следует вставлять хеш в GUID, даже если он подходит. Самый простой пример: две копии одного и того же файла должны иметь разные идентификаторы GUID, но одинаковый хеш. Первые 8 букв имени человека тоже неплохо умещаются в 16 байтов.
dbkk
2
@ user2332868 Нарушение SHA-1 не влияет на вероятность случайных коллизий. Когда злонамеренный умысел представляет собой угрозу для вашего использования, я думаю, что слепой выбор любой хэш-функции является неправильным, и вам нужно потратить время на анализ рисков / затрат для вашего конкретного случая.
Андрей Таранцов

Ответы:

140

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

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

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

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

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

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

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

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

Эрик Бернетт
источник
1
Я очень благодарен вам за такой уровень детализации. Это очень полезно.
Joelc
1
Для некоторых приложений может подойти даже некриптографическая хеш-функция. OP никогда не упоминал, было ли это специально для паролей, или для аутентификации запроса-ответа, или для токенов доступа, или просто для индексации кучи строк / файлов. С другой стороны, производительность - это проблема для ОП ...
Сева Алексеев
113

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

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

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

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

Но ... MD5 не работает

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

В настоящее время нет известных атак на MD5 с использованием предварительного образа или второго предварительного образа .

Так что же такого «ломкого» в MD5, спросите вы? Третья сторона может сгенерировать 2 сообщения, одно из которых ЗЛО, а другое ХОРОШО, что оба хеш-значения имеют одно и то же значение. ( Атака столкновения )

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

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

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

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

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

  • Используйте функцию на основе SHA2XX, если вам нужна криптографически безопасная хеш-функция.

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

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

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

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

Актуальную информацию о различных хеш-функциях можно найти в зоопарке хеш-функций .

Но подождите, это еще не все

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

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

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

Сэм Шафран
источник
Хотя и MD5, и SHA-1 были ослаблены, MD5 намного слабее, чем SHA-1, но лишь немного быстрее. Были обнаружены фактические коллизии MD5, которые использовались для реальных эксплойтов (подделка сертификатов CA), но, насколько мне известно, реальных коллизий SHA-1 обнаружено не было (хотя количество операций было значительно уменьшено из-за перебора). И учитывая, насколько слабее MD5, я не удивлюсь, если атаки второго прообраза возникнут раньше для MD5, чем для SHA-1. Таким образом, я думаю, вам следует использовать SHA-1, если вам нужна скорость, а не сопротивление столкновениям, а в противном случае использовать один из семейства SHA-2.
Брайан Кэмпбелл
1
@Brian довольно ясно, что в течение следующих нескольких лет люди смогут запускать атаки с коллизией на SHA1, это эффективно сделает SHA1 таким же полезным, как и MD5. Сертификат CA - это атака с коллизией, аналогично через несколько лет люди смогут чтобы запустить такую ​​же атаку на сертификаты CA SHA1. Атака зависит от злонамеренной стороны, создающей ЗЛОЙ и ХОРОШИЙ сертификат. Нет известных первичных атак на MD5, и тот факт, что есть атаки на коллизии, не делает атаки предварительных изображений более или менее вероятными.
Сэм Саффрон,
Дело не столько в том, какой хеш вы используете для паролей, сколько в том, что хешируется. Если ваша соль известна, ваша база данных немедленно уязвима для атаки по словарю; если ваша соль носит процедурный характер, а ваша файловая система скомпрометирована, вы (снова) уязвимы; если ваша соль опущена, вы снова подвергаетесь риску. Речь идет о безопасности, независимо от того, ЧТО хешируется. Сертификаты я не буду рассматривать, потому что я не занимался ими как программист (IE, создание, понимание и т. Д.).
Роберт К.
Термин «сломанный» имеет особое значение в контексте хеширования, и это не то значение, на котором делается акцент в данном ответе. Все, что этот ответ приведет к путанице.
Джоэл Макбет
1
Это отличный ответ, потому что он ориентирован на практичность. Хэши используются не только для обеспечения безопасности (например, для создания ключей поиска в кеше для неконфиденциальных данных или для определения того, изменился ли сериализованный объект). Шансы на целевую атаку практически равны нулю (никогда не говори никогда), и даже если атака будет успешной, она не окажет материального воздействия. Отличная работа с упором на практическое (а не теоретическое) воздействие.
DVK
36

Обновить:

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

Оригинальный ответ:

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

  1. RIPEMD BROKEN, никогда не следует использовать, как показано в этом pdf
  2. MD-5 BROKEN, никогда не следует использовать, можно сломать за 2 минуты с помощью ноутбука
  3. SHA-1 BROKEN, никогда не должен использоваться, сломан в принципе, атаки улучшаются с каждой неделей
  4. SHA-2 WEAK, вероятно, будет сломан в ближайшие несколько лет. Было обнаружено несколько слабых мест. Обратите внимание, что, как правило, чем больше размер ключа, тем сложнее взломать хеш-функцию. Хотя размер ключа = сила не всегда верно, в основном это правда. Таким образом, SHA-256, вероятно, слабее SHA-512.
  5. НЕТ ИЗВЕСТНЫХ СЛАБЫХ, является кандидатом на SHA-3 . Он довольно новый и поэтому не тестировался. Он был реализован на нескольких языках.
  6. MD6 НЕТ ИЗВЕСТНЫХ СЛАБЫХ НОСИТЕЛЕЙ - еще один кандидат на SHA-3. Возможно, сильнее, чем Скиен, но медленнее на одноядерных машинах. Как и Скиен, это непроверено. Некоторые разработчики, ориентированные на безопасность, используют его в критически важных ролях. .

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

Итан Хейлман
источник
6
Я бы не стал ставить Skein и MD6 так высоко в список; есть причина, по которой соревнование SHA-3 не будет завершено до конца 2012 года. Требуется много времени и много глаз, чтобы убедиться, что хеш-функция действительно может быть безопасной, и ни одна из этих функций существуют уже достаточно долго для этого.
Эрик Бернетт,
Я согласен с вашими мнениями, но я думаю, что сообщество находится в странном положении. Все используемые хеш-функции опасно близки к тому, чтобы быть сломанными (возможно, это не SHA2 256-512), и все же нам нужно дождаться 2012 года, чтобы выбрать замену. выберите свой яд: слабый / сломанный или непроверенный (большинство кандидатов NIST не публиковались более 6 месяцев)? Трудный выбор.
Итан Хейлман
6
RIPEMD сломан, но RIPEMD-128/160/256 другие и не сломаны.
Bwooce
Мне неизвестны эффективные реализации Skein для .NET. Я встречал SkeinFish и nskein, и оба были очень медленными.
Cocowalla
1
Я бы подождал с использованием SHA-3, пока не появится фактический стандарт, по крайней мере, если вы действительно хотите следовать стандарту. В самом алгоритме слишком много вариантов.
Paŭlo Ebermann 01
3

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

rlbond
источник
1
Хотя я ни в коем случае не являюсь экспертом в этой области, разве в настоящее время невозможно вычислить произвольные хэши MD5 с помощью грубой силы?
mafu
@mafu: Поздний ответ, но можно вычислить любой хеш с помощью грубой силы. Это может занять очень много времени.
Warty
@ItzWarty Я специально имел в виду необходимое время - поскольку MD5 довольно короткий, я подумал, что можно было бы просто добавить в него разумный вычислительный источник (E3 или дешевую компьютерную сетку, несколько машин с несколькими видеокартами, что-то вдоль этих строк) и иметь возможность вычислить произвольный хеш MD5 в течение, скажем, нескольких дней.
mafu 02
@mafu Атака с использованием предварительного изображения стоит 2 ^ 127 вызовов хэша для 128-битного хэша. Это далеко не осуществимо. 2 ^ 80 вызовов возможно, но уже очень дорого.
CodesInChaos
3

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

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

Флорин Мирча
источник
Это может быть быстрее, за исключением того, что многие реализации имеют аппаратную поддержку, что делает SHA-256 довольно быстрым.
zaph
1
Согласен. по состоянию на 2019 год Blake2b является лучшим хешем общего назначения, выпущенным на сегодняшний день. Значительно быстрее, чем все другие альтернативы, и не менее безопасен (по крайней мере, в каком-либо значимом смысле), и может выполняться только в 336 байтах оперативной памяти (168 для blake2s), о, и он оптимизирован для процессоров с прямым порядком байтов, что является преобладающий порядок байтов в современных системах.
hanshenrik
2

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

tvanfosson
источник
1
Много раз, обсуждая решения проблемы, я упоминаю, что использую MD5 для быстрой идентификации (хеширования строки), они говорят: «Но md5 не работает ... не используйте его, используйте sha1» ... если что-то настолько фундаментально нарушено с некоторыми из более слабых хешей, что их следует избегать ... например, реальные рабочие случаи, когда нормальные данные вызывают коллизии
Сэм Саффрон,
Видя, как MD5 отлично работал у миллионов людей в течение пятнадцати лет, я подозреваю, что для вас это нормально, если безопасность хеширования не имеет решающего значения.
mqp
2
@sambo MD5 отлично работает практически в любом случае, кроме случаев, когда фактическая безопасность / целостность вашей системы зависит от предотвращения конфликтов.
Rex M
2

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

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

Майк Боерс
источник
@Mike: Я с вами в этом вопросе, вот что я искал в этом вопросе, это что-то о более слабых хэш-функциях, настолько фундаментально сломанных, что их никогда не следует использовать.
Сэм Саффрон,
Кроме того, если срок службы данных или требуемых средств защиты данных короче, чем период взлома (несколько минут в наши дни iirc), MD5 вполне подойдет. Ситуативно полезно, но все же полезно.
annakata
@annakata - имейте в виду, что вам также следует избегать повторного использования ключей в нескольких сообщениях, чтобы его можно было использовать в этих обстоятельствах.
Стив Уэстбрук,
0

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

синий
источник
1
хэш-функции обычно не используют ключи
Итан Хейлман,
0

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

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

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

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

Неизвестно
источник
Этот комментарий очень старый и кажется довольно похороненным, но этот фрагмент - RIAA, как известно, может создавать последовательности с эквивалентными хешами - бросился мне в глаза, и мне очень любопытно, каков был контекст для этого. В частности, брутфорс MD5 8 лет назад был немного менее тривиальным, чем в 2017 году, так что у них, должно быть, была довольно веская причина.
i336_