高専セキュリティコンテスト2017:Crypto:400ptのwriteup

高専セキュリティコンテスト2017の僕のwriteupはここをみて
http://hmkyu.blogspot.jp/2017/10/2017writeup.html

Homomorphic Encryption [Crypto / 400pt]

Problem

In the server, addition with encrypted flag and your encrypted message is computed. Following cryptosystem has additive homomorphism.

Link: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.2657&rep=rep1&type=pdf

nc server_adress port

[Netcat]

nc score.kosensc2017.tech 40053

解説

Homomorphic Encryptionとは、日本語で準同型暗号とも呼ばれ、平文を暗号化した状態でも演算を行える性質を持っています。私は、情報数学をやってたこともありませんし、代数学も適当にしか聞いていなかったので詳しく説明出来ませんので、詳しくはwikiでも見てください。

さて、今回の問題はその準同型性を利用した問題だそうで、ncで問題サーバに接続すると、以下のようなメッセージが表示されます。

Plz input encrypted message and public key!
C,n,g,h(in decimal string)

このCやらnやらgやらhというのは、↑のリンクのpdfに書いてあるOkamoto–Uchiyama cryptosystemという暗号方式に準拠しています。細かい説明は省きます(英文を読んでくれ)

Cは暗号化した平文
nは公開鍵n
gは公開鍵g
hは公開鍵h

で、これに対して適切に値を与えると、10進数の数字が帰ってきます。問題文に書いている通り、こちらが暗号化した平文に、サーバ側がflagを足して、こちらに値を返しています。即ち、Enc(m)・Enc(flag)=Enc(m+flag)になってるってことですね。この操作が出来るのはこの暗号方式が準同型性を持っているからだそうです。

やること

1. 鍵を作る
2. 中身がない=0を暗号化する
3. サーバに値を渡す
4. サーバから帰ってきた値を複合する
5. flagが得られる
です。このとき、中身がない文暗号文を渡すのは、flagだけ欲しいからです。(変に"A"とか渡すと、数字から文字列に変える時面倒なので)

ここで競プロの強い人や、ctfのすごい人は論文を読んでコードを書くんでしょうけど、私は3度チャレンジして失敗したので諦めました。

