SECCON 2020 Online CTF Writeup(Catch up) Part1

#1 はじめに
2020/10/17 15:00(JST)~2020/10/18 15:00(JST)で開催されたSECCON 2020 Online CTFにTeam N30Z30Nは…諸事情により参加できませんでした。
しかしながら今回のSECCONは「難化したけど良問ばかり」という噂、キャッチアップしない手はないと思った次第です。
さしあたり、現状のN30Z30Nで一番の得点源となっているCryptoを強化するのが良かろう、という事情から、Cryotoのwarmup問題のうちの1問から着手しようと思います。

#2 Writeup(Catch up)
##2-1 This is RSA(Crypto, Warmup)
###問題文
>　As you may know.

###添付ファイル（this_is_rsa.c84016880d55d4486506826e79e8fe87.tar.gz, 解凍後）
```rsa.rb
require 'openssl'

def get_prime
  i = OpenSSL::BN.rand(512).to_s.unpack1('H*').hex
  OpenSSL::BN.new(i).prime? ? i : get_prime
end

p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)

puts "N = #{n}"
puts "c = #{c}"
```

```output.txt
N = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528
```

###解法の検討
「warmup」を称する問題ですが、CTFで「baby」や「warmup」という言葉に何度騙されたことか…
それはさておき、まずは問題を見てみましょう。
「rsa.rb」の内容が示す通りPlainなRSAで、modulus N、exponent e、ciphertext cが与えられており、eは一般的な値である65537です（小さかったり大きかったりすればそこが攻略の糸口になり得るが、今回はそういったことはない）。そして、MsieveやFactorDBでもNを分解してくれません（SECCONはそう甘くはありません。まぁ、そりゃそうでしょうけど）。あと、不審な点があるとすれば素数の生成法ですので、そこを精査することにします。

###素数生成ロジックの精査
rubyに慣れていない場合は特にそうですが、提供されたコードを一見すると「512ビットの乱数をとり、素数ならそれを返す」ようにも読めてしまいます。しかし、実際調べてみる（コードの意味を紐解く or 実際に動かしてみる）と、「512bitの整数を10進法で表す文字列をバイト列と見なし、それを整数にしたものが素数ならばそれを返す」という動きをしていることがわかります。pythonで雑に書きなおすとこんな感じです（OpenSSLの部分はrandomで置き換え）。

```test1.py
from Crypto.Util.number import *
import random
def get_prime():
  s = bytes_to_long(str(random.randint(2**511, 2**512-1)).encode())
  if isPrime(p):
    return p
  else:
    return get_prime()
```
そして、このロジックで生成される素数を16進で見てみると

```
0x3133343938303535353333323637373934333630333231333732353431383931323138303932323832313838323037393334363036313938383831313837393339323233383032333238323132303934383336373537373035333335313434383934343734363832393939383733353039373830333737323132363435343835353834333838353433363137313136393834303033363631333931
```
という具合に、「30」～「39」の羅列となっているわけです。

###作戦立案
p、qは「特殊な形」をしていることが判りました。そしてこれらは、2バイトずつ区切るとすべて「30～39」の10通りしかないことから、下から順に2バイト、4バイト、6バイト、と2バイトずつbruteforceで増やして掛け算して、nを16進法で表した時の値と辻褄が合うようにすればp、qを構成できそうな感じがしてきます。

###とにかくやってみる！
上の方針に沿って、雑にsolverを書いてみました。

```solve1.py
from Crypto.Util.number import *
import itertools

n = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528
e = 65537

N = hex(n)

p = 0
q = 0
pos = 0
while(1):
  for i, j  in itertools.product(range(0x30, 0x40), repeat = 2):
    _p = p + (i << (8 * pos))
    _q = q + (j << (8 * pos))
    if(hex(_p * _q)[-2 * (pos + 1):] == N[-2 * (pos + 1):]):
      p = _p
      q = _q
      pos = pos + 1
      break    
  if(p * q == n):
    break
  elif(p * q > n):
    print("oops!")
    break

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)).decode())
```

果たして、これを実行すると以下のフラグを得ます。
> **SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?}**

###ん？これでいいのか？
上のsolverは極めて雑なものです。なぜなら、「p、qの構成途中の候補が複数存在し、かつ最初の候補で失敗すること」をまったく想定していません。実際、p、qを変えたとき上のsolverではフラグを得られない場合が発生します。この欠点を修正し、ちゃんと実装した（はずの）solverが以下のものとなります。
※@kusano_kさんのWriteup
https://qiita.com/kusano_k/items/0ec2a09483eaa7b900d1
を参考にさせていただきました。

```solve2.py
from Crypto.Util.number import *
import itertools

n = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528
e = 65537

def fact(cp, cq, pos):
  global p, q
  if(cp * cq > n):
    return False
  if pos != 0:
    if n % cp == 0:
      p = cp
      q = n // p
      return True
    elif n % cq == 0:
      q = cq
      p = n // q
      return True
  for i, j  in itertools.product(range(0x30, 0x40), repeat = 2):
    _cp = cp + (i << (8 * pos))
    _cq = cq + (j << (8 * pos))
    if(hex(_cp * _cq)[-2 * (pos + 1):] == N[-2 * (pos + 1):]):
      if fact(_cp, _cq, pos + 1):
        return True
  return False

N = hex(n)
fact(0, 0, 0)

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)).decode())
```

###いろいろ思ったこと
solve2.pyはp、qの値によらずちゃんとフラグを出してくれます（くれるはずです）が、solve1.pyは「都合の良い」p、qでなければ失敗します。したがって、solve2.pyはsolve1.pyより優っているという見方ができます。
しかし、限られた（短い）時間の中で、「質の高いsolverを書くこと」ではなく「フラグを通すこと」を目的とする競技においては、solve1.pyによる解答は、少なくとも全否定するようなものではないと考えます。
（これはあくまで推測ですが、warmup枠ということで、作問レビュー中に雑なソルバーでも解けるようp、qの値が調整されたのかもしれません。）
結局のところ、「一発でクリティカルなsolverを実装できれば良いが、テキトーなsolverから入って修正を重ねていくのもアリじゃね？」「完全なsolverが欲しければ、それは競技の後の検討（復習）でやればよい」「正答したものであっても、競技後に復習する意味はある」というのがこのcatch upで得た答えであります。

＜つづく＞