UPD. Эта версия обладает недоработками и даже парочкой уязвимостей. Новая, более безопасная версия скоро будет доступна.
Под конец школы я стал увлекаться информационной безопасностью, шифрованием, и всем подобным. Стал изучать существующие алгоритмы шифрования, начиная с шифра Цезаря и заканчивая роторами Энигмы. Узнал, что большинство алгоритмов перестановки - полная фигня, потому что частотный анализ позволяет с лёгкостью опознать исходные данные, и я захотел придумать что-то своё, что может бороться с частотным анализом, при этом являясь алгоритмом перестановки. Не знаю, зачем, не знаю, для какой цели. Никто бы не стал его использовать, да и криптостойкость наверняка была бы ужасна. Просто хочется быть радостным, что смог что-то придумать сам. Ну и на уроке английского придумал алгоритм, где на матрице надо найти соответствующую букву или байт, и определённым способом сместиться по этой матрице, выбрав другую букву или байт. После каждой буквы или байта - смещаться нужно было уже по-другому. Получилась некая Энигма. Из плюсов - одинаковый набор символов или байтов подряд (например: FFFFFFFF или 00000000) кодировались во множество непредсказуемых символов (A7105261 или 9321FDC7), а так же у алгоритма была особенность - у него были режим шифрования и расшифровки, что, в теории, усложняло определение ключа и исходных данных (потому что "дешифровка" на исходные данные тоже являлась шифрованием), иначе говоря - у алгоритма была направленность. Ещё, алгоритм можно было усложнять и изменять под свои нужны при помощи изменения выбора символа или самой таблицы. Из минусов - очень медленная скорость работы, и если данные повторяются слишком часто (например - 256 мегабайт нулей, начало .wav файла или просто структурированные данные), то становились явными повторения.
Это проблема «длины ключа». Если она не больше, чем шифруемые данные — избежать повторений не выйдет, только отсрочить за счёт усложнения алгоритма. И недавно, когда я рассказывал про этот алгоритм своему знакомому, вспоминал детали, плюсы и минусы - в голову пришла мысль: а что, если попытаться решить и эту проблему? Сделать ключ равным длине данных? А разве такое возможно?
Я тут же догадался применять хэш-функции. Пускай она генерирует в зависимости от места в данных ещё один хэш для этого места. Тогда получается бесконечный набор хэшей - их можно использовать как ключ шифрования, явно превышающий почти любой не бесконечный набор данных!
Я начал продумывать этот новый алгоритм, и вскоре придумал это:
На вход подаётся парольная фраза и данные в виде байтов. Данные разбиваются на чанки, равные размеру хэша (У SHA-256 это 32 байта). Для каждого чанка формируется свой хэш: (Парольная фраза или хэш парольной фразы)+(Номер чанка) Затем, чанк делает XOR с этим хэшем.
Такая модель позволяет распараллеливать процесс "обработки" (из-за XOR не совсем неправильно называть процесс шифрованием или дешифрованием, поэтому я называю его "обработкой"). Например - седьмой поток процессора может обрабатывать каждый седьмой чанк из количества потоков, четвёртый поток - каждый четвёртый из количества потоков. Ещё, для ускорения, можно использовать аппаратные ускорители вычисления хэшей.
У алгоритма нет повторений в зашифрованных данных. Проверено на файле весом 2 гигабайта, полностью состоящем из букв "А". (Я даже не вижу здесь возможных вариантов с зацикливанием хэша, он тут невозможен).
Скорость шифрования, возможно, оставляет желать лучшего - 1 гигабайт за 55 секунд на одном потоке процессора с частотой 2.5 GHz, но опять же - её можно существенно ускорить, добавляя многопоточность, выбирая другие алгоритмы (SHA-128 быстрее, но требует больше чанков) и уменьшая затраты на передачу данных между основной программой и функцией.
Чтобы доказать хорошую криптостойкость алгоритма - нужно покопаться в возможных математических бэкдорах хэш-алгоритмов, потому что остальных слабых мест я пока что не вижу. Размышления о том, как можно расшифровать зашифрованные данные без знания ключа довольно сложны... В теории, если взять один чанк, перебирать XOR'ы, и получить более-менее правдивые данные, таким образом примерно узнав хэш чанка, а затем попытаться провести обратный хэш‑алгоритм на этот хэш (практически невозможно, если не составить огромную таблицу для перебранных байтов), и попытаться получить что‑то типа исходной строки «что‑то + номер чанка», то можно узнать это «что‑то», добавить другой номер чанка, хэшировать, и проверить на другом чанке. Но в теории, благодаря хэш‑коллизям, совпадения можно оправдывать случайным совпадением, так как, в теории, возможен такой «основной ключ», который при обработке каждого зашифрованного чанка выдаст любой желаемый результат той же длины. (Пускай вероятность и меньше, чем что-либо в этой вселенной, но не равна нулю).
Для наглядной демонстрации, я написал программу на чистом Си и выложил в своём репозитории. Пока что написана только для Linux (лень ставить винду и настраивать всё для компиляции и тестов), требует наличие библиотеки IUP (Не понял как собрать static версию, памагите).
Разумеется, этот алгоритм очень напоминает современные алгоритмы, проверенные временем, и более быстрые, так что я не претендую на то, что этот алгоритм стоит использовать. Скорее - просто изучить ради интереса. Кстати, возможно, такой алгоритм уже существует и даже где-то используется, так что я не претендую на первооткрывательство. Я просто придумал его сам для себя, и решил написать статью об этом для людей, которые могут заинтересоваться подобным.
Если кому-то интересно - пишите, как можно улучшить или ухудшить алгоритм и реализации.
Комментарии (29)
fedorro
21.05.2024 17:03Берем первый чанк, знаем его номер, перебираем "Main key", склеивая с единицей и считая хэш, ксорим с зашифровным блоком, пока не получим читаемый текст, ключ найден, все данные расшифровны, ура.
KOCTEP Автор
21.05.2024 17:03Хм... Как вы описываете - могут быть ложные совпадения, при чём очень много, так что нужны дополнительные проверки на другие чанки. Но в целом - возможно. Вообще стал задумываться, что в этом алгоритме "Main Key" очень уязвимое место, даже если это хэш, ведь перебрать надо не так уж и много вариантов. Значит, нужно полностью передумать этот алгоритм, каким-то образом сокрыв "Main Key" от данных... Или просто не выдумывать всякую фигню и использовать нормальные и проверенные алгоритмы))
fedorro
21.05.2024 17:03Можно на втором же чанке проверять... Ну и чтобы уменьшить ложные срабатывания можно перебирать Passphrase, перед хэшем прогоняя её через шаги формирования "Main Key" .
suns
21.05.2024 17:03Это работает буквально с любым алгоритмом
fedorro
21.05.2024 17:03Да, но тут шаги простые, и блоки отдельно независимо шифруются. Кроме того последний блок, если шифротекстоказался не кратен длинне блока, нужно дополнять, например нулями или другой известной константой. Можно попробовать по последним байтам предположить что они дополнения отXORить с них биты хэша блока, длинной во всё дополнения и сбрутить остальные.
KOCTEP Автор
21.05.2024 17:03В моей реализации, в функцию передаётся информация о длине чанка, так что если чанк "неполный" - он так и шифруется, никак не меняя длину данных. Хотя я подозреваю, что передача числа тратит немало процессорного времени... Но тогда можно сделать отдельную функцию для шифрования неполных чанков, и вызывать её для последнего, передавая его длину, а все остальные (полные) шифровать без передачи длины чанка, чтобы сэкономить на времени передачи данных. Разумеется, никаких проверок делать не надо, надо сделать два цикла, for(количество_чанков-1) и потом отдельный вызов для неполного. Ну или вызывать операцию для неполного чанка после завершения обработки всех полных чанков, если это многопоточность
hddscan
21.05.2024 17:03+4Brute force ключа должен считать безопасной возможностью взлома, если ключ криптостойкий.
На современных процах скорость SHA256 примерно 2ГБ в секунду, т.е примерно 7.5 миллионов хешей в секунду для этого алгоритма или примерно 4.8 * 10 в 62й степени лет для полного перебора всех вариантов.
suns
21.05.2024 17:03Очень похоже на CTR режим в aes, там тоже шифрование/дешифрование через xor работает
Низкая скорость связана с большим количеством вызовов iup
pae174
21.05.2024 17:03+2Вы изобрели шифр Вернама (ну почти).
У Вернама открытый текст ксорится с ключем, который а) имеет размер, равный размеру открытого текста, б) является полностью случайным и в) является одноразовым.
У вас открытый текст ксорится с ключем, который а) имеет размер открытого текста, б) создан с использованием ГПСЧ с затравкой на входе (она у вас там называется Main key) и в) не является одноразовым, но его можно сделать таковым, добавив во всю эту схему случайный вектор инициализации.
lorc
21.05.2024 17:03+3Да нет, это обычное гаммирование. Им все пользуются даже когда юзают AES например. Почитайте про режимы CTR или GCM (если хочется еще и аутентификации). Их можно применять с любым блочным шифром, хоть AES, хоть DES.
hddscan
21.05.2024 17:03+1У вашего алгоритма есть серьезный недостаток - некриптостойкий Main key. Ключ шифрования должен быть сформирован случайным образом и иметь достаточную длину. Иначе его можно легко подобрать по словарю.
Это проблему частично можно решить завернув Passphrase в многократное хэширование (например 100000 SHA256 в цикле). Но все равно это существенно снижает безопасность и сильно зависит от пароля.
KOCTEP Автор
21.05.2024 17:03Да, на схеме изображён процесс преобразования парольной фразы в хэш ("Optional" - по желанию). Можно прикрутить туда Argon2, настроить приблизительное время шифрования на секунду-две (защита от брутфорса паролей), и как-то заставить его выдавать хэш огромной длины, чтобы "Main Key" был довольно сложный. Но всё же - его можно перебрать, и получить "Main Key" в чистом виде, чтобы потом добавить любую цифру, прогнать через SHA-256 и получить ключ для любого чанка... Так что у меня есть подозрения, что алгоритм фигня полная, хоть попытка и неплохая. А может - можно как-то сокрыть "Main Key" от чанков...
TEMN1J
21.05.2024 17:03Пожалуйста, не надо 100000 SHA256 в цикле. Есть хорошие алгоритмы: SCRYPT, BCRYPT, ARGON2, PBKDF2
KOCTEP Автор
21.05.2024 17:03Смотря для чего. Сейчас проектирую новую наглядную схему, с исправлением уязвимостей (XOR и утечка парольной фразы). Парольная фраза теперь будет проходить через PBKDF2. А вот ключ для каждого отдельного чанка (от результата работы PBKDF2 и номера чанка) всё ещё будет генерироваться с помощью SHA-256 - этого достаточно, и это быстро, что хорошо для шифрования больших файлов
lorc
21.05.2024 17:03+8Вы изобрели режим шифрования CTR, только у вас вместе IV/Nonce - Main Key, а вместо блочного шифра - хеш функция.
Проблема тут в том, что нельзя зашифровать два разных сообщения одним ключом. Точнее, зашифровать то можно, но атакующий поксорит их между собой и таким образом получит два поксоренных но незашифрованных сообщения. Это сильно упрощает анализ, особенно если сообщений не два, а хотя бы десяток.
Вам надо добавить случайный IV к каждому сообщению, как делают все режимы шифрования кроме EBC. Тогда фокус с XOR больше не прокатит.
lorc
21.05.2024 17:03+5Вообще, когда разрабатываете криптосистему, обращайте внимание на все возможные атаки. Кейс "у атакующего есть только одно перехваченное сообщение и знание алгоритма" - самый простой. Но что если:
Атакующий может перехватить сотни и тысячи сообщений зашифрованных одним ключом? Как я уже говорил, в вашем примере - он просто поксорит эти сообщения между собой и таким образом избавится от вашего шифра
Атакующий может подсунуть вам plaintext, который вы зашифруете? Это не так уж маловероятно, как кажется. Тогда он может подсунуть вам все нули и получить гаммирующую последовательность в чистом виде. Дальше ксорим ее с любым зашифрованным сообщением и вуаля!
Что если атакующий знает минимум одну пару шифротекст/открытый текст? Он может поксорить их между собой и получить гаммирующую последовательность. Дальше см. предыдущий пункт.
-
Что если атакующий может слать вам для проверки тысячи/миллионы сообщений? Например сервер ожидает запрос зашифрованный определенным ключом и отдает разные коды ошибок в случае если ему удалось расшифровать запрос и увидеть там валидные данные или нет.
Это то что вспомнилось из головы. На самом деле атак больше.
Если вам реально интересна криптография - сходите на https://cryptopals.com/
Там собрано кучу упражнений по взлом шифров. Вы научитесь делать это на практике. Ну и соответственно понимать, как проектировать системы чтобы ваш шифр не поломали так легкою
KOCTEP Автор
21.05.2024 17:03На счёт "фокуса с XOR" - никогда о таком не слышал... То есть, злоумышленник может собрать, например, кучу файлов, зашифрованных одним и тем же подобным алгоритмом, да ещё и одним ключом, и как-то получить что-то типа корреляции?
На счёт "plain text" - тут опасность даже не в подстановке своих данных, а в том, что пользователь сам себя может подставить, зашифровав файл с большим количеством нулей (например в начале .wav файлов есть похожие моменты, насколько я помню). Получается, что нули - главный враг XOR'а, ведь просто просвечивают ключ...
Вообще, этот алгоритм больше применим к шифрованию личных файлов, например для шифрования одного большого архива "Анапа 2006", чем для шифрования сотен тысяч сообщений. Но я согласен, что нельзя использовать одинаковые """пароли""" с таким алгоритмом.
Или же, стоит добавить что-нибудь эдакое? Уже второй человек советует добавить "случайность", но я что-то пока не догоняю, что за "случайность", и не помешает ли это удобному шифрованию/дешифрованию. Может, к ключу добавлять имя файла? В моей реализации шифрованные файлы имеют на конце "_computed", так что по-идее, можно её игнорировать при дешифровке, и таким образом, ключ будет уникальным для разных файлов при одинаковой парольной фразе. Или, нужно добавить что-то другое?
P.S. Почитал про IV - вектор инициализации. Как-то сложно придумать, куда его вставить в этой схеме. По-сути, добавление номера чанка к "Main Key" и хэширование всего этого дела - это и есть местный аналог IV. Но почему-то он получился очень уязвимый. Значит, можно заменить номер чанка на соответствующий элемент какой-нибудь псевдослучайной последовательности + IV? А от чего брать IV, чтобы при расшифровке проблем не было? Сложна...
lorc
21.05.2024 17:03+4На счёт "фокуса с XOR" - никогда о таком не слышал... То есть, злоумышленник может собрать, например, кучу файлов, зашифрованных одним и тем же подобным алгоритмом, да ещё и одним ключом, и как-то получить что-то типа корреляции?
Нет, все куда проще. Вы же шифруете вот так
ciper=HASH(mainkey + chunkid) XOR plain.Допустим у у нас есть два заширфованных текста:С1 = HASH(mainkey + chunkid) XOR plain1иС2 = HASH(mainkey + chunkid) XOR plain2.Делаем
C1 XOR C2и получаемplain1 XOR plain2потому что часть сHASH()сократится. Анализироватьplain1 XOR plain2уже намного проще, особенно если можно набрать несколько таких пар. Но в любом случае на этом моменте шифр уже сломан.Получается, что нули - главный враг XOR'а, ведь просто просвечивают ключ...
Именно! Но если у вас гамма-последовательность каждый раз разная (благодаря случайным IV), то это уже не проблема.
Значит, можно заменить номер чанка на соответствующий элемент какой-нибудь псевдослучайной последовательности + IV?
ну можно и так. Но лучше считать
HASH(mainkey + IV + chunkid), символ + тут - это конкатенация, а не арифметическое сложение, если что.А от чего брать IV, чтобы при расшифровке проблем не было?
А его надо хранить. При шифровании генерируете 16 случайных байт и кладете их в самое начало файла, например. Или в конец. Их не надо никак шифровать или прятать. Главное требование - вектор должен быть разным каждый раз. И пофиг что его всем видно. При расшифровке, соответственно сначала читаете IV, потом уже основной шифропоток.
KOCTEP Автор
21.05.2024 17:03+1А-фи-геть. XOR'нув два файла одинаковым ключом, не важно какой длины и сложности, а потом XOR'нув их между собой - мы получаем обратно исходные файлы, даже не зная ключа? Я в афиге с этой информации, не знал о таком. Но буду знать. Спасибо вам за знания!
Итак, благодаря комментариям, в алгоритме найдено 3 места для атаки:
XOR-фокус. Собираюсь чинить его при помощи использования и сохранения IV. Думаю, брать за IV вот такую конструкцию:
SHA-256(strcat(текущее время в секундах, миллисекунды))Брутфорс парольной фразы. Собираюсь чинить при помощи обязательного прогона через Argon2. Информацию о приблизительном времени работы Argon2 можно хранить рядом с IV в зашифрованном файле.
Брутфорс "Main key", как писал один из первых комментаторов. Эм... Если парольная фраза будет обязательно хэшироваться... То удачи брутфорснуть. По моим скромным подсчётам (даём фору компьютерам, вдруг квантовые захотят использовать), надо перебрать 256 вариантов для каждого байта, а байтов 32 или больше. А значит, надо перебрать в лучшем случае 58244594029230756747090036884923424763000 вариантов хэша. Со скоростью 100 триллиардов хэшей в секунду (что "нифига себе" даже для квантовых компьютеров) - понадобится 18.936.158.587.322.733 лет. То есть почти 19 триллиардов лет. И это в лучшем случае, с невероятной скоростью.
Значит, надо сделать алгоритм разносторонним - должен появиться выбор между "шифровать" и "дешифровать", который добавляет или убирает часть с IV и "временем работы" Argon2. Надо сделать обязательным хэширование парольной фразы для использования в "Main key".
Ещё на долю секунды в голову закралась мысль, что можно добавить рядом с IV и "временем" работы Argon2 ещё и некую строку из номеров "неудачных" чанков, в которых среднее арифметическое между байтами меньше константной, и для таких чанков нужно генерировать ключ дважды (использовать хэш для чанка из хэша для чанка). Но, так как для каждого файла будет свой "Main key", думаю, что эта идея бесполезная, и лишь будет замедлять процесс. Ведь я этот алгоритм сначала и придумал, чтобы избавиться от повторений! А злоумышленнику неизвестно, является ли чанк неудачным или нет, так что никаких подозрений он вызывать не будет. Максимум - узнает ключ чанка. Но чтобы узнать другие - придётся перебирать "Main Key", а это, мягко говоря, надолго.
Возможно, алгоритм немного замедлится, хотя можно применять аппаратные ускорения вычисления хэшей для более комфортного использования. Но с такой защитой, алгоритм будет вполне рабочим и безопасным, я подозреваю?
Спасибо вам за подсказки и объяснения!
Number571
21.05.2024 17:03+4Схема интересная, опирается по большей части на безопасность самой криптографической хеш-функции, что хорошо. Но в этом подходе есть также и ряд подводных камней:
Хеш-функции в массе своей итеративны, вследствие этого, номер который дополняет ключ чисто теоретически может дополняться ещё "сверх того". Эта атака может быть применена когда совпадут одновременно два условия: 1) Хеш-функция успешно захешировала блоки в котором находится полный ключ, 2) Номер блока не дополняется до статичной длины. При таких условиях будет осуществима атака удлинения сообщения, где криптоаналитик сможет продолжить шифровать сообщение валидным ключом при этом его не зная. Вследствие этого, лучше использовать не хеш-функцию, а HMAC от этой хеш-функции,
Криптостойкость шифрованного блока ограничена числом N/2 (парадокс дней рождения), где N - длина выходного блока хеш-функции. Иными словами, через N/2 будет возможно взломать один из блоков с вероятностью >50%. Для SHA-256, SHA-512 это приемлемо, но для более малых хеш-функций (например MD5) - это уже будет уязвимостью. Вследствие этого, даже если энтропия ключа будет равна X, где X > N/2, то фактическая безопасность шифра останется всё также равной N/2,
Парольная фраза должна проходить всё же через KDF (например, scrypt, pbkdf2), а не через хеш-функцию. Это не повысит энтропию ключа, но повысит сложность полного перебора. Тем не менее, я бы в данной схеме вообще убрал данный блок, потому что это избыточно. Например, в спецификации AES нет пункта, который бы требовал пропускать ключ через KDF, т.к. предполагается, что ключ уже надёжный. Я бы просто в коде установил, что длина ключа должна быть равна N/2 от длины блока N. В таком случае, мы явно говорим, что безопасность нашего шифра равна N/2 с учётом атаки парадокса дней рождения,
В схеме не хватает дополнительной оказии для сеанса связи. Если шифрование повторится дважды с одним ключом, то это будет крайне плохим событием. Эта проблема уже опирается не на криптографическую хеш-функцию, а на поточную структуру вашего алгоритма. Данная проблема свойственна всем поточным шифрам и режимам шифрования формирующих поточность, как CTR, OFB. Для борьбы с этим либо создают случайный вектор инициализации для каждого шифрованного сообщения, либо уникальный номер для конкретного сеанса связи.
KOCTEP Автор
21.05.2024 17:034 пункт - уже знаю, буду принимать меры для исправления этой уязвимости. А вот для генерации пароля думаю использовать Argon2. Но задумался об эффективной длине парольной фразы и её рекомендации, чтобы избежать неудачных коллизий. На счёт первых двух пунктов я что-то не сильно догоняю, но могу сказать, что длина номера чанка всегда одинаковая, типа 000001 и 999999 (всего возможны 20 цифр).
rezedent12
21.05.2024 17:03Каждый может придумать алгоритм шифрования который не сможет взломать сам.
Вообще с точки зрения теории информации, фундаментально её нельзя создать из ничего. Если ключ "надуть", он по сути более стойким не станет.
Короче. Вот тебе идея. Существует память на пережигаемых перемычках, полагаю её возможно сделать в форме микрочипа. Такая память будет даже дешевле flash-памяти. В эту память записывается условный терабайт ключа. Два таких одинаковых чипа вставляют в маршрутизаторы и связывают их IP туннелем. Сами чипы не позволяют напрямую считывать своё содержимое. У них есть только ограниченный набор функций. Они сами выполняют простейшую расшифровку или шифрование с помощью XOR.
Проблема такого метода, в том что чипам надо как то договариваться о текущем блоке и не позволять кому либо произвольно сдвинуть текущий блок или спровоцировать их перерасход. Самый простой способ решить эту проблему, это в каждом блоке зарезервировать некоторое количество байт под хэшируемую последовательность.
Каждый успешно переданный и принятый пакет, должен стирать часть ключа, пережигая "перемычки" в чипе. Лучше конечно что бы чип вообще не подразумевал возможность считать с него ключ без препарирования под сканирующим микроскопом.
Однако всё же не понятно как решить проблемы подмены открытой части сообщений в подобном протоколе. Которая могла бы имитировать обычный сбой процесса синхронизации и провоцировать произвольный пропуск блоков. Полагаю нужно вместо номеров блоков, использовать их хэши.
vitaliyterletskiy
21.05.2024 17:03Ваш подход имеет потенциал, но требует тщательной проработки деталей и учета различных атак и уязвимостей. Важно также учитывать практические аспекты, такие как износ чипов и необходимость их периодического обновления.
suurtoll
Это у вас довольно стандартный шифр гаммирования, где гамма генерируется не самым оптимальным образом (медленно, зависит от номера блока). У вас получается :
Hash(Masterkey||0) - гамма для блока 0
Hash(Masterkey||1) - гамма для блока 1
...
Если известен открытый текст для любого блока, то это облегчает задачу аналитика. Насколько - зависит от свойств Hash.
KOCTEP Автор
Да, всё так. Вообще, насколько я понял - стоит заменить хэширование на более быстрый, но при этом стойкий алгоритм, и немного поиграться с гаммой - как получается AES.