Nist

Привет, Хабр. Недавно NIST на своем сайте объявили о старте третьего этапа стандартизации постквантовой криптографии. В третий этап прошли 3 кандидата на цифровую подпись и 4 кандидата на асимметричное шифрование. Так же были представлены 8 альтернативных кандидатов. Я подумал, что хабровчан заинтересует данное событие. Более подробнее под катом.

Немного истории

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

Это стало существенной проблемой для криптографии, так как безопасность распространенных стандартизированных систем зависит от сложности решения этих задач.
Тем не менее, квантовые вычисления довольно длительное время оставались лишь красивой абстракцией, которую не было технической возможности реализовать. Но в последнее время возможность создания квантовых компьютеров была пересмотрена и это стимулировало NIST запустить в 2016 году открытый конкурс на создание новых постквантовых стандартов. Точнее говоря, NIST заинтересовано в создании новых стандартов асимметричного шифрования (Public-Key Encryption) и цифровой подписи (Digital Signatures).

На участие в конкурсе подали заявки 69 команд со всего мира. Эта тема была широко освещена и даже были посты на хабре. Из предложенных схем во второй этап прошли всего 26. И вот, 22 июля 2020 года, были объявлены финалисты второго этапа, которые прошли дальше. Осталось всего 4 кандидата на асимметричное шифрование и 3 кандидата на цифровую подпись.

Кандидаты прошедшие в третий этап

Итак, кандидаты на новый постквантовый стандарт цифровой подписи:

• CRYSTALS-DILITHIUM Является представителем криптографии на решетках. За основу взята схема Фиата-Шамира с прерываниями. Криптоанализ сводится к решению задач Module-LWE и Module-SIS. Имеет хорошую производительность и может быть эффективно реализована на малоресурсных устройствах. NIST попросили авторов добавить набор общесистемных параметров для 5 уровня безопасности.
• FALCON Так же является представителем криптографии на решетках. Но за основу взят фреймворк GPV. Криптоанализ сводится к задаче SIS на NTRU-решетках. Главным недостатком этой схемы является сложная програмная и апаратная реализация. Схема используют вычисления над числами с плавающей запятой, что сильно усложняет как анализ стойкости к атакам по сторонним каналам, так и делает сложным реализацию для малоресурсных устройств.
• Rainbow Является предствителем криптографии на мультивариативных преобразованиях. За основу взята схема UOV. Главным преимуществом является размер цифровой подписи. Но из-за большого размера ключа эту схему рекомендуется ипользовать только для специфических задач, где размер ключей не критичен.

NIST так же заявили что хотя бы одна из схем CRYSTALS-DILITHIUM и FALCON будет стандартизирована. Таким образом, для цифровой подписи скорей всего в будущем будут использоваться схемы на основе криптографии на решетках. А для более специфических задач Rainbow.

Для асимметричного шифрования в третий этап вышли:

• Classic McEliece Является представителем криптографии на кодах исправляющих ошибки. Основная конструкция схемы была предложена еще в 1979 году и хорошо изучена. Имеет малые размеры шифротекстов, но очень большой размер ключа. Из-за чего имеет те же проблемы, что и Rainbow и рекомендуется к использованию только для специфических задач.
• CRYSTALS-KYBER Является представителем криптографии на решетках. Криптоанализ сводится к решению задачи Module-LWE. Для обеспечения стойкости к атакам с адаптивно подобраными шифротекстами используется преобразование Фуджисаки-Окамото. Имеет хорошую производительность и безопасность, но NIST так же напоминают, что Module-LWE это относительно малоизученная проблема и требует более детального криптоанализа.
  
• NTRU Является представителем криптографии на решетках. За основу взята схема NTRUEncryt, предложенная более 20 лет назад. Проблема NTRU, в отличие от Module-LWE (и других модификаций) была очень хорошо изучена, что является очень важным фактором.
  
• SABER Является представителем криптографии на решетках. Криптоанализ сводится к проблеме MLWR (Module-LWE, где вместо сложения с вектором ошибки используется
  округление по меньшему модулю). Используется преобразование Фуджисаки-Окамото, как и в CRYSTALS-KYBER.
  

В целом, ситуация аналогичная для общего использования рекомендуются схемы на основе решоток. Но NIST сделали замечание, что только одна из схем на решетках (CRYSTALS-KYBER, NTRU, SABER) будет стандартизирована.

Альтернативные схемы

Так же NIST отобрали 8 альтернативных схем, которые не вошли в финал, но являются перспективными.

