Потоковый шифр
Требуется сделать потоковый шифр с такими свойствами:
1. Минимально необходимый обьем состояния.
2. 256-битная необратимость функции. То есть если противник завладел полным состоянием шифра в момент i, то ему потребуется 2^256 работы чтобы получить состояние шифра в момент i-1.
3. 256-битная стойкость к раскрытию по известной гамме шифра.
4. Гарантированный минимальный период 2^128.
Берем блочный шифр F(Key,X) c 64-битным блоком X и 128 битным ключом K. Берем хеш функцию H(X,Y) с размером 256 бит. Берем некую машину состояний M шириной 128 бит с полным периодом; возможно некриптостойкую (LSFR, LCG или даже последовательность Вейля). Состояние шифра = (M,X) = состояние машины + состояние хеш функции. Состояние [0] начально инициализируется неким криптостойким способом из исходного ключа и IV.
На каждом шаге делается:
1. Переход в новое состояние машины M[i+1] из M[i]
2. Хеширование X[i+1] = H(X[i],M[i+1])
3. Берем какие-то 128 бит из 256-битного X[i+1] как ключ K.
4. Делим 128-битное состояние M на 2 x 64 bit и берем их как X0,X1.
5. Генерируем два выходных 64-битных значения Y0 = F(K, X0), Y1 = F(K, X1). (Y0,Y1) – гамма шифра.
Если противник завладел состоянием шифра, то для прокручивания шифра назад ему придется находить прообразы для 256-битной хеш функции.
Если противник завладел гаммой шифра, то для восстановления cостояния (M,X) ему нужно 2^256 работы.
Итого имеем 256-битную стойкость при 384-битном состоянии; при условии что хеш функция и шифр идеальны. Для получения 128 бит гаммы требуется два выполнения шифра и одно выполнение хеш функции.
Покритикуйте предложенную схему.
Зачем? Чужие мысли же плохо помогают при отсутствии собственных.
комментариев: 9796 документов: 488 редакций: 5664
Сейчас везде, где только можно, используют блочный шифр (AES) в самом простом потоковом режиме — режиме счётчика. Это считается хорошей практикой, и теоретически с этим никаких проблем нет. Не встречал ни одной публикации, где-бы объяснялось, почему счётчик — это плохо и нужно городить какие-то более навороченные конструкции поверх. Если блочный шифр неразличим от идеального, то и со счётчиком, там где можно его использовать, всё хорошо; если различим — то надо менять сам блочный шифр, а не городить перестраховки на уровне режима шифрования.
Насчёт «чужих мыслей», по аналогии с предыдущим тредом как-то так и есть. Если где-то кто-то опубликует убедительные доказательства, что режим счётчика — это фундаментально плохо, тогда есть смысл смотреть дальше. А пока всех вроде как устраивают решения на основе
«чужих мыслей»счётчика и без наворачивания велосипедов поверх.Потоковый шифр без произвольного доступа? Такое сейчас стараются не использовать. Похожие по набору требований конструкции используются в CSPRNG с перетиранием предыдущих использованных состояний, но не называют их потоковыми шифрами с особыми свойствами.
Хотя, действительно, зачем пересказывать «чужие мысли». А то, начну страдать от того, что своих
велосипедогенераторовнет.P.S.: Ошибся, есть :) Правда, только для демонстрации возможности реализации определённой концепции для очень экзотического случая. В ходе обсуждения одной темы возник оффтопик по обслуживанию согласованных одноразовых блокнотов на CPUF-носителях посредством подстраховочного протокола, обеспечивающего переход от инф.-теоретической стойкости к вычислительной в случае компрометации оборудования. Возникло предположение об использовании некоего режима шифрования, который очень похож по требованиям на описываемый вами, была рассмотрена возможность реализации конструкции на основе Sponge/Keccak.
1. Блочный шифр биективен. В режиме счетчика получаем не (псевдо)случайную последовательность, а перестановку. Чтобы выходная последовательность выглядела случайной, пространство выходных значений должно быть существенно меньше пространства состояний. Например, выводить половину битов от ширины блока.
2. Блочный шифр ограничен. Одно и то же значение cчетчика при всех возможных ключах будет отображено не на любое, а на какое-то подмножество возможных выходных значений. То есть размер ключа должен быть существенно больше размера блока.
В результате СTR режим довольно неэффективный по размеру состояния и по вычислительным затратам; безопасный при соблюдении ограничений. Произвольный доступ тоже является недостатком в ряде случаев.
Только и слышно про AES/Keccak. Sponge при элегантности и простоте концепции имеет большой оверхед по размеру состояния; вопросительную вычислительную эффективность; стойкость cущественно зависит от используемой функции. Т.е. sponge по сути еще один режим использования блочного шифра. AES – математически строгая оптимизация на тему сомнительной целевой функции. Такое впечатление, что подобрали задачу под математику; а не наоборот.
комментариев: 9796 документов: 488 редакций: 5664
Это т.н. тривиальные различители. В подавляющем большинстве областей применения они не представляют собой никаких теоретических или практических сложностей. По ним выход идеальной PRF можно различить от счётчика только за 2n/2 шагов, где n — размер блока (внутреннего состояния) выхода. Так все в курсе, что 264 блоков открытого текста в режиме счётчика потоком на одном ключе шифровать нельзя, а больше 264 ключей тоже маловероятно, что кто-то способен использовать.
Зато самый простой по доказательствам и по реализации.
На практике до пределов этих ограничений никто и не доходит, они с лихвой покрывают все мыслимые потребности. А в том подавляющем большинстве случаев, где эти ограничения допустимы, он ещё и эффективен.
Лёгкость распараллеливания и быстродействие тоже иногда в узком наборе случаях пытаются намеренно ухудшить (по возможности, строго параметризированно), например в PBKDF. Для вашего случая можно запихать шифр в CSPRNG, но там действительно будут проблемы с размером блока (внутреннего состояния). Для таких случаев и создали продвинутые режимы Keccak.
Так и было до создания Keccak. Авторы подобрали эффективную, хотя и несколько заоптимизированную функцию, не без своих проблем, но проблему оверхеда решили, пусть и с некоторой натяжкой.
А разве может быть как-то по другому? Это делали специально, потому что
это хорошо, правильно и всем понравитсякриптографы лучше всего знают, как проектировать и анализировать стойкость именно блочных перестановок, в отличие от всего остального. Для Sponge доказано, что если внутренняя бесключевая перестановка неотличима от идеальной, то и все Sponge-режимы неотличимы от идеальных до границ, задаваемых соотношением "Flat Sponge Claim". В любом блочном шифре такой же подход: раундовая функция должна обладать определёнными функциями стойкости, неразличимыми от идеальных путём перебора после r раундов.Ну пусть кто-то предложит лучше обоснованные функции, зато механизм оптимизации уже готов.
Честно говоря, совершенно непонятно, что вы можете предложить лучше этого, для каких условий, для каких задач, по каким критериям. Также как и в ряде других ваших вопросов, непонятно, чем
кроме NIH-синдромапродиктовано желание создавать и предлагать на рассмотрение местной публике какие-то странные, вычурные,маргинальныенемейнстримные, плохо обоснованные криптоконструкции взамен существующих и теоретически обоснованных.A вот Бернштейн сделал хеш функцию в режиме счетчика (Salsa/ChaCha); чем избавился от различителя по биективности и от лишних проблем реализации блочных шифров (ключевое расписание, эффективная обратная функция...).
Теперь применим вместо счетчика состояние другой хеш функции, которое, в свою очередь, будем перехешировать от счетчика. Получаем шифр, работающий только вперед. Дальнейшие построения – вопрос оптимизации.
Cм. начало треда.
Пробовал предложить местной публике детский, смешной шифр:
https://www.pgpru.com/forum/prakticheskajabezopasnostj/zascommunicator?p=7&show_comments=1#comments
Никто ничего не заметил. Криптографы :)
Зачем что-то писать. Есть букварь. Все написано от "A" до "Я" ?
К мейнстрим конструкциям отработаны мейнстрим подходы ко взлому, построено специализированное железо, посчитаны дифференциальные характеристики; заготовлены таблицы. Не-мейнстрим решение требует индивидуального подхода; его дороже сломать.
Мне интересны следующие темы:
1. Универсальный масштабируемый по размеру ключа и блока примитив блочного шифра. Предельно простой в реализации; эффективность второстепенна.
2. Aлгоритмы с минимальным оверхедом по памяти. Идеально чтобы вcя требуемая память была равна размеру блока + размер ключа.
3. Обьединение шифров с целью перестраховки. Например, блочный шифр собирается произвольным образом из разнородных примитивов на основе ключа. Чтобы нельзя было раз и навсегда провести подготовительные рассчеты.
комментариев: 9796 документов: 488 редакций: 5664
Вам был дан ответ, повторяющий более общую позицию, вынесённую в FAQ.
Сразу же непонятен первый пункт — это что, незаконченное предложение?
В целом, если кто-то хочет анализировать любительские поделки, претендующие на фундаментальные исследования — никто не против таких тем. Может кто-то заинтересуется, разберёт ваши изыскания и ответит. Но по поводу шифрпанка всегда готовьтесь услышать предостережения, если не вам лично, то пользователям крипто.
Клиент так непроходимо туп, что не может сослаться на конкретный комментарий, но ЧСВ и бравада скоро не поместятся в форум.
Как обычно, совсем нечего сказать по делу?
Вот игрушечный потоковый шифр на две строчки. Найдите ключ seed.
Покажите, что вы специалист, а не ученый попугай, научившийся повторять AES, Keccak и другие умные слова.
http://www.zas-comm.ru
Начало генерируемой гаммы (256 байт):
комментариев: 11558 документов: 1036 редакций: 4118
почёсывания ЧСВпопытки самоутверждения? Одно дело, если б это был единичный эксцесс, но ведь воспроизводится в точности из раза в раз. Ну, окей, если местная публика не удовлетворяет, пишите вIACRболее подходящий шифрпанковский форум, где Ваши велосипеды оценят должным, с Вашей точки зрения, образом, никто ж здесь не держит.Человек, cчитающий себя специалистом, по крайней мере обязан вести себя прилично. Особенно если специалистом не является :) Так и думал, что окажется слабо решить элементарную задачу. В таком случае, какой смысл разговаривать о высоких материях.
Cдаетесь? Привести решение?
комментариев: 11558 документов: 1036 редакций: 4118
Ваши бы слова да богу в уши. Почему же автор этих строк считает, что на него данная обязанность не распространяется?
Присоединяюсь к вышеозвученному вопросу: с чего Вы решили, что Вам здесь должны что-то доказывать? Что Вы сделали, чтобы проявить к себе достаточный интерес? Стабильно наблюдаю только апломб и ничем, помимо мнения автора, не подкреплённые утверждения.
ЗЫ: обратная функция будет seed = (seed ^ 0x5e62a7e83848d96b) * 9150747060186627967, первый байт сида 29h, дальше мне лениво.
комментариев: 9796 документов: 488 редакций: 5664
Сдвиг влево на 7 будет давать изменения с каждыи битом, кратные 27, аналогичные умножению, а с минусом исходного seed замена байта на входе будет менять один байт на выходе в этом же месте. XOR с одинаковой константой между двумя повторами тоже можно учесть. Сдвиг вправо на 56 бит даст ненулевой результат только после числа 256 — можно много чего придумать, чтобы подобрать результат на сокращённом числе вариантов, но это больше по части оптимизации битовых операций. Может кому-то это всё и интересно пробовать.
Много слов, a xватило бы одной 64-битной цифры.
Неправильно.
В приведенной функции биты распространяются только влево и только <<7; прохождение переноса через 7 бит маловероятно; так что...