Управление ключами шифрования и безопасность сети

Криптографические хэш-функции

Разбить на страницы
Показывать лекцию целиком

2.1. Введение

Рассмотренная в лекции 11 криптографическая хэш-функция получает сообщение произвольной длины и создает дайджест сообщения фиксированной длины. Окончательная цель этой главы состоит в том, чтобы обсудить детали двух наиболее перспективных криптографических алгоритмов хэширования - SHA-512 и Whirlpool. Однако мы сначала должны обсудить некоторые общие идеи, которые могут быть применены к любой криптографической хэш-функции.

Итеративная хэш-функция

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

Схема Меркеля-Дамгарда (Merkle-Damgard)

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

(рис 2.1) Схема Меркеля-Дамгарда

Схема использует следующие шаги:

  • Длина сообщения и дополнение добавляются в конец сообщения, чтобы создать увеличенное сообщение, которое может быть равномерно разделено на n -битовые блоки; здесь n - размер блока, который будет обработан функцией сжатия.
  • Сообщение тогда рассматривают как t блоков, размер каждого состоит из n бит. Мы обозначим каждый блок М1,..., Мt. Мы обозначаем дайджест, созданный при t итерациях, - H1, H2,...., Ht
  • Перед стартом итерации дайджест H0 устанавливается на фиксированное значение, обычно называемое IV (начальное значение или начальный вектор).
  • Функция сжатия при каждой итерации обрабатывает Hi-1 и М., создавая новый Hi. Другими словами, мы имеем Hi = .f (Hi-1, Мi), где f - функция сжатия.
  • Ht - функция криптографического хэширования первоначального сообщения, то есть h(M).Если функция сжатия в схеме Меркеля-Дамгарда устойчива к коллизии, хэш-функция также устойчива к коллизии.

    • Две группы функций сжатия

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

    Хэш-функции, сделанные на "пустом месте"

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

    Дайджест сообщения (MD)

    Несколько алгоритмов хэширования были разработаны Роном Ривестом. Они известны в литературе как MD2, MD4 и MD5, где MD обозначает Дайджест Сообщения. Последняя версия, MD5, является усиленной версией MD4, которая делит сообщение на блоки по 512 битов и создает дайджест на 128 битов. Оказалось, что дайджест сообщения размером 128 битов - слишком маленький, чтобы быть устойчивым к атаке коллизии.

    Алгоритм безопасного хэширования (SHA - Secure Hash Algorithm)

    Алгоритм безопасного хэширования (SHA) - стандарт, который был разработан национальным Институтом Стандартов и Технологии (NIST - National Institute of Standards and Technology) и издан как Федеральный Стандарт Обработки Информации (FIP 180). Он упоминается в литературе как Стандарт Безопасного хэширования ( SHS - Secure Hash Standard ). Стандарт главным образом базируется на MD5. В 1995 г. он был пересмотрен под названием FIP 180-1, который включает SHA-1. Позже он снова был пересмотрен под названием FIP 180-2, который определяет четыре новых версии: SHA-224, SHA-256, SHA-384 и SHA-512. табл. 2.1 дает список некоторых из характеристик этих версий.

    Характеристики алгоритмов безопасного хэширования (SHAs)
    Характеристики SHA-1 SHA-224 SHA-256 SHA-384 SHA-512
    Максимальный размер сообщения 264 - 1 264 - 1 264 - 1 2128 - 1 2128 - 1
    Размер блока 512 512 512 1024 1024
    Размер дайджеста сообщения 160 224 256 384 512
    Число раундов 80 64 64 80 80
    Размер слова 32 32 32 64 64

    Все эти версии имеют одну и ту же структуру. SHA-512 будет рассмотрен подробно позже в этой лекции.

    Другие Алгоритмы сохранения целостности (RIPMD - RACE Integrity Primitives Evaluation Message Digest).Группа алгоритмов криптографического хэширования( RIPMD ) имеет несколько версий. RIPEMD-160 - алгоритм хэширования с дайджестом сообщения на 160 битов. RIPEMD-160 использует ту же структуру, что и MD5, но применяет два варианта выполнения.

    HAVAL - алгоритм хэширования переменной длины с дайджестом сообщения размера 128, 160, 192, 224 и 256. Размер блока - 1024 бита.

    Хэш-функции, основанные на блочных шифрах

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

    Схема Рабина. Итеративная хэш-функция, предложенная Рабиным, очень проста. Схема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования. Блок сообщения используется как ключ; предварительно созданный дайджест используется как исходный текст. Зашифрованный текст - новый дайджест сообщения. Обратите внимание, что размер дайджеста - это размер блочного шифра данных в основной криптографической системе. Например, если DES используется как блочный шифр, размер дайджеста - только 64 бита. Хотя схема очень проста, она может быть раскрыта с помощью атаки "сведения к середине", рассмотренной в лекции 6, поскольку противник может применить алгоритм дешифрования криптографической системы. Рис. 2.2 показывает схему Рабина.

    (рис 2.2) Схема Рабина

    Схема Девиса-Мейера (Davies-Mayer). В основном она повторяет схему Рабина, за исключением того, что использует прямую связь для защиты от атаки "сведения в середину".

    (рис 2.3) Схема Девиса-Мейера

    Схема Матиса-Мейера-Осеаса (Metyas-Mayer-Oseas). Это версия схемы Девиса-Мейера: блоки сообщения применяются как ключи криптосистемы. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, AES хорошо подходит для этой цели.

    (рис 2.4) Схема Матиса-Мейера-Осеаса

    Схема Миагучи-Пренеля - расширенная версия схемы Матиса-Мейера-Осеаса. Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью ИСКЛЮЧАЮЩЕГО ИЛИ и создают новый дайджест. Эта схема используется в Whirlpool для создания хэш-функции. На рис. 2.5 показана схема Миагучи-Пренеля.

    (рис 2.5) Схема Миагучи-Пренеля

    2.2. SHA-512

    версия SHA (Secure Hash Algorithm) - алгоритм безопасного хэширования с 512-битовым дайджестом сообщения. Эта версия похожа на другие алгоритмы этого семейства, которые основаны на схеме Меркеля-Дамгарда. Мы выбрали для рассмотрения особую версию. Она самая поздняя, обладает более полной структурой, чем другие, и наиболее длинным дайджестом сообщения. Если понять эту версию, нетрудно будет усвоить структуру других версий.

    Введение

    SHA-512 создает дайджест из сообщения, содержащего много блоков. Каждый блок имеет длину 1024 бита, как это показано на рис. 2.6.

    (рис 2.6) Создание дайджеста сообщения SHA-512

    Дайджест вначале устанавливается на определенное заранее значение 512 битов. Алгоритм смешивает это начальное значение с первым блоком сообщения, чтобы создать первый промежуточный дайджест сообщения 512 битов. Этот дайджест затем смешивается со вторым блоком, чтобы создать второй промежуточный дайджест. Наконец, (N - l) -ый дайджест смешивается с N -ым блоком - они создают N -ый дайджест. Когда последний блок обработан, результирующий дайджест - это дайджест полного сообщения.

    Подготовка сообщения

    SHA-512 требует, чтобы длина первоначального сообщения была меньше, чем 2128 битов. Если длина сообщения равна или больше, чем 2128, оно не будет обработано SHA-512. Это обычно не проблема, потому что 2128 битов превосходят возможную сегодня полную емкость хранения любой системы.

    SHA-512 создает дайджест сообщения на 512 битов из сообщения меньшего, чем 2128.

    Пример 2.1

    Этот пример показывает, что ограничение длины сообщения SHA-512 - не серьезная проблема. Предположим, что мы должны передать сообщение длиною 2128 бита в секунду. Какое время потребуется для системы коммуникаций со скоростью передачи данных 264 бита в секунду, чтобы передать это сообщение?

    Решение

    Системы коммуникаций, которая может передать 264 бита в секунду, пока еще не существует. Даже если бы она была, потребовалось бы много лет, чтобы передать это сообщение. Отсюда ясно, что мы не должны волноваться по поводу ограничения длины сообщения для SHA-512.

    Пример 2.2

    Этот пример также касается длины сообщения в SHA-512. Сколько страниц занимает сообщение 2128 бит?

    Предположим, что символ имеет длину 32 или 26 бит. Каждая страница - меньше, чем 2048, или приблизительно 212, символов. Тогда 2128 битов требуют по крайней мере 2128/218, или 2110 страниц. И снова ясно, что мы не должны волноваться об ограничении на длину сообщения.

    Поле длины и заполнение

    Прежде чем дайджест сообщения может быть создан, SHA-512 требует сложения поля длины - это целое число без знака на 128 битов, которое определяет длину сообщения в битах, - с сообщением. Это длина первоначального сообщения перед заполнением. Поле целого числа без знака 128 битов можно определить как число между 0 и 2128 - 1, которое является максимальной длиной сообщения, принятого в SHA-512. Поле длины определяет длину первоначального сообщения перед его сложением или заполнением (рис. 2.7).

    (рис 2.7) Заполнение и поле длины в SHA-512

    Перед сложением поля длины мы должны дополнить первоначальное сообщение, чтобы сделать длину кратной 1024. Для поля длины резервируется 128 битов, как показано на рис. 2.7. Длина области заполнения может быть рассчитана следующим образом. Пусть |M| - длина первоначального сообщения и |P| - длина поля заполнения.

    ( M  +  P  + 128) = 0 mod 1024 ->   P   = (- M   - 128) mod 1024

    Формат заполнения - это одна 1, сопровождаемая необходимым числом нулей (0).

    Пример 2.3

    Какое число битов заполнения необходимо, если длина первоначального сообщения - 2590 битов?

    Решение

    Мы можем вычислить число битов заполнения следующим образом:

    P = (-2590 -128) mod 1024 = -2718 mod  1024 = 354

    Заполнение состоит из одной 1, сопровождаемой 353 нулями.

    Пример 2.4

    Нужно ли заполнение, если длина первоначального сообщения уже кратна 1024 битам?

    Решение

    Да, нужно, потому что мы должны добавить поле длины. Заполнение необходимо, чтобы сделать и новый блок кратным 1024 битам.

    Пример 2.5

    Каково минимальное и максимальное число битов заполнения, которые можно добавить к сообщению?

    Решение

    Минимальная длина заполнения - 0, и это случается, когда (-M - 128) mod 1024 = 0 ; тогда |M| = -128 mod 1024 = 896 mod 1024 бит. Другими словами, последний блок в первоначальном сообщении - 896 битов. Мы добавляем поле длины на 128 битов, чтобы сделать блок полным.

    Максимальная длина заполнения - 1023, и это случается, когда (- M - 128) = 1023 mod 1024. Это означает, что длина первоначального сообщения - M = (-128 - 1023) mod 1024 или M = 897 mod 1024. В этом случае мы не можем просто добавить область длины, потому что длина последнего блока будет превышать на один бит число 1024. Так что мы нуждаемся в заполнении 127 битами, чтобы закончить этот блок и создать второй блок заполнения 896 битов. Теперь можно добавить поле длины, чтобы сделать этот блок полным.

    Слова

    SHA-512 оперирует словами; он - ориентируемый на слово. Слово определено длиной 64 бита. Это означает, что после того как заполнение и поле длины добавляются к сообщению, каждый блок сообщения состоит из шестнадцати слов по 64 бита. Дайджест сообщения также образуется из слов по 64 бита, но дайджест сообщения - только восемь слов, и слова обозначают A, B, C, D, E, F, G и H, как показано на рис. 2.8.

    (рис 2.8) Блок сообщения и дайджест в виде отдельных словSHA-512 - алгоритм, ориентированный на слово. Каждый блок - 16 слов; в дайджесте - только 8 слов.

    Расширение слова

    Перед обработкой каждый блок сообщения должен быть расширен. Блок образован из 1024 битов, или шестнадцати слов по 64 бита. Как мы увидим позже, в фазе обработки нам нужно 80 слов. Так что блок с 16-ю словами должен быть расширен до 80 слов от W0 до W79. рис. 2.9 показывает процесс расширения слова. Блок на 1024 бита порождает первые слова; остальная часть слов получается от уже сделанных слов согласно операциям, которые показаны на рисунке.

    (рис 2.9) Расширение слова в SHA -52

    Пример 2.6

    Показать, как получить W60.

    Решение

    Каждое слово в диапазоне W16 до W79 получено в результате обработки четырех слов, созданных предварительно на предыдущих шагах. W60 получено как

    $$W_{60} = W_{44} \oplus RotShift _{1-8-7} (W_{45}) \oplus W_{53} \oplus RotShift _{19 -61-6}(W_{58})$$

    Инициализация дайджеста сообщения

    Алгоритм использует восемь констант для инициализации дайджеста сообщения. Мы обозначаем их от A0 до H0, что соответствует обозначению слов, используемых для дайджеста. табл. 2.2 показывает значение этих констант.

    Значение констант при инициализации дайджеста сообщения SHA-512
    Буфер Значение (шестнадцатеричное) Буфер Значение (шестнадцатеричное)
    A0 6A09E667F3BCC908 E0 510E527FADE682D1
    B0 3B67AE8584CAA73B F0 9B05688C2B3E6C1F
    C0 3C6EF372EF94F828 G0 1F83D9ABFB41BD6B
    D0 A54FE53A5F1D36F1 H0 5BEOCD19137E2179

    Читатель может задаться вопросом, откуда взяты эти значения. Они рассчитаны из первых восьми простых чисел (2, 3, 5, 7, 11, 13, 17 и 19). Каждое значение - дробная часть квадратного корня соответствующего простого числа после преобразования к двоичной форме и сохранения только первых 64 битов. Например, восьмое простое число - 19 имеет квадратный корень (191/.2) = 4,35889894354. Преобразовывая число к двоичной форме только с 64 битами в дробной части, мы имеем

    (100.0101 1011 1110... 1001)2 -> (4,5BEOCD19137E2179)16

    SHA-512 сохраняет дробную часть (5BEOCD19137E2179)16 как целое число без знака.

    Функция сжатия

    SHA-512 создает 512 битов дайджест-сообщения (восемь слов на 64 бита) из сообщения, которое состоит из множества блоков, где каждый блок содержит 1024 бита. Обработка каждого блока данных в SHA-512 включает 80 раундов. рис. 2.10 показывает общую схему сжатия функции. В каждом раунде содержание восьми предыдущих буферов - это одно слово из расширенного блока ( Wi ), и одна константа на 64 бита ( Ki ), смешанные вместе. Они обработаны затем, чтобы создать новое множество из восьми буферов. В начале обработки значения восьми буферов сохранены как восемь временных переменных. В конце обработки (после того как сделан шаг 79) эти значения добавляются к значениям, созданным на шаге 79. Мы вызываем эту последнюю операцию финальным сложением, как это показано на рисунке.

    (рис 2.10) Функция сжатия в SHA-512

    Структура каждого раунда

    (рис 2.11) Структура каждого раунда SHA-512

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

    A -> B     B -> C    C  -> D    E -> F   F -> G    G -> H

    Два новых буфера, A и E, получают соответствующие значения от некоторых сложных функций, которые включают в себя некоторые значения предыдущих буферов, соответствующее слово для этого раунда (Wi) и константу для этого раунда (Ki). Рис. 2.11 показывает структуру каждого раунда.

    Здесь есть два смесителя, три функции и несколько операторов. Каждый смеситель обрабатывает две функции. Описание функций и операторов приведено ниже.

  • То, что мы называем мажоритарной функцией, является поразрядной функцией. Она использует три соответствующих бита в трех буферах ( A, B и C ) и вычисляет$$( A_{j} \ AND \ B_{j}) \oplus (B_{j} \ AND \ C_{j}) ) \oplus (C_{j} \ AND \ A_{j})$$

    Результат - это значение, которое имеет большинство из трех бит. Если два или три бита равны единице (1) , то результат имеет значение бит 1; иначе он равен 0.

    Функция, которую мы называем условной функцией ( Conditional ) - также поразрядная функция. Она использует три бита, которые содержатся в трех буферах ( E, F и G ), и вычисляет

    $$(E_{j } \ AND \ F_{j}) \oplus (NOT \ E_{j } \ AND \ G_{j})$$

    Результат подчиняется логике "Если E, то F ; иначе G ".

  • Функция "циклическое перемещение" (Rotate) обрабатывает три значения одного и того же буфера ( A или E ) и применяет операцию ИСКЛЮЧАЮЩЕЕ ИЛИ с результатом мажоритарной функции.$$Rotate (A): RotR_{28 }(A) \oplus RotR_{34} (A) \oplus RotR_{29}(A) \\ Rotate (E): RotR_{28 }(A) \oplus RotR_{34} (E) \oplus RotR_{29}(E)$$
  • Функция "циклическое перемещение вправо" (RotRi (x) ) - та же самая, которую мы использовали в процессе расширения слова.
  • Оператор сложения, применяемый в процессе, - сложение по модулю 264. Он означает результат сложения двух или больше буферов, содержащих всегда слово на 64 бита.
  • Есть 80 констант, K0 к K79, каждая по 64 бита, как показано в табл. 2.3 в шестнадцатеричной форме (четыре в каждой строке таблицы). Аналогично начальным значениям для восьми буферов, эти значения вычислены из первых 80 простых чисел ( 2, 3..., 409 ).
    •
    Восемьдесят констант, используемых для восьмидесяти раундов в SHA-512
    428A2F98D728AE22 7137449123EF65CD B5COFBCFEC4D3B2F E9B5DBA58189DBBC
    3956C25BF348B538 59F111F1B605D019 923F82A4AF194F9B AB1C5ED5DA6D8118
    D807AA98A3030242 12835B0145706FBE 243185BE4EE4B28C 550 C7DC3D5FFB4E2
    72BE5D74F27B896F 80DEB1FE3B1696B1 9BDC06A725C71235 C19 BF1 74CF 692694
    E49B69C19EF14AD2 EFBE4786384F25E3 OFC19DC68B8CD5B5 240 CA1CC77AC9C65
    2DE92C6F592B0275 4A7484AA6EA6E483 5CBOA9DCBD41FBD4 76F 9 8 8DA831 153B5
    983E5152EE66DFAB A831C66D2DB43210 B00327C898FB213F BF5 97FC7 BEEF0EE4
    C6EOOBF33DA88FC2 D5A79147930AA725 06CA6351E003826F 142 92 967 0AOE6E70
    27B70A8546D22FFC 2E1B21385C26C926 4D2C6DFC5AC42AED 533 80 D1 39D95B3DF
    650A73548BAF63DE 766AOABB3C77B2A8 81C2C92E47EDAEE6 92722 C8 514 823 53B
    A2BFE8A14CF10364 A81A664BBC423001 C24B8B70DOF89791 C76C5 1A 30 6 54BE30
    D192E819D6EF5218 D69906245565A910 F40E35855771202A 106AA 07 032BBD1B8
    19A4C116B8D2DOC8 1E376C085141AB53 2748774CDF8EEB99 34BOBCB 5E 19B4 8A8
    391COCB3C5C95A63 4ED8AA4AE3418ACB 5B9CCA4F7763E373 682 E 6FF 3D6B2B8A3
    748F82EE5DEFB2FC 78A5636F43172F60 84C87814A1FOAB72 8CC7 020 81A 6439EC
    90BEFFFA23631E28 A4506CEBDE82BDE9 BEF9A3F7B2C67915 C671 78F 2E372532B
    CA273ECEEA26619C D186B8C721COC207 EADA7DD6CDEOEB1E F57D 4F7 FEE6E178
    06F067AA72176FBA OA637DC5A2C898A6 113F9804BEF90DAE 1B71 0B3 5131C471B
    28DB77F523047D84 32CAAB7B40C72493 3C9EBEOA15C9BEBC 431D 67C 49C100D4C
    4CC5D4BECB3E42B6 4597F299CFC657E2 5FCB6FAB3AD6FAEC 6C44 198 C4A475 817

    Каждое значение - дробная часть кубического корня из соответствующего простого числа после преобразования этого числа к двоичной форме, сохраняются только первые 64 бита. Например, 80-е простое число - ( 409 ). Кубический корень (409) 1/3 = 7,42291412044. Преобразовывая это число к двоичному виду только с 64 битами в дробной части, мы получаем

    (111,0110 1100 0100 0100...0111) 2 -> (7,6C44198C4A475817).

    SHA-512 сохраняет дробную часть, (6C44198C4A475817)16, как целое число без знака.

    Пример 2.7

    Мы применяем мажоритарную функцию к значениям буферов A, B и C. Если крайние левые шестнадцатеричные цифры этих буферов - 0x7, 0xA и 0xE соответственно, то какая цифра будет крайней левой частью результата?

    Решение

    Цифры в двоичной форме - 0111, 1010 и 1110.

  • Первые биты - 0, 1 и 1. Мажоритарная функция равна 1. Мы можем доказать это, используя определение мажоритарной функции:$$(0 \ AND \ 1) \oplus (1 \ AND \ 1) \oplus C (1 \ AND \ 0) = 0 \oplus 1 \oplus 0 = 1$$
  • Вторые биты - 1, 0 и 1. Мажоритарная функция равна 1 .
  • Третьи биты - 1, 1 и 1. Мажоритарная функция равна 1.
  • Четвертые биты - 1, 0 и 0. Мажоритарная функция равна 0. Результат - 1110, или 0xE в шестнадцатеричной форме.
    •

    Пример 2.8

    Мы применяем условную функцию ( Conditional ) для буферов E, F и G. Если крайние левые шестнадцатеричные цифры этих буферов - 0x9, 0xE и 0xF соответственно, то какая цифра будет крайней левой частью результата?

    Решение

    Цифры в двоичной форме - 1001, 1110 и 1111.

  • Первые биты - 1,1 и 1. Следовательно, E1 = 1, результат - F1, который равен 1. Чтобы доказать результат, мы можем также использовать определение функции Condition:$$(1 \ AND \ 1) \oplus (NOT \ 1 \ AND \ 1) = 1 \oplus 0 = 1$$
  • Вторые биты - 0, 0 и 1. Следовательно, E2 - 0, результат - F3, который равен 1.
  • Третьи биты образовывают дугу 0, 1 и 1. Следовательно, E3 - 0, результат - G3, который равен 1.
  • Четвертые биты - 1, 0 и 1. Следовательно, E4 - 1, результат - F4, который равен 0. Результат - 1110, или 0x1 в шестнадцатеричной форме.
    •

    Анализ

    С дайджестом сообщения 512 битов от SHA-512 ожидалось, что он будет более стойким ко всем типам атак, включая атаки коллизии. Он должен был быть лучшим проектом этой версии: более эффективным и более безопасным, чем предыдущие. Однако необходимы были серьезные исследования и испытания, для того чтобы это подтвердить.

    2.3. Whirlpool

    Whirlpool разработан Винсентом Риджменом (Vincent Rijmen) и Пауло Баретто (Paolo Barreto). Он одобрен европейской организацией NESSIE ( New European Schemes for Signature, Integrity and Encryption - Новые европейские схемы подписей, целостности и шифрования ).

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

    (рис 2.12) Whirlpool хэш-функция

    Подготовка

    Перед стартом алгоритма хэширования сообщение должно быть готово к процессу. Whirlpool требует, чтобы длина первоначального сообщения была меньше, чем 2256 бита. Сообщение должно быть дополнено прежде, чем начать обработку. Дополнение содержит единственный бит, равный 1, а затем следует необходимое чисел нулевых битов, чтобы сделать длину дополнения нечетным числом, кратным 256 битам. После дополнения добавляется блок 256 битов, чтобы указать длину первоначального сообщения. Этот блок обрабатывается как число без знака.

    После дополнения первоначального сообщения и присоединения поля длины увеличенный размер сообщения становится кратным 256 битам или кратным 512 битам. Whirlpool создает дайджест 512 из сообщения, состоящего из многих блоков по 512 бит. Дайджест из 512 бит, H0, начинается всеми нулями. Это становится ключом шифра для шифрования первого блока. Из зашифрованного текста каждого зашифрованного блока получают ключ шифра для следующего блока после того, как его складывают по модулю два с предыдущим ключом шифра и блоком исходного текста. Дайджест сообщения - конечный зашифрованный текст на 512 битов после последней операции ИСКЛЮЧАЮЩЕЕ ИЛИ.

    Шифр Whirlpool

    Шифр Whirlpool - шифр не-Файстеля, похож на AES и был главным образом, разработан как блочный шифр, который используется в алгоритме хэширования. Вместо того чтобы дать полное описание этого шифра, мы будем исходить из того, что читатель знаком с AES по материалам Главы 7. Ниже только приводится сравнение шифра Whirlpool с шифром AES и отмечается их отличие.

    Раунды

    Whirlpool - шифр, который использует 10 раундов. Размер блока и ключевой размер - 512 битов. Шифр применяет 11 ключей раунда K0 - K10, каждый по 512 битов. рис. 2.13 показывает общий вид процесса шифрования шифром Whirlpool.

    (рис 2.13) Общая идея шифра Whirlpool

    Матрицы состояний и блоки

    Подобно шифру AES, шифр Whirlpool использует матрицы состояний и блоки. Однако размер блока или матрицы состояний - 512 битов. Блок рассматривается как строка матрицы длиной 64 байта; матрица состояний - как квадратная матрица 8 x 8 байтов. В отличие от AES преобразование "блок - матрица состояний" или "матрица состояний - блок" происходят строка за строкой. рис. 2.14 показывает блок, матрицу состояний и преобразование в шифр Whirlpool.

    (рис 2.14) Блок и матрица состояний шифра Whirlpool

    Структура каждого раунда

    Рис. 2.15 показывает структуру каждого раунда. Каждый раунд использует четыре преобразования.

    (рис 2.15)

    SubBytes. Подобно AES, SubBytes обеспечивает нелинейное преобразование. Байт представлен как две шестнадцатеричных цифры. Левая цифра определяет строку, а правая - столбец таблицы подстановки. Две шестнадцатеричных цифры в пересечении строки и столбца - новый байт. рис. 2.16 иллюстрирует идею.

    (рис 2.16) Преобразование SubBytes шифра Whirlpool

    В преобразовании SubBytes матрица состояний обрабатывается как матрица байтов 8 x 8. Преобразование делается одновременно только с одним байтом. Содержание каждого байта изменяется, но порядок следования байтов в матрице остается тем же самым. В процессе каждый байт преобразуется независимо; мы имеем 64 различных преобразований байт-к-байту.

    Таблица 2.4 показывает таблицу подстановки (S-блок) для преобразования подбайтов. Преобразование обеспечивает эффект перемешивания. Например, два байта, 5A16 и 5B16, которые отличаются только одним битом (самый правый бит), преобразованы к 5B16 и 8816, которые отличаются пятью битами.

    Таблица преобразования SubBytes (S-Box)
    0 / 2 3 4 5 6 7 8 9 A B C D E F
    0 18 23 C6 E8 87 B8 01 4F 36 A6 D2 F5 79 6F 91 52
    1 16 BC 9B 8E A3 0C 7B 35 1D E0 D7 C2 2E 4B FE 57
    2 15 77 37 E5 9F F0 4A CA 58 C9 29 0A B1 A0 6B 85
    3 BD 5D 10 14 CB 3E 05 67 E4 27 41 8B A7 7D 95 C8
    4 FB EF 7C 66 DD 17 47 9E CA 2D BF 07 AD 5A 83 33
    5 63 02 AA 71 C8 19 49 C9 F2 E3 5B 88 9A 26 32 BO
    6 E9 OF D5 80 BE CD 34 48 FF 7A 90 5F 20 68 1A AE
    7 B4 54 93 2'2 64 F1 73 12 40 08 C3 EC DB A1 8D 3D
    8 97 00 CF :B 76 82 D6 1B B5 AF 6A 50 45 F3 30 EF
    9 3F 55 A2 EA 65 BA 2F CO DE 1C FD 4D 92 75 06 8A
    A B2 E6 OE F 62 D4 A8 96 F9 C5 25 59 84 72 39 4C
    B 5E 7S 38 8C C1 A5 E2 61 B3 21 9C 1E 43 C7 FC 04
    C 51 99 6D 0D FA DF 7E 24 3B AB CE 11 8F 4E B7 EB
    D 3C S1 94 '-7 9B 13 2C D3 E7 6E C4 03 56 44 7E A9
    E 2A BB C1 53 DC OB 9D 6C 31 74 F6 46 AC 89 14 E1
    F 16 3A 69 09 70 B6 CO ED CC 42 98 A4 28 5C F8 86

    Входы в табл. 2.4 могут быть вычислены алгебраически, используя поле G(24) с неприводимым полиномом (x4 + x + 1), как показано на рис. 2.17. Каждая шестнадцатеричная цифра в байте вводится в миниблок ( E и E-1 ). Результаты передаются в другой миниблок R. E -блоки вычисляют степень, равную шестнадцатеричному значению входа; R -миниблок использует псевдослучайный генератор чисел.

    (рис 2.17) Операция SubBytes шифра Whirlpool $$E(вход) = (x^{3} +x+1)^{вход} \ mod (x^{4} + x + 1), \ если \ вход \ne 0xF \\ E(0xF) = 0$$

    E-1 -блок - это только инверсия E -блока, где роли входов и выходов изменились. Значения входа-выхода для блоков сведены в таблицу на рис. 2.17.

    ShiftColumns . Чтобы обеспечить перестановку, Whirlpool использует преобразование ShiftColumns , которое является подобным преобразованию ShiftRows в AES, за исключением того, что вместо строк сдвигаются столбцы. Смещение зависит от позиции столбца. Столбец 0 сдвигается на 0 байтов (смещения нет), в то время как столбец 7 сдвигается на 7 байтов. рис. 2.18 показывает преобразование смещения.

    (рис 2.18) Преобразование ShiftColumns шифра Whirlpool

    MixRows.Преобразование MixRows имеет тот же самый эффект, что и преобразование MixColumns в AES: оно рассеивает биты. Преобразование MixRows - матричное преобразование, где байты интерпретируются как слова по 8 битов (или полиномы) с коэффициентами в GF(28). Умножение байтов проводится в GF(28), но модуль отличается от используемого в AES. Шифр Whirlpool применяет ( 0x11 D ) или ( x8 + x4 + x3 + x2 + 1 ) как модуль. Сложение слов по 8 битов - то же самое, что ИСКЛЮЧАЮЩЕЕ ИЛИ. На рис. 2.19 представлено преобразование MixRows.

    (рис 2.19) Преобразование MixRows шифра Whirlpool

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

    AddRoundKey. Преобразование AddRoundKey в шифре Whirlpool делается байт за байтом, потому что каждый ключ раунда - матрица состояний 8 x 8 байт. рис. 2.20 показывает этот процесс. Байт матрицы состояний данных складывается в поле GF(28) с соответствующим байтом матрицы состояний ключей раунда. Результат - новый байт в новой матрице состояний.

    (рис 2.20) Преобразование AddRoundKey шифра Whirlpool

    Расширение ключа

    Как показывает рис. 2.21, алгоритм расширения ключей в Whirlpool полностью отличается от алгоритма в AES. Вместо того чтобы применять новый алгоритм создания ключей раунда, Whirlpool использует копию алгоритма шифрования (без предраунда), чтобы создать ключи раунда. Выход каждого раунда в алгоритме шифрования есть ключи для этого раунда. На первый взгляд это напоминает определение, где ключи раунда для алгоритма расширения ключа получаются из него самого. Откуда получается алгоритм расширения? Whirlpool изящно решил эту проблему, используя десять констант раунда ( RC ) как виртуальные ключи раунда для алгоритма расширения ключей. Другими словами, алгоритм расширения ключей применяет константы как ключи раунда. Алгоритм шифрования использует выход каждого раунда алгоритма расширения ключей как ключи раунда. Алгоритм генерирования ключей обрабатывает ключ шифра как исходный текст и зашифровывает его. Обратите внимание, что ключ шифра - также К0 для алгоритма шифрования.

    (рис 2.21) Расширение ключа шифра Whirlpool

    Константы раунда. Каждая константа раунда RCr является матрицей 8 x 8, где только первая строка имеет значения, отличные от нуля. Остальная часть входов содержит все нули. Значения для первой строки в каждой матрице констант могут быть вычислены, используя преобразование SubBytes ( табл. 2.4).

    RC round[строка, столбец] = Subbytes (8 (round -1) + столбец)   если  строка = 0 
