MICKEY

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии, MICKEY (англ. Mutual Irregular Clocking KEYstream generator) — алгоритм потокового шифрования. Существует два варианта этого алгоритма — с длиной ключа 80 бит (MICKEY) и 128 бит (MICKEY-128). Он был разработан Стивом Бэббиджем и Мэтью Доддом в 2005 году с целью использования в системах с ограниченными ресурсами. Этот алгоритм имеет простую аппаратную реализацию при высокой степени защищённости. В нём используется нерегулярное тактирование сдвиговых регистров, а также новые методы, обеспечивающие достаточно большой период и псевдослучайность ключевой последовательности и устойчивость к атакам[1]. Алгоритм MICKEY участвовал в конкурсном проекте eSTREAM, организованным сообществом eCRYPT. Текущая версия алгоритма — 2.0. Она вошла в портфолио eCRYPT, как потоковый шифр для аппаратной реализации[2].

Взаимное управление тактированием регистров R и S

Терминология

[править | править код]

Входные параметры:

  • ключ K длиной 80 бит, его биты обозначаются k0, k1 …, k79;
  • инициализирующая переменная IV длиной от 0 до 80 бит, её биты обозначаются iv0, …, ivдлина IV — 1.

Ключевая последовательность обозначается z0, z1, z2.

Ограничения использования

[править | править код]

Максимальная длина ключевой последовательности, полученной с помощью одной пары (K, IV) составляет 240 бит. Однако допускается получение 240 таких последовательностей при использовании одного K при условии, что IV выбирается разными для каждой новой последовательности.

Устройство генератора ключевой последовательности

[править | править код]

Генератор состоит из двух регистров R и S, каждый из которых имеет длину 100 бит.

Биты этих регистров обозначаются r0, r1, …, r99 и s0, s1, …, s99 соответственно.

Сдвиг регистра R

[править | править код]

Набор входов обратной связи регистра R обозначается RTAPS.

RTAPS = { 0, 1, 3, 4, 5, 6, 9, 12, 13, 16, 19, 20, 21, 22, 25, 28, 37, 38, 41, 42, 45, 46, 50, 52, 54, 56,

58, 60, 61, 63, 64, 65, 66, 67, 71, 72, 79, 80, 81, 82, 87, 88, 89, 90, 91, 92, 94, 95, 96, 97 }


Операция сдвига CLOCK_R (R, INPUT_BIT_R, CONTROL_BIT_R) определяется следующей последовательностью действий:

  • пусть r0, r1, …, r99 — состояние регистра до сдвига, а r'0, r'1, …, r'99 — после сдвига;
  • FEEDBACK_BIT = r99 ⊕ INPUT_BIT_R;
  • для 1 ≤ i ≤ 99, r'i = ri-1; r'0 = 0;
  • для 0 ≤ i ≤ 99, если i ∈ RTAPS, r'i = r'i ⊕ FEEDBACK_BIT;
  • если CONTROL_BIT_R = 1, то
    • для 0 ≤ i ≤ 99, r'i = r'i ⊕ ri.

Сдвиг регистра S

[править | править код]

Определим четыре последовательности COMP01 … COMP098, COMP11 … COMP198, FB00 … FB099, FB10 … FB99 в соответствии с таблицей:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
COMP0i 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0
COMP1i 1 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1
FB0i 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1
FB1i 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0
i 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
COMP0i 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1
COMP1i 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1
FB0i 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1
FB1i 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0
i 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
COMP0i 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1
COMP1i 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1
FB0i 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
FB1i 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1
i 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
COMP0i 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1
COMP1i 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0
FB0i 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0
FB1i 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1

Функция сдвига регистра S CLOCK_S определяется как последовательность действий:

  • пусть s0, s1, …, s99 — состояние регистра до сдвига, а s'0, s'1, …, s'99 — после сдвига. ŝ0, ŝ1, …, ŝ99 будем обозначать промежуточное состояние регистра;
  • FEEDBACK_BIT = s99 ⊕ INPUT_BIT_S;
  • для 1 ≤ i ≤ 98, ŝi = si-1 ⊕ ((si ⊕ COMP0i)•(si+1 ⊕ COMP1i)); ŝ0 = 0; ŝ99 = s98;
  • если CONTROL_BIT_S = 0, то
    • для 0 ≤ i ≤ 99, s'i = ŝi ⊕ (FB0i • FEEDBACK_BIT);
  • если CONTROL_BIT_S = 1, то
    • для 0 ≤ i ≤ 99, s'i = ŝi ⊕ (FB1i • FEEDBACK_BIT).

Управление тактированием всего генератора

[править | править код]

