「plain RSAに対する攻撃手法を実装してみる」では、平文をそのまま暗号化した場合のRSA（plain RSA）に対するいくつかの攻撃手法を実装した。 他にも、plain RSAについては適応的選択暗号文攻撃（CCA2）に対して安全でないことが知られている。 ここでは、plain RSAに対する適応的選択暗号文攻撃が可能であることを確認した上で、現在用いられているパディング方式についてまとめてみる。
環境
Ubuntu 14.04.3 LTS 64bit版
$ uname -a Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 14.04.3 LTS Release: 14.04 Codename: trusty
適応的選択暗号文攻撃
選択暗号文攻撃（CCA; Chosen-ciphertext Attack）は、任意に選択した暗号文に対する平文が得られる（復号できる）状況で、これを利用してある暗号文に対する平文を求める攻撃を指す。 ただし、目的とする暗号文自体を復号することはできないものとする。 選択暗号文攻撃はさらに、目的とする暗号文を得た上で暗号文を選択できる適応的選択暗号文攻撃（CCA2）と、そうでないもの（CCA1）に分けられる。 CCA2のほうが攻撃に用いる情報が多いため、より強い攻撃であるといえる。
暗号においては、他の暗号文の復号結果からある暗号文に対応する平文に関する情報が推測できないことが望ましい。 このような性質は識別不可能性（Indistinguishability; IND）と呼ばれ、CCA2のもとでも識別できないことを指してIND-CCA2と表す。
平文をそのまま暗号化した場合のRSA（plain RSA）は、CCA2に対して安全でない。 具体的には、平文mと対応する暗号文cに対し、適当な整数rのもとでre cに対応する平文がr mになることから、これをrで割ることでmを求めることができる。 これをコードで確認してみると次のようになる。
# plain.py
import sys
import os
import gmpy
def encrypt(m, e, n):
return pow(m, e, n)
def decrypt(c, d, n):
return pow(c, d, n)
n = 0x00a6ef4f3e5aa17855c988a66ce4521cc0221f302cddaf8b10ecd348f27464b465dd7e69983b2cced881bea51b4c6a41a32bc45b2693f89879910c9d332b38ef0ab26c74bff9fa44d6bed1401b8848af669daf4fc4c71902e38b7fd8d0abd364eb4a5f666e818eb342780ab9f177559bd62c0ce9e246b62ac6d982271cbd98e0e8d6c0aab810d3485a156a86193395006527a7d816d07e0fee11d5ea4cf00437ad27fec8dd9023d0133020106162d4d82471a26d5d29888f0221b64cda932dfa1e20c0970cf673b6aff466d583f7c2a48d0785e6334f89f1605e770b10740c13f9c58c010cda4db2c2a216f791aa0196291d832f75fcfc74d55e36980b81f70ca9
e = 65537
d = 0x00904ba15acbaa7142ee2e8174f4b3098906b5a0c5d765eab6598f94a986f4997ec7c38271050d894a5a7439716c4f18a77ba88205c9b803cc6915d73828af50e9152b6c8b98ffbccb472bc6d745a9567c43e70af39409c99678b9ace74aef3277b3d4dcccbe8e63e31bb261e217fdd6f37d263870d0209cbf3fba2226d4b836078790e970daf98a2fe23eddcb25089483452f66c9bf6122f5000065b20213d9b268e7dee1aba400cd1a526aa838c53fa2eaec4a40624a651ce0b975c5500f950370aaa48ccfb14151678f0f8b7744fec2bceb9015f5a16dc7ce13d77e3058f7cc3a3778f629e2d9ba121d87bb1c87b3dde88e07bc679cb699bdc39d806b82f281
m = long(sys.argv[1])
print m
c = encrypt(m, e, n)
print decrypt(c, d, n)
r = 2
cr = (c * pow(r, e, n)) % n
mr = decrypt(cr, d, n)
mprime = (mr * gmpy.invert(r, n)) % n
print mprime
$ python plain.py 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890
上の結果から、直接暗号文を復号しなくても、他の暗号文に対応する平文から求めたい平文が計算できていることがわかる。
RSAを暗号化に用いる際は、平文に適当なパディングをつけた上で暗号化し、復号時にパディングを取り除くようにすることが一般的である。 RSAにおけるパディング方式はPKCS #1で定められており、RFC 3447としても発行されている。 PKCS #1では、PKCS #1 v1.5とOAEPの二つのパディング方式が定義されている。
PKCS #1 v1.5
PKCS #1 v1.5は、RSAにおいて最も広く用いられているパディング方式である。 PKCS #1 v1.5では、平文Mを次のようにパディングする。
EM = 0x00 || 0x02 || PS || 0x00 || M PS: pseudo-randomly generated nonzero octets
実際にコードで表すと次のようになる。
# pkcs1.py
import sys
import os
import gmpy
def num2str(n, k=None):
s = ''
while n:
s += chr(n & 0xff)
n >>= 8
s = s[::-1]
if k:
s = '\x00' * (k-len(s)) + s
return s
def str2num(s):
n = 0
for c in s:
n <<= 8
n += ord(c)
return n
def pad_pkcs1(m, n):
ns = num2str(n)
ms = num2str(m)
if len(ms) > len(ns) - 11:
raise Exception("message too long")
ps = os.urandom(len(ns) - len(ms) - 3)
while '\x00' in ps:
ps = os.urandom(len(ns) - len(ms) - 3)
return str2num('\x00\x02' + ps + '\x00' + ms)
def strip_pkcs1(m, n):
ns = num2str(n)
ms = num2str(m, len(ns))
if not ms.startswith('\x00\x02'):
raise Exception("decryption error")
padend = ms.index('\x00', 2)
return str2num(ms[padend+1:])
def encrypt_pkcs1(m, e, n):
print "[+] plain: %0512x" % m
m = pad_pkcs1(m, n)
print "[+] padded: %0512x" % m
return pow(m, e, n)
def decrypt_pkcs1(c, d, n):
m = pow(c, d, n)
print "[+] decrypted: %0512x" % m
return strip_pkcs1(m, n)
n = 0x00a6ef4f3e5aa17855c988a66ce4521cc0221f302cddaf8b10ecd348f27464b465dd7e69983b2cced881bea51b4c6a41a32bc45b2693f89879910c9d332b38ef0ab26c74bff9fa44d6bed1401b8848af669daf4fc4c71902e38b7fd8d0abd364eb4a5f666e818eb342780ab9f177559bd62c0ce9e246b62ac6d982271cbd98e0e8d6c0aab810d3485a156a86193395006527a7d816d07e0fee11d5ea4cf00437ad27fec8dd9023d0133020106162d4d82471a26d5d29888f0221b64cda932dfa1e20c0970cf673b6aff466d583f7c2a48d0785e6334f89f1605e770b10740c13f9c58c010cda4db2c2a216f791aa0196291d832f75fcfc74d55e36980b81f70ca9
e = 65537
d = 0x00904ba15acbaa7142ee2e8174f4b3098906b5a0c5d765eab6598f94a986f4997ec7c38271050d894a5a7439716c4f18a77ba88205c9b803cc6915d73828af50e9152b6c8b98ffbccb472bc6d745a9567c43e70af39409c99678b9ace74aef3277b3d4dcccbe8e63e31bb261e217fdd6f37d263870d0209cbf3fba2226d4b836078790e970daf98a2fe23eddcb25089483452f66c9bf6122f5000065b20213d9b268e7dee1aba400cd1a526aa838c53fa2eaec4a40624a651ce0b975c5500f950370aaa48ccfb14151678f0f8b7744fec2bceb9015f5a16dc7ce13d77e3058f7cc3a3778f629e2d9ba121d87bb1c87b3dde88e07bc679cb699bdc39d806b82f281
m = long(sys.argv[1])
print m
c = encrypt_pkcs1(m, e, n)
print decrypt_pkcs1(c, d, n)
r = 2
cr = (c * pow(r, e, n)) % n
mr = decrypt_pkcs1(cr, d, n)
mprime = (mr * gmpy.invert(r, n)) % n
print mprime
$ python pkcs1.py 1234567890123456789012345678901234567890
1234567890123456789012345678901234567890
[+] plain: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003a0c92075c0dbf3b8acbc5f96ce3f0ad2
[+] padded: 00025a810ec67dfcfa79d4b2b7a8caf68ca56d67641c9295d6a7890c8c6b0f976c1ebbe911cc69b73146d056ed2317cf853d2dc1443f20aafc1a35288a9fc4f4b098fe0bed56a287bb94afed24c57367436b4c972874e11fedbcfe5d76688de21591fb534fe23ce5ac215159162497abee978442a3cb812f68edab3bf16984c9c684cc644a81d024c997d8ad5dc32b0939381ccaf9b727caea706ae98edc4b1fa26a450a1876c42e84b12a988574859ed5ab46af8ee87e44d6cbe81301deb8a08ef4544e7428d7891446aa3e5fcf2755f912e61d26ee9c6b3fea105763fc9bd7ecd1e537147772cf94ceab9635de0003a0c92075c0dbf3b8acbc5f96ce3f0ad2
[+] decrypted: 00025a810ec67dfcfa79d4b2b7a8caf68ca56d67641c9295d6a7890c8c6b0f976c1ebbe911cc69b73146d056ed2317cf853d2dc1443f20aafc1a35288a9fc4f4b098fe0bed56a287bb94afed24c57367436b4c972874e11fedbcfe5d76688de21591fb534fe23ce5ac215159162497abee978442a3cb812f68edab3bf16984c9c684cc644a81d024c997d8ad5dc32b0939381ccaf9b727caea706ae98edc4b1fa26a450a1876c42e84b12a988574859ed5ab46af8ee87e44d6cbe81301deb8a08ef4544e7428d7891446aa3e5fcf2755f912e61d26ee9c6b3fea105763fc9bd7ecd1e537147772cf94ceab9635de0003a0c92075c0dbf3b8acbc5f96ce3f0ad2
1234567890123456789012345678901234567890
[+] decrypted: 0004b5021d8cfbf9f4f3a9656f5195ed194adacec839252bad4f121918d61f2ed83d77d22398d36e628da0adda462f9f0a7a5b82887e4155f8346a51153f89e96131fc17daad450f77295fda498ae6ce86d6992e50e9c23fdb79fcbaecd11bc42b23f6a69fc479cb5842a2b22c492f57dd2f08854797025ed1db5677e2d309938d0998c89503a049932fb15abb86561272703995f36e4f95d4e0d5d31db8963f44d48a1430ed885d096255310ae90b3dab568d5f1dd0fc89ad97d02603bd71411de8a89ce851af12288d547cbf9e4eabf225cc3a4ddd38d67fd420aec7f937afd9a3ca6e28eee59f299d572c6bbc0007419240eb81b7e7715978bf2d9c7e15a4
Traceback (most recent call last):
File "pkcs1.py", line 64, in <module>
mr = decrypt_pkcs1(cr, d, n)
File "pkcs1.py", line 50, in decrypt_pkcs1
return strip_pkcs1(m, n)
File "pkcs1.py", line 37, in strip_pkcs1
raise Exception("decryption error")
Exception: decryption error
上の結果から、暗号化したものが正しく復号できていること、また、r=2としたときの選択暗号文に対して復号エラーとなっていることがわかる。 しかし、PKCS #1 v1.5は1024bitの平文に対して100万程度の選択暗号文を取ることで攻撃可能なことが知られており、IND-CCA2ではない。
なお、OpenSSLのrsautlコマンドでは、パディング方式としてPKCS #1 v1.5がデフォルトとなっている。
OAEP
もうひとつのパディング方式であるOAEP（Optimal Asymmetric Encryption Padding）は、RSAと組み合わせたときIND-CCA2であることが証明されている。 OAEPでは、平文Mを次のような仕組みでパディングする。
+----------+---------+-------+
DB = | lHash | PS | M |
+----------+---------+-------+
|
+----------+ V
| seed |--> MGF ---> xor
+----------+ |
| |
+--+ V |
|00| xor <----- MGF <-----|
+--+ | |
| | |
V V V
+--+----------+----------------------------+
EM = |00|maskedSeed| maskedDB |
+--+----------+----------------------------+
PS: zero octets
MGF: mask generation function (with hash function)
復号の際は、maskedSeed ^ MGF(maskedDB) = seedを計算した後、MGF(seed) ^ maskedDBを計算することでMを得る。
RSAにおけるパディング方式としては、PKCS #1 v1.5よりもOAEPを用いるほうがより安全である。
