Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.8 MDC Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.6 HAVAL   Содержание   Предметный указатель

5.2.7 Схемы хэширования, использующие алгоритмы блочного шифрования

Идея использовать алгоритм блочного шифрования [Schnr], в стойкости которого мы уверены, для построения надежных схем хэширования выглядит естественной. Напрашивается мысль использовать алгоритм блочного шифрования в режиме "с зацеплением" при нулевой синхропосылке. При этом считать хэш-кодом последний шифрблок. Именно такой подход, использующий DES-алгоритм, описан в предложенном стандарте США: FIPS 113 [NBS1]. Очевидно, что на роль DES-алгоритма здесь годится произвольный блочный шифр [BPS], [DGV2], [Kn].

Однако при таком подходе возникают две проблемы. Во-первых, размер блока большинства блочных шифров (для DESа -- 64 бита) недостаточен для того, чтобы хэш-функция была устойчива против метода на основе парадокса дня рождения. Во-вторых, предлагаемый метод требует задания некоторого ключа, на котором происходит шифрование. В дальнейшем этот ключ необходимо держать в секрете, ибо злоумышленник, зная этот ключ и хэш-значение, может выполнить процедуру в обратном направлении. Следующим шагом в развитии идеи использовать блочный шифр для хэширования является подход, при котором очередной блок текста подается в качестве ключа, а хэш-значение предыдущего шага -- в качестве входного блока. Выход алгоритма блочного шифрования является текущим хэш-значением (схема Рабина). Существует масса модификаций этого метода, в том числе хэш-функции, выход которых в два раза длиннее блока. В ряде модификаций промежуточное хэш-значение суммируется покоординатно по модулю 2 с блоком текста. В этом случае подразумевается, что размер ключа и блока у шифра совпадают. В литературе встречаются 12 различных схем хэширования для случая, когда размер ключа и блока у шифра совпадают:     1) $ H_i=E_{M_i}(H_{i-1})\oplus H_{i-1}$ (схема Дэвиса -- Мейера);

    2) $ H_i=E_{H_{i-1}}(M_{i})\oplus H_{i-1}\oplus M_i$ (схема Миягучи);

    3) $ H_i=E_{H_{i-1}}(M_{i})\oplus M_i$ (схема Матиаса, Мейера, Осиаса);

    4) $ H_i=E_{H_{i-1}}(H_{i-1}\oplus M_{i})\oplus
H_{i-1}\oplus M_i$;

    5) $ H_i=E_{H_{i-1}}(H_{i-1}\oplus M_{i})\oplus M_i$;

    6) $ H_i=E_{M_{i}}(M_{i}\oplus H_{i-1})\oplus M_i\oplus
H_{i-1}$;

    7) $ H_i=E_{M_{i}}(H_{i-1})\oplus M_i\oplus H_{i-1}$;

    8) $ H_i=E_{M_{i}}(M_{i}\oplus H_{i-1})\oplus H_{i-1}$;

    9) $ H_i=E_{H_{i-1}\oplus M_i}(M_{i})\oplus H_{i-1}$;

    10) $ H_i=E_{H_{i-1}\oplus M_{i}}(H_{i-1})\oplus
H_{i-1}$;

    11) $ H_i=E_{H_{i-1}\oplus M_{i}}(M_{i})\oplus M_{i}$;

    12) $ H_i=E_{H_{i-1}\oplus M_{i}}(H_{i-1})\oplus M_{i}$, где $ E_k(M)$ обозначает результат применения алгоритма блочного шифрования с ключом $ k$ к блоку $ M$.

Во всех подобных схемах полагают $ H_0=I_H$, где $ I_H$ -- начальное значение.

Для алгоритмов блочного шифрования с размером ключа в два раза большим чем размер шифруемого блока (например, IDEA) в 1992 году была предложена модифицированная схема Дэвиса -- Мейера: $ H_0=I_H$, где $ I_H$ -- начальное значение;

$ H_i=E_{H_{i-1},M_i}(H_{i-1})$.

