Pythonでストリーム暗号RC4を実装し、脆弱性の一端を垣間見る

Crypto

この頃、SSLの暗号化などにストリーム暗号RC4を使わないほうがいいといった話がよく聞かれるようになった。 2013年版のCRYPTREC暗号リストでも128bitのRC4が「運用監視暗号リスト」に入っているし、先日には、Microsoftからストリーム暗号RC4を使わないようにというセキュリティアドバイザリが出ている。 CVEとしては今年の3月に出ているようだ。

そこで、ここでは実際にPythonでRC4を実装し、RC4の脆弱性に関する簡単な例を再現してみる。

ストリーム暗号とは何か

暗号には大きく分けて公開鍵暗号と共通鍵暗号がある。 公開鍵暗号は、他人に見られても大丈夫な鍵（公開鍵）と自分だけが知っている鍵（秘密鍵）のペアを使って暗号化するもので、代表的なものにRSAがある。 一方、共通鍵暗号は送信者・受信者で共通の鍵を使って暗号化する。 共通鍵暗号は、さらにブロック暗号とストリーム暗号に分けられる。 ブロック暗号は、一定のbit数のブロックごとに暗号化する方式で、代表的なものにAESがある。 ストリーム暗号は、1ビットあるいは1バイト単位で逐次的に暗号化していく方式で、RC4はこれに該当する。

PythonでRC4を実装してみる

RC4は、一定のbit数の鍵から256マスの変換テーブル S を生成し（KSAフェーズ）、この S を更新しながら数字を1バイトずつ出力する（PRGAフェーズ）。 そして、この出力された数字とメッセージを1バイトずつXORしていくことで暗号化が行われる。 復号についても、同様の手順で数字を出力し1バイトずつ暗号文とXORすることで元のメッセージを得る。

実際にアルゴリズムをPythonで書くと、次のようになる。 なお、演算の詳細はそのままなので省略する。

# -*- coding: utf-8 -*-

def KSA(key):
    # key から256マスの変換テーブル S を作る
    S = range(256)
    j = 0
    for i in xrange(256):
        j = (j + S[i] + ord(key[i % len(key)])) % 256
        S[i], S[j] = S[j], S[i]
    return S

def PRGA(S):
    # S を更新しながら1バイトずつ数字を吐き出すジェネレータを返す
    i, j = 0, 0
    while True:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        K = S[(S[i] + S[j]) % 256]
        yield K

def RC4(data, key):
    # data がメッセージなら暗号化、暗号文なら復号する
    S = KSA(key)
    gen = PRGA(S)
    data = bytearray(data)
    result = bytearray(c ^ n for c, n in zip(data, gen))
    return str(result)

# 鍵とメッセージを準備
key = 'this_is_a_key'
message = 'this_is_a_message'

# 暗号化して、復号する
print "key: %r (%d bits)" % (key, len(key)*8)
print "message: %r" % message
ciphertext = RC4(message, key)
print "ciphertext: %r" % ciphertext
message2 = RC4(ciphertext, key)
print "message2: %r" % message2

実行すると、正しく復号できていることが確認できる。

$ python rc4.py
key: 'this_is_a_key' (104 bits)
message: 'this_is_a_message'
ciphertext: 'HB\xcb\xe2\xa1sv\x10\x1c\xaf9\x91n\xdb\x06`*'
message2: 'this_is_a_message'

脆弱性の一端を垣間見る

上のアルゴリズムからわかるように、暗号としては PRGA が吐き出す数字の列が完全ランダム（真正乱数）に近いほどよい。 しかし、実際にはこの数字の列はそれほどランダムではない、つまり偏り（バイアス）があることがわかっている。

たとえば、PRGAが吐き出す2個目の数字について、0が出る確率は他の値より2倍大きい [Mantin and Shamir 2001]。 なので、同じメッセージを大量の異なる鍵で暗号化したものが得られれば、2文字目の出現頻度を計算し一番多いものを選ぶことで、元のメッセージの2文字目を復元できる。 なお、この場合は一番多く現れる数字が0、つまりXORしても値が変わらないので元のメッセージがそのまま現れるが、0以外の場合でも暗号文をその数字でXORすることで同様に復元できる。

実際に、Pythonで確かめてみる。 次のコードは、同じメッセージを2^16個のランダムな鍵で暗号化し、2文字目の出現頻度をカウントし、最も多い文字を出力する。

# -*- coding: utf-8 -*-

def KSA(key):
    # key から256マスの変換テーブル S を作る
    S = range(256)
    j = 0
    for i in xrange(256):
        j = (j + S[i] + ord(key[i % len(key)])) % 256
        S[i], S[j] = S[j], S[i]
    return S

def PRGA(S):
    # S を更新しながら1バイトずつ数字を吐き出すジェネレータを返す
    i, j = 0, 0
    while True:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        K = S[(S[i] + S[j]) % 256]
        yield K

def RC4(data, key):
    # data がメッセージなら暗号化、暗号文なら復号する
    S = KSA(key)
    gen = PRGA(S)
    data = bytearray(data)
    result = bytearray(c ^ n for c, n in zip(data, gen))
    return str(result)

import os
# メッセージは共通
message = 'this_is_a_message'

results = [0] * 256
i = 0L
while i < 2**16:
    # 128bitのランダムな鍵で暗号化し、2文字目の出現頻度をカウントする
    key = os.urandom(128)
    ciphertext = RC4(message, key)
    second_value = ord(ciphertext[1])
    results[second_value] += 1
    i += 1

# トップ5を計算し、推定結果を出力
from collections import Counter
freq_map = dict((chr(i), n) for i, n in enumerate(results))
top5_freq = Counter(freq_map).most_common(5)

print "message: %r" % message
print "top 5 frequencies: %r" % top5_freq
print "estimated 2nd character: %r" % top5_freq[0][0]

実行すると、次のように推定に成功していることが確認できる。

$ python rc4_2.py
message: 'this_is_a_message'
top 5 frequencies: [('h', 514), ('/', 294), ('\xa7', 293), ('\x1f', 288), ('-', 288)]
estimated 2nd character: 'h'

2文字目以外にも出現頻度の偏りがあるため、同一のメッセージが大量の異なる鍵で暗号化されたものが得られれば、同様の方法で元のメッセージが復元されうる。 USENIX Security 2013の発表では観測数の増加にともない推定の成功率が大きくなる様子が示され、他の工夫と組み合わせることにより2^33～2^34回の観測でHTTP Cookieが盗聴できるレベルになるとされている。

参考リンク