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

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

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

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

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

Обновить

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

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

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

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

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

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

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

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

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

Источник

5 ответов

Это очень похоже на проблему 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: (незарегистрированные пользователи не могут включать изображения, поэтому вот ссылка) https://en.wikipedia.org/wiki/File:TEA_InfoBox_Diagram.png

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам