Как будет взломан алгоритм с генерацией бесконечного ключа шифрования?

Question

[Ярослав]

Правильно ли я понимаю, что невозможно взломать простой xor сообщения и длинного ключа (ключ длиннее чем сообщение)?

Но что будет, если у Alice и Bob вместо конкретного длинного ключа будет некоторый несложный алгоритм, может быть с параметрами, который создает этот бесконечный ключ? Например, упрощенно, ключом пусть будет число Пи (алгоритм вычисления любого знака). Любое первое сообщение (тысяча знаков) xor'им с первой тысячью знаков числа Пи и передаем. Следующее сообщение xor'им со следующими знаками, и так далее.

Eve прослушивает трафик между Алисой и Бобом но ничего не знает про используемый алгоритм и его параметры. При этом Eve очень грамотный и опытный криптоаналитик. Как он может вскрыть такой простой шифр?

(Для усложнения - пусть будет несколько последовательностей, хотя бы pi и e, и какие-то их усложнения, например pi от 1000 знака xor с е от 2000 знака, получаем ключ, которым уже xor сообщение.

Comments

[CityCat4]

Ярославище, осторожнее - математика ест моск! Рискуешь мутировать в Перельмана :)

Answer 1

[mayton2019]

Обычно криптоаналитик знает что ищет.

А что будет если я, (Боб к примеру) прикольнулся и вместо отмысленного сообщения посылаю белый шум? Не известно сколько таких шумных сообщений я посылаю. Алиса предупреждена об этом методе и просто игнорирует первые N сообщений.

P.S. Число Pi в данном случае не удовлетворяет Керхгофсу. Не параметризируется и его сложно менять на что-то новое в случае компрометации.

Comments

[Ярослав]

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

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

[mayton2019]

Ярослав, по поводу замусоривания. Эти все методы давно известны. Есть такой оригинальный который скрывает сам факт шифрования. Стеганография называется. Но у него - другой недостаток. Размер носителя увеличивается в 10-100 раз.

Вот криптография ставит обычно сверх-задачу. Размер шифротекста должен быть равен размеру открытого текста. Здесь - любой симметричный шифр подходит. Но плюс padding на границу блока.

Ну и еще есть куча требований по архитектуре. Типы операций должны быть доступны для всего спектра железа. XOR, SHIFT и AND/OR. И никаких вам синусов и логарифмов. Сами понимаете. Зачем нужен шифроалгоритм который посадит батарейку на вашей блю-тус гарнитуре за 5 минут? Ну и гибкость. Заменил ключ и - это равносильно что заменил на 99% алгоритм. Любой крипто-хакер будет отброшен на начало работ. Всё что этого намайнил - можно выкинуть.

Поэтому доморощенные шифры обычно и не участвуют в конкурсах на созданеи стандарта. Иначе любой-бы школьник накидал синусов и логарифмов и ходил-бы надувая щёки. Дескыть я тоже крипто-эксперт. И число Пи и число "е" и ряды Тейлора не подходят на роль симметричного шифро-алгоритма. Нет гибкости.

По поводу Пентагона. Я думаю что его агенты такой фигнёй не занимаются. Они либо ставят вам в телефон приложение типа Пегасус. Причем вы не заметите как. Ибо - глобализм и корпорации. Власть - в тесной дружбе с последними. Либо просто берут вас под белы ручки и ведут в тюрьму возле Кубы. Где вам оказывают очень горячий приём. А против таких методов обычно криптография не работает. Она получается - как математика. Работает только в условиях чистых. Алиса Боб и Кларк. Короче сплошные абстракции.

Answer 2

[Николай Савельев]

Это классический "security through obscurity".
Зная алгоритм такого шифрования его легко взломать

Comments

[Ярослав]

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

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

Answer 3

[shurshur]

Если есть алгоритм генерации бесконечного ключа K(n) (n - порядковый номер элемента ключа) с заданными параметрами, взломщик будет перебирать значения параметров, пытаясь применять сгенерированный ключ к шифрованному тексту. Полученное проверяется на текстовую валидность. Когда получится нормальный естественный текст - ключ взломан.

Например, пусть параметры p и q, алгоритм K(n)=p^n mod q, тогда взломщик просто устроит перебор значений (p; q) от (0; 0) до бесконечности.

Или пусть алгоритм будет K(n)=цифра числа пи "n+p", где p - параметр ключа. Тогда будем делать перебор значений p. Это будет довольно быстро, ведь нам надо будет просто последовательно генерировать цифры числа пи, помнить последние $длина_шифротекста символов и проверять их применимость как ключа.

Более того, если мы не знаем, использует ли наша жертва цифры числа пи или дискретную степенную функцию, мы можем проверять обе версии параллельно, атакуя оба варианта генерации ключа. И даже три или 10 вариантов генерации ключа.

Собственно, чтобы подобный алгоритм имел хоть какой-то смысл, надо, чтобы поиск этих самых параметров p и q был безумно сложным. Если можно проверять миллион вариантов ключа в секунду, то для криптостойкости потребуется, чтобы требовались даже не миллиарды, а как минимум триллионы секунд перебора. Ведь миллиард секунд - это жалкие 8 лет, если взять тысячу вычислителей, то 8 лет превратятся в месяц. а при 30 тыс. - в сутки.

Любой дискретный шифр с известным или предполагаемым алгоритмом ломается перебором. Даже хрестоматийный весьма стойкий RSA ломается. Защита данных дополнительно обеспечивается сменой ключа, алгоритмами Диффи-Хеллмана, реализацией PFS итд итп.

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

Answer 4

[Владимир Дубровин]

Такой подход нарушает принцип Кергофса. Взломать ваш алгоритм можно двумя способами:
1. Подобрав алгоритм генерации, это можно сделать, например, перебирая функционалы составляющие функцию вашего алгоритма.
2. В вашем варианте алгоритм к тому же не устойчив к known plaintext атакам. Предположим Алиса передает Бобу сообщение которое известно атакующему - тогда зная это сообщение и проксорив его с "шифрованым" текстом можно получить сгенерированную последовательность и в дальнйшем дешифровать любое сообщение, поэтому в современные алгоритмы обязательно вносится обратная связь и/или какой-нибудь nonce.

P.S. предположу, что вы пытаетесь переизобрести потоковый шифр