LA CTF 2023 Writeup - よっちんのブログ

この大会は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}