1週間以内で記事にするとは何だったのか。というわけでタイトルの通り、質問で出ていた「Encrypt-then-MACだと安全だけどMAC-then-Encryptだとダメってどういうこと？」について解説します。
宣伝: 第2回もやります
第2回を立てたので今度こそ宣伝します。とはいえ開催2週間前に日程告知することになってしまったのは準備がぬるかったですゴメンナサイ…orz
要約
普通はここだけ覚えてれば十分です。
そもそもここでいう安全性とは？
安全性の概念として、
- 秘匿性 (→(1), (4))
- 完全性 (→(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))で保証されている
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 cipherENCから構成する。このENCはperfect secrecyを持つone-time padのようなものでもよい。ENC*: n-bitの平文xに対し、ENC*はxを以下の要領で 2n-bit のx'にencodeし、そのうえでENCを適用する*1:-
x_i= 0 ならx_(2i-1), x_2iは (0,0) -
x_i= 1 ならx_(2i-1), x_2iは (1,0) または (0,1) のどちらか任意のものを選ぶ -
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の場合は？
- 以上より、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は安全である。
参考文献
- (0) Cryptography Stack Exchange: Should we MAC-then-encrypt or encrypt-then-MAC?
- (1) Krawczyk, “The order of encryption and authentication for protecting communications (Or: how secure is SSL?)”, 2001
- 文中で証明として引用されているのは (2) Caneeti and Krawczyk, “Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels”, 2001。
- (3) Bellare and Namprempre, “Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm”
- (4) 岡本龍明, 『暗号理論における安全性概念』(中央大学数学教室講究録 No.2), 2008
