Дайджест последних достижений в области криптографии. Выпуск нулевой



    Привет!
    Хотелось бы в одной статье вкратце рассказать о достижениях математиков, которыми мы уже пользуемся или скоро будем.
    Начнем

    Post-Quantum crypto


    Ни для кого не секрет, что грядут квантовые компьютеры. И как только они станут работать в полную силу, публичноключевой криптографии в современном её понимании придет конец. RSA, DSA, ECC, DH. Все современные популярные криптопримитивы для обмена ключами и подписей станут мусором. К счастью, есть свет в конце тоннеля и в последние годы идут активные исследования алгоритмов, устойчивых к взлому на квантовых компьютерах. Проводятся ежегодные конференции на эту тему и уже есть первые рекомендации по алгоритмам, которые можно использовать для противодействия квантовым компьютерам.

    image

    Многие из этих алгоритмов давно существуют и хорошо изучены. 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
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 26

      +1
      Если я помню правильно, квантовые компьютеры могут решать факторизацию за O(exp(sqrt(n))) вместо O(exp(n)). Так что я бы не сказал, что вот прямо все, всей криптографии конец. Скорее наоборот. Получается, нужно просто увеличить длину ключа возведением текущей длины в квадрат. Получится порядка одного-пяти мегабайт, что кажется большим числом, но таковым на современных коннектах на самом деле не является.
        +1
        Если я правильно помню, то O(exp(sqrt(n))) — это для NP-полных задач, а конкретно для факторизации чисел оценка значительно лучше.
          +1
          Да, я освежил тему, вы правы. Похоже, действительно придется полностью новое все придумывать.
            0

            Не подскажите ли статью где можно наглядно посмотреть на сколько лучше?

      • UFO just landed and posted this here
          0
          Да, это они конечно сплоховали. Спасибо, не знал
          • UFO just landed and posted this here
            0
            В Кузнечике и Стрибоге просто один и тот же S-box.
            +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/
              0
              Принято, спасибо ) Я как раз рассчитывал на то, что добрые комментаторы дополнят дайджест новостями, которые я пропустил
              0
              Простите за комментарий из read-only, но нет ли каких-либо достижений по криптографии на решётках? Субъективно, про них много говорят на различных докладах IACR
                0
                Как видно по слайду вначале статьи, NTRUEncrypt, который на решетках, активно исследуется. На данный момент есть рекомендуемые параметры (в википедии) которые считаются безопасными
                +1
                А можно популярно — чем постквантовые алгоритмы принципиально отличаются от тех, которые превратятся в мусор? У них просто вычислительная сложность драматически выше?
                  0
                  Не обязательно. Просто квантовые компьютеры в определенных случаях могут некоторые вещи считать сильно быстрее обычных компов, за счет своей квантовой природы. А есть алгоритмы, которые не подвержены ускорению с помощью квантовых механизмов, их как раз активно изучают
                  0
                  Очень давно, где-то читал новость, про какие-то суперразреженные хеши (возможно новость была о премии за это дело), которые могут использоваться для криптографии. Не могу никаких концов в инете найти, а врезалось в память, может кому-то это о чём-то говорит?
                    0
                    Вроде, на симметричные схемы квантовая криптография не особо покушается, там так называемые «медленные квантовые алгоритмы» типа Гровера которые интересны скорее с точки зрения теории. Но ведь, наверное, есть случаи когда нужны именно асимметричные схемы вместо RSA? Вот те-же банковские операции, что с ними?
                      0
                      Ну, вообще именно из-за гровера рекоммендуют увеличивать размер ключей до 256 бит. Вчера как раз прочитал, что доказали его оптимальность. По поводу банковского сектора — там уже во всю орудует NTRU, жалко что он патентованый
                        0
                        Спасибо. Посмотрел — NTRU какой-то решёточный. Но решёточные же вроде и открытые есть.
                          0
                          да чет не очень их много https://en.wikipedia.org/wiki/Lattice-based_cryptography
                            0
                            В википедии ещё пишут, что теперь и у NTRU есть open source реализация. Кого тогда патент волнует? Но там даже не особо понятно из описания, почему он именно решёточный.
                              0
                              Мне кажется, из описания предельно понятно, почему он решеточный https://en.wikipedia.org/wiki/NTRUEncrypt Потому что, основан на проблеме поиска кратчайшего вектора в решетке. На счет реализаций хз. Реализации может и открытые, но сам алгоритм то патентованый. NTRU под GPL, поэтому опен сорс может юзать его. https://github.com/NTRUOpenSourceProject/ntru-crypto
                                0
                                Меня смутило, что там написано:
                                Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices.

                                То есть связан, но не эквивалентен. Алгоритм, как и RSA использует умножение, хотя и не двух чисел, такая сборная солянка, так что мне например не всё «предельно понятно». В том прагматическом смысле, что почему вдруг через некоторое время кто-нибудь не найдёт быстрый квантовый алгоритм.
                                  0
                                  вот и ищут )
                      +1
                      Я бы немного подкорректировал:

                      — HS1-SIV вряд ли считается самым перспективным, он весьма корявый и security level у него низкий (в одном из вариантов — 28 бит всего)
                      — GCM-SIV не является участником CAESAR, но авторы активно его продвигают, и он скоро станет стандартом IETF
                      — атака Альвена и Блоки на Argon2, на которую вы дали ссылку, уменьшает стоимость перебора на ASIC в два раза. Это хуже, чем результат авторов (в три раза).

                      Only users with full accounts can post comments. Log in, please.