この大会は2023/2/11 13:00(JST)~2023/2/13 7:00(JST)に開催されました。
今回もチームで参戦。結果は7794点で980チーム中52位でした。
自分で解けた問題をWriteupとして書いておきます。
discord (misc)
Discordに入り、#faqチャネルのトピックを見ると、フラグが書いてあった。
Check out some frequently asked questions. Please read them before asking questions, but if you are still unsure, feel free to make a support ticket in #support. Flag: lactf{i_joined_discord_and_read_the_faq}
lactf{i_joined_discord_and_read_the_faq}
hike to where? (misc)
写真の場所を答える問題。LACTFの公式ページ https://lactf.uclaacm.com/ のSpeakersに写真の人が載っている。名前は Carey Nachenberg。
写真にあるワードから、"hike"を付け、"Carey Nachenberg hike"でGoogle検索する。検索結果から画像タブを選択し、岩の感じの近い画像の箇所を探す。
https://www.peaksandprofessorsucla.org/post/11-06-skull-rock-via-temescal-canyon-w-carey-nachenberg
場所は「Skull Rock」。
lactf{skull_rock}
hidden in plain sheets (misc)
スプレッドシートで閲覧のみが可能だが、「編集」「検索と置換」メニューから全シートに対して検索ができる。一文字ずつ「大文字と小文字の区別」にチェックを入れ検索し、フラグの断片の情報を集める。
&:非表示のセルflag!N1で値「&」との一致が見つかりました。 1:非表示のセルflag!H1で値「1」との一致が見つかりました。 3:非表示のセルflag!K1で値「3」との一致が見つかりました。 5:非表示のセルflag!Z1で値「5」との一致が見つかりました。 A:非表示のセルflag!AG1で値「A」との一致が見つかりました。 D:非表示のセルflag!X1で値「D」との一致が見つかりました。 H:非表示のセルflag!G1で値「H」との一致が見つかりました。 O:非表示のセルflag!R1で値「O」との一致が見つかりました。 T:非表示のセルflag!V1で値「T」との一致が見つかりました。 _:非表示のセルflag!M1で値「_」との一致が見つかりました。 a:非表示のセルflag!B1で値「a」との一致が見つかりました。 c:非表示のセルflag!C1で値「c」との一致が見つかりました。 d:非表示のセルflag!I1で値「d」との一致が見つかりました。 f:非表示のセルflag!E1で値「f」との一致が見つかりました。 h:非表示のセルflag!AA1で値「h」との一致が見つかりました。 l:非表示のセルflag!A1で値「l」との一致が見つかりました。 n:非表示のセルflag!L1で値「n」との一致が見つかりました。 p:非表示のセルflag!P1で値「p」との一致が見つかりました。 r:非表示のセルflag!Q1で値「r」との一致が見つかりました。 t:非表示のセルflag!D1で値「t」との一致が見つかりました。 {:非表示のセルflag!F1で値「{」との一致が見つかりました。 }:非表示のセルflag!AR1で値「}」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!J1:AQ1]
1:非表示のセルflag!AM1で値「1」との一致が見つかりました。 c:非表示のセルflag!U1で値「c」との一致が見つかりました。 d:非表示のセルflag!J1で値「d」との一致が見つかりました。 t:非表示のセルflag!S1で値「t」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!O1:AQ1]
3:非表示のセルflag!T1で値「3」との一致が見つかりました。 _:非表示のセルflag!O1で値「_」との一致が見つかりました。 n:非表示のセルflag!AK1で値「n」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!W1:AQ1]
3:非表示のセルflag!W1で値「3」との一致が見つかりました。 T:非表示のセルflag!AD1で値「T」との一致が見つかりました。 _:非表示のセルflag!Y1で値「_」との一致が見つかりました。 r:非表示のセルflag!AH1で値「r」との一致が見つかりました。 t:非表示のセルflag!AN1で値「t」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!AB1:AQ1]
3:非表示のセルflag!AB1で値「3」との一致が見つかりました。 5:非表示のセルflag!AE1で値「5」との一致が見つかりました。 _:非表示のセルflag!AF1で値「_」との一致が見つかりました。 h:非表示のセルflag!AO1で値「h」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!AC1:AQ1]
3:非表示のセルflag!AC1で値「3」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!AI1:AQ1]
3:非表示のセルflag!AI1で値「3」との一致が見つかりました。 _:非表示のセルflag!AJ1で値「_」との一致が見つかりました。 r:非表示のセルflag!AQ1で値「r」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!AL1:AQ1]
3:非表示のセルflag!AL1で値「3」との一致が見つかりました。
検索範囲を変える。[特定の範囲][flag!AP1:AQ1]
3:非表示のセルflag!AP1で値「3」との一致が見つかりました。
AAAAAAAAAAAAAAAAAA ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQR lactf{H1dd3n_&_prOt3cT3D_5h33T5_Ar3_n31th3r}
lactf{H1dd3n_&_prOt3cT3D_5h33T5_Ar3_n31th3r}
caterpillar (rev)
ブラウザのデベロッパーツールで確認しながら、フラグの条件を見ていく。
-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~[] →17 -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~[] →108
"-~"の数がそのまま数値になることがわかるので、スクリプトで条件を抽出し、フラグを割り出す。
#!/usr/bin/env python3 with open('caterpillar.js', 'r') as f: data = f.read().splitlines()[1] data = data[4:-3].split(' && ') flag = [''] * len(data) for d in data: pos = d.split(' == ')[0].count('-~') val = d.split(' == ')[1].count('-~') flag[pos] = chr(val) flag = ''.join(flag) print(flag)
lactf{th3_hungry_l1ttl3_c4t3rp1ll4r_at3_th3_fl4g_4g41n}
string-cheese (rev)
Ghidraでデコンパイルする。
undefined8 main(void) { int iVar1; size_t sVar2; char local_108 [256]; printf("What\'s my favorite flavor of string cheese? "); fflush(stdout); fgets(local_108,0x100,stdin); sVar2 = strcspn(local_108,"\n"); local_108[sVar2] = '\0'; iVar1 = strcmp(local_108,"blueberry"); if (iVar1 == 0) { puts("...how did you know? That isn\'t even a real flavor..."); puts("Well I guess I should give you the flag now..."); print_flag(); } else { puts("Hmm... I don\'t think that\'s quite it. Better luck next time!"); } return 0; }
"blueberry"と答えれば、フラグが表示されることがわかる。
$ nc lac.tf 31131 What's my favorite flavor of string cheese? blueberry ...how did you know? That isn't even a real flavor... Well I guess I should give you the flag now... lactf{d0n7_m4k3_fun_0f_my_t4st3_1n_ch33s3}
lactf{d0n7_m4k3_fun_0f_my_t4st3_1n_ch33s3}
finals-simulator (rev)
Ghidraでデコンパイルする。
undefined8 main(void) { int iVar1; size_t sVar2; int local_11c; char local_118 [264]; char *local_10; puts("Welcome to Finals Simulator 2023: Math Edition!"); printf("Question #1: What is sin(x)/n? "); fflush(stdout); fgets(local_118,0x100,stdin); sVar2 = strcspn(local_118,"\n"); local_118[sVar2] = '\0'; iVar1 = strcmp(local_118,"six"); if (iVar1 == 0) { printf("Question #2: What\'s the prettiest number? "); fflush(stdout); __isoc99_scanf(&DAT_001020c3,&local_11c); if ((local_11c + 0x58) * 0x2a == 0x2179556a) { printf("Question #3: What\'s the integral of 1/cabin dcabin? "); fflush(stdout); getchar(); fgets(local_118,0x100,stdin); sVar2 = strcspn(local_118,"\n"); local_118[sVar2] = '\0'; for (local_10 = local_118; *local_10 != '\0'; local_10 = local_10 + 1) { *local_10 = (char)((long)(*local_10 * 0x11) % 0xfd); } putchar(10); iVar1 = strcmp(local_118,enc); if (iVar1 == 0) { puts("Wow! A 100%! You must be really good at math! Here, have a flag as a reward."); print_flag(); } else { puts("Wrong! You failed."); } } else { puts("Wrong! You failed."); } } else { puts("Wrong! You failed."); } return 0; } enc XREF[2]: Entry Point(*), main:001013f8(*) 00104080 0e c9 9d undefine b8 26 83 26 41 74 00104080 0e undefined10Eh [0] XREF[2]: Entry Point(*), main:001013f8(*) 00104081 c9 undefined1C9h [1] 00104082 9d undefined19Dh [2] 00104083 b8 undefined1B8h [3] 00104084 26 undefined126h [4] 00104085 83 undefined183h [5] 00104086 26 undefined126h [6] 00104087 41 undefined141h [7] 00104088 74 undefined174h [8] 00104089 e9 undefined1E9h [9] 0010408a 26 undefined126h [10] 0010408b a5 undefined1A5h [11] 0010408c 83 undefined183h [12] 0010408d 94 undefined194h [13] 0010408e 0e undefined10Eh [14] 0010408f 63 undefined163h [15] 00104090 37 undefined137h [16] 00104091 37 undefined137h [17] 00104092 37 undefined137h [18] 00104093 00 undefined100h [19]
Questionに答えていく。
・Question #1: What is sin(x)/n? →"six" ・Question #2: What\'s the prettiest number? →(local_11c + 0x58) * 0x2a == 0x2179556aを満たすlocal_11c →local_11c = 0x2179556a / 0x2a - 0x58 = 13371337 ・Question #3: What\'s the integral of 1/cabin dcabin? →入力文字の各文字について、*local_10 = (char)((long)(*local_10 * 0x11) % 0xfd) で変換し、encと同じになる。 →ブルートーフォースで答えを見つける。 →"it's a log cabin!!!"
#!/usr/bin/env python3 enc = [0x0e, 0xc9, 0x9d, 0xb8, 0x26, 0x83, 0x26, 0x41, 0x74, 0xe9, 0x26, 0xa5, 0x83, 0x94, 0x0e, 0x63, 0x37, 0x37, 0x37] ans = '' for i in range(len(enc)): for code in range(32, 127): if (code * 0x11) % 0xfd == enc[i]: ans += chr(code) break print(ans)
$ nc lac.tf 31132 Welcome to Finals Simulator 2023: Math Edition! Question #1: What is sin(x)/n? six Question #2: What's the prettiest number? 13371337 Question #3: What's the integral of 1/cabin dcabin? it's a log cabin!!! Wow! A 100%! You must be really good at math! Here, have a flag as a reward. lactf{im_n0t_qu1t3_sur3_th4ts_h0w_m4th_w0rks_bu7_0k}
lactf{im_n0t_qu1t3_sur3_th4ts_h0w_m4th_w0rks_bu7_0k}
greek cipher (crypto)
ギリシャ文字の暗号になっている。換字式暗号と推測する。一旦適当にアルファベットに置き換える。
ABA CDE FGDH IJKI LEMBEN OKPNKQ HKN GDI IJP RBQNI SPQNDG BG JBNIDQC NENSPOIPA DR ENBGT PGOQCSIBDG? UP GPBIJPQ. ABA CDE FGDH IJKI LEMBEN OKPNKQ HKN SQDVKVMC RMEPGI BG TQPPF? UP GPBIJPQ. B MBFP JDH TQPPF OJKQKOIPQ MDDF IJDETJ, PWPG BR B OKG'I QPKA IJPU. MKOIR{B_TEPNN_ENBGT_UKGC_TQPPF_OJKQKOIPQN_ABAG'I_NIDS_CDE._HPMM_SMKCPA_B_UENI_NKC.ODGTQKIN!}
quipqiupで復号する。
DID YOU KNOW THAT JULIUS CAESAR WAS NOT THE FIRST PERSON IN HISTORY SUSPECTED OF USING ENCRYPTION? ME NEITHER. DID YOU KNOW THAT JULIUS CAESAR WAS PROBABLY FLUENT IN GREEK? ME NEITHER. I LIKE HOW GREEK CHARACTER LOOK THOUGH, EVEN IF I CAN'T READ THEM. LACTF{I_GUESS_USING_MANY_GREEK_CHARACTERS_DIDN'T_STOP_YOU._WELL_PLAYED_I_MUST_SAY.CONGRATS!}
文末にフラグが含まれている。小文字で答える必要があるので、変換する。
lactf{i_guess_using_many_greek_characters_didn't_stop_you._well_played_i_must_say.congrats!}
rolling in the mud (crypto)
Pigpen Cipher。https://en.wikipedia.org/wiki/Pigpen_cipherを参照しながら、復号する。なお復号する際、画像を180度回転させた上で行う。
lactf{rolling_and_rolling_and_rolling_until_the_pigs_go_home}
one-more-time-pad (crypto)
XOR鍵がフラグになっている。平文と暗号文のXORを取れば、フラグがわかる。
#!/usr/bin/env python3 from Crypto.Util.strxor import strxor pt = b"Long ago, the four nations lived together in harmony ..." ct = "200e0d13461a055b4e592b0054543902462d1000042b045f1c407f18581b56194c150c13030f0a5110593606111c3e1f5e305e174571431e" ct = bytes.fromhex(ct) key = strxor(pt, ct) index = key.index(b"lactf", 1) flag = key[:32].decode() print(flag)
lactf{b4by_h1t_m3_0ne_m0r3_t1m3}
chinese-lazy-theorem-1 (crypto)
サーバの処理概要は以下の通り。
・p, q: 512ビット素数 ・n = p * q ・target: ランダム1以上n以下整数 ・used_oracle = False ・p, qを表示 ・以下繰り返し ・response: 入力 ・responseが"1"の場合 ・used_oracleがTrueの場合、メッセージ表示 ・used_oracleがFalseの場合 ・modulus: 数値入力 ・modulusが0以下の場合、メッセージ表示 ・modulusが0より大きい場合 ・used_oracle = True ・target%modulusを表示 ・responseが"2"の場合 ・guess: 数値入力 ・guessがtargetと同じ場合、フラグを表示
modulusでp*qを指定すれば、targetが表示される。このtargetをguessに指定すればフラグが表示される。
#!/usr/bin/env python3 import socket def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('lac.tf', 31110)) data = recvuntil(s, b'\n').rstrip() print(data) p = int(data) data = recvuntil(s, b'\n').rstrip() print(data) q = int(data) n = p * q data = recvuntil(s, b'>> ') print(data + '1') s.sendall(b'1\n') data = recvuntil(s, b': ') print(data + str(n)) s.sendall(str(n).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) target = data data = recvuntil(s, b'>> ') print(data + '2') s.sendall(b'2\n') data = recvuntil(s, b': ') print(data + str(target)) s.sendall(str(target).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
10083872147051283573257007447823329935918808400808582083597787025058852660834863379684543585349035166555384728430779818003891186255659840225570587291792421 13156551568782229536833995399746981804971700080597595773717551150193280502133093534670031445678780605500194714753145218815112819263849412128035771910128911 To quote Pete Bancini, "I'm tired." I'll answer one modulus question, that's it. What do you want? 1: Ask for a modulus 2: Guess my number 3: Exit >> 1 Type your modulus here: 132668983915686994111228276504638451534702169890184461009306824599327337183669342178399826449492979269443261943127553141909799529706058438368685689553999155963373318408459621545639091436590860163989671422618093218516574043158751220315631552003689982472467188724658004229710531958503736666449560201066362783531 75352257241703214757072436220792132249157565335228525963975012765615488181653632474527378608328913376697357049697617776585808134737608208252913066849791335552719106034089868004254632076176658866014464404605464096003216329702923912036528304667789750868298041110309371559239215041436595799500366133945598582885 What do you want? 1: Ask for a modulus 2: Guess my number 3: Exit >> 2 Type your guess here: 75352257241703214757072436220792132249157565335228525963975012765615488181653632474527378608328913376697357049697617776585808134737608208252913066849791335552719106034089868004254632076176658866014464404605464096003216329702923912036528304667789750868298041110309371559239215041436595799500366133945598582885 lactf{too_lazy_to_bound_the_modulus}
lactf{too_lazy_to_bound_the_modulus}
chinese-lazy-theorem-2 (crypto)
サーバの処理概要は以下の通り。
・p, q: 512ビット素数 ・n = p * q * 2 * 3 * 5 ・target: ランダム1以上n以下整数 ・oracle_uses = 0 ・p, qを表示 ・以下繰り返し ・response: 入力 ・responseが"1"の場合 ・oracle_usesが2の場合、メッセージ表示 ・oracle_usesが2以外の場合 ・modulus: 数値入力 ・modulusが0以下の場合、メッセージ表示 ・modulusが0より大きく、p, qの最大値より大きい場合、メッセージ表示 ・modulusが0より大きく、p, qの最大値以下の場合 ・oracle_usesを1プラス ・target%modulusを表示 ・responseが"2"の場合 ・以下30回繰り返し ・guess: 数値入力 ・guessがtargetと同じ場合、フラグを表示して終了
modulusに1回目でp、2回目でqを指定する。target % modulusが表示されるので、CRTでtarget % (p*q)を割り出す。あとはこの値をベースにp*qの30倍までプラスした値を試していけば、targetと同じ値にあたりフラグが表示される。
#!/usr/bin/env python3 import socket from sympy.ntheory.modular import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('lac.tf', 31111)) data = recvuntil(s, b'\n').rstrip() print(data) p = int(data) data = recvuntil(s, b'\n').rstrip() print(data) q = int(data) modulus = [p, q] remains = [] for mod in modulus: data = recvuntil(s, b'>> ') print(data + '1') s.sendall(b'1\n') data = recvuntil(s, b': ') print(data + str(mod)) s.sendall(str(mod).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) remains.append(int(data)) base = int(crt(modulus, remains)[0]) data = recvuntil(s, b'>> ') print(data + '2') s.sendall(b'2\n') for i in range(30): target = base + (p * q) * i data = recvuntil(s, b': ') print(data + str(target)) s.sendall(str(target).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) if data != 'nope': break
実行結果は以下の通り。
9111260498521138436621848553463791826166726352693563353823492191207958098334412055667841438747878246261312516716701456497329019659424847933168029282799869 9953243347335660292399409566564817275571124698729758718090017675500807498810308054769192080594763880349139106024460931740238195639656887534971495346008833 This time I'll answer 2 modulus questions and give you 30 guesses. What do you want? 1: Ask for a modulus 2: Guess my number 3: Exit >> 1 Type your modulus here: 9111260498521138436621848553463791826166726352693563353823492191207958098334412055667841438747878246261312516716701456497329019659424847933168029282799869 9081766231987960001801239134096578041887199065209736857194311959037753569563975441936605177466996291767036925388210674748469329571733227223196666157596437 What do you want? 1: Ask for a modulus 2: Guess my number 3: Exit >> 1 Type your modulus here: 9953243347335660292399409566564817275571124698729758718090017675500807498810308054769192080594763880349139106024460931740238195639656887534971495346008833 5564799787928348914210642672813682673885795293843193239062401924055911377137997798386123444451185142441918378651189626151130881222818216250626992827456756 What do you want? 1: Ask for a modulus 2: Guess my number 3: Exit >> 2 Type your guess here: 15559791073818543120776156030708626460902208964630640218368921836716666016536350803034035363776132173386940757352765282804221441678863066854345216520513041608952085252285546731369028028540794500701666282541484222931509547379428797887941546693874776532082236170698049292209585954482929561548603762965205502531 nope Type your guess here: 106246384016566255967009346802696068315715160408939211821015376057289113515453501986424718721929383876006536139752603264641281554887994963919237286610580499579524701105505242995230105919984699898064834491403131459262295320555682660613458329663551673390280762240071925223797268057754574290507113548529850745408 nope Type your guess here: 196932976959313968813242537574683510170528111853247783423661830277861561014370653169815402080082635578626131522152441246478341668097126860984129356700647957550097316958724939259091183811428605295428002700264778695593081093731936523338975112633228570248479288309445801155384950161026219019465623334094495988285 nope Type your guess here: 287619569902061681659475728346670952025341063297556355026308284498434008513287804353206085438235887281245726904552279228315401781306258758049021426790715415520669932811944635522952261702872510692791170909126425931923866866908190386064491895602905467106677814378819677086972632264297863748424133119659141231162 nope Type your guess here: 378306162844809394505708919118658393880154014741864926628954738719006456012204955536596768796389138983865322286952117210152461894515390655113913496880782873491242548665164331786813339594316416090154339117988073168254652640084444248790008678572582363964876340448193553018560314367569508477382642905223786474039 nope Type your guess here: 468992755787557107351942109890645835734966966186173498231601192939578903511122106719987452154542390686484917669351955191989522007724522552178805566970850331461815164518384028050674417485760321487517507326849720404585438413260698111515525461542259260823074866517567428950147996470841153206341152690788431716916 nope Type your guess here: 559679348730304820198175300662633277589779917630482069834247647160151351010039257903378135512695642389104513051751793173826582120933654449243697637060917789432387780371603724314535495377204226884880675535711367640916224186436951974241042244511936157681273392586941304881735678574112797935299662476353076959793 nope Type your guess here: 650365941673052533044408491434620719444592869074790641436894101380723798508956409086768818870848894091724108434151631155663642234142786346308589707150985247402960396224823420578396573268648132282243843744573014877247009959613205836966559027481613054539471918656315180813323360677384442664258172261917722202670 nope Type your guess here: 741052534615800245890641682206608161299405820519099213039540555601296246007873560270159502229002145794343703816551469137500702347351918243373481777241052705373533012078043116842257651160092037679607011953434662113577795732789459699692075810451289951397670444725689056744911042780656087393216682047482367445547 nope Type your guess here: 831739127558547958736874872978595603154218771963407784642187009821868693506790711453550185587155397496963299198951307119337762460561050140438373847331120163344105627931262813106118729051535943076970180162296309349908581505965713562417592593420966848255868970795062932676498724883927732122175191833047012688424 nope Type your guess here: 922425720501295671583108063750583045009031723407716356244833464042441141005707862636940868945308649199582894581351145101174822573770182037503265917421187621314678243784482509369979806942979848474333348371157956586239367279141967425143109376390643745114067496864436808608086406987199376851133701618611657931301 nope Type your guess here: 1013112313444043384429341254522570486863844674852024927847479918263013588504625013820331552303461900902202489963750983083011882686979313934568157987511255079285250859637702205633840884834423753871696516580019603822570153052318221287868626159360320641972266022933810684539674089090471021580092211404176303174178 nope Type your guess here: 1103798906386791097275574445294557928718657626296333499450126372483586036003542165003722235661615152604822085346150821064848942800188445831633050057601322537255823475490921901897701962725867659269059684788881251058900938825494475150594142942329997538830464549003184560471261771193742666309050721189740948417055 nope Type your guess here: 1194485499329538810121807636066545370573470577740642071052772826704158483502459316187112919019768404307441680728550659046686002913397577728697942127691389995226396091344141598161563040617311564666422852997742898295231724598670729013319659725299674435688663075072558436402849453297014311038009230975305593659932 nope Type your guess here: 1285172092272286522968040826838532812428283529184950642655419280924730931001376467370503602377921656010061276110950497028523063026606709625762834197781457453196968707197361294425424118508755470063786021206604545531562510371846982876045176508269351332546861601141932312334437135400285955766967740760870238902809 nope Type your guess here: 1375858685215034235814274017610520254283096480629259214258065735145303378500293618553894285736074907712680871493350335010360123139815841522827726267871524911167541323050580990689285196400199375461149189415466192767893296145023236738770693291239028229405060127211306188266024817503557600495926250546434884145686 nope Type your guess here: 1466545278157781948660507208382507696137909432073567785860712189365875825999210769737284969094228159415300466875750172992197183253024973419892618337961592369138113938903800686953146274291643280858512357624327840004224081918199490601496210074208705126263258653280680064197612499606829245224884760331999529388563 nope Type your guess here: 1557231871100529661506740399154495137992722383517876357463358643586448273498127920920675652452381411117920062258150010974034243366234105316957510408051659827108686554757020383217007352183087186255875525833189487240554867691375744464221726857178382023121457179350053940129200181710100889953843270117564174631440 nope Type your guess here: 1647918464043277374352973589926482579847535334962184929066005097807020720997045072104066335810534662820539657640549848955871303479443237214022402478141727285079259170610240079480868430074531091653238694042051134476885653464551998326947243640148058919979655705419427816060787863813372534682801779903128819874317 nope Type your guess here: 1738605056986025087199206780698470021702348286406493500668651552027593168495962223287457019168687914523159253022949686937708363592652369111087294548231794743049831786463459775744729507965974997050601862250912781713216439237728252189672760423117735816837854231488801691992375545916644179411760289688693465117194 lactf{n0t_$o_l@a@AzY_aNYm0Re}
lactf{n0t_$o_l@a@AzY_aNYm0Re}
ravin-cryptosystem (crypto)
暗号化処理の概要は以下の通り。
・p, q: 100ビット素数 ・n = p * q ・e = 65537 ・m: フラグの数値化 ・c = fastpow(m, e, n) ・n, e, cを表示
eが65537の場合、以下のような計算になる。
c = fastpow(m, e, n) = pow(m, e - 1, n) = pow(m, 2**16, n)
nを素因数分解する。
>yafu-x64.exe "factor(996905207436360486995498787817606430974884117659908727125853)" -v -threads 4 02/11/23 15:09:24 v1.34.5 @ XXXXXXXX, System/Build Info: Using GMP-ECM 6.3, Powered by GMP 5.1.1 detected Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes measured cpu frequency ~= 2899.299640 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> fac: factoring 996905207436360486995498787817606430974884117659908727125853 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C60 rho: x^2 + 2, starting 1000 iterations on C60 rho: x^2 + 1, starting 1000 iterations on C60 pm1: starting B1 = 150K, B2 = gmp-ecm default on C60 fac: setting target pretesting digits to 18.46 fac: sum of completed work is t0.00 fac: work done at B1=2000: 0 curves, max work = 30 curves fac: 30 more curves at B1=2000 needed to get to t18.46 ecm: 30/30 curves on C60, B1=2K, B2=gmp-ecm default fac: setting target pretesting digits to 18.46 fac: t15: 1.00 fac: t20: 0.04 fac: sum of completed work is t15.18 fac: work done at B1=11000: 0 curves, max work = 74 curves fac: 49 more curves at B1=11000 needed to get to t18.46 ecm: 49/49 curves on C60, B1=11K, B2=gmp-ecm default fac: setting target pretesting digits to 18.46 fac: t15: 5.08 fac: t20: 0.70 fac: t25: 0.03 fac: sum of completed work is t18.49 starting SIQS on c60: 996905207436360486995498787817606430974884117659908727125853 ==== sieve params ==== n = 62 digits, 206 bits factor base: 3824 primes (max prime = 78877) single large prime cutoff: 4732620 (60 * pmax) allocating 2 large prime slices of factor base buckets hold 2048 elements using SSE4.1 enabled 32k sieve core sieve interval: 4 blocks of size 32768 polynomial A has ~ 7 factors using multiplier of 53 using SPV correction of 21 bits, starting at offset 34 using SSE2 for x64 sieve scanning using SSE2 for resieving 13-16 bit primes using SSE2 for 8x trial divison to 13 bits using SSE4.1 and inline ASM for small prime sieving using SSE2 for poly updating up to 15 bits using SSE4.1 for medium prime poly updating using SSE4.1 and inline ASM for large prime poly updating trial factoring cutoff at 69 bits ==== sieving in progress ( 4 threads): 3888 relations needed ==== ==== Press ctrl-c to abort and save state ==== 3661 rels found: 1916 full + 1745 from 17153 partial, (15814.52 rels/sec) sieving required 9828 total polynomials trial division touched 160974 sieve locations out of 2576351232 QS elapsed time = 1.2975 seconds. ==== post processing stage (msieve-1.38) ==== begin with 20238 relations reduce to 5720 relations in 2 passes attempting to read 5720 relations recovered 5720 relations recovered 4306 polynomials freed 1 duplicate relations attempting to build 4012 cycles found 4012 cycles in 1 passes distribution of cycle lengths: length 1 : 2054 length 2 : 1958 largest cycle: 2 relations matrix is 3824 x 4012 (0.5 MB) with weight 102141 (25.46/col) sparse part has weight 102141 (25.46/col) filtering completed in 4 passes matrix is 3524 x 3588 (0.4 MB) with weight 89132 (24.84/col) sparse part has weight 89132 (24.84/col) commencing Lanczos iteration memory use: 0.6 MB lanczos halted after 57 iterations (dim = 3521) recovered 63 nontrivial dependencies Lanczos elapsed time = 0.0770 seconds. Sqrt elapsed time = 0.0020 seconds. SIQS elapsed time = 1.3773 seconds. pretesting / qs ratio was 0.89 Total factoring time = 2.6716 seconds ***factors found*** P31 = 1157379696919172022755244871343 P30 = 861346721469213227608792923571 ans = 1
この値を使って、16回Rabin暗号の復号方法で復号していき、フラグ形式にあてはまるものを探す。
#!/usr/bin/python3 from Crypto.Util.number import * def egcd(a, b): if a == 0: return b, 0, 1 else: gcd, y, x = egcd(b % a, a) return gcd, x - (b // a) * y, y with open('output.txt', 'r') as f: params = f.read().splitlines() n = int(params[0].split(' ')[-1]) e = int(params[1].split(' ')[-1]) c = int(params[2].split(' ')[-1]) p = 861346721469213227608792923571 q = 1157379696919172022755244871343 assert p * q == n assert p % 4 == 3 and q % 4 == 3 cs = [c] for i in range(16): ps = [] for c2 in cs: r = pow(c2, (p + 1) // 4, p) s = pow(c2, (q + 1) // 4, q) gcd, x0, x1 = egcd(p, q) x = (r * x1 * q + s * x0 * p) % n y = (r * x1 * q - s * x0 * p) % n if x not in ps: ps.append(x) if n - x not in ps: ps.append(n - x) if y not in ps: ps.append(y) if n - y not in ps: ps.append(n - y) cs = ps for m in ps: flag = long_to_bytes(m) if flag.startswith(b'lactf{'): flag = flag.decode() print(flag) break
lactf{g@rbl3d_r6v1ng5}
hill-easy (crypto)
サーバの処理概要は以下の通り。
・n = 20 ・A: 0以上95以下の20x20の行列 ・fakeflag: "lactf{" + [33個のランダム英小文字+"{"] + "}" ・fakeflag2: "lactf{" + [33個のランダム英小文字+"{"] + "}" ・f1: fakeflagの前半の暗号化 ・f2: fakeflagの後半の暗号化 ・f3: fakeflag2の前半の暗号化 ・f4: fakeflag2の後半の暗号化 ・f1, f2を表示 ・以下10回繰り返し(i) ・guess(i) ・trydecode() ・guess: 入力 ・oracle(guess) ・o1: guessの前半の暗号化 ・o2: guessの後半の暗号化 ・o1とf1が一致し、o2とf2が一致している場合、flagを表示して終了 ・o1とf1が異なり、o2とf2が異なる場合、o1, o2を表示 ・fakeflag2を表示 ・guess1: 入力 ・guess2: 入力 ・guess1とf3が一致し、guess2とf4が一致している場合、flagを表示
1回のguessで2個の暗号が得られる。それを10回実施すると、20個の暗号が得られる。
[p00_00, p00_01, ... p00_19] [c00_00, c00_01, ... c00_19] [p01_00, p01_01, ... p01_19] [c01_00, c01_01, ... c01_19] A * : = : [p18_00, p18_01, ... p18_19] [c18_00, c18_01, ... c18_19] [p19_00, p19_01, ... p19_19] [c19_00, c19_01, ... c19_19]
上記は次のように表すことができる。
A * P = C
" "(スペース)文字が0、"!"が1であることを利用して、Pに単位行列Eを指定すれば、以下のように計算できる。
A * E = C = A
このAを使って、fakeflag2を暗号化すれば、f3, f4がわかる。
#!/usr/bin/env python3 import socket import numpy as np n = 20 def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def stoa(s): return [ord(c) - 32 for c in s] def stov(s): return np.array([ord(c) - 32 for c in s]) def vtos(v): return ''.join([chr(v[i] + 32) for i in range(n)]) def encrypt(s): return vtos(np.matmul(A, stov(s)) % 95) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('lac.tf', 31140)) for _ in range(5): data = recvuntil(s, b'\n').rstrip() print(data) C = [] for i in range(10): guess = ' ' * (i * 2) + '!' + ' ' * (19 - i * 2) guess += ' ' * (i * 2 + 1) + '!' + ' ' * (19 - i * 2 - 1) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b': ') print(data + guess) s.sendall(guess.encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) C.append(stoa(data)) data = recvuntil(s, b'\n').rstrip() print(data) C.append(stoa(data)) data = recvuntil(s, b'\n').rstrip() print(data) C = np.array(C).T A = C for _ in range(3): data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) fakeflag2 = data f3 = encrypt(fakeflag2[:n]) f4 = encrypt(fakeflag2[n:]) data = recvuntil(s, b': ') print(data + f3) s.sendall(f3.encode() + b'\n') data = recvuntil(s, b': ') print(data + f4) s.sendall(f4.encode() + b'\n') for _ in range(3): data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
On the hill lies a stone. It reads: \X7vYKO7dW(,jaU5{Fb# $=J!qmT8kOPTqHW+IQ?u A mysterious figure offers you 10 attempts at decoding the stone: Enter your guess: ! ! Incorrect: %X,!F\H xfD,~RCF'=Oo fg_^l-xj'tEhP%exw"vw You have 9 attempts left Enter your guess: ! ! Incorrect: |GI'=Lqnv$!Fb%R[1f.S ,q(JXl9jY<tcNsxprw?a You have 8 attempts left Enter your guess: ! ! Incorrect: jvK5'7"RH'1`U'wNP5c" VAL]oDx;TBuc|bJE(1}G You have 7 attempts left Enter your guess: ! ! Incorrect: +a2!Id_^[[,X^\ax&w}" gs_1bETZ?:7)vDd?>w79 You have 6 attempts left Enter your guess: ! ! Incorrect: l@U$[x+6l[+1/@O({8]> Jaq}n08^k8 Fl1:E!},y You have 5 attempts left Enter your guess: ! ! Incorrect: &<?wLA#X-?~Wv<-%B,^R l7;.(?C 4~z`|J"2jiQ_ You have 4 attempts left Enter your guess: ! ! Incorrect: ywuVj+j@J2s3.h~< 8ch !eeswtYO?xA!ytAj)yrI You have 3 attempts left Enter your guess: ! ! Incorrect: K_)R"z&3Ry}h#=M.:p}4 Udk]-t!/^H^N{//,\t'W You have 2 attempts left Enter your guess: ! ! Incorrect: nkRJ3tdXPhNt3HE|#Oo IN&Z3x0!3_(t^sZNk&PH You have 1 attempts left Enter your guess: ! ! Incorrect: OaVzfp>SF P0G_rpc;e8 -)ZL&__d5h'7+/=h"1Cj You have 0 attempts left The figure frowns, and turns to leave. In desperation, you beg for one more chance. The figure ponders, then reluctantly agrees to offer you an alternative task. Create a new stone that decodes to the following: lactf{qzxpywywqihskjssgpiuqmustvkkblyba} Enter the first half: !P^P\w9#_;U^kYF&0a_E Enter the second half: ~9hv7T*Q;<1t=:0%|4@u The text on the stone begins to rearrange itself into another message: lactf{tHeY_SaiD_l!NaLg_wOuLD_bE_fUN_115}
lactf{tHeY_SaiD_l!NaLg_wOuLD_bE_fUN_115}
guess-the-bit! (crypto)
サーバの処理概要は以下の通り。
・n: 固定の既知数値 ・a = 6 ・n, aを表示 ・150回以下繰り返し ・bit: ランダム0または1 ・c: ランダム0以上n未満整数 ・c = c**2 ・bitが1の場合 ・cにaを書ける ・cを表示 ・guess: 数値入力 ・guessがbitと異なる場合 ・チャレンジ終了 ・フラグを表示
cの平方根が整数の場合は0、そうでない場合は1で答えればよい。
#!/usr/bin/env python3 import socket import gmpy2 def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('lac.tf', 31190)) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) for i in range(150): data = recvuntil(s, b'\n').rstrip() print(data) c = int(data.split(' ')[-1]) _, success = gmpy2.iroot(c, 2) if success: bit = 0 else: bit = 1 data = recvuntil(s, b'? ') print(data + str(bit)) s.sendall(str(bit).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
n = 43799663339063312211273714468571591746940179019655418145595314556164983756585900662541462573429625012257141409310387298658375836921310691578072985664621716240663221443527506757539532339372290041884633435626429390371850645743643273836882575180662344402698999778971350763364891217650903860191529913028504029597794358613653479290767790778510701279503128925407744958108039428298936189375732992781717888915493080336718221632665984609704015735266455668556495869437668868103607888809570667555794011994982530936046877122373871458757189204379101886886020141036227219889443327932080080504040633414853351599120601270071913534530651 a = 6 c = 1278405426782007745636807646591459392472166084937705953534760819148358207566528014572478816990768730481391573632768022712935909244253465158447719149565141940695390122618685277300932070929656796488014518535766677311117321040876418126995574424047224954655360189663816790835561821905477260072716238634746358905716900994287008918992286316867000469376600363773277044986420255855706582663228080139207031705855365887502404454833025842725036161258451269773945721637889946306373484183879484866884971260257751698228487909710105317025625894444207382674653021659169090675282674934844766546519612728001518952977313002402031886029458058306813333021590519702125468820538424637077254988914146208306417105061556363739766808720554581985316093368511974605192281088298814982575636845462008969760728187436873395412842201768120361025956128227570382323143512395354194183126735720864607074005451666337445693266887882314728055575021372187475578633155842170536310085237862326684825287183742526522984116614157737509059566325184455099899220023540135451056785481030358240511375262114276805941361693379754555651672204568071925727347487262509329817234766745592685254625970720742355082853983817254691982233194835933800735891000303610676703802968649778844768159065200891664 What is your guess? 0 c = 1141645009219804703518282906231209585015596354063656746253677238204059892548733614070254541303464464153384980635994954432562761089344396480008943356887975087576517085917718191723041940287313605637341697360342477552537030015837744928021675439986079753182546860099382886973529757331015569772567820799623519998328017475151828811967532433577380711288490220090192369030071032672040390571067773164993438888230746836089438937362957583203947410852040648661057253909099376043139123685303955087073684722602852149783862849651560251811323411191398862902799059571547039244481606414256563051229669603449404559189059603634238689251921632506080472105928371828580237490686342622891492847936556482602637728471653545095166453737429333988061099266626891540362216549193206717518551484655281525937592447174358817529956477126685728552008091223650959951142056064041305825118598789008217798748640708823663548226221560141883029212609952160938146552436621621636970541329664960733857157480685450976699393384189979174533803299890710012649455318534360383536070828409402764872913469211398106662714614184473417651691500936527227038750733166165987309721087077504691944744717658091132148215689637807237385985017462826726755602256638269738513931162775207762538490628943575969 What is your guess? 0 : : c = 721432692386123484537933616793520337213743647084575347722567316489962481299244670101324706960975794503912291267890445679762804114803837382167894877361333145017657776452523280913883510819174005294672875744773191571096804361702315763913449220802285170343203981589142217924395448606900528154254470567753875354060001878553476433951040929905456216372064039719534219200639576362879510178568809891974638555175819802079787620839317422113968742822277082590446383648072838144240388323029413133509723099233754711748261499228632580687418916319671544127013603684965387019753264874562530111090758516380897355756938278945685815172607819390354225674634789913100302412447313382088517924513249362473428966536858183664959614021050875969714078046307339833235163770887646122176614554127440096486344734593283214749149229101268433240739311628489837225237507547384740395856536609136757119653438491263733737394493030406143487492676220476853583038085527680202905806906868431388887815457676910291124452961522573327280432018570252206462411748198567246264850393017459126981555224619277717357159716592568662459726450044053056771816682778623269116668743118805268634324633215526806136921723406896859615475409826106172537383067862776128239541066128101103576037679303881956 What is your guess? 0 c = 604993156677068743270842218064488628671731388284834406206863283796836954425368580044874555822704585697448150856435757535836373593498127103963708708138485753772340990722923003606457814758085608359054963513545009646202446229739589776307197914846493635368378123397783040656794841330815395762098577798156721484940231427552616426799016511843800726266044084063648819380318764586000318934176052257839160198553613554275507928932268067876897688877331470725828010386324598687812369662433058044173663848148375600653497095413863414632975274341506323896059936355924632186685425908652975538885726373027803006546648130478108719477810275574518017929555991409815500689610479693736250532036551684384781848638706873495249155950690327440538718215765586872258012239894107641851851277008467820299616655503147066855826464077397179417071195211011467570966216699355713976353963622565828408737853870176794125097911303383699710367019607070450642207987748887756878368959177976456587622239109583092667224159188333908513124870688062472876747293695307774712311051848856685956632087486820826909420067011198440801474759360423337845224514079235561274081027322509133739425467934832263552082849856065736092588220978631067472864433951021409628978369537260158243051667148996184 What is your guess? 1 Congrats! Here's your flag: lactf{sm4ll_pla1nt3xt_sp4ac3s_ar3n't_al4ways_e4sy}
lactf{sm4ll_pla1nt3xt_sp4ac3s_ar3n't_al4ways_e4sy}
feedback (misc)
アンケートに答えると、以下のメッセージが表示された。
Thanks for responding! We really appreciate your feedback, and we hope to come back next year bigger and better! I know all you want is the flag. The flag is lactf{1_2_feedback_and_i_actually_submitted}, and replace 1 and 2 with flag parts 1 and 2. You noticed them throughout the form, right? Do NOT open a ticket asking where parts 1 and 2 are - we will just close them.
フラグのパート1と2を確認する必要がある。よく見たら、アンケートフォームの冒頭にこう書いてある。
Flag part 1 is i_give_my for when you need it later.
もう一度アンケートを見ていくと、好きなチャレンジの選択肢の中にflag part 2が入っていた。
flag-part-two is very_helpful
lactf{i_give_my_very_helpful_feedback_and_i_actually_submitted}