id: Гость   вход   регистрация
текущее время 13:31 28/03/2024
Автор темы: gegel, тема открыта 17/03/2014 22:53 Печать
Категории: исходные тексты
http://www.pgpru.com/Форум/Криптография/КомпактнаяС-реализацияУниверсальногоKeccakSpongeИПримерыКриптопримитивов
создать
просмотр
ссылки

Компактная С-реализация универсального Keccak Sponge и примеры криптопримитивов


Обсуждение в другой ветке затронуло тему модерн Keccak-криптографии. Тема интересная, и я с ней практически не был знаком, но после небольшого обзора источников нашел все необходимое для практическрй реализации сабжа. Так как других релизаций не оказалось (даже в качестве части мелких проектов на github). Пришлось самовольно выбрать подходящий режим F-функции и паддинг. При необходимости данные параметры можно изменить в установках.


В качестве базовой использована портабельная реализация F-фукнкции fileKeccak-compact.c
Алгоритмы функционирования Sponge взяты из работы fileDuplexing the sponge: single-pass authenticated encryption and othe applicationsfileтут в слайдах).
Использован режим, рекомендованный NIST для 512-хеша: B/R = 1600/576 и оверхед паддинга 1 байт. Работа F-функции проверяется по нескольким тестовым векторам из документа fileShortMsgKAT_512.txt


Реализован универсальный Sponge-объект, работающий как в нормальном, так и в дуплекс-режиме в зависимости от параметров запроса. Используются всего три функции:
Init, Data и Finalize. На их основены представлены примеры реализации следующих криптопримитивов (включая инкрементальные процедуры): хеширования, HMAC, KDF, PKDF, потокового шифрования, аутентифицированного однопроходового шифрования (SpongeWrap), а также генератора псевдослучайных чисел (SpongePRG).


Исходный код компилирован GCC для Linux32 и BCB для Win32 (i386) и не требует никаких внешних библиотек.


