Elliptic Curve Integrated Encryption Scheme (ECIES) の調査と実装を行いました

WebPayは現在、Apple Payへの対応を進めています。 Apple PayではElliptic Curve Cryptographer(ECC、楕円曲線暗号)が用いられるという事前の情報に基づき、Elliptic Curve Integrated Encryption Scheme (ECIES)の実装を行いました。 結局、Apple Payで送信される暗号文はECIESの形式を満たすものではなかったため、そのまま利用することはできませんでしたが、 この実験を通じて得た知見をもとにテンポよく実装を進めることができました。

本記事はその知見を共有することを目指して、ECIESについて簡単に説明したあと、 実験的に実装したRubyライブラリ、openssl-pkey-ec-iesを紹介します。

ECIESとは

Elliptic Curve Integrated Encryption Schemeの頭文字を取ってECIESと呼称しています。 Elliptic Curveは楕円曲線暗号を使用することを意味します。 Integrated Encryption SchemeはDiffie-Hellman鍵交換と、データを共通鍵暗号で暗号化し、その鍵を公開鍵暗号で暗号化して暗号文をつくるハイブッド暗号を組み合わせ、よりセキュアな情報のやりとりを可能にする方法のことです。 公開鍵暗号とDiffie-Hellman鍵交換に楕円曲線暗号を使っているため、この名で呼ばれます。

公開鍵暗号は解くのが難しい数学上の問題を用いて、暗号化する鍵と復号化する鍵が別個のものでありながら、暗号文のやりとりを可能にする方法です。 従来、広く用いられてきたRSA公開鍵暗号では、因数分解問題を利用していました。 最近では、これに代わって楕円曲線上の離散対数問題を利用した、楕円曲線暗号が用いられ始めています。 楕円曲線暗号はRSA公開鍵暗号に比べて、同じ強度を持つ鍵長が短かいため、処理速度が向上することで知られています。 詳細はOpenSSLWikiのElliptic Curve Cryptographyの項などを参照してください。

公開鍵暗号の難点は、ごく短い文の暗号化しかできないことです。 数学上の問題を利用した暗号なので、巨大なデータを暗号化しようとするとサイズの大きい計算を行うことになり、不必要に時間がかかってしまいます。 そのため、文を共通鍵暗号で暗号化し、その暗号化に使用した鍵を公開鍵暗号で暗号化し、2つのデータを一緒の送信する、ハイブリッド暗号が用いられます。

Integrated Encryption SchemeはDiffie-Hellman鍵交換とハイブリッド暗号を用いて暗号通信する手順を定めています。 IESについてはA Survey of the Elliptic Curve Integrated Encryption Scheme(Gayoso Martínez, Víctor. et, al. JOURNAL OF COMPUTER SCIENCE AND ENGINEERING 2, 2 (2010), 7-13, 2010)が図入りでよくまとまっているので、是非併せてご覧ください。

暗号化

暗号通信の説明の通例にならい、送信者アリスが受信者ボブに秘密のメッセージを送信することにして流れを列挙します 暗号に関する用語がたくさん出てきますが十分に説明できていない箇所もあります。不明な箇所は調べながらお読みください。

アリスの手元には、アリス自身の秘密鍵、ボブの公開鍵、秘密のメッセージがあります。

  1. まず、アリスは一回の通信で使い捨てにする仮の鍵ペア(ephemeral key)を作ります。
  2. 仮の鍵ペアの秘密鍵と、受信者ボブの公開鍵をつかってKey Agreementを行います。 Key Agreementはお互いが秘密鍵を手元に隠した状態で、第三者がわからないバイト列、shared secretを作る操作です。 実際にはDiffie-Helmann鍵交換アルゴリズムの一種になります。 このバイト列はこれ以降の処理で使う鍵の素になります。
  3. shared secretはKey Agreementのアルゴリズムに依存した長さになりますが、大抵そのままでは鍵として短かすぎて使えません。 そこでKey Derivation Functionと呼ばれる関数を用いて、十分な長さに伸ばします。 Key Derivation Functionにはいろいろなバージョンがありますが、だいたいshared secretにバイト列を付加して一方向ハッシュ関数にかけ、つなげるものです。
  4. 共通鍵暗号化とMAC tag作成に十分な長さのバイト列を得たら、これを共通鍵暗号に使う部分(ENC key)とMAC tag作成に使う部分(MAC key)に分割します。
  5. 秘密のメッセージをENC keyを使って共通鍵暗号で暗号化します。こうして暗号化されたメッセージが得られます。
  6. 次に暗号化されたメッセージに対してMAC(Message Authentication Code)アルゴリズムを適用し、tagを作成します。鍵はさきほど作成したMAC keyを使います。

