Алгоритм двойного храповика (Glikjnmb ;fkwukik ]jghkfntg)

Алгоритм двойного храповика (англ. Double Ratchet Algorithm, ранее был назван Axolotl Ratchet^[1] ^[2]) — алгоритм управления ключами, разработанный Тревором Перрином (англ. Trevor Perrin) и Мокси Марлинспайком (англ. Moxie Marlinspike) в 2013 году. Данный алгоритм может быть использован как часть криптографического протокола для того, чтобы обеспечить сквозное шифрование для мгновенного обмена сообщениями. После первоначального обмена ключами он управляет текущим обновлением и обслуживанием коротких ключей сеанса. Он объединяет криптографический храповик на основе обмена ключами по протоколу Диффи-Хеллмана и храповик, построенный на основе функции формирования ключа, такой как, например, хеш-функция. Таким образом алгоритм представляет собой двойной храповой механизм, что и отражено в его названии.

Разработчики описывают алгоритм как самовосстанавливающийся, поскольку при определённых условиях он отключает злоумышленника от доступа к открытому тексту сообщения после взлома ключа сеанса^[3]. Это условие заключается в том, что между компрометацией ключа и сообщением, о котором идёт речь, было по крайней мере одно сообщение, которое не было подделано злоумышленником. Это фактически вынуждает злоумышленника перехватывать всю связь между честными сторонами, так как он теряет доступ, как только между ними передаётся одно нескомпрометированное сообщение. Это свойство позже было названо Future Secrecy, или пост-скомпрометированная безопасность (англ. Post-Compromise Security)^[4].

Введение

Данный алгоритм используется двумя сторонами для обмена зашифрованными сообщениями на основе общего секретного ключа. Как правило, стороны используют протокол начального соглашения Extended Triple Diffie-Hellman (X3DH)^[5], при котором происходит тройной обмен ключами для того, чтобы согласовать общий секретный ключ. После этого участники соединения будут использовать Double Ratchet для отправки и получения зашифрованных сообщений. При каждом сообщении Double Ratchet стороны должны получать новые ключи для каждого сообщения Double Ratchet, чтобы более ранние ключи не могли быть рассчитаны из более поздних. Также участники соединения направляют общие значения Диффи-Хеллмана, прилагаемые к их сообщениям. Результаты вычислений Диффи-Хелмана смешиваются с производными ключами, так что более поздние ключи не могут быть рассчитаны из более ранних. Эти свойства дают некоторую защиту зашифрованным сообщениям, приходящим ранее взлома или после него, в случае компрометации ключей стороны^[6].

История возникновения

Алгоритм двойного храповика был разработан в 2013 году Тревором Перрином и Мокси Марлинспайком, создателем некоммерческой организации разработчиков открытого программного обеспечения Open Whisper Systems. Целью этой организации является развитие простого в использовании набора мобильных приложений для безопасного общения^[7]. Организация основана в 2013 году и состоит из небольшой группы разработчиков, финансируемой за счёт пожертвований и грантов, а также большого сообщества разработчиков-добровольцев. В феврале 2014 года Тревор Перрин и Мокси Марлинспайк представили алгоритм как часть сигнального протокола (англ. Signal Protocol). Замысел алгоритма двойного храповика основан на храповике Диффи-Хеллмана, который был представлен криптографических протокол для систем мгновенного обмена сообщениями (Off-The-Record Messaging (OTR)) и сочетает его с храповым механизмом с симметричным ключом, смоделированным по протоколу мгновенного обмена сообщениями — Silent Circle Instant Messaging Protocol (SCIMP). Первоначально храповик был назван в честь животного, находящегося под угрозой исчезновения, аксолотля, который обладает исключительными возможностями самовосстановления. В марте 2016 года разработчики переименовали Axolotl Ratchet в Double Ratchet Algorithm, чтобы лучше различать храповик и полный протокол^[2], поскольку некоторые использовали имя Axolotl имея в виду сигнальный протокол^[8]^[2].

Свойства

Алгоритм двойного храповика обладает свойствами, которые были широко доступны в сквозных системах шифрования в течение длительного времени: шифрование содержимого на всем пути транспортировки, а также аутентификация удалённого узла и защита от манипулирования сообщениями. Как гибрид храповых механизмов Диффи-Хеллмана и функции формирования ключа, он сочетает в себе несколько желаемых характеристик обоих принципов. Из обмена сообщениями OTR он берёт свойства прямой секретности и автоматически восстанавливает секретность в случае компрометации ключа сеанса, пересылает конфиденциальную информацию со взломом секретного постоянного основного ключа и правдоподобное отрицание авторства сообщений. Кроме того, он позволяет обновлять сессионные ключи без взаимодействия с удалённым узлом, используя вторичные храповики на основе функции формирования ключа. Применяется дополнительный шаг формирования ключа, позволяющий удерживать ключи сеанса для сообщений, посылаемых вне порядка, не подвергая опасности следующие ключи для обнаружения переупорядочения, удаления и повторной передачи отправленных сообщений и улучшения свойств конфиденциальности по сравнению с сообщениями OTR.

