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 бит, его биты обозначаются k₀, k₁ …, k₇₉;
инициализирующая переменная IV длиной от 0 до 80 бит, её биты обозначаются iv₀, …, iv_{длина IV — 1}.

Ключевая последовательность обозначается z₀, z₁, z₂ ….

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

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

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

РегистрыПравить

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

Биты этих регистров обозначаются r₀, r₁, …, r₉₉ и s₀, s₁, …, s₉₉ соответственно.

Сдвиг регистра 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) определяется следующей последовательностью действий:

пусть r₀, r₁, …, r₉₉ — состояние регистра до сдвига, а r'₀, r'₁, …, r'₉₉ — после сдвига;
FEEDBACK_BIT = r₉₉ ⊕ INPUT_BIT_R;
для 1 ≤ i ≤ 99, r'_i = r_i-1; r'₀ = 0;
для 0 ≤ i ≤ 99, если i ∈ RTAPS, r'_i = r'_i ⊕ FEEDBACK_BIT;
если CONTROL_BIT_R = 1, то
- для 0 ≤ i ≤ 99, r'_i = r'_i ⊕ r_i.

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

Определим четыре последовательности COMP0₁ … COMP0₉₈, COMP1₁ … COMP1₉₈, FB0₀ … FB0₉₉, FB1₀ … FB₉₉ в соответствии с таблицей:

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
COMP0_i		0	0	0	1	1	0	0	0	1	0	1	1	1	1	0	1	0	0	1	0	1	0	1	0
COMP1_i		1	0	1	1	0	0	1	0	1	1	1	1	0	0	1	0	1	0	0	0	1	1	0	1
FB0_i	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
FB1_i	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
COMP0_i	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
COMP1_i	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
FB0_i	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
FB1_i	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
COMP0_i	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
COMP1_i	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
FB0_i	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
FB1_i	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
COMP0_i	1	1	1	0	1	0	1	1	1	1	1	1	0	1	0	1	0	0	0	0	0	0	1	1
COMP1_i	1	1	1	0	0	0	1	0	0	0	0	1	1	1	0	0	0	1	0	0	1	1	0	0
FB0_i	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
FB1_i	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 определяется как последовательность действий:

пусть s₀, s₁, …, s₉₉ — состояние регистра до сдвига, а s'₀, s'₁, …, s'₉₉ — после сдвига. ŝ₀, ŝ₁, …, ŝ₉₉ будем обозначать промежуточное состояние регистра;
FEEDBACK_BIT = s₉₉ ⊕ INPUT_BIT_S;
для 1 ≤ i ≤ 98, ŝ_i = s_i-1 ⊕ ((s_i ⊕ COMP0_i)•(s_i+1 ⊕ COMP1_i)); ŝ₀ = 0; ŝ₉₉ = s₉₈;
если CONTROL_BIT_S = 0, то
- для 0 ≤ i ≤ 99, s'_i = ŝ_i ⊕ (FB0_i • FEEDBACK_BIT);
если CONTROL_BIT_S = 1, то
- для 0 ≤ i ≤ 99, s'_i = ŝ_i ⊕ (FB1_i • FEEDBACK_BIT).

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

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

СONTROL_BIT_R = s₃₄ ⊕ r₆₇;
CONTROL_BIT_S = s₆₇ ⊕ r₃₃;
если MIXING = TRUE, тогда INPUT_BIT_R = INPUT_BIT ⊕ s₅₀, а если 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 = iv_i);
загружается K — для 0 ≤ i ≤ 79,
- CLOCK_KG (R, S, MIXING = TRUE, INPUT_BIT = k_i);
для 0 ≤ i ≤ 99,
- CLOCK_KG (R, S, MIXING =TRUE, INPUT_BIT = 0).

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

После загрузки и инициализации можно начинать генерировать ключевую последовательность z₀, z₁, …, z_L-1:

для 0 ≤ i ≤ L − 1,
- z_i = r₀ ⊕ s₀;
- CLOCK_KG (R, S, MIXING = FALSE, INPUT_BIT = 0).

ОсобенностиПравить

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

Когда флаг CONTROL_BIT_R = 0, R представляет собой обычный регистр сдвига с линейной обратной связью Галуа-типа, с примитивным характеристическим многочленом C_R = x¹⁰⁰ + Σxⁱ, где i ∈ RTAPS и входным битом INPUT_BIT_R, примешиваемым к обратной связи операцией XOR. Если представить элементы поля GF(2¹⁰⁰) многочленами Σr_ixⁱ, где 0 ≤ i ≤ 99 по модулю C_R(x), то сдвиг регистра — это умножение на x в этом поле.

Когда флаг CONTROL_BIT_R = 1, то помимо сдвига каждого бита происходит его сложение по модулю два с предыдущем значением бита, что соответствует умножению на x + 1 в том же поле. Характеристический многочлен C_R(x) выбран таким образом, что он является делителем многочлена x^J + x + 1, где J = 2⁵⁰ — 157. Следовательно такт регистра R при CONTROL_BIT_R = 1 соответствует его сдвигу J раз.

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

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

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

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

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

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

верно для регистра R, так как clock^J • clock¹ = clock¹ • clock^J, но не верно для регистра S, операции тактирования которого не коммутируют.
не верно для обоих регистров. Для R для любых t ≤ 2⁴⁰ и u существует не более одной пары n₁ и n_J таких, что 0 ≤ n₁,n_J ≤ t, n₁ + n_J = t и n₁ + n_JJ = u, где n₁ и n_J соответствуют однократному и J-кратному сдвигу.
не верно для обоих регистров. Для R для любого заданного u существует не более одной тройки t, n₁ и n_J таких, что t ≤ 2⁴⁰, 0 ≤ n₁,n_J ≤ t, n₁ + n_J = t и n₁ + n_JJ = u.

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

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

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

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

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

ПримечанияПравить

↑ Steve Babbage, Matthew Dodd. The stream cipher MICKEY 2.0 Архивная копия от 27 мая 2011 на Wayback Machine (англ.)
↑ T. Good and M. Benaissa. Hardware results for selected stream cipher candidates Архивная копия от 2 марта 2011 на Wayback Machine (англ.)

СсылкиПравить

[1] Steve Babbage, Matthew Dodd. The stream cipher MICKEY 2.0 Архивная копия от 27 мая 2011 на Wayback Machine (англ.)

[2] T. Good and M. Benaissa. Hardware results for selected stream cipher candidates Архивная копия от 2 марта 2011 на Wayback Machine (англ.)

[1]

[2]