こうして、仮の鍵ペアの公開鍵、暗号化されたメッセージ、MAC tagが得られました。これをセットにしたものが暗号文になります。

復号化

ボブはアリスからこの暗号文を受け取り、復号化します。 手順はアリスが暗号化した時とほとんど同じで、公開鍵暗号の部分だけ秘密鍵と公開鍵が逆になります。

  1. ボブは暗号文に含まれる仮の鍵ペアの公開鍵と、自分の秘密鍵を持っています。 この2つでKey Agreementを行い、アリスが利用したのと同じshared secretを得ます。 Key Agreementアルゴリズムの仕組みにより、やりとりした公開鍵を使って同じshared secretが得られます。
  2. shared secretからアリスと同じKDFで復号化のための鍵を得ます。 KDFはその名の通り写像なので、同じ鍵が得られます。
  3. この自分で作ったMAC keyと、アリスから受け取った暗号メッセージを使ってMAC tagを再計算し、アリスから受け取ったものと同一であることを確認します。
  4. 最後に暗号メッセージをENC keyで復号化して、秘密のメッセージを得ます。

こうして無事二人は通信することができました。

ECIESの難しさ

ここまで、Key Agreement、Key Derivation Function、ENC、MAC等に関して、あえて詳細な言及を避けてきました。 なぜならこれらはIESの仕様では一つに定められておらず、いくつかのアルゴリズムの中から選択できるからです。 逆にいえば、IESが暗号通信方式を定めているといっても、正しくメッセージのやり取りをするためには両者が使用するアルゴリズムについて事前に合意しなければいけません。 さらに、上にあげたサーベイにまとめられているように、現時点でIESの仕様が複数存在し、それぞれ指定しているアルゴリズムが違います。 大抵のアルゴリズムは暗号を扱うライブラリ(OpenSSL libcryptoなど)に含まれている著名なものですが、楕円曲線暗号じたいが比較的新しい技術であることもあり、まだ入っていない場合もあります。 とくにKDFは実装が簡単なぶん、ライブラリなどにおさめられていない場合が多く、仕様書を参照して定義を調べ、ただしく実装しなければいけません。 KDFはKey Derivation Functions: How many KDFs are there?に比較、実装例があり、自分で実装する必要にせまられた時に参考になります。

アルゴリズムのみならず、3つの要素を暗号文にまとめる方法にもばらつきがあります。 ANSI 9.63では共通鍵、暗号メッセージ、MAC tagの順としていますが、とIEEE 1363aでは共通鍵、MAC tag、暗号メッセージとしています。 鍵とMAC tagのバイト長は選択したアルゴリズムから決定できるので、のこりが暗号メッセージとして受信側で分割できる仕組みですが、順番が間違っていてはしかたありません。

他にも、共通鍵暗号で指定するinitialization vectorやKDFのオプショナルな入力について送受信者間の合意が必要です。

暗号通信においてはこのような詳細こそがもっとも重要であり、正しく合意が成立していなければ復号できません。 通信方式を策定をする側は丁寧すぎるくらいに細部まで説明をすべきですし、 実装する側はここまで述べたような事項に関して細心の注意を払う必要があります。

OpenSSL等の広く用いられているライブラリでも、まだ全部を統括して行う実装はなく、 ECDHなどIESの一部の機能を提供しているにすぎません。 公開されている既存の実装を調べましたが、ECIESの仕様に完全には従っていなかったり、バグがあったり、 アルゴリズムの設定の自由度が低いなど、実用に耐えるものは見付かりませんでした。 残念ながら、今回公開したRubyのライブラリも、アルゴリズムを選択するためにCのソースを編集する必要があり、実行時に切り替えることができないなど、未熟な点があります。