В сочетании с инфраструктурой открытого ключа для хранения предварительно сформированных одноразовых ключей (prekeys) он позволяет инициализировать сеансы обмена сообщениями без присутствия удалённого узла (асинхронной связи). Использование тройного обмена ключами Диффи-Хеллмана (X3DH) в качестве метода первоначального обмена ключами улучшает свойства отрицания. Примером этого является протокол сигналов, который объединяет алгоритм двойного храпового механизма, prekeys и первоначальный обмен ключами с помощью тройного обмена ключами Диффи-Хеллмана^[9]. Протокол обеспечивает конфиденциальность, целостность, аутентификацию, согласованность участников, проверку адресатов, прямую конфиденциальность, скрытую конфиденциальность (также известную как future secrecy), сохранение причинно-следственных связей, неприемлемость сообщений, отказ от сообщений, отказ от участия и асинхронность^[9]. Он не обеспечивает сохранение анонимности и требует серверов для ретрансляции сообщений и хранения материалов открытого ключа^[9].

Схема функционирования

Клиент обновляет ключ сеанса при взаимодействии с удалённым узлом, используя храповик Диффи-Хеллмана, когда это возможно, иначе независимо, используя храповик хеша. Поэтому с каждым сообщением клиент, использующий двойной храповик, выдвигает один из двух хеш-храповиков (один для отправки, один для получения), которые берут общий ключ от храповика Диффи-Хеллмана. В то же время он пытается использовать любую возможность, чтобы предоставить удалённому узлу новое общедоступное значение Диффи-Хеллмана и выдвигать храповик Диффи-Хеллмана всякий раз, когда поступает новое значение Диффи-Хеллмана от удалённого узла. Как только новый общий ключ установлен, инициализируется новый храповик хеша.

В качестве криптографических примитивов, алгоритма двойного храповика использует:

для храпового механизма Диффи-Хеллмана

Эллиптическая кривая Диффи-Хеллмана (ECDH) с кривой 25519,

для кодов аутентификации сообщений (MAC, аутентификация)

Код аутентификации сообщения с ключом-хеш (HMAC) — механизм обмена данными с использованием секретного ключа (как в MAC — к сообщению добавляется специальный набор символов для обеспечения его целостности и аутентификации источника данных) и хеш-функций на основе SHA-256 — безопасного алгоритма хеширования

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

Стандарт расширенного шифрования (англ. Advanced Encryption Standard (AES)) — симметричный алгоритм блочного шифрования, частично в режиме Cipher Block Chaining (CBC) с заполнением в соответствии с PKCS № 5 и частично в режиме счётчика (CTR) без заполнения,

для храпового механизма на основе хеш

HMAC^[10].

Шифрование заголовка Double Ratchet

В некоторых случаях может быть желательно зашифровать заголовки, чтобы подслушивающее устройство не могло определить, какие сообщения относятся к каким сеансам или какой порядок у сообщений в сеансе. При шифровании заголовка каждая сторона хранит симметричный заголовочный ключ и следующий заголовочный ключ как для отправки так и для приёма. Посылающий заголовочный ключ используется для шифрования заголовков для текущей цепочки отправки. Когда к получателю приходит сообщение, он сначала должен связать сообщение с соответствующим сеансом Double Ratchet, если кроме этого сеанса присутствуют также другие сеансы с другими сторонами. После того как получатель связал сообщение с сеансом, он пытается дешифровать заголовок с помощью получающего ключа заголовка этого сеанса, следующего заголовочного ключа и любых других ключей заголовка, соответствующих пропущенным сообщениям. Успешное дешифрование с помощью следующего ключа заголовка указывает, что получатель должен выполнить шаг храповки Диффи-Хеллмана. Во время шага храповика Диффи-Хеллмана следующие ключи заголовка заменяют текущие ключи заголовка, а новые следующие заголовочные ключи принимаются как дополнительный выходные переменные из корневого хеша.

Список приложений

Ниже приведён список приложений, использующих алгоритм двойного храповика или его пользовательскую реализацию^{[источник не указан 249 дней]}

   ChatSecure
   Conversations
   Cryptocat
   Facebook Messenger
   G Data Secure Chat
   Gajim
   Google Allo
   Haven
   Pond
   Riot
   Signal
   Silent Phone
   Skype
   Viber
   WhatsApp
   Wire

Примечания

