FICUSONLINE F9E
X3DH (Extended Triple Diffie-Hellman) とECDH(Elliptic Curve Diffie-Hellman)について
Linphoneが採用しているメッセージ暗号化(LIME)には、Signalが公開しているX3DHとダブルラチェットというプロトコルが採用されています。X3DHはECDHを応用した共有鍵を生成する手順であり、ダブルラチェットは、X3DHプロトコルで生成された共有鍵を用いて、メッセージの暗号化および復号に使用する新しい鍵を生成・更新するための手順です。ここではまずX3DHとECDHについて纏めます。
Takanobu FuseAdministrator

7 months ago

Web Development

メッセージ暗号化

Linphoneが採用しているメッセージの暗号化(LIME)には、Signalが公開している以下のプロトコルが採用されています。X3DHは共有鍵を生成する手順であり、ダブルラチェットは、X3DHプロトコルで生成された共有鍵を用いて、メッセージの暗号化および復号に使用する新しい鍵を生成・更新する手順です。

  1. X3DH(Extended Triple Diffie-Hellman)
  2. ダブルラチェット(Double-Ratchet)

暗号化に使用される鍵そのものは、幾何学的な楕円曲線上のX座標（モジュロ演算後の座標）であり、X3DHやダブルラチェットでは、演算効率とセキュリティのバランスを考慮した以下の楕円曲線が利用されています。

Curve25519 (𝐸 ∶ 𝑦² = 𝑥³ + 486662𝑥² + 𝑥 and 𝑝 = 2²⁵⁵ − 19)

Curve25519

または、

Curve448 (𝐸 ∶ 𝑦² + 𝑥² = 1 − 39081𝑥²𝑦² and 𝑝 = 2⁴⁴⁸ − 2²²⁴ − 1)

Curve448

X3DH（Extended Triple Diffie-Hellman）

ECDH(Elliptic Curve Diffie-Hellman)は楕円曲線上の座標を利用した共有鍵生成アルゴリズムで、X3DHはそれを拡張したもの。共有鍵を生成するための鍵が幾つか追加され、プロセスが多段になっています。

X3DHは、主に初めて通信を行う二者間で、安全に暗号鍵を交換し、後続のメッセージ暗号化に必要な「セッション鍵」を確立するために使用されます。具体的には、初回の鍵交換および信頼関係の確立に関わるプロセスでX3DHが使われます。

X3DHは次のプロセスにおいて重要な役割を果たします。

1. 初回の鍵交換（初めて通信を開始する際）

利用者同士が初めてメッセージを送る際、どちらの利用者も相手の公開鍵をまだ知らない状態です。このとき、X3DHを使って安全な鍵交換を行い、暗号化されたメッセージを交換できるようにします。この初回の鍵交換によって、両者の間にセッション鍵が生成され、その後のメッセージが暗号化されます。

X3DHは、次の4つの鍵を使って安全な鍵交換を実現します。

長期公開鍵（Identity Key, IK）:

各ユーザーが事前に生成しておき、他のユーザーに公開する公開鍵。これによって通信相手のアイデンティティを識別できます。

署名付き一時公開鍵（Signed PreKey, SPK）:

各ユーザーが公開する一時的な公開鍵で、長期公開鍵で署名されています。これは、中間者攻撃を防ぐために重要です。

一時的公開鍵（One-Time PreKey, OPK）:

一度しか使わない一時的な公開鍵。この鍵は、通信の秘匿性を強化するために用意されており、すでに交換されているかもしれない他の鍵とは独立したものです。

送信者のエフェメラル鍵（Ephemeral Key, EK）:

メッセージ送信時に一時的に生成される鍵で、セッションの際に使用されます。

2. X3DHによる鍵交換プロトコルの流れ

X3DHは、次の手順で安全な鍵交換を行います。

公開鍵の受け取り:

メッセージ送信者（Alice）は、受信者（Bob）の公開鍵セット（Identity Key、Signed PreKey、One-Time PreKey）をX3DHサーバーから取得します。

  • Aliceは、Bobの長期的な公開鍵Identity Keyを使ってSigned PreKeyの署名を検証 —> DH1

Diffie-Hellman鍵交換:

Aliceは、自身のエフェメラル鍵（EK）を生成し、Bobの公開鍵と共に、次の3つのDiffie-Hellman鍵交換を実行します。

  • Aliceのエフェメラル鍵とBobのIdentity Key —> DH2
  • Aliceのエフェメラル鍵とBobのSigned PreKey —> DH3
  • Aliceのエフェメラル鍵とBobのOne-Time PreKey —> DH4

これにより、共有の秘密情報が生成されます。この秘密情報をもとにして、暗号鍵が導出されます。

