Comments 30
Это у вас довольно стандартный шифр гаммирования, где гамма генерируется не самым оптимальным образом (медленно, зависит от номера блока). У вас получается :
Hash(Masterkey||0) - гамма для блока 0
Hash(Masterkey||1) - гамма для блока 1
...
Если известен открытый текст для любого блока, то это облегчает задачу аналитика. Насколько - зависит от свойств Hash.
Берем первый чанк, знаем его номер, перебираем "Main key", склеивая с единицей и считая хэш, ксорим с зашифровным блоком, пока не получим читаемый текст, ключ найден, все данные расшифровны, ура.
Хм... Как вы описываете - могут быть ложные совпадения, при чём очень много, так что нужны дополнительные проверки на другие чанки. Но в целом - возможно. Вообще стал задумываться, что в этом алгоритме "Main Key" очень уязвимое место, даже если это хэш, ведь перебрать надо не так уж и много вариантов. Значит, нужно полностью передумать этот алгоритм, каким-то образом сокрыв "Main Key" от данных... Или просто не выдумывать всякую фигню и использовать нормальные и проверенные алгоритмы))
Это работает буквально с любым алгоритмом
Да, но тут шаги простые, и блоки отдельно независимо шифруются. Кроме того последний блок, если шифротекстоказался не кратен длинне блока, нужно дополнять, например нулями или другой известной константой. Можно попробовать по последним байтам предположить что они дополнения отXORить с них биты хэша блока, длинной во всё дополнения и сбрутить остальные.
В моей реализации, в функцию передаётся информация о длине чанка, так что если чанк "неполный" - он так и шифруется, никак не меняя длину данных. Хотя я подозреваю, что передача числа тратит немало процессорного времени... Но тогда можно сделать отдельную функцию для шифрования неполных чанков, и вызывать её для последнего, передавая его длину, а все остальные (полные) шифровать без передачи длины чанка, чтобы сэкономить на времени передачи данных. Разумеется, никаких проверок делать не надо, надо сделать два цикла, for(количество_чанков-1) и потом отдельный вызов для неполного. Ну или вызывать операцию для неполного чанка после завершения обработки всех полных чанков, если это многопоточность
Brute force ключа должен считать безопасной возможностью взлома, если ключ криптостойкий.
На современных процах скорость SHA256 примерно 2ГБ в секунду, т.е примерно 7.5 миллионов хешей в секунду для этого алгоритма или примерно 4.8 * 10 в 62й степени лет для полного перебора всех вариантов.
Чтобы такого не было шифруется нечитаемый текст.
Очень похоже на CTR режим в aes, там тоже шифрование/дешифрование через xor работает
Низкая скорость связана с большим количеством вызовов iup
Вы изобрели шифр Вернама (ну почти).
У Вернама открытый текст ксорится с ключем, который а) имеет размер, равный размеру открытого текста, б) является полностью случайным и в) является одноразовым.
У вас открытый текст ксорится с ключем, который а) имеет размер открытого текста, б) создан с использованием ГПСЧ с затравкой на входе (она у вас там называется Main key) и в) не является одноразовым, но его можно сделать таковым, добавив во всю эту схему случайный вектор инициализации.
У вашего алгоритма есть серьезный недостаток - некриптостойкий Main key. Ключ шифрования должен быть сформирован случайным образом и иметь достаточную длину. Иначе его можно легко подобрать по словарю.
Это проблему частично можно решить завернув Passphrase в многократное хэширование (например 100000 SHA256 в цикле). Но все равно это существенно снижает безопасность и сильно зависит от пароля.
Да, на схеме изображён процесс преобразования парольной фразы в хэш ("Optional" - по желанию). Можно прикрутить туда Argon2, настроить приблизительное время шифрования на секунду-две (защита от брутфорса паролей), и как-то заставить его выдавать хэш огромной длины, чтобы "Main Key" был довольно сложный. Но всё же - его можно перебрать, и получить "Main Key" в чистом виде, чтобы потом добавить любую цифру, прогнать через SHA-256 и получить ключ для любого чанка... Так что у меня есть подозрения, что алгоритм фигня полная, хоть попытка и неплохая. А может - можно как-то сокрыть "Main Key" от чанков...
Пожалуйста, не надо 100000 SHA256 в цикле. Есть хорошие алгоритмы: SCRYPT, BCRYPT, ARGON2, PBKDF2
Смотря для чего. Сейчас проектирую новую наглядную схему, с исправлением уязвимостей (XOR и утечка парольной фразы). Парольная фраза теперь будет проходить через PBKDF2. А вот ключ для каждого отдельного чанка (от результата работы PBKDF2 и номера чанка) всё ещё будет генерироваться с помощью SHA-256 - этого достаточно, и это быстро, что хорошо для шифрования больших файлов
Вы изобрели режим шифрования CTR, только у вас вместе IV/Nonce - Main Key, а вместо блочного шифра - хеш функция.
Проблема тут в том, что нельзя зашифровать два разных сообщения одним ключом. Точнее, зашифровать то можно, но атакующий поксорит их между собой и таким образом получит два поксоренных но незашифрованных сообщения. Это сильно упрощает анализ, особенно если сообщений не два, а хотя бы десяток.
Вам надо добавить случайный IV к каждому сообщению, как делают все режимы шифрования кроме EBC. Тогда фокус с XOR больше не прокатит.
Вообще, когда разрабатываете криптосистему, обращайте внимание на все возможные атаки. Кейс "у атакующего есть только одно перехваченное сообщение и знание алгоритма" - самый простой. Но что если:
Атакующий может перехватить сотни и тысячи сообщений зашифрованных одним ключом? Как я уже говорил, в вашем примере - он просто поксорит эти сообщения между собой и таким образом избавится от вашего шифра
Атакующий может подсунуть вам plaintext, который вы зашифруете? Это не так уж маловероятно, как кажется. Тогда он может подсунуть вам все нули и получить гаммирующую последовательность в чистом виде. Дальше ксорим ее с любым зашифрованным сообщением и вуаля!
Что если атакующий знает минимум одну пару шифротекст/открытый текст? Он может поксорить их между собой и получить гаммирующую последовательность. Дальше см. предыдущий пункт.
Что если атакующий может слать вам для проверки тысячи/миллионы сообщений? Например сервер ожидает запрос зашифрованный определенным ключом и отдает разные коды ошибок в случае если ему удалось расшифровать запрос и увидеть там валидные данные или нет.
Это то что вспомнилось из головы. На самом деле атак больше.
Если вам реально интересна криптография - сходите на https://cryptopals.com/
Там собрано кучу упражнений по взлом шифров. Вы научитесь делать это на практике. Ну и соответственно понимать, как проектировать системы чтобы ваш шифр не поломали так легкою
На счёт "фокуса с XOR" - никогда о таком не слышал... То есть, злоумышленник может собрать, например, кучу файлов, зашифрованных одним и тем же подобным алгоритмом, да ещё и одним ключом, и как-то получить что-то типа корреляции?
На счёт "plain text" - тут опасность даже не в подстановке своих данных, а в том, что пользователь сам себя может подставить, зашифровав файл с большим количеством нулей (например в начале .wav файлов есть похожие моменты, насколько я помню). Получается, что нули - главный враг XOR'а, ведь просто просвечивают ключ...
Вообще, этот алгоритм больше применим к шифрованию личных файлов, например для шифрования одного большого архива "Анапа 2006", чем для шифрования сотен тысяч сообщений. Но я согласен, что нельзя использовать одинаковые """пароли""" с таким алгоритмом.
Или же, стоит добавить что-нибудь эдакое? Уже второй человек советует добавить "случайность", но я что-то пока не догоняю, что за "случайность", и не помешает ли это удобному шифрованию/дешифрованию. Может, к ключу добавлять имя файла? В моей реализации шифрованные файлы имеют на конце "_computed", так что по-идее, можно её игнорировать при дешифровке, и таким образом, ключ будет уникальным для разных файлов при одинаковой парольной фразе. Или, нужно добавить что-то другое?
P.S. Почитал про IV - вектор инициализации. Как-то сложно придумать, куда его вставить в этой схеме. По-сути, добавление номера чанка к "Main Key" и хэширование всего этого дела - это и есть местный аналог IV. Но почему-то он получился очень уязвимый. Значит, можно заменить номер чанка на соответствующий элемент какой-нибудь псевдослучайной последовательности + IV? А от чего брать IV, чтобы при расшифровке проблем не было? Сложна...
На счёт "фокуса с 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, потом уже основной шифропоток.
А-фи-геть. 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", а это, мягко говоря, надолго.
Возможно, алгоритм немного замедлится, хотя можно применять аппаратные ускорения вычисления хэшей для более комфортного использования. Но с такой защитой, алгоритм будет вполне рабочим и безопасным, я подозреваю?
Спасибо вам за подсказки и объяснения!
Гуглим, например, GCM mode.
И да - Вы опасно некомпетентным викриптографии.
Схема интересная, опирается по большей части на безопасность самой криптографической хеш-функции, что хорошо. Но в этом подходе есть также и ряд подводных камней:
Хеш-функции в массе своей итеративны, вследствие этого, номер который дополняет ключ чисто теоретически может дополняться ещё "сверх того". Эта атака может быть применена когда совпадут одновременно два условия: 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. Для борьбы с этим либо создают случайный вектор инициализации для каждого шифрованного сообщения, либо уникальный номер для конкретного сеанса связи.
4 пункт - уже знаю, буду принимать меры для исправления этой уязвимости. А вот для генерации пароля думаю использовать Argon2. Но задумался об эффективной длине парольной фразы и её рекомендации, чтобы избежать неудачных коллизий. На счёт первых двух пунктов я что-то не сильно догоняю, но могу сказать, что длина номера чанка всегда одинаковая, типа 000001 и 999999 (всего возможны 20 цифр).
Каждый может придумать алгоритм шифрования который не сможет взломать сам.
Вообще с точки зрения теории информации, фундаментально её нельзя создать из ничего. Если ключ "надуть", он по сути более стойким не станет.
Короче. Вот тебе идея. Существует память на пережигаемых перемычках, полагаю её возможно сделать в форме микрочипа. Такая память будет даже дешевле flash-памяти. В эту память записывается условный терабайт ключа. Два таких одинаковых чипа вставляют в маршрутизаторы и связывают их IP туннелем. Сами чипы не позволяют напрямую считывать своё содержимое. У них есть только ограниченный набор функций. Они сами выполняют простейшую расшифровку или шифрование с помощью XOR.
Проблема такого метода, в том что чипам надо как то договариваться о текущем блоке и не позволять кому либо произвольно сдвинуть текущий блок или спровоцировать их перерасход. Самый простой способ решить эту проблему, это в каждом блоке зарезервировать некоторое количество байт под хэшируемую последовательность.
Каждый успешно переданный и принятый пакет, должен стирать часть ключа, пережигая "перемычки" в чипе. Лучше конечно что бы чип вообще не подразумевал возможность считать с него ключ без препарирования под сканирующим микроскопом.
Однако всё же не понятно как решить проблемы подмены открытой части сообщений в подобном протоколе. Которая могла бы имитировать обычный сбой процесса синхронизации и провоцировать произвольный пропуск блоков. Полагаю нужно вместо номеров блоков, использовать их хэши.
Я вас, наверное, не обрадую, но вы не изобрели ничего нового или, хотя бы, нетривиального. Шифр, который вы предложили, построен по классической схеме из первой же главы учебника. Как будто бы можно даже показать его криптостойкость в некотором смысле, если потребовать соблюдение ряда дополнительных условий.
Я не профессиональный криптограф, поэтому вывод строгого доказательства со всеми нужными ссылками займёт у меня неоправданно много времени. Но приведу общую идею почему я считаю, что шифр стойкий.
Вот ваш шифр:
Давайте дополнительно потребуем, что:
ключ
должен быть фиксированной битовой ширины (то есть, никаких «main key» произвольной длины!),счётчик
тоже должен быть фиксированной битовой ширины (достаточной для хранения индекса блока даже безумно длинного сообщения).
Эти дополнительные требования исключают length-extension-атаку на хеш-функцию, поэтому, интуитивно, её стойкость в этом сценарии будет эквивалентна стойкости конструкции HMAC от неё. Поэтому мы можем переписать ваш шифр на эквивалентный по стойкости:
Далее предположим, что функция 
построена по схеме Меркла-Дамгора (SHA-256 именно такая) и лежащая в её основе функция компрессии является криптоскойкой псевдослучайной функцией (для функций семейства SHA на данный момент не доказано обратного). Для таких хеш-функций доказано†, что 
является стойкой псевдослучайной функцией (PRF) относительно ключа. Следовательно, снова можем переписать шифр на эквивалентный по стойкости:
Это выражение — классический блочный шифр в режиме со счётчиком. Его стойкость доказана при условии, что:
ключ
выбирается случайным образом из множества возможных ключей,ключ используется для шифрования не более чем одного сообщения.
Этот вывод, вообще говоря, довольно очевиден с самого начала, если вспомнить, что SHA-256 построена на основе полноценного блочного шифра SHACAL-2. С тем же успехом можно было бы просто применить этот блочный шифр напрямую.
† В доказательство этого утверждения я никогда подробно не вчитывался, поэтому сошлюсь тут Википедию, https://en.wikipedia.org/wiki/HMAC:
In particular, Mihir Bellare proved that HMAC is a pseudo-random function (PRF) under the sole assumption that the compression function is a PRF. [далее ссылка на PDF с публикацией]
Идеальный алгоритм шифрования? HASH-CRYPT (1 часть)