Среди схем цифровой подписи:

• SPHINCS+ и Picnic являются схемами на основе симметричных криптопримитивов. Криптоанализ SPHINCS+ сводится к стойкости хеш-функций, а Picnic к NIZK и блочным шифрам. Эти схемы являются довольно новыми и малоизучеными. Но основной их недостаток все же в огромном размере подписи, что делает их неприменимым для многих задач.
  
• GeMSS Похожа на Rainbow, но основана на HFE, вместо UOV. Имеет больший размер ключа и более медленный процес подписи. Выбран в качестве альтернативы на случай нахождения уязвимостей в Rainbow.

Среди асимметричного шифрования:

• BIKE Является схемой на кодах исправляющих ошибки. Требует более детального иследования безопасности.
• FrodoKEM Является представителем криптографии на решетках. Криптоанализ сводится к проблеме LWE, которая более изучена чем Module-LWE (и другие разновидности). Имеет слишком медленные алгоритмы шифрования\расшифрования.
  
• HQC Является схемой на кодах исправляющих ошибки. Базируется на квазициклических кодах. Имеет слишком медленные алгоритмы шифрования\расшифрования.
  
• NTRU Prime Является представителем криптографии на решетках. Имеет хорошую защищенность от алгебраических атак.
  
• SIKE Является единственной схемой (среди поданных на конкурс), что базируется на изогениях эллиптических кривых. Требует более детального изучения.
  

Краткие выводы

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

Стоит заметить, что в мире уже есть стандартизированные схемы на решетках: раз ,два. Так что, скорей всего, именно криптография на решетках в ближайшие годы все больше будет вытеснять привычные RSA и ECDSA. Но в то же время в узкоспециализированных областях будут популярны иные решения.

Мэттью Стэйматс тестирует разные маски. Источник: NIST

Многие люди носят маски в общественных местах, чтобы замедлить распространение COVID-19, выполняя рекомендации центров по контролю и профилактике заболеваний. Однако маски с клапанами для выдоха не замедляют распространение инфекции. Новые видеоролики американского Национального института стандартов и технологий (NIST) демонстрируют, почему.

На видео показано, как воздушный поток проходит через маски с клапанами выдоха и без них. Материалы создал инженер-исследователь NIST Мэттью Стэйматс. Видео опубликованы вместе с сопутствующей исследовательской статьей в журнале Physics of Fluids.

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

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

Маски, которые рекомендуют для замедления распространения COVID-19, в основном предназначены для защиты людей вокруг владельца. Они улавливают выдыхаемые капли, которые могут содержать вирус, и тем самым замедляют распространение инфекции. Согласно экспертам, даже люди без симптомов должны носить маски, потому что можно переносить болезнь бессимптомно.

Это видео, созданное с использованием шлиреновой системы визуализации, показывает динамику воздушного потока для маски N95 с клапаном выдоха (слева) и маски без клапана выдоха. Воздух проходит через клапан нефильтрованным. Маски с клапанами не замедляют распространение COVID, и их не следует носить для этой цели. Источник: Мэттью Стэйматс/NIST.

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

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

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

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

Это видео создано с использованием техники светорассеяния. Ролик демонстрирует динамику воздушного потока при ношении маски N95 с клапаном выдоха (слева) и без клапана выдоха (в центре). Маски с клапанами не замедляют распространение COVID, и их не следует носить для этого. Источник: Мэттью Стэйматс/NIST.

Стэйматс создал второе видео, используя метод рассеяния света.

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

В противоположность съемке с шлирен-методом, этот ролик показывает движение капель в воздухе. Слева капли выходят и не фильтруются через клапан маски N95. В середине нет клапана, и дыхания не видно, потому что маска задержала капли. Справа маска не надета.

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

Кроме того, видео, полученные с помощью рассеяния света, можно проанализировать на компьютере так, как невозможно для шлирен-изображений. Стэйматс написал код, который подсчитал яркие пиксели в видео и использовал его для оценки числа капель в воздухе. Это не точный замер количества капель: двухмерное видео не может захватить то, что происходит в полном трехмерном объеме воздуха. Однако полученные числа показывают тенденции, которые можно проанализировать, чтобы лучше понять динамику воздушного потока, проходящего через разные виды масок.

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

Основной эффект клапанов все равно виден на этих роликах. Стэйматс надеется, что видео помогут людям с одного взгляда понять, почему маски, предназначенные для замедления распространения COVID-19, не должны иметь клапанов.