WAKE ( англ. W ord A uto K ey E ncryption , шифрование слов на автоматическом ключе ) — алгоритм поточного шифрования на автоматическом ключе, разработанный в 1993 году. Изначально проектировался как среднескоростная система шифрования (скорость в поточных шифрах измеряется в циклах на байт шифруемого открытого текста ) блоков (минимального количества информации, которое может быть обработано алгоритмом; в данном случае блок составляет 32 бита ), обладающая высокой безопасностью. По мнению автора, является простым алгоритмом быстрого шифрования, подходящим для обработки больших массивов данных, а также коротких сообщений, где изменяется только секретный ключ . Подходит для использования хешей на секретных ключах, используемых при верификации . Одним из примеров возможного практического использования данного алгоритма является шифрование потока текстовых данных в SMS . Из-за большого размера блоков не может быть использован в коммуникациях в режиме реального времени .

Свойства

Алгоритм работает в режиме CFB — предыдущее слово шифрованной последовательности служит основанием генерации следующего. Однако существуют модификации алгоритма, связанные с изменением процесса генерации ключа и позволяющие работать в режимах OFB и ROFB (Reverse OFB) . В гамме шифра используются 32- битовые слова , а длина стартового ключа составляет 128 бит . Также в алгоритме используется S-блок замены , состоящий из 256 32-битных слов. В работе используются четыре переменные , для лучшей производительности в этом качестве нужно использовать регистры . При работе полагается повторное использование таблиц в кэше и наличие большого пространства состояний . Это означает, что кэш данных должен без проблем вмещать таблицу из 256 слов .

Алгоритм является достаточно быстрым — на 32-битовых процессорах VLIW архитектуры оценочная производительность составляет 6.38 циклов на байт, что превышает аналогичный показатель алгоритма SEAL , но уступает RC4 (3.5 и 10.6 циклов на байт, соответственно) .

Шифр поддается криптоанализу, а именно атакам по подобранному открытому тексту и подобранному шифротексту .

Структура алгоритма

Алгоритм строится на основе каскадного использования функции смешения ${\displaystyle M(x,y,S)=(x+y)>>8\oplus S_{(x+y)\land 255}}$ ( ${\displaystyle \land }$ — знак побитовой конъюнкции , ${\displaystyle \oplus }$ — битовая операция исключающего «ИЛИ» , битовый сдвиг ${\displaystyle >>}$ является логическим ) , которая при помощи ${\displaystyle S}$ -блока замены преобразует 32-битовые слова ${\displaystyle x}$ и ${\displaystyle y}$ , подаваемые на вход, в 32-битовое слово на выходе. Причем слова в ${\displaystyle S}$ -блоке составляются таким образом, что множество старших байтов этих слов представляет собой перестановку от 0 до 255 (первые байты каждого слова являются уникальными), тогда как оставшиеся 3 байта заполняются случайным образом . Функция смешения ${\displaystyle M(x,y,S)}$ сделана реверсивной из таких соображений, что знания одного из слов на входе и слова на выходе будет достаточно для восстановления второго неизвестного на входе .

