sonickun.log

備忘録

GoogleがTLSでの採用を提唱している共通鍵暗号方式「ChaCha」についてまとめた

セキュリティ プログラミング

ChaCha（チャチャ）という一見ふざけた名前の暗号が最近（自分の中で）話題ということで，勉強がてらに記事にしてみました．

背景

2016年4月現在，TLSの新しいバージョンとしてTLS 1.3が提案されており，ドラフトが公開されている．

TLS 1.2からの大きな変更点として，以下の2つがある．

  • ハンドシェイクの省略によるRTT（Round Trip Time）の削減
  • 危殆化した暗号の廃止

「危殆化した暗号」とは，Forward SecrecyでないCipher Suite（RSAのみを用いたもの）や，認証つき暗号でないCipher Suite（CBCモードのブロック暗号やRC4を用いたもの）のことを指す．
上記のドラフトによれば，2016年4月現在で実装必須暗号として制定されている暗号方式は以下の通りとなっている．

A TLS-compliant application SHOULD implement the following cipher
suites:

TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256

共通鍵暗号は，ブロック暗号としてAES，ストリーム暗号としてChaCha20の二つのみとなっており，3DESやRC4は廃止される見込みである．
ChaChaという，実績も少なく，聞き慣れない暗号方式がTLS 1.3で提案されている理由の一つとして，Googleがこの暗号方式を推奨していることが挙げられる．

TLS1.3の他に，次世代のWeb通信規格として，HTTP/2がある．HTTP/2は元々はGoogleのSPDYを元に策定さていることもあり，GoogleのTLS 1.3に対する発言力もかなり大きいものと推察できる．

ChaChaの構造

Salsa20

Salsa20は，ダニエル・バーンスタインによって開発されたストリーム暗号であり，後に同氏がSalsa20の変種としてChaChaを発表した．両者は互いに似たような構造を持つが，今回はChaChaのアルゴリズムを中心に解説する．

Chacha

ChaChaは，RFC 7538によって標準化されている．
ChaChaの暗号化と復号は，まったく同じ手順によって実現可能である．暗号化・復号の流れの全体像は以下のとおりである．

1. 定数，鍵，ブロックカウント，Nonce から64byteの入力ストリームを作る
2. 入力ストリームに対して20ラウンドの演算を行い，最終アレイを元のアレイに加えて64byteの出力ストリームを得る
3. 最後に平文と出力ストリームのXORをとり，暗号化（復号）する

初期状態

上記の手順1について，入力ストリームは以下のように定まる．

  • 定数：16byte（4 words）->{0x61707865, 0x3320646e, 0x79622d32, 0x6b206574}
  • 鍵：32byte (8 words)
  • ブロックカウント：4byte（1 word）
  • Nonce: 12byte（3 words）

ブロックカウントとは，暗号化（復号）するブロックが何番目のブロックかを示しており，1ブロック64byteなので，最大256GBのデータまで対応できる．
Nonceは1度だけ使われるワンタイムトークンを意味し，リトルインディアンで格納される．
入力ストリームの構造は以下のようになる．

cccccccc cccccccc cccccccc cccccccc
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn

c=constant k=key b=blockcount n=nonce

ラウンド操作

ChaChaは"ChaCha20"とも呼ばれるように，合計20ラウンドの操作を行う．
ChaChaのラウンドは"column rounds"と"diagonal rounds"という二種類のラウンドの繰り返しとなる．またそれぞれのラウンドは以下のように4つの"quarter-rounds"で構成されている．QUARTERROUNDの引数はストリームの何番目のwordかを示す．

# column rounds
QUARTERROUND ( 0, 4, 8,12)
QUARTERROUND ( 1, 5, 9,13)
QUARTERROUND ( 2, 6,10,14)
QUARTERROUND ( 3, 7,11,15)

# diagonal rounds
QUARTERROUND ( 0, 5,10,15)
QUARTERROUND ( 1, 6,11,12)
QUARTERROUND ( 2, 7, 8,13)
QUARTERROUND ( 3, 4, 9,14)

また，ラウンド関数QUARTERROUND()の演算は以下のように行う．なお，^は排他的論理和，<<<は左ローテート操作を示す．

QUARTERROUND(a, b, c, d):
    a += b; d ^= a; d <<<= 16;
    c += d; b ^= c; b <<<= 12;
    a += b; d ^= a; d <<<= 8;
    c += d; b ^= c; b <<<= 7;

最後に，手順3にある通り，ラウンド操作を施したストリームと入力ストリームを足しあわせて出力ストリームとし，暗号文（平文）とXORをとることで復号（暗号化）できる．


ChaChaの安全性

Salsa20およびChachaは，XOR，32-bit addition mod 2^32，32ビット長のワード16個のローテートを用いており，これにより，ソフトウェア実装におけるタイミング攻撃を回避することができる．
2013年時点では，Salsa20/12およびSalsa20/20の解読に成功した例はない．最良の攻撃法では12あるいは20ラウンド中8ラウンドまで解読されている．
ChaChaではラウンドごと，あるいはブロックごとの発散を大きくすることでSalsa20に比べパフォーマンスが向上している．ChaChaに対する攻撃も試みられたが，Salsa20よりも1ラウンド少ない結果となり失敗した．

その後の経過について調べることができなかったが，AESのように十分な安全性評価を行ったのかどうかが疑問に残る．


実装してみた

2015年に開催されたTrend Micro CTFの演習問題で出題されたChaCha暗号の問題を解いてみる．

Hi this is chacha. I'm 20 years old.
I have a question. Could you answer a question below?...haha. Just kidding.
6bd00ba222523f58de196fb471eea08d9fff95b5bbe6123dd3a8b9026ac0fa84

Key: 23AD52B15FA7EBDC4672D72289253D95DC9A4324FC369F593FDCC7733AD77617
nonce:5A5F6C13C1F12653

"Hi this is chacha."と言っていることから，これはChaChaで暗号化された文章であることがすぐに分かる．

Solver

なお，今回は暗号文が1ブロック分のデータ量しか無かったため，ブロックカウントの更新は実装していない．

Result

flag: TMCTF{Whose_garden_is_internet?}

無事，ChaCha暗号を復号できたことが分かる．

参考


2015/04/04 追記
このエントリが公開された翌日に，ChaCha20-Poly1305についてさらに詳しくまとめられた記事が出ました．
ぜひこちらも併せて読んでみると良いと思います．
d.hatena.ne.jp