Какую криптографическую хеш-функцию выбрать?
.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; и это основа 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();
}
9 ответов
В криптографии хеш-функции обеспечивают три отдельные функции.
- Сопротивление столкновению: Насколько сложно кому-то найти два сообщения (любые два сообщения), которые хэшируют одно и то же.
- Сопротивление прообразу: Учитывая хэш, как трудно найти другое сообщение, которое хэширует то же самое? Также известен как односторонняя хэш-функция.
- Сопротивление второму прообразу: Получив сообщение, найдите другое сообщение, которое хэширует то же самое.
Эти свойства связаны, но независимы. Например, сопротивление столкновению подразумевает сопротивление второму прообразу, но не наоборот. Для любого конкретного приложения у вас будут разные требования, требующие одно или несколько из этих свойств. Хеш-функция для защиты паролей на сервере обычно требует только устойчивости к прообразу, в то время как дайджесты сообщений требуют всех трех.
Было показано, что 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 сообщения, одно из которых ЗЛО, а другое ХОРОШЕЕ, и оба хэшируют одно и то же значение. ( Столкновение атаки)
Тем не менее, текущая рекомендация 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.
Но подождите больше
Быстрая хеш-функция может быть проклятием. Например: очень распространенное использование хеш-функций - хранение паролей. По сути, вы вычисляете хеш пароля в сочетании с известной случайной строкой (для предотвращения радужных атак) и сохраняете этот хеш в базе данных.
Проблема в том, что если злоумышленник получит дамп базы данных, он может довольно эффективно угадать пароли, используя грубую силу. Каждая комбинация, которую он пробует, занимает доли миллисекунды, и он может опробовать сотни тысяч паролей в секунду.
Чтобы обойти эту проблему, можно использовать алгоритм bcrypt, он спроектирован как медленный, поэтому злоумышленник будет сильно замедлен при атаке на систему с использованием bcrypt. Недавно scrypt сделал заголовок, и некоторые считают его более эффективным, чем bcrypt, но я не знаю реализации.Net.
Обновить:
Времена изменились, у нас есть победитель SHA3. Я бы порекомендовал использовать keccak (он же SHA3) победителя конкурса SHA3.
Оригинальный ответ:
В порядке от слабого к сильному я бы сказал:
- RIPEMD BROKEN, никогда не должен использоваться, как видно из этого PDF
- MD-5 BROKEN, никогда не должен использоваться, может быть сломан через 2 минуты с ноутбуком
- SHA-1 BROKEN, никогда не должен использоваться, в принципе сломан, атаки становятся лучше с неделей
- SHA-2 WEAK, вероятно, будет сломан в ближайшие несколько лет. Было обнаружено несколько слабых мест. Обратите внимание, что, как правило, чем больше размер ключа, тем сложнее сломать хеш-функцию. Хотя размер ключа = сила не всегда верен, он в основном верен. Так что SHA-256, вероятно, слабее, чем SHA-512.
- Скейн НЕТ НЕИЗВЕСТНЫХ, является кандидатом на SHA-3. Это довольно новый и, следовательно, не проверенный. Это было реализовано на нескольких языках.
- MD6 NO KNOWN WEAKNESSES, еще один кандидат на SHA-3. Вероятно, сильнее, чем Skien, но медленнее на одноядерных машинах. Как и у Шиена, он не проверен. Некоторые разработчики, ориентированные на безопасность, используют его в критически важных ролях.
Лично я бы использовал MD6, потому что никогда нельзя быть слишком параноиком. Если скорость действительно беспокоит, я бы посмотрел на Skein или SHA-256.
В защите MD5 не существует известного способа создания файла с произвольным хешем MD5. Первоначальный автор должен заранее запланировать рабочее столкновение. Таким образом, если получатель доверяет отправителю, с MD5 все в порядке. MD5 нарушается, если подписчик злонамеренный, но он, как известно, не уязвим для атак "человек посередине".
Было бы неплохо взглянуть на алгоритм BLAKE2.
Как описано, он быстрее, чем MD5, и, по крайней мере, такой же безопасный, как SHA-3. Он также реализован несколькими программными приложениями, включая WinRar.
Какой из них вы используете, зависит от того, для чего вы его используете. Если вы просто хотите убедиться, что файлы не будут повреждены при транспортировке и не заботятся о безопасности, сделайте это быстро и без проблем. Если вам нужны цифровые подписи для федеральных соглашений о спасении на несколько миллиардов долларов и вам нужно убедиться, что они не подделаны, сделайте все возможное, чтобы подделать и замедлить.
Я хотел бы присоединиться (до того, как md5 разорвется на части), что я все еще широко использую md5, несмотря на его подавляющую ломкость для большого количества крипто.
Пока вы не заботитесь о защите от столкновений (вы все еще можете безопасно использовать md5 в hmac) и вам нужна скорость (иногда вам нужен более медленный хэш), вы все равно можете уверенно использовать md5.
Я не эксперт в такого рода вещах, но я слежу за сообществом безопасности, и многие люди считают, что хэш md5 сломан. Я бы сказал, что использовать зависит от того, насколько чувствительны данные и от конкретного приложения. Возможно, вам удастся использовать немного менее безопасный хеш, если ключ хороший и сильный.
Вот мои предложения для вас:
- Вы, вероятно, должны забыть MD5, если вы ожидаете атаки. Для них в Интернете есть множество радужных таблиц, и такие корпорации, как RIAA, как известно, способны создавать последовательности с эквивалентными хэшами.
- Используйте соль, если можете. Включение длины сообщения в сообщение может очень затруднить создание полезного хэш-конфликта.
- Как общее практическое правило, больше битов означает меньше столкновений (по принципу голубя) и медленнее, и, возможно, более безопасно (если вы не гений математики, который может найти уязвимости).
Смотрите здесь документ, в котором подробно описан алгоритм создания коллизий md5 за 31 секунду с настольным компьютером Intel P4.