鍵の導出（Key Derivation）:

Diffie-Hellman鍵交換で得られた秘密情報を入力として、HKDF（HMAC-based Key Derivation Function）を使用して、共有のセッション鍵が導出されます。この鍵を使って、その後の通信を暗号化します。 セッション鍵の確立:

こうして確立されたセッション鍵は、その後のメッセージ送信に使用されます。初回のメッセージがこの鍵で暗号化され、受信者は自分の秘密鍵を使って復号します。

3. 後続の通信とDouble Ratchetプロトコルとの連携

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

X3DHにおけるEdDSAの役割

EdDSAを使う場合、署名の対象は必ず何かしらのデータである必要があります。署名の対象はメッセージ本文に限定されず、鍵自体や鍵の属性なども署名対象として扱います。

EdDSA（LinphoneのLIMEではXEdDSAではなくEdDSAが使用されています）は、次の場面で使用されます。

Edwards-Curve Digital Signature Algorithm (EdDSA)

1. Signed PreKeyの署名

Signed PreKeyは、各ユーザーがサーバーにアップロードしておく一時的な公開鍵で、X3DHプロトコルの鍵交換で利用されます。 このPreKeyが第三者によって改ざんされないように、ユーザーの長期Identity Key（IDキー）でEd25519署名を施します。この署名により、他者がSigned PreKeyを勝手に差し替えたり、改ざんすることを防ぎます。

2. 署名の検証 DH1

鍵交換を開始する際、メッセージの送信者（Alice）は受信者（Bob）のSigned PreKeyをサーバーから取得します。 Aliceは、Bobの長期Identity Keyで、このSigned PreKeyに施されたEd25519署名を検証します。この検証プロセスにより、Signed PreKeyが確かにBobによって生成されたものであり、改ざんされていないことが確認されます。

メッセージを送受信するAliceとBobの双方で以下定義する鍵により共有鍵を生成します。

  • Alice’s identity key IKA

  • Alice’s ephemeral key EKA

  • Bob’s identity key IKB

  • Bob’s signed prekey SPKB

  • Bob’s prekey signature Sig(IKB, Encode(SPKB))

  • (Optionally) Bob’s one-time prekey OPKB

DH1 = DH(IKA, SPKB)
DH2 = DH(EKA, IKB)
DH3 = DH(EKA, SPKB)
SK = KDF(DH1 || DH2 || DH3)

または、

DH1 = DH(IKA, SPKB)
DH2 = DH(EKA, IKB)
DH3 = DH(EKA, SPKB)
DH4 = DH(EKA, OPKB)
SK = KDF(DH1 || DH2 || DH3 || DH4)

X3DH

ECDH(Elliptic Curve Diffie-Hellman)

ECDHで利用される楕円曲線上の任意の2点P,Qを結ぶ直線（または任意の点Pにおける接線）が、楕円曲線自身と交わる点R’をX軸に対して反転させた点をRとした場合、P+Q=R（接線の場合はP+P=2P=R）が幾何学的に楕円曲線上で成立するとします。この点の演算をそれぞれ、

  • P+Q=R：点の加法（Point Addition)、
  • P+P=2P=R：点のスカラー乗算（Point Doubling）

と定義します。

上記のルールに従うと、R=2Pにおける接線が再び楕円曲線と交わる点のX軸に対して反転させた点が2P+2P=4Pと定義できます。同じようにして点4Pにおける接線から4P+4P=8Pの点を定義できます。

ここまでで点P,2P,4P,8Pが定義できました。この各点から、例えば点3Pは、点Pと点2Pを結んだ直線が再び楕円曲線と交わる点のX軸に対して反転させた点と定義できます。このように点のスカラー乗算と加法を効率的に利用することで、2P+4P=6P、4P+8P=12P、この12Pから12P+8P=20Pなど各点の演算を効率的に行うことができます。

Point Addition

楕円曲線と各点の演算について、下記サイトが分かりやすく纏めています。

The Animated Elliptic Curve

Point Addition

ECDHでは、実際の楕円曲線上の任意の点を直接利用する訳ではありません。各点の座標が割り切れない小数や無限遠点を扱うことになってしまい非現実的です。そのため、楕円曲線の方程式の両辺をモジュロ演算し、その演算結果が等しくなる点(x,y)の集合体に変換します。以下のイメージです。

Curve25519

上記の楕円曲線Curve25519上の任意の点を、モジュロ演算により有限領域にプロット（一部抜粋）。

点の総数は、

n = 2²⁵² + 27742317777372353535851937790883648493

となります。

