MICKEY

Поделись знанием:
Перейти к: навигация, поиск

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





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

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

  • ключ 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 и битов из двух регистров для получения бита управления обеспечивает отсутствие корреляции между этим битом управления и контролируемым регистром. Благодаря этому энтропия не уменьшается при работе генератора.

Напишите отзыв о статье "MICKEY"

Примечания

  1. [www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf Steve Babbage, Matthew Dodd. The stream cipher MICKEY 2.0]  (англ.)
  2. [www.ecrypt.eu.org/stream/papersdir/2007/023.pdf T. Good and M. Benaissa. Hardware results for selected stream cipher candidates]  (англ.)

Ссылки

  • [www.ecrypt.eu.org/stream/mickey128.html Раздел eSTREAM, посвящённый MICKEY-128]
  • [www.ecrypt.eu.org/stream/mickeypf.html Раздел eSTREAM, посвящённый MICKEY 2.0]
  • [eprints.qut.edu.au/37243/1/Sultan_Al-Hinai_Thesis.pdf Sultan Zayid Mohammed Al-Hinai, Algebraic Attacks on Clock-Controlled Stream Ciphers]
  • [www.cosic.esat.kuleuven.be/publications/thesis-155.pdf Hongxu Zhao, Shiqi Li, Power Analysis Attacks on a Hardware Implementation of the Stream Cipher MICKEY]

Отрывок, характеризующий MICKEY

