ScytheCTF 2017 Writeup

Harekaze で ScytheCTF 2017 に参加しました。（1チーム3人までだったので、@hiwwさん、@st98_さんと一緒に出ました） チームは425ptを獲得して7位、私はそのうち200ptを獲得しました。

[Crypto 150] rsa-love

渡されたzipファイルの中身は以下のようになっています。

Archive:  crypto.zip
  Length     Date   Time    Name
 --------    ----   ----    ----
        0  03-08-17 22:59   crypto/
      512  03-08-17 17:58   crypto/ciphertext1
      512  03-08-17 17:58   crypto/ciphertext2
      895  03-08-17 22:57   crypto/makefile.pyc
      795  03-08-17 17:58   crypto/pubkey
 --------                   -------
     2714                   5 files

makefile.pyc を uncompyle2 でデコンパイルすると、以下のようになっています。

#Embedded file name: ./makefile.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
flag = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'
e = 17L
p = getPrime(2048)
q = getPrime(2048)
n = p * q
m = int(flag.encode('hex'), 16)
c1 = pow(m + 525689, e, n)
f = open('ciphertext1', 'w')
f.write(hex(c1)[2:-1].decode('hex'))
f.close()
c2 = pow(m + 614039, e, n)
f = open('ciphertext2', 'w')
f.write(hex(c2)[2:-1].decode('hex'))
f.close()
rsa = RSA.construct((n, e))
f = open('pubkey', 'w')
f.write(rsa.publickey().exportKey())
f.close()

少し調べると、Franklin-Reiter related message attackという攻撃手法が使えそうだということがわかりました。以下は参考にさせて頂いた記事です。

• 公開鍵暗号 - RSA - 基礎 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
• SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー

最終的には、下のようにsageスクリプトを書くとフラグが出てきました。

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    n = 861989937789654426343461243692067541646389136311279472446273771380858591625799045480051880016167718577658753128114583588383932472239887532172654339870957744753326309084673348480208200721928375516193389541702362452779965541554418677435608451699395256247138474396834520098936161405270620432424672291929888064130422062921966409668948497829705768760525774247650535053422643580738401556942324260544893782468891562816590270831614624237877973003686291610265574551629414163200950228047285602529516064690646175978064578814463967642861445483802710181935820557001553628723227309919458243310054535987861396335937057322519432286790724315958028243706586026951293434287385440723446396785106065925954282107811068208807162110744413874784050820334181968892572151375893316164421299682073611671735120835384408284028006058512208895055633703444944571240009593754857230895392515268894872261726043200570474182492569784574170294738999962439991665188355923101471407683779419743815417334789620414324520353716086440275136258345544515245749214223565224488530498725011173014355937540112656062646800663153687788062813622722398138482615418491235933205129196807880212257539452423260828545503342523786106829637208140030098553391575548646889945502359545728826142377267
    e = 17

    with open("ciphertext1", "r") as f:
        c1 = int(f.read().encode('hex'), 16)
    with open("ciphertext2", "r") as f:
        c2 = int(f.read().encode('hex'), 16)

    m1 = related_message_attack(c1, c2, 88350, e, n)
    flag = hex(long(m1 - 525689))[2:-1].decode('hex')
    print flag

[Stego 50] quick challenge

ソラちゃん（@st98_）が GitHub - jaybosamiya/busysteg: Hide information content into busy areas of images, optimally を見つけていたものの、ビルドにはOpenCVが必要とのことだったので、調べたら何故か入っていました。（いついれたかわからない…）

しかし、そのままビルドしようとするとオペランドの型が曖昧であるというようなエラーがでてビルドできませんでした…

--- a/busysteg.cpp
+++ b/busysteg.cpp
@@ -193,7 +193,7 @@ void hide_data(char* inimg, char* indata, char* outimg) {
   }
   long int fsize = fin.tellg();
   fin.seekg(0, ios_base::end);
-  fsize = fin.tellg() - fsize;
+  fsize = (long)fin.tellg() - fsize;
   fin.seekg(0, ios_base::beg);
   char *buf = new char[fsize + 16];
   memcpy(buf, "BUSYSTEG", 8);

以上のように変更することで無事ビルドし、flagを取り出すことができました。