CTFZone 2019 Quals Writeup

…………焦ったぜ…………1問も解けねぇんじゃねぇかってな…………

1.[Crypto]Agents[110]

1.[Crypto]Agents[110]

AES-OFBの問題。ncすると↓を返される。

Choose action:
1) Go to HQ
2) Go to Agent
<any other key>) exit
█

1) Go to HQを選ぶと↓のように、「ignatij158040と名乗り、このメッセージをAgentに届けなさい」とおつかいを頼まれる。名前とメッセージは1) Go to HQを選ぶたびに変わる。

1
You are messenger. Your mission is to deliver message to our agent. Use name "ignatij158040" for communication.
        
Message is securily encrypted with AES-OFB (key and IV already delivered with quantum channel). Just deliver this message: 

axXzivRO7h0vDvW6ZfjIxoeyviwuHWI8+0D5f2Ab7QCEzkD1IvQXno8JKJPZUCzUpif1YWyCsF3TBdiLJY0KK1rtmOCemRVCnAQqsTbcSQg4m3lt2nE4ckyEJeKA3iDsqty+L2ZDTEuv8qerVq3tEks0oq0X2/4r3h+ioqWBz4cNFupy1sb4GpIVQTdApncbGTdnM2XMHqphaFa5LlxBrVyrUORjMRu3ESkJ7EqG0Xx91Tt4wSO9BCQjqA34cW+hfRSI0iYTkI6BNYvuHxQLBNJx7kfHv/AHMTCf32kdMrcCQf2yUR8wAWInHtW1L3bRcU22ingOeP9K2mWlCtMCM2GhuZnNshEJJKBAzRN/1X8ze9+V/I9uR2veeimDI0IpNdyXyi3Dunu11rBZl8ie622lIA8B2M+q4GmvlBmc+z7ZLhfbBGCk7DhCUOH3Vi1FfA==

Choose action:
1) Go to HQ
2) Go to Agent
<any other key>) exit
█

さらに2) Go to Agentを選ぶと、まず名乗れと言われる。

2
Hello, delivery boy! Give me your name
█

さっき付けられた名前を入力すると、次にメッセージを聞かれる。

ignatij158040
Ok, give me message from HQ
█

さらにさっき言われたメッセージを入力すると、

axXzivRO7h0vDvW6ZfjIxoeyviwuHWI8+0D5f2Ab7QCEzkD1IvQXno8JKJPZUCzUpif1YWyCsF3TBdiLJY0KK1rtmOCemRVCnAQqsTbcSQg4m3lt2nE4ckyEJeKA3iDsqty+L2ZDTEuv8qerVq3tEks0oq0X2/4r3h+ioqWBz4cNFupy1sb4GpIVQTdApncbGTdnM2XMHqphaFa5LlxBrVyrUORjMRu3ESkJ7EqG0Xx91Tt4wSO9BCQjqA34cW+hfRSI0iYTkI6BNYvuHxQLBNJx7kfHv/AHMTCf32kdMrcCQf2yUR8wAWInHtW1L3bRcU22ingOeP9K2mWlCtMCM2GhuZnNshEJJKBAzRN/1X8ze9+V/I9uR2veeimDI0IpNdyXyi3Dunu11rBZl8ie622lIA8B2M+q4GmvlBmc+z7ZLhfbBGCk7DhCUOH3Vi1FfA==
Thank you. HQ posted here that you are untrusted, so i cant give you secret info.

Bye!

と言われ、何も教えてくれないまま追い返される。

また、付けられた名前と違う名前を答えると

tekitou_name
error occuried
I don't know this nick.

You are spy.

と怒られる。名前を真面目に答えても、メッセージが適当に改竄してあると

tekitoumessage==
JSON corrupted
You are spy.

とやっぱり怒られる。ただし、改竄の仕方によっては普通に受け取ってくれる場合もある。

また、同じ名前で2回来ると、(先のメッセージが突き返されていたとしても、)↓のように追い返される。よって、同じ名前で別々のメッセージを2回届けることはできない。

kiprian307353
error occuried
Message from your nick already delivered.

You are spy.

では解答に入る。メッセージはAES-OFBで暗号化されているようなので、まずはAES-OFBについて↓のサイトなどで勉強する。

暗号技術入門04 ブロック暗号のモード〜ブロック暗号をどのように繰り返すのか〜 | SpiriteK Blog

勉強すると、OFBモードは1ビット単位での改竄が可能だと分かる。そこで、メッセージ中の1バイトだけを改竄してAgentに渡し、受け取ってくれるか怒られるかをチェックすることで、どのバイトが何の役割を果たしているかのヒントを得ることができる。

1バイト目から順に改竄していくと、前から12バイト目の下3ビットを改竄したときに、↓のように初めて見る反応が返ってくる。

