Алгоритмы решения проблемы булевой выполнимости (SAT — от Satisfiability) и реализующие их средства (SAT‑решатели) позволяют определить выполнимость конкретной булевой формулы — существует ли такой набор определенных булевых значений («ложь»/«истина») переменных формулы, при которых результат формулы становится истинным.

Проблема булевой выполнимости хорошо изучена; существуют различные методы сведения разного рода частных задач к формулировке на их основе конкретной булевой формулы и последующего решения определенного экземпляра задачи с помощью алгоритмов решения проблемы булевой выполнимости. Алгоритмический аппарат также активно развивается; в частности, предложены эффективные алгоритмы, позволяющие автоматизировать поиск значений переменных, приводящих к решению проблемы булевой выполнимости [1]. Алгоритмы, лежащие в основе SAT‑решателей, хорошо распараллеливаются, что позволяет эффективно использовать вычислительные кластеры [2].

В анализе криптографических алгоритмов существует достаточно много задач, которые могут быть сведены к решению проблемы булевой выполнимости, что позволяет использовать хорошо изученный математический и эффективный алгоритмический аппарат решения SAT‑задач для доказательства криптографических свойств (или для получения информации о криптографических свойствах) анализируемого алгоритма. В этой статье мы совместно с моей коллегой — ведущим аналитиком компании «Актив» Мариной Скоробогатовой — подготовили небольшой обзор применений подхода сведения задач криптоанализа к SAT‑задачам, который и предлагаем вам под катом.

Приветствую, Хабр!  В анализе криптографических алгоритмов достаточно часто используется понятие оракула. Оракул – это некоторая гипотетическая вычислительная сущность, которая может мгновенно выполнять конкретные требуемые криптоаналитику операции. Например, выдавать истинно случайные числа (случайный оракул), или зашифровывать/расшифровывать данные на некотором априори известном оракулу ключе шифрования (соответственно, оракул зашифрования/расшифрования). 

Предлагаю в этой статье пойти дальше и рассмотреть оракул, способный найти прообраз (точнее, совокупность возможных прообразов) заданного хеш-кода конкретной хеш-функции. Поскольку хеш-функции часто используются в более сложных конструкциях, предлагаем посмотреть и порассуждать, как наличие такого оракула влияет на свойства вышележащих криптографических механизмов. В качестве их примера рассмотрим конструкции HMAC (Hash-based Message Authentication Codes – коды аутентификации сообщений на основе хеширования).

Приветствую, Хабр!

Напомню, что в августе текущего года Институт стандартов и технологий США NIST выпустил стандарт NIST SP 800-232 [1], описывающий четыре низкоресурсных криптографических алгоритма на базе семейства алгоритмов Ascon:
· алгоритм аутентифицированного шифрования с присоединенными данными Ascon-AEAD128;
· три алгоритма хеширования: Ascon-Hash256 (классическая хеш-функция), Ascon-XOF128 (хеш-функция с переменным размером выходного значения) и Ascon-CXOF128 (хеш-функция с кастомизацией и переменным размером выходного значения).

Данная статья из двух частей посвящена детальному обзору вышеупомянутого стандарта. В первой части статьи было подробно описано внутреннее преобразование, общее для всех стандартизованных алгоритмов, и разобрана верхнеуровневая структура алгоритма Ascon-AEAD128. В этой, заключительной, части предлагаю Вашему вниманию подробное рассмотрение структуры алгоритмов хеширования, а также обзор рекомендаций и ограничений по применению алгоритмов, описанных в NIST SP 800-232.

Приветствую, Хабр!

Совсем недавно – в августе текущего года – Институт стандартов и технологий США NIST выпустил стандарт NIST SP 800-232 [1], описывающий четыре низкоресурсных криптографических алгоритма на базе семейства алгоритмов Ascon:

· алгоритм аутентифицированного шифрования с присоединенными данными Ascon-AEAD128;
· три алгоритма хеширования: Ascon-Hash256 (классическая хеш-функция), Ascon-XOF128 (хеш-функция с переменным размером выходного значения) и Ascon-CXOF128 (хеш-функция с кастомизацией и переменным размером выходного значения). 

Предыдущий опыт показывает, что криптографические стандарты США после их принятия обычно широко используются во всем мире, поэтому данный документ может представлять значительный интерес и достоин детального разбора (краткий обзор стандарта NIST SP 800-232 уже был опубликован на Хабре ранее здесь), который я и предлагаю вам в двух частях в этой (и следующей) статье.

Приветствую, Хабр!

Структура криптографических алгоритмов, названная ее авторами «губкой» (sponge), была предложена в 2007 году. С тех пор на базе структуры криптографической губки было разработано достаточно много известных криптоалгоритмов.

Эта структура была детально исследована и показала высокую криптографическую стойкость основанных на ней алгоритмов (при грамотной разработке и реализации), а также экономичность – относительно низкие требования к ресурсам. Кроме того, было предложено несколько модификаций структуры, позволяющих существенно расширить сферу ее применения.

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

Приветствую, Хабр! В моей предыдущей статье были описаны принятые в прошлом году стандарты США FIPS (Federal Information Processing Standard — Федеральный стандарт обработки информации — аналог стандартов ГОСТ Р в России) на постквантовые алгоритмы электронной подписи (FIPS 204 и FIPS 205) и инкапсуляции ключей (FIPS 203). Данные криптостандарты были приняты в результате тщательного анализа и отбора алгоритмов в рамках открытого конкурса, проводимого Институтом стандартов и технологий США NIST; данный конкурс также был описан в предыдущей статье.

Стандарты FIPS 203 [1] и FIPS 204 [2] описывают алгоритмы, основанные на применении структурированных алгебраических решеток, тогда как алгоритм, стандартизованный в FIPS 205 [3], базируется на стойкости нижележащих хеш‑функций; данный алгоритм называется Stateless Hash‑Based Digital Signature Algorithm (SLH‑DSA) — алгоритм электронной подписи на основе хеширования без сохранения состояния. Стоит сказать, что данные алгоритмы стали не первыми постквантовыми криптоалгоритмами, стандартизованными в США, — еще в 2020 году в США был издана «специальная публикация» (SP — Special Publication — аналог рекомендаций по стандартизации в России) NIST SP 800–208 [4], описывающая несколько алгоритмов электронной подписи с сохранением состояния, также основанных на хеш‑функциях.

Далее в статье — описание и схемы алгоритмов, описанных в NIST SP 800–208, а также небольшой анализ особенностей алгоритмов данного класса.

Приветствую, Хабр!

В своей предыдущей статье (посвященной оценке необходимости срочного перехода на постквантовые криптоалгоритмы) я упомянул о принятых в США стандартах на постквантовые алгоритмы электронной подписи и обмена ключами. Данные стандарты были приняты в августе прошлого года (а перед этим они в течение года проходили оценку криптологическим сообществом в виде драфтов), при этом Институт стандартов и технологий США NIST анонсировал принятие дополнительных (альтернативных) постквантовых криптостандартов в будущем.

Поскольку принятие стандартов на постквантовые криптоалгоритмы можно считать весьма значительным событием в сфере асимметричной криптографии, а также принимая во внимание предполагаемый переход с традиционных на вышеупомянутые стандарты на горизонте в несколько лет (причем не только в США, но и в той значительной части мира, которая ориентируется на стандарты США), предлагаю вашему вниманию в данной статье описание (помимо описаний, я попытался схематично изобразить основные преобразования – под катом много схем с пояснениями) алгоритмов, на которых основаны постквантовые криптостандарты США, а также краткое обсуждение ближайших перспектив выхода новых стандартов на постквантовые криптоалгоритмы и рекомендаций по переходу с традиционных криптографических алгоритмов на постквантовые. Перечень текущих стандартов и рекомендаций NIST в части асимметричной криптографии со ссылками на их официальные публикации приведен в списке литературы к данной статье.

Приветствую, Хабр! Долгое время я принадлежал к числу тех, кто скептически относится к возможностям квантового криптоанализа в частности и квантовых вычислений вообще. Мое отношение к этому вопросу кардинально изменилось после того, как я услышал один из докладов на прошедшей конференции «РусКрипто», авторы которого очень четко показали преимущества криптоанализа на основе гибридных вычислений, совместно использующих традиционные и квантовые компьютеры, по сравнению с классическим криптоанализом.

Дальнейшие события прошедшего года, включающие в себя как усиление возможностей квантовых вычислений «в железе», а не только на бумаге, так и активные действия по разработке и стандартизации постквантовых криптоалгоритмов, показали, что далее игнорировать или относиться скептически к квантовым вычислениям/криптоанализу губительно.

Предлагаю вашему вниманию статью с анализом степени срочности перехода на постквантовые алгоритмы. Справедливости ради, я приведу и недавние высказывания известных экспертов-скептиков, но основная мысль статьи состоит в том, что откладывать далее переход на постквантовые криптоалгоритмы невозможно – начинать их реализацию и думать об их внедрении необходимо прямо сейчас, чтобы, скажем, через 5 лет такой переход был уже осуществлен. Иначе можем опоздать (прежде всего, из-за усиливающихся с каждым годом возможностей гибридных вычислений).

Подробности – далее.

Приветствую, Хабр! Хотелось бы этой статьей продолжить обзор нефинансовых применений блокчейн-технологий, начатый мной ранее на примере использования блокчейна для хранения идентификационных данных. Рассмотрим здесь существующие подходы по применению блокчейна в системах Интернета вещей различного назначения.

Казалось бы, между ресурсоемким по своей природе блокчейном и Интернетом вещей, построенном на использовании устройств с ограниченными ресурсами, лежит огромная пропасть. Однако многие из свойств блокчейна оказались настолько востребованными в Интернете вещей, что появилось целое направление блокчейн-технологий – низкоресурсный блокчейн (Lightweight Blockchain, LWB), в рамках которого было предложено множество подходов к созданию блокчейнов с пониженными требованиями к ресурсам и, следовательно, к их адаптации для реализации в системах Интернета вещей и, в частности, в устройствах с низкими вычислительными ресурсами.

Опишем далее, какие же свойства блокчейна оказались полезными для Интернета вещей, по каким направлениям идет создание низкоресурсных блокчейнов и как они впоследствии применяются.

Приветствую, Хабр! Моя предыдущая статья была посвящена формализованным критериям выбора базовой технологии хранения и обработки данных, совокупность которых позволяла ответить на вопрос, использовать ли в конкретной системе блокчейн-технологии или ограничиться хорошо изученными СУБД. При этом ответ на данный вопрос при использовании формализованных методов выбора мог быть получен именно на основе технических факторов, не принимая во внимание различные «политические» аспекты выбора, такие как, например, повышенный информационный шум, продолжающийся вокруг блокчейна.

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

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

Приветствую, Хабр! В очередной раз возникло желание обсудить блокчейн‑технологии, хотя им и было посвящено уже немало публикаций на Хабре (да и, несомненно, их еще будет много в дальнейшем).

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

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

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

В этой статье мы рассмотрим достоинства и недостатки блокчейн‑технологий и попытаемся классифицировать сферы их применения, после чего дадим обзор формализованных методов выбора: «блокчейн или не блокчейн».

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

Различные методы эволюции ключей (терминология не устоялась, предпочитаю использовать такой перевод словосочетания «key-evolving techniques») асимметричных криптоалгоритмов позволяют защититься от компрометации секретных ключей путем периодической модификации ключевых пар. Подобная защита направлена не на предотвращение компрометации секретного ключа, а на минимизацию последствий такой компрометации: поскольку ключи периодически модифицируются, эволюционируют, данные методы позволяют ограничиться отрицательным воздействием компрометации ключа на свойство целостности или конфиденциальности сообщений, зашифрованных или подписанных только в течение определенного, относительно короткого периода, оставляя защиту сообщений других периодов ненарушенной. Большинство протоколов с эволюцией ключей подразумевает достаточно активный обмен сообщениями между сторонами защищенного обмена данными. При этом бывают сценарии, когда возможности для интерактивного взаимодействия у сторон отсутствуют.

Далее предлагаю обсудить различные известные методы эволюции ключей (обеспечивающие различные полезные свойства криптосхем: от секретности в будущем до устойчивости к вторжениям), после чего описать возможный вариант протокола модификации ключевых пар для неинтерактивных применений. 

Приветствую, Хабр! Меня зовут Сергей Панасенко, я работаю в компании «Актив» директором по научной работе. По роду занятий мне достаточно часто требуется знание (а иногда и решение вопросов практического применения) нормативных документов регуляторов в области ИБ, в том числе приказов ФСТЭК России, которые устанавливают требования по защите данных в информационных системах различного назначения (подробнее о них – под катом), а также меры по защите информации, применимые для обеспечения соответствия данным требованиям. Одна из таких мер – контроль перемещения машинных носителей информации за пределы контролируемой зоны, вызвала мой  особый интерес. Данная мера выглядит важной для обеспечения безопасности, но ее реализация напрямую (проверка сотрудников на выходе с предприятий) выглядит весьма затруднительной: носители (для определенности – USB-флешки) становятся всё более миниатюрными, и проверка их отсутствия у выходящего с территории сотрудника может превратиться в проблему и для сотрудников, и для проверяющих.

Вместо этого возникла идея определения местонахождения носителей внутри контролируемой зоны по принципу «белого списка», которой захотелось поделиться с вами. Буду признателен за обратную связь и полезные замечания.

Итак, начнем.