Системный архитектор, криптоманьяк
5,0
рейтинг
15 января 2015 в 14:59

Разработка → Curve25519, EdDSA и Poly1305: Три обделенных вниманием криптопримитива tutorial

Есть такой очень хороший товарищ по имени Daniel Julius Bernstein. Математик, программист и спец по компьютерной безопасности. Его хэш CubeHash чуть не дотянул до третьего раунда SHA-3, а потоковый шифр Salsa20 попал в шорт лист проекта eStream. А еще он автор культовой в узких кругах криптобиблиотеки NaCl, о трех штуках из которой я бы хотел вкратце рассказать.

Curve25519


Это эллиптическая кривая и набор параметров к ней подобранных таким образом, чтобы обеспечить более высокое быстродействие (в среднем, 20-25%) и избавиться от некоторых проблем с безопасностью у традиционного ECDH.

Кривая используется y2 = x3 + 486662x2 + x. Это — кривая Монтгомери над полем вычетов по модулю простого числа 2255 − 19 (что и дало название схеме) и с базовой точкой x=9. Схема использует точки в сжатой форме (только X координаты), позволяя таким образом использовать "Лестницу Монтгомери", которая делает умножение точек за фиксированное время, избавляя нас от Timing attacks.

Curve25519 используется как обмен ключами по умолчанию в OpenSSH, I2p, Tor, Tox и даже в IOS.

Чем эта схема так хороша с точки зрения программиста?

Она очень простая и быстрая. Чтобы сгенерировать новую ключевую пару, мы подаем на вход схеме любые 32 случайных байта, которые будут закрытым ключом. Из них мы получаем 32 байта открытого ключа. Затем как обычно, обмениваемся открытыми ключами и считаем общий. Насколько именно она быстрее классического ECDH с 256битными кривыми сказать не возьмусь, зависит от реализации. Мне она нравится за устойчивость к timing attacks и за возможность использовать любые 32байтные массивы в качестве закрытых ключей.

EdDSA


Точнее, ее частный случай, Ed25519, как можно догадаться, тоже убыстренный и усиленный вариант цифровой подписи на эллиптических кривых. Используется схема Шнорра для «Скрученной кривой» Эдвардса, изобретенной, кстати, тем же Даниэлем Бернштайном в 2007 году.

Испольуется такая вот кривая:


которая эквивалентна кривой для Curve25519

EdDSA используется, например, в OpenBSD signify tool, чтобы подписывать образы

И так, Curve25519 и Ed25519 — примитивы на эллиптических кривых, оптимизированные по быстродействию и написанные таким образом, чтобы минимизировать или вовсе исключить влияние входных данных на процесс расчета ключей\подписей.

Poly1305


Это MAC (Message authentication code), работающий совместно с AES или любым другим шифром по вашему желанию. Он считает 16 байтный (128 бит) MAC, используя 256 битный ключ AES, который разделяется на два по 128 бит (k,r) и соль (nonce).
Он разбивает сообщение на блоки по 16 байт и работает с ними как с коэффициентами полинома в r по модулю простого числа 2130−5

Результат получается на 4 байта меньше, чем обычный HMAC-SHA1, не имеет проблем с безопасностью и работает быстрее.

Именно поэтому его вместе с потоковым шифром ChaCha20 использует Google вместо RC4, а так же он включен в OpenSSH, которому теперь не нужно зависеть от OpenSSL

Референсная реализация всего этого в библиотеке NaCl на C, но есть порты на java и c#, например.

Надеюсь, после этой статьи у вас появится желание узнать об этих примитивах побольше и использовать их в ваших приложениях.
@Scratch
карма
101,7
рейтинг 5,0
Системный архитектор, криптоманьяк
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (8)

  • +1
    Если кому интересно, про «скрученные» кривые Эдвардса и то, как они могут использовать в отечественных схемах подписи, вот неплохая статья.
  • 0
    А про саму реализацию EdDSA не хотите рассказать, а то все существующие это порт с бернштейновской реализации на ассемблере? В частности везде требуется представление в виде Little Endian.
    • +1
      Есть еще библиотека с говорящим названием Tweet NaCl (угадайте автора)
      Там, кажется, big-endian структуры.

      Там ровно те же алгоритмы, все те же constant-time operations. Но, конечно, медленнее.
      Есть порты на кучу языков, такие же лаконичные
  • 0
    У меня Гугл использует «The connection is encrypted and authenticated using AES_128_GCM and uses ECDHE_ECDSA as the key exchange mechanism.».
    • 0
      As of February 2014, almost all HTTPS connections made from Chrome browsers on Android devices to Google properties have used the new cipher suite; Google plans to make it available as part of the Android platform in a future release.
    • +1
      Если посмотреть на все их ciphersuites, видно, что действительно есть TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256. Возможно, Chrome будет использовать этот сьют в каких-то ситуациях. Возможно, они когда-то понизят приоритет TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 и тогда все браузеры, у которых есть поддержка первого сьюта, перейдут на второй.
  • +1
    Как админу хочется поблагодарить этого талантливого дядьку за djbdns и qmail.
    • 0
      а… с одной стороны он типа сделал qmail опенсурс сразу, но с такими условиями что никто не может менять ОСНОВНОЙ код и распространять, т.е. все изменения в виде патчей, там аж целый портал патчей набрался. Благодаря этому недальновидному подходу (о да, умница автор просто хотел чтобы все любовались на его код, (он и в самом деле красивый), а не засоряли его). Благодаря этому подходу qmail практически мертв, и его место было занято postfix… Он одумался какое-то время назад, но поезд ушел.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.