Сразу предупреждаю: тема изучалась мною с нуля и все написано за пару вечеров, так что это не более чем пример-игрушка. Я старался очень тщательно комментировать код и сделал короткое readme. Любые замечания приветствуются, хотя, боюсь, что в лучшем случае этим заинтересуются лишь единицы. Так что будем считать представленную работу вариантом самовыражения. Скачать исходники можно fileтут.


 
Комментарии
— unknown (18/03/2014 09:52, исправлен 18/03/2014 09:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Авторам пишите. Укажите, что это неофициальная демонстрационная реализация. Думаю, они и полезные замечания сделают и поправят, если что, и вообще будут рады, если кто-то возьмётся за грамотную реализацию. Заодно кто-то ещё подтянется. Они на конференции пропагандировали Keccak среди программеров, но пока никто не внял. Можете сделать себе репутацию на первенстве, если хотите.


Другой вопрос, что только после того, как будет официально стандартизирован обычный SHA-3, только после этого и будут стандартизировать все другие дополнительные режимы Keccak. При этом возможны какие-то мелкие изменения параметров. Но, по согласованию с авторами, вам будет проще внести небольшие правки в уже готовый код.

— Гость (18/03/2014 11:43)   <#>
Что-то мне RNG не нравится (файл fastpool.c), есть на мой взгляд косяки, способствующие небезопасному использованию.

1. Не учтена многопоточность (общие pool и state не защищены), при одновременном доступе будет лажа.
2. randPoolAddWord, randPoolAddBytes циклически ксорят содержимое пула с поступающими данными. Надежность этой операции как-то сомнительна. Вы уверены что поступление на вход данных с плохой статистикой, специально подобранных данных, или связанных какой-то формулой, не может уменьшать уже накопленную энтропию? На мой взгляд, на каждом поступлении энтропии надо сразу делать absorbing.
3. Слишком мало источников энтропии, по-сути безопасность целиком висит на системном RNG (и код к нему привязан).

Кстати, почему пул затирается 0xAC а не нулями? Чем обусловлен такой выбор?
— gegel (18/03/2014 12:20)   профиль/связь   <#>
комментариев: 393   документов: 4   редакций: 0
Не учтена многопоточность (общие pool и state не защищены), при одновременном доступе будет лажа

Это да, согласен. Данный пример и не планировался как полноценный системный PRG.
циклически ксорят содержимое пула с поступающими данными
Не совсем так: входящая энтропия распределяется по пулу равномерно, хотя и предсказуемо. Эта часть кода взята из генератора Циммермановского PGPFone. Идея в скорости обработки входящей энтропии: она поступает небольшими порциями, но очень часто: с обработчика перемещения мыши в GUI, устройства захвата аудио и т.п. Контролируя некоторые источники, теоретически можно уменьшить их суммарную энтропию, не смотря на используемый полином и битовый сдвиг.
На мой взгляд, на каждом поступлении энтропии надо сразу делать absorbing
По уму да, но ценой резкого снижения быстродействия. Вообще-то логично принимать решение, исходя из требований к конкретному случаю: частота ресида и приблизительное количество энтропии в порции.
Слишком мало источников энтропии
А их в коде совсем нет. Системный RNG в данном случае используется только для инициализации вместе с seed-файлом, а затем энтропия добавляется внешними вызовами randPoolAddBytes. В данном коде представлен только коллектор энтропии и генератор рандома.
почему пул затирается 0xAC а не нулями
Наверное, глупость с моей стороны: переписал с другого кода, не подумав. Принципиально никакой разницы, только лишние вопросы.

Скажу честно, я не знаком в деталях с теорией проектирования PRG, это отдельная область. Целью данного примера было реализовать приведенный в работе выше алгоритм SpongePRG + рюшечки, необходимые для примитивной демонстрации примера.
— Гость (18/03/2014 17:59)   <#>

А что, потоковому шифру на основе KeccaK уже можно доверять так же, как и хорошим блочным шифрам (типа AES и Twofish), или это просто очередной потоковый шифр с непонятной безопасностью?
— unknown (19/03/2014 09:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Исторически потоковые шифры проектировались по другой схеме в отличие от блочных. Раз они только разворачивали ключ в гамму, а подавать на вход внутреннего состояния открытый текст не нужно, то можно было на многом сэкономить. Поэтому потоковые шифры были привлекательны как быстродействующие и малоресурсоёмкие. Но вот с доказательствами стойкости действительно было плохо. И ломали их часто.

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

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

По конструкции это не должно уступать стойкости блочного шифра. Правда, если сравнивать с традиционными потоковыми шифрами Sponge совсем некорректно, то и с блочными — не вполне. Это не «очередной потоковый шифр на основе», это нечто третье по отношению к блочным и потоковым шифрам, но ближе к блочным по использованным элементам конструкции.
— Гость (19/03/2014 18:59)   <#>
А в дисковом шифровании тоже может использоваться KeccaK? Для этого уже есть какие-то режимы типа XTS? Как я понимаю, AES-CTR — это только для шифрования коммуникаций. Диск потоковыми шифрами вроде не шифруют(?).
— unknown (19/03/2014 22:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Интересовался у авторов этой темой. Они сказали, что даже если к бесключевой перестановке от Keccak приделать ключи, как я им предлагал, то работать как блочный шифр он будет, но оно проектировалось в расчёте только на быструю перестановку в одну сторону. Обратная перестановка на расшифрование будет слишком медленной.

Уже не от авторов, а чисто по своим соображениям. Есть другая возможность. Существуют теоретические и экзотические разработки, позволяющие использовать именно в дисковом шифровании псевдослучайные функции, не превращая их в перестановки и не превращая в подобие блочного шифра. В такой экзотический режим можно было бы запихнуть и Keccak, а может даже адаптировать Sponge под такой режим. Но я даже вспомнить названия этих работ и найти их не смог (совершенно не понял на чём там основана идея), когда снова заинтересовался.
— gegel (19/03/2014 23:42)   профиль/связь   <#>
комментариев: 393   документов: 4   редакций: 0
Что-то мне RNG не нравится (файл fastpool.c), есть на мой взгляд косяки, способствующие небезопасному использованию.


Полностью переписал (теперь sprng.c):
1. Добавил мутекс, теперь реализация поддерживает многопоточность
2. Убрал fastpool, теперь энтропия последовательно абсорбируется в Sponge, F-функция вызывается только при заполнении очередного блока (71 байт). Перед генерацией рандома в случае наличия необработанной энтропии, также выполняется F-функция, затем выжимаестя блок рандома. Если не весь рандом использован, и не поступало дополнительной энтропии, то при следующем запросе рандома используется оставшаяся часть старого рандома.
Вообщем, сейчас все в точности соответствует описанию SpongePRG из цитированной выше работы. Надежность выше за счет снижения быстродействия, так что непосредственно повесить ресид на обработчик перемещения мыши в данном случае вряд ли будет хорошей идеей.
Хотелось бы услышать Ваш комментарий по поводу такого варианта реализации PRG.


Также изменил переключатель режима Sponge, сделав его более гибким и логичным.

Размести код на github.

Авторам пишите. Укажите, что это неофициальная демонстрационная реализация.


Спасибо, попробую.
— Гость (20/03/2014 06:41)   <#>
Замечания по новому коду:

1. waitMutex / mutex = 0 замените на waitMutex / releaseMutex, внутри функций сделайте платформо-зависимые реализации через директивы условной компиляции. Вариант с глобальной переменной должен включаться только если платформа не опознана.
2. Скрытая ошибка: переменная mutex должна быть volatile, иначе оптимизатор может давать непредсказуемые глюки. Внимательно к этому относитесь, я уже на такое напарывался.
3. randFeed('abc') + randFeed('def') == randFeed('abcdef'), получается различитель от идеального PRNG (вопрос к unknown'у, существует ли его формальная модель?). Нужно как-то разделять разные поступления энтропии, самое простое – вызывать F каждый раз. Не уверен, является ли это уязвимостью, пусть unknown скажет.
4. Еще потенциальная уязвимость: атакующий сделавший дамп памяти, может скомпрометировать ключи сгенерированные до момента атаки. Если получить полное состояние, F отматывается назад сколько угодно раз, с восстановлением всего, что было сгенерировано вплоть до последнего ресида (а если ресид был с малой фактической энтропией, можно его сбрутить и отматывать дальше). Это очень и очень плохо. На мой взгяд, нужно затирать байты извлеченные из состояния, либо применять к пулу необратимое преобразование после каждого вызова генерации. Опять вопрос к unknown'у: рассматриваются ли подобные атаки в формальных моделях, и существует ли требование стойкости предыдущих ключей к компрометации состояния PRNG?
5. В стандарте на DRBG есть такое понятие как prediction resistance flag, этот флаг устанавливается если с момента последней генерации поступило достаточно энтропии, чтобы текущее состояние не было предсказуемо из предыдущего. На мой взгляд, стоит добавить.
6. У нас 1 глобальный инстанс генератора на весь процесс. Может стоит сделать функции работающие с состоянием PRNG во внешней структуре?
— unknown (20/03/2014 09:57, исправлен 20/03/2014 10:10)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

По п.3 — всё должно смешиваться во внутреннем состоянии. Иначе говоря, во внутреннем состоянии должно накопиться столько энтропии, что даже если дальше на вход поступает низкая энтропия (хоть одни нули), PRNG разворачивает гамму внутреннего состояния сколько угодно долго, а reseed низкой энтропией просто на неё никак существенно не влияет.


По п.4 — поэтому в Unix разделяют блокируемый по энтропии /dev/random и неблокируемый /dev/urandom. Последние исследования говорят, что блокируемый генератор не нужен.



How to Eat Your Entropy and Have it Too — Optimal Recovery Strategies for Compromised RNGs, Yevgeniy Dodis and Adi Shamir and Noah Stephens-Davidowitz and Daniel Wichs.


Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, Yevgeniy Dodis and David Pointcheval and Sylvain Ruhault and Damien Vergnaud and Daniel Wichs.


fileRandom Number Generation, Revisited, Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergnaud, Daniel Wichs.

— gegel (20/03/2014 13:41)   профиль/связь   <#>
комментариев: 393   документов: 4   редакций: 0
Замечания по новому коду

1,2 – принято, учту.
3 – в fileописании реализации SpongePRG (в начале стр. 14) авторы предлагают последовательно накапливать энтропию во входном буфере. А как вам вариант использовать для накопления полином со сдвигом из предыдущего кода (состояние его указателя неизвестно снаружи)? В любом случае вызывать каждый раз F – критическое снижение быстродействия: просто попробуйте повесить это на обработчик перемещения мыши.
4 там же, стр. 14, второй-третий абзацы. Авторы возлагают обеспечение FS на пользователя, предлагая периодически вызывать Forget() (затирая большую часть состояния и выполняя F), исходя из ситуации. В принципе, пользователь может всегда вызывать Forget() после Fetch() опять же ценой снижения быстродействия.
5 вопрос в том, есть ли надежный алгоритм оценки этого самого количества энтропии? Если ткнете носом, добавить не проблема.
6 – принято, осознаю и учту по возможности.
— unknown (20/03/2014 14:17)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Keccak должен быть самодостаточным, не надо на него ничего навешивать, тем более по выбору наугад, без обоснования.

Иначе вы в лучшем случае переизобретёте The Parazoa Family: Generalizing the Sponge Hash Functions, Elena Andreeva and Bart Mennink and Bart Preneel, да ещё скрестив это с дуплексом. Оставьте это теоретикам.

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

Или решайте, что это медленный для ваших целей генератор. Или ждите, пока не разовьют какие-нибудь распараллеливаемые режимы.
— gegel (20/03/2014 15:21, исправлен 20/03/2014 15:26)   профиль/связь   <#>
комментариев: 393   документов: 4   редакций: 0
как только вход дуплекса заполнился, нужно обязательно вызывать f

Именно так сейчас и реализовано. В принципе, этого достаточно, т.к. часто поступающая энтропия (от перемещения мыши) имеет малый размер (скажем, по несколько младших бит X и Y координат), поэтому при достаточном размере блока R функция F будет вызываться не часто.
Но суть вопроса была в другом:

randFeed('abc') + randFeed('def') == randFeed('abcdef'), получается различитель

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

— unknown (20/03/2014 21:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
randFeed('abc') + randFeed('def') == randFeed('abcdef'), получается различитель от идеального PRNG (вопрос к unknown'у, существует ли его формальная модель?). Нужно как-то разделять разные поступления энтропии, самое простое – вызывать F каждый раз.

Возможно я не понимаю, о чём здесь конкретно. Нельзя складывать по модулю или объединять выходы за пределами функции. Это уже Parazoa какая-то, а не Sponge или какой-то нетривиальный режим. В те места, куда положено закачивать в duplex-Sponge энтропию, туда и надо закачивать. Откуда надо снимать — с тех выходов и надо снимать. С учётом того, что вкачать надо больше, чем снимать, чтобы менее качественная энтропия сжималась в более качественную (т.н. «дистилляция энтропии»). Т.е., может даже вкачать в Sponge 2n байт, а снять на выходе с дуплекса n байт или меньше.
— Гость (21/03/2014 11:50)   <#>

Проще поставить ссылку на старое и более полное обсуждение этих вопросов [1], [2].
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3