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

Question

В данный момент я пытаюсь взломать блочный шифр TEA в C. Это задание, и чайный шифр ослаблен, поэтому ключ состоит из 2 16-битных чисел.

Нам даликод для кодирования открытого текста с использованием ключа и для декодирования зашифрованного текста также с помощью ключа.

У меня есть несколько примеров открытого текста:

1. кодированный открытый текст (1234,5678) (3e08, fbab)
2. кодированный в открытом виде (6789, dabc) (6617,72b5)

Обновление

Метод кодирования принимает открытый текст и ключ, кодирует (открытый текст), key1).Это происходит снова с другим ключом, чтобы создать закодированное сообщение, закодировать (ciphertext1, ключ), которое затем создает закодированное (3e08, fbab) или закодированное (6617,72b5).

Как бы я пошел на взлом этогошифр?

В данный момент я кодирую известный открытый текст всеми возможными ключами;размер ключа равен шестнадцатеричному значению ffffffff.Я записываю это в файл.

Но теперь я застрял и нуждаюсь в руководстве.

---

Как я могу использовать слабость эквивалентных ключей TEA, чтобы уменьшить количество времени, которое это могло бывзять взломать шифр?Кроме того, я собираюсь использовать человека в средней атаке.

Как и в случае кодирования с использованием известного открытого текста и всех ключей 1, он создаст весь зашифрованный текст с соответствующим ключом и сохранит его в таблице.

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

Затем я могу сравнить две таблицы вместе, чтобы увидеть, соответствует ли какой-либо из кодировок с ключом 1 дешифровкам с ключом 2.

Я хотел бы также использовать слабость equilenvent, если бы кто-то мог помочь мне в реализации этого в коде, что было бы здорово.Есть идеи?

Answer 1

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

Answer 2

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

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

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.

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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