id: Гость   вход   регистрация
текущее время 18:31 29/03/2024
Автор темы: Гость, тема открыта 29/09/2014 23:29 Печать
Категории: криптография, алгоритмы, симметричное шифрование
создать
просмотр
ссылки

Потоковый шифр


Требуется сделать потоковый шифр с такими свойствами:
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 бит гаммы требуется два выполнения шифра и одно выполнение хеш функции.


Покритикуйте предложенную схему.


http://www.zas-comm.ru


 
На страницу: 1, 2 След.
Комментарии
— Гость (30/09/2014 04:52)   <#>

Зачем? Чужие мысли же плохо помогают при отсутствии собственных.
— unknown (30/09/2014 22:24, исправлен 01/10/2014 14:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Сейчас везде, где только можно, используют блочный шифр (AES) в самом простом потоковом режиме — режиме счётчика. Это считается хорошей практикой, и теоретически с этим никаких проблем нет. Не встречал ни одной публикации, где-бы объяснялось, почему счётчик — это плохо и нужно городить какие-то более навороченные конструкции поверх. Если блочный шифр неразличим от идеального, то и со счётчиком, там где можно его использовать, всё хорошо; если различим — то надо менять сам блочный шифр, а не городить перестраховки на уровне режима шифрования.


Насчёт «чужих мыслей», по аналогии с предыдущим тредом как-то так и есть. Если где-то кто-то опубликует убедительные доказательства, что режим счётчика — это фундаментально плохо, тогда есть смысл смотреть дальше. А пока всех вроде как устраивают решения на основе «чужих мыслей» счётчика и без наворачивания велосипедов поверх.



Потоковый шифр без произвольного доступа? Такое сейчас стараются не использовать. Похожие по набору требований конструкции используются в CSPRNG с перетиранием предыдущих использованных состояний, но не называют их потоковыми шифрами с особыми свойствами.


Хотя, действительно, зачем пересказывать «чужие мысли». А то, начну страдать от того, что своих велосипедогенераторов нет.


P.S.: Ошибся, есть :) Правда, только для демонстрации возможности реализации определённой концепции для очень экзотического случая. В ходе обсуждения одной темы возник оффтопик по обслуживанию согласованных одноразовых блокнотов на CPUF-носителях посредством подстраховочного протокола, обеспечивающего переход от инф.-теоретической стойкости к вычислительной в случае компрометации оборудования. Возникло предположение об использовании некоего режима шифрования, который очень похож по требованиям на описываемый вами, была рассмотрена возможность реализации конструкции на основе Sponge/Keccak.

— ZAS (01/10/2014 19:08)   <#>
Сейчас везде, где только можно, используют блочный шифр (AES) в самом простом потоковом ршежиме — режиме счётчика. Это считается хорошей практикой, и теоретически с этим никаких проблем нет. Не встречал ни одной публикации, где-бы объяснялось, почему счётчик — это плохо


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

2. Блочный шифр ограничен. Одно и то же значение cчетчика при всех возможных ключах будет отображено не на любое, а на какое-то подмножество возможных выходных значений. То есть размер ключа должен быть существенно больше размера блока.

В результате СTR режим довольно неэффективный по размеру состояния и по вычислительным затратам; безопасный при соблюдении ограничений. Произвольный доступ тоже является недостатком в ряде случаев.

Возникло предположение об использовании некоего режима шифрования, который очень похож по требованиям на описываемый вами, была рассмотрена возможность реализации конструкции на основе Sponge/Keccak.


Только и слышно про AES/Keccak. Sponge при элегантности и простоте концепции имеет большой оверхед по размеру состояния; вопросительную вычислительную эффективность; стойкость cущественно зависит от используемой функции. Т.е. sponge по сути еще один режим использования блочного шифра. AES – математически строгая оптимизация на тему сомнительной целевой функции. Такое впечатление, что подобрали задачу под математику; а не наоборот.
— unknown (01/10/2014 21:37, исправлен 01/10/2014 21:49)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Это т.н. тривиальные различители. В подавляющем большинстве областей применения они не представляют собой никаких теоретических или практических сложностей. По ним выход идеальной PRF можно различить от счётчика только за 2n/2 шагов, где n — размер блока (внутреннего состояния) выхода. Так все в курсе, что 264 блоков открытого текста в режиме счётчика потоком на одном ключе шифровать нельзя, а больше 264 ключей тоже маловероятно, что кто-то способен использовать.