OpenSSL::PKey::EC::IESの紹介

以上で説明したECIESをRuby向けライブラリとして実装したものが、今回公開したopenssl-pkey-ec-iesです。 OpenSSL標準ライブラリに含まれるOpenSSL::PKey::ECを拡張して実装しています。 ECIESはこのように複雑な仕組みですが、使い方は非常に簡単です。

まずは楕円曲線暗号の鍵ペアを作ります。OpenSSL::PKey::ECでも、openssl ecparamコマンドでも作れます。

1
2
$ openssl ecparam -genkey -out ec_privkey.pem -name prime256v1
$ openssl ec -in ec_privkey.pem -pubout -out ec_pubkey.pem

その鍵をOpenSSL::PKey::EC::IESのコンストラクタに渡し、インスタンスを作成します。 暗号化には公開鍵を、復号化には秘密鍵を指定します。

OpenSSL::PKey::RSAは公開鍵暗号なので扱える文字列長に制限がありましたが、ECIESは上述のとおりハイブリッド暗号なので長い文字列でも暗号化できます。

1
2
ec = OpenSSL::PKey::EC::IES.new(File.read('ec_pubkey.pem'), "placeholder")
cryptogram = ec.public_encrypt('my secret')  # => cryptogram in string

次に復号化してみます。さきほどの鍵ペアの秘密鍵をつかってインスタンスを作りなおし、#private_decrypt()に暗号文を渡します。 元のメッセージが得られるはずです。

1
2
ec = OpenSSL::PKey::EC::IES.new(File.read('ec_privkey.pem'), "placeholder")
result = ec.private_decrypt(cryptogram) # => 'my secret'

"placeholder"は、今後拡張してアルゴリズムの組み合わせなどを指定するために用意していますが、今は使いません。 空文字か、判別のための文字列を指定しておいてください。

OpenSSL::PKey::EC::IESの詳細

このライブラリはほとんどOpenSSLを使ったc extで構成されています。 実装にあたってはpublic domainで投稿された次のメッセージを参考にしました。 OpenSSL - Dev - Code for using ECIES to protect data (ECC + AES + SHA)

アルゴリズムは次のように選択しています。

  • KA: ECDH
  • KDF: ANSI-X9-62-KDF (a.k.a. KDF2)
  • KDF Hash function: SHA1
  • ENC: AES-128-CBC (iv: null bytes)
  • MAC: HMAC-SHA1
  • 直列化: 共通鍵、暗号メッセージ、MAC tagの順 (ANSI X9.63 形式)

コードでは、openssl-pkey-ec-ies/ies.c:22でコンテクストを作って設定しています。 KDFやIVはここから設定できないので、設定する場合はecies.cを変更する必要があります。

このように設定した理由はJavaのECIES実装であるFlexiproviderと疎通確認をするためです。 実際にRubyで作成した暗号文をFlexiproviderで復号し、またFlexiproviderで作成した暗号をRubyで解読することができます。 ただし、FlexiproviderにはKDFに渡されるshared secretのバイト表現が間違ったものになるバグがありますので注意してください。

まとめ

WebPayでECIES実装をそのまま使うことはなくなりましたが、今後ECIESが必要な人の助けになればと思い、今回公開するに至りました。

理解してみればすぐであるものの、どれを信頼してよいかも定かでなく、自分の知識も不完全という状況で試行錯誤するというのはなかなかに骨の折れるものです。 この記事は、次にECIESに触れる人が少しでもつまづきを無くせればと思い、ライブラリの紹介にとどまることなく、ECIESを使用するうえでの注意点を指摘しました。

こうして自ら暗号方式の実装を行うと、書籍やウェブサイトの説明から得るものと、自分でライブラリを触ったり実装することで得られるものの圧倒的な差に気が付かされます。 公開鍵暗号や証明書についてはウェブエンジニアであれば知識を持っているでしょうが、実際にどのようなフォーマットで記述されているのか、どのような手順で処理されているのか、実装するときはどこに注意しないといけないのかといった詳細を知ると、もっと視野が広がるでしょう。 機会があれば、ぜひ暗号方式や暗号通信に直接、触れてみてください。