— Гость (27/02/2013 01:25)   
Чтобы шифр XOR был стойким, нужно, чтобы это был одноразовый блокнот (one time pad), а длина ключа совпадала с длиной зашифровываемого текста. Это делает XOR непрактичным. Ни про какие безопасные модификации XOR'а не слышал, современные шифры строятся так, что они далеки от исходного XOR.


Длина гаммы не изменится. Это эквивалентно проксориванию с третьим паролем, который есть XOR ваших двух паролей (при одинаковой их длине). Проблемы те же, что и с одноразовым XOR'ом. Ломается частотным анализом и т.п.

— Euler (27/02/2013 02:22)   

Длина изменилась с 8 на 15, пароли не просто не одинаковой длины, а взаимнопросты. Современные шифры не интересуют, интересует именно возможность использования криптоаналитиком этого свойства гаммы.

— Гость (27/02/2013 03:22)   

Шифртекст = Текст ⊕ Пароль1 ⊕ Пароль 2 = Текст ⊕ (Пароль1 ⊕ Пароль2) = Текст ⊕ Пароль3, где Пароль3 = Пароль1 ⊕ Пароль2, причём имеет ту же длину, что и Пароль1 и что Пароль2. Я правильно вашу схему понял?


В чём цель? Изучение криптоанализа на простейших нестойких слабых шифрах? В институте задали задачу? Или взлом шифра какого-то Васи Пупкина?

Понимаете, есть некоторое утверждение, которое является по сути теоремой. Если вы не соблюдаете условия теоремы, вы получаете слабый небезопасный шифр, не удовлетворяющий современным критериям безопасности шифров. И в чём тогда смысл его анализировать? Ознакомьтесь с FAQ для начала:

• Понятие об отличии сертификационного и практического криптоанализа^[link2].
• Анализ любительских шифров^[link3].

— Euler (27/02/2013 04:18)   

Похоже нет. Давайте на примере. Шифруем сообщение "000000000000000000000000000000"(тридцать символов '0') паролем "12345678". Получаем "\1\2\3\4\5\6\7\8\1\2\3\4\5\6\7\8\1\2\3\4\5\6\7\8\1\2\3\4\5\6"(где \d – это символ с кодом d). Теперь разобъём тот же пароль на несколько частей, так чтобы НОК произведения длин этих частей был наибольшим, таким образом гамма увеличивается до НОК(5,3)=15. Получаем шифровку: "00022>1?<31?>3=00022>1?<31?>3=".
Дизассемблировал программу в которой трафик так шифровался двумя взаимнопростыми ключами, вот и стало интересно. Очевидно, что это усложняет описанный в википедии способ вскрытия, поэтому я попытался придумать другой, но не смог.

— unknown (27/02/2013 10:26, исправлен 27/02/2013 10:31)   

Получается:

Шифртекст = Текст ⊕ (Пароль (длина = p / n) || Пароль (длина = q / n) ), где "||" — это конкатенация (объединение),

n = p • q – НОК.

Т.е. длина увеличивается за счёт того, что две половинки пароля ещё и частично совпадают (перекрываются)?

— Euler (27/02/2013 13:48)   

эм... я тут ничего не понял, из второй строки следует, что n>=p, а в первой p делится на n, т.е. длина получается не больше единицы.
Более того – только за счёт этого. Для пароля из восьми символов операция шифрования на языке си будет выглядеть так:
//c - шифротекст. //p - исходный текст //k1 - первая часть пароля //k2 - вторая часть пароля //p_len - длина исходного текста for(int i=0;i<p_len;i++) c[i] = p[i] ^ (k1[i]%5) ^ (k2[i]%3)

— unknown (27/02/2013 15:03)   
Хорошо, обозначение неудачное, с длиной не получилось, это просто относительная величина: доли, проценты. К тому же простые p и q перепутались, то ли это модули, то ли сами значения, да и ещё буква p с открытым текстом совпадает.

Методом перебора по скачкам в статистике подберём значение первого периода, в котором будет сокращаться в ноль второй период по ксору:

Каждая третья пара шифртекстов будет давать вот такое:

c₍₁₎ ⊕ c₍₃₎ = p₍₁₎ ⊕ p₍₃₎ ⊕ ( k₁₍₁₎ mod 5) ⊕ ( k₁₍₃₎ mod 5)

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

Дальше можно подобрать и второй период.

И вообще, информация или догадка о каждом p_n, k_1(n), k_2(n), mod (X), mod (Y) приближает к разгадке. А уж про наличие возможности криптоанализа с использованием известных или подобранных открытых текстов даже напоминать смешно. Не может линейная функция считаться шифром.