Curve25519のECDHでは、点が不規則にプロットされるため（ただしy=p/2の直線に対し線対称）、起点Pおよび双方（倍率aとbを秘密鍵として使用）の共有点 aP や bP が第三者に知られても、(a+b)P を計算することは容易ですが、 abP を特定することは実質的に不可能です。これは、楕円曲線離散対数問題が非常に困難であり、n が天文学的に大きい数であるためです。

Modulo Field

Curve25519のECDHで生成される具体的な共有鍵の例として、起点Pを

P=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 )

とした場合、AliceとBob各々が秘密鍵を定義し公開鍵を相互に交換することで共有鍵を生成します。このCurve25519を採用した鍵交換プロトコルがX25519です。

秘密鍵（P点のスカラー倍率）

Bob private (b):	19606234678399378633456480350841655717034562515722490628739051202331311643228
Alice private (a): 	109204347234327284008793236257980475297107461097776439083128173099763401227175

公開鍵（スカラー倍率で乗算した点aPと点bPのX座標）

Bob public (bP):	 b'34c2b65e53c2877a7321c29ac3a1c2bac29d3721c29fc3bb44c291c392c28dc38574c38d7562c3bf71c39fc2a4c3aec2b973'
Alice public (aP):	 b'c2a307c384c3b9c39f64067cc3b724c290c3a818c28fc2abc2aa151d0a3e2c2c42c38cc28f4e3f0e1d54c2a744'

共有鍵（AliceとBobがそれぞれの秘密鍵と公開鍵をスカラー乗算した点のX座標）

Bob shared (b)aP:	 b'c382c2ba19c3b1c39142c38ec39161c2b93251c390c2876ac2b477c3bf6ec28740c2a7c387c283c2be6ec2b1c28bc3a32dc3a128'
Alice shared (a)bP:	 b'c382c2ba19c3b1c39142c38ec39161c2b93251c390c2876ac2b477c3bf6ec28740c2a7c387c283c2be6ec2b1c28bc3a32dc3a128'

X25519の使用される各鍵サイズは32バイト（256ビット）ですが、様々なセキュリティ上の懸念事項に対処するため、以下の5ビットの値は固定されています。

Bits Value Reason
0,1,2 0 Protect against small-subgroup attacks, which would allow one peer to use a manipulated secret key to discover the other peer’s secret key
254 1 Prevent implementors from skipping a multiplication round for smaller keys, which would expose a timing leak
255 0 Constrain n < 2²⁵⁵, which prevents the algorithm from reaching the “infinity” result for base-point x=9

以下は、楕円曲線をモジュロ演算した有限領域における点の演算方法の具体例です。起点P(X0,Y0)を(5,7)とします。この点の接線から2Pを算出します。

y²=x³+9x+1 mod 61

点Pにおける接線の傾きλは、両辺を微分して

2y･dy/dx=3x²+9 λ=dy/dx=(3x²+9)/2y=(325+9)/27=42/7=6 mod 61 = 6

2P(X1,Y1)の座標は、

X1=λ²-2X0=36-25=26 mod 61 = 26 Y1=λ(X0-X1)-Y0=6(5-26)-7=6(-21)-7=-126-7=-133 mod 61 = (-61*2-11) mod 61 = -11 mod 61 = 50

よって2P(26,50)となります。

y²=x³+9x+1 mod 61

同様にして点2Pの接線とその座標から点4P、点4Pの接線とその座標から点8P、以下、点16P、点32P、点64P、点128P…が算出できます。

倍加と加算アルゴリズム (Double and Add Algorithm)

スカラー倍kをバイナリ変換（2進数）すると点kPの演算を効率的に行えます。ビット単位でスカラー値を扱い、各ビットに対して「倍加（Double）」と「加算（Add）」の操作を繰り返します（実用上、モンゴメリーラダーというサイドチャネル攻撃（タイミング攻撃や電磁放射攻撃など）に強いアルゴリズムが使用されます）。

ビットが1の場合は「倍加+加算」、ビットが0の場合は「倍加のみ」を行います。

例えば k=151の場合、そのバイナリは、10010111 となります。よって、

151P = (2⁷x1+2⁶x0+2⁵x0+2⁴x1+2³x0+2²x1+2¹x1+2⁰x1)P

  • ビット0：点Pそのものを表します。
  • ビット1：1　点の倍加2Pと点の加算2P+P
  • ビット2：1　点の倍加4Pと点の加算4P+2P+P
  • ビット3：0　点の倍加8P
  • ビット4：1　点の倍加16Pと点の加算16P+4P+2P+P
  • ビット5：0　点の倍加32P
  • ビット6：0　点の倍加64P
  • ビット7：1　点の倍加128Pと点の加算128P+16P+4P+2P+P=151P

7回の倍加と4回の加算で処理できます。