RCround [строка, столбец] = 0   если строка ^ 0

    Другими словами, RC1 использует первые восемь входов в таблице преобразования SubBytes ( табл. 2.4); RC2 использует вторые восемь входов, и т. д. рис. 2.22 показывает пример RC3, где первая строка - третьи восемь входов в таблице SubBytes.

    (рис 2.22) Константы для третьего раунда

    Итоги шифра Whirlpool.

    В табл. 2.5 приведены основные характеристики шифра Whirlpool.

    Основные характеристики шифра Whirlpool
    Размер блока: 512 бит
    Размер ключа шифра: 512 бит
    Число раундов: 10
    Расширение ключа: использование шифра непосредственно с константами раунда в качестве ключей раунда
    Подстановка: Преобразование SubBytes
    Перестановка: Преобразование ShiftColumns
    Смешивание: Преобразование MixRows
    Константы раунда: кубические корни первых восьмидесяти простых чисел

    Анализ

    Хотя Whirlpool не был всесторонне изучен или проверен, он базируется на устойчивой схеме Миагучи-Пренеля - (Miyaguchi-Preneel), а для функции сжатия использует шифр, который основан на AES, относительно которой было доказано, что эта криптографическая система - очень стойкая к атакам. Кроме того, размер дайджеста сообщения тот же, что и в SHA-512. Поэтому, как ожидается, Whirlpool будет очень сильной функцией криптографического хэширования. Однако необходимы серьезные испытания и исследования, чтобы подтвердить это. Единственный установленный недостаток - Whirlpool, который использует шифр как функцию сжатия, не может быть так же эффективен, как SHA-512, особенно когда он реализуется на аппаратных средствах.

    2.4. Рекомендованная литература

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

    Книги

    Несколько книг дают хороший обзор функций криптографического хэширования - [Sti06], [Sta06], [Sch99], [Mao04], [KPS02], [PHS03] и [MOV97] .

    Сайты

    Нижеследующие сайты дают больше информации о темах, рассмотренных в этой лекции.

  • http://www.unixwiz.net/techtips/iguide-crypto-hashes.html
  • http://www.faqs.org/rfcs/rfc4231.html
  • http://www.itl.nist.gov/fipspubs/fip 180-1.htm
  • http://www.ietf.org/rfc/rfc3174.txt http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
    •

    2.5. Итоги

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

  • Схема Меркеля-Дамгарда (Merkle-Damgard) - итеративная функция криптографического хэширования, устойчивая к коллизиям, если при этом функция сжатия устойчива к коллизиям. Эта схема сегодня - основа для многих функций криптографического хэширования.

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

  • Множество функций криптографического хэширования использует функции сжатия, которые сделаны на "пустом месте". Эти функции сжатия специально разработаны для этой цели, которую они обслуживают. Некоторые примеры: группа Дайджестов Сообщения - MD ; группа Алгоритмов Безопасного хэширования - SHA, RIPEMD и HAVAL.

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

  • Одна из перспективных функций криптографического хэширования - SHA-512 с 512-битовым дайджестом сообщения, основанным на схеме Меркеля-Дамгарда. Она разработана "на пустом месте" только для этой цели.

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

    •

    2.6. Набор для практики

    Обзорные вопросы

  • Определите функцию криптографического хэширования.
  • Определите итеративную функцию криптографического хэширования.
  • Опишите идею схемы Меркеля-Дамгарда и объяснить, почему эта идея важна для разработки функции криптографического хэширования.
  • Перечислите представителей семейства хэш-функций, которые используют шифр как функцию сжатия.
  • Перечислите некоторые схемы, который были разработаны, чтобы использовать блочный шифр как функцию сжатия.
  • Перечислите главные особенности функции криптографического хэширования SHA-512. Какой типа функции сжатия используется в SHA-512?
  • Перечислите некоторые особенности функции криптографического хэширования. Какая функция сжатия используется в Whirlpool?
  • Сравните контрастные особенности SHA-512 и функций криптографического хэширования Whirlpool.
    •

    Упражнения

  • В SHA-512 покажите значение поля длины в шестнадцатеричной форме для следующих длин сообщения:
  • 1000 битов
  • 10 000 битов
  • 1000 000 битов
    •
  • В Whirlpool покажите значение поля длины в шестнадцатеричной форме для следующих длин сообщения:
  • 1000 битов
  • 10 000 битов
  • 1000 000 битов
  • Каково дополнение для SHA-512, если длина сообщения:
  • 5120 битов
  • 5121 бит
  • 6143 бита
  • Каково дополнение для Whirlpool, если длина сообщения:
  • 5120 битов
  • 5121 бит
  • 6143 бита
  • В каждом из следующих случаев покажите, что если два сообщения имеют одни и те же последние блоки, то их последний блок после дополнения поля длины один и тот же:
  • хэш-функция - SHA-512
  • хэш-функция - Whirlpool
  • Вычислите G0 в табл. 2.2, используя седьмое простое число ( 17 ).
  • Сравните функцию сжатия SHA-512 без последней операции (конечное сложение) с шифром Файстеля на 80 раундов. Показать совпадения и отличия.
  • Функцию сжатия, используемую в SHA-512 (рис. 2.10), можно представить как шифр с процессом шифрования с 80 раундами, если слова от W0 до W79, представляют как ключи раунда в одной из схем, рссмотренных в этой лекции (Рабина, Дэвиса-Меейра, Мэтиса-Мейера-Осеаса или Миагучи-Пренеля). Что это напоминает? Подсказка: Подумайте об эффекте операции конечного сложения.
  • Покажите, что SHA-512 может быть субъектом "атаки сведения к середине", если из функции сжатия удалена операция конечного сложения.
  • Составить таблицу, такую же как табл. 2.5, чтобы сравнить AES и Whirlpool.
  • Показать, что третья операция не может быть удалена из десятого раунда в шифре Whirlpool, но она должна быть удалена в шифре AES.
  • Найдите результат операции RotR12 (x), если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат операции ShL12(x), если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат операции Rotate(x),если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат функции Conditional (x,y,z), если
    x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
 y = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
 z = 3234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат функции Majority (x, y, z), если
    x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
 y = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
 z = 3234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Напишите процедуру (в псевдокоде) для вычисления RotRi (x) в SHA-512 (рис. 2.9).
  • Напишите процедуру (в псевдокоде), чтобы вычислить ShLi (x) в SHA-512 (рис. 2.9).
  • Напишите процедуру (в псевдокоде) для функции Conditional в SHA-512 (рис. 2.11).
  • Напишите процедуру (в псевдокоде) для функции Rotate в SHA-512 (рис. 2.11),
  • Напишите процедуру (в псевдокоде), чтобы вычислить начальный дайджест (значения A0 до H0 ) в SHA-512 (табл. 2.2).
  • Напишите процедуру (в псевдокоде), чтобы вычислить восемьдесят констант в SHA-512 (табл. 2.3).
  • Напишите процедуру (в псевдокоде) для алгоритма расширения слова в SHA-512, показанном на рис. 2.9. Рассмотрите два случая:
  • Использование массива 80 элементов, содержащих все слова.
  • Использование массива 16 элементов, содержащего только 16 слов одновременно.
  • Напишите процедуру (в псевдокоде) для функции сжатия в SHA-512.
  • Напишите процедуру (в псевдокоде), чтобы изменить блок 512 бит к 8 x8 матрицам состояний (рис. 2.4).
  • Напишите процедуру (в псевдокоде), чтобы изменить состояний 8 8 матрицу для блоков 512 бит (рис. 2.4).
  • Напишите процедуру (в псевдокоде) для преобразования SubBytes в шифре Whirlpool (рис. 2.16).
  • Напишите процедуру (в псевдокоде) для ShiftColumns преобразования в шифре Whirlpool (рис. 2.18).
  • Напишите процедуру (в псевдокоде) для MixRows преобразования в шифре Whirlpool (рис. 2.19).
  • Напишите процедуру (в псевдокоде) для AddRoundKey преобразования в шифре Whirlpool (рис. 2.20).
  • Напишите процедуру (в псевдокоде) для расширения ключа в шифре Whirlpool (рис. 2.21)
  • Напишите процедуру (в псевдокоде), чтобы создать константы раунда в шифре Whirlpool (рис. 2.20).
  • Напишите процедуру (в псевдокоде) для шифра Whirlpool.
  • Напишите процедуру (в псевдокоде) для функции криптографического хэширования Whirlpool.
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о SHA-1. Затем сравнить функцию сжатия в SHA-1 с такими же функциями в SHA-512. Каковы совпадения? Каковы отличия?
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о следующих функциях сжатия и сравнить их с SHA-512:
  • SHA-224
  • SHA-256
  • SHA-384
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о RIPEMD и сравнить ее с SHA-512.
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о HAVAL и сравнить ее с SHA-512.
    • Страницы:

    2.1. Введение

    Рассмотренная в лекции 11 криптографическая хэш-функция получает сообщение произвольной длины и создает дайджест сообщения фиксированной длины. Окончательная цель этой главы состоит в том, чтобы обсудить детали двух наиболее перспективных криптографических алгоритмов хэширования - SHA-512 и Whirlpool. Однако мы сначала должны обсудить некоторые общие идеи, которые могут быть применены к любой криптографической хэш-функции.

    Итеративная хэш-функция

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

    Схема Меркеля-Дамгарда (Merkle-Damgard)

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

    (рис 2.1) Схема Меркеля-Дамгарда

    Схема использует следующие шаги:

  • Длина сообщения и дополнение добавляются в конец сообщения, чтобы создать увеличенное сообщение, которое может быть равномерно разделено на n -битовые блоки; здесь n - размер блока, который будет обработан функцией сжатия.
  • Сообщение тогда рассматривают как t блоков, размер каждого состоит из n бит. Мы обозначим каждый блок М1,..., Мt. Мы обозначаем дайджест, созданный при t итерациях, - H1, H2,...., Ht
  • Перед стартом итерации дайджест H0 устанавливается на фиксированное значение, обычно называемое IV (начальное значение или начальный вектор).
  • Функция сжатия при каждой итерации обрабатывает Hi-1 и М., создавая новый Hi. Другими словами, мы имеем Hi = .f (Hi-1, Мi), где f - функция сжатия.
  • Ht - функция криптографического хэширования первоначального сообщения, то есть h(M).Если функция сжатия в схеме Меркеля-Дамгарда устойчива к коллизии, хэш-функция также устойчива к коллизии.

    • Две группы функций сжатия

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

    Хэш-функции, сделанные на "пустом месте"

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

    Дайджест сообщения (MD)

    Несколько алгоритмов хэширования были разработаны Роном Ривестом. Они известны в литературе как MD2, MD4 и MD5, где MD обозначает Дайджест Сообщения. Последняя версия, MD5, является усиленной версией MD4, которая делит сообщение на блоки по 512 битов и создает дайджест на 128 битов. Оказалось, что дайджест сообщения размером 128 битов - слишком маленький, чтобы быть устойчивым к атаке коллизии.

    Алгоритм безопасного хэширования (SHA - Secure Hash Algorithm)

    Алгоритм безопасного хэширования (SHA) - стандарт, который был разработан национальным Институтом Стандартов и Технологии (NIST - National Institute of Standards and Technology) и издан как Федеральный Стандарт Обработки Информации (FIP 180). Он упоминается в литературе как Стандарт Безопасного хэширования ( SHS - Secure Hash Standard ). Стандарт главным образом базируется на MD5. В 1995 г. он был пересмотрен под названием FIP 180-1, который включает SHA-1. Позже он снова был пересмотрен под названием FIP 180-2, который определяет четыре новых версии: SHA-224, SHA-256, SHA-384 и SHA-512. табл. 2.1 дает список некоторых из характеристик этих версий.

    Характеристики алгоритмов безопасного хэширования (SHAs)
    Характеристики SHA-1 SHA-224 SHA-256 SHA-384 SHA-512
    Максимальный размер сообщения 264 - 1 264 - 1 264 - 1 2128 - 1 2128 - 1
    Размер блока 512 512 512 1024 1024
    Размер дайджеста сообщения 160 224 256 384 512
    Число раундов 80 64 64 80 80
    Размер слова 32 32 32 64 64

    Все эти версии имеют одну и ту же структуру. SHA-512 будет рассмотрен подробно позже в этой лекции.

    Другие Алгоритмы сохранения целостности (RIPMD - RACE Integrity Primitives Evaluation Message Digest).Группа алгоритмов криптографического хэширования( RIPMD ) имеет несколько версий. RIPEMD-160 - алгоритм хэширования с дайджестом сообщения на 160 битов. RIPEMD-160 использует ту же структуру, что и MD5, но применяет два варианта выполнения.

    HAVAL - алгоритм хэширования переменной длины с дайджестом сообщения размера 128, 160, 192, 224 и 256. Размер блока - 1024 бита.

    Хэш-функции, основанные на блочных шифрах

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

    Схема Рабина. Итеративная хэш-функция, предложенная Рабиным, очень проста. Схема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования. Блок сообщения используется как ключ; предварительно созданный дайджест используется как исходный текст. Зашифрованный текст - новый дайджест сообщения. Обратите внимание, что размер дайджеста - это размер блочного шифра данных в основной криптографической системе. Например, если DES используется как блочный шифр, размер дайджеста - только 64 бита. Хотя схема очень проста, она может быть раскрыта с помощью атаки "сведения к середине", рассмотренной в лекции 6, поскольку противник может применить алгоритм дешифрования криптографической системы. Рис. 2.2 показывает схему Рабина.

    (рис 2.2) Схема Рабина

    Схема Девиса-Мейера (Davies-Mayer). В основном она повторяет схему Рабина, за исключением того, что использует прямую связь для защиты от атаки "сведения в середину".

    (рис 2.3) Схема Девиса-Мейера

    Схема Матиса-Мейера-Осеаса (Metyas-Mayer-Oseas). Это версия схемы Девиса-Мейера: блоки сообщения применяются как ключи криптосистемы. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, AES хорошо подходит для этой цели.

    (рис 2.4) Схема Матиса-Мейера-Осеаса

    Схема Миагучи-Пренеля - расширенная версия схемы Матиса-Мейера-Осеаса. Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью ИСКЛЮЧАЮЩЕГО ИЛИ и создают новый дайджест. Эта схема используется в Whirlpool для создания хэш-функции. На рис. 2.5 показана схема Миагучи-Пренеля.

    (рис 2.5) Схема Миагучи-Пренеля

    2.2. SHA-512

    версия SHA (Secure Hash Algorithm) - алгоритм безопасного хэширования с 512-битовым дайджестом сообщения. Эта версия похожа на другие алгоритмы этого семейства, которые основаны на схеме Меркеля-Дамгарда. Мы выбрали для рассмотрения особую версию. Она самая поздняя, обладает более полной структурой, чем другие, и наиболее длинным дайджестом сообщения. Если понять эту версию, нетрудно будет усвоить структуру других версий.

    Введение

    SHA-512 создает дайджест из сообщения, содержащего много блоков. Каждый блок имеет длину 1024 бита, как это показано на рис. 2.6.

    (рис 2.6) Создание дайджеста сообщения SHA-512

    Дайджест вначале устанавливается на определенное заранее значение 512 битов. Алгоритм смешивает это начальное значение с первым блоком сообщения, чтобы создать первый промежуточный дайджест сообщения 512 битов. Этот дайджест затем смешивается со вторым блоком, чтобы создать второй промежуточный дайджест. Наконец, (N - l) -ый дайджест смешивается с N -ым блоком - они создают N -ый дайджест. Когда последний блок обработан, результирующий дайджест - это дайджест полного сообщения.

    Подготовка сообщения

    SHA-512 требует, чтобы длина первоначального сообщения была меньше, чем 2128 битов. Если длина сообщения равна или больше, чем 2128, оно не будет обработано SHA-512. Это обычно не проблема, потому что 2128 битов превосходят возможную сегодня полную емкость хранения любой системы.

    SHA-512 создает дайджест сообщения на 512 битов из сообщения меньшего, чем 2128.

    Пример 2.1

    Этот пример показывает, что ограничение длины сообщения SHA-512 - не серьезная проблема. Предположим, что мы должны передать сообщение длиною 2128 бита в секунду. Какое время потребуется для системы коммуникаций со скоростью передачи данных 264 бита в секунду, чтобы передать это сообщение?

    Решение

    Системы коммуникаций, которая может передать 264 бита в секунду, пока еще не существует. Даже если бы она была, потребовалось бы много лет, чтобы передать это сообщение. Отсюда ясно, что мы не должны волноваться по поводу ограничения длины сообщения для SHA-512.

    Пример 2.2

    Этот пример также касается длины сообщения в SHA-512. Сколько страниц занимает сообщение 2128 бит?

    Предположим, что символ имеет длину 32 или 26 бит. Каждая страница - меньше, чем 2048, или приблизительно 212, символов. Тогда 2128 битов требуют по крайней мере 2128/218, или 2110 страниц. И снова ясно, что мы не должны волноваться об ограничении на длину сообщения.

    Поле длины и заполнение

    Прежде чем дайджест сообщения может быть создан, SHA-512 требует сложения поля длины - это целое число без знака на 128 битов, которое определяет длину сообщения в битах, - с сообщением. Это длина первоначального сообщения перед заполнением. Поле целого числа без знака 128 битов можно определить как число между 0 и 2128 - 1, которое является максимальной длиной сообщения, принятого в SHA-512. Поле длины определяет длину первоначального сообщения перед его сложением или заполнением (рис. 2.7).

    (рис 2.7) Заполнение и поле длины в SHA-512

    Перед сложением поля длины мы должны дополнить первоначальное сообщение, чтобы сделать длину кратной 1024. Для поля длины резервируется 128 битов, как показано на рис. 2.7. Длина области заполнения может быть рассчитана следующим образом. Пусть |M| - длина первоначального сообщения и |P| - длина поля заполнения.

    ( M  +  P  + 128) = 0 mod 1024 ->   P   = (- M   - 128) mod 1024

    Формат заполнения - это одна 1, сопровождаемая необходимым числом нулей (0).

    Пример 2.3

    Какое число битов заполнения необходимо, если длина первоначального сообщения - 2590 битов?

    Решение

    Мы можем вычислить число битов заполнения следующим образом:

    P = (-2590 -128) mod 1024 = -2718 mod  1024 = 354

    Заполнение состоит из одной 1, сопровождаемой 353 нулями.

    Пример 2.4

    Нужно ли заполнение, если длина первоначального сообщения уже кратна 1024 битам?

    Решение

    Да, нужно, потому что мы должны добавить поле длины. Заполнение необходимо, чтобы сделать и новый блок кратным 1024 битам.

    Пример 2.5

    Каково минимальное и максимальное число битов заполнения, которые можно добавить к сообщению?

    Решение

    Минимальная длина заполнения - 0, и это случается, когда (-M - 128) mod 1024 = 0 ; тогда |M| = -128 mod 1024 = 896 mod 1024 бит. Другими словами, последний блок в первоначальном сообщении - 896 битов. Мы добавляем поле длины на 128 битов, чтобы сделать блок полным.

    Максимальная длина заполнения - 1023, и это случается, когда (- M - 128) = 1023 mod 1024. Это означает, что длина первоначального сообщения - M = (-128 - 1023) mod 1024 или M = 897 mod 1024. В этом случае мы не можем просто добавить область длины, потому что длина последнего блока будет превышать на один бит число 1024. Так что мы нуждаемся в заполнении 127 битами, чтобы закончить этот блок и создать второй блок заполнения 896 битов. Теперь можно добавить поле длины, чтобы сделать этот блок полным.

    Слова

    SHA-512 оперирует словами; он - ориентируемый на слово. Слово определено длиной 64 бита. Это означает, что после того как заполнение и поле длины добавляются к сообщению, каждый блок сообщения состоит из шестнадцати слов по 64 бита. Дайджест сообщения также образуется из слов по 64 бита, но дайджест сообщения - только восемь слов, и слова обозначают A, B, C, D, E, F, G и H, как показано на рис. 2.8.

    (рис 2.8) Блок сообщения и дайджест в виде отдельных словSHA-512 - алгоритм, ориентированный на слово. Каждый блок - 16 слов; в дайджесте - только 8 слов.

    Расширение слова

    Перед обработкой каждый блок сообщения должен быть расширен. Блок образован из 1024 битов, или шестнадцати слов по 64 бита. Как мы увидим позже, в фазе обработки нам нужно 80 слов. Так что блок с 16-ю словами должен быть расширен до 80 слов от W0 до W79. рис. 2.9 показывает процесс расширения слова. Блок на 1024 бита порождает первые слова; остальная часть слов получается от уже сделанных слов согласно операциям, которые показаны на рисунке.

    (рис 2.9) Расширение слова в SHA -52

    Пример 2.6

    Показать, как получить W60.

    Решение

    Каждое слово в диапазоне W16 до W79 получено в результате обработки четырех слов, созданных предварительно на предыдущих шагах. W60 получено как

    $$W_{60} = W_{44} \oplus RotShift _{1-8-7} (W_{45}) \oplus W_{53} \oplus RotShift _{19 -61-6}(W_{58})$$

    Инициализация дайджеста сообщения

    Алгоритм использует восемь констант для инициализации дайджеста сообщения. Мы обозначаем их от A0 до H0, что соответствует обозначению слов, используемых для дайджеста. табл. 2.2 показывает значение этих констант.

    Значение констант при инициализации дайджеста сообщения SHA-512
    Буфер Значение (шестнадцатеричное) Буфер Значение (шестнадцатеричное)
    A0 6A09E667F3BCC908 E0 510E527FADE682D1
    B0 3B67AE8584CAA73B F0 9B05688C2B3E6C1F
    C0 3C6EF372EF94F828 G0 1F83D9ABFB41BD6B
    D0 A54FE53A5F1D36F1 H0 5BEOCD19137E2179

    Читатель может задаться вопросом, откуда взяты эти значения. Они рассчитаны из первых восьми простых чисел (2, 3, 5, 7, 11, 13, 17 и 19). Каждое значение - дробная часть квадратного корня соответствующего простого числа после преобразования к двоичной форме и сохранения только первых 64 битов. Например, восьмое простое число - 19 имеет квадратный корень (191/.2) = 4,35889894354. Преобразовывая число к двоичной форме только с 64 битами в дробной части, мы имеем

    (100.0101 1011 1110... 1001)2 -> (4,5BEOCD19137E2179)16

    SHA-512 сохраняет дробную часть (5BEOCD19137E2179)16 как целое число без знака.

    Функция сжатия

    SHA-512 создает 512 битов дайджест-сообщения (восемь слов на 64 бита) из сообщения, которое состоит из множества блоков, где каждый блок содержит 1024 бита. Обработка каждого блока данных в SHA-512 включает 80 раундов. рис. 2.10 показывает общую схему сжатия функции. В каждом раунде содержание восьми предыдущих буферов - это одно слово из расширенного блока ( Wi ), и одна константа на 64 бита ( Ki ), смешанные вместе. Они обработаны затем, чтобы создать новое множество из восьми буферов. В начале обработки значения восьми буферов сохранены как восемь временных переменных. В конце обработки (после того как сделан шаг 79) эти значения добавляются к значениям, созданным на шаге 79. Мы вызываем эту последнюю операцию финальным сложением, как это показано на рисунке.

    (рис 2.10) Функция сжатия в SHA-512

    Структура каждого раунда

    (рис 2.11) Структура каждого раунда SHA-512

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

    A -> B     B -> C    C  -> D    E -> F   F -> G    G -> H

    Два новых буфера, A и E, получают соответствующие значения от некоторых сложных функций, которые включают в себя некоторые значения предыдущих буферов, соответствующее слово для этого раунда (Wi) и константу для этого раунда (Ki). Рис. 2.11 показывает структуру каждого раунда.

    Здесь есть два смесителя, три функции и несколько операторов. Каждый смеситель обрабатывает две функции. Описание функций и операторов приведено ниже.

  • То, что мы называем мажоритарной функцией, является поразрядной функцией. Она использует три соответствующих бита в трех буферах ( A, B и C ) и вычисляет$$( A_{j} \ AND \ B_{j}) \oplus (B_{j} \ AND \ C_{j}) ) \oplus (C_{j} \ AND \ A_{j})$$

    Результат - это значение, которое имеет большинство из трех бит. Если два или три бита равны единице (1) , то результат имеет значение бит 1; иначе он равен 0.

    Функция, которую мы называем условной функцией ( Conditional ) - также поразрядная функция. Она использует три бита, которые содержатся в трех буферах ( E, F и G ), и вычисляет

    $$(E_{j } \ AND \ F_{j}) \oplus (NOT \ E_{j } \ AND \ G_{j})$$

    Результат подчиняется логике "Если E, то F ; иначе G ".

  • Функция "циклическое перемещение" (Rotate) обрабатывает три значения одного и того же буфера ( A или E ) и применяет операцию ИСКЛЮЧАЮЩЕЕ ИЛИ с результатом мажоритарной функции.$$Rotate (A): RotR_{28 }(A) \oplus RotR_{34} (A) \oplus RotR_{29}(A) \\ Rotate (E): RotR_{28 }(A) \oplus RotR_{34} (E) \oplus RotR_{29}(E)$$
  • Функция "циклическое перемещение вправо" (RotRi (x) ) - та же самая, которую мы использовали в процессе расширения слова.
  • Оператор сложения, применяемый в процессе, - сложение по модулю 264. Он означает результат сложения двух или больше буферов, содержащих всегда слово на 64 бита.
  • Есть 80 констант, K0 к K79, каждая по 64 бита, как показано в табл. 2.3 в шестнадцатеричной форме (четыре в каждой строке таблицы). Аналогично начальным значениям для восьми буферов, эти значения вычислены из первых 80 простых чисел ( 2, 3..., 409 ).
    •
    Восемьдесят констант, используемых для восьмидесяти раундов в SHA-512
    428A2F98D728AE22 7137449123EF65CD B5COFBCFEC4D3B2F E9B5DBA58189DBBC
    3956C25BF348B538 59F111F1B605D019 923F82A4AF194F9B AB1C5ED5DA6D8118
    D807AA98A3030242 12835B0145706FBE 243185BE4EE4B28C 550 C7DC3D5FFB4E2
    72BE5D74F27B896F 80DEB1FE3B1696B1 9BDC06A725C71235 C19 BF1 74CF 692694
    E49B69C19EF14AD2 EFBE4786384F25E3 OFC19DC68B8CD5B5 240 CA1CC77AC9C65
    2DE92C6F592B0275 4A7484AA6EA6E483 5CBOA9DCBD41FBD4 76F 9 8 8DA831 153B5
    983E5152EE66DFAB A831C66D2DB43210 B00327C898FB213F BF5 97FC7 BEEF0EE4
    C6EOOBF33DA88FC2 D5A79147930AA725 06CA6351E003826F 142 92 967 0AOE6E70
    27B70A8546D22FFC 2E1B21385C26C926 4D2C6DFC5AC42AED 533 80 D1 39D95B3DF
    650A73548BAF63DE 766AOABB3C77B2A8 81C2C92E47EDAEE6 92722 C8 514 823 53B
    A2BFE8A14CF10364 A81A664BBC423001 C24B8B70DOF89791 C76C5 1A 30 6 54BE30
    D192E819D6EF5218 D69906245565A910 F40E35855771202A 106AA 07 032BBD1B8
    19A4C116B8D2DOC8 1E376C085141AB53 2748774CDF8EEB99 34BOBCB 5E 19B4 8A8
    391COCB3C5C95A63 4ED8AA4AE3418ACB 5B9CCA4F7763E373 682 E 6FF 3D6B2B8A3
    748F82EE5DEFB2FC 78A5636F43172F60 84C87814A1FOAB72 8CC7 020 81A 6439EC
    90BEFFFA23631E28 A4506CEBDE82BDE9 BEF9A3F7B2C67915 C671 78F 2E372532B
    CA273ECEEA26619C D186B8C721COC207 EADA7DD6CDEOEB1E F57D 4F7 FEE6E178
    06F067AA72176FBA OA637DC5A2C898A6 113F9804BEF90DAE 1B71 0B3 5131C471B
    28DB77F523047D84 32CAAB7B40C72493 3C9EBEOA15C9BEBC 431D 67C 49C100D4C
    4CC5D4BECB3E42B6 4597F299CFC657E2 5FCB6FAB3AD6FAEC 6C44 198 C4A475 817

    Каждое значение - дробная часть кубического корня из соответствующего простого числа после преобразования этого числа к двоичной форме, сохраняются только первые 64 бита. Например, 80-е простое число - ( 409 ). Кубический корень (409) 1/3 = 7,42291412044. Преобразовывая это число к двоичному виду только с 64 битами в дробной части, мы получаем

    (111,0110 1100 0100 0100...0111) 2 -> (7,6C44198C4A475817).

    SHA-512 сохраняет дробную часть, (6C44198C4A475817)16, как целое число без знака.

    Пример 2.7

    Мы применяем мажоритарную функцию к значениям буферов A, B и C. Если крайние левые шестнадцатеричные цифры этих буферов - 0x7, 0xA и 0xE соответственно, то какая цифра будет крайней левой частью результата?

    Решение

    Цифры в двоичной форме - 0111, 1010 и 1110.

  • Первые биты - 0, 1 и 1. Мажоритарная функция равна 1. Мы можем доказать это, используя определение мажоритарной функции:$$(0 \ AND \ 1) \oplus (1 \ AND \ 1) \oplus C (1 \ AND \ 0) = 0 \oplus 1 \oplus 0 = 1$$
  • Вторые биты - 1, 0 и 1. Мажоритарная функция равна 1 .
  • Третьи биты - 1, 1 и 1. Мажоритарная функция равна 1.
  • Четвертые биты - 1, 0 и 0. Мажоритарная функция равна 0. Результат - 1110, или 0xE в шестнадцатеричной форме.
    •

    Пример 2.8

    Мы применяем условную функцию ( Conditional ) для буферов E, F и G. Если крайние левые шестнадцатеричные цифры этих буферов - 0x9, 0xE и 0xF соответственно, то какая цифра будет крайней левой частью результата?

    Решение

    Цифры в двоичной форме - 1001, 1110 и 1111.

  • Первые биты - 1,1 и 1. Следовательно, E1 = 1, результат - F1, который равен 1. Чтобы доказать результат, мы можем также использовать определение функции Condition:$$(1 \ AND \ 1) \oplus (NOT \ 1 \ AND \ 1) = 1 \oplus 0 = 1$$
  • Вторые биты - 0, 0 и 1. Следовательно, E2 - 0, результат - F3, который равен 1.
  • Третьи биты образовывают дугу 0, 1 и 1. Следовательно, E3 - 0, результат - G3, который равен 1.
  • Четвертые биты - 1, 0 и 1. Следовательно, E4 - 1, результат - F4, который равен 0. Результат - 1110, или 0x1 в шестнадцатеричной форме.
    •

    Анализ

    С дайджестом сообщения 512 битов от SHA-512 ожидалось, что он будет более стойким ко всем типам атак, включая атаки коллизии. Он должен был быть лучшим проектом этой версии: более эффективным и более безопасным, чем предыдущие. Однако необходимы были серьезные исследования и испытания, для того чтобы это подтвердить.

    2.3. Whirlpool

    Whirlpool разработан Винсентом Риджменом (Vincent Rijmen) и Пауло Баретто (Paolo Barreto). Он одобрен европейской организацией NESSIE ( New European Schemes for Signature, Integrity and Encryption - Новые европейские схемы подписей, целостности и шифрования ).

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

    (рис 2.12) Whirlpool хэш-функция

    Подготовка

    Перед стартом алгоритма хэширования сообщение должно быть готово к процессу. Whirlpool требует, чтобы длина первоначального сообщения была меньше, чем 2256 бита. Сообщение должно быть дополнено прежде, чем начать обработку. Дополнение содержит единственный бит, равный 1, а затем следует необходимое чисел нулевых битов, чтобы сделать длину дополнения нечетным числом, кратным 256 битам. После дополнения добавляется блок 256 битов, чтобы указать длину первоначального сообщения. Этот блок обрабатывается как число без знака.

    После дополнения первоначального сообщения и присоединения поля длины увеличенный размер сообщения становится кратным 256 битам или кратным 512 битам. Whirlpool создает дайджест 512 из сообщения, состоящего из многих блоков по 512 бит. Дайджест из 512 бит, H0, начинается всеми нулями. Это становится ключом шифра для шифрования первого блока. Из зашифрованного текста каждого зашифрованного блока получают ключ шифра для следующего блока после того, как его складывают по модулю два с предыдущим ключом шифра и блоком исходного текста. Дайджест сообщения - конечный зашифрованный текст на 512 битов после последней операции ИСКЛЮЧАЮЩЕЕ ИЛИ.

    Шифр Whirlpool

    Шифр Whirlpool - шифр не-Файстеля, похож на AES и был главным образом, разработан как блочный шифр, который используется в алгоритме хэширования. Вместо того чтобы дать полное описание этого шифра, мы будем исходить из того, что читатель знаком с AES по материалам Главы 7. Ниже только приводится сравнение шифра Whirlpool с шифром AES и отмечается их отличие.

    Раунды

    Whirlpool - шифр, который использует 10 раундов. Размер блока и ключевой размер - 512 битов. Шифр применяет 11 ключей раунда K0 - K10, каждый по 512 битов. рис. 2.13 показывает общий вид процесса шифрования шифром Whirlpool.

    (рис 2.13) Общая идея шифра Whirlpool

    Матрицы состояний и блоки

    Подобно шифру AES, шифр Whirlpool использует матрицы состояний и блоки. Однако размер блока или матрицы состояний - 512 битов. Блок рассматривается как строка матрицы длиной 64 байта; матрица состояний - как квадратная матрица 8 x 8 байтов. В отличие от AES преобразование "блок - матрица состояний" или "матрица состояний - блок" происходят строка за строкой. рис. 2.14 показывает блок, матрицу состояний и преобразование в шифр Whirlpool.

    (рис 2.14) Блок и матрица состояний шифра Whirlpool

    Структура каждого раунда

    Рис. 2.15 показывает структуру каждого раунда. Каждый раунд использует четыре преобразования.

    (рис 2.15)

    SubBytes. Подобно AES, SubBytes обеспечивает нелинейное преобразование. Байт представлен как две шестнадцатеричных цифры. Левая цифра определяет строку, а правая - столбец таблицы подстановки. Две шестнадцатеричных цифры в пересечении строки и столбца - новый байт. рис. 2.16 иллюстрирует идею.

    (рис 2.16) Преобразование SubBytes шифра Whirlpool

    В преобразовании SubBytes матрица состояний обрабатывается как матрица байтов 8 x 8. Преобразование делается одновременно только с одним байтом. Содержание каждого байта изменяется, но порядок следования байтов в матрице остается тем же самым. В процессе каждый байт преобразуется независимо; мы имеем 64 различных преобразований байт-к-байту.

    Таблица 2.4 показывает таблицу подстановки (S-блок) для преобразования подбайтов. Преобразование обеспечивает эффект перемешивания. Например, два байта, 5A16 и 5B16, которые отличаются только одним битом (самый правый бит), преобразованы к 5B16 и 8816, которые отличаются пятью битами.

    Таблица преобразования SubBytes (S-Box)
    0 / 2 3 4 5 6 7 8 9 A B C D E F
    0 18 23 C6 E8 87 B8 01 4F 36 A6 D2 F5 79 6F 91 52
    1 16 BC 9B 8E A3 0C 7B 35 1D E0 D7 C2 2E 4B FE 57
    2 15 77 37 E5 9F F0 4A CA 58 C9 29 0A B1 A0 6B 85
    3 BD 5D 10 14 CB 3E 05 67 E4 27 41 8B A7 7D 95 C8
    4 FB EF 7C 66 DD 17 47 9E CA 2D BF 07 AD 5A 83 33
    5 63 02 AA 71 C8 19 49 C9 F2 E3 5B 88 9A 26 32 BO
    6 E9 OF D5 80 BE CD 34 48 FF 7A 90 5F 20 68 1A AE
    7 B4 54 93 2'2 64 F1 73 12 40 08 C3 EC DB A1 8D 3D
    8 97 00 CF :B 76 82 D6 1B B5 AF 6A 50 45 F3 30 EF
    9 3F 55 A2 EA 65 BA 2F CO DE 1C FD 4D 92 75 06 8A
    A B2 E6 OE F 62 D4 A8 96 F9 C5 25 59 84 72 39 4C
    B 5E 7S 38 8C C1 A5 E2 61 B3 21 9C 1E 43 C7 FC 04
    C 51 99 6D 0D FA DF 7E 24 3B AB CE 11 8F 4E B7 EB
    D 3C S1 94 '-7 9B 13 2C D3 E7 6E C4 03 56 44 7E A9
    E 2A BB C1 53 DC OB 9D 6C 31 74 F6 46 AC 89 14 E1
    F 16 3A 69 09 70 B6 CO ED CC 42 98 A4 28 5C F8 86

    Входы в табл. 2.4 могут быть вычислены алгебраически, используя поле G(24) с неприводимым полиномом (x4 + x + 1), как показано на рис. 2.17. Каждая шестнадцатеричная цифра в байте вводится в миниблок ( E и E-1 ). Результаты передаются в другой миниблок R. E -блоки вычисляют степень, равную шестнадцатеричному значению входа; R -миниблок использует псевдослучайный генератор чисел.

    (рис 2.17) Операция SubBytes шифра Whirlpool $$E(вход) = (x^{3} +x+1)^{вход} \ mod (x^{4} + x + 1), \ если \ вход \ne 0xF \\ E(0xF) = 0$$

    E-1 -блок - это только инверсия E -блока, где роли входов и выходов изменились. Значения входа-выхода для блоков сведены в таблицу на рис. 2.17.

    ShiftColumns . Чтобы обеспечить перестановку, Whirlpool использует преобразование ShiftColumns , которое является подобным преобразованию ShiftRows в AES, за исключением того, что вместо строк сдвигаются столбцы. Смещение зависит от позиции столбца. Столбец 0 сдвигается на 0 байтов (смещения нет), в то время как столбец 7 сдвигается на 7 байтов. рис. 2.18 показывает преобразование смещения.

    (рис 2.18) Преобразование ShiftColumns шифра Whirlpool

    MixRows.Преобразование MixRows имеет тот же самый эффект, что и преобразование MixColumns в AES: оно рассеивает биты. Преобразование MixRows - матричное преобразование, где байты интерпретируются как слова по 8 битов (или полиномы) с коэффициентами в GF(28). Умножение байтов проводится в GF(28), но модуль отличается от используемого в AES. Шифр Whirlpool применяет ( 0x11 D ) или ( x8 + x4 + x3 + x2 + 1 ) как модуль. Сложение слов по 8 битов - то же самое, что ИСКЛЮЧАЮЩЕЕ ИЛИ. На рис. 2.19 представлено преобразование MixRows.

    (рис 2.19) Преобразование MixRows шифра Whirlpool

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

    AddRoundKey. Преобразование AddRoundKey в шифре Whirlpool делается байт за байтом, потому что каждый ключ раунда - матрица состояний 8 x 8 байт. рис. 2.20 показывает этот процесс. Байт матрицы состояний данных складывается в поле GF(28) с соответствующим байтом матрицы состояний ключей раунда. Результат - новый байт в новой матрице состояний.

    (рис 2.20) Преобразование AddRoundKey шифра Whirlpool

    Расширение ключа

    Как показывает рис. 2.21, алгоритм расширения ключей в Whirlpool полностью отличается от алгоритма в AES. Вместо того чтобы применять новый алгоритм создания ключей раунда, Whirlpool использует копию алгоритма шифрования (без предраунда), чтобы создать ключи раунда. Выход каждого раунда в алгоритме шифрования есть ключи для этого раунда. На первый взгляд это напоминает определение, где ключи раунда для алгоритма расширения ключа получаются из него самого. Откуда получается алгоритм расширения? Whirlpool изящно решил эту проблему, используя десять констант раунда ( RC ) как виртуальные ключи раунда для алгоритма расширения ключей. Другими словами, алгоритм расширения ключей применяет константы как ключи раунда. Алгоритм шифрования использует выход каждого раунда алгоритма расширения ключей как ключи раунда. Алгоритм генерирования ключей обрабатывает ключ шифра как исходный текст и зашифровывает его. Обратите внимание, что ключ шифра - также К0 для алгоритма шифрования.

    (рис 2.21) Расширение ключа шифра Whirlpool

    Константы раунда. Каждая константа раунда RCr является матрицей 8 x 8, где только первая строка имеет значения, отличные от нуля. Остальная часть входов содержит все нули. Значения для первой строки в каждой матрице констант могут быть вычислены, используя преобразование SubBytes ( табл. 2.4).

    RC round[строка, столбец] = Subbytes (8 (round -1) + столбец)   если  строка = 0 
