Я уже писал о том, что меня беспокоит возможность подбора пароля RC4 методом «грубой силы» в моей системе шифросвязи Extra Systems Cypher Net. И внедренная мною туда с целью защиты от подобной опасности хаотическая перетасовка алфавита поначалу показалась мне панацеей. Однако более пристальный взгляд на эту проблему показал, что есть настоятельная необходимость предпринять еще ряд дополнительных мер.
Дело в том, что в настоящее время стандартом кодировки символов является UTF8. В случае чисто английского языка — это прекрасное решение. Каждый печатный знак продолжает кодироваться одним байтом (как и во времена MS-DOS), и простая замена алфавита (описанная в предыдущей публикации), в принципе, достаточна для того, чтобы заблокировать перебор паролей RC4 (хотя и оставляет небольшую, на самом деле мифическую, лазейку в виде анализа частоты употребления символов; кстати говоря, описанный здесь метод устраняет и ее). Но для кириллицы ситуация иная: каждая буква кодируется двумя байтами, и тут начинается для нас (криптографов) самое интересное (и не очень приятное).
Возьмем, например, слово «проверка». В UTF8 оно кодируется такой последовательностью байт:
D0 BF D1 80 D0 BE D0 B2 D0 B5 D1 80 D0 BA D0 B0 п р о в е р к а
Как вы видите, байт «D0» регулярно повторяется. Как вы знаете из предыдущего материала, метод перетасовки алфавита был мною внедрен в Extra Systems Cypher Net исключительно с той целью, чтобы попытки подбора пароля RC4 не могли опираться на получение осмысленного текста. И после применения процедуры
void shuffle_buffer(unsigned char *buffer_ptr, int buffer_len, unsigned char *shuffle_data)
{
short counter;
for(counter = 0; counter < buffer_len; counter++) buffer_ptr[counter] = shuffle_data[buffer_ptr[counter]];
}
к вышеуказанной последовательности байт, которая в UTF8 кодирует слово «проверка» мы получим такую последовательность:
old state: D0 BF D1 80 D0 BE D0 B2 D0 B5 D1 80 D0 BA D0 B0 new state: 95 BB 54 6B 95 59 95 80 95 C8 54 6B 95 AD 95 4B
Легко видеть, что при любой интерпретации этой «кодировки» хакер уже не сможет увидеть здесь осмысленный текст (ввиду полной хаотичности замен). Однако хорошо видно, что на местах, где раньше было «D0», теперь стоит «95» (естественно, это относится к использованной в данном примере таблице замены алфавита; в общем случае, это будет какой-то иной код, но точно также — он будет везде одинаковый).
Во всех примерах используется таблица 00: 53 7E 7F 9B 56 D9 04 D1 76 B7 8F 38 A9 CD AF 62 10: 75 1A FF EF 32 FA 5C BD 5B 01 5A 37 D7 4D 4A A0 20: 33 C0 15 34 B4 E3 A3 90 2D 0D 10 4F 5E 4C 52 1F 30: ED C2 B1 5F 8B 12 16 D3 98 65 9F EC C7 C1 84 23 40: E2 CF 41 FB 66 CB CC 60 DD FE A7 AB 28 13 FC 8E 50: 3C AA B2 A8 03 C4 51 78 48 E6 1C 14 EE F0 EA 2E 60: 88 55 7A A4 0B 97 43 DA 11 4E 96 3A E8 CE 61 6F 70: 87 B5 39 35 7C 29 BF B6 0A 30 26 D0 F3 F2 0E 8A 80: 6B 58 22 6C FD 6A E4 7B E1 3B 9A C3 19 45 3E 0F 90: DF BA 31 6D DE E9 F7 3F 79 5D 02 8C F6 63 24 B3 A0: C9 21 49 D5 93 AC D2 44 B8 BE 72 71 74 46 3D EB B0: 4B A1 80 05 20 C8 67 85 92 82 AD 47 F9 06 59 BB C0: BC AE DC F1 B0 77 17 40 81 6E 1E 83 F8 E5 70 A5 D0: 95 54 C6 DB 0C B9 69 27 7D D4 68 94 86 2C D8 08 E0: 73 2B A2 9E 57 F4 2A 99 E0 91 9C 50 64 89 8D 1B F0: A6 18 42 9D D6 07 36 00 F5 E7 09 25 CA 2F 1D C5
То есть, мы все же при этом оставили хакеру лазейку: он теперь, конечно, лишен возможности искать осмысленный текст, но у него осталась возможность (если субъект сеанса шифросвязи использует какой-либо язык, отличный от чисто английского) искать в перехваченном трафике некие регулярные повторения. Конечно, это намного сложнее, но принципиальная возможность (пусть даже и совершенно призрачная) все же остается.
Нельзя ли как-то перекрыть и этот канал для попыток взлома, подумал я? А что если нам циклически сдвинуть биты?
void shuffle_rotate_l(unsigned char *buffer_ptr, int buffer_len)
{
int i;
unsigned char x;
if (!buffer_len) return;
x = buffer_ptr[0];
for(i = 0; i < (buffer_len - 1); i++) buffer_ptr[i] = (buffer_ptr[i] << 4) | (buffer_ptr[i + 1] >> 4);
buffer_ptr[buffer_len - 1] = (buffer_ptr[buffer_len - 1] << 4) | (x >> 4);
}
Ну и, конечно, для надежности, тут же еще раз сменить алфавит:
initial state: D0 BF D1 80 D0 BE D0 B2 D0 B5 D1 80 D0 BA D0 B0 shuffle_buffer: 95 BB 54 6B 95 59 95 80 95 C8 54 6B 95 AD 95 4B shuffle_rotate_l: 5B B5 46 B9 55 99 58 09 5C 85 46 B9 5A D9 54 B9 shuffle_buffer: 14 C8 CC 82 C4 5D 48 B7 EE 6A CC 82 1C D4 03 82
Очевидно, что проблема повторяемости кода «D0» благодаря этой модификации алгоритма блестяще разрешилась. Теперь на этих местах везде стоят различные коды. Казалось бы, нам уже пора пить шампанское? Но — нет. Не будем спешить и посмотрим внимательнее на то, что у нас получилось.
На месте русской буквы «р» (которая в слове «проверка» дважды повторяется), то есть UTF8 кода «D1 80», мы теперь, несмотря на все наши остроумные изощрения и титанические усилия, видим одну и ту же последовательность «CC 82». То есть, повторение букв будет приводить к повторениям и в нашей новой кодировке? Беда. А нельзя ли еще что-нибудь придумать? Можно! А давайте-ка, для разнообразия, попробуем на этот раз уже не сдвиг, а обмен битами:
void shuffle_twist(unsigned char *buffer_ptr, int buffer_len)
{
if (buffer_len < 2) return;
int i;
unsigned char x, y;
for(i = 1; i < buffer_len; i++) { x = buffer_ptr[i - 1]; y = buffer_ptr[i]; buffer_ptr[i - 1] = (x & 0xF0) | (y >> 4);
buffer_ptr[i] = (y & 0xF) | (x << 4);
}
}
Смотрим, что получилось (естественно, и алфавит заодно меняем — это дело святое, без этого никак):
initial state: D0 BF D1 80 D0 BE D0 B2 D0 B5 D1 80 D0 BA D0 B0 shuffle_buffer: 95 BB 54 6B 95 59 95 80 95 C8 54 6B 95 AD 95 4B shuffle_rotate_l: 5B B5 46 B9 55 99 58 09 5C 85 46 B9 5A D9 54 B9 shuffle_buffer: 14 C8 CC 82 C4 5D 48 B7 EE 6A CC 82 1C D4 03 82 shuffle_twist: 1C 4C 88 CC 25 44 DB 8E 76 EC A8 C1 2D C0 48 32 shuffle_buffer: D7 28 E1 F8 E3 66 94 3E BF 64 B8 AE 4C BC DD B1
Ну, что вам сказать? Вот это и есть то, что я называю полной и окончательной победой. Никаких повторений, на выходе мы получили последовательность байт, которая выглядит как набор совершенно случайных чисел. Таким образом, этот мой простой метод предварительного шифрования (изложенный в данной публикации) настолько запутывает ситуацию, что хакеру нет смысла даже начинать взлом основного метода шифрования (в нашем случае — RC4).
Кстати, об энтропии. Вот вам та же таблица, но вместо последовательности байт — значение энтропии (по Шеннону). Надо при этом учесть, что 4 бита энтропии на байт — теоретический максимум для последовательности из 16 байт.
initial state: 2.78 bits per byte shuffle_buffer: 2.78 bits per byte shuffle_rotate_l: 3.58 bits per byte shuffle_buffer: 3.58 bits per byte shuffle_twist: 4.00 bits per byte shuffle_buffer: 4.00 bits per byte
Легко видеть, что процедура shuffle_buffer никогда не меняет энтропию, а процедуры shuffle_rotate_l и shuffle_twist — последовательно ее увеличивают, доводя в итоге до теоретического максимума.
Подчеркиваю: данный метод запутывания противника не претендует на самостоятельность в мире промышленной криптографии, он так и называется — «предварительный». В кодах нашей программы шифросвязи он используется именно в таком качестве:
shuffle_encrypt_buffer(str_buf, buf_size); encrypt_buffer(str_buf, buf_size);
Где encrypt_buffer — основной метод шифрования (в нашем случае, RC4), а под shuffle_encrypt_buffer (который вызывается перед основной процедурой) как раз и понимается весь комплекс описанных выше предварительных манипуляций:
void shuffle_encrypt_buffer(unsigned char *buffer_ptr, int buffer_len)
{
shuffle_buffer(buffer_ptr, buffer_len, shuffle_encrypt_data);
shuffle_rotate_l(buffer_ptr, buffer_len);
shuffle_buffer(buffer_ptr, buffer_len, shuffle_encrypt_data);
shuffle_twist(buffer_ptr, buffer_len);
shuffle_buffer(buffer_ptr, buffer_len, shuffle_encrypt_data);
}
Единственная задача этой криптографической технологии заключается в том, чтобы, перебирая пароли основного метода шифрования по методу «грубой силы», злоумышленник даже не заметил тот момент, когда ему таки действительно удастся найти правильный пароль.