[要約] Proving the TLS Handshake Secure

##Introduction
TLSには3つの課題がある。

• TLSの安全性は設定に依存

• プロトコルのロジックが複雑

• プロトコルの安全性を保障するには強力なassumptionが必要

###Cryptographic Agility in TLS
Acarにより提案されたAgile Security[1]を用いてTLSの安全性を証明する。
Agilityとは個々にセキュアなプリミティブ(e.g. Authenticated encryption, PRFs, digital signature)が何度も安全に鍵を共有できるという性質のこと。汎用的結合可能性(universal composability)と似て、schemesを抽象化している。
慣習的に、ひとつの鍵を署名と暗号化等の複数の目的で用いることは良くないとされているが、joint security[2]という性質を満たせばそのような場合でも安全であることが証明できる。
TLSがagilityを満たすかどうかはciphersuiteに依存する。ciphershiteとは用いられる暗号primitiveのアルゴリズムの組み合わせのことである。TLS_e_s_WITH_rと表され、eはKEM、sはsignature、rはauthenticated encryptionのアルゴリズムを示す。

[1]http://research.microsoft.com/apps/pubs/default.aspx?id=121045
[2]https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&es_th=1&ie=UTF-8#q=securely%20combining%20public-key%20cryptosystems
###Empirical Study of Web Servers and Browsers
online analyzer[1]を用いて、有名なサイトの設定を確認した。

[1]https://ssllabs.com/ssltest/analyze.html

###Cross-Ciphersuite Attacks
典型的なCross-Ciphersuite Attacksを紹介する。
一つ目は、鍵の使い回しによる攻撃である。KEMとsigningの両方で同じ鍵を使用する設定は非推奨になっているにも関わらず多くのサイトがこの設定に対応している。
二つ目は、DHとECDHに関しての攻撃である。TLS1.2で新たに追加されたSRP(Secure Remote Password)とPSK(Pre-shared key)とECDHを用いて、サーバをoracleとして使用することで攻撃を行う。[1]
三つ目は、DEMにおいてFalse Start[2]を用いた攻撃である。False Startにより、共有鍵の確認を行う前にdataを送信する。これにより、お互いが違うアルゴリズムで通信を行うことでkey recovery attackをされる可能性がある。

[1]http://dl.acm.org/citation.cfm?id=2382206
[2]http://tools.ietf.org/html/draft-bmoeller-tls-falsestart-00

###Multiple Sessions and Connections
Bellare & Rogaway[1]とは違い、TLSの場合はsession毎にparameterを共有する[2]。ServerとClientの集合をepochsとし、各epochはhandshakeを走らせる。完全なhandshakeを走らせるepochをsessionと呼び、省略されたhandshakeを走らせるepochをresumptionと呼ぶ。
Sessionは新しいmaster secretを作成するが、Resumptionは前回の完全なsessionを用いる。

[1]http://link.springer.com/chapter/10.1007/3-540-48329-2_21
[2]https://tools.ietf.org/html/draft-ietf-tls-rfc5246-bis-00#page-85

###Proving the TLS Handshake Secure
この論文ではTLSのhandshakeに焦点を絞る。互いに情報を共有してしまうsessionをAgilityを考慮しながらモデリングする。また、RSAとDSAを用いた署名を基本とした一方向、双方向認証もモデリングする。
dual-purpose keyに関しては、この方法では克服できない。
TLSの特徴は、handshakeの途中でrecord layerにアルゴリズムとderived keyを渡すことである。これにより、最後のmessageはTLSで暗号化することができる。
モジュール性を実現するために、record key generationとhandshakeを分割する。これらを分割することで、攻撃者にnetworkとrecord layerの両方を操作させることが安全にできる。
Completionは、record-keyが安全であることを確認するために必要である。Completion自体の安全はFinished message controversy[1]を使うことで確保できる。

[1]http://link.springer.com/chapter/10.1007/978-3-642-32009-5_17
###Overview of the Paper

• Agile signatures and certificates

比較的単純なagile definitionから始める。TLSは3つの署名アルゴリズム(RSA, DSA, ECDSA)をサポートしている。hashのalgorithmはversionに依存する。versionによっては弱いhashを使用することがあるので、どのような組み合わせならば安全になるのかを証明する。

• Master secrets, key encapsulation, and key derivation

handshake全体をKEMとして扱うのではなく、premaster secret, master secret, record-key derivationの3つのpahseに分ける。master secretをpremaster secretからsecureに生成する方法とrecord-keyとFinished messageを取り出す方法を示す。
一度作られると、master secretはPRFの鍵として複数のepochsに2つの目的で使用される。ひとつは、record-keyを抽出するため、hutatumeha,MACを計算するためである。

• Agile security model and TLS proof for multiple sequences of handshakes

handshakeの主な目的は二つある。ひとつは、record layerで使用する共通鍵を共有すること、もうひとつは、いくつかのparameterを固定することである。
Adversaryには、honest connectionsとlong-term keyを作るためのorcaleを持たせる。これにより、Adversaryを制御することとmessageを交換することができるようになる。
提案法ではsecure key derivationも提供する。これはBellare-Rogawayのsession identifiersに似ているが、safetyとpartneringの両方を定義する点で異なる。
recorded long-term keyによるsessionが安全である条件のverified safetyも提供する。
提案手法により、TLSのsecurityの証明を個々の組み合わせに対して行わなくても、全体として安全性を証明できる。
このmodelでは、record layerでの各algorithmについて説明する。