↑ Perrin, Trevor. "Compare Revisions", GitHub (неопр.) (30 марта 2016). Дата обращения: 7 декабря 2018. Архивировано 7 мая 2017 года.
↑ ¹ ² ³ Marlinspike, Moxie. "Signal on the outside, Signal on the inside" (неопр.) (30 марта 2016). Дата обращения: 7 декабря 2018. Архивировано 15 ноября 2018 года.
↑ Marlinspike, Moxie. "Advanced cryptographic ratcheting" (неопр.) (26 ноября 2013). Дата обращения: 7 декабря 2018. Архивировано 7 августа 2019 года.
↑ Katriel Cohn-Gordon ; Cas Cremers ; Luke Garratt. "On Post-compromise Security" (неопр.) (11 августа 2016). Дата обращения: 7 декабря 2018. Архивировано 7 июня 2018 года.
↑ Trevor Perrin (editor), Moxie Marlinspike. "The X3DH Key Agreement Protocol" (неопр.) (4 ноября 2016). Дата обращения: 7 декабря 2018. Архивировано 23 ноября 2020 года.
↑ Trevor Perrin (editor), Moxie Marlinspike. "The Double Ratchet Algorithm" (неопр.) (20 ноября 2016). Дата обращения: 7 декабря 2018. Архивировано 21 августа 2019 года.
↑ whispersystems.org. Open Whisper Systems >> Home (неопр.). Дата обращения: 7 декабря 2018. Архивировано 9 декабря 2018 года.
↑ Katriel Cohn-Gordon , Cas Cremers , Benjamin Dowling , Luke Garratt , Douglas Stebila. "A Formal Security Analysis of the Signal Messaging Protocol" (неопр.) (ноябрь 2017). Дата обращения: 7 декабря 2018. Архивировано 22 февраля 2017 года.
↑ ¹ ² ³ Nik Unger , Sergej Dechand Joseph Bonneau , Sascha Fahl , Henning Perl Ian Goldberg , Matthew Smith. "SoK: Secure Messaging" (неопр.) (2015). Дата обращения: 7 декабря 2018. Архивировано 1 ноября 2020 года.
↑ Tilman Frosch , Christian Mainka , Christoph Bader , Florian Bergsma , Jorg Schwenk , Thorsten Holz. "How Secure is TextSecure?" (неопр.) (2014). Дата обращения: 7 декабря 2018. Архивировано 28 февраля 2019 года.

[1] Perrin, Trevor. "Compare Revisions", GitHub (неопр.) (30 марта 2016). Дата обращения: 7 декабря 2018. Архивировано 7 мая 2017 года.

[автоссылка1-2] ¹ ² ³ Marlinspike, Moxie. "Signal on the outside, Signal on the inside" (неопр.) (30 марта 2016). Дата обращения: 7 декабря 2018. Архивировано 15 ноября 2018 года.

[3] Marlinspike, Moxie. "Advanced cryptographic ratcheting" (неопр.) (26 ноября 2013). Дата обращения: 7 декабря 2018. Архивировано 7 августа 2019 года.

[4] Katriel Cohn-Gordon ; Cas Cremers ; Luke Garratt. "On Post-compromise Security" (неопр.) (11 августа 2016). Дата обращения: 7 декабря 2018. Архивировано 7 июня 2018 года.

[5] Trevor Perrin (editor), Moxie Marlinspike. "The X3DH Key Agreement Protocol" (неопр.) (4 ноября 2016). Дата обращения: 7 декабря 2018. Архивировано 23 ноября 2020 года.

[6] Trevor Perrin (editor), Moxie Marlinspike. "The Double Ratchet Algorithm" (неопр.) (20 ноября 2016). Дата обращения: 7 декабря 2018. Архивировано 21 августа 2019 года.

[7] whispersystems.org. Open Whisper Systems >> Home (неопр.). Дата обращения: 7 декабря 2018. Архивировано 9 декабря 2018 года.

[8] Katriel Cohn-Gordon , Cas Cremers , Benjamin Dowling , Luke Garratt , Douglas Stebila. "A Formal Security Analysis of the Signal Messaging Protocol" (неопр.) (ноябрь 2017). Дата обращения: 7 декабря 2018. Архивировано 22 февраля 2017 года.

[автоссылка2-9] ¹ ² ³ Nik Unger , Sergej Dechand Joseph Bonneau , Sascha Fahl , Henning Perl Ian Goldberg , Matthew Smith. "SoK: Secure Messaging" (неопр.) (2015). Дата обращения: 7 декабря 2018. Архивировано 1 ноября 2020 года.

[10] Tilman Frosch , Christian Mainka , Christoph Bader , Florian Bergsma , Jorg Schwenk , Thorsten Holz. "How Secure is TextSecure?" (неопр.) (2014). Дата обращения: 7 декабря 2018. Архивировано 28 февраля 2019 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]