Ламерский вопрос про шифрование

[aterentiev]

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

Comments

[ex0_planet]

Как всё запущено....

Там _в_любом_ случае будет брутфорс, стойкость алгоритма в том, чтобы найденные уязвимости (способы сократить перебор) не сокращали перебор слишком сильно. Как было с DES например, когда придумали как перебрать его не за 2^32, а за 2^22, а потом и 2^16 итераций. Как _твоя_ схема себя поведет при подобных атаках - неизвестно. Возможно, второй слой добавит 20-30 порядков итераций перебора, а возможно только 2-3.

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

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

А, и да. Если настойчиво просят вмандить что-нибудь наколеночное вместо того чтобы поставить нормальный контроллер с нормальным AES, то вот какое соображение: лучше потерять работу вследствие разногласий с начальством, чем потерять её же будучи ответственным за рекламации от клиентов.

[dibr]

Я не очень понимаю, как брутфорсить то, что ты не знаешь. Может там каждый пятый байт на единицу увеличивается, может каждый третий - xor'ится с числом 13, а может каждый чётный, кроме тех, позиции которых делятся на 72 и 196, складывается с числовыми значениями символов закольцованного слова "xyz~=", уменьшается на 1/3 номера своей позиции с инвертированными 7 и 3 битом, и меняется местами с соседом справа. Каким образом можно алгоритмически перебрать все виды "детсадовских" шифров, при условии что это только верхний слой, и то что под ним тоже нужно брутфорсить?

[ex0_planet]

Нормальный (а не курильщика) криптоанализ подразумевает что весь алгоритм известен снизу доверху.

[dibr]

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

Если "детсадовский" алгоритм так или иначе обнародуется, тогда в нём конечно нет смысла. Суть именно в security by obscurity, и в том что расшифровщик не знает, о чём мы c будущим корреспондентом шептались в лесу месяц назад.

[ex0_planet]

Очень сложно "не обнародовать" алгоритм в современных условиях, потому что при нужде его вытащат из любой железки.

Потом, наивные алгоритмы чаще всего выявляются анализом статистики. Их можно постепенно усложнять, но так мы постепенно придем к сильному алгоритму. Да, возможно, посередине есть sweet spot где и алгоритм не чересчур тяжелый, и секурность хорошая, но ответить на этот вопрос не будучи математиком-криптографом с NNN лет опыта довольно сложно :)

Из совокупности практических соображений я бы предложил все же не выпендриваться и слушать песню «Валенки» имплементировать AES-128/256.

[nlothik]

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

[dibr]

Секундочку:

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

2) повторю вопрос: "я не очень понимаю, как брутфорсить то, что ты не знаешь". Как в принципе алгоритмизировать перебор алгоритмов, пусть даже алгоритмы "детсадовские" - как должна быть устроена программа взлома/перебора, чтобы в принципе добраться до алгоритма "каждый чётный, кроме тех, позиции которых делятся на 72 и 196 [и так далее]"?

[nlothik]

> 1) слабый ("детсадовский") алгоритм у нас сверху, под ним - стандартный, но взламываемый брутфорсом (с коротким ключом).

Вот тут уже да, разговор немного другой.

Не знаю, как насчёт симметричного шифрования. По-быстрому нарисовал RSA, и да, расшифровав назад изменённый шум получил обратно тоже шум. Симметричный алгоритм я на коленке уже не нарисую, так что ничего ответить не могу :)

> как должна быть устроена программа взлома/перебора, чтобы в принципе добраться до алгоритма "каждый чётный, кроме тех, позиции которых делятся на 72 и 196 [и так далее]"?

Ну, любой повторяющийся ключ ломается. Все эти initialization vector, padding, cbc и прочие умные слова были придуманы именно для того, чтобы не повторять ключ.

Я в своё время в университете рисовал прогу для ломания шифрования заменой с повторяющимся ключом. С условием что было известно, что дешифровываем мы английский текст. Каким именно образом осуществляется замена -- через сдвиг или через XOR, в принципе, не так важно.

