Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 34
Криптографические алгоритмы так не пишутся. Сходу могу сказать, что у вас будет сохраняться статистика символов в больших блоках, что уже очень плохо.
«И тогда мой мозг понесся думать про XOR-шифрование. Оно ведь довольно простое, а я думал, как можно его улучшить.» — алгоритм XOR-шифрования (или, более канонично, шифр Вернама), несмотря на свою простоту, является абсолютным шифром (скорее всего единственным таковым) — в случае одноразовых равновероятных ключей длиной с само сообщение. А ваш шифр вообще из категории шифров перестановки, не понимаю как его можно считать «улучшенным» шифром Вернама.
Я думал о том, что можно подобрать часть ключа — и тогда уже будет видна часть сообщения, если применить этот ключ на сообщение. Следовательно, если использовать перемешивание — будут видны лишь отдельные куски сообщения, а не подряд несколько кусков сообщения.
Все существующие шифры перестановки с легкостью взламываются с помощью компьютера. Ваш шифр неплохо бы пошел на школьную олимпиаду по криптографии, не больше.
И как же взламывают, например, псевдослучайные перестановки из 4096 элементов (хотя бы основная идея)?
Чистые шифры перестановок очень чувствительны к избыточности исходного сообщения. Их надежность падает экспоненциально при уменьшении энтропии относительно максимальной. Простейший пример — сигнатуры файлов в которых положение определенных байт известно — позволяет уменьшить n! до (n-k)!.. Также известны вероятностные распределения символов для естественных языков — можно использовать любую избыточность.
Да, конечно, можно использовать алгоритмы сжатия и другие преобразования, увеличивающие энтропию или преобразовывающие известное распределение в неизвестное — но это уже комбинированный шифр, а в их составе перестановки вполне имеют место.
Да, конечно, можно использовать алгоритмы сжатия и другие преобразования, увеличивающие энтропию или преобразовывающие известное распределение в неизвестное — но это уже комбинированный шифр, а в их составе перестановки вполне имеют место.
Насчет легковзламываемости имелось ввиду — при сопоставимой длинне ключа с другими шифрами. Перестановочные шифры имеют значительно худшие храктеристики в равных условиях.
4096 перестановка — ключ размера 43250.046889935249 бит. Сравните с AES 256 бит ключа. Даже 128 бит AES на практике не взламывается, хотя считается в перспективе не надежным.
4096 перестановка — ключ размера 43250.046889935249 бит. Сравните с AES 256 бит ключа. Даже 128 бит AES на практике не взламывается, хотя считается в перспективе не надежным.
128 бит — это примерно перестановка 34 элементов. Как она ломается описанным выше способом — надеюсь понятно.
Анаграмма из 34 букв? Не знаю. Иногда и над 15 приходится долго думать. Если известно, на каком языке, в голову приходит анализ вероятностей пар-троек символов. Но найти кратчайший путь без циклов в нагруженном ориентированном графе (максимизировать вероятность пар символов) — это же задача коммивояжера! NP, однако.
Файл внутри PE exec — знаем, что первые два байта MZ/PE, узнаем первые два символа перестановки, перебор сокращается в 1122 раз.
Статистическое распределение символов внутри перестановка сохраняет — можем узнать тип содержимого, проанализировать условные вероятности последовательностей символов — энтропия английского текста на уровне 1-1.5 бит на символ, следовательно корреляционная атака сократит ключ еще раз в 6-8. А там и перебирать останется совсем капли.
Вот еще пример бинарного файла, выбрал что побольше:
$ ent /usr/bin/emacs
Entropy = 4.189078 bits per byte.
Optimum compression would reduce the size
of this 10803128 byte file by 47 percent.
Chi square distribution for 10803128 samples is 859695276.68, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 56.3785 (127.5 = random).
Monte Carlo value for Pi is 3.784757856 (error 20.47 percent).
Serial correlation coefficient is 0.470131 (totally uncorrelated = 0.0).
обратите внимание на последнюю строку — она как раз показывает автокорреляцию данного файла, т.е. отклонение от равновероятностьи различных последовательностей символов. Даже не зная информацию о содержимом, это можно использовать в корреляционной атаке.
Статистическое распределение символов внутри перестановка сохраняет — можем узнать тип содержимого, проанализировать условные вероятности последовательностей символов — энтропия английского текста на уровне 1-1.5 бит на символ, следовательно корреляционная атака сократит ключ еще раз в 6-8. А там и перебирать останется совсем капли.
Вот еще пример бинарного файла, выбрал что побольше:
$ ent /usr/bin/emacs
Entropy = 4.189078 bits per byte.
Optimum compression would reduce the size
of this 10803128 byte file by 47 percent.
Chi square distribution for 10803128 samples is 859695276.68, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 56.3785 (127.5 = random).
Monte Carlo value for Pi is 3.784757856 (error 20.47 percent).
Serial correlation coefficient is 0.470131 (totally uncorrelated = 0.0).
обратите внимание на последнюю строку — она как раз показывает автокорреляцию данного файла, т.е. отклонение от равновероятностьи различных последовательностей символов. Даже не зная информацию о содержимом, это можно использовать в корреляционной атаке.
В русском тексте даже анализ вероятностей четверок символов дал мне объем информации в 3.2 бита на символ — этого не хватило, чтобы разложить посимвольную сумму двух текстов на слагаемые. Как можно получить 1-1.5 бита?
Из википедии: en.wikipedia.org/wiki/Entropy_(information_theory)
The entropy rate of English text is between 1.0 and 1.5 bits per letter, or as low as 0.6 to 1.3 bits per letter, according to estimates by Shannon based on human experiments.
Анализ последовательностей символов — это автокорреляция.
The entropy rate of English text is between 1.0 and 1.5 bits per letter, or as low as 0.6 to 1.3 bits per letter, according to estimates by Shannon based on human experiments.
Анализ последовательностей символов — это автокорреляция.
У псевдослучайной перестановки ключ может быть любым (хоть 32 бита) — он подается на вход RND:
seed=key;
for(int i=len;--i>0;) swap(&arr[i],&arr[irand(i+1)]);
seed=key;
for(int i=len;--i>0;) swap(&arr[i],&arr[irand(i+1)]);
ГПСЧ не берут энтропию из воздуха — она берут ее только из ключа. Если вариантов ключа меньше, чем перестановок, ключами будет только подмножество всех возможных перестановок мощности 2^размер_ключа
О чем я и говорю. Можно взять те же 128 бит — и получить эквивалентный по ключу шифр. И сортировать 13-битные блоки (а не байты), но это уже извращение. Проще уж XOR с результатом RND. Неожиданностей меньше.
Расширение ключа как одна из операций комбинированного шифра используется, и часто помогает его улучшить, но это опять же наворачивание дополнительных улучшений на исходный шифр перестановки.
Сложность атаки будет примерно = сложность_атаки_на_шифр_перестановки * сложность_атаки_на_ГПСЧ, использованный при расширении ключа.
Сложность атаки будет примерно = сложность_атаки_на_шифр_перестановки * сложность_атаки_на_ГПСЧ, использованный при расширении ключа.
И это в случае если комбинация процедуры расширения ключа и исходного шифра будет надежной и не породит новых уязвимостей, или их еще не обнаружат при криптоанализе, так как они всегда есть в таких комбинациях и теоретически позволяют свести сложность атаки на комбинированный шифр до максимума из этих двух сложностей.
Ну уж извините, в тщетных попытках уснуть лучшего в голову не пришло! Я просто решил написать о том, что я думал, так как нигде ничего похожего я не нашёл.
Не злитесь, это слова человека, которому пять лет в университете вдалбливали криптографию. А хабр — не личный бложик, чтобы постить на него все что в голову пришло, невзирая на полезность и адекватность пришеднего. Я же не лезу на CNN вещать свои дилетантские мысли на тему экономики.
Пять лет криптографии в универе? Простите, можно узнать, что это за ВУЗ?
Просто интересно.
Просто интересно.
Томский государственный. А под криптографией я имел ввиду «основы криптографии» и «введение в компьютерную безопасность» на первом курсе, «теория чисел в криптографии» на втором, «криптографические методы защиты информации» на третьем, «булевы функции в криптографии» на четвертом и «криптографические протоколы», «аппаратная реализация криптоалгоритмов», «конечно-автоматные криптосистемы» и «квантовая криптография» на пятом. Очень подробные курсы, с обширной теорией и практикой.
www.fpmk.tsu.ru/entrance/directions/
www.fpmk.tsu.ru/entrance/directions/
… чтобы постить на него все что в голову пришло, невзирая на полезность и адекватность пришеднего.
Хм… зачем же так строго?) Да конечно перед публикацией все же надо хорошо обдумать все, проверить корректность решения и пр. Но ведь все не просчитаешь, порой нужен свежий взгляд со стороны. Уверен что как статья так и комментарии к ней будут полезны как автору так и многим другим.
Не могу промолчать — читайте матчасть, друзья!
Криптография это наука, иногда похожа на алхимию — но так бывает…
Криптография это наука, иногда похожа на алхимию — но так бывает…
Возможно, с точки зрения криптографической науки этот алгоритм слабый. Действительно, мы видим буквы из фразы «Hello World» и можем догадаться, что было написано. Если перемешивать битовые строки некратные байту (или юникод), то внешне строка станет нечитаемой. Но самое главное, этот алгоритм красив и может использоваться для каких-то иных целей кроме серетной передачи информации. Может быть для формирования тестовых последовательностей или обработки видео. Надо просто запомнить его и применить в своей задаче.
Сравните его с сетью фейстеля.
Не понял при чем здесь XOR.
Не понял почему это шифрование.
Да, в широком смысле шифрование это «способ преобразования открытой информации в закрытую, и обратно.». В данном алгоритме нет ключа шифрования, а согласно одному из принципов криптографии сам алгоритм не может быть секретным. У вас что-то вроде функции хеширования. Но если ваша функция обратима (я не проверял на обратимость), то это даже не хеширование.
Не понял почему это шифрование.
Да, в широком смысле шифрование это «способ преобразования открытой информации в закрытую, и обратно.». В данном алгоритме нет ключа шифрования, а согласно одному из принципов криптографии сам алгоритм не может быть секретным. У вас что-то вроде функции хеширования. Но если ваша функция обратима (я не проверял на обратимость), то это даже не хеширование.
Ну вас и плющит с недосыпу…
Совет по поводу реализации данного алгоритма на С++:
Не всегда правильно/логично, с точки зрения проектирования, все реализовывать через классы. В данном случае считаю что логичнее было бы реализовать в виде функций. Да понимаю, что обычно всегда есть тяга к «объектности», но просто не всегда она уместна)
Не всегда правильно/логично, с точки зрения проектирования, все реализовывать через классы. В данном случае считаю что логичнее было бы реализовать в виде функций. Да понимаю, что обычно всегда есть тяга к «объектности», но просто не всегда она уместна)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мысли перед сном: алгоритм фрактального перемешивания