7.2. Ошибки в кодировании алгоритмов

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

В феврале 2001 года в почтовой рассылке cryptography-digest происходило обсуждение ошибки при реализации алгоритма шифрования Alleged RC4 на языке ADA.

История алгоритма шифрования RC4
Потоковый шифр RC4 был разработан Роном Ривестом в 1987 году. Этот шифр позволяет использовать ключи размером от 8 до 2048 бит (с шагом 8). В RC4 для зашифрования и расшифрования применяются одни и те же действия: генерируется гамма, которая накладывается на шифруемое сообщение путем сложения по модулю 2 (операция XOR).
RC4 применяется в таких продуктах, как Microsoft Office, Lotus Notes, Adobe Acrobat и др.
Алгоритм RC4 является собственностью компании RSA Data Security, Inc. Его описание никогда не было опубликовано и предоставлялось партнерам только после подписания соглашения о неразглашении. Однако в сентябре 1994 года в списке рассылки Cipherpunks (Шифропанки) кто-то анонимно опубликовал алгоритм шифрования, который на всех известных тестовых значениях совпадал с RC4. С тех пор сам алгоритм перестал быть секретом, но название RC4 остается торговой маркой. То есть, чтобы получить право заявлять, что в коммерческом программном продукте используется RC4, необходимо приобрести лицензию на этот алгоритм у RSA Data Security. А без лицензии можно утверждать лишь то, что "используется алгоритм, похожий на RC4 и совпадающий с ним на всем известном множестве тестов". Именно поэтому на языке ADA был реализован Alleged (предполагаемый) RC4.

Одно из достоинств RC4 (кроме обещаний компании RSA Data Security, Inc., что алгоритм устойчив к дифференциальному и линейному методам криптоанализа и, вероятно, не содержит коротких циклов) — его простота (листинг 7.1).

Листинг 7.1. Исходный текст алгоритма RC4 на языке г:

typedef unsigned char RC4_CELL; typedef struct { // структура для хранения текущего состояния ключа RC4_CELL state(256); // таблица перестановок RC4_CELL X, у; } RC4_KEY;


void swap_byte (RC4_CELL *a, RC4_CELL *b) {  // обмен  значений двух ячеек 

  RC4_CELL t = *a; *a = *b; *b = t; 

  }
void RC4_setKey (   //  загрузка ключа (инициализация таблицы перестановок) 

  RC4_KEY *key,      // хранилище ключа 

  int len,           // длина ключа 

  RC4_CELL *data     // данные ключа 
RC4_CELL t, *s = key->State; 

  int i, id;
for (i = 0; i < 256; i + + ) s[i] = i; 

  key->x =  key->y = 0;
for (id = i = 0; i < 256; i + + )  { 

  id = (datat i % len] + s[i] + id) & Oxff ; 

  swap_byte (&s[i],  &s[id]);
void RC4 (               // процедура шифрования 

  RC4_KEY *key,           // хранилище ключа 

  int len,                      // длина шифруемых данных 

  RC4_CELL *data          //  шифруемые данные 

  { 

  RC4_CELL   *s  = key->state,   x = кеу->х,   у = key->y;
for    (;   len > 0;   len--,   data++>    { 

  x =    {x + 1)   &    Oxff; 

  y   =    (s[x]    + y)     & Oxff ; 

  swap_byte    (&s[x], &sty]); 

  *data"=s[(s[x]    +     s [y]} & Oxff] ; 

  }
key->x = x;   key->y = y; }

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

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

А = А хоr В; В = В xor A; A = А хоr В;

Именно этот прием и был использован в реализации RC4 на языке ADA. Однако автор кода не учел одну простую вещь: алгоритм обмена содержимого двух ячеек памяти без использования вспомогательных переменных работает только для разных переменных. Если значения, хранящиеся в А и в, совпадают, алгоритм работает правильно. Но если А и в — одна и та же переменная, ее значение будет обнулено при попытке обмена.

В RC4 индекс одного из переставляемых элементов таблицы последовательно (циклически) возрастает, а индекс другого элемента вычисляется по текущему состоянию ключа. И, разумеется, возникают ситуации, когда значения индексов совпадают. При этом в корректной реализации таблица перестановок просто остается без изменений, а при использовании обмена без вспомогательных переменных один из элементов таблицы будет обнулен.

Очень интересно посмотреть, как такая ошибка скажется на работе алгоритма шифрования в целом.

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

Во-вторых, на коротких сообщениях алгоритм с ошибкой может работать в точности так же, как и правильно реализованный алгоритм. То есть ошибка может остаться незамеченной, если тестировать алгоритм шифрования только на коротких образцах.

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

*data ^= s[(s[x] + s [у]) & Oxff];

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

Поиск по сайту

Новые публикации

Смотрите также