Безопасность SHA - раздел Компьютеры, Однонаправленные хэш-функции Sha Очень Похожа На Md4, Но Выдает 160-Битовое Хэш-Значение. Главным Изменени...
SHA очень похожа на MD4, но выдает 160-битовое хэш-значение. Главным изменением является введение расширяющего преобразования и добавление выхода предыдущего шага в следующий с целью получения более быстрого лавинного эффекта. Рон Ривест опубликовал цели, преследуемые им при проектировании MD5, но разработчики SHA этого не сделали. Вот улучшения, внесенные Ривестом в MD5 относительно MD4, и их сравнение с SHA:
1. "Добавился четвертый этап." В SHA тоже. Однако в SHA на четвертом этапе используется та же функция f, что и на втором этапе.
2. "Теперь в каждом действии используется уникальная прибавляемая константа ." SHA придерживается схемы MD4, повторно используя константы для каждой группы их 20 этапов.
3. "Функция G на этапе 2 с ((XaY)v(XaZ)v(YaZ)) была изменена на (XaZ)v(Ya(Z)), чтобы сделать G менее симметричной." В SHA используется версия функции из MD4: (1л 7) v(Xa Z) v (7л Z).
4. "Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быстрый лавинный эффект." Это изменение было внесено и в SHA. Отличие состоит в том, что в SHA добавлена пятая переменная к Ъ, с и d, которые уже используются в ft. Это незначительное изменение делает применения вскрытия MD5 ден Боером и Босселаерсом невозможным по отношению к SHA.
5. "Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3 , чтобы сделать
шаблоны менее похожими." SHA в этом месте совершенно отличается, так как использует циклический код исправления ошибок.
6. "Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для уск о-рения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на других этапах." SHA на каждом этапе использует постоянное значение сдвига. Это значение - взаимно простое число с размером слова, как и в MD4.
Это приводит к следующему заключению: SHA - это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 - это MD4 с улучшенным битовым хэшированием, дополнительным этапом и улучшенным лавинным эффектом .
Сведения об успешных криптографических вскрытиях SHA отсутствуют. Так как эта однонаправленная хэш-функция выдает 160-хэш-значение, она устойчивее к вскрытию грубой силой (включая вскрытие методом дня рождения), чем 128-битовые хэш-функции, рассматриваемые в этой главе .
18.8 RIPE-MD
RIPE-MD была разработана для проекта RIPE Европейского сообщества [1305] (см. раздел 25.7). Этот алгоритм представляет собой вариант MD4, разработанный так, чтобы противостоять известным методам криптографического вскрытия, и выдает 128-битовое хэш-значение . Внесены изменения в циклические сдвиги и порядок слов сообщения. Кроме того, параллельно работают две копии алгоритма, отличающиеся константами . После каждого блока результат обоих копий добавляется к переменным сцепления . По видимому, это повышает устойчивость алгоритма к криптоанализу.
18.9 HAVAL
HAVAL - это однонаправленная хэш-функция переменной длины [1646]. Она является модификацией MD5. HAVAL обрабатывает сообщение блоками по 1024 бита, в два раза большими, чем в MD5. Используется восемь 32-битовых переменных сцепления, в два раза больше, чем в MD5, и переменное число этапов, от трех до пяти (в каждом 16 действий). Функция может выдавать хэш-значения длиной 128, 160, 192, 224 или 256 битов.
HAVAL заменяет простые нелинейные функции MD5 на сильно нелинейные функции 7 переменных, каждая из которых удовлетворяет строгому лавинному критерию . На каждом этапе используется одна функция, но при каждом действии входные переменные переставляются различным образом . Используется новый порядок сообщения, и при каждом этапе (кроме первого этапа) используется своя прибавляемая константа . В алгоритме также используется два циклических сдвига.
H = G; G = F; F = E; E = D; D = C; С = В; В = А; А = TEMP
Переменное количество этапов и переменная длина выдаваемого значения означают, что существует 15 ве р-сий алгоритма. Вскрытие MD5, выполненное ден Боером и Босселаерсом [203], неприменимо к HAVAL из-за циклического сдвига Н.
18.10 Другие однонаправленные хэш-функции
MD3 является еще одной хэш-функцией, предложенной Роном Ривестом . Она имела ряд недостатков и никогда не выходила за пределы лаборатории, хотя ее описание недавно было опубликовано в [1335].
Группа исследователей из Университета Ватерлоо предложила однонаправленную хэш-функцию на базе итеративного возведения в степень в GF(2593) [22]. По этой схеме сообщение разбивается на 593-битовые блоки. Начиная с первого блока блоки последовательно возводятся в степень . Показатель степени - это результат вычислений для предыдущего блока, первый показатель задается с помощью IV.
Айвэн Дамгард (Ivan Damgard) разработал однонаправленную хэш-функцию, основанную на проблеме рю к-зака (см. раздел 19.2) [414], она может быть взломана примерно за 232 операций [290, 1232, 787].
В качестве основы для однонаправленных хэш-функций предлагался и клеточный автомат Стива Вольфрама [1608]. Ранняя реализация [414] небезопасна [1052,404]. Другая однонаправленная хэш-функция, Cellhash [384, 404], и улучшенная версия, Subbash [384,402, 405], также основаны на клеточных автоматах и предназначены для аппаратной реализации. Boognish объединил принципы Cellhash и MD4 [402, 407]. StepRightUp также может быть реализована как хэш-функция [402].
Летом 1991 года Клаус Шнорр (Claus Schnorr) предложил однонаправленную хэш-функцию на базе дис-
кретного преобразования Фурье, названную FFT-Hash [1399]. Через несколько месяцев она была взломана двумя независимыми группами [403, 84]. Шнорр предложил новую версию, FFT-Hash II (предыдущая была переименована в FFT-Hash I) [1400], которая была взломана через несколько недель [1567]. Шнорр предложил дальнейшие модификации [1402, 1403] но, при данных обстоятельствах, они намного медленнее, чем другие алгоритмы этой главы. Еще одна хэш-функция, SL2[1526], небезопасна [315].
Дополнительную информацию по теории проектирования однонаправленных хэш-функций из однонапра в-ленных функций и однонаправленных перестановок можно найти в [412, 1138, 1342].
В качестве однонаправленных хэш-функций можно использовать симметричные блочные алгоритмы ши ф-рования. Идея в том, что если безопасен блочный алгоритм, то и однонаправленная хэш-функция будет без о-пасной.
Самым очевидным способом является шифрование сообщения в режиме СВС или CFB с помощью фиксированного ключа и IV, хэш-значением будет последний блок шифротекста. Эти методы описаны в различных стандартах, использующих DES: оба режима в [1143], СВС в [1145], CFB в [55, 56, 54]. Этот способ не слишком подходит для однонаправленных хэш-функций, хотя он будет работать для MAC (см. раздел 18.14) [29].
Способ поумнее использует в качестве ключа блок сообщения, предыдущее хэш-значение в качестве входа, а текущее хэш-значение служит выходом.
Действительные хэш-функции даже еще сложнее. Размер блока обычно совпадает с длиной ключа, и разм е-ром хэш-значения будет длина блока. Так как большинство блочных алгоритмов 64-битовые, спроектирован ряд схем, дающих хэш-значение в два раза большее длины блока .
При условии, что хэш-функция правильна, безопасность этой схемы основана на безопасности используемой блочной функции. Однако есть и исключения. Дифференциальный криптоанализ лучше работает против блочных функций в хэш-функциях, чем против блочных функций, используемых для шифрования : ключ известен, поэтому можно использовать различные приемы. Для успеха нужна только одна правильная пара, и можно г е-нерировать столько выбранного открытого текста, сколько нужно. Это направление освещается в [1263, 858, 1313].
Ниже приведен обзор различных хэш-функций, описанных в литературе [925, 1465, 1262]. Выводы о возможности вскрытия предполагают, что используемый блочный алгоритм безопасен, и лучшим вскрытием явл я-ется вскрытие грубой силой.
Полезной мерой для хэш-функций, основанных на блочных шифрах, является скорость хэширования,или количество и-битовых блоков сообщения (и - это размер блока алгоритма), обрабатываемых при шифровании. Чем выше скорость хэширования, тем быстрее алгоритм . (Другое определение этого параметра дается в [1262], но определение, приведенное мной, более интуитивно и шире используется . Это может запутать.)
На сайте allrefs.net читайте: Однонаправленные хэш-функции...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Безопасность SHA
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Однонаправленные хэш-функции
18.1 Основы
Однонаправленная функция ЩМ) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h.
h = ЩМ), где
Длины однонаправленных хэш-функций
64-битовые хэш-функции слишком малы, чтобы противостоять вскрытию методом дня рождения . Более практичны однонаправленные хэш-функции, выдающие 128-битовые хэш-значения . При этом, чтобы найти два
Обзор однонаправленных хэш-функций
Не легко построить функцию, вход которой имеет произвольный размер, а тем более сделаьть ее однон а-правленной. В реальном мире однонаправленные хэш-функции строятся на идее функции сжатия.
Криптоанализ Snefru
Используя дифференциальный криптоанализ, Бихам и Шамир показали небезопасность двухпроходного Snefru (с 128-битовым хэш-значением) [172]. Их способ вскрытия за несколько минут обнаруживает пару соо
Описание MD5
После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, к
Безопасность MD5
Рон Ривест привел следующие улучшения MD5 в сравнении с MD4 [1322]:
1. Добавился четвертый этап.
2. Теперь в каждом действии используется уникальная прибавляемая константа .
Описание SHA
Во первых, сообщение дополняется, чтобы его длина была кратной 512 битам . Используется то же дополнение, что и в MD5: сначала добавляется 1, а затем нули так, чтобы длина полученного сообщения бы
Модификация схемы Davies-Meyer
Лай (Lai) и Массей (Massey) модифицировали метод Davies-Meyer, чтобы можно было использовать шифр IDEA [930, 925]. IDEA использует 64-битовый блок и 128-битовый ключ. Вот предложенная ими схема:
Preneel-Bosselaers-Govaerts-Vandewalle
Эта хэш-функция, впервые предложенная в [1266], выдает хэш-значение, в два раза большее длины блока алгоритма шифрования: при 64-битовом алгоритме получается 128-битовое хэш-значение .
При
Quisquater-Girault
Эта схема, впервые предложенная в [1279], генерирует хэш-значение, в два раза большее длины блока. Ее скорость хэширования равна 1. Она использует два хэш-значения, G, и Я„ и хэширует вместе два бл
Тандемная (Tandem) и одновременная (Abreast) схемы Davies-Meyer
Другой способ обойти ограничения, присущие блочным шифрам с 64-битовым ключом, использует алг о-ритм, подобный IDEA (см. раздел 13.9), с 64-битовым блоком и 128-битовым ключом. Следующие две схемы
MDC-2 u MDC-4
MDC-2 и MDC-4 разработаны в IBM [1081, 1079]. В настоящее время изучается вопрос использования MDC-2, иногда называемой Meyer-Schilling, в качестве стандарта ANSI и ISO [61, 765], этот вариант был
Хэш-функция AR
Хэш-функция AR была разработана Algorithmic Research, Ltd. и затем распространена ISO только для информации [767]. Ее базовая структура является вариантом используемого блочного шифра (DES в упомя
Хэш-функция ГОСТ
Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94 [657]. В ней используется блочный алгоритм ГОСТ (см. раздел 14.1), хотя теоретически может использоваться любой блочный а
СВС-МАС
Простейший способ создать зависящую от ключа однонаправленную хэш-функцию - шифрование сообщения блочным алгоритмом в режимах СВС или CFB. Хэш-значением является последний шифрованный блок, зашифр
Методы Джунемана
Этот MAC также называют квадратичным конгруэнтным кодом обнаружения манипуляции ( quadratic con-graential manipulation detection code, QCMDC) [792, 789]. Сначала разделим сообщение на от-битовые бл
RIPE-MAC
RIPE-MAC был изобретен Бартом Пренелом [1262] и использован в проекте RIPE [1305] (см. раздел 18.8). Он основан на ISO 9797 [763] и использует DES в качестве функции блочного шифрования. Существует
IBC-хэш
IBC-хэш - это еще один MAC, используемый в проекте RIPE [1305] (см. раздел 18.8). Он интересен потому, что его безопасность доказана, вероятность успешного вскрытия может быть оценена количественно
Однонаправленная хэш-функция MAC
В качестве MAC может быть использована и однонаправленная хэш-функция [1537]. Пусть Алиса и Боб используют общий ключ К, и Алиса хочет отправить Бобу MAC сообщения М. Алиса объединяе
Безопасность алгоритмов с открытыми ключами
Так как у криптоаналитика есть доступ к открытому ключу, он всегда может выбрать для шифрования любое сообщение. Это означает, что криптоаналитик при заданном C = EKЦP) мож
Создание открытого ключа из закрытого
Рассмотрим работу алгоритма, не углубляясь в теорию чисел : чтобы получить нормальную последовательность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52},
Шифрование
Для шифрования сообщение сначала разбивается на блоки, равные по длине числу элементов последов а-тельности рюкзака. Затем, считая, что единица указывает на присутствие члена последовательности, а
Дешифрирование
Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую поел е-довательность, а также значения я и от, использованные для превращения ее в нормальную последователь
Практические реализации
Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовател ь-ность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов . Дл
Безопасность метода рюкзака
Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов . Сначала был раскрыт единственный бит открытого текста [725]. Затем Шамир показал, что в определенных
Скорость RSA
Аппаратно RSA примерно в 1000 раз медленнее DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем - 64 килобита в секунду [258]. Существуют также микросхемы, которые выполня-
Вскрытие с выбранным шифротекстом против RSA
Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а надстроенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопа
Вскрытие общего модуля RSA
При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль я, но каждому свои значения показателей степени е и d. К сожалению, это не работает. Наиболее очевидная проб
Вскрытие малого показателя шифрования RSA
Шифрование и проверка подписи RSA выполняется быстрее, если для е используется небольшое значение, но это также может быть небезопасным [704]. Если е(е + 1)/2 линейно
Полученные уроки
Джудит Мур (Judith Moore) на основании перечисленных вскрытий приводит следующие ограничения RSA [1114, 1115]:
— Знание одной пары показателей шифрования/дешифрирования для данного модуля
Вскрытие шифрования и подписи с использованием RSA
Имеет смысл подписывать сообщение перед шифрованием (см. раздел 2.7), но на практике никто не выполняет этого. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания [48].
Стандарты
RSA de facto является стандартом почти по всему миру. ISO почти, but not quite, created an RSA digital-signature standard; RSA служит информационным дополнением ISO 9796 [762.]. Французское
Патенты
Алгоритм RSA запатентован в Соединенных Штатах [1330], но ни водной другой стране. РКР получила лицензию вместе с другими патентами в области криптографии с открытыми ключами (раздел 25.5). Срок д
Патенты
Алгоритм Pohlig-Hellman запатентован в США [722] и в Канаде. РКР получила лицензию вместе с другими патентами в области криптографии с открытыми ключами (см. раздел 25.5).
19.5 Rabin
Шифрование EIGamal
Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения М сначала выбирается случайное число к, взаимно простое ср - 1. Затем вычисляются
Патенты
EIGamal незапатентован. Но, прежде чем двигаться вперед и реализовывать алгоритм, нужно знать, что РКР считает, что этот алгоритм попадает под действие патента Диффи-Хеллмана [718]. Однако срок дей
Алгоритм цифровой подписи (DIGITAL SIGNATURE ALGORITHM, DSA)
В августе 19991 года Национальный институт стандартов и техники (National Institute of Standards and Technology, NIST) предложил для использования в своем Стандарте цифровой подписи (Digital Signa
Битовым показателем степени (на SPARC II)
512 битов 768 битов 1024 бита
Подпись 0.20 с 0.43 с 0.57 с
Проверка 0.35 с 0.80 с 1.27 с
Практические реализации DSA часто можно ускорить с помощью предварительных вычисл
Генерация простых чисел DSA
Ленстра и Хабер указали, что взломать некоторые модули намного легче, чем другие [950]. Если кто-нибудь заставит пользователей сети использовать один из таких слабых модулей, то их подписи будет ле
Безопасность DSA
С 512 битами DSA недостаточно надежен для длительной безопасности, но он вполне надежен при 1024 б и-тах. В своем первом заявлении на эту тему NSA так комментировало утверждение Джо Эбернети (Joe A
Вскрытия к
Для каждой подписи нужно новое значение к, которое должно выбираться случайным образом. Если Ева узнает к, которое Алиса использовала для подписи сообщения, может быть воспользовавши
Опасности общего модуля
Хотя DSS не определяет применение пользователями общего модуля, различные реализации могут воспол ь-зоваться такой возможностью. Например, Налоговое управление рассматривает использование DSS для э
Дискретных логарифмов
Уравнение подписи Уравнение проверки
(1) r'k=s+mx mod q
(2) r'k=m+sx mod q
(3) sk= r'+mx mod q
/-gy-mod p
ONG-SCHNORR-SHAMIR
Эта схема подписи использует многочлены по модулю п [1219, 1220]. Выбирается большое целое число (знать разложение п на множители не обязательно). Затем выбирается случайное число
Безопасность ESIGN
Когда этот алгоритм был впервые предложен, к было выбрано равным 2 [1215]. Такая схема быстро была взломана Эрни Брикеллом (Ernie Brickell) и Джоном ДеЛаурентисом [261], которые распространи
Патенты
ESICN запатентован в Соединенных Штатах [1208], Канаде, Англии, Франции, Германии и Италии. Любой, кто хочет получить лицензию на алгоритм, должен обратиться в Отдел интеллектуальной собственности
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов