ダブルラチェットアルゴリズムをRubyで実装する

ダブルラチェットアルゴリズム（Double Ratchet Algorithm）をRubyで実装してみる。

このアルゴリズムはSignalプロトコルの主要な構成要素の1つであり、Signalの公式Webサイトに[技術的なホワイトペーパー](https://signal.org/docs/specifications/doubleratchet/)がある。今回はこのドキュメントにできるだけ沿った形での実装を目指す。

動くコードは https://github.com/ts-3156/doubleratchet-ruby に置いています。

## ダブルラチェットアルゴリズムで何ができるか

ダブルラチェットアルゴリズムを正しく実装できれば、Signalアプリのような匿名メッセンジャーアプリを作ることができます。

現代的で堅牢な暗号通信を実装するにはダブルラチェットアルゴリズムはほぼ必須の要素です。

暗号通信において、ダブルラチェットアルゴリズムはX3DHプロトコルで鍵交換をした後の「メッセージ本文の送受信時」に使用されます。


## ダブルラチェットアルゴリズムとは

ダブルラチェットアルゴリズム（Double Ratchet Algorithm）は、暗号通信に用いる秘密鍵を随時更新することでその通信における前方秘匿性、後方秘匿性を提供します。つまり、秘密鍵が漏洩したとしても過去のメッセージの復号化はできず、将来のメッセージの復号化にもある程度の耐性があります。


ダブルラチェットアルゴリズムでは、対象鍵ラチェットとDHラチェットを組み合わせることでこの性質を実現しています。


:::note alert
暗号化アルゴリズムや暗号化プロトコルにはたくさんの種類があり、誤用しやすく、潜在的な落とし穴がたくさんあります。

安全なセキュリティシステムの設計を正しく行うことは非常に難しく、通常はセキュリティ専門家の領域となります。

設計や実装にほんの小さな間違いがあるだけでセキュリティが完全に無効になる可能性があります。

この記事の作者はセキュリティ専門家ではありません。できるだけ正しい情報を書くよう心掛けていますが、書かれた情報の正しさはご自身で検証してください。
:::

## ダブルラチェットアルゴリズムの仕組み

ダブルラチェットアルゴリズムの詳細な動作については [技術的なホワイトペーパー](https://signal.org/docs/specifications/doubleratchet/) をご確認ください。分かりやすく解説されています。

その上で、この記事では公式ドキュメントだけでは理解が難しかった点のみ解説します。

#### 受信/送信チェーンとは受信/送信用の秘密鍵を生成するKDFチェーンのこと

「送信チェーン」という名前は抽象的で意味が分かりづらいですが、これはKDFチェーンを指しています。つまり、送信チェーンでは1つ前のチェーンキーから次のチェーンキーとメッセージキーを生成することを繰り返しています。受信チェーンについても同じです。

#### 送信者の送信チェーンは受信者の受信チェーンと一致する

公式ドキュメントではアリス（= 送信者）の送信/受信チェーンのみ記載されていますが、実際はボブ（= 受信者）も全く同じチェーンを持っています。送信者と受信者で役割が反対なため、一方の送信チェーンはもう片方の受信チェーンと一致します。

#### 新しい公開鍵を受信すると受信/送信チェーンが作り直される

新しい公開鍵（= 新しいメッセージ）が届くと受信/チェーンが作り直されます。この「作り直す」とは、長さが0の状態にリセットされるということです。注意点として、新しいメッセージに必ず新しい公開鍵が含まれているわけではありません。一方が連続してメッセージを送信すると、それらのメッセージには同じ公開鍵が含まれています。

#### PNとは1つ前の送信チェーンの長さのこと

PNは作り直される前の送信チェーンの長さです。新しい公開鍵でDHラチェットステップが適用されると送信チェーンがリセットされます。このリセット前の送信チェーンの長さのことです。実装上は、新しい公開鍵が届いた瞬間のみ使用されます。

#### 「順序が乱れたメッセージ」の扱いはコードを見た方が早い

送信と受信の順番が時系列通りではない場合について、文字と図の説明だけだと非常にややこしく感じますが、実装上はかなりシンプルに解決されています。ドキュメントに載っているPythonの参考コードを事前に見ておくことをおすすめします。

## Rubyで実装したコード

Rubyでの実装にはlibsodiumのRubyバインディングであるRbNaCl gemを用いています。

暗号プリミティブの独自実装はせずにライブラリで用意されているものを利用しています。

```ruby
def generate_dh
    key = RbNaCl::PrivateKey.generate
    [key, key.public_key]
end
```

X25519形式の鍵を使用しています。RbNaCl::PrivateKeyはBoxes::Curve25519XSalsa20Poly1305::PrivateKeyのエイリアスです。

```ruby
def dh(key1, key2)
    RbNaCl::GroupElement.new(key2).mult(key1)
end
```

DHの計算には楕円曲線上でのスカラー乗算を直接用いています。

```ruby
def kdf_rk(rk, dh_out)
    opt = {
        salt: rk,
        info: 'MyApplication'.unpack1('H*'),
        length: 64,
        hash: 'SHA256'
    }
    out = OpenSSL::KDF.hkdf(dh_out, **opt)
    [out[0..31], out[32..63]]
  end
```

`KDF_RK(rk, dh_out)`の実装にはRubyの`OpenSSL::KDF.hkdf`を用いています。前半32バイトがルートキー、後半32バイトがチェーンキーになります。

```ruby
def kdf_ck(ck)
    new_ck = OpenSSL::HMAC.digest('sha256', ck, ['02'].pack('H*'))
    mk = OpenSSL::HMAC.digest('sha256', ck, ['01'].pack('H*'))
    [new_ck, mk]
end
```

`KDF_CK(ck)`の実装にはRubyの`OpenSSL::HMAC.digest`を用いています。これを選んだ理由は公式ドキュメントで推奨されるアルゴリズムとして「SHA-256またはSHA-512を使用したHMAC」が指定されているためです。
おそらくパフォーマンス上の理由でhkdfではなくhmacが指定されているのだと思われます。

```ruby
def encrypt(mk, plaintext, ad)
    cipher = RbNaCl::AEAD::XChaCha20Poly1305IETF.new(mk)
    # メッセージキーは一度しか使用されないため、nonceは固定の値でもかまわない。
    nonce = ['00' * cipher.nonce_bytes].pack('H*')
    cipher.encrypt(nonce, plaintext, ad)
end
```

暗号化アルゴリズムにはSIVモードまたはCBCモードとHMACの組み合わせによるAEAD暗号方式が推奨されており、理由として「鍵の誤用にある程度の耐性があるから」と書かれています。どちらを選んだとしても今回の環境では独自実装が必要になるため、ライブラリで用意されているXChaCha20Poly1305IETFを暗号化方式として採用しました。

```ruby
def decrypt(mk, ciphertext, ad)
    cipher = RbNaCl::AEAD::XChaCha20Poly1305IETF.new(mk)
    nonce = ['00' * cipher.nonce_bytes].pack('H*')
    cipher.decrypt(nonce, ciphertext, ad)
end
```

復号化は特に工夫なく普通に行っています。

```ruby
def message_header(dh, pn, n)
    {dh: dh, pn: pn, n: n}
end

def concat(ad, header)
    ad + Marshal.dump({dh: header[:dh].to_bytes, pn: header[:pn], n: header[:n]})
end
```

メッセージヘッダーとAssociated dataはバイトシーケンスとしてそのまま連結しています。

```ruby
def ratchet_encrypt(state, plaintext, ad)
    state[:cks], mk = kdf_ck(state[:cks])
    header = message_header(state[:dhs_pub], state[:pn], state[:ns])
    state[:ns] += 1
    [header, encrypt(mk, plaintext, concat(ad, header))]
end
```

`RatchetEncrypt()`はPythonの参考コードをそのままRubyで書き直しています。

```ruby
def ratchet_decrypt(state, header, ciphertext, ad)
    header[:dh] = RbNaCl::PublicKey.new(header[:dh])
    plaintext = try_skipped_message_keys(state, header, ciphertext, ad)
    return plaintext if plaintext

    if header[:dh] != state[:dhr]
      # 以前の受信チェーンのスキップ済みメッセージキーを保存しておく
      skip_message_keys(state, header[:pn])
      dh_ratchet(state, header)
    end

    # 新しい受信チェーンのスキップ済みメッセージキーを保存しておく
    skip_message_keys(state, header[:n])
    state[:ckr], mk = kdf_ck(state[:ckr])
    state[:nr] += 1
    decrypt(mk, ciphertext, concat(ad, header))
  end
```

`RatchetDecrypt()`は暗号文の復号化とスキップされたメッセージキーの保存の役割を持っています。この関数も元のPythonコードをそのままRubyで書き直しているのですが、「順序が乱れたメッセージ」の扱いを非常にスマートに解決していて驚きます…！

----

残りの関数については公式ドキュメントのPythonコードとRubyで書き直したコードにあまり差がないため説明を省略します。

動くコードは https://github.com/ts-3156/doubleratchet-ruby に置いています。

## セキュリティ上の考慮事項

[公式ドキュメント](https://signal.org/docs/specifications/doubleratchet/#security-considerations) をご確認ください。


## 参考にした情報

https://signal.org/docs/specifications/doubleratchet/

https://github.com/RubyCrypto/rbnacl

https://doc.libsodium.org/

https://github.com/ts-3156/doubleratchet-ruby/