Курносое и черноволосатое лицо Васьки Денисова и вся его маленькая сбитая фигурка с его жилистою (с короткими пальцами, покрытыми волосами) кистью руки, в которой он держал ефес вынутой наголо сабли, было точно такое же, как и всегда, особенно к вечеру, после выпитых двух бутылок. Он был только более обыкновенного красен и, задрав свою мохнатую голову кверху, как птицы, когда они пьют, безжалостно вдавив своими маленькими ногами шпоры в бока доброго Бедуина, он, будто падая назад, поскакал к другому флангу эскадрона и хриплым голосом закричал, чтоб осмотрели пистолеты. Он подъехал к Кирстену. Штаб ротмистр, на широкой и степенной кобыле, шагом ехал навстречу Денисову. Штаб ротмистр, с своими длинными усами, был серьезен, как и всегда, только глаза его блестели больше обыкновенного.
– Да что? – сказал он Денисову, – не дойдет дело до драки. Вот увидишь, назад уйдем.
– Чог'т их знает, что делают – проворчал Денисов. – А! Г'остов! – крикнул он юнкеру, заметив его веселое лицо. – Ну, дождался.
И он улыбнулся одобрительно, видимо радуясь на юнкера.
Ростов почувствовал себя совершенно счастливым. В это время начальник показался на мосту. Денисов поскакал к нему.
– Ваше пг'евосходительство! позвольте атаковать! я их опг'окину.
– Какие тут атаки, – сказал начальник скучливым голосом, морщась, как от докучливой мухи. – И зачем вы тут стоите? Видите, фланкеры отступают. Ведите назад эскадрон.
Эскадрон перешел мост и вышел из под выстрелов, не потеряв ни одного человека. Вслед за ним перешел и второй эскадрон, бывший в цепи, и последние казаки очистили ту сторону.
Два эскадрона павлоградцев, перейдя мост, один за другим, пошли назад на гору. Полковой командир Карл Богданович Шуберт подъехал к эскадрону Денисова и ехал шагом недалеко от Ростова, не обращая на него никакого внимания, несмотря на то, что после бывшего столкновения за Телянина, они виделись теперь в первый раз. Ростов, чувствуя себя во фронте во власти человека, перед которым он теперь считал себя виноватым, не спускал глаз с атлетической спины, белокурого затылка и красной шеи полкового командира. Ростову то казалось, что Богданыч только притворяется невнимательным, и что вся цель его теперь состоит в том, чтоб испытать храбрость юнкера, и он выпрямлялся и весело оглядывался; то ему казалось, что Богданыч нарочно едет близко, чтобы показать Ростову свою храбрость. То ему думалось, что враг его теперь нарочно пошлет эскадрон в отчаянную атаку, чтобы наказать его, Ростова. То думалось, что после атаки он подойдет к нему и великодушно протянет ему, раненому, руку примирения.
Знакомая павлоградцам, с высокоподнятыми плечами, фигура Жеркова (он недавно выбыл из их полка) подъехала к полковому командиру. Жерков, после своего изгнания из главного штаба, не остался в полку, говоря, что он не дурак во фронте лямку тянуть, когда он при штабе, ничего не делая, получит наград больше, и умел пристроиться ординарцем к князю Багратиону. Он приехал к своему бывшему начальнику с приказанием от начальника ариергарда.
– Полковник, – сказал он с своею мрачною серьезностью, обращаясь ко врагу Ростова и оглядывая товарищей, – велено остановиться, мост зажечь.
– Кто велено? – угрюмо спросил полковник.
– Уж я и не знаю, полковник, кто велено , – серьезно отвечал корнет, – но только мне князь приказал: «Поезжай и скажи полковнику, чтобы гусары вернулись скорей и зажгли бы мост».
Вслед за Жерковым к гусарскому полковнику подъехал свитский офицер с тем же приказанием. Вслед за свитским офицером на казачьей лошади, которая насилу несла его галопом, подъехал толстый Несвицкий.
– Как же, полковник, – кричал он еще на езде, – я вам говорил мост зажечь, а теперь кто то переврал; там все с ума сходят, ничего не разберешь.
Полковник неторопливо остановил полк и обратился к Несвицкому:
– Вы мне говорили про горючие вещества, – сказал он, – а про то, чтобы зажигать, вы мне ничего не говорили.
– Да как же, батюшка, – заговорил, остановившись, Несвицкий, снимая фуражку и расправляя пухлой рукой мокрые от пота волосы, – как же не говорил, что мост зажечь, когда горючие вещества положили?
– Я вам не «батюшка», господин штаб офицер, а вы мне не говорили, чтоб мост зажигайт! Я служба знаю, и мне в привычка приказание строго исполняйт. Вы сказали, мост зажгут, а кто зажгут, я святым духом не могу знайт…
– Ну, вот всегда так, – махнув рукой, сказал Несвицкий. – Ты как здесь? – обратился он к Жеркову.
– Да за тем же. Однако ты отсырел, дай я тебя выжму.
– Вы сказали, господин штаб офицер, – продолжал полковник обиженным тоном…
– Полковник, – перебил свитский офицер, – надо торопиться, а то неприятель пододвинет орудия на картечный выстрел.
Полковник молча посмотрел на свитского офицера, на толстого штаб офицера, на Жеркова и нахмурился.
– Я буду мост зажигайт, – сказал он торжественным тоном, как будто бы выражал этим, что, несмотря на все делаемые ему неприятности, он всё таки сделает то, что должно.
Ударив своими длинными мускулистыми ногами лошадь, как будто она была во всем виновата, полковник выдвинулся вперед к 2 му эскадрону, тому самому, в котором служил Ростов под командою Денисова, скомандовал вернуться назад к мосту.
«Ну, так и есть, – подумал Ростов, – он хочет испытать меня! – Сердце его сжалось, и кровь бросилась к лицу. – Пускай посмотрит, трус ли я» – подумал он.
Опять на всех веселых лицах людей эскадрона появилась та серьезная черта, которая была на них в то время, как они стояли под ядрами. Ростов, не спуская глаз, смотрел на своего врага, полкового командира, желая найти на его лице подтверждение своих догадок; но полковник ни разу не взглянул на Ростова, а смотрел, как всегда во фронте, строго и торжественно. Послышалась команда.
– Живо! Живо! – проговорило около него несколько голосов.
Цепляясь саблями за поводья, гремя шпорами и торопясь, слезали гусары, сами не зная, что они будут делать. Гусары крестились. Ростов уже не смотрел на полкового командира, – ему некогда было. Он боялся, с замиранием сердца боялся, как бы ему не отстать от гусар. Рука его дрожала, когда он передавал лошадь коноводу, и он чувствовал, как со стуком приливает кровь к его сердцу. Денисов, заваливаясь назад и крича что то, проехал мимо него. Ростов ничего не видел, кроме бежавших вокруг него гусар, цеплявшихся шпорами и бренчавших саблями.
– Носилки! – крикнул чей то голос сзади.
Ростов не подумал о том, что значит требование носилок: он бежал, стараясь только быть впереди всех; но у самого моста он, не смотря под ноги, попал в вязкую, растоптанную грязь и, споткнувшись, упал на руки. Его обежали другие.
– По обоий сторона, ротмистр, – послышался ему голос полкового командира, который, заехав вперед, стал верхом недалеко от моста с торжествующим и веселым лицом.
Ростов, обтирая испачканные руки о рейтузы, оглянулся на своего врага и хотел бежать дальше, полагая, что чем он дальше уйдет вперед, тем будет лучше. Но Богданыч, хотя и не глядел и не узнал Ростова, крикнул на него:
– Кто по средине моста бежит? На права сторона! Юнкер, назад! – сердито закричал он и обратился к Денисову, который, щеголяя храбростью, въехал верхом на доски моста.
– Зачем рисковайт, ротмистр! Вы бы слезали, – сказал полковник.
– Э! виноватого найдет, – отвечал Васька Денисов, поворачиваясь на седле.

