банальный xor, продолжение :)

Почему банальный xor не надежен? Можно ли востановить текст?
Допустим p1, p2, p3, p4 .... pn - это файлы зашифрованные одним ключем - k,
соответственно:
c1 = p1 xor k
c2 = p2 xor k
c3 = p3 xor k
c4 = p4 xor k
....
cn = pn xor k
Во всех случаях длина k больше любого из p. Можно ли, имея все эти шифротексты,
получить k или хотябы один из p?
PS. В p - двоичные данные, а не текст.

 

Говорили же уже, что перексорив например p1 и p2 мы получаем с1 xor c2 (поправьте если вру)
а там уже дело техники...

это не должно влиять на криптостойкость алгоритма )

 

userx

Если у тебя в p1, p2, p3, p4 .... pn лежат случайные (или не отличающиеся от них по характеристикам) данные и k длинее данных, то да - система получится стойкой. До тех пор, пока не удастся узнать какой-нибудь из p_{i}.

 

Все правильно, c{i} xor c{j} = p{i} xor p{j}, и то что это действие полностью избавляет нас от гаммы тоже верно. Но реально это дает нам только ВСЕ ВОЗМОЖНЫЕ ПАРЫ при ксоре дающие одно и тоже число (равное c{i} xor c{j}). Для одного байта это может быть не много, а вот сколько их будет для p длиной в 1024 бит? 4096 бит? 8 Мбайт?

Предположим, что это звуковая волна в сыром формате (без стандартных заголовков), или изображение также в сыром формате, строки из RGBA... Это делает все возможные дешифрованные данные равновероятными. Т.е. нет механизма явного определения того получили мы открытый текст или нет. Определить можно только как говорится на глаз.

Правильно, но как получить p{i} зная только c1, c2, c3, c4, c5, c6 ... cn? Есть ли реальный способ? Ведь здесь метод анализа частотных характеристик не подойдет.

 

если формат данных неизвестен и оригинальный файл по характеристикам рендом то нет. Но с таким же успехом можно выложить и нешифрованный файл. зачем тогда вообще xor?

 

Ты не совсем понял. Формат известен, но в нем нет заголовгов (т.е. нет одинаковых данных для всех p) по которым можно было бы получить часть ключа.

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

Кстати изображение в сыром формате нельзя защитить ксором, странно что никто не заметил... При этом измениться только цвет и все. А вот звуковая волна другое дело.

Я сейчас не говорю про конкретные проги, которые успешно проигрывают эти файлы. Есть ли они или нет. Попробуйте абстрагироваться, ДОПУСТИМ ЕСТЬ программа способная нужным образом использовать эти файлы. И ДОПУСТИМ ЧТО ЕСТЬ двоичные данные файлах. И что они защищены xor-ом с ключем бОльшим по размеру чем любой закрытый файл. Можно ли получить хотябы один открытый файл? или XOR слаб только на словах?

 

Ну вот опять xor.
userx
xor - это симметричный алгоритм шифрования.
Это значит, что процедура, которая у тебя используется для шифрования, с тем же успехом может
использоваться и для дешифрования.
Именно поэтому xor слаб.

Иными словами, твой файл зашифрованный xor нет смысла, даже пытаться сопоставлять с чем-то.
Загнал его принудительно в ту процедуру, которой ты его шифруешь и получил на выходе открытый файл.
ВСЕ!!!
И хоть какой длины ты там ключ ставь.

 

это понятно, но если у тебя нет верного ключа на выходе ты получишь искаженные данные

Какой ты простой Файлы уже зашифрованы, лежат себе готовые спокойно. А ключ в уме.
И как ты их загонишь в процедуру без ключа??? )) Если бы речь шла о шифрующих устройствах, то ты был бы прав.

кстати, большинство потоковых шифров симетричны, взять к примеру rc4

 

Miller Rabin
Вот тебе шифрованный по xor файл
S`cho!Lhmmds
Получи из него открытый текст.

 

userx

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

Стойкой называется система шифрования, которая выполняет определенные требования. Одно из простейших требований - надежность шифрования не должна зависеть от данных. В случае xor'a это требование не выполняется (исключение - one-time pad), поэтому xor автоматически является слабым. Не говоря уже о стойкости к known plaintext атаке

 

Stiver, по поводу стойкости согласен.

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

Предлагаю всем перейти ко второму вопросу. Как получить p{i}, зная n шифротекстов?

 

кроме как ручками никак... либо анализом того, что по идее должно получиться, что почти одно и тоже(зависит от качества анализа), причем если гамма действительно случайна, то 100%й гарантии что все байтики сложатся как надо нет.
Ессно чем больше шифротекстов тем больше вероятность того что мы подберем правильный ксоробайт
Минус в том что длина ключа = max длине файла (больше не имеет смысла) и в том что чем больше шифротекстов, тем больше вероятности подобрать то что надо... Если уж юзать гамму, то в кач-ве одноразового блокнота.

 

А как подбирать?
Для данных длиной в байт получается 256 вариантов p{i} и p{j} для одного значения, равного с{i} xor c{j}, причем для любых значений c{i} и c{j} (в пределе байта 0-255 включительно).

 

разговор не об одном байте а о файлах, которые, предположительно можно анализировать. не со 100%й точностью, но можно... Сам же сказал что

 

давай для простоты сократим размер файла до 1 байта

а каким образом количество щифротекстов может сократить количество возможных вариантов ключей?

 

Да успокойся ты, говорят же - нельзя. Только анализировать если известно примерно, что должно получится. (И если получится, то тоже примерно). Понятно, что если исходными были монохромные картинки (лучше векторные даже ), то визуально по ксору первой с остальными ты ее сможешь выделить ( т.е. понять что там было такое нарисовано), но не факт что восстановишь точно. Все остальное флуд..

 

В дополнение: шифрованные XOR базы в .DBF (старая Aladdin'овская защита, ок. 95 г.). Текст на двух языках (bidirectional), keysize (определился после нескольких проб) - 16384 байт. Комбинируя файлы между собой (около десятка) и сами с собой + характерные особенности .DBF - восстановил все.

 

Сегодня выяснил, что ключ можно востановить зная (p1 xor p2 xor p3)

 

Да, архисложная задача. Только откуда возьмется такая информация ? А так можно найти ключ, зная p(1)^p(2)^..p(2*n+1), толку то..

 

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

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

1. Есть процедура, которая осуществляет шифрование по твоему методу. Она естественно общедоступна
2. Есть файл, который ты хочешь защитить. Он секретный.
3. Есть ключ, которым ты шифруешь файл. Он супер большой и супер секретный.
4. Ты зашифровал файл этим ключом по XOR это знают все и он тоже общедоступен. Но прочитать правильно его может только тот, кто знает ключ.

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

А в стойкой криптосистеме такую взаимосвязь будет найти ОЧЕНЬ СЛОЖНО.

Рассмотрим вариант 2. Пусть твоя процедура перед тем как начать шифрование спрашивает "Какой ключ будем использовать?" И потом шифрует этим ключем.
Именно про это ты и втирал нам усиленно столько постов.

Только тогда такой вопрос?
А что ты этим сможешь защитить?
Единственная область применения данного подхода, как говорится "For home use only".

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

Именно поэтому не представляет никакого практического интереса