• Code-Based Verified Implementation

###Notation

##Agile Signature

agile signature schemeは3つのalgorithmから構成される。
KeyGenは鍵生成algorithmであり、Sing と Verifyはひとつのagility parameterをとる。
署名スキームs = (keygen, sign, verify)、hash-then-sign scheme $S_s$ = (KeyGen, Sign, Verify)とする。
Definition1を満たす時、EUF-CMAという。
hash algorithmが固定され一致している場合は、$p \in P$の確認は行わない。
hとh'が与えられ、core signature scheme自体がjoint range上で$(\epsilon, t)$-EUF-CMA secureな場合、$(\epsilon^\prime, t^\prime, h, {h,h^\prime})$-secureを満たすagile hash-then-sign signatureを証明できる。
しかし、TLSで使用されるcore signature schemesはEUF-CMA secureではない。

Agile Signatureを満たすために、筆者らはhashにvariationを持たせている。つまり、hash functionのアルゴリズムを固定しなくても、個々のhash functionである制約を満たせばsignature全体がsecureであることを証明している。

##Master Secrets & Key Encapsulation
RSAとDHにおいてのpremaster phaseをmodelingする。

####RSA
keygenは(pk, sk)を作成する。enc(pv, pk)は46byteの乱数をpvに追加したpms(pre-master secret)とPKCS#1v1.5で作成した暗号文cを返す。dec(pv, sk, c)はcを復号する。
####Deffie-Hellman
keygenはgroup parameterであるppを選択した後に、$(g^x, x)$を計算し、$pk=(pp, g^x)$と$sk=(pk, x)$を返す。$enc(pv, (pp, g^x))$はyを選択し、$pms=g^{xy}$と$c=g^y$を返す。$dec(pv, (pk, x), c)$は$c^x = g^{xy}$を返す。

これらのpmsはIND notionにおいてsecureではない。pmsは鍵として使われるのではなく、key extraction function(KEF)に渡されて、master secret(ms)を作るのに使用される。master secretのKEMはagile labeled KEMとしてmodelingする。これのagility parameterはvalid protocol versionとhash algorithmである。

###Generic ms-KEM construction
master secretを共有するphaseのKEMをagile labeled KEMと定義する。これは、labeled KEMにagile parameterを加えた拡張版である。
pms-KEMはe=(keygen, enc, dec)、agile key extraction function familyはKEF,master secret KEM(ms-KEM)は $E_e=(KeyGen, Enc, Dec)$とする。
ms-KEMの定義は以下とする。

• KeyGen

$KeyGen() \equiv keygen()$

• Enc(pv, h, pk, l)

Enc(pv, h, pk, l):
$pms, c \gets enc(pv, pk)$
$ms \gets KEF(pv, h, pms, l)$
return ms,c

• Dec(pv, h, sk, l, c)

Dec(pv, h, sk, l, c):
$pms \gets dec(pv, sk, c)$
$if pms = \perp then pms \gets pv \parallel $$

Definition2のIND-RCCAは3つのPKEにおいて既知の要素を組み合わせて構成されている。

• label-based IND-CCA

• IND-RCCA[1]

• n-IND-CCA

[1]http://eprint.iacr.org/2003/174.pdf

##疑問
####- Lemma1が分からない。
n-IND-CCAの変形をそのまま使用している。RCCAiのiはhybrid argumentの位置を示している。

####- resumption handshakeとは何か？
前回の完全なsessionを再利用してconnectionを生成する方法をresumptionと呼ぶ。これにより、connectionを生成するコストを省けるが、security上の問題がある。

####- ms-KEM、pms-KEMとは何か？
####- p.8のPKCS#1v1.5におけるa randomly chosen 46-byte stringとは何か？
####- Introductionにおいてひとつの証明書を複数の目的に使うことで、より状況が悪化しているとあるが具体的にどのような使われ方をしているのか？
参考: Wildcard Certificate
####- masterがPRFのアルゴリズムを変えるだけで、同じ秘密を使い回すかもしれないというのは、仕様に書かれている？それとも、そのような慣習がある？
####- p.8で(p*, P) = (MD5, {MD5,...})と表現しているが、どういう意味なのか分からない。
参考:pはhash functionでPはhash function familyという様な記述があったが、$p \not\in P$のpatternもあるのでよく分からない。

Pはオラクルがsignできるhash function familyであり、pはadversaryが問い合わせているhash functionである。なので$p \not\in P$の状態があっても何の問題もない。

####- p.8のthe pre-image security of MD5とは。
t = MD5(m)とした時、tをhash value、mをpre-imageと呼ぶ。tからmを求められないことをpre-image securityと呼ぶ。
t = MD5(m) = MD(m1)となるような、m1が見つからないことはsecond pre-image securityと呼ぶ。

####- p.8のdisjoint rangeとは。
アルゴリズムごとにidのようなものを割り振り、アルゴリズムが違うがhash値は一緒ということをさけている。実際のhash値ではないidの部分をdisjoint rangeと呼ぶ。

####- p.8でEUF-CMA secureを満たさないと直前で述べているのに、Definition1が成り立つことを仮定している。
Pとpの組み合わせ次第ではEUF-CMAよりも弱いmodelをDefinition1では作ることができる。(MD5, {SHA1})はその例である。