Под катом я изложу идеи для подобных алгоритмов и обещаю, что они будут посложнее обыкновенного XOR с фиксированым ключом. На всякий случай обращаю внимание на то, что эти алгоритмы не претендуют на звание криптостойких, но уверен, что вы сможете найти им применение.
Предпосылки
Предполагается, что потенциальный взломщик либо не имеет доступа к коду, который осуществляет шифрование, либо не имеет достаточной квалификации для реверс-инжениринга, либо данные не настолько ценны, чтобы тратить время на более тяжёлые методы взлома.
Наверно все знают, что в подобных случаях чаще всего применяют простое циклическое наложение ключа фиксированой длины с помощью операции XOR. И все так же хорошо знают, что такая защита не выдерживает даже начинающего «хакера» или продвинутого пользователя. Хотелось бы что-нибудь посложнее, но простое в реализации.
А если генерировать ключ?
Первое, что приходит в голову, это генерировать достаточно длинный ключ, чтобы хотя бы усложнить нахождение длины ключа. Например, использовать некий генератор псевдослучайных чисел с входными данными, известными и отправителю, и получателю. Один из таких часто применяемых генераторов — линейный конгруэнтный ГПСЧ (ГСПЧ это генератор псевдослучайных чисел). Мы, конечно, догадываемся, что это плохо, но что же именно плохо в этом подходе? Проблема в том, что довольно трудно генерировать параметры для самого генератора. Программно подобрать хорошие параметры для линейного конгруэнтного ГПСЧ, чтобы последовательность была длинная и невырожденая, довольно трудно. По этому поводу можно почитать в 3.2.1 в книге Д.Кнута «Искусство программирования». Поэтому зачастую эти параметры вколачивают в код как константы и, как следствие, потенциальный взломщик получает множество сообщений зашифрованых с одним ключом, что значительно упрощает его работу.
А что если использовать сами данные для генерации этой псевдослучайной последовательности?
Эта идея осенила меня лет 20 назад, когда я «помогал» писать диплом одной моей знакомой студентке. На первый взгляд кажется, что это невозможно, ведь нам нужен генератор, который выдавал бы одинаковую последовательность и при шифровке, и при расшифровке. Как ни странно, именно этот «убийственный» тезис и даёт нам путь к созданию такого генератора. Да, нам нужен алгоритм, который меняет значения своих внутренних переменных одинаково, если ему дать исходный байт (или что там у нас является атомарной единицей кодирования) и зашифрованый байт. Как этого достичь? Всё гениальное просто — для вычисления следующего значения ключа можно задействовать коммутативные операции для пар исходных-шифрованых байт. Так как результат операции не зависит от порядка операндов в паре, то очевидно, что такой алгоритм будет менять свои переменные при расшифровке точно так же как и при шифровке, но последовательность ключей для других входных данных будет другой.
Пример генератора ключей, зависящего от входных данных
Чтоб было понятней, рассмотрим простенький пример такого алгоритма.
Пусть xn — это очередной код в исходных данных, kn — текущий ключ, kn+1 — следующее значение ключа, yn — зашифрованый код xn.
Q(a,b) — некая коммутативная функция, т.е. такая, что q(a,b)==q(b,a).
F(a,b,c) — некая целочисленная функция.
Toгда итерацию по (де)кодированию можно описать так:
yn := xn xor kn;
kn+1 := F( kn, Q( xn, yn ), n );
Если для функции F() понятно, что её имплементация в общем-то ограничена лишь нашей фантазией и здравым смыслом, то про Q(), вероятно, вам хочется увидеть подробностей, а именно, каким таким условиям она должна соответствовать, чтобы быть коммутативной. Самый простой способ этого достичь — использовать аргументы только парами в коммутативных операциях, например xor, сложение, умножение. Примеры:
Q(a,b) = a xor b. (Исправлено: пожалуй я тут погорячился, ведь при наложении исходного и зашифрованного кода получается ключ, что нежелательно. Я лично использую немного более сложные функции).
Q(a,b) = ((a xor b) or 1) * (( a + b ) xor 1).
Как видите, придумать свою супер-пупер функцию Q() совсем не сложно. Другое дело, нужно ли её делать сложной? Думаю, что особого смысла в её переусложнении нет.
Ну а теперь-то что плохо?
Да, не зная кода функции кодирования, прочитать что-либо будет весьма затруднительно. Но какие зацепки всё-таки остаются? Если входные параметры для скремблера будут одинаковыми, то
- Если два сообщения начинаются с одних и тех же данных, то и начало зашифрованых данных будет абсолютно одинаковым;
- Ключ для первого кода одинаков;
- Длина зашифрованного сообщения точно совпадает с длиной исходного сообщения.
Как с этим бороться, но не положить свою молодую жизнь? Конечно, способов борьбы может быть много, но хочется дёшево и сердито, есть ли такие? У меня есть несколько идей на этот счёт.
Чтобы побороть первые два пункта, есть очень простой, но эффективный приём. При шифровании перед каждым сообщением вставляйте случайные данные. Достаточно даже одного байта(кода). Так как следующий ключ зависит от данных, то даже для одинаковых сообщений мы получим разные последовательности ключей. Получателю нужно просто отбрасывать этот префикс после расшифровки сообщения.
Для борьбы с третьим пунктом можно добавлять случайные данные до и/или после сообщения.
А ещё идеи есть?
А то! У меня всегда есть идеи!
Допустим вы передаёте данные в сжатом виде. Или данные уже частично зашифрованы. Или каждое сообщение/блок достаточно длинные и состоят из двоичных данных с примерно равномерным распределением кодов. В этом случае любое вмешательство в порядок кодов в сообщении может существенно усложнить жизнь потенциальному взломщику. Уверен, что вы можете и сами придумать некий примитивный перемешиватель байтов в блоке данных, но я ведь обещал интересные и красивые идеи.
Перемешиватель данных (shuffler)
Обычно для решения этой задачи используют некий ГСПЧ для получения пар индексов кодов в блоке данных, которые меняют местами. Неприятность этого метода в том, что трудно гарантировать, что какая-то часть данных не останется на том же месте. Также не совсем понятно, сколько же перестановок нужно сделать, чтобы достичь приемлемого результата, хотя для надёжности можно просто пройтись по всем кодам сообщения и обменять каждый со случайным. Но есть ещё одна неприятность — если генератор имеет плохое распределение по квадрату (а линейный конгруэнтный именно такой болезнью и болеет, и причём безнадёжно), то при определённых размерах блока можно нарваться на зацикливание выдаваемых значений. Я довольно долго шёл к идее быстрого псевдослучайного перемешивателя данных (shuffler) и считаю, что она заслуживает вашего внимания не только как алгоритм для скремблирования.
Немного теории. В пункте 3.2.1.2 книги Д.Кнута «Искусство программирования» можно найти критерии для выбора множителя для линейного конгруэнтного генератора, чтобы длина генерируемой последовательности равнялась модулю. Что это означает? Это значит, что для генератора с модулем m каждое значение от 0 до m-1 будет выдано ровно один раз. Зачем это нам? Вспомним, что для нашего перетасовщика было бы желательно гарантировать, что все байты(коды) сообщения поменяли своё место. То есть, если длина данного блока данных равна этому самому m, то нам будет достаточно просто записывать очередной входной байт(код) сообщения в выходной буффер по индексу, равному очередному значению из генератора. Простота этого алгоритма настолько сооблазнительна, что я не мог пройти мимо.
Но, как всегда случается с чем-то сооблазнительным, не обошлось без проблем. Во-первых, не все m одинаково полезны хороши. Из той же главы той же книги мы видим, что если m является произведением простых чисел в первой степени, то полного перебора элементов мы достичь не можем в принципе (не считая перебора подряд, что нам, конечно, не интересно). Получается, что получить нужный нам генератор с заданной длиной последовательности нельзя, и, следовательно, если у нас сообщения произвольной длины, то мы не всегда можем найти такой генератор. Тупик? А действительно ли нам нужны генераторы произвольной длины? Вспомним о том, что для потенциального взломщика знание длины сообщения очень даже небесполезно. Тогда мы уже знаем и способ борьбы, который мы успешно применяли для генератора, зависящего от входных данных. Правильно, надо подбросить случайный мусор, и лучше всего перед полезными данными. Правда, есть проблема в том, что в каждом блоке нужно как-то указывать количество полезной информации в нём. Если же в вашем случае длина всех сообщений/блоков данных фиксирована, то вы вы можете зафиксировать и m — выбрать первое удобное для вас значение, которое больше длины входного блока и удовлетворяет критерию из теоремы A из 3.2.1.3 из книги.
Теперь о самом критерии для параметров генератора xn+1=(a*xn+c) mod m:
- c и m взаимно просты;
- a — 1 кратно p для всех простых делителей p числа m;
- a — 1 должно быть кратно 4, если m кратно 4.
Как бы этого достичь малой кровью? Я предлагаю такой вариант:
m = 2n, где n>3;
с = p, p — простое число & p>2;
a = 4*k+1.
Как легко заметить, все три условия выполняются и такие значения довольно легко подобрать.
Ещё идеи?
Довольно очевидна идея объединить shuffler и генератор, зависящий от данных. Для этого мы сначала скармиваем генератору нужное количество мусора, чтобы подогнать длину сообщения под размер блока shuffler`а, а потом уже прогоняем данные самого сообщения. Все выходные коды пишем по индексам, которые получаем от shuffler.
Распечатать статью