RCround [строка, столбец] = 0   если строка ^ 0

    Другими словами, RC1 использует первые восемь входов в таблице преобразования SubBytes ( табл. 2.4); RC2 использует вторые восемь входов, и т. д. рис. 2.22 показывает пример RC3, где первая строка - третьи восемь входов в таблице SubBytes.

    (рис 2.22) Константы для третьего раунда

    Итоги шифра Whirlpool.

    В табл. 2.5 приведены основные характеристики шифра Whirlpool.

    Основные характеристики шифра Whirlpool
    Размер блока: 512 бит
    Размер ключа шифра: 512 бит
    Число раундов: 10
    Расширение ключа: использование шифра непосредственно с константами раунда в качестве ключей раунда
    Подстановка: Преобразование SubBytes
    Перестановка: Преобразование ShiftColumns
    Смешивание: Преобразование MixRows
    Константы раунда: кубические корни первых восьмидесяти простых чисел

    Анализ

    Хотя Whirlpool не был всесторонне изучен или проверен, он базируется на устойчивой схеме Миагучи-Пренеля - (Miyaguchi-Preneel), а для функции сжатия использует шифр, который основан на AES, относительно которой было доказано, что эта криптографическая система - очень стойкая к атакам. Кроме того, размер дайджеста сообщения тот же, что и в SHA-512. Поэтому, как ожидается, Whirlpool будет очень сильной функцией криптографического хэширования. Однако необходимы серьезные испытания и исследования, чтобы подтвердить это. Единственный установленный недостаток - Whirlpool, который использует шифр как функцию сжатия, не может быть так же эффективен, как SHA-512, особенно когда он реализуется на аппаратных средствах.

    2.4. Рекомендованная литература

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

    Книги

    Несколько книг дают хороший обзор функций криптографического хэширования - [Sti06], [Sta06], [Sch99], [Mao04], [KPS02], [PHS03] и [MOV97] .

    Сайты

    Нижеследующие сайты дают больше информации о темах, рассмотренных в этой лекции.

  • http://www.unixwiz.net/techtips/iguide-crypto-hashes.html
  • http://www.faqs.org/rfcs/rfc4231.html
  • http://www.itl.nist.gov/fipspubs/fip 180-1.htm
  • http://www.ietf.org/rfc/rfc3174.txt http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
    •

    2.5. Итоги

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

  • Схема Меркеля-Дамгарда (Merkle-Damgard) - итеративная функция криптографического хэширования, устойчивая к коллизиям, если при этом функция сжатия устойчива к коллизиям. Эта схема сегодня - основа для многих функций криптографического хэширования.

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

  • Множество функций криптографического хэширования использует функции сжатия, которые сделаны на "пустом месте". Эти функции сжатия специально разработаны для этой цели, которую они обслуживают. Некоторые примеры: группа Дайджестов Сообщения - MD ; группа Алгоритмов Безопасного хэширования - SHA, RIPEMD и HAVAL.

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

  • Одна из перспективных функций криптографического хэширования - SHA-512 с 512-битовым дайджестом сообщения, основанным на схеме Меркеля-Дамгарда. Она разработана "на пустом месте" только для этой цели.

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

    •

    2.6. Набор для практики

    Обзорные вопросы

  • Определите функцию криптографического хэширования.
  • Определите итеративную функцию криптографического хэширования.
  • Опишите идею схемы Меркеля-Дамгарда и объяснить, почему эта идея важна для разработки функции криптографического хэширования.
  • Перечислите представителей семейства хэш-функций, которые используют шифр как функцию сжатия.
  • Перечислите некоторые схемы, который были разработаны, чтобы использовать блочный шифр как функцию сжатия.
  • Перечислите главные особенности функции криптографического хэширования SHA-512. Какой типа функции сжатия используется в SHA-512?
  • Перечислите некоторые особенности функции криптографического хэширования. Какая функция сжатия используется в Whirlpool?
  • Сравните контрастные особенности SHA-512 и функций криптографического хэширования Whirlpool.
    •

    Упражнения

  • В SHA-512 покажите значение поля длины в шестнадцатеричной форме для следующих длин сообщения:
  • 1000 битов
  • 10 000 битов
  • 1000 000 битов
    •
  • В Whirlpool покажите значение поля длины в шестнадцатеричной форме для следующих длин сообщения:
  • 1000 битов
  • 10 000 битов
  • 1000 000 битов
  • Каково дополнение для SHA-512, если длина сообщения:
  • 5120 битов
  • 5121 бит
  • 6143 бита
  • Каково дополнение для Whirlpool, если длина сообщения:
  • 5120 битов
  • 5121 бит
  • 6143 бита
  • В каждом из следующих случаев покажите, что если два сообщения имеют одни и те же последние блоки, то их последний блок после дополнения поля длины один и тот же:
  • хэш-функция - SHA-512
  • хэш-функция - Whirlpool
  • Вычислите G0 в табл. 2.2, используя седьмое простое число ( 17 ).
  • Сравните функцию сжатия SHA-512 без последней операции (конечное сложение) с шифром Файстеля на 80 раундов. Показать совпадения и отличия.
  • Функцию сжатия, используемую в SHA-512 (рис. 2.10), можно представить как шифр с процессом шифрования с 80 раундами, если слова от W0 до W79, представляют как ключи раунда в одной из схем, рссмотренных в этой лекции (Рабина, Дэвиса-Меейра, Мэтиса-Мейера-Осеаса или Миагучи-Пренеля). Что это напоминает? Подсказка: Подумайте об эффекте операции конечного сложения.
  • Покажите, что SHA-512 может быть субъектом "атаки сведения к середине", если из функции сжатия удалена операция конечного сложения.
  • Составить таблицу, такую же как табл. 2.5, чтобы сравнить AES и Whirlpool.
  • Показать, что третья операция не может быть удалена из десятого раунда в шифре Whirlpool, но она должна быть удалена в шифре AES.
  • Найдите результат операции RotR12 (x), если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат операции ShL12(x), если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат операции Rotate(x),если x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат функции Conditional (x,y,z), если
    x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
 y = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
 z = 3234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Найдите результат функции Majority (x, y, z), если
    x = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
 y = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
 z = 3234 5678 ABCD 2345 34564 5678 ABCD 2468
  • Напишите процедуру (в псевдокоде) для вычисления RotRi (x) в SHA-512 (рис. 2.9).
  • Напишите процедуру (в псевдокоде), чтобы вычислить ShLi (x) в SHA-512 (рис. 2.9).
  • Напишите процедуру (в псевдокоде) для функции Conditional в SHA-512 (рис. 2.11).
  • Напишите процедуру (в псевдокоде) для функции Rotate в SHA-512 (рис. 2.11),
  • Напишите процедуру (в псевдокоде), чтобы вычислить начальный дайджест (значения A0 до H0 ) в SHA-512 (табл. 2.2).
  • Напишите процедуру (в псевдокоде), чтобы вычислить восемьдесят констант в SHA-512 (табл. 2.3).
  • Напишите процедуру (в псевдокоде) для алгоритма расширения слова в SHA-512, показанном на рис. 2.9. Рассмотрите два случая:
  • Использование массива 80 элементов, содержащих все слова.
  • Использование массива 16 элементов, содержащего только 16 слов одновременно.
  • Напишите процедуру (в псевдокоде) для функции сжатия в SHA-512.
  • Напишите процедуру (в псевдокоде), чтобы изменить блок 512 бит к 8 x8 матрицам состояний (рис. 2.4).
  • Напишите процедуру (в псевдокоде), чтобы изменить состояний 8 8 матрицу для блоков 512 бит (рис. 2.4).
  • Напишите процедуру (в псевдокоде) для преобразования SubBytes в шифре Whirlpool (рис. 2.16).
  • Напишите процедуру (в псевдокоде) для ShiftColumns преобразования в шифре Whirlpool (рис. 2.18).
  • Напишите процедуру (в псевдокоде) для MixRows преобразования в шифре Whirlpool (рис. 2.19).
  • Напишите процедуру (в псевдокоде) для AddRoundKey преобразования в шифре Whirlpool (рис. 2.20).
  • Напишите процедуру (в псевдокоде) для расширения ключа в шифре Whirlpool (рис. 2.21)
  • Напишите процедуру (в псевдокоде), чтобы создать константы раунда в шифре Whirlpool (рис. 2.20).
  • Напишите процедуру (в псевдокоде) для шифра Whirlpool.
  • Напишите процедуру (в псевдокоде) для функции криптографического хэширования Whirlpool.
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о SHA-1. Затем сравнить функцию сжатия в SHA-1 с такими же функциями в SHA-512. Каковы совпадения? Каковы отличия?
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о следующих функциях сжатия и сравнить их с SHA-512:
  • SHA-224
  • SHA-256
  • SHA-384
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о RIPEMD и сравнить ее с SHA-512.
  • Используйте Internet (или другие доступные ресурсы), чтобы найти информацию о HAVAL и сравнить ее с SHA-512.
    • Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^