Многие криптографические алгоритмы весьма сложны, и при их реализации легко допустить ошибку. Хотя можно допустить ошибку и при реализации сравнительно простых алгоритмов. В феврале 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 х, у; } RC4_KEY; void swap_byte (RC4_CELL *a, RC4_CELL *b)
{ // обмен значений двух ячеек RC4_CELL t = *а; *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 x = key->y = 0; for (id = i = 0; i state, x = кеу->х, у = кеу->у; for (; len > 0; len--, data++) { x = {x + 1) Sc Oxff; у = (s[x] + y) & Oxff; swap_byte (&s[x], &s ty)); *data л= s[(s[x] + s[y]) & Oxff]; } key->x = x; key->y = y; }
Как видно, и в процедуре загрузки ключа, и в процедуре шифрования при вызове функции swap_byte() происходит обмен местами двух элементов таблицы перестановок. Существует алгоритм обмена содержимого двух ячеек без использования вспомогательных переменных. Для того чтобы поменять местами д и в , необходимо выполнить три операции: А = А хог В; В = В xor A; А = А хог В;
Именно этот прием и был использован в реализации RC4 на языке ADA. Однако автор кода не учел одну простую вещь: алгоритм обмена содержимого двух ячеек памяти без использования вспомогательных переменных работает только для разных переменных. Если значения, хранящиеся в А и в, совпадают, алгоритм работает правильно. Но если А и в — одна и та же переменная, ее значение будет обнулено при попытке обмена. В RC4 индекс одного из перестаатяемых элементов таблицы последовательно (циклически) возрастает, а индекс другого элемента вычисляется по текущему состоянию ключа. И, разумеется, возникают ситуации, когда значения индексов совпадают.
При этом в корректной реализации таблица перестановок просто остается без изменений, а при использовании обмена без вспомогательных переменных один из элементов таблицы будет обнулен. Очень интересно посмотреть, как такая ошибка скажется на работе алгоритма шифрования в целом. Во-первых, этот алгоритм может показаться полностью работоспособным, т. к. и зашифрование, и расшифрование будут идти совершенно одинаково. А значит, данные, зашифрованные этим алгоритмом, могут быть им же успешно расшифрованы. Во-вторых, на коротких сообщениях алгоритм с ошибкой может работать в точности так же, как и правильно реализованный алгоритм. То есть ошибка может остаться незамеченной, если тестировать алгоритм шифрования только на коротких образцах. И, в-третьих, при шифровании значительного объема данных без смены ключа все большее число элементов таблицы перестановок будет становиться нулевыми. А так как преобразование шифруемых данных осуществляется путем наложения выбранного элемента таблицы перестановок при помощи операции XOR: *data Л= s [ ( s [ x ] + s[у]) & Oxff]; то шифртекст во многих местах будет совпадать с открытым текстом. То есть изрядная часть данных окажется вообще незашифрованной.
