Вопрос: взлом шифра xor
Пишу диплом-псвдонаучную работу (чесно сознаюсь):
Имееться n камер видеонаблюдения, с которых снимаються данные и передаються.
Данные (кадры) сначала архивируються, потом к ним прибавляються некие случайные биты и все это прогоняеться через P/S-box.
В итоге получаеться псевдослучайная последовательность бит.
Теперь самое главное: эта последовательность шифруеться обычным шифром xor. Длина ключа 64 бит, эти 64 бит ключа выбраны случайно, но ключ повторяеться нужное число раз, пока не будет заксорено все сообщение.
Вопрос:
Можно ли востаносить псевдослучайную последовательность без знания ключа?
p.s.
К поточным шифрам прошу не отсылать.
К атакам на основе извесного открытого теста тоже.
Как можно зацепиться за повторения ключа?
Трудность в том что ксоряться практически случайные данные.
Писал уравнения, но неизвесных больше чам самих уравнений.
Брут пароля не подходит. Перебор частями тоже, все равно знание её части абсолюно ничего не даст в востановлении исходного сообщения.
Ссылки
[link1] https://www.pgpru.com/forum/prakticheskajabezopasnostj/goldlockshifrovaniemobiljnyhperegovorov?p=1&show_comments=1#comments
И давно у нас XOR — шифр, а не элементарная логическая операция?
Что есть
истинашифр? :)P — открытый текст
K — ключ
C — шифртекст
C = K xor P
C1 xor C2 = (K xor P1 ) xor (K xor P2 ) = P1 xor P2
xor двух блоков шифртекста будет давать данные о xor двух блоков открытого текста. Ну да, его там сжимали, черз S/P блоки пропускали, это затрудняет анализ, но это биективное преобразование без ключа, когда-то так поломали экстрактор случайности (генератор случайных чисел из шума, работающий по схожему принципу), после чего доказали, что все экстракторы должны строиться на небиективных сжимающих функциях.
И какой бы ни была информация в данном случае, она будет иметь отклонения от случайной, что отразится на статистике, чем больше блоков, тем больше будет утечка информации о ключе.
Вопрос обычно ставят так — можно ли для начала найти различитель от идеальной псевдослучайной функции?
Т.е. камера не может сломаться и показывать чёрный экран к примеру? И каие-нибудь вспышки в объектив нельзя делать, чтобы в шифртексте поискать отклик?
истинашифр? :)Обратимая функция, для которой невозможно построить различитель от PRP или PRF (псевдослучайной перестановки всех вариантов блоков открытого текста в шифртекст или псевдослучайной функции, задаваемой ключом) быстрее, чем атаки грубой силой при любом типе воздействия на вход (или выход, если он обратим: вход по ключу — необратим, а вот выход по тексту в блочном шифре обратим).
Если бы так...
Как только будет черный экран (или часть кадра займет один цвет) – архиватор сожмет кадр, а освободивщееся место займут случайные данные. И это все затем будет подано на
P/S-box-ы.:(
В том и беда – данные, которые попадают на ксор, практически случайные.(Проверено тестами). Если я буду ксорить пары блоков – буду получать ксоры пар практически случайных блоков.
Може еще есть способы использовать многократное повторение ключа?
[offtop]
Мама дорогая! В наше время даже школьники так уже не писали. Книг вообще не читаете, только Интернет? А надо бы...
[/offtop]
1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.
2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов. Результатом операции будет удаление ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3бита действительной информации(см раздел 11.1), существующая значительная избыточность позволяет определить способ шифрования.
© Шнайер
По условию задачи это не требуется — там уже указано, что ключ 64 бита.
Он уже объяснил, почему в его случае это так просто не прокатит.
Т.е. это тренировочная задача, не для того чтобы её критиковать. Система заведомо дефектная, нужно найти самый простой и красивый способ взлома.
P — открытый текст
|| — дополнение
C — шифртекст
K — ключ
A — архивирование
R — данные из истинного генератора случайных чисел (TRNG) для дополнения к размеру блока
S — шеренга S-блоков (S-блок сказано, что один, значит он повторяется n раз по размеру блока), допустим размер 8x8, значит повторяется 8 раз для размера блока = 64
Pb — P-блок (побитовая перестановка), допустим 64 (равен размеру блока).
C = K xor Pb (S (A (P) || R ))
И всё это в один раунд без ключа, ключ только накладывается ксором поверх.
Может подойдёт какой-то упрощённый линейный криптоанализ или хи-квадрат криптоанализ, надо в подробностях ковыряться.
истинашифр? :)И почему бы тогда не удостоить
схему одноразовых блокнотовэлементарную логичкскую операцию XOR гордого звания шифра? :)Совершенно верно.
Ещё раз: блочный шифр — обратимая функция, неотличимая от PRP (псевдослучайной перестановки всех вариантов блоков и т.д. см. выше), задаваемой ключом.
Поточный шифр — функция, неотличимая от PRF, задаваемая ключом и внутренним состоянием, выход которой обратимо (чаще всего путём того же xor) накладывается на открытый текст в виде гаммы — для получения шифртекста в итоге.
Кстати, возможны мнимые противоречия из-за промежуточных вариантов.
Совершенно естественно, что одноразовый блокнот, построенный на XOR — это предельный вариант даже не PRF, а "True"RF, соответственно — это частный (или предельный: ключ стремится к бесконечности, а внутреннего состояния нет и не нужно) случай потокового шифра.
Но XOR — это операция, а не шифр. Просто в одноразовом блокноте она фактически единственная. Но если не соблюдать правила одноразовости, истинной случайности, то получается совсем другая схема, пусть с тем же XOR, но нестойкая. Автора топика вариант такой системы и интересует, но в рамках строго заданных практических условий и с наворотами — атака только по шифртексту, открытый текст труднопредсказуем, содержит много энтропии, дополнительно сжимается и дополняется истинно случайными данными (которые в процессе расшифровки видимо отбрасываются), пропускается через S- и P-блок.
А нет ли тут общего с Gold Lock[link1]? Там тоже модифицированный XOR. Хотя как именно модифицированный не уточняется.
Тогда у кого-то есть шанс на $250000? До 1 февраля 2010.
В Gold Lock с вероятность 90% AES в режиме счётчика, XOR только накладывает гамму на поток.
unknown правильно описал ситему.
Это не поточный шифр. Ключ длиной 64 бит и повторяеться много раз.
Система явно дефектная, но вот как воспользоваться дефектом?
Похоже на этот вопрос современная криптография не может ответить.
p.s.: конкурс Gold Lock мне не знаком.
С чего вы взяли, что это возможно? Криптография старается работать без дефектных схем, чтобы быть применимой в случаях, намного более широких чем вами описанный.