Зато самый простой по доказательствам и по реализации.



На практике до пределов этих ограничений никто и не доходит, они с лихвой покрывают все мыслимые потребности. А в том подавляющем большинстве случаев, где эти ограничения допустимы, он ещё и эффективен.



Лёгкость распараллеливания и быстродействие тоже иногда в узком наборе случаях пытаются намеренно ухудшить (по возможности, строго параметризированно), например в PBKDF. Для вашего случая можно запихать шифр в CSPRNG, но там действительно будут проблемы с размером блока (внутреннего состояния). Для таких случаев и создали продвинутые режимы Keccak.



Так и было до создания Keccak. Авторы подобрали эффективную, хотя и несколько заоптимизированную функцию, не без своих проблем, но проблему оверхеда решили, пусть и с некоторой натяжкой.



А разве может быть как-то по другому? Это делали специально, потому что это хорошо, правильно и всем понравится криптографы лучше всего знают, как проектировать и анализировать стойкость именно блочных перестановок, в отличие от всего остального. Для Sponge доказано, что если внутренняя бесключевая перестановка неотличима от идеальной, то и все Sponge-режимы неотличимы от идеальных до границ, задаваемых соотношением "Flat Sponge Claim". В любом блочном шифре такой же подход: раундовая функция должна обладать определёнными функциями стойкости, неразличимыми от идеальных путём перебора после r раундов.



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



Честно говоря, совершенно непонятно, что вы можете предложить лучше этого, для каких условий, для каких задач, по каким критериям. Также как и в ряде других ваших вопросов, непонятно, чем кроме NIH-синдрома продиктовано желание создавать и предлагать на рассмотрение местной публике какие-то странные, вычурные, маргинальные немейнстримные, плохо обоснованные криптоконструкции взамен существующих и теоретически обоснованных.

— ZAS (01/10/2014 22:35)   <#>
>В результате СTR режим довольно неэффективный по размеру состояния и по вычислительным затратам;


Зато самый простой по доказательствам и по реализации.


A вот Бернштейн сделал хеш функцию в режиме счетчика (Salsa/ChaCha); чем избавился от различителя по биективности и от лишних проблем реализации блочных шифров (ключевое расписание, эффективная обратная функция...).
Теперь применим вместо счетчика состояние другой хеш функции, которое, в свою очередь, будем перехешировать от счетчика. Получаем шифр, работающий только вперед. Дальнейшие построения – вопрос оптимизации.

Честно говоря, совершенно непонятно, что вы можете предложить лучше этого, для каких условий, для каких задач, по каким критериям.


Cм. начало треда.

непонятно, чем кроме NIH-синдрома продиктовано желание создавать и предлагать на рассмотрение местной публике


Пробовал предложить местной публике детский, смешной шифр:
https://www.pgpru.com/forum/prakticheskajabezopasnostj/zascommunicator?p=7&show_comments=1#comments
Никто ничего не заметил. Криптографы :)

немейнстримные, плохо обоснованные криптоконструкции взамен существующих и теоретически обоснованных.


Зачем что-то писать. Есть букварь. Все написано от "A" до "Я" ?

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


Мне интересны следующие темы:

1. Универсальный масштабируемый по размеру ключа и блока примитив блочного шифра. Предельно простой в реализации; эффективность второстепенна.

2. Aлгоритмы с минимальным оверхедом по памяти. Идеально чтобы вcя требуемая память была равна размеру блока + размер ключа.

3. Обьединение шифров с целью перестраховки. Например, блочный шифр собирается произвольным образом из разнородных примитивов на основе ключа. Чтобы нельзя было раз и навсегда провести подготовительные рассчеты.
— unknown (02/10/2014 11:07, исправлен 02/10/2014 11:10)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Вам был дан ответ, повторяющий более общую позицию, вынесённую в FAQ.