— Гость (27/02/2013 15:34)   

Шифр — всё, что превращает текст в (обратимую) абракадабру. В народе считают как-то так.

— unknown (27/02/2013 15:37)   
Ну раз так:


Не может линейная функция считаться стойким шифром.

— Гость (27/02/2013 15:53)   
Из нестойкости шифра не следует лёгкость его взлома в абсолютно всех ситуациях, из-за чего обывательски считается, что нестойкие шифры имеют право на жизнь. И дело здесь в том, что показать нестойкость шифра намного лечге, чем написать исчерпывающее руководство по оптимальному его взлому во всех возможных ситуациях с чёткими оценками на требование к ресурсам, к количеству нужных пар {текст,шифртекст} и т.д. Т.е. пусть система явно дефектная, но вот как воспользоваться дефектом?^[link4] В современном мире эта проблема решается просто: «нам пофигу на дефектные «шифры», т.к. всюду рекомендуется использовать современные и стойкие, каковые слишком далеки от практичного взлома; тот же, кто использует дефектные, т.е. от практического взлома недалёкие, — ССЗБ».

— unknown (27/02/2013 16:04)   
Криптоанализ любительских шифров^[link5].

— Euler (27/02/2013 16:14)   

Периоды и так известны, это же часть алгоритма шифрования. Вопрос в том как этим воспользоваться. Что толку от этой информации, если мы всё равно будем действовать как при обычном "ксоре" с паролем в 15 символов.

— unknown (27/02/2013 16:33)   
Действуйте^[link6]. :)

При перексоривании символов шифртекстов можно сокращать части эти половинок ключа, т.е. будет видно, что каждый 3-ий фрагмент открытого текста будет эффективно ксориться только одним фрагментов из одной половинки пароля, а каждый 5-ый — только одним из второй половинки.

— Гость (27/02/2013 23:19)   
Пусть открытый текст, который мы хотим зашифровать — вывод ГСЧ. Мы ксорим этот вывод каждый раз с одним и тем же фиксированным паролем (да пусть хоть даже ксорим каждый бит с единицей). Может ли по шифртексту атакующий получить какую-то частичную информацию об открытом тексте? Насколько я понимаю, нет.

— Гость (27/02/2013 23:26)   

И ещё: если считать, что высокоэнтропийные данные непредсказуемы для противника, то ситуация похожа, а высокоэнтропийными они будут после архивации, сжатия и т.д. Получается, что все атаки на XOR в конечном счёте сводятся к связыванию шифртекста с открытым текстом. Конечно, для любого архиватора связь между открытым текстом и архивированным есть (а, следовательно, и между открытым и зашифрованным, по транзитивности), но, чем она сложнее, тем тяжелее анализировать/взламывать такой «шифр». Unknown, как далёк я от понимания?

— unknown (28/02/2013 10:18, исправлен 28/02/2013 10:20)   

Пусть открытый текст, который мы хотим зашифровать — вывод ГСЧ. Мы ксорим этот вывод каждый раз с одним и тем же фиксированным паролем (да пусть хоть даже ксорим каждый бит с единицей). Может ли по шифртексту атакующий получить какую-то частичную информацию об открытом тексте? Насколько я понимаю, нет.

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

Получается, что все атаки на XOR в конечном счёте сводятся к связыванию шифртекста с открытым текстом. Конечно, для любого архиватора связь между открытым текстом и архивированным есть

Берёте огромный словарь не только со словами, но и с часто встречающимися фрагментами тэгов HTML, разметки файловых систем и пр. Архивируете, перебираете.

чем она сложнее, тем тяжелее анализировать/взламывать такой «шифр».

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

Вот ваш тезис примерно таков: "Пусть XOR — слабый шифр, но простейшее преобразование позволяет вычислительно увеличить гамму из ключа в два раза". Без каких-либо теоретических обоснований.

Вам контртезис с примером: "XOR фрагментов шифртекста по известным (или вычисленным) периодам позволяет сократить гамму обратно".

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

— Гость (02/03/2013 05:01)   

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

Согласен, но я не топикстартер. :)
Просто решил слегка уточнить ваши ответы, адресованные ему.

— Гость (02/03/2013 12:05)   
Да человеку коннкретный шифр взломать надо, а вы его теориями кормите :)

— unknown (02/03/2013 19:16)   
А вдруг автор хочет чего-то наподобие этого^[link7]. :)