BETA

Dragonfly Key Exchangeの概要

投稿日:2019-12-23
最終更新:2019-12-23

Ahoy!

これはセキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2019 の20日目ですが,書くのを忘れていたので投稿日は23日です.

このお話をなんで書くかというと,今年のセキュリティ・キャンプ2019全国大会で実装したDragonfly Key Exchangeの話せなかった部分についてまとめるのを忘れていたことに気が付いてしまったからです.いつかやらなきゃな,は大体忘れています.

この記事は基本的にRFC7664(Dragonfly Key Exchange)に基づいています.手元の資料で分かる限りの補足はするように心がけておりますが,SAEについてはRFCと異なる部分が多いため,明記されている場合を除きRFCの記述とSAEの実装方法は異なる可能性があることをご承知おきください.

概要(3行)

  • 鍵の共有はECDHもしくはDHを使う i.e. この鍵共有の主目的は鍵の共有の確認
  • 確認には2つのステップを踏まなければいけない
  • 共有した鍵が同じかどうかを確認するだけなので,鍵自身が改ざんされていたらわからないし,そもそもの共有方法,実装が脆弱だったら詰み(ですが,実際はペイロードを送信するタイミングが攻撃者に予測されないようになっているため全てが改ざんされる可能性は対策を行わない場合と比べて低いです)

詳細

ここからはスライドでほんのちょっとだけ映った次の図について説明していきます.この図はCommit ExchangeとConfirm Exchangeに焦点を当てています.
なお本章では注釈がない場合,[]は楕円曲線上の点のスカラー倍,+は楕円曲線上の点の足し算とします.

鍵共有の特徴

Dragonfly Key Exchange(以下Dragonflyとする)は (Elliptic Curve) Diffie-Hellman Key Exchange を用いて鍵を共有した際に,鍵が正しく共有されているかを確認することに重点をおいている鍵共有です.PEの導出にも癖があって,パスワードを事前に何かしらの方法で共有しておく必要があります.

事前にパスワードを共有した相手としか共有点をつくれないようにするため,パスワードを基に共有点PEを求めます.PEは楕円曲線上の点にならない場合が多いため,楕円曲線上の点になるまで何回も楕円曲線のパラメータを調整します.

次に,従来のDiffie-Hellman鍵共有において一番の問題点である中間者による攻撃を検知するために,共有鍵とハッシュ関数などを使って各ピア(コンピュータなど)で鍵の正当性を確認します.

この仕組みによって,どちらかの持っている共有鍵が改ざんされている,もしくは欠損している場合にはお互いの出した値が異なるため,その時点での値は捨てて鍵の共有を最初から始めることができます.

共有点PEの導出

PEはP(x,y)が鍵共有で最初に共有した楕円曲線上の点になるまでPasswordをベースとしてseedを作成しhanting-and-pecking技術でPを作ります.counterを使うためhanting-and-pecking技術をk回(kは任意の自然数)繰り返すのですが,kをある程度大きくしておかないと毎回計算が終わる時間が固定されてしまい,サイドチャネル攻撃の原因になってしまうためkを40以上に設定することが推奨されています.Python風に書くとこんな感じです.最後にlsbで反転したりしなかったりがありますが,これはセキュリティの念押しみたいなものです.

[python]  
input : alice_macAddress,bob_macAddress,Password,curve  
k = 40  
counter = 1  
while True:  
  base = hash(counter)  
  seed = KDF(base)  
  if (seed point is on the curve)  
    x = seed  
    break  
  counter += 1  
  if (counter > k)  
    break  
y = calcY(x)  
if (lsb(x) == lsb(base))  
  generateCurvePoint(x,y)  
else  
  generateCurvePoint(x,p - y)  

SAEにおいてPEの導出は基本的にAP側で行われます.これはTLSがサーバ側でPEを計算するのと同じです.

Commit Exchange

共有鍵をそのまま渡して確認していたら第三者に鍵が見つかってしまうので,まずは共有鍵と公開鍵を使って各自で値を求めてみましょう.

前処理として,各ピアでprivateとmaskを定義し,それぞれ1 < private < q1 < mask < q となるランダムな値を設定します.そしてscalarとElementという要素を求めます.これらの要素は次のようになります.
inverseは逆元をとるという意味です.
scalar = (private + mask) mod q
Element = inverse([mask](PE))

この段階で交換する要素は求めたscalarとElementのみで,相手から受け取ったscalarをpeer-scalar,Elementをpeer-Elementと定義します.ここまで計算すると各々でss(secret string)を求めることができて,ssは

ss = hash([private](peer-Element + [peer-scalar](PE)))

となります.ここでPEを使うため,パスワードが正しく共有されていないとお互いのssが共通になりません.

ssを全て送るのは通信量的に効率的とは言えないのでssの上位数ビットを相手に送ります.これを今後はkckと呼ぶことにします.

Confirm Exchange

ここではパスワードが本物かどうか,鍵が改ざんされているかを確かめます.

confirmの式は次の式で求めることができます.+はここでは文字列の連結の意味を表わしています.

confirm = hash(kck + scalar + peer-scalar + Element + Peer-Element)

つまり,kckが異なる=ssが異なる=パスワードが異なることより値がお互いに同じになっていなければ正しく共有されたとは言えません.中間者攻撃を受けた場合にもconfirmの値は等しくなりません.

これを図のように確認すればよい,ということです.

まとめ

このRFC7664で定義された暗号技術は「SAEのための暗号技術」といっても過言ではないと思います.

今までは事前共有鍵を用いていましたがこれからは事前共有鍵ではなく,事前に共有したパスワードを基に共有鍵を決めるため,前方匿秘性がつき比較的安全です.

Dragonbloodなどの脆弱性も見つかっていますが,Dragonbloodを発見した研究者がBlackHatで「WPA3を使うべき」と言っているように,WPA2に存在するKRACKという脆弱性はとても危険です.これからWPA3がいち早く広まることを祈念しつつ結びの言葉とさせていただきます.

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

暗号を学ばなければならない.だからこそ暗号を学ばなければならない

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう