Encrypt-then-MAC vs MAC-then-Encrypt (『プロフェッショナルSSL/TLS』読書会第1回フォローアップ記事)

1週間以内で記事にするとは何だったのか。というわけでタイトルの通り、質問で出ていた「Encrypt-then-MACだと安全だけどMAC-then-Encryptだとダメってどういうこと?」について解説します。

宣伝: 第2回もやります

第2回を立てたので今度こそ宣伝します。とはいえ開催2週間前に日程告知することになってしまったのは準備がぬるかったですゴメンナサイ…orz

ptls-study.connpass.com

要約

普通はここだけ覚えてれば十分です。

  • 結論だけ取り出すと、EncryptがIND-CPAかつMACがsecure MAC(どちらも定義は示しますが、「まとも」と読んでおけばよい)であるとき、
    • Encrypt-then-MACは安全
    • 一方MAC-then-Encryptでは安全でない場合がある
      • ただし、MAC-then-Encryptでも暗号化がOne-Time Pad、randomized counter mode(CTRモード)、ランダムな初期化ベクタでのCBCモードのときは安全。ECBモードのときに問題がある。
      • 固定IV、もしくは予測可能なIVのCBCモードは実質ECBモードと同じのため攻撃が可能。BEAST攻撃に利用された。

そもそもここでいう安全性とは?

安全性の概念として、

  • 秘匿性 (→(1), (4))
    • IND(強秘匿性, Indistinguishability): 暗号文から平文についての部分情報が得られないことを示す性質
      • IND-CPA: 選択平文攻撃下での強秘匿性
      • IND-CCA: 選択暗号文攻撃下での強秘匿性
      • CPA, CCAの定義は(4)の3.3.2参照
    • NM(頑強性, Non-Malleability): 「ある暗号文から、関連する平文へと復号される新しい暗号文を得る」ことが難しいことを示す性質
      • NM-CPA: 選択平文攻撃下での頑強性
  • 完全性 (→(3))
    • INT-PTXT: 送信者が暗号化していないメッセージに復号されるような暗号文を生成することが困難である性質
    • INT-CTXT: 送信者が一度も生成していない有効に復号される暗号文を生成することが困難である性質

というクラスがある。(メモ:このうちINDとNMに関するクラスは暗号学で広く使われるが、INT-PTXT/INT-CTXTはこういう形式では今のところ(3)でしか使われているのを見たことがない)

より厳密に「安全性」を説明すると、Encrypt-then-MACはstrongly unforgeableなMACを使うことでIND-CPA/IND-CCA/NM-CPA/INT-PTXT/INT-CTXTすべての性質を満たすことができるが、MAC-then-EncryptはIND-CPAとINT-PTXTしか満たすことができないことが示されている(→(3))。

EncryptとMACの役割

  • Encrypt(暗号化)は引数の秘密性を保証し、
  • MACは引数の真正性を保証する。

組み合わせによって何が起こるか

EtM: Encrypt(plaintext) + MAC(Encrypt(plaintext)) では:

  • 平文の秘密性はEncryptで保証されている
  • 暗号文の真正性がMAC(Encrypt(plaintext))で保証されている
    • 仮に暗号文が挿し替えられていたとしても、MACのほうも挿し替えなければMACが一致せずエラーとなる。
    • これにより、真正な暗号文のみが復号されるので、結果として平文の秘密性と真正性の両方が保たれることになる。

MtE: Encrypt(plaintext + MAC(plaintext)) では:

  • 暗号文の真正性は担保されない。復号するまで真正なものかニセモノかわからない。
  • 平文の真正性は復号結果のMAC(plaintext)によって保証されている
  • 平文の秘密性はEncryptによって保証されている

ここで、MtEで使うEncryptがmalleable(=NMでない)場合に選択暗号文攻撃(=CCA)が成立してしまうことが問題である、という性質があるため、MtEは脆弱である、というふうに言われる。

具体例としては、AESをECBモードで使った場合にはECBモードがmalleableであるためMAC-then-Encryptでは安全性が保たれない。

MAC-then-Encryptが脆弱である例

(1)で示されている例を示すと、

  • IND-CPAな暗号方式 ENC* を stream cipher ENC から構成する。この ENC はperfect secrecyを持つone-time padのようなものでもよい。
    • ENC* : n-bitの平文 x に対し、 ENC*x を以下の要領で 2n-bit の x' にencodeし、そのうえで ENC を適用する*1:
      1. x_i = 0 なら x_(2i-1), x_2i は (0,0)
      2. x_i = 1 なら x_(2i-1), x_2i は (1,0) または (0,1) のどちらか任意のものを選ぶ
      3. x_(2i-1), x_2i として (1,1) が入っていたらdecodingの段階でエラーとする。
  • ENC* のみが使われているときに、1bit目の中身を以下の方法で知ることができる:
    • ENC*(x) をinterceptし、
    • (y_1, y_2) をbit反転させた y' を構築してそれを送信
    • 復号が成功したら1bit目は1、復号が失敗したら1bit目は0
      • 理由: (0,0)を反転したら(1,1)になり、これは復号のdecode時にエラーになるため。(1,0)と(0,1)は反転させてもdecodeは成功する。
    • これを1bit目から順番に1bitずつやれば全bitの中身がわかる
    • (筆者注:これはIND-CPAだがIND-CCAでない*2暗号を(IND-CPAよりも強い)perfect secrecyのある暗号から構築できる、ということを示している。1bitごとの復号オラクルができてしまっている!)
  • MAC-then-Encryptの場合は?
    • MACエンコード前の平文に適用されることに注意。暗号文を改変しても同じ平文にたどり着く場合MAC checkは成功する。そうでない場合MAC checkは失敗。
    • 攻撃対象の平文のbitが1ならMAC checkは成功、0なら失敗。結果として同じ。
  • 以上より、IND-CPAな暗号ENC*を使ってもMAC-then-EncryptがinsecureなケースがあるMAC-then-Encryptがsecureであるためにはより強い概念が必要である。

MAC-then-Encryptで問題ないケース

(1)ではさらに、

  • MACがone-query attackに耐えるものであればOne-Time Padを使ったMAC-then-Encryptは安全
  • MACがsecure MAC familyであればCBC with random IVを使ったMAC-then-Encryptは安全

であることを示している。One-Time Padの代わりにnon-repeating nonceを使っても同じ結果が得られるため、CTRモードを使ったMtEは安全である。

参考文献

*1:6/16修正: ENC適用しなかったらただのencodingで暗号化でもなんでもない、当然IND-CPAですらない

*2:6/16修正: この構成はCCAの成立のみを示しているので、Non-malleabilityについては何も示していない、よってここはNM-CPAではなくIND-CCAが正しい。