Через статистический анализ, конечно. Подобный метод шифрования будет детерминистическим -- т.е. одна и та же буква всегда будет шифроваться одним и тем же шифротекстом. Введя условия типа "каждая вторая буква" ты, конечно, немного замутишь воду, но КМК при достаточно большом тексте можно вполне будет анализировать и это. Например, самая часто встречающаяся буква в английском тексте -- e. Значит, надо искать те символы, которых в твоём шифротексте больше всего, и получится, что чаще всего там будет две буквы -- например, n если это нечётная e, и q если чётная. Как-то так я и действовал.

[dibr]

> Ну, любой повторяющийся ключ ломается

Оценил длину повторения последовательности из своего комментария (плюсуем 1/3 номера своей позиции, кроме тех, позиции которых делятся на 72 и 196, плюс зацикленное ключевое слово из 5 букв), получил 564480 байт (256*3 от "позиции/3", ещё 3 из множителей 72, 7*7 из множителей 196, и 5 из длины ключевого слова). Ломаем перебором? :-) А ведь это я чисто как пример придумал, константы и методы специально не подбирал.
При этом я сразу вспомнил про возможность нарисовать на коленке генератор псевдослучайных чисел и использовать его, мне просто было лениво это делать. Если потратить несколько минут на создание такого генератора и подбор констант чтобы он не зацикливался совсем уж сразу, думаю длину повторения можно легко догнать до миллионов, если не миллиардов, байт. При этом реальный "ключ" - константы генератора - как бы небольшой, но взломщик не знает _алгоритм_, т.е. алгоритм в каком-то смысле является частью ключа, а длина повтора - ну уж вот такая вот.

Ну и осталась не раскрыта тема "...и меняется местами с соседом справа" из того же алгоритма. Как алгоритмизовать подбор таких вот - тривиальных - штучек? А их - штучек - может быть несколько.

> Через статистический анализ, конечно. Подобный метод шифрования будет детерминистическим

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

> Например, самая часто встречающаяся буква в английском тексте -- e

Ва-ау! Как всё просто, и как я сам не догадался!!!
А какая самая часто встречающаяся буква в AES-128? Пойду ломать, рассказ "золотой жук" у меня есть, больше получается ничего и не надо :-)

[nlothik]

> Оценил длину повторения последовательности из своего комментария (плюсуем 1/3 номера своей позиции, кроме тех, позиции которых делятся на 72 и 196, плюс зацикленное ключевое слово из 5 букв), получил 564480 байт (256*3 от "позиции/3", ещё 3 из множителей 72, 7*7 из множителей 196, и 5 из длины ключевого слова). Ломаем перебором? :-) А ведь это я чисто как пример придумал, константы и методы специально не подбирал.

Почему перебором? Статистическим анализом. При наличии достаточного количества нагенерённого таким алгоритмом траффика (если таким, например, вайфай кодировать) -- достаточно тривиальная задача. Собственно, WPA2 именно через повторение ключа и поломали, хотя там внутри вообще-то полноценный AES.

> При шифровании "символ-в-символ" шум на входе преобразуется в шум на выходе.

Это да, я с этим не спорю. Просто в связке AES+тривиальный алгоритм силу подобному шифрованию даёт именно AES, а без него тривиальному алгоритму жить недолго.

[sakurovskiy]

//Я не очень понимаю, как брутфорсить то, что ты не знаешь.

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

Я проходил курс на курсере по криптографии, там это все разбирается, и порицается "доморощенная" криптография, из-за уязвимостей.

[dibr]

> сильно сомневаюсь что ваш алгоритм выдаст белый шум

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

> порицается "доморощенная" криптография, из-за уязвимостей

Конечно порицается - в большинстве практических случаев взломщик имеет доступ к алгоритму (он описан в протоколе, или есть доступ к железке/программе), взломать надо только ключ, а к этому "домашние" алгоритмы не готовы. Если же "Юстас" договорился об алгоритме с "Алексом", и они никому-никому об этом не говорят - то...

[sakurovskiy]

Понял. Вы зашифрованное одним алгоритмом, берете и шифруете еще раз?

Да дело осложняется. Тут уж как повезет - можно предполагать алгоритмы и пробовать.

//Конечно порицается

Порицается из-за уязвимостей. Доморощенная криптография на алгоритмах Юстаса-Алекса ломается намного проще, чем промышленные стандарты ссл, AES и такое прочее.