Double Ratchet Algorithm

ダブルラチェットプロトコルにおける鍵交換と鍵生成の仕組み

X3DHで初回の鍵交換が完了すると、その後の通信はダブルラチェットプロトコルによって管理されます。ダブルラチェットプロトコルは、メッセージごとに新しい鍵を生成し、より高いセキュリティを提供します。

X3DHで確立されたセッション鍵は、ダブルラチェットプロトコルのルートキーとなり、以降のすべての鍵交換とメッセージ暗号化プロセスの基礎となります。ルートキーから派生するチェーンキーが、各メッセージに使われる暗号鍵を生成し、セキュアな通信が維持されます。

DHラチェットアルゴリズム（The Double Ratchet Algorithm）

DH Ratchet

1. DH鍵交換（Diffie-Hellman）

図の左側にある2つの鍵ペア（Private key と Public key）が、Diffie-Hellman（DH）鍵交換に使われます。通信の参加者が、互いの公開鍵と自分の秘密鍵を使用して共有鍵を生成します。この共有鍵は第三者に知られることなく安全に共有されます。

Private key: メンバーの秘密鍵。各ラチェットステップで更新され、新しい鍵ペアを生成。
Public key: 相手に公開される鍵。これを使って双方が共有鍵を生成。
DH: 相手の公開鍵と自分の秘密鍵を使って共有鍵を生成。この共有鍵は、KDFの入力に使われます。

2. KDF（鍵導出関数）

図の中央にあるKDFは、共有鍵や他の鍵（ルートキーなど）から新しい鍵を生成するための関数です。

Key, In: 共有鍵（DH鍵交換の結果）と既存のルートキーが入力されます。
Out: KDFからは、次に使う新しい鍵が導出されます。ここでは、新しいルートキーと、- 送信チェーンキーまたは受信チェーンキーが生成されます。

KDFを使うことで、鍵が毎回更新され、攻撃者が過去の鍵を手に入れても未来のメッセージが保護され続ける「前方秘匿性」が保証されます。

3. ルートキー（Root Key）

図の最上部と最下部にあるルートキーは、KDFによって更新され、次のラチェットステップで再び使われます。ルートキーは、暗号通信の最初から続いている基本的な鍵であり、KDFの計算によって常に新しく更新されます。

4. 送信チェーンキーと受信チェーンキー

図の右側に示されている送信チェーンキーと受信チェーンキーは、それぞれメッセージの暗号化に使われる鍵です。

送信チェーンキーは、メッセージを送る際に使用される鍵です。受信チェーンキーは、メッセージを受け取る際に使用される鍵です。送信側と受信側で異なるチェーンキーが生成されることで、送信と受信のセキュリティが独立して保たれます。

ダブルラチェットプロトコル（Double Ratchet Protocol）

ダブルラチェットの「ダブル」とは、2つの異なるラチェット機構を指しています。このプロトコルは、通信の安全性を高めるために2種類の鍵生成メカニズム（ラチェット）を組み合わせています。

Each Ratchet

1. 対称鍵ラチェット（Symmetric-key Ratchet）

対称鍵（送受信）ラチェットは、既存の対称鍵（セッション鍵）をもとに、新しい鍵を生成するメカニズムです。新しいメッセージを送るたびに、以前の鍵から次の鍵が生成されます。これにより、過去の鍵が漏洩しても新しい鍵は守られる「前方秘匿性（forward secrecy）」が確保されます。

メッセージごとに鍵を更新
メッセージが送受信されるたびに鍵を更新することで、各メッセージを個別に保護

2. 公開鍵ラチェット（Public-key Ratchet）

公開鍵（DH）ラチェットは、セッション中に新しい鍵交換を行うために使用されます。この鍵交換は非同期で行われ、片方のユーザーが新しい鍵ペアを生成して相手に公開鍵を送信します。これにより、長期的な鍵の更新が可能になり、過去の鍵漏洩の影響をさらに減らすことができます。

通信セッション中に、新しい公開鍵ペアを交換
新しい公開鍵に基づいて、双方で新しいセッション鍵を生成

公開鍵（DH）ラチェットは、ルートKDF チェーンを2 回更新し、KDF出力キーを新しい受信および送信チェーンキーとして使用することから構成されます。

「ダブルラチェット」プロトコルは、前方秘匿性と将来秘匿性（post-compromise security）の両方を保証するために設計されています。

前方秘匿性: 新しいメッセージごとに異なる鍵が使われるため、過去の鍵が漏れても新しいメッセージは保護されます。