そこで、Githubを漁っていると、
https://github.com/tutzauel/BA/tree/master/SeComLib
というリポジトリが引っかかりました。どうやらオランダのデルフト工科大学というノーベル賞も排出してるすごい学校の学生による、準同型暗号を計算するC++ライブラリみたいです。
(リファレンスはこっち https://mihaitodor.github.io/SeComLib/index.html)

リファレンスのトップページに乗っているinstallガイドに従ってmakeすると、resources/sampleにPaillier暗号での使い方が書いてあって、test/main.cppに搭載してる暗号化方式のそれぞれの動作テストが書いてあるので、それを参考にしながらコードを記述しました。makefileはsample見て書き直して。サーバとの通信処理とか全くやらず、copy&pasteで値を貼り付けるので正直クソースですね。(複合出来た時嬉しさのあまり書き直さなかった)

main.cpp

#include <iostream>

//include library headers
#include "core/big_integer.h"
#include "core/okamoto_uchiyama.h"

using namespace SeComLib::Core;
using namespace SeComLib::Utils;

int main () {
    OkamotoUchiyama privateCryptoProvider;
    privateCryptoProvider.GenerateKeys();
    OkamotoUchiyamaPublicKey publicKeyClone;
    // 公開鍵を生成(後ろで秘密鍵も生成している)
    publicKeyClone.G = privateCryptoProvider.GetPublicKey().G;
    publicKeyClone.H = privateCryptoProvider.GetPublicKey().H;
    publicKeyClone.n = privateCryptoProvider.GetPublicKey().n;
    std::cout << "G: " << publicKeyClone.G.ToString(10) <<std::endl;
    std::cout << "H: " << publicKeyClone.H.ToString(10) <<std::endl;
    std::cout << "n: " << publicKeyClone.n.ToString(10) <<std::endl;
    //秘密鍵をコピー
    OkamotoUchiyamaPrivateKey privateKeyClone;
    privateKeyClone.p = privateCryptoProvider.GetPrivateKey().p;
    privateKeyClone.q = privateCryptoProvider.GetPrivateKey().q;
    privateKeyClone.gp = privateCryptoProvider.GetPrivateKey().gp;
    privateKeyClone.t = privateCryptoProvider.GetPrivateKey().t;

    OkamotoUchiyama publicCryptoProvider(publicKeyClone, privateKeyClone);

    BigInteger f(0);
    std::cout << "plain number is " << "0" << std::endl;
    OkamotoUchiyama::Ciphertext encF = publicCryptoProvider.EncryptInteger(f);
    std::cout << "enc(f) : " << encF.data.ToString(10) << std::endl;
    std::string userinputString;
    std::cin >> userinputString; 
    BigInteger userinputInteger(userinputString);
    //新しく空のciphertext作って入れようとしたら怒れたので再利用してる
    encF.data = userinputInteger;
    std::cout << "dec(enc(f)) : " << privateCryptoProvider.DecryptInteger(encF).ToString(10) << std::endl;

    return 0;
}

config.xml

<?xml version="1.0"?>
<config>
	<Core>
		<OkamotoUchiyama>
			<keySize>2047</keySize>
			<sizeT>160</sizeT><!-- The bit size of p's prime factor, t -->
			<!-- The bit size of the message space (if the private key is not available) -->
			<messageSpaceSize>500</messageSpaceSize><!-- Must be less than the bit size of p, which is, roughly, 1/3 of keySize -->
		</OkamotoUchiyama>
		<RandomizerCache>
			<capacity>100</capacity>
		</RandomizerCache>
	</Core>
</config>

実行して、値をcopy&pasteするとflagの10進数が取れるので文字列化しておわり。(python以外普段触ってなかったのでbinasciiで文字列化しました。ｵﾊｽﾞｶｼｰ)
高専セキュリティコンテストの運営の方にサーバ側のソースコードを頂いて試しました。ありがとうございます。下にソースコードを掲載します。

crypto400_py.py

# -*- coding:utf-8 -*-
import sys
import random
import binascii

def okamoto_uchiyama_HomAdd(list):
    c,n,g,h = list

    # flag data
    anshex = binascii.hexlify("SCKOSEN{0k4m0to-Uch1y4ma_Crypt0syst3m_has_h0mom0rph1sm}")
    ansval = int(anshex,16)

    # Homomorphic Additive
    r = random.randint(2,n)
    c1 = pow(g,ansval,n)*pow(h,r,n)%n
    r = random.randint(2,n)
    c2 = (c1 * c * pow(h,r,n))%n

    # return new encrypted
    return c2

if __name__ == '__main__':
    print 'Plz input encrypted message and public key!'
    print 'C,n,g,h(in decimal string)'
    rcvmsg = sys.stdin.readline()
    rcvmsg = rcvmsg.rstrip('\n')
    rcvmsg = rcvmsg.rstrip('\r')
    rcvlist = rcvmsg.split(",")
    if len(rcvlist) != 4:
        print 'plz input valid format c,n,g,h'
        exit()
    rcvlist = map(int,rcvlist)
    sndval = okamoto_uchiyama_HomAdd(rcvlist)
    print str(sndval)
    exit()

この問題を特に当たって、ふるつき君による協力がありました(ライブラリのビルドトラブルとか、サーバ側ソースコードをもらってくるとかでお世話になった)
快く、ソースコードを公開して頂いた運営の皆様ありがとうございます。

追記
気が向いたらpythonバージョンのソルバでも書きます。

kyumina

イベントの度に書きます

高専セキュリティコンテスト2017:Crypto:400ptのwriteup

Homomorphic Encryption [Crypto / 400pt]

Problem

解説

やること