dJ3k1NEsiw75NFol+RqpwpV9X34RwOC/jpqTpeirzwM/GZz61J7DdrXUUvF7mRduw6x91DXmIs6HCdpCMrSqHos/DXgb5DzBiObH3lIA2qOtLej4+seIx86TEy3IRLyIrAmJ4SIDv99ZgT0R9eFx6vu5b2CjLONdLqlFX5MseiGlMbnZiTRSXbE0tVMzswn1RjtuGCedQpsGfFy2ylnZYr7nrNJ8Tl75QHzwtk1xKsTFEtrko5pdgEVIrL/Thw0XdeBaeazpjdFIHq1Jd1XtKvMTiKU4NwUFuGjcO4ZqZaOunMfNLAs9HB99s4hHgSijNiT7YsrB400gP5mdb9j68Ep+r7Te/5p3aD2QabOcLWEruTkM48mUpd0yjK1Jp+XxIdTVJTvmI6crCkVNUHHy7s8mwWxj9DjutjqaTWVS+nh4enJSXCKXpSOwyHaHe0K2qw==
Thank you. HQ said that I can rely on you. Here is top secret message.
It is encrypted with public RSA key contained in message that you gave me.
Please deliver it to HQ as soon as posible.

6872c2091fdc4ef1458500f9bd3e13b70dcb92071e623189e189bc19e6d5eb24a1b199baf0bcf964816fbe97b2371dcf777372c1f1f5b627ad8dd6360adb230a131fab73b67886b5fb3f1e077ea0b6ab76a2bc9de945195656faaca20fd08c524c10044b268e59613d0fe6f5c35a0f0f460845b4ad843eb1387fdb9e9c9f25cb

どうやら12バイト目は何か重要なフラグ(CTF的な意味ではなく)が入る場所で、そのフラグが立っていたから信用された、ということらしい。
この後1) Go to HQを選んでもまたおつかいを頼まれるだけなので、この16進数のシークレットメッセージの中に重要情報が含まれていると考えられる。このシークレットメッセージはRSAで暗号化されていて、その公開鍵はさっきのAES-OFBで暗号化されたメッセージの中に書かれているということなので、それについてさらに情報を集めることにする。

さっきのAES-OFBメッセージについて、12バイト目以降も改竄しながら試行錯誤していくと、以下のことが判明する。

  • メッセージ長は必ず337バイトである。
  • 1~11、13~17、327~331、337バイト目は改竄すると確実に怒られる。
  • 18~326、332~336バイト目は改竄すると怒られる場合と怒られない場合がある。
  • 18~326バイト目はまったく同じ改竄をしても、怒られる場合と怒られない場合がある。つまり平文が毎回変わっている。
  • 332~336バイト目はまったく同じ改竄をすると、まったく同じ応答が返ってくる。つまり平文が毎回変わらない。↓にXORしても怒られない数のリストを示す。
332 [0, 1, 2, 3, 4, 5, 7, 14, 15, 22, 27, 59, 60, 63]
333 [0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 27, 80, 112]
334 [0, 1, 2, 3, 4, 5, 6, 7, 12, 13, 27, 80, 112]
335 [0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 29, 86, 118]
336 [0, 1, 2, 3, 4, 5, 6, 7, 14, 15, 23, 58, 61, 62]

例えば332バイト目に14や15をXORしても怒られないが、6、8、9などをXORすると怒られる。

この結果を見ると、332~336バイト目は公開鍵 {e=}65537を表しているような気がしてくる。また、18~326バイト目は公開鍵 {N}を表しているのではないかという感じがする。(1024ビットの数は10進法だと大体308~309桁ぐらいなので、桁数もそれっぽい。)しかし {N}の具体的な値は分からないし、そもそも分かったところで秘密鍵がなければ復号できない。

ここで、シークレットメッセージを受け取るときに言われたことをもう一度思い返してみる。

It is encrypted with public RSA key contained in message that you gave me.

この文から、AES-OFBメッセージ中の公開鍵を別の値に改竄してから渡した場合、改竄後の値を用いてシークレットメッセージが作られる、と予想できる。そこで、332~336バイト目の65537    1(スペース4つと1)に改竄し(JSON形式ではスペースは内容に影響しない)、さらに12バイト目のフラグも立てた状態でメッセージを渡してみる。RSAの暗号文は {m^e(\mathrm{mod}\;N)}{m}は平文)で求めるから、{e=1}のときは平文がそのまま出てくるはずである。

実際に渡してみると、

6374667a6f6e657b3046425f4d3064335f43346e375f243456335f4133245f4b33597d

と、ちゃんとシークレットメッセージが短くなっていて、暗号化に {e=1}が使われたことが分かる。これをlong_to_bytes()にかけると(CTF的な意味での)フラグが出る。