id: Гость   вход   регистрация
текущее время 11:20 29/03/2024
Автор темы: Гость, тема открыта 13/09/2013 01:01 Печать
Категории: криптография, анонимность, криптоанализ, алгоритмы, атаки
http://www.pgpru.com/Форум/Криптография/ВзломПоточногоШифра
создать
просмотр
ссылки

Взлом поточного шифра


Здравствуйте уважаемые форумчане. Я в криптографии не силен, но хотелось бы немного углубиться и изучить азы этой науки? Вот столкнулся с интересной задачей, но не могу разобраться как решить. Суть задачи состоит в том, что есть 11 зашифрованных сообщений(различной длинны), они шифровались поточным шифром, с одинаковым ключом. Как можно расшифровать эти сообщения, в смысле как можно подобрать ключ,исходя из этих сообщений? В подсказке к задаче написано, что нужно про xor-ить все шифротексты. Но каким образом это должно помочь мне в поиске ключа? Заранее спасибо!


 
Комментарии
— Гость (13/09/2013 04:59)   <#>

Даже не знаю. Вы у меня спрашиваете? Кто хочет, тот углубляется, начиная с этого.


Заранее пожалуйста. Чувствую, что сентябрь уже в разгаре. Ждём зимней сессии.
— Иван (13/09/2013 10:34)   <#>
Сообщение писал поздно ночью ночью,поэтому возможно допустил пару ошибок и поставил не те знаки. Обязательно язвить? Это задание из онлайн курса криптографии оксфордского университета. Прочитав слайды по лекциям, я так и не понял как можно получить ключ из 11 шифротекстов, зашифрованных одним и тем же ключом.
— Иван (13/09/2013 11:28)   <#>
Хочу внести некоторую ясность. Я не школьник и не стремлюсь получить пятерку. Это действительно задача из онлайн курса Оксфордского университета. Как ответ к данной задаче- был приведен скрипт на питоне. Но питон я никогда не изучал. В подсказке к задаче было написано проксорить все шифротексты, я проксорил каждый шифротекст между собой, но кроме совпадающих байт, в некоторых местах, я ничего не нашел. Да я понимаю, если
  • c-шифротекст
  • k-ключ
  • p-открытый текст
Ci xor Cj=Pi xor Pj ,но я понять не могу каким образом мне это может помочь. Для тех кто по прежнему считает,что я ленивый школьник, преследующий меркантильные цели -хочу заверить это не так(курс лекций о котором я говорил выше, давно окончен, просто задача очень зацепила), вот даже кусок текста программы на java, где я ксорил строки:

правда немного индусский код получился, но сойдет, так как писалось на быструю руку, в данном коде я ксорил между собой две строки и выводил результаты на экран.
— unknown (13/09/2013 17:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Вот об этом сходу можно было подумать безо всякого кода. Если ключ одинаковый, а вектор инициализации не используется, то получаются одинаковые гаммы. А уже даже по двум шифртекстам можно восстановить только ксор двух открытых текстов, что тоже даёт существенную утечку: АНБ-шный проект Venonа так ломал советские одноразовые блокноты.
— Гость (13/09/2013 18:07)   <#>
Во-первых не Оксфордского, а Стенфордского университета.
Во-вторых, определить гамму при таком большом количестве осмысленных сообщений (с учетом низкой энтропии естественных языков) можно и вручную (если с английским проблем нет, хотя раз Вы слушаете онлайн курсы на нем, то видимо все в порядке), так даже более наглядно получается.
Вот, к примеру, ciphertext#3 и ciphertext#4 совпадают в первых четырех байтах, т.е. буквах в кодировке ASCII. В предположении что все открытые тексты являются английскими предложениями – попробуйте их заксорить с наиболее употребляемым словом английского языка "The " (вместе с пробелом конечно). Если предположение верное, то Вы получите первые четыре байта гаммы, проверить которые можно, к примеру, на ciphertext#6, в результате чего получите начало какого-то другого слова на английском, затем Вы можете предположить что это за слово и определить последующие символы гаммы и т.д.
— Иван (14/09/2013 04:18)   <#>
Вот это я и хочу узнать,каким образом это Ci xor Cj=Pi xor Pj может подтолкнуть меня к расшифровке? По поводу перебора символов по часто встречающимся словам в английском языке, а именно артикли и "and" и прочие часто встречающиеся слова, но я подумал, что подсказка проксорить все шифротексты-была дана не зря, и что есть какой то математический способ...
— Иван (14/09/2013 11:51)   <#>
Извините, сообщение это же писал на другом форуме, и так перенес с бб кодами.
Кажется я понял,как это делать. Если формула шифрования Ci=Pi xor Ki, где
Ci-шифротекст
Pi-открытый текст
Ki-ключ
то имея несколько сообщений зашифрованных одним ключом ,будет верно равенство
C1i xor C2i=P1i xor P2i
а дальше нужно брать буквы английского алфавита и ксорить их код по ascii таблице, при равенстве байт -говорит о том что использовались именно эти буквы. а дальше не сложно вычислить где какая буква должна стоять. Потом по формуле вычисляем ключ.
— Гость (14/09/2013 20:41)   <#>
Да, примерно так, только вот вариантов будет достаточно много (по числу букв). Можете еще воспользоваться тем фактом, что разность кодов букв в ASCII коде всегда находится в фиксированном интервале значений, а, допустим, разность кода буквы и кода пробела в другом интервале. Основываясь на этом факте можно сделать предположение, что в одном из двух шифротекстов на i позиции находится пробел, и определить в каком именно с помощью третьего шифротекста, заксорив с ними.
— Гость (15/09/2013 15:12)   <#>
Раз в современном мире современные шифры не ломают такими простыми уловками, зачем тогда обучать студентов этим уловкам? Можено же и просто объяснить на пальцах, почему примитивные шифры могут легко взламываться из-за того, что будет утекать, как минимум, частичная информация об открытом тексте. Чтобы это объяснить, не надо требовать доведения шифра до полного взлома. Исторически, когда стойких шифров не было, а добыча текста была делом государственной важности, это было оправдано, но сейчас же никто таким трюкачеством не занимается. Взлом примитивных любительских шифров с точки зрения его практического взлома, опять же, может быть интересен только форензикам.
— unknown (15/09/2013 19:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Диски больше десяти лет шифровали простым CBC. Пока простым ксором не проверили, что это приводит к элементарной утечке информации без знания ключа, хотя теоретически это давно было известно, но у теоретиков руки не доходили. Всевозможные ошибки с повторной генерацией гаммы в поточных шифрах и ГПСЧ из-за неправильных протоколов и реализации из той же серии. Если можно на практике показать, как это легко приводит к уязвимости, то почему бы это не сделать.
— Гость (15/09/2013 19:28)   <#>
Здесь дело не совсем в шифре, а в его неправильном использовании. Будь гамма сформирована с помощью AES в режиме CTR или путем бросания равновероятной монеты – в случае ее многократного использования итог будет один.
В этом онлайн курсе просто затрагиваются общие темы, введение в криптографию так сказать. Задание такое выбрано, вероятно, из-за того что результат наглядно виден, это ведь не абстрактное снижение стойкости с 2^128 до 2^126. Смысла объяснять метод биклик для широких масс нет и не будет.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3