Дифференцильная атака

1 Свойства и структура алгоритма

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

Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров). Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу. Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

1.2 Математическое описание алгоритма

Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей [math]Δfirst[/math], после чего определяется наиболее вероятная разница выходных шифртекстов [math]Δlast[/math] на предпоследнем раунде [math]R-1[/math]. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования. Пусть [math]p[/math] - вероятность дифференциальной характеристики [math]Δfirst→Δlast[/math], воздействущей на [math]b[/math] бит результирующего шифртекста. Тогда атака проводится следующим образом:

1. Берется небольшая положительная константа [math]c[/math] (обычно равная 2 или 3). Генерируется [math]c/p[/math] пар текстов с входной разницей [math]Δfirst[/math];
2. Все данные пары текстов пропускаются через [math]R[/math] раундов алгоритма шифрования, после чего получаются соответствующие шифртексты [math]Y_{R}[/math];
3. Для всех возможных значений [math]b[/math] бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов [math]Y_{R}[/math] данные тексты расшифровываются на всех возможных значениях [math]b[/math] бит раундового ключа, в результате чего получаются значения [math]Y_{R-1}[/math];
4. Для каждой пары текстов путем их сложения находится своя разница [math]ΔY_{R-1}[/math]. Далее значение [math]ΔY_{R-1}[/math] сравнивается c [math]Δlast[/math]. Если они совпадают, счетчик для данного [math]b[/math] бит ключа увеличивается на 1.

После такого полного перебора раундовым ключом является то значение [math]b[/math] бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

1.3 Вычислительное ядро алгоритма

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей [math]ΔX[/math], получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов [math]ΔY_{R-1}[/math] на [math]{R-1}[/math] раунде совпадает с искомой разницей [math]ΔU[/math], счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

1.4 Макроструктура алгоритма

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

1.5 Схема реализации последовательного алгоритма

В данном пункте приведены

double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
  for (int j=0; j<R;j++)
  {
  firsttext = cipher(firsttext);
  secondtext = cipher(secondtext);
  }
  for (int k=0; k< pow(2,b);k++)
  {
    firsttext = decipher(firsttext,k)
    secondtext = decipher(secondtext,k)
    if (deltalast == firsttext ^ secondtext)
    {
    result[k]++
    }
  }
}
int max=0
for (int k=0; k< pow(2,b);k++)
  {
    if (result[k] > max) max=result[k]
  }

1.6 Последовательная сложность алгоритма

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью [math]p[/math], на нахождение [math]b[/math] бит раундового ключа [math]R-1[/math] раунда шифрования потребуется около [math](2c/p)(R+2^b)[/math] операций шифрования, где [math]c[/math] - некоторая небольшая константа. Так как основным параметром является вероятность [math]p[/math], от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.

1.7 Информационный граф алгоритма и блок-схема обработки одного текста

Рассмотрим информационный граф для обработки всех пар текстов. Как видно из графа, обработка каждой пары текстов происходит независимо, после чего значения всех счетчиков сохраняются в один список.

Информационный граф

Действия, происходящие для каждой пары текстов в графе, можно подробно рассмотреть с использованием следующей блок-схемы. Как из видно схемы, для каждого текста [math]X[/math] сначала генерируется второй текст при помощи добавления к нему разницы [math]Δfirst[/math], взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение [math]R[/math] раундов для обеих текстов из пары. После получения шифртекстов [math]Y_R[/math] и [math]Y'_R[/math] в результате последнего раунда, для всех возможных [math]b[/math] бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница [math]ΔY_{R-1}[/math] сравнивается с искомой [math]Δlast[/math] в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.

Блок-схема обработки одного текста

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

1.8 Ресурс параллелизма алгоритма

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

Стоить отметить, что существуют другие ресурсы параллелизма, как в алгоритме атаки, так и в алгоритме шифрования, но их параллелизм не является эффективным. Так как в каждой паре существует два текста, каждый текст из пары можно шифровать и расшифровывать параллельно, однако так как число пар в блочном шифре Present может близиться к [math]2^{32}[/math] и для каждой пары необходимо находить разницу текстов данной пары, более эффективным является обработка обеих текстов из пары одним процессом. Помимо этого, некоторые операции в алгоритме шифрования могут выполняться параллельно. Такими операциями являются операция побитового сложения текста с раундовым ключом и операция подстановки бит частей текста по 4 бита. Так как подобная параллельность обычно достигается при аппаратной реализации шифрования (где каждый бит текста течет по своему каналу), то при программной реализации более эффективным является совмещение преобразований в одно, путем хранения результата преобразований в одной большой таблице. Распараллеливание этих операция для каждого текста из всех обрабатываемых текстов принесет огромные накладные расходы на синхронизацию и обмен информацией между процессами.

1.9 Входные и выходные данные алгоритма

Входные данные: алгоритм шифрования, константа [math]c[/math], вероятность характеристики [math]p[/math], число бит раундового ключа [math]b[/math], число раундов шифрования [math]R[/math], входная разница между парами текстов [math]deltafirst[/math], выходная разница между парами текстов [math]deltalast[/math]

Объём входных данных: Объем входных не изменяется, изменяются только сами входные данные.

Выходные данные: Биты раундового ключа последнего раунда.

Объём выходных данных: [math]b[/math].

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

	Число процессов
Число генерируемых пар текстов	1	2	4	8	16	32
[math]10^7[/math]	42,1364	21,1016	11,6119	6,1043	3,06838	1,5346
[math]2*10^7[/math]	84,4536	45,0574	23,3564	12,2063	6,13689	3,0685
[math]4*10^7[/math]	169,6	85,1138	46,0756	24,4103	12,276	6,1380
[math]8*10^7[/math]	339,081	170,628	95,0417	48,8382	24,5472	12,275
[math]16*10^7[/math]	683,5931	345,1143	175,181	97,6816	49,094	24,553

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

Масштабируемость алгоритма

Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

2.7 Существующие реализации алгоритма

На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

3 Литература

M. Heys "A tutorial on linear and differential cryptanalysis" [1].