xenon
@xenon
Too drunk to fsck

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

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

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

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

(Для усложнения - пусть будет несколько последовательностей, хотя бы pi и e, и какие-то их усложнения, например pi от 1000 знака xor с е от 2000 знака, получаем ключ, которым уже xor сообщение.
  • Вопрос задан
  • 430 просмотров
Пригласить эксперта
Ответы на вопрос 5
@AlexVWill
При этом Eve очень грамотный и опытный криптоаналитик. Как он может вскрыть такой простой шифр?

Брутфорсом. Да, взломщик не знает какой именно алгоритм используется, но если есть именно АЛГОРИТМ генерации ключа (а не некая псевдослучайная величина), то поиском последовательности символов можно найти ключ. Т.к. алгоритмы генерации числа пи, числа Эйлера (e) и подобных иррациональных чисел известны.
Ответ написан
@mayton2019
Bigdata Engineer
Обычно криптоаналитик знает что ищет.

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

P.S. Число Pi в данном случае не удовлетворяет Керхгофсу. Не параметризируется и его сложно менять на что-то новое в случае компрометации.
Ответ написан
AgentSmith
@AgentSmith
Это мой ответ на твой вопрос
Это классический "security through obscurity".
Зная алгоритм такого шифрования его легко взломать
Ответ написан
shurshur
@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 такая же фигня. С нормальными шифрами это, разумеется, не прокатывает.
Ответ написан
Комментировать
Такой подход нарушает принцип Кергофса. Взломать ваш алгоритм можно двумя способами:
1. Подобрав алгоритм генерации, это можно сделать, например, перебирая функционалы составляющие функцию вашего алгоритма.
2. В вашем варианте алгоритм к тому же не устойчив к known plaintext атакам. Предположим Алиса передает Бобу сообщение которое известно атакующему - тогда зная это сообщение и проксорив его с "шифрованым" текстом можно получить сгенерированную последовательность и в дальнйшем дешифровать любое сообщение, поэтому в современные алгоритмы обязательно вносится обратная связь и/или какой-нибудь nonce.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы