Войти  |  Регистрация
Авторизация

WAKE



WAKE (англ. Word Auto Key Encryption, шифрование слов на автоматическом ключе) — алгоритм поточного шифрования на автоматическом ключе, разработанный Дэвидом Уилером в 1993 году. Изначально проектировался как среднескоростная система шифрования (скорость в поточных шифрах измеряется в циклах на байт шифруемого открытого текста) блоков (минимального количества информации, которое может быть обработано алгоритмом; в данном случае блок составляет 32 бита), обладающая высокой безопасностью. По мнению автора, является простым алгоритмом быстрого шифрования, подходящим для обработки больших массивов данных, а также коротких сообщений, где изменяется только секретный ключ. Подходит для использования хешей на секретных ключах, используемых при верификации. Одним из примеров возможного практического использования данного алгоритма является шифрование потока текстовых данных в SMS. Из-за большого размера блоков не может быть использован в коммуникациях в режиме реального времени.

Свойства

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

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

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

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

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

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

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

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

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

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

  • Инициализировать вспомогательную таблицу s {displaystyle s} , состоящую из 8 слов, имеющих между собой перестановку первых трех бит: s [ 0 ] : 726 a 8 f 3 b {displaystyle s[0]:726a8f3b} s [ 1 ] : e 69 a 3 b 5 c {displaystyle s[1]:e69a3b5c} s [ 2 ] : d 3 c 71 f e 5 {displaystyle s[2]:d3c71fe5} s [ 3 ] : a b 3 c 73 d 2 {displaystyle s[3]:ab3c73d2} s [ 4 ] : 4 d 3 a 8 e b 3 {displaystyle s[4]:4d3a8eb3} s [ 5 ] : 0396 d 6 e 8 {displaystyle s[5]:0396d6e8} s [ 6 ] : 3 d 4 c 2 f 7 a {displaystyle s[6]:3d4c2f7a} s [ 7 ] : 9 e e 27 c f 3 {displaystyle s[7]:9ee27cf3}
  • Копировать ключ K {displaystyle K} в первые 4 слова S {displaystyle S} таким образом, что: S [ 0 ] . . . S [ 3 ] : {displaystyle S[0]...S[3]:} S [ 0 ] = K [ 0 ] ;   S [ 1 ] = K [ 1 ] {displaystyle S[0]=K[0]; S[1]=K[1]} S [ 2 ] = K [ 2 ] ;   S [ 3 ] = K [ 3 ] {displaystyle S[2]=K[2]; S[3]=K[3]} , где K [ 0 ] ,   K [ 1 ] ,   K [ 2 ] ,   K [ 3 ] {displaystyle K[0], K[1], K[2], K[3]} — есть результат разбиения ключа на четыре равные части.
  • Остальные слова образовать в цикле: f o r   n = 4 t o 255 : {displaystyle for n=4quad toquad 255:} x = S [ n − 1 ] + S [ n − 4 ] {displaystyle x=S[n-1]+S[n-4]} S [ n ] = x >> 3 ⊕ s [ x ∧ 7 ] {displaystyle S[n]=x>>3oplus s[xwedge 7]}
  • Произвести суммирование: f o r   n = 0 t o 22 : {displaystyle for n=0quad toquad 22:} S [ n ]   + = S [ n + 89 ] {displaystyle S[n] +!=S[n+89]} . Таким образом, даже первые несколько слов будут зависеть от всех бит K {displaystyle K} .
  • Определить вспомогательные переменные: X = S [ 33 ] {displaystyle X=S[33]} Z = S [ 59 ] ∨ 0 x 01000001 {displaystyle Z=S[59]lor 0{ ext{x}}01000001} Z = Z ∧ 0 x F F 7 F F F F F {displaystyle Z=Zland 0{ ext{x}}FF7FFFFF} X = ( X ∧ 0 x F F 7 F F F F F h ) + Z {displaystyle X=(Xland 0{ ext{x}}FF7FFFFFh)+Z}
  • Осуществить перестановку в первом байте слов таблицы: f o r   n = 0 t o 255 : {displaystyle for n=0quad toquad 255:} X = ( X ∧ 0 x F F 7 F F F F F ) + Z {displaystyle X=(Xland 0{ ext{x}}FF7FFFFF)+Z} S [ n ] = S [ n ] ∧ 0 x 00 F F F F F F ⊕ X {displaystyle S[n]=S[n]land 0{ ext{x}}00FFFFFFoplus X}
  • Инициализировать следующие переменные: S [ 256 ] = S [ 0 ] {displaystyle S[256]=S[0]} X = X ∧ 255 {displaystyle X=Xland 255}
  • Перемешать между собой слова в S {displaystyle S} : f o r   n = 0 t o 255 : {displaystyle for n=0quad toquad 255:} T e m p = ( S [ n ⊕ X ] ⊕ X ) ∧ 255 {displaystyle Temp=(S[noplus X]oplus X)land 255} S [ n ] = S [ T e m p ] {displaystyle S[n]=S[Temp]} S [ X ] = S [ n + 1 ] {displaystyle S[X]=S[n+1]}
  • Метод построения может быть легко изменён, и вышеприведенный алгоритм является лишь примером. Главное, чтобы результат алгоритма обладал всеми свойствами, представленными из соображений криптографической стойкости S {displaystyle S} -блока. Так, например, можно заполнить таблицу слов случайными числами, но в таком случае происходит утечка информации о повторяющихся и нулевых записях таблицы, не превышающая 1.5 бита на каждую запись. Тем не менее, создатель алгоритма утверждает, что процесс перестановки на старших байтах слов существенно помогает снизить утечку. А перестановка на всех четырёх байтах ещё больше нивелирует вероятность прочтения таблицы. Таким образом, алгоритм заполнения, приведенный выше, является компромиссом между безопасностью и скоростью, так как в нём осуществляется перестановка именно старших байт слов S {displaystyle S} -блока.

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

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

  • Сначала необходимо инициализировать значения регистров R 3 − R 6 {displaystyle R3-R6} ключом K {displaystyle K} (возможно, другим): R 3 [ 0 ] = K [ 0 ] {displaystyle R3[0]=K[0]} R 4 [ 0 ] = K [ 1 ] {displaystyle R4[0]=K[1]} R 5 [ 0 ] = K [ 2 ] {displaystyle R5[0]=K[2]} R 6 [ 0 ] = K [ 3 ] {displaystyle R6[0]=K[3]} K [ 0 ] ,   K [ 1 ] ,   K [ 2 ] ,   K [ 3 ] {displaystyle K[0], K[1], K[2], K[3]} отвечают за то же разбиение ключа на равные части.
  • Слова в ключевой последовательности вычисляются следующим образом: R 3 [ i + 1 ] = M ( R 3 i , R 6 i ) {displaystyle R3[i+1]=M(R3_{i},R6_{i})} R 4 [ i + 1 ] = M ( R 4 i , R 3 i ) {displaystyle R4[i+1]=M(R4_{i},R3_{i})} R 5 [ i + 1 ] = M ( R 5 i , R 4 i ) {displaystyle R5[i+1]=M(R5_{i},R4_{i})} R 6 [ i + 1 ] = M ( R 6 i , R 5 i ) {displaystyle R6[i+1]=M(R6_{i},R5_{i})}
  • Очередное слово ключевой последовательности определяется значением крайнего регистра: K i + 1 = R 6 [ i + 1 ] {displaystyle K_{i+1}=R6[i+1]}
  • Ключ следует менять при наличии большого открытого текста (период изменения ключа составляет примерно 10000 слов — в таком случае замедление работы алгоритма составляет около 2-3 %).

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

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

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

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

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

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

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

  • Инициализация стартового ключа K {displaystyle K} : K = {displaystyle K=} «legitosinarhusni». В шестнадцатеричной системе счисления он будет выглядеть так: K = 6 C 656769746 F 73696 E 61726875736 E 69 {displaystyle K=6C656769746F73696E61726875736E69}
  • Необходимо разбить ключ на четыре равные части и инициализировать стартовые значения регистров: R 3 [ 0 ] = 6 C 656769 {displaystyle R3[0]=6C656769} R 4 [ 0 ] = 746 F 7369 {displaystyle R4[0]=746F7369} R 5 [ 0 ] = 6 E 617268 {displaystyle R5[0]=6E617268} R 6 [ 0 ] = 75736 E 69 {displaystyle R6[0]=75736E69}
  • Вычисление следующего слова ключевой последовательности ( S {displaystyle S} -блок уже сгенерирован на основе имеющегося стартового ключа): M ( R 3 [ 0 ] , R 6 [ 0 ] ) = M ( 6 C 656769 , 75736 E 69 ) = ( 6 C 656769 + 75736 E 69 ) >> 8 ⊕ S ( 6 C 656769 + 75736 E 69 ) ∧ 255 10 = E 1 D 8 D 5 D 2 >> 8 ⊕ S 210 = 00 E 1 D 8 D 5 ⊕ 1 C 5 A 4 A 56 = 1 C B B 9283 {displaystyle M(R3[0],R6[0])=M(6C656769,75736E69)=(6C656769+75736E69)>>8oplus S_{(6C656769+75736E69)land 255_{10}}=E1D8D5D2>>8oplus S_{210}=00E1D8D5oplus 1C5A4A56=1CBB9283} R 3 [ 1 ] = 1 C B B 9283 {displaystyle R3[1]=1CBB9283} M ( R 4 [ 0 ] , R 3 [ 1 ] ) = M ( 746 F 7369 , 1 C B B 9283 ) = ( 746 F 7369 + 1 C B B 9283 ) >> 8 ⊕ S ( 746 F 7369 + 1 C B B 9283 ) ∧ 255 10 = 912 B 05 E R 5 >> 8 ⊕ S 236 = 00912 B 05 ⊕ 26853 B 5 R 4 = 2614105 E {displaystyle M(R4[0],R3[1])=M(746F7369,1CBB9283)=(746F7369+1CBB9283)>>8oplus S_{(746F7369+1CBB9283)land 255_{10}}=912B05ER5>>8oplus S_{236}=00912B05oplus 26853B5R4=2614105E} R 4 [ 1 ] = 2614105 E {displaystyle R4[1]=2614105E} M ( R 5 [ 0 ] , R 4 [ 1 ] ) = M ( 6 E 617268 , 2614105 E ) = ( 6 E 617268 + 2614105 E ) >> 8 ⊕ S ( 6 E 617268 + 2614105 E ) ∧ 255 10 = 947582 C 6 >> 8 ⊕ S 198 = 00947582 ⊕ 244 C 066 R 5 = 24 D 873 E E {displaystyle M(R5[0],R4[1])=M(6E617268,2614105E)=(6E617268+2614105E)>>8oplus S_{(6E617268+2614105E)land 255_{10}}=947582C6>>8oplus S_{198}=00947582oplus 244C066R5=24D873EE} R 5 [ 1 ] = 24 D 873 E E {displaystyle R5[1]=24D873EE} M ( R 6 [ 0 ] , R 5 [ 1 ] ) = M ( 75736 E 69 , 24 D 873 E E ) = ( 75736 E 69 + 24 D 873 E E ) >> 8 ⊕ S ( 75736 E 69 + 24 D 873 E E ) ∧ 255 10 = 9 A 4 B E 257 >> 8 ⊕ S 87 = 009 A 4 B E 2 ⊕ C 2 C 748 D 2 = C 25 D 0330 {displaystyle M(R6[0],R5[1])=M(75736E69,24D873EE)=(75736E69+24D873EE)>>8oplus S_{(75736E69+24D873EE)land 255_{10}}=9A4BE257>>8oplus S_{87}=009A4BE2oplus C2C748D2=C25D0330} R 6 [ 1 ] = C 25 D 0330 {displaystyle R6[1]=C25D0330} K 1 = C 25 D 0330 {displaystyle K_{1}=C25D0330} — новый ключ.
  • Далее, пусть в роли открытого текста взят «ROBBI RAHIM». В HEX-представлении это будет p = 524 F 42424920524148494 D {displaystyle p=524F42424920524148494D} . Необходимо произвести гаммирование данной числовой последовательности с ключом:
  • Итак, зашифрованной последовательностью слов является «•_Ar‹}QqŠ_N».

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

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

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


    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent