公平なランサムウェア

Engilsh version is here.

はじめに

以前から「公平なランサムウェア」を作りたいと思っていた。つまり、ランサムウェアの作者でBitcoinを欲しいアリスと、アリスのランサムウェアに感染してデータを暗号化されたボブがいるとする。ボブはアリスにBitcoinを支払ってデータを復号してもらいたいが、この2人には次のような不正が考えられる。

アリスの不正

ボブがBitcoinを送金したにも関わらず、暗号化を解除する鍵を渡さない

ボブの不正

アリスが暗号化を解除する鍵を送信したにも関わらず、Bitcoinを送金しない

つまり、ボブがBitcoinを送金したら確実に暗号化を解除する鍵を得られるようにしたい。
この文章ではこれらの不正を防ぎつつ取引を公平に行う方法について説明する。この文章を読んで何か分からないことや疑問、改善するべきところを見つけた場合は気軽にコメントなどで教えて欲しい。

暗号技術

紹介するプロトコルで利用する暗号技術について軽く説明する。

RSA暗号

暗号化関数$f$は公開鍵暗号RSAであり、公開鍵$(e, N)$を用いて次のように定義される。

$$
f_e(x) = x^e \bmod{N}
$$

また、秘密鍵$d$を用いて暗号文$y$を復号する関数$f^{-1}$を次のように定義する。

$$
f^{-1}_d(y) = y^d \bmod{N}
$$

RSA暗号は公開鍵から暗号文を復号することはできない。また、仮に平文と暗号文と公開鍵の組を持っていたとしても、それらから秘密鍵を推測することはできない。

ハッシュ関数

アリスとボブの2人の間にはハッシュ関数$H$が共有されているものとする。ただし、このハッシュ関数はBitcoinのスクリプトで実行できるSHA256またはRIPEMD160でなければならない。

対称鍵暗号

アリスとボブの2人の間には対称鍵暗号$H^{prg}$が共有されているものとする。この関数は対称鍵$k$を用いてデータ$x$を暗号化して暗号文$y$を得る場合、次のように表記する。

$$
y := H^{prg}_k(x)
$$

また、復号関数を$H^{-prg}$とすると、次が成り立つ。

  x = H^{-prg}_k(H^{prg}_k(x))

この関数はたとえばChaCha20などを利用すればよい。

ゼロ知識証明

今回のプロトコルでは次のようなことを証明できるゼロ知識証明を利用する。

• 公開鍵$(e, N)$で暗号化されたデータ$c := f_e(t)$において、ハッシュ値$H(k)$の原像$k$が$s := H^{prg}_k(f^{-1}_d(c))$を復号できる対象鍵$k$と等しい

ただし、これの実行中にアリスの秘密鍵$d$や対称鍵$k$、元の平文$t$が検証者に知られることはないものとする。つまり、アリスがボブとこのゼロ知識証明を利用したとしても、ボブは秘密鍵$d$と対称鍵$k$が何であるかを知ることはできないし、かつ平文$t_1, \dots, t_m$のいずれも突き止めることができない。
これの実装方法についてはRSA暗号を利用した方法があり、具体的な実装については後述する。

Bitcoin

BitcoinのトランザクションにはscriptSigとscriptPubKeyというスタックマシーン用のスクリプトが格納されており、これらを実行した結果が$\text{true}$かどうかによって取引が有効かどうかを判断している。たとえば次のような例で説明する。

1. AがBへ1 BTCを送信された（Tx.1）
2. BがCへ1 BTCを送信する（Tx.2）

このとき、まず（Tx.2）のscriptSigを実行し、次に（Tx.1）のscriptPubKeyを実行する。この結果が$\text{true}$であれば、Bitcoinのブロックチェーンに受理されるということになる。つまり、ブロックチェーンにあるなんらかのscriptPubKeyに対して、スタックマシーンを動作させた結果が$\text{true}$になるようなscriptSigを作ることができれば、誰へでも送金することができる。

前提条件

まず、ボブのデータ$t_1, t_2, \dots, t_m$があり、アリスの公開鍵$(e, N)$を利用した関数$f$で暗号化され、ボブの手元には$c_1, c_2, \dots, c_m; (c_i := f_e(t_i))$がある。
また、アリスは次のように考えている必要がある。

• 暗号化されたボブのデータ$c_1, \dots, c_m$のうち、ボブの希望するデータを少なくとも1つを無償で復号してもよい

なぜこのような条件が必要であるかというと、アリスはボブのコンピュータ上でランサムウェアのような任意のプログラムを実行できる状態にあった。この文章で説明するプロトコルを利用することで、ボブは手元の暗号文をBitcoinの送金を対価に復号できる。ただし、ボブは今手元にある暗号文が自分のコンピュータに元々あったデータを暗号化した結果なのか、それともアリスが乱数などで作成したデータを暗号化したものなのかを判断することができない。そこでアリスは少なくとも1つのデータを無償で復号し、それをボブに確認させてボブの手元にある暗号文がボブの元々持っていたデータを暗号化したものであることを証明する必要がある。この条件から、同時に次のような条件も導かれる。

• ボブは所持していたデータ$t_1, \dots, t_m$のうち少なくとも1つのデータを識別できる

ボブのコンピュータには大量のファイルが存在するので、そのうち少なくとも1つの内容が正しいかどうかを識別できるというのはそれほど非現実的な条件ではない。

プロトコル

アリスは$c_1, \dots, c_m$を復号する条件として$x$ BTCを要求しているものとする。また、アリスのBitcoinアドレスを$\mathcal{A}$として、ボブのBitcoinアドレスを$\mathcal{B}$とする。そして、ランサムウェアがボブのデータを暗号化する際に利用した公開鍵$(e, N)$をボブは知っているものとする。
このプロトコルはPhase 1、Phase 2、Phase 3から構成されており、この順番で実行する。いずれかのPhaseが失敗した場合、取引は直ちに中止となる。

Phase 1

このPhaseではボブの指定した暗号文$c_i$をアリスが正しく復号できることを確認する。

1. ボブは乱数$r$を生成し、内容が正しいことを識別できる平文$t_i$に対応する暗号文$c_i$を選び、$s := c_ir^e \bmod N$を計算しアリスへ送信する
2. アリスは秘密鍵$d$を用いて$\bar{s} := f^{-1}_d(s)$を計算しボブへ送信する
   • $\bar{s} = f^{-1}_d(s) = s^d = (c_ir^e)^d = c^{d}_i r = t_i r \pmod{N}$
3. ボブは$t_i = \bar{s}, /, r \bmod{N}$を検証する
   • 検証に失敗した場合、取引は中止となる

ここで、ボブはまず暗号文を乱数$r$でブラインドしてどのような暗号文を復号しようとしているのかを隠している。つまりアリスはボブがどの暗号文を復号したのかは分からない。このようにすることで、アリスが適当な平文$t_i$をボブのコンピュータからあらかじめコピーしておいて、ボブが送信した暗号文に関わらず$t_i$を返信するという不正を防止している。

Phase 2

このPhaseでは暗号文が全て同じ秘密鍵で復号できることのゼロ知識証明を行う。

1. ボブは$n$個の乱数$r_1, r_2, \dots, r_n$を作成し、$\sigma_i := r_i^e$を計算する
2. ボブは$m$個の乱数$\rho_1, \rho_2, \dots, \rho_m$を作成し、$\delta_i := c_i\rho_i^e$を計算する
3. ボブは$\{\sigma_1, \dots, \sigma_n, \delta_1, \dots, \delta_m\}$をランダムに並べ換えた列を$\beta := \{\beta_1, \dots, \beta_{n+m}\}$として、これをアリスへ送信する

• ただし、$\beta$のうち$\sigma_i$を$F$とし、また$\beta$のうち$\delta_i$を$R$とする

1. アリスは$i := 1, \dots, n + m$について次を計算する

• 乱数$k_i$を作成し、$s_i := H^{prg}_{k_i}(f^{-1}_d(\beta_i))$
• ハッシュ値$h_i := H(k_i)$

1. アリスは$s_1, \dots, s_{n+m}$と$h_1, \dots, h_{n+m}$をボブへ送信する
2. ボブは$r_1, r_2, \dots, r_n$と$F$をアリスへ送信する
3. アリスは全ての$i \in F$について$\beta_i = r_i^e$を検証する

• 失敗した場合、ボブが不正をしたとみなして取引を中止する

1. アリスは全ての$i \in F$について$k_i$をボブへ送信する
2. ボブは全ての$i \in F$について、$h_i = H(k_i)$かつ$r_i = H^{-prg}_{k_i}(s_i)$となることを確認する

• 失敗した場合、取引を中止する

今ボブはアリスが$c_i$を復号できるかどうかを知りたいが、アリスは無料で復号するつもりはない。そこで（1）において、まずボブはFake Valuesというダミーの値を作り、それと（2）で作成した本物の値を（3）で混ぜてシャッフルしている。そしてこの$n + m$個のデータをアリスに送信し、アリスがダミーデータ$n$個を正しく復号できたとする。確かにアリスにはその$n$個だけを上手く復号して、残り$m$個の本物のデータは全く関係のない対称鍵で暗号化されている可能性もある。しかし、アリスの不正が成功する場合というのは$n + m$個のデータの中から$n$個のデータを選んだ組み合せの中の1通りしかないため、不正が成功する確率は次のようになる。

$$
\frac{1}{{}_{n + m} \mathrm{C} _n}
$$

よって、$n$や$m$が十分に大きければアリスの不正が成功する確率は極めて少ないと言える。
また、ボブがFake Valuesであると偽って暗号文$c_i$をアリスに送信した場合、Bitcoinを支払うことなく復号できてしまう。これを避けるために（7）でアリスはボブの送信したFake Valuesを検証してからFake Valuesの対称鍵$k_i$を公開している。

Phase 3

このPhaseではボブからアリスへの送金と秘密鍵の公開を同時に行う。

1. $i \in R$として、ボブは$x$ BTCを送金する次のようなscriptPubKeyを持つトランザクション（Tx.1）をブロックチェーンに送信する¹

\begin{array}{l}
\texttt{OP_SHA256} \
h_1 \
\texttt{OP_EQUAL} \
\texttt{OP_IF} \
;;; \texttt{OP_SHA256} \
;;; h_2 \
;;; \texttt{OP_EQUALVERIFY} \
;;; \vdots \
;;; \texttt{OP_SHA256} \
;;; h_m \
;;; \texttt{OP_EQUALVERIFY} \
;;; \mathcal{A} \
\texttt{OP_ELSE} \
;;; \text{block height}, + 100\
;;; \texttt{OP_CHECKLOCKTIMEVERIFY} \
;;; \texttt{OP_DROP} \
;;; \mathcal{B} \
\texttt{OP_ENDIF} \
\texttt{OP_CHECKSIG}
\end{array}
```

• このスクリプトの詳細は後述する

1. アリスは（Tx.1）について次を確認する

• 送金額が$x$ BTCであること
• $h_1, \dots, h_m$はアリスが送信したハッシュ値であること
• $\mathcal{A}$がアリスのBitcoinアドレスであること
• 確認に失敗した場合、取引を中止する

1. アリスはscriptSigに$k_i; (i \in R)$を入れたトランザクション（Tx.2）をブロックチェーンに送信する
2. アリスのトランザクションが受理された場合、次の2つが同時に発生する（ただし$i \in R$）

• ボブはブロックチェーンに記載された$k_i$を利用して$t_i := H^{-prg}_{k_i}(s_i)$を得る
• アリスはトランザクションが受理され、$x$ BTCを得る

（1）のスクリプトについて説明する。アリスが（Tx.2）において、scriptSigに対称鍵$k_1, \dots, k_m$を入れたとすると、まず$k_1$がスタックに入り、それ対して（Tx.1）のscriptPubKeyの先頭の$\texttt{OP_SHA256}$が実行され、結果のハッシュ値がスタックに入る。そして$h_1$をスタックにのせるので、スタックの状態は次のようになる。

\def\AtSOne#1\csod{%
	\begin{array}{c|}
		\hline
		#1\\
		\hline
	\end{array}
}%
\def\AtSTwo#1,#2\csod{%
	\begin{array}{c|c|}
		\hline
		#1 & #2\\
		\hline
	\end{array}
}%
\def\SOne#1{\AtSOne#1\csod}
\def\STwo#1{\AtSTwo#1\csod}
\def\AtSThree#1,#2,#3\csod{%
	\begin{array}{c|c|c|}
		\hline
		#1 & #2 & #3\\
		\hline
	\end{array}
}%
\def\AtSFour#1,#2,#3,#4\csod{%
	\begin{array}{c|c|c|c|}
		\hline
		#1 & #2 & #3 & #4\\
		\hline
	\end{array}
}%
\def\AtSFive#1,#2,#3,#4,#5\csod{%
	\begin{array}{c|c|c|c|c|}
		\hline
		#1 & #2 & #3 & #4 & #5\\
		\hline
	\end{array}
}%
\def\SOne#1{\AtSOne#1\csod}
\def\STwo#1{\AtSTwo#1\csod}
\def\SThree#1{\AtSThree#1\csod}
\def\SFour#1{\AtSFour#1\csod}
\def\SFive#1{\AtSFive#1\csod}
\def\dosc#1#2\csod{{\rm #1{\scriptsize #2}}}
\SFive{h_1, H(k_1), k_2, \cdots, k_m}

そして$\texttt{OP_EQUALVERIFY}$でこれらを比較し、等しい場合は先頭が$\text{true}$となり、次の対称鍵$k_2$について同様にハッシュ値を計算し$h_2$と比較する。もし$h_1, \dots h_m$のいずれかでハッシュ値の比較に失敗した場合は、$\texttt{OP_EQUALVERIFY}$によって直ちにスクリプトが失敗する。全てのハッシュ値の比較に成功した場合、アリスのBitcoinアドレス$\mathcal{A}$で署名の検証$\texttt{OP_CHECKSIG}$が実行される。またそうでない場合は$\texttt{OP_CHECKLOCKTIMEVERIFY}$によって、現在のブロックチェーンの長さから100以上伸びた後はボブが$x$ BTCを取り出せるようになっている。これはアリスが（1）の後に姿を消した場合にボブが$x$ BTCを回収できなくなることを防ぐためである。

まとめ

このようにすることで、公平なランサムウェアを作成できると考えられる。最初に公開したバージョンでは、確かにアリスから何らかの暗号文の秘密鍵をBitcoinで買うことはできるが、暗号文を復号した結果がボブの元々所持していたデータなのか、それともアリスが作成した乱数なのかの区別ができなかった。そこでアリスは、少なくとも1つのデータを無償で復号することにより、ボブの手元にある暗号文がボブの求めるデータを暗号化したものであることを証明することとした。この部分を何らかのゼロ知識証明で実行できれば、よりよいプロトコルになると考えられる。

参考文献

• The first successful Zero-Knowledge Contingent Payment
• TumbleBit: An Untrusted Bitcoin-Compatible Anonymous Payment Hub
• ビットコインにおけるトランザクション、その展性と影響
• Script (Bitcoin Wiki)
• Bitcoinを技術的に理解する

1. このスクリプトはハッシュ関数$H$をSHA256とした場合のものである。 ↩