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

StackOverflow https://stackoverflow.com/questions/800685

Вопрос

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

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

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

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

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

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

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

  • Разве MD5 нельзя доверять?В обычных ситуациях, когда вы используете алгоритм MD5 без злого умысла и ни у какой третьей стороны нет злонамеренных намерений, вы ожидаете ЛЮБЫХ коллизий (то есть два произвольных byte[] создают один и тот же хэш)

  • Насколько 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. Устойчивость к столкновениям:Как сложно кому-то найти два сообщения(любой два сообщения), которые имеют одинаковый хэш.
  2. Сопротивление прообразу:Учитывая хеш, насколько сложно найти другое сообщение с таким же хешем?Также известен как односторонняя хэш-функция.
  3. Второе сопротивление прообразу:Учитывая сообщение, найдите другое сообщение с таким же хешем.

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

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

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

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

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

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

Другие советы

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

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

MD5/SHA1/Sha2xx не имеют шансов на коллизию.

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

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

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

В настоящее время неизвестных атаки на прообраз или второй прообраз на МД5.

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

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

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

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

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

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

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

Никто никогда не обнаруживал коллизий SHA512.ВСЕГДА.Они очень старались.В этом отношении никто никогда не обнаруживал коллизий SHA256 или 384..

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

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

Число атак на коллизии SHA1 сократилось до 2^52, и это не займет много времени, пока коллизии SHA1 не станут общедоступными.

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

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

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

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

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

Обновлять:

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

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

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

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

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

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

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

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

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

Было бы неплохо взглянуть на БЛЕЙК2 алгоритм.

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top