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

Question

.NET Framework поставляется с 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; и это основа типа 3 UUID . 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();
    }

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

Принцип голубиного отверстия гласит, что изо всех сил старайтесь не помещать более 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 не исчезнут в дикой природе.

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

Но подождите еще

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

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

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

Answer 3

Обновление:

Времена изменились, у нас есть победитель 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. Skein NO KNOWN WEAKNESSES, является кандидатом на SHA-3 . Это довольно новый и, следовательно, не проверенный. Он был реализован на нескольких языках.
6. MD6 НЕТ НЕИЗВЕСТНЫХ, еще один кандидат на SHA-3. Вероятно, сильнее, чем Skien, но медленнее на одноядерных машинах. Как и Шиен, он не проверен. Некоторые разработчики, ориентированные на безопасность, используют его в критически важных ролях .

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

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

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

Answer 9

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