Допустим, вы живете в каменном веке и изобрели шифр с 8-битным ключом, то есть, всего имеется 28 = 256 комбинаций. Назвали вы его SAES (Stone Age Encryption Standard). Шифр работал отлично, но прогресс не стоит на месте: у людей отросло больше пальцев на руках, они научились быстрее считать, и ваш 8-битный шифр стал не таким надежным, как раньше, потому что подобрать комбинацию из 256 вариантов стало просто. Вы решаете, что нужно сделать 16-битный шифр (216 = 65536 вариантов ключа). SAES себя хорошо зарекомендовал во всех остальных качествах, кроме размера ключа. Почему бы не взять его за основу и просто увеличить размер ключа с 8-ми до 16-ти бит?

Как это сделать? – думаете вы. Что если взять и зашифровать текст сначала одним 8-битным ключом, например, «A», а потом полученный зашифрованный текст зашифровать еще одним (возможно, другим) 8-битным ключом, например «B»?

  1. ШИФРОВАТЬ(«Dear Bob», «A») = «Ynfxr4hf»
  2. ШИФРОВАТЬ(«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.