将来秘匿性: 公開鍵ラチェットによって、もしセッション中に秘密鍵が漏洩した場合でも、将来のメッセージは安全に保護され続けます。

Aliceのラチェットフロー

Double Ratchet Flow

AliceとBobのラチェットフローイメージ

Double Ratchet

送受信ラチェットA1は以前に生成されたもの。
AliceはラチェットA1で生成したメッセージ送信鍵でメッセージを暗号化して送信
それを受信したBobは、ラチェットA1で生成したメッセージ受信鍵でメッセージを復号

Bobは新たなセッションでメッセージを送受信するため、ラチェットDH1を実行し公開鍵をAliceに送信
AliceはBobの新たな公開鍵と自身の新旧の秘密鍵からラチェットDH1を実行し、メッセージ送受信鍵の生成に必要なチェーン鍵（送受信の2種類）を生成
ラチェットDH1により、メッセージ送受信鍵を生成するための送受信ラチェットA2,A3,A4,B1,B2を実行

BobがメッセージA4を受信後、再びラチェットDH2を実行し公開鍵をAliceに送信
AliceはBobの新たな公開鍵と自身の新旧の秘密鍵からラチェットDH2を実行し、メッセージ送受信鍵の生成に必要なチェーン鍵（送受信の2種類）を生成
ラチェットDH2により、メッセージ送受信鍵を生成するための送受信ラチェットA5,B3,B4を実行

HKDF (HMAC-based Key Derivation Function)

HKDFは、HMAC（Hash-based Message Authentication Code） をベースにした鍵導出関数で、既存の秘密情報（例：共有鍵や乱数）から、暗号化や認証などに使用する鍵を生成します。

HKDFは以下の2つの主要なステップから成り立っています。

抽出フェーズ（Extract）:

入力となる秘密情報（乱数や共有鍵など）から、一貫した長さの「擬似乱数（PRK: Pseudo-Random Key）」を生成します。このプロセスには、HMACが使われ、入力データがHMACのハッシュ関数で「圧縮」されます。

拡張フェーズ（Expand）:

抽出フェーズで得られたPRKを基に、必要な長さの鍵素材を生成します。この拡張プロセスでもHMACを使います。

LinphoneのLIMEのHKDFでは、ルートキーとチェインキーを生成するHMACハッシュ関数（HKDF_RK, HKDF_CK）としてSHA512が導入されていています。

HKDF_RK

function KDF_RK(RK<32bytes>, DH_out<32, 56bytes>)
	info ← "DR Root Chain Key Derivation"
	RK<32bytes> || CK<32bytes> ← HKDFSha512(RK, DH_out, info)
	return RK<32bytes>, CK<32bytes>
end function

salt : RK(Root Key)
ikm : the output of ECDH(DH_out)
info : “DR Root Chain Key Derivation”
CK : Chain Key
Note) DH_out : X25519 >>> 32 bytes output, X448 >>> 56 bytes output, || means concatenation

function HKDFSha512(salt, ikm, info)
	return okm
end function

salt : optionnal
ikm : input key material
info : string
okm : output key material

HKDF_CK

function KDF_CK(CK<32bytes>)
	MK || IV ← HmacSha512(ChainKey, 0x01)
	CK ← HmacSha512(ChainKey, 0x02)
	return CK<32bytes>, MK<32bytes>, IV<16bytes>
end function

MK : Message Key
IV : Initialisation Vector
Note) || means concatenation

メッセージの暗号化と復号

ダブルラチェットプロトコルでは、各メッセージが新しい対称鍵で暗号化されます。メッセージそのものを暗号化するためにAES-256-GCMが使用されます。

暗号化 : 送信者は、生成された対称鍵を使って、AES-256-GCMでメッセージを暗号化します。この際、GCMモードにより認証タグが生成されます。暗号化の際には、ノンス（nonce）または初期化ベクタ（IV: Initialization Vector） というランダムな値が必要です。

復号化 : 受信者は、受信したメッセージに対応する対称鍵をラチェットプロセスで生成し、AES-256-GCMを使ってメッセージを復号し、認証タグを確認することで改ざんされていないかチェックします。

メッセージの認証

AES-256-GCMは、単なる暗号化に加えて、メッセージの改ざんを防ぐための認証機能も備えています。GCM（Galois/Counter Mode） は、暗号化したデータの整合性を確認するために認証タグを生成します。

改ざん検知 : 受信者がメッセージを復号化するとき、暗号文に付随している認証タグを検証することで、メッセージが改ざんされていないことを確認できます。もし認証に失敗すれば、メッセージは破棄され、正しいデータを受け取ったかどうかが保証されます。