Допустим, вы живете в каменном веке и изобрели шифр с 8-битным ключом, то есть,
всего имеется 28 = 256 комбинаций. Назвали вы его SAES (Stone Age
Encryption Standard). Шифр работал отлично, но прогресс не стоит на месте: у
людей отросло больше пальцев на руках, они научились быстрее считать, и ваш
8-битный шифр стал не таким надежным, как раньше, потому что подобрать комбинацию из 256
вариантов стало просто. Вы решаете, что нужно сделать 16-битный шифр
(216 = 65536 вариантов ключа). SAES себя хорошо зарекомендовал во
всех остальных качествах, кроме размера ключа. Почему бы не взять его за основу
и просто увеличить размер ключа с 8-ми до 16-ти бит?
Как это сделать? -- думаете вы. Что если взять и зашифровать текст сначала
одним 8-битным ключом, например, "A", а потом полученный зашифрованный текст
зашифровать еще одним (возможно, другим) 8-битным ключом, например "B"?
- ШИФРОВАТЬ("Dear Bob", "A") = "Ynfxr4hf"
- ШИФРОВАТЬ("Ynfxr4hf", "B") = "1m6Bp0nh"
Или вот так можно изобразить: EncryptK2(EncryptK1(текст)).
В итоге получится, что шифр у нас один и тот же, но две операции шифрования с
8-битным ключом расширяют размер ключа до 16-ти бит. Да? Назовем его 2SAES.
Как только вы подумали об этом, начался ураган, гром и молния, яркая вспышка и перед вами
появились
Диффи
с
Хеллманом,
которые изобрели машину времени и путешествуют по всяким векам, предостерегая
народ в прошлом от ошибок в криптографии и спрашивая у народа в будущем, как
обстоят дела с дискретными логарифмами.
"Чувак," -- говорят они, -- "мы в 1977 году занимались такой же фигней как ты и придумали
атаку "встреча посередине" (meet-in-the-middle). Для нахождения ключей для
твоего шифра понадобится не 216 операций, а 29 операций плюс 28 памяти. Нужно сначала зашифровать известный текст всеми возможными 8-битными ключами и сохранить результат, а потом пробовать расшифровывать шифротекст, опять же, 8-битными ключами. Если текст, который мы расшифровали совпадет с одним из тех, что мы зашифровали и сохранили ранее, то мы получим все два ключа."
И начали выдалбливать на большом камне код на Си, чтобы продемонстрировать
атаку. (Стоит отметить, что код вы прекрасно понимали, потому что Си был
изобретен как раз где-то в каменном веке.)
#include <err.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <openssl/blowfish.h>
#include <openssl/lhash.h>
Это инклюды, которые нам понадобятся. Давай сделаем пару функций для шифрования:
/* Encryption and decryption */
void
cipher(int what, uint8_t *dst, uint8_t *src, uint8_t key)
{
BF_KEY bk;
BF_set_key(&bk, 1, &key);
BF_ecb_encrypt(src, dst, &bk, what);
}
Для примера будем использовать Blowfish с 8-битным ключом, потому что твой SAES
в libcrypto еще не добавили. Аргумент what может быть BF_ENCRYPT для шифрования и
BF_DECRYPT для расшифровки. Эта функция может шифровать текст длинной только
1 байт.
Теперь выдолбим аналог 2SAES. Для демонстрации атак нам нужно только шифрование:
void
double_encrypt(uint8_t *dst, uint8_t *src, uint8_t key[2])
{
cipher(BF_ENCRYPT, dst, src, key[0]);
cipher(BF_ENCRYPT, dst, dst, key[1]);
}
То есть, берем 16-битный (2-байтный) ключ, шифруем текст первыми восемью
битами, а результат шифруем вторыми восемью битами.
Приступим к атакам. Это нам пригодится:
/* Attacks */
const char report[] = "Key: \"%c%c\"\tOperations: %d\n";
const char notfound[] = "No keys founds in %d operations\n";
Итак, брутфорс, простой перебор ключей:
/*
* Bruteforce attack
*/
void
bruteforce(uint8_t *plaintext, uint8_t *ciphertext)
{
uint8_t buf1[8], buf2[8];
int i, j, op = 0;
for (i = 0; i < 256; i++) {
cipher(BF_DECRYPT, buf1, ciphertext, i);
for (j = 0; j < 256; j++) {
++op;
cipher(BF_DECRYPT, buf2, buf1, j);
if (memcmp(buf2, plaintext, 8) == 0) {
printf(report, j, i, op);
return;
}
}
}
printf(notfound, op);
}
Нам известны текст и шифротекст (например, мы знаем, что Алиса всегда начинает
свои письма с фразы "Hello Bob"). Тупо подбираем первый и второй ключи,
расшифровывая текст комбинациями и сравнивая его с оригинальным текстом. Если
текст совпал, значит мы нашли ключи. Нам понадобится в худшем случае 65536
вариантов, чтобы найти правильные ключи.
А смотри как делается наша meet-in-the-middle атака. Нам нужно где-то хранить
шифротексты -- известный текст, зашифрованный всеми возможными 8-битными ключами. Типа:
- Ynfxr4hf => A
- dfRYO1Hi => B
- ...
и так со всеми 256 ключами.
Давай-ка возьмем OpenSSL-евскую хэш-таблицу, в которую запихаем 28
шифротекстов с соответствующими ключами.
/*
* Meet-in-the-middle attack
*/
/* Hash table of encrypted texts mapped to all possible keys */
typedef struct {
uint8_t enc[8]; /* encrypted text, hash table key */
uint8_t key; /* 8-bit encryption key */
} EK;
/* EK_hash works reliably only if long is 64 bits */
unsigned long EK_hash(const EK *v) { return *(unsigned long *)v->enc; }
static IMPLEMENT_LHASH_HASH_FN(EK_hash, const EK*);
int EK_cmp(const EK *v1, const EK *v2) { return memcmp(v1->enc, v2->enc, 8); }
static IMPLEMENT_LHASH_COMP_FN(EK_cmp, const EK*);
Ключом хэш-таблицы будет шифротекст, а значением -- 8-битный ключ шифрования,
чтобы мы могли примерно так спрашивать нашу таблицу: "таблица-таблица,
повернись ко мне передом, а к лесу задом, и скажи мне: если у меня есть
шифротекст "бла-бла", то каким ключом это было зашифровано?"
Но для начала таблицу надо заполнить, для чего выдолбим такую функцию:
void
encrypt_all_keys(LHASH *h, EK items[], uint8_t *plaintext)
{
int i;
for (i = 0; i < 256; i++) {
items[i].key = i;
cipher(BF_ENCRYPT, items[i].enc, plaintext, i);
lh_insert(h, &items[i]);
}
}
Эта функция будет шифровать заданный текст всеми ключами от 0 до 255 поочередно,
поворачивать таблицу к нам передом, а к лесу задом, и запихивать в нее
получившиеся шифротексты и соответствующие им ключи.
Приступим непосредственно к атаке:
void
meetinthemiddle(uint8_t *plaintext, uint8_t *ciphertext)
{
EK items[256], lookup, *found;
LHASH *h;
int i;
if ((h = lh_new(LHASH_HASH_FN(EK_hash),
LHASH_COMP_FN(EK_cmp))) == NULL) {
warn("hash table");
return;
}
encrypt_all_keys(h, items, plaintext);
for (i = 0; i < 256; i++) {
cipher(BF_DECRYPT, lookup.enc, ciphertext, i);
if ((found = lh_retrieve(h, &lookup)) != NULL) {
printf(report, found->key, i, i+256);
goto done;
}
}
printf(notfound, i+256);
done:
lh_free(h);
}
В этой функции мы создаем таблицу и заполняем ее, как описано выше на камне. После чего
начинаем полу-брутфорсить: расшифровывать шифротекст всеми ключами от 0 до 255
и спрашивать таблицу, есть ли в ней соответствующий шифротекст с ключом. Если
есть -- та-да-м! -- встретились посередине и нашли оба ключа.
(В отчете к i добавляется 256, потому что мы хотим посчитать количество операций, а при заполнении хэш-таблицы мы как раз сделали 256 операций.)
Чтобы проверить, как все это работает, давай выдолбим макрос, который будет
измерять, сколько времени затрачивают атаки:
#define MEASURE(x) do { \
printf("%s\n", #x); \
clock_t t = clock(); (x); \
printf("%.3f sec\n\n", (clock()-t)/(double)CLOCKS_PER_SEC); \
} while (0)
и main, в которой сначала запустим брутфорс, а потом meet-in-the-middle:
int
main()
{
uint8_t plaintext[8] = "Dear Bob";
uint8_t key[2] = "Go";
uint8_t ciphertext[8];
double_encrypt(ciphertext, plaintext, key);
MEASURE( bruteforce(plaintext, ciphertext) );
MEASURE( meetinthemiddle(plaintext, ciphertext) );
return 0;
}
Программа шифрует текст "Dear Bob" 16-битным ключом "Go" и запускает атаки,
выводя найденный ключ.
Попробуем? Назовем камень, на котором мы выдалбливали код "meet.c",
откомпилируем,
$ cc -lcrypto -o meet meet.c
и запустим:
$ ./meet
bruteforce(plaintext, ciphertext)
Key: "Go" Operations: 28488
1.361 sec
meetinthemiddle(plaintext, ciphertext)
Key: "Go" Operations: 367
0.018 sec
Йай! Брутфорс занял 1.4 секунды и 28488 операций, а наша крутая атака всего
0.018 секунды и 367 операций (и примерно 256*(8+8) = 4096 байт памяти)!
На этом Диффи с Хеллманом завели Делореан и улетели в будущее узнавать, как там поживают квантовые компьютеры, а в наше время археологи раскопали камень с выбитым кодом и выложили его на гитхаб:
Заодно перевели на современный язык:
Для алгоритмов шифрования с нормальным размером ключа такая атака, конечно, не очень практична. Например, чтобы сломать двойной Blowfish, как выше, но, скажем, с двумя 64-битными ключами, нужно 265 операций и 2 эксабайта памяти. Где столько найти-то? (Да и вообще, что за экса такая?) Но знать о такой штуке полезно. Например, 3DES, который делает EncryptK3(DecryptK2(EncryptK1(текст))), хоть и позволяет шифровать с тройным ключом (56*3 = 168 бит), но из-за meet-in-the-middle секьюрность у него 168-56 = 112 бит.
C'est la vie.
Коллаж сделан из фоток с википедии: 1 2 3.
—
07.07.2011