Сразу же непонятен первый пункт — это что, незаконченное предложение?


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

— Гость (02/10/2014 13:47)   <#>

Клиент так непроходимо туп, что не может сослаться на конкретный комментарий, но ЧСВ и бравада скоро не поместятся в форум.
— ZAS (02/10/2014 18:30)   <#>
> Пробовал предложить местной публике детский, смешной шифр

Клиент так непроходимо туп, что не может сослаться на конкретный комментарий, но ЧСВ и бравада скоро не поместятся в форум.


Как обычно, совсем нечего сказать по делу?

Вот игрушечный потоковый шифр на две строчки. Найдите ключ seed.
Покажите, что вы специалист, а не ученый попугай, научившийся повторять AES, Keccak и другие умные слова.

http://www.zas-comm.ru




Начало генерируемой гаммы (256 байт):

— Гость (04/10/2014 07:43)   <#>
Клиент по-прежнему думает, что ему здесь кто-то чем-то обязан?
— SATtva (04/10/2014 09:06)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Действительно странно. Приходите на форум, выкладываете очередной велосипед, просите критики/советов. Велосипед критикуют с принятых в этом форуме позиций. Вы начинаете капризничать, что такие советы и критика Вас не устраивают, и "кто вы тут такие вообще?" и "чего добились?". В чём смысл всего этого действа, кроме почёсывания ЧСВ попытки самоутверждения? Одно дело, если б это был единичный эксцесс, но ведь воспроизводится в точности из раза в раз. Ну, окей, если местная публика не удовлетворяет, пишите в IACR более подходящий шифрпанковский форум, где Ваши велосипеды оценят должным, с Вашей точки зрения, образом, никто ж здесь не держит.
— ZAS (04/10/2014 17:35)   <#>
Клиент по-прежнему думает, что ему здесь кто-то чем-то обязан?


Человек, cчитающий себя специалистом, по крайней мере обязан вести себя прилично. Особенно если специалистом не является :) Так и думал, что окажется слабо решить элементарную задачу. В таком случае, какой смысл разговаривать о высоких материях.

Cдаетесь? Привести решение?
— SATtva (04/10/2014 18:03)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118

Ваши бы слова да богу в уши. Почему же автор этих строк считает, что на него данная обязанность не распространяется?


Присоединяюсь к вышеозвученному вопросу: с чего Вы решили, что Вам здесь должны что-то доказывать? Что Вы сделали, чтобы проявить к себе достаточный интерес? Стабильно наблюдаю только апломб и ничем, помимо мнения автора, не подкреплённые утверждения.
— Гость (04/10/2014 22:25)   <#>
Ок, все лохи, тогда чего же ты Дартаньян тут делаешь?
ЗЫ: обратная функция будет seed = (seed ^ 0x5e62a7e83848d96b) * 9150747060186627967, первый байт сида 29h, дальше мне лениво.
— unknown (04/10/2014 23:58, исправлен 05/10/2014 00:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Сдвиг влево на 7 будет давать изменения с каждыи битом, кратные 27, аналогичные умножению, а с минусом исходного seed замена байта на входе будет менять один байт на выходе в этом же месте. XOR с одинаковой константой между двумя повторами тоже можно учесть. Сдвиг вправо на 56 бит даст ненулевой результат только после числа 256 — можно много чего придумать, чтобы подобрать результат на сокращённом числе вариантов, но это больше по части оптимизации битовых операций. Может кому-то это всё и интересно пробовать.

— ZAS (05/10/2014 03:47)   <#>
...с чего Вы решили, что Вам здесь должны что-то доказывать...


Много слов, a xватило бы одной 64-битной цифры.

обратная функция будет seed = (seed ^ 0x5e62a7e83848d96b) * 9150747060186627967, первый байт сида 29h


Неправильно.

Сдвиг влево на 7 будет давать изменения с каждыи битом, кратные 27, аналогичные умножению, а с минусом исходного seed замена байта на входе будет менять один байт на выходе в этом же месте. XOR с одинаковой константой между двумя повторами тоже можно учесть.


В приведенной функции биты распространяются только влево и только <<7; прохождение переноса через 7 бит маловероятно; так что...
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3