Линейный криптоанализ

     Таблица 2.2.1 – Пятый S-блок DES.

     В ходе анализа мы прослеживаем все  возможные комбинации двоичных векторов i и j. Каждую пару векторов мы используем в качестве маски, которую накладываем на все возможные пары вход – выход блока замены. Эти маски  указывают нам на биты входа и выхода соответственно, которые необходимо  сложить  по  модулю 2, а  затем  сравнить  полученные  результаты. Результат анализа приведен в приложении в таблице (2). В этой таблице значение Q5(i,j), имеющее наибольшее отклонение от ½, помечено *. Следовательно, Q*5(I*,j*) = 12, где j = (1,1,1,1), а i = (0,1,0,0,0,0). Это говорит о том, что из всех возможных входных значений (от 0 до 63) и соответствующих им выходных  значений, 12 раз  встречается  совпадение  второго  входного  бита  и суммы по модулю 2 всех четырех выходных битов. Из таблицы (2), приведенной в приложении, следует, что данными 12 парами являются следующие:

     Получается, что (Y,j) = (X,i)  ⊕  (K,i), где i=16, а j = 15, для 12 пар входвыход S5 блока из имеющихся 64. Говоря другими словами, в большинстве случаев они будут неравны между собой, а следовательно их сумма по модулю  два  в  большинстве  случаев  будет  равна 1. То  есть  по  уравнению (2.1.2) получается, что в большинстве случаев Q(i,j) = 1.

     Прибавив  по модулю два (X,i) к правой и левой  части уравнения (Y,j)=(X,i) ⊕ (K,i),  получим эффективный линейный   статистический  аналог S5 блока:

X2  ⊕  Y1  ⊕  Y2 ⊕  Y3  ⊕  Y4 = K2,                        (2.2.6)

и это уравнение  выполняется с вероятностью р = 3/16.

     Уравнения для эффективных линейных статистических аналогов всех S блоков приведены в таблице 2.2.2. Здесь X = (x1, …, x6), Y = (y1, …, y4), K=(k1,…, k6) – входные, выходные и ключевые векторы соответственно.

Таблица 2.2.2 - Уравнения для эффективных линейных статистических аналогов всех S блоков DES.

     Так как в рассматриваемом нами S5 - блоке в уравнении участвует второй бит, то легко можно посчитать, что этот бит на самом деле будет 26 битом  всего  входного  сообщения  Х.  Однако,  зная,  что  при  входе   в F блок, входной вектор претерпевает изменения с помощью перестановки с расширением,  то,  воспользовавшись  приведенной  ниже  таблицей,  легко  можно определить, что  на 26 позиции будет находиться на самом деле 17 входной бит таблицы 2.2.3.

Таблица 2.2.3 – Промежуточные вычисления.

     Точно так же выходной вектор, прежде чем выйти из F-блока претерпевает перестановку с помощью F - блока. Поэтому выходящие из S5 блока 17, 18, 19 и 20 биты соответственно окажутся на  8, 14, 25 и 3 позиции выходного вектора таблицы (2.2.4). 

Таблица 2.2.4 – Промежуточные вычисления.

     Тогда полученное нами эффективное линейное статистическое уравнение примет вид:

X17  ⊕  Y3 ⊕  Y8 ⊕  Y14  ⊕  Y25 = K26,                        (2.2.7)

при  ∆ = 5/8. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.3 Нахождение статических  аналогов для трех  циклов алгоритма  DES 
 

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

   Прежде  чем пояснить вышесказанное на  примере, рассмотрим несколько базовых  определений:

Лемма 1: если Q(1),…, Q(n) – независимые бинарные случайные величины, то

∆ (Q(1)⊕ … ⊕ Q(n)) = П ∆ (Q(i)),                              (2.3.1)

где i=1,…, n.

Доказательство: докажем эту лемму для двух независимых величин. Так как Q(1)  и Q(2) независимы  и  при  этом  Р(Q(1)=1)=р1,  Р(Q(2)=1)=р2,  Р(Q(1)=0)=1– р1  и Р(Q(2)=0)=1 – р2. то Р(Q(1)⊕ Q(2) = 1) =  Р(Q(1)=1)Р(Q(2)=0) + Р(Q(1)=0)Р(Q(2)=1) = р2(1 – р1) + р1(1 – р2) = р2 – р1р2 + р1 – р1р2 = р2 + р1  2р1р2. ∆ (Q(1)⊕ Q(2)) = 1 – 2р(Q(1)⊕ Q(2) =1) = 1 – 2(р2 + р1 – 2р1р2) = 1 – 2р2 – 2р1 + 4р1р2 = (1 – 2р1)( 1 – 2р2) =  ∆ (Q(1)) ∆ (Q(2)).

     А теперь расcмотрим n независимых величин. Пусть Q(1)⊕ Q(2)  ⊕ … ⊕ Q(n-1) = Q’ и p’ = p(Q’=1), pn = p(Q(n)=1).

     Тогда P(Q’ ⊕ Q(n) = 1) = p(Q’=1)p(Q(n) = 0) + p(Q’=0)p(Q(n) = 1) = p’(1-pn) + (1-p’)pn = p’ + pn – 2p’pn. ∆ (Q(1)⊕ … ⊕ Q(n)) =  ∆ (Q’ ⊕ Q(n)) = 1 – 2p(Q’ ⊕ Q(n) = 1)  = 1 – 2(p’ + pn – 2p’pn) = 1 – 2pn – 2p’ +4p’pn = (1 – 2p’)(1 – 2pn) =  ∆ (Q’)  ∆(Q(n)) = П ∆ (Q(i)).

Рисунок 2.3.1 – Схема трех раундов DES.

     Замечание 1: массе называл тройной суммой S(i)  для i-го раунда случайную величину вида

       Q(i) = fi (X(i))  ⊕  gi (Y(i))  ⊕  hi (K(i)),                   (2.3.2)

     где fi, gi, hi – равновероятностные булевы функции.

     В определении Матсуи fi, gi, hi – линейные функции.

     Определение 2:  последовательные тройные суммы S(1+i) и S(i)  называются вязанными, если fi+1  = gi.

     Из  определения  следует,  что Q(i)  ⊕   S(1+i) = fi (X(i))  ⊕  gi (Y(i))  ⊕  hi(K(i))  ⊕  fi+1 (X(i+1))  ⊕  gi+1 (Y(i+1))  ⊕  bi+1 (K(i+1)),где Y(i) = X(i+1). 

     Определение 3: если Q(1),…, Q(n) – связанные тройные суммы, то тогда:

(2.3.3) 

и Q1….n называется n-раундовой тройной суммой.

     В случае линейных функций формула (2.3.3) дает иное соотношение:

              

(2.3.4) 

которое выполняется с вероятностью, определяемой  ∆ (Q(1)⊕ … ⊕ Q(n)) и леммой 1.

     Определение 4: эффективным линейным статистическим аналогом называется  линейный  статистический  аналог (2.3.4)  из  заданного множества с наибольшим  ∆ .

     Поясним все вышесказанное на примере. Для  этого рассмотрим схему 

3-раундового DES, изображенную на рисунке (2.3.1) .

     Эффективными  линейными статистическими аналогами 1-й и 3-й итераций являются уравнения:

              (2.3.5)

каждое  из которых выполняется с вероятностью 3/16.

     Учитывая  Х(1) = PR(3) = CL, Y( = PL  ⊕  X(2), Y(3) = CR  ⊕  X(2),

после сложения этих уравнений получим:

                                          (2.3.6)

     По  лемме 1  ∆  = (5/8)*(5/8) = 25/64 и это уравнение выполняется с вероятностью р = (1 –  ∆ )/2 = 39/128.

     Найти биты ключа К(1)  ⊕  К(3) можно, решая уравнение (2.3.6) с использованием алгоритма, приведенного ниже.

     Алгоритм: пусть N - число всех открытых текстов и T - число открытых текстов, для которых левая часть (2.3.6) равна 0.

Если Т> N/2, то:

     Успех алгоритма возрастает с ростом N и  ∆  = |1 – 2p|. Вероятность успеха определяется следующей леммой.

     Лемма 2: пусть N - число открытых текстов и р - вероятность выполнения линейного уравнения (2.1.2). Предположим, что ∆ = |1 — 2р| —> 0. Тогда вероятность успеха алгоритма имеет вид:

                                          (2.3.6)

где

                                            (2.3.7)

     Числовые вычисления (2.3.7) сведены в таблице (2.3.1)

Таблица 2.3.1 – Числовые вычисления

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

2.4 Пример применения линейного криптоанализа к раскрытию ключа. 
 

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

   Схема данного алгоритма представлена на рисунке (2.4.1). Входной блок представляет собой последовательность из 16 бит, которые разделяются на две части, правая из которых проходит через блок шифрования f, после чего складывается по модулю 2 с левой частью. Выходное шифрованное сообщение состоит из двух 8-битовых частей, правая часть которого представляет собой правую часть входного сообщения, а левая - результат сложения по модулю два.

     Рассмотрим  подробнее f блок, изображенный а рисунке (2.4.2). Входное 8-битовое сообщение проходит через блок перестановки с расширением так, что на выходе мы имеем 12 бит. Данные таблицы перестановки с расширением приведены в таблице (2.4.1). Читать таблицу следует справа налево. То есть третий бит становится в первую позицию и т. д. таким образом что самый старший бит имеет номер I, а самый младший - номер 12. После этого 12-битовый ключ и преобразованное входное сообщение складываются по модулю 2. Результат сложения разбивается на три группы по четыре бита, каждая из которых проходит соответственно блок I, блок 2 и блок З. При этом из первых двух блоков выходит по три бита, а из третьего блока - два.

     Замена  в первых двух блоках производится по приведенным табл. 2.4.2 и 2.4.3 по следующему принципу. 
 

Рисунок 2.4.1 – Общая схема алгоритма  шифрования.

     Пусть в блок входит четыре бита: al, а2, аЗ, а4. При этом первый бит определяет номер строки (если а I = 0. то это соответствует первому- столбцу, а если а I = I - второму), а остальные три - номер столбца (ООО = первому столбцу, 111= восьмому столбцу).

     Несколько иначе дело обстоит с третьим  блоком. Из него в отличие от первых двух выходит не три бита, а два. Замена осуществляется согласно таблице 2.4.4. При этом, если al, а2, аЗ, а4 - входные биты блока 3, то биты al и а4 определяют номер сроки, а биты а2 и аЗ - номер столбца (аналогично S- блокам алгоритма DES). 

     Рисунок 2.4.2 - Алгоритм шифрования.