WAKE состоит из четырёх каскадов функции ${\displaystyle M(x,y,S)}$ с обратными связями по каждому и ещё одной на всю группу каскадов. Такое количество выбрано, как минимально возможное для полной (англ.) ( данных в слове (то есть при изменении хотя бы одного бита ключа происходит полное изменение результата работы алгоритма шифрования), происходящей из-за того, что ${\displaystyle S}$ -блок осуществляет нелинейное преобразование , и использование побитового «И» и исключающего «ИЛИ» также вносит небольшую нелинейность .

Описание алгоритма

Процесс шифрования происходит в три этапа :

1. Процесс генерации S-блока;
2. Процесс генерации автоключа;
3. Непосредственно шифрование и расшифровывание.

Процесс генерации S-блока

В первую очередь происходит инициализация первых значений ${\displaystyle S}$ -блока (таблицы замены) секретным ключом. Даётся пример алгоритма заполнения данной таблицы :

1. Инициализировать вспомогательную таблицу ${\displaystyle s}$ , состоящую из 8 слов, имеющих между собой перестановку первых трех бит:

   ${\displaystyle s[0]:726a8f3b}$

   ${\displaystyle s[1]:e69a3b5c}$

   ${\displaystyle s[2]:d3c71fe5}$

   ${\displaystyle s[3]:ab3c73d2}$

   ${\displaystyle s[4]:4d3a8eb3}$

   ${\displaystyle s[5]:0396d6e8}$

   ${\displaystyle s[6]:3d4c2f7a}$

   ${\displaystyle s[7]:9ee27cf3}$

2. Копировать ключ ${\displaystyle K}$ в первые 4 слова ${\displaystyle S}$ таким образом, что:

   ${\displaystyle S[0]...S[3]:}$

   ${\displaystyle S[0]=K[0];\ S[1]=K[1]}$

   ${\displaystyle S[2]=K[2];\ S[3]=K[3]}$ , где ${\displaystyle K[0],\ K[1],\ K[2],\ K[3]}$ — есть результат разбиения ключа на четыре равные части.

3. Остальные слова образовать в цикле :

   ${\displaystyle for\ n=4\quad to\quad 255:}$

   ${\displaystyle x=S[n-1]+S[n-4]}$

   ${\displaystyle S[n]=x>>3\oplus s[x\wedge 7]}$

4. Произвести суммирование:

   ${\displaystyle for\ n=0\quad to\quad 22:}$

   ${\displaystyle S[n]\ +\!=S[n+89]}$ .

   Таким образом, даже первые несколько слов будут зависеть от всех бит ${\displaystyle K}$ .

5. Определить вспомогательные переменные:

   ${\displaystyle X=S[33]}$

   ${\displaystyle Z=S[59]\lor 0{\text{x}}01000001}$

   ${\displaystyle Z=Z\land 0{\text{x}}FF7FFFFF}$

   ${\displaystyle X=(X\land 0{\text{x}}FF7FFFFFh)+Z}$

6. Осуществить перестановку в первом байте слов таблицы:

   ${\displaystyle for\ n=0\quad to\quad 255:}$

   ${\displaystyle X=(X\land 0{\text{x}}FF7FFFFF)+Z}$

   ${\displaystyle S[n]=S[n]\land 0{\text{x}}00FFFFFF\oplus X}$

7. Инициализировать следующие переменные:

   ${\displaystyle S[256]=S[0]}$

   ${\displaystyle X=X\land 255}$

8. Перемешать между собой слова в ${\displaystyle S}$ :

   ${\displaystyle for\ n=0\quad to\quad 255:}$

   ${\displaystyle Temp=(S[n\oplus X]\oplus X)\land 255}$

   ${\displaystyle S[n]=S[Temp]}$

   ${\displaystyle S[X]=S[n+1]}$

Метод построения может быть легко изменён, и вышеприведенный алгоритм является лишь примером. Главное, чтобы результат алгоритма обладал всеми свойствами, представленными из соображений криптографической стойкости ${\displaystyle S}$ -блока . Так, например, можно заполнить таблицу слов случайными числами , но в таком случае происходит утечка информации о повторяющихся и нулевых записях таблицы, не превышающая 1.5 бита на каждую запись. Тем не менее, создатель алгоритма утверждает, что процесс перестановки на старших байтах слов существенно помогает снизить утечку. А перестановка на всех четырёх байтах ещё больше нивелирует вероятность прочтения таблицы. Таким образом, алгоритм заполнения, приведенный выше, является компромиссом между безопасностью и скоростью, так как в нём осуществляется перестановка именно старших байт слов ${\displaystyle S}$ -блока .

Процесс генерации автоключа

Генерация производится согласно блок-схеме алгоритма :

1. Сначала необходимо инициализировать значения регистров ${\displaystyle R3-R6}$ ключом ${\displaystyle K}$ (возможно, другим):

   ${\displaystyle R3[0]=K[0]}$

   ${\displaystyle R4[0]=K[1]}$

   ${\displaystyle R5[0]=K[2]}$

   ${\displaystyle R6[0]=K[3]}$

   ${\displaystyle K[0],\ K[1],\ K[2],\ K[3]}$ отвечают за то же разбиение ключа на равные части.

2. Слова в ключевой последовательности вычисляются следующим образом:

   ${\displaystyle R3[i+1]=M(R3_{i},R6_{i})}$

   ${\displaystyle R4[i+1]=M(R4_{i},R3_{i})}$

   ${\displaystyle R5[i+1]=M(R5_{i},R4_{i})}$

   ${\displaystyle R6[i+1]=M(R6_{i},R5_{i})}$

3. Очередное слово ключевой последовательности определяется значением крайнего регистра:

   ${\displaystyle K_{i+1}=R6[i+1]}$

Ключ следует менять при наличии большого открытого текста (период изменения ключа составляет примерно 10000 слов — в таком случае замедление работы алгоритма составляет около 2-3 %) .

Шифрование и расшифровывание

Оба метода представляют собой гаммирование открытого текста (или шифротекста) с ключевой последовательностью. Шифрование и расшифровывание осуществляются по формуле :

${\displaystyle z_{i}=p_{i}\oplus K_{i}}$ , где ${\displaystyle p_{i}}$ — слово открытого текста или шифротекста в зависимости от того, осуществляется ли шифрование или расшифровывание.

Способы использования

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

1. Дополнение зашифрованных данных двумя словами на обоих концах и последующее заполнение всех бит этих слов одинаковыми случайными значениями. Таким образом, декодер сможет распознавать, когда необходимо использовать следующий ключ в ключевой последовательности для успешной расшифровки сообщения;
2. Изменение стартового ключа для каждого нового блока данных;
3. Шифрование последних четырёх слов открытого текста, дальнейшее гаммирование с помощью стартового ключа всей последовательности и осуществление того же самого в обратном порядке с помощью другого стартового ключа. Этот метод также может подразумевать использование какой-либо стандартной хеш-функции на секретном ключе, имеющей тот же стартовый ключ и таблицу замены для генерации хеша длиной в 128 бит. Этот хеш смешивается с первыми четырьмя словами открытого текста, собственно, в дальнейшем шифрование происходит тем же образом, как и ранее. Так, каждое новое сообщение образует новый результат на выходе алгоритма. Также в случае использования хеш-функции скорость выполнения повышается примерно в 5 раз в сравнении с обычным методом. Метод хорош тем, что хорошо подходит для коротких сообщений, где многократное вычисление таблицы замены заметно снижает эффективность применения. Так что использование одной и той же таблицы замены является оправданным шагом.

Пример работы

Пример работы данного алгоритма шифрования представлен следующим образом :

№	Символ открытого текста	Код ASCII	Процесс гаммирования	Результат ASCII	Выходной символ
1	R	52	52 XOR C2	90	•
2	O	4F	4F XOR 5D	12	_ ( упр. символ )
3	B	42	42 XOR 03	41	A
4	B	42	42 XOR 30	72	r
5	I	49	49 XOR C2	8B	‹
6	SPACE	20	20 XOR 5D	7D	}
7	R	52	52 XOR 03	51	Q
8	A	41	41 XOR 30	71	q
9	H	48	48 XOR C2	8A	Š
10	I	49	49 XOR 5D	14	_ (упр. символ)
11	M	4D	4D XOR 03	4E	N

Итак, зашифрованной последовательностью слов является «•_Ar‹}QqŠ_N».

Криптоанализ

Алгоритм поточного шифрования поддается дешифрованию путём атак по подобранному открытому тексту и подобранному шифротексту . В случае первого варианта атаки производится попытка восстановить таблицу замены, перебирая варианты открытого текста на входе, второй представляет собой подбор шифротекста для точного определения тех же неизвестных значений ${\displaystyle S}$ -блока. Известно, что вычислительная сложность атаки по подобранному открытому тексту составляет примерно ${\displaystyle 10^{14.4}}$ или ${\displaystyle 10^{19.2}}$ в зависимости от выбранной модификации атаки (в первом случае используется больше вариантов открытого текста). Вычислительная сложность атаки путем полного перебора составляет примерно ${\displaystyle 3*10^{2504}}$ , то есть относительная эффективность атаки по подобранному открытому тексту является очевидной . Ещё одно преимущество атаки, предложенной в рассматриваемой статье , заключается в том, что она не зависит от смены ключа . Тем не менее, алгоритмы, с помощью которых производится криптоанализ , становятся невыполнимы, если увеличить длину слова ( ${\displaystyle 4n}$ бит, где ${\displaystyle n>8}$ ). Таким образом, они могут быть значительно улучшены в перспективе .

Также, продолжительное изменение данных в каком-либо одном месте алгоритма шифрования в процессе работы может скомпрометировать таблицу замены. В случае, если ${\displaystyle S}$ -блок уже известен, то требуется всего 5 пар слов открытого-зашифрованного текста для того, чтобы точно определить значения регистров ${\displaystyle R3-R6}$ .

Примечания

Литература

Книги

• Schneier, B. Applied Cryptography: Protocols, Algorthms, and Source Code in C. — 2nd edition. — John Wiley & Sons, Inc., 1996. — 784 с. — ISBN 0471128457 .
• А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н. Шамкин. Криптографическая защита информации : учебное пособие. — Тамбов: Изд-во Тамб. гос. техн. ун-та, 2006. — 140 с. — ISBN 5-8265-0503-6 .

Статьи

• Wheeler, D. (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 1993-12-09. — P. 127—134 . — ISBN 3540581081 . — doi : .
• Craig S. K. Clapp. (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 1997-01-20. — P. 273—287 . — doi : .
• Legito, Robbi Rahim . (англ.) . www.ijrter.com (2017). Дата обращения: 8 февраля 2017.
• Marina Pudovkina. . — 2001-01-01. — № 065 .
• (англ.) . ResearchGate. Дата обращения: 18 февраля 2017.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.