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

Привет, %username%

Пришло время для свежей пачки криптоновостей, пока они еще не перестали быть новостями. В этом выпуске:

• Новый рекорд вычисления дискретного логарифма
• VPN сервер и клиент, использующие Noise протокол
• Постквантовая криптография в Chrome уже сегодня!
• Чего вы не знаете о новом E2E шифровании в Facebook
• RLWE избавляется от R и это идет ему на пользу
• Comodo хотел поиметь Let`s Encrypt, но сфейлил. А Let`s Encrypt с завтрашнего дня будет поддерживать ddns
• Появились минимальные требования к реализациям алгоритмов RSA, DSA, DH, устойчивым к side-channel атакам

Предыдущий выпуск тут ^[1]

Рекорд вычисления дискретного логарифма

Группа исследователей из EPFL и Университета Лейпцига смогла посчитать ^[2] логарифм по основанию простого числа размером 768 бит. Для этого им понадобилось 200 ядер и время с февраля 2015 года. Использовали они вариант цифрового решета. Таким образом логарифмирование сравнялось с факторизацией где рекорд для обычных чисел тоже 768 бит ^[3]

Wireguard ^[4]. VPN, использующий самые модные криптоалгоритмы

Не успели опубликовать спеку по Noise protocol, как уже появилось решение на его основе.
Очень минималистичный VPN, в котором используются Noise protocol framework, Curve25519, ChaCha20, Poly1305, BLAKE2, SipHash24 и HKDF. Работает в режиме ядра, но активно пилятся usermode версии на Go и Rust. Советую присмотреться, очень крутая штука.

Google добавил постквантовое шифрование в Chrome Canary

Подробнее тут ^[5]. Используется алгоритм New Hope, который основан на проблеме RLWE ^[6], которая в свою очередь является частным вариантом криптографии на решетках ^[7]. Это сравнительно молодая область криптографии, еще плохо изучена и поэтому её пока нельзя использовать в реальной жизни. Но в качестве эксперимента, почему бы и нет?

E2E шифрование в Facebook позволяет настучать на собеседника

Они назвали этот механизм Franking ^[8]. Он позволяет отправить Abuse report в случае необходимости. Реализуется следующим образом:

1. Генерируется случайный ключ N_f
2. Считается T_f = HMAC·SHA256(N_f, M)
3. N_f конкатенируется с M и шифруется ключом получателя. На сервер отправляется T_f и шифротекст
4. Сервер считает R_f= HMAC·SHA256(ключ фейсбука, T_f || метаданные (кто, кому,...))
5. Получателю отправляется R_f, T_f, шифротекст
6. Получатель расшифровывает шифротекст, считает HMAC(N_f, M) и сравнивает с T_f. Если сравнение не проходит, то выбрасывает сообщение
7. Если получатель хочет пожаловаться фейсбуку, то отправляет ему расшифрованное сообщение, R_f, N_f
8. Фейсбук убеждается, что это именно то сообщение, которое отправил отправитель и принимает соответствующие действия

Таким образом, отвертерться от обзывательства Васи козлом не получится.

RLWE без R

Итак, есть криптография на решетках. Хороша тем, что её в будущем не взломает квантовый компьютер. Но её параметры огромны, размеры ключей достигают мегабайтов. Есть частный её случай, называемый обучение с ошибками ^[9]. Так вот, обучение с ошибками хоть тоже очень круто, но тем не менее из-за ограничений на размер ключа и других было нереально использовать в продакшене. Поэтому к LWE добавили кольца и назвали это RLWE ^[6], который уже используется в Chrome Canary, т.е. там параметры стали уже более-менее человеческими по размерам.

К сожалению, степень изученности обратно пропорциональна навороченности алгоритма и добавление колец возможно ослабило LWE. Поэтому группа товарищей реализовала согласование ключей без колец и опубликовало на эту тему доку ^[10]. Размеры сообщений в каждую сторону находятся в пределах 12 кб, операция согласования ключей занимает около 1.3 мс. Это примерно в 5 раз больше по объему хэндшейка DH, а так же в 1.6 раз замедляет пропускную способность TLS сервера, но тем не менее это уже сравнимо с New Hope и можно использовать на практике. При этом структура получается более безопасной.

Comodo оборзел

И решил для нескольких своих сервисов зарегистрировать торговую марку Let’s Encrypt. Мало того, что торгуют воздухом, так еще и чужая слава покоя не дает. Но, сообщество собралось силами, надавало комоду по сусалам и отбило торговую марку. Подробности тут ^[11].

Кстати, после завтрашнего апдейта ^[12] можно будет прикручивать бесплатный TLS к dyndns хостам! Это суперкруто, все хомяки теперь будут с сертификатами.

Защищаемся от Side channel атак

Не секрет, что нынче информацию о ключах шифрования можно удаленно снимать чуть ли не через вентилятор. Поэтому, все большую популярность обретают constant-time алгоритмы, которые не зависят от входных данных. Немцы выпустили минимальные требования для реализаций, выполнение которых усложнит задачу получения секретных данных через побочные каналы данных. Интересный документ ^[13], советую ознакомиться.

На этом у меня всё, до новых встреч!

Автор: Scratch

Источник ^[14]