Стойкость подобных схем зависит от криптографических и иных свойств алгоритмов блочного шифрования, лежащих в их основе. В частности, даже если алгоритм шифрования является стойким, некоторые из предложенных схем обладают коллизиями [MOI]. К подобным эффектам могут приводить такие свойства алгоритма шифрования как комплиментарность (шифрование инвертированного открытого текста на инвертированном ключе приводит к инвертированному шифртексту), наличие слабых и полуслабых ключей и т. п.

Еще одной слабостью указанных выше схем хэширования является то, что размер хэш-кода совпадает с размером блока алгоритма шифрования. Чаще всего размер блока недостаточен для того, чтобы схема была стойкой против атаки на базе "парадокса дня рождения". Поэтому были предприняты попытки построения хэш-алгоритмов на базе блочного шифра с размером хэш-кода в $ k$ раз (как правило, $ k=2$) большим, чем размер блока алгоритма шифрования:


Схема Приниля -- Босселэра -- Гувертса -- Вандервалле [PrBGV] $ G_0=I_G$, где $ I_G$ -- начальное значение;

$ H_0=I_H$, где $ I_H$ -- еще одно начальное значение;

$ G_i=E_{H_{i-1}\oplus L_i}(R_i\oplus G_{i-1})\oplus
R_i\oplus G_{i-1}\oplus H_{i-1}$;

$ H_i=E_{R_{i}\oplus L_i}(H_{i-1}\oplus G_{i-1})\oplus
L_i\oplus G_{i-1}\oplus H_{i-1}$, где $ L_i$, $ R_i$ -- левая и правая половины очередного блока хэшируемого текста. Хэш-кодом является конкатенация последних значений $ G_i$, $ H_i$.

Вскоре после опубликования данной схемы появились работы, показавшие, что схема слабая (см. [Lai], [LaM]).


Схема Кискате -- Жиро [QG] $ G_0=I_G$, где $ I_G$ -- начальное значение;

$ H_0=I_H$, где $ I_H$ -- еще одно начальное значение;

$ W_i +E_{L_i}(R_i\oplus G_{i-1})\oplus R_i\oplus H_{i-1}$;

$ G_i =E_{R_i}(W_i\oplus L_i)\oplus L_i\oplus G_{i-1}\oplus
H_{i-1}$;

$ H_i =W_i\oplus G_{i-1}$, где $ L_i$, $ R_i$ -- соседние блоки хэшируемого текста. Хэш-кодом является конкатенация последних значений $ G_i$, $ H_i$.

В 1989 году данный алгоритм рассматривался в качестве проекта стандарта ISO. В дальнейшем были выявлены его слабости (см. [Co], [Lai]) и от него отказались.


Сдвоенная схема Дэвиса -- Мейера [PS], [Pr] $ G_0=I_G$, где $ I_G$ -- начальное значение;

$ H_0=I_H$, где $ I_H$ -- еще одно начальное значение;

$ W_i =E_{G_{i-1},M_i}(H_{i-1})$;

$ G_i =G_{i-1}\oplus E_{M_i, W_i}(G_{i-1})$;

$ H_i = W_i\oplus H_{i-1}$.

Хэш-кодом является конкатенация последних значений $ G_i$, $ H_i$.

В оригинальной работе (см. [LaM], [Lai]) предложено в качестве алгоритма шифрования использовать схему IDEA. В таком варианте, на сегодняшний день не известно результатов, предлагающих метод построения коллизий, эффективнее, чем метод, основанный на "парадоксе дня рождения".


Последовательная схема Дэвиса -- Мейера [PS], [Pr] $ G_0=I_G$, где $ I_G$ -- начальное значение;

$ H_0=I_H$, где $ I_H$ -- еще одно начальное значение;

$ G_i=G_{i-1}\oplus E_{M_i,H_{i-1}}(\qopname\relax o{not}G_{i-1})$;

$ H_i=H_{i-1}\oplus E_{G_{i-1},M_i}(H_{i-1})$.

Хэш-кодом является конкатенация последних значений $ G_i$, $ H_i$.

В оригинальной работе (см. [LaM], [Lai]) предложено в качестве алгоритма шифрования использовать схему IDEA. В таком варианте, на сегодняшний день не известно результатов, предлагающих метод построения коллизий, эффективнее, чем метод, основанный на "парадоксе дня рождения".


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.8 MDC Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.6 HAVAL   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   

TopList Rambler's Top100