11.03 // НИСТ утвердил две новые хэш-функции SHA-512/t в стандарте SHS - FIPS 180-4
После признания хэш-функции SHA-1 нестойкой, её присутствие в стандарте Secure Hash Standart остаётся для совместимости со старыми системами и в целях возможности планомерного выведения из употребления. В отношений функций SHA-2 также наблюдается определённый прогресс в криптоанализе, который однако пока не привёл даже к теоретическому взлому. Объявленный конкурс на новый стандарт на основе хэш-функции SHA-3 является долгосрочным проектом, завершение и внедрение результатов которого возможно лишь в отдалённой перспективе.
В это время Национальный Институт Стандартов и Технологий США вносит незначительные уточнения в текущий SHS. В мартовском выпуске стандарта помимо традиционного набора хэш-функций (SHA-1, SHA-224, SHA-256, SHA-384, SHA-512) вводятся и дополнительные варианты использования: SHA-512/224 и SHA-512/256. Как несложно догадаться, это значение хэш-функции SHA-512, полученное отбрасыванием лишних бит, однако при этом используются отличающиеся константы первоначального заполнения (в то время как остальной набор констант остаётся неизменным). Поэтому выход такой функции будет полностью отличаться от SHA-512: можно говорить о двух новых хэш-функциях, которые не следует путать с уже имеющимиcя.
Это позволяет использовать функции с уменьшенным размером выхода, но при вычислении полного 512-битного хэша с максимальным внутренним состоянием, что является возможно неоптимальным по быстродействию и другим ресурсам, но обеспечивает максимальный запас прочности. При этом из предыдущих алгоритмов только SHA-384 и SHA-512 были ориентированы на использование 64-битных слов, что сохраняется и в новом алгоритме.
Для сообщений размером не более 264 бит допустимо использовать SHA-1, SHA-224, SHA-256; в то время как SHA-384, SHA-512, SHA-512/224, SHA-512/256 могут работать с сообщениями размером до 2128 бит.
Таким образом, функции семейства SHA-512/t являются несложной и легковнедряемой модификацией хэш-функций семейства SHA-2, предназначенной для повышения уровня стойкости в качестве временной меры до момента принятия SHA-3. НИСТ опубликовал алгоритм вычисления констант для любого приемлемого значения t, но зафиксировал в текущем стандарте только хэш-функции на основе двух значений. В случае необходимости использования некоторыми приложениями нестандартной длины выхода хэш-функции SHA-2, НИСТ рекомендует использовать аналогичное отбрасывание битов, но с учётом рекомендаций, опубликованных в SP 800-107: Recommendation for Applications Using Approved Hash Algorithms.
комментариев: 9796 документов: 488 редакций: 5664
Это замечание абсолютно верно, но и абсолютно тривиально. Если бы хэш-функция была бы идеальной (неотличимой от пресловутого случайного оракула), то кроме тривиальной атаки нахождения решений перебором с ней ничего нельзя было бы поделать. Поэтому, стойкость хэш-функции зависела бы только от размера выхода.
Никакая хэш-функция не может быть идеальной, поэтому нужно учитывать и размер её внутреннего состояния. Однако, размер внутреннего состояния заранее учитывается таким образом, чтобы соответствовать размеру выхода. Это опять же верно, если функция стойкая в более широком смысле (здесь можно ещё развернуть дискуссию о различии между двумя видами стойкости — как модельный чёрный ящик с набором известных параметров в духе т.н. "доказуемой безопасности" и как реальный алгоритм).
Но что если функция оказывается нестойкой к различным видам криптоанализа (а к SHA-2 доверие в этом плане также снижается)? Тогда, чем больше внутреннее состояние и больше количество раундов, тем (при прочих равных) функция более стойкая.
Вот две обновлённые функции, заменяющие две старые (размер выхода у них одинаковый):
Английская вики всё ещё не знает про новые функции и обозначение в таблице через "/"-слэш приводит к путанице, там имеются в виду обычные варианты хэшей! Можно подозревать, что такая путаница и непонимание будет существовать ещё какое-то время после принятия этого стандарта.
Он слишком короткий (128 бит) и здесь возможен уже брутфорс. Предлагается обрезать SHA-512 до 224 бит и до 256 бит. Но чтобы выход не выглядел просто как обрезанная функция (это важно с точки зрения безопасности — чтобы не было подмены в некоторых протоколах), то в самой функции изменены некоторые константы, поэтому выход выглядит как новая функция.
комментариев: 9796 документов: 488 редакций: 5664
Это давний спор теоретиков. Точно найти работы, источники где в явном виде дан определённый вывод, пожалуй не смогу. Скорее это заявлено некоторыми исследователями в дизайне новых хэш-функций (и то неявно), но похожий вопрос где-то обсуждался.
Что лучше — сжатие внутреннего состояния или урезание? При условии что состояние уже равномерно перемешано — иначе это будет сжатие двух различимых состояний в одно. Пока необщепринято, но некоторые считают, что урезание (отбрасывание) лучше.
Теоретически это означает (на уровне слабых, необщепризнанных доказательств и спекуляций), что если для хэш-функции будет найден различитель и она окажется дефектной, то утечка внутреннего состояния через сжатие будет сильнее, чем через отбрасывание. Что позволит, якобы, быстрее перейти от различителя к поиску коллизий и пр.
Так, в новой хэш-функции (SHA-3 кандидат)-Keccak используется урезание от большого внутреннего состояния перед выходом. А также модификация внутреннего состояния нужным числом дополнительных раундов перед новой порцией "выдавливания с урезанием" — если нужно получить произвольно длинный выход. В то время как во всех остальных (SHA-3)-финалистах (если ничего не пропустил) используется более традиционный подход с применением функций сжатия внутри раундов.
В SHA-2, естественно, старая классическая конструкция Дамгарда-Меркла со сжатием внутри раундов, но выход в конце хэш-функции теперь решили сделать с отбрасыванием. При угрозе взлома это ИМХО некая робкая малобоснованная надежда (попытка подрихтовать фасад). Если SHA-2 окажется уязвимой перед криптоанализом, то из двух вариантов SHA-2-(отбрасывание) и SHA-2-(XOR двух половин), первый будет слегка более стойким (при прочих равных и минимальных доп. затратах на быстродействие хэша).
Как там на самом деле думал НИСТ, точно не указано, но вариант с ксором для построения функций сжатия известен и наверняка он рассматривался. Хотя строгих доказательств, что "отбрасывание лучше ксора" до сих пор нет, вероятно НИСТ решил подстраховаться. Во внутренней структуре — осталось сжатие, снаружи — отбрасывание.
В других стандартах НИСТ также предлагает урезание, а не ксор.
комментариев: 9796 документов: 488 редакций: 5664
Хочется надеться, что в конкурсе SHA-3 победит Keccak (или хотя бы Skein, но он менее удобен), в котором этих проблем вообще не будет и который вытеснит почти все симметричные криптоалгоритмы в силу своей универсальности. Тогда не нужно будет придумывать схемы-велосипеды для того, чтобы правильно и по стандарту сокращать и удлинять. Всё будет заложено в исходном алгоритме.
Кстати, имейте ввиду, что из рекомендаций НИСТ, по ссылке в топике.
комментариев: 9796 документов: 488 редакций: 5664
Совершенно верно. Для того, чтобы стандарты были приняты к использованию в системах национальной безопасности их должно утвердить ещё непосредственно само АНБ, как в случае с AES или ECC. Но само АНБ не даёт подробного обоснования, они или ссылаются на те же стандарты НИСТа, или иногда сами их через НИСТ проталкивают (кстати SHA-0, SHA-1 и SHA-2 были разработаны в АНБ как аналог MD5).
А как же тогда Если считать, что хэши разные, если отличается хоть один символ, то в чём тут брутфорс 128-мибитной случайной строки?
комментариев: 9796 документов: 488 редакций: 5664
128-битный хэш обладает 64-битной стойкостью против нахождения коллизий брутфорсом. Поэтому в SHA-3 также предусмотрен размер хэша от 224 до 512 бит (что даёт 112 и 256 стойкости на подбор коллизий соответственно).
Понятно, но это просто специфика требований конкретного конкурса НИСТ, а не «фундаментальное» свойство любого хэша. Не очень понятно, откуда это требование взялось. С хэшами всё настолько плохо, что замена n/2 на n в потребовала бы исключить всех кандидатов?
Вопрос снят.