Привет!
Хотелось бы в одной статье вкратце рассказать о достижениях математиков, которыми мы уже пользуемся или скоро будем.
Начнем
Post-Quantum crypto
Ни для кого не секрет, что грядут квантовые компьютеры. И как только они станут работать в полную силу, публичноключевой криптографии в современном её понимании придет конец. RSA, DSA, ECC, DH. Все современные популярные криптопримитивы для обмена ключами и подписей станут мусором. К счастью, есть свет в конце тоннеля и в последние годы идут активные исследования алгоритмов, устойчивых к взлому на квантовых компьютерах. Проводятся ежегодные конференции на эту тему и уже есть первые рекомендации по алгоритмам, которые можно использовать для противодействия квантовым компьютерам.
Многие из этих алгоритмов давно существуют и хорошо изучены. McEliece, например, создан в 1978 году. Hash based signatures (слайды об XMSS signatures, pdf) тоже родом из 80х. Единственное — размеры ключей, передаваемых данных, скорость работы и т.п. у асимметричных алгоритмов могут быть не такими удобными как сейчас.
Nonce-misuse-resistance и AEAD-режим блочного шифрования
Довольно старая штука, но про неё мало кто знает. В 2000 году была предложена схема, которая позволяла получить сообщение, состоящее из зашифрованных данных, незашифрованной служебной части, например, размера пакета, и некоего значения, зависящего от ключа, которое позволяло аутентифицировать всё сообщение целиком. Этот режим шифрования оказался настолько удобным, что в 2007 году NIST приняла одну из его реализаций — AES GCM как стандарт. В современных процессорах intel даже инструкция специальная есть PCLMULQDQ помимо AES-NI, которая позволяет реализовывать этот режим очень шустрым образом.
Проблема в том, что все AEAD алгоритмы обязательно требуют некое дополнительно значение nonce, которое обязано быть разным для разных сообщений, шифруемых одним ключом. Не обязательно случайным, просто разным. Иначе ваша криптография превратится в тыкву. Т.е. либо использовать счетчик какой-то и хранить состояние, либо использовать случайные nonce и надеяться, что они не совпадут. Буквально на днях группа исследователей опубликовала атаку на TLS, которая как раз эксплуатирует уязвимость nonce reuse. Там и Visa уязвима и еще половина всех серверов в интернете, довольно серьезная дырка.
Чтобы обезопасить таких вот криворуких реализаторщиков хороших алгоритмов, устроили крипто контест CAESAR, целью которого является найти лучший алгоритм AEAD, в том числе защищенный от атак типа nonce reuse/misuse.
Самыми перспективными считаются HS1-SIV (PDF) и AES-GSM-SIV (pdf)
Второму так вообще не нужно ничего нового, он использует уже существующие инструкции AES-NI и PCLMULQDQ, поэтому очень шустрый. Даже реализацию запилили на гитхабе.
Noise protocol
Если вы следите за новостями, то в курсе, что WhatsApp включил шифрование для всех по умолчанию. Используют они лучший, на мой взгляд, протокол Signal, но это не самое интересное в новости.
Создатель протокола Signal Trevor Perrin так же разработал легковесную замену TLS, noise protocol. Это не просто протокол, это фреймворк для построения безопасных протоколов передачи данных. И WhatsApp используют его для сетевого уровня взаимодействия. Он гораздо проще TLS и гораздо более дуракоустойчив. Вот, даже видео сняли с объяснением того, как он работает
Реализации уже есть на C, Go, Haskell и Rust(от самого автора). Будет приятно увидеть реализацию у какого-нибудь гугла, вещь стоящая.
ARGON2
Я уже ранее писал об этом memory hard алгоритме для получения хэшей паролей. Повторюсь — хватит использовать просто хэш(соль+пароль), используйте нормальные KDF вроде scrypt, bcrypt или превосходящий их по характеристикам ARGON2. Из нового — появились хорошие слайды (pdf) с последней конференции, и не стоит забывать о коинах на его основе. Может получиться довольно перспективная валюта без asicов.
Реверс инжиниринг S-box шифра «Кузнечик»
Интересный анализ новых российских алгоритмов шифрования и хеширования «Кузнечик», «Стрибог» и «Стрибоб» от Alex Biryukov, Leo Perrin, Aleksei Udovenko показывает, что ключевой элемент — таблица замены размером 16x16 была сгенерирована не случайным образом, как утверждают разработчики, а с помощью скрытого алгоритма (pdf)
Довольно интересный результат, который наводит на подозрения о скрытом бекдоре. Иначе, зачем врать?
На этом у меня всё, увидимся в новых дайджестах!
P.S.
Еще одна хорошая новость от BalinTomsk
Комментарии (26)
Ivan_83
20.05.2016 13:23+3По поводу таблиц для кузнечика и стрибога, моя догадка в том, что они использовали один и тот же ГСПЧ/алгоритм, а исследователи нашли в его выходе закономерности.
Те из этого не следует что там есть какие бэкдоры, в том же кузнечике ещё и ключ используется, а в хэше вроде оно на всякие коллизии не влияет.
Учитывая общий уровень написания документации и примеров думаю что это скорее разгельдяйство, чем умысел.
И забавное/печальное о стрибоге: https://www.pgpru.com/novosti/2014/oshibkavstrukturerossijjskojjheshfunkciistribogprivelakejopolnoraundovomuvzlomu
оно по важнее таблиц будет.
BalinTomsk
20.05.2016 17:36+1Мне кажется вы упустили еше одну новость:
Учёные из университета Техаса предложили новый метод генерации случайных чисел, который позволяет комбинировать две относительно некачественные последовательности случайных чисел и получать качественный результат. Открытие может иметь далекоидущие последствия в области криптографии.
http://eccc.hpi-web.de/report/2015/119/
Исследования в этой области ведутся не одно десятилетие, но специалисты полагают, что в данном случае был совершён прорыв. До сих пор функции, которые генерируют качественные случайные последовательности на основе пары менее качественных, нуждались в более качественном «сырье».
Научная работа, описывающая новый метод, была опубликована в марте, а в июне её авторы, Дэвид Цукерман и Ишан Чаттопадхья, расскажут о своём открытии на симпозиуме по теории алгоритмов, которую проводит международная Ассоциация вычислительной техники (ACM).
В работе Цукермана и Чаттопадхьи предложена функция, принимающая случайные последовательности на n бит из двух источников со значениями мин-энтропии не менее logCn для достаточно большого значения C и выдающая случайный бит с ошибкой n??(1). Лучший метод, известный ранее, требовал более качественных источников с мин-энтропией 0,499n.
«Мы продемонстрировали, что если у вас есть два низкокачественных источника случайных чисел, — а источники невысокого качества куда проще найти, — и они независимы друг от друга и не коррелируют между собой, то их можно комбинировать и получить случайное число высокого качества», — объясняет Цукерман.
https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/
Scratch
20.05.2016 17:43Принято, спасибо ) Я как раз рассчитывал на то, что добрые комментаторы дополнят дайджест новостями, которые я пропустил
El_corona
20.05.2016 18:50Простите за комментарий из read-only, но нет ли каких-либо достижений по криптографии на решётках? Субъективно, про них много говорят на различных докладах IACR
Scratch
20.05.2016 18:55Как видно по слайду вначале статьи, NTRUEncrypt, который на решетках, активно исследуется. На данный момент есть рекомендуемые параметры (в википедии) которые считаются безопасными
Stas911
20.05.2016 19:51+1А можно популярно — чем постквантовые алгоритмы принципиально отличаются от тех, которые превратятся в мусор? У них просто вычислительная сложность драматически выше?
Scratch
20.05.2016 21:10Не обязательно. Просто квантовые компьютеры в определенных случаях могут некоторые вещи считать сильно быстрее обычных компов, за счет своей квантовой природы. А есть алгоритмы, которые не подвержены ускорению с помощью квантовых механизмов, их как раз активно изучают
VaalKIA
20.05.2016 22:38Очень давно, где-то читал новость, про какие-то суперразреженные хеши (возможно новость была о премии за это дело), которые могут использоваться для криптографии. Не могу никаких концов в инете найти, а врезалось в память, может кому-то это о чём-то говорит?
quverty
22.05.2016 12:42Вроде, на симметричные схемы квантовая криптография не особо покушается, там так называемые «медленные квантовые алгоритмы» типа Гровера которые интересны скорее с точки зрения теории. Но ведь, наверное, есть случаи когда нужны именно асимметричные схемы вместо RSA? Вот те-же банковские операции, что с ними?
Scratch
22.05.2016 13:12Ну, вообще именно из-за гровера рекоммендуют увеличивать размер ключей до 256 бит. Вчера как раз прочитал, что доказали его оптимальность. По поводу банковского сектора — там уже во всю орудует NTRU, жалко что он патентованый
quverty
22.05.2016 13:44Спасибо. Посмотрел — NTRU какой-то решёточный. Но решёточные же вроде и открытые есть.
Scratch
22.05.2016 18:28да чет не очень их много https://en.wikipedia.org/wiki/Lattice-based_cryptography
quverty
22.05.2016 20:03В википедии ещё пишут, что теперь и у NTRU есть open source реализация. Кого тогда патент волнует? Но там даже не особо понятно из описания, почему он именно решёточный.
Scratch
22.05.2016 21:24Мне кажется, из описания предельно понятно, почему он решеточный https://en.wikipedia.org/wiki/NTRUEncrypt Потому что, основан на проблеме поиска кратчайшего вектора в решетке. На счет реализаций хз. Реализации может и открытые, но сам алгоритм то патентованый. NTRU под GPL, поэтому опен сорс может юзать его. https://github.com/NTRUOpenSourceProject/ntru-crypto
quverty
22.05.2016 21:35Меня смутило, что там написано:
Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices.
То есть связан, но не эквивалентен. Алгоритм, как и RSA использует умножение, хотя и не двух чисел, такая сборная солянка, так что мне например не всё «предельно понятно». В том прагматическом смысле, что почему вдруг через некоторое время кто-нибудь не найдёт быстрый квантовый алгоритм.
lightjedi
24.05.2016 10:40+1Я бы немного подкорректировал:
— HS1-SIV вряд ли считается самым перспективным, он весьма корявый и security level у него низкий (в одном из вариантов — 28 бит всего)
— GCM-SIV не является участником CAESAR, но авторы активно его продвигают, и он скоро станет стандартом IETF
— атака Альвена и Блоки на Argon2, на которую вы дали ссылку, уменьшает стоимость перебора на ASIC в два раза. Это хуже, чем результат авторов (в три раза).
Monnoroch
Если я помню правильно, квантовые компьютеры могут решать факторизацию за O(exp(sqrt(n))) вместо O(exp(n)). Так что я бы не сказал, что вот прямо все, всей криптографии конец. Скорее наоборот. Получается, нужно просто увеличить длину ключа возведением текущей длины в квадрат. Получится порядка одного-пяти мегабайт, что кажется большим числом, но таковым на современных коннектах на самом деле не является.
potan
Если я правильно помню, то O(exp(sqrt(n))) — это для NP-полных задач, а конкретно для факторизации чисел оценка значительно лучше.
Monnoroch
Да, я освежил тему, вы правы. Похоже, действительно придется полностью новое все придумывать.
ComradeAndrew
Не подскажите ли статью где можно наглядно посмотреть на сколько лучше?
potan
Алгоритм Шора
ComradeAndrew
И действительно сильно упрощает факторизацию.