id: Гость   вход   регистрация
текущее время 20:48 28/03/2024
Автор темы: Гость, тема открыта 28/12/2009 18:48 Печать
Категории: криптография, случайные числа
https://www.pgpru.com/Форум/Криптография/ВопросВзломШифраXor
создать
просмотр
ссылки

Вопрос: взлом шифра xor


Пишу диплом-псвдонаучную работу (чесно сознаюсь):


Имееться n камер видеонаблюдения, с которых снимаються данные и передаються.


Данные (кадры) сначала архивируються, потом к ним прибавляються некие случайные биты и все это прогоняеться через P/S-box.
В итоге получаеться псевдослучайная последовательность бит.


Теперь самое главное: эта последовательность шифруеться обычным шифром xor. Длина ключа 64 бит, эти 64 бит ключа выбраны случайно, но ключ повторяеться нужное число раз, пока не будет заксорено все сообщение.


Вопрос:
Можно ли востаносить псевдослучайную последовательность без знания ключа?


p.s.


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


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


Брут пароля не подходит. Перебор частями тоже, все равно знание её части абсолюно ничего не даст в востановлении исходного сообщения.



 
Комментарии
— SATtva (28/12/2009 20:01)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
эта последовательность шифруеться обычным шифром xor

И давно у нас XOR — шифр, а не элементарная логическая операция?
— Гость (28/12/2009 21:09)   <#>
Что есть истина шифр? :)
— unknown (28/12/2009 22:12, исправлен 28/12/2009 22:27)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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 (псевдослучайной перестановки всех вариантов блоков открытого текста в шифртекст или псевдослучайной функции, задаваемой ключом) быстрее, чем атаки грубой силой при любом типе воздействия на вход (или выход, если он обратим: вход по ключу — необратим, а вот выход по тексту в блочном шифре обратим).

— Mekong (28/12/2009 22:42)   <#>
Т.е. камера не может сломаться и показывать чёрный экран к примеру? И каие-нибудь вспышки в объектив нельзя делать, чтобы в шифртексте поискать отклик?

Если бы так...
Как только будет черный экран (или часть кадра займет один цвет) – архиватор сожмет кадр, а освободивщееся место займут случайные данные. И это все затем будет подано на
P/S-box-ы.:(
В том и беда – данные, которые попадают на ксор, практически случайные.(Проверено тестами). Если я буду ксорить пары блоков – буду получать ксоры пар практически случайных блоков.

Може еще есть способы использовать многократное повторение ключа?
— Гость (29/12/2009 00:43)   <#>
[offtop]
Пишу диплом ... передаються ... получаеться

Мама дорогая! В наше время даже школьники так уже не писали. Книг вообще не читаете, только Интернет? А надо бы...
[/offtop]
— Paran0ik (29/12/2009 09:24)   профиль/связь   <#>
комментариев: 88   документов: 13   редакций: 3
1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.
2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов. Результатом операции будет удаление ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3бита действительной информации(см раздел 11.1), существующая значительная избыточность позволяет определить способ шифрования.

© Шнайер
— unknown (29/12/2009 10:11, исправлен 29/12/2009 10:15)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

По условию задачи это не требуется — там уже указано, что ключ 64 бита.


Он уже объяснил, почему в его случае это так просто не прокатит.


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

— unknown (29/12/2009 10:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
P — открытый текст
|| — дополнение
C — шифртекст
K — ключ
A — архивирование
R — данные из истинного генератора случайных чисел (TRNG) для дополнения к размеру блока
S — шеренга S-блоков (S-блок сказано, что один, значит он повторяется n раз по размеру блока), допустим размер 8x8, значит повторяется 8 раз для размера блока = 64
Pb — P-блок (побитовая перестановка), допустим 64 (равен размеру блока).

C = K xor Pb (S (A (P) || R ))

И всё это в один раунд без ключа, ключ только накладывается ксором поверх.

Может подойдёт какой-то упрощённый линейный криптоанализ или хи-квадрат криптоанализ, надо в подробностях ковыряться.
— Гость (29/12/2009 18:38)   <#>

И почему бы тогда не удостоить схему одноразовых блокнотов элементарную логичкскую операцию XOR гордого звания шифра? :)
— unknown (29/12/2009 21:14, исправлен 29/12/2009 21:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Совершенно верно.


Ещё раз: блочный шифр — обратимая функция, неотличимая от PRP (псевдослучайной перестановки всех вариантов блоков и т.д. см. выше), задаваемой ключом.


Поточный шифр — функция, неотличимая от PRF, задаваемая ключом и внутренним состоянием, выход которой обратимо (чаще всего путём того же xor) накладывается на открытый текст в виде гаммы — для получения шифртекста в итоге.


Кстати, возможны мнимые противоречия из-за промежуточных вариантов.


Совершенно естественно, что одноразовый блокнот, построенный на XOR — это предельный вариант даже не PRF, а "True"RF, соответственно — это частный (или предельный: ключ стремится к бесконечности, а внутреннего состояния нет и не нужно) случай потокового шифра.


Но XOR — это операция, а не шифр. Просто в одноразовом блокноте она фактически единственная. Но если не соблюдать правила одноразовости, истинной случайности, то получается совсем другая схема, пусть с тем же XOR, но нестойкая. Автора топика вариант такой системы и интересует, но в рамках строго заданных практических условий и с наворотами — атака только по шифртексту, открытый текст труднопредсказуем, содержит много энтропии, дополнительно сжимается и дополняется истинно случайными данными (которые в процессе расшифровки видимо отбрасываются), пропускается через S- и P-блок.

— Гость (30/12/2009 17:42)   <#>
А нет ли тут общего с Gold Lock? Там тоже модифицированный XOR. Хотя как именно модифицированный не уточняется.

Тогда у кого-то есть шанс на $250000? До 1 февраля 2010.
— SATtva (30/12/2009 18:37)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
В Gold Lock с вероятность 90% AES в режиме счётчика, XOR только накладывает гамму на поток.
— mekong (30/12/2009 19:07)   <#>
unknown правильно описал ситему.
Это не поточный шифр. Ключ длиной 64 бит и повторяеться много раз.

Система явно дефектная, но вот как воспользоваться дефектом?

Похоже на этот вопрос современная криптография не может ответить.

p.s.: конкурс Gold Lock мне не знаком.
— Гость (30/12/2009 19:40)   <#>
Система явно дефектная, но вот как воспользоваться дефектом?

С чего вы взяли, что это возможно? Криптография старается работать без дефектных схем, чтобы быть применимой в случаях, намного более широких чем вами описанный.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3