Между тем Несвицкий, Жерков и свитский офицер стояли вместе вне выстрелов и смотрели то на эту небольшую кучку людей в желтых киверах, темнозеленых куртках, расшитых снурками, и синих рейтузах, копошившихся у моста, то на ту сторону, на приближавшиеся вдалеке синие капоты и группы с лошадьми, которые легко можно было признать за орудия.
«Зажгут или не зажгут мост? Кто прежде? Они добегут и зажгут мост, или французы подъедут на картечный выстрел и перебьют их?» Эти вопросы с замиранием сердца невольно задавал себе каждый из того большого количества войск, которые стояли над мостом и при ярком вечернем свете смотрели на мост и гусаров и на ту сторону, на подвигавшиеся синие капоты со штыками и орудиями.
– Ох! достанется гусарам! – говорил Несвицкий, – не дальше картечного выстрела теперь.
– Напрасно он так много людей повел, – сказал свитский офицер.
– И в самом деле, – сказал Несвицкий. – Тут бы двух молодцов послать, всё равно бы.
– Ах, ваше сиятельство, – вмешался Жерков, не спуская глаз с гусар, но всё с своею наивною манерой, из за которой нельзя было догадаться, серьезно ли, что он говорит, или нет. – Ах, ваше сиятельство! Как вы судите! Двух человек послать, а нам то кто же Владимира с бантом даст? А так то, хоть и поколотят, да можно эскадрон представить и самому бантик получить. Наш Богданыч порядки знает.
– Ну, – сказал свитский офицер, – это картечь!
Он показывал на французские орудия, которые снимались с передков и поспешно отъезжали.
На французской стороне, в тех группах, где были орудия, показался дымок, другой, третий, почти в одно время, и в ту минуту, как долетел звук первого выстрела, показался четвертый. Два звука, один за другим, и третий.
– О, ох! – охнул Несвицкий, как будто от жгучей боли, хватая за руку свитского офицера. – Посмотрите, упал один, упал, упал!
– Два, кажется?
– Был бы я царь, никогда бы не воевал, – сказал Несвицкий, отворачиваясь.
Французские орудия опять поспешно заряжали. Пехота в синих капотах бегом двинулась к мосту. Опять, но в разных промежутках, показались дымки, и защелкала и затрещала картечь по мосту. Но в этот раз Несвицкий не мог видеть того, что делалось на мосту. С моста поднялся густой дым. Гусары успели зажечь мост, и французские батареи стреляли по ним уже не для того, чтобы помешать, а для того, что орудия были наведены и было по ком стрелять.