Как взломать ослабленный блочный шифр TEA?

Это очень похоже на задачу Double Crypt из конкурса программирования IOI '2001. Общее решение показано здесь, оно не даст вам код, но может указать вам в правильном направлении.

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

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

for (test_key=0; test_key<max; test_key++)
    if (encrypt(plaintext, test_key) == ciphertext)
        std::cout << "Key = " << test_key << "\n";

Шифрование, происходящее дважды, означает, что ваш encrypt будет выглядеть примерно так:

return TEA_encrypt(TEA_encrypt(plaintext, key), key);

Edit2: хорошо, исходя из отредактированного вопроса, вам, по-видимому, придется дважды использовать ослабленный TEA, каждый со своим 16-битным ключом. Вы можете сделать это с помощью одного цикла, как показано выше, и разделить test_key на два независимых 16-битных ключа, или вы можете сделать вложенный цикл, например:

for (test_key1=0; test_key1<0xffff; test_key1++)
    for (test_key2=0; test_key2<0xffff; test_key2++)
        if (encrypt(encrypt(plaintext, test_key1), test_key2) == ciphertext)
            // we found the keys.

Я не уверен, справедливо ли это свойство для 16-битных ключей, но 128-битные ключи обладают тем свойством, что четыре ключа эквивалентны, что сокращает пространство поиска в четыре раза. Я не сразу помню, как найти эквивалентные ключи, только то, что ключевое пространство не так велико, как кажется. Это означает, что он подвержен атаке с использованием связанного ключа.

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

Эквивалентные клавиши достаточно просты для понимания и сокращают пространство клавиш в четыре раза. Ключ разделен на четыре части. Каждый цикл TEA состоит из двух раундов. Первый использует первые две части ключа, а второй использует 3-ю и 4-ю части. Вот схема одного цикла (двух раундов) TEA: (незарегистрированные пользователи не могут включать изображения, поэтому вот ссылка) https://en.wikipedia.org/wiki/File:TEA_InfoBox_Diagram.png

Примечание: зеленые прямоугольники — это дополнение, красные кружки — XOR.

TEA работает с блоками, которые он разбивает на две половины. Во время каждого раунда одна половина блока сдвигается на 4,0 или -5 бит влево, к ней добавляется часть ключа или константа раунда, а затем к другой половине добавляется XOR полученных значений. блока. Переворот старшего бита любого ключевого сегмента переворачивает один и тот же бит в суммах, для которых он используется, и, соответственно, в результате XOR, но не имеет другого эффекта. Изменение старшего бита обоих ключевых сегментов, используемых в цикле, дважды переворачивает один и тот же бит в продукте XOR, оставляя его неизменным. Переворачивание этих двух битов вместе не меняет результат блочного шифра, делая перевернутый ключ эквивалентным оригиналу. Это можно сделать как для (первого/второго), так и для (третьего/четвертого) ключевых сегментов, уменьшив эффективное количество ключей в четыре раза.

Учитывая (скромный) размер вашего ключа шифрования, вы можете позволить себе создать предварительно рассчитанную таблицу (используйте тот же код, что и выше, и храните данные в больших фрагментах памяти — если у вас недостаточно оперативной памяти, сбрасывайте фрагменты на диск и сохраните схему адресации, чтобы вы могли искать их в правильном порядке).

Это позволит вам охватить всю область, и поиск решения будет выполняться в режиме реального времени (поиск в одной таблице).

Тот же прием (усечение ключей) использовался (не так давно) в ведущих программах Office. Теперь они используют неслучайные данные для генерации ключей шифрования, что (в лучшем случае) приводит к тому же результату. На практике возможность знать ключи шифрования до их генерации (поскольку так называемый генератор случайных чисел предсказуем) даже более желательна, чем усечение ключей (оно приводит к тому же результату, но без необходимости создавать и хранить радужные столы).

Это называется марш прогресса...