Определим функцию CLOCK_KG (R, S, MIXING, INPUT_BIT) следующим образом:

  • СONTROL_BIT_R = s34 ⊕ r67;
  • CONTROL_BIT_S = s67 ⊕ r33;
  • если MIXING = TRUE, тогда INPUT_BIT_R = INPUT_BIT ⊕ s50, а если MIXING = FALSE, тогда INPUT_BIT_R = INPUT_BIT;
  • INPUT_BIT_S = INPUT_BIT;
  • CLOCK_R (R, INPUT_BIT_R, CONTROL_BIT_R);
  • CLOCK_S (S, INPUT_BIT_S, CONTROL_BIT_S).

Загрузка ключа и инициализация

[править | править код]

Регистры инициализируются с использованием начальных параметров K и IV следующим образом:

  • в регистры R и S записываются нули;
  • загружается IV — для 0 ≤ i ≤ длина IV — 1,
    • CLOCK_KG (R, S, MIXING = TRUE, INPUT_BIT = ivi);
  • загружается K — для 0 ≤ i ≤ 79,
    • CLOCK_KG (R, S, MIXING = TRUE, INPUT_BIT = ki);
  • для 0 ≤ i ≤ 99,
    • CLOCK_KG (R, S, MIXING =TRUE, INPUT_BIT = 0).

Генерация ключевой последовательности

[править | править код]

После загрузки и инициализации можно начинать генерировать ключевую последовательность z0, z1, , zL-1:

  • для 0 ≤ i ≤ L − 1,
    • zi = r0 ⊕ s0;
    • CLOCK_KG (R, S, MIXING = FALSE, INPUT_BIT = 0).

Особенности

[править | править код]

Нерегулярное тактирование регистра R

[править | править код]
  • Когда флаг CONTROL_BIT_R = 0, R представляет собой обычный регистр сдвига с линейной обратной связью Галуа-типа, с примитивным характеристическим многочленом CR = x100 + Σxi, где i ∈ RTAPS и входным битом INPUT_BIT_R, примешиваемым к обратной связи операцией XOR. Если представить элементы поля GF(2100) многочленами Σrixi, где 0 ≤ i ≤ 99 по модулю CR(x), то сдвиг регистра — это умножение на x в этом поле.
  • Когда флаг CONTROL_BIT_R = 1, то помимо сдвига каждого бита происходит его сложение по модулю два с предыдущем значением бита, что соответствует умножению на x + 1 в том же поле. Характеристический многочлен CR(x) выбран таким образом, что он является делителем многочлена xJ + x + 1, где J = 250 — 157. Следовательно такт регистра R при CONTROL_BIT_R = 1 соответствует его сдвигу J раз.

Причины использования нерегулярного тактирования

[править | править код]

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

  1. сдвиг регистра сначала m раз, а потом n раз дает тот же результат, что и сдвиг регистра сначала n раз, а потом m раз, то есть разные варианты тактирования коммутируют. Это дает преимущество криптоаналитику, так как нет необходимости определять порядок таких операций;
  2. также, если вариантов тактирования регистра много, то, например, пять сдвигов регистра дает одиночная и четырёхкратная операция тактирования или двукратная и трёхкратная, что ещё больше уменьшает количество комбинаций для перебора, упрощая статистическую атаку;
  3. n-кратный сдвиг может произойти после любого сдвига.

При разработке в основу шифра MICKEY легли следующие идеи:

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

В отношении указанных свойств 1-3, ухудшающих криптостойкость, MICKEY ведёт себя следующим образом:

  1. верно для регистра R, так как clockJ • clock1 = clock1 • clockJ, но не верно для регистра S, операции тактирования которого не коммутируют.
  2. не верно для обоих регистров. Для R для любых t ≤ 240 и u существует не более одной пары n1 и nJ таких, что 0 ≤ n1,nJ ≤ t, n1 + nJ = t и n1 + nJJ = u, где n1 и nJ соответствуют однократному и J-кратному сдвигу.
  3. не верно для обоих регистров. Для R для любого заданного u существует не более одной тройки t, n1 и nJ таких, что t ≤ 240, 0 ≤ n1,nJ ≤ t, n1 + nJ = t и n1 + nJJ = u.

Регистр R обеспечивает неповторяемость состояния генератора и хорошие локальные статистические свойства. Влияние регистра R на S также предотвращает зацикливание S с маленьким периодом. Если J ≤ 260, то состояние регистра R не повторится при генерации ключевой последовательности длиной вплоть до 240 бит. А если J ≥ 240, то свойство (2) не верно.

Выбор битов управления тактированием

[править | править код]

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

Количество энтропии

[править | править код]

Так как нерегулярное тактирование управляется битами из самого генератора, это может уменьшить количество энтропии в генераторе. Использование операции XOR и битов из двух регистров для получения бита управления обеспечивает отсутствие корреляции между этим битом управления и контролируемым регистром. Благодаря этому энтропия не уменьшается при работе генератора.

Примечания

[править | править код]