Криптоанализ: XOR двух текстовых файлов - PullRequest
7 голосов
/ 15 апреля 2011

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

РЕДАКТИРОВАТЬ:

Хорошо, у меня также есть два шифротекста, которые я XORed, чтобы получить XOR двух открытых текстов.Причина, по которой я задаю этот вопрос, заключается в том, что, по словам Брюса Шнайера, с.198, Прикладная криптография, 1996 "... она может XOR их вместе и получить два XI-сообщения в открытом виде, которые можно XORed друг с другом. Это легко сломать, и затем она может XOR один из открытых текстов с помощью зашифрованного текста, чтобы получить ключевой поток".(Это относится к простому потоковому шифру) Но кроме этого он не дал никаких объяснений.Вот почему я спросил здесь.Прости мое невежество.

Кроме того, используемый алгоритм является простым, и используется симметричный ключ, длина которого составляет 3.

ДОПОЛНИТЕЛЬНОЕ РЕДАКТИРОВАНИЕ:

Я забыл добавить: я предполагаю, что для шифрования использовался простой потоковый шифр.

Ответы [ 5 ]

7 голосов
/ 15 апреля 2011

Я не криптоаналитик, но если вы знаете что-то о характеристиках файлов, у вас может быть шанс.

Например, предположим, что вы знаете, что оба исходных текста:

  • содержит простой текст на английском языке ASCII
  • статьи о спорте (или что-то еще)

Учитывая эти 2 фрагмента информации, один из подходов, который вы можете использовать, - это сканирование зашифрованного текста «расшифровкой» с использованием слов, которые вы, возможно, ожидаете найти в них, таких как «футбол», «игрок», «счет» и т. Д. Выполните расшифровку, используя «футбол» в позиции 0 зашифрованного текста, затем в позиции 1, затем в 2 и т. Д.

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

Повторите этот процесс с другими словами / фразами / фрагментами, которые вы, вероятно, ожидаете увидеть в открытых текстах.


В ответ на правку вашего вопроса: о чем говорит Шнайер, так это о том, что если у кого-то есть 2 зашифрованных текста, которые были зашифрованы с помощью XOR с использованием того же ключа, то XOR при использовании этих зашифрованных текстов «отменит» поток ключей, поскольку:

(A ^ k) - ciphertext of A
(B ^ k) - ciphertext of B

(A ^ k) ^ (B ^ k) - the two ciphertexts XOR'ed together which simplifies to:

A ^ B ^ k ^ k - which continues to simplify to
A ^ B ^ 0
A ^ B

Так что теперь у злоумышленника есть новый зашифрованный текст, который состоит только из двух открытых текстов. Если злоумышленник знает один из открытых текстов (скажем, у злоумышленника есть законный доступ к A, но не к B), его можно использовать для восстановления другого открытого текста:

A ^ (A ^ B)
(A ^ A) ^ B
0 ^ B
B

Теперь у атакующего есть открытый текст для B.

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

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

5 голосов
/ 15 апреля 2011

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

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

Обратите внимание, что в коде ASCII пробел является двоичным "0010 0000", и изменение этого бита в букве изменит регистр букв (от нижнего до верхнего и наоборот). Будет много XORing с использованием пробела, если оба файла - простой текст, верно? Анализ таблицы печатных символов на этой странице .

Также в конце вы можете использовать проверку орфографии.

Я знаю, что не дал решения для вашего вопроса. Я просто дал вам несколько советов. Веселитесь, и, пожалуйста, поделитесь своими выводами. Это действительно интересное задание.

4 голосов
/ 15 апреля 2011

Это интересно.Книга Шнейера действительно говорит, что это легко сломать.И тогда он как бы оставляет это в покое.Я полагаю, вы должны оставить некоторые упражнения читателю!

Есть статья Доусона и Нильсона , которая, очевидно, описывает автоматизированный процесс для этой задачи для текстовых файлов.Это немного на стороне $$, чтобы купить одну статью.Тем не менее, вторая статья под названием Подход на естественном языке к автоматизированному криптоанализу двукратных прокладок ссылается на работу Доусона и Нильсена и описывает некоторые допущения, которые они сделали (прежде всего то, что текст был ограничен 27 символами).Но эта вторая статья, кажется, находится в свободном доступе и описывает их собственную систему.Я не знаю наверняка, что это бесплатно, но это открыто доступно на сервере Университета Джона Хопкинса.

Эта статья занимает около 10 страниц и выглядит интересно.У меня нет времени читать это сейчас, но может позже.Я нахожу интересным (и рассказывающим), что требуется 10-страничный документ, чтобы описать задачу, которую другой криптограф назвал «легкой».

0 голосов
/ 15 апреля 2011

Если у вас нет одного из текстовых файлов, вы не можете получить исходную информацию о другом.Математически выражено:

p1 XOR p2 = en

У вас есть одно уравнение с двумя неизвестными, вы не можете извлечь из него что-то значимое.

0 голосов
/ 15 апреля 2011

Я не думаю, что вы можете - не зная ничего о структуре двух файлов.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...