# UTCTF 2024 writeup (Author: dpduy123)
- Cuối tuần vừa rồi, mình đã tham gia đánh giải UTCTF 2024 cùng với "We make team just to participate CTF contest". Bọn mình end giải với rank 115 (Scoreboard đang được frozen) và mình đã giải được 4/8 bài Crypto. (Do trình của mình còn quá yếu nên không giải được nhiều như các Crypto Player khác trong trường).
- Dưới đây là writeup cho các challenge mà mình đã giải được:
## Solution available for:
### Cryptography:
1. [RSA-256](#RSA-256)
2. [Beginner:Anti-dcode.fr](#Beginner:Anti-dcode.fr)
3. [numbers_go_brrr](#numbers_go_brrr) (Coming soon)
4. [bits_and_pieces](#bits_and_pieces)
5. [Cryptordle](#Cryptordle)
6. [numbers_go_brrr_2](#numbers_go_brrr_2) (Coming soon)
7. [simple_signature](#simple_signature) (Coming soon)
8. [Forgery](#Forgery) (Comming soon)
## RSA-256
>Based on the military-grade encryption offered by AES-256, RSA-256 will usher in a new era of cutting-edge security... or at least, better security than RSA-128.
Attachment:
* vals.txt
```
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
```
Solution:
- Đây là bài warm up của RSA, ta có thể dễ dàng phân tích N thành 2 thừa số nguyên tố p * q một cách dễ dàng vì N chỉ có 256.
Script:
``` python = 0
from Crypto.Util.number import *
import math
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
p = 1025252665848145091840062845209085931
q = 75575216771551332467177108987001026743883
#Ta nhận được p và q thông qua phân tích N thành thừa số nguyến tố.
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag)
```
-> Flag: `utflag{just_send_plaintext}`
## Beginner:Anti-dcode.fr
>I've heard that everyone just uses dcode.fr to solve all of their crypto problems. Shameful, really.
>This is really just a basic Caesar cipher, with a few extra random characters on either side of the flag. Dcode can handle that, right? >:)
>The '{', '}', and '_' characters aren't part of the Caesar cipher, just a-z. As a reminder, all flags start with "utflag{".
Attachment:
* LoooongCaesarCipher.txt
```
Xâu quá to nên mình không thể dán vào đây được.
Mời các bạn download attachment tại https://utctf.live/challenges
```
Solution:
- Ý tưởng chính: So khớp chuỗi (String matching) và Caesar.
- Gọi xâu cần được decrypt trong file LoooongCaesar.Cipher.txt là n, có độ dài N
- Xâu n có 10^6 ký tự bao gồm các ký tự từ 'a' đến 'z', ký tự '{', '}' và '_'.
- Ta có mảng f[] với f[i] là khoảng cách giữa ký tự n[i] và n[i + 1] trong bảng chữ cái theo chiều kim đồng hồ.
- Vì flag ta cần bắt có dạng là utflag{} nên dù quay utflag{} theo cách nào thì f[i] luôn không đổi với i là ký tự thứ i trong xâu. Suy ra f[i] (0 <= i <= 4) là 1 hằng số.
- Bây giờ ta chỉ cần tìm xâu con trong n có dạng "n[i-5]n[i-4]n[i-3]n[i-2]n[i-1]n[i]{ " thỏa điều kiện (giống như so khớp chuỗi) rồi ném vào Caesar Decrypt Tool bất ký nào đó để tìm ra Flag.
- Độ phúc tạp thuật toán O(n) vì xâu con "utflag" chỉ có độ dài là 6 nên ta có thể dùng thuật trâu để so khớp chuỗi
Script:
``` c++ = 0
#include <bits/stdc++.h>
#define int long long
#define pii pair <int,int>
#define st first
#define nd second
#define vi vector <int>
#define vpii vector <pii>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define FILE ""
using namespace std;
const int oo = 1e18;
const int base = 311;
const int mod = 998244353;
const int N = 1e6 + 6;
using namespace std;
int f[5];
int g[5];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string n = ""
cin >> n; // Nhap xau n tu file LoooongCaesarCipher.txt vao input
f[0] = 25;
f[1] = 12;
f[2] = 6;
f[3] = 15;
f[4] = 6; //hang so mang f cua utflag
//cout << n.size() << "\n";
bool ok;
vector <int> pos;
int d = 0;
for (int i = 6; i < n.size(); i++)
{
ok = true;
if (n[i] == '{') {
for (int j = i - 6; j < i; j++)
{
if (n[j] < 'a' || n[j] > 'z') {ok = false; break;}
}
if (ok == false) continue;
d = 0;
for (int j = i - 6; j < i - 1; j++)
{
if (n[j + 1] < n[j]) g[d] = n[j + 1] + 26 - n[j];
else g[d] = n[j + 1] - n[j];
if (g[d] != f[d]) {ok = false; break;}
d++;
}
if (!ok) continue;
pos.push_back(i - 6);
}
}
//for (auto j : pos) cout << j << " "; cout << "\n";
int x = pos[0];
for (int i = x; i < x + 6; i++) {cout << n[i]; d = i;}
d++;
while (n[d] != '}') {
cout << n[d]; d++;
}
cout << n[d];
return 0;
}
/*
From Benq:
int overflow?
array bounds?
Special Cases (n = 1?)
Do something instead of nothing and stay organized
WRITE STUFF DOWN
DON'T GET STUCK ON ONE APPROACH
*/
```
Output: `cbntio{zqx_lkwlm}`
Quay Caesar cái output là sẽ ra flag.
-> Flag: `utflag{rip_dcode}`
## bits_and_pieces
>I really really like RSA, so implemented it myself <3.
>A two parter.
Attachment:
* vals.txt
```
n1: 16895844090302140592659203092326754397916615877156418083775983326567262857434286784352755691231372524046947817027609871339779052340298851455825343914565349651333283551138205456284824077873043013595313773956794816682958706482754685120090750397747015038669047713101397337825418638859770626618854997324831793483659910322937454178396049671348919161991562332828398316094938835561259917841140366936226953293604869404280861112141284704018480497443189808649594222983536682286615023646284397886256209485789545675225329069539408667982428192470430204799653602931007107335558965120815430420898506688511671241705574335613090682013
e1: 65537
c1: 7818321254750334008379589501292325137682074322887683915464861106561934924365660251934320703022566522347141167914364318838415147127470950035180892461318743733126352087505518644388733527228841614726465965063829798897019439281915857574681062185664885100301873341937972872093168047018772766147350521571412432577721606426701002748739547026207569446359265024200993747841661884692928926039185964274224841237045619928248330951699007619244530879692563852129885323775823816451787955743942968401187507702618237082254283484203161006940664144806744142758756632646039371103714891470816121641325719797534020540250766889785919814382
n2: 22160567763948492895090996477047180485455524932702696697570991168736807463988465318899280678030104758714228331712868417831523511943197686617200545714707332594532611440360591874484774459472586464202240208125663048882939144024375040954148333792401257005790372881106262295967972148685076689432551379850079201234407868804450612865472429316169948404048708078383285810578598637431494164050174843806035033795105585543061957794162099125273596995686952118842090801867908842775373362066408634559153339824637727686109642585264413233583449179272399592842009933883647300090091041520319428330663770540635256486617825262149407200317
e2: 65537
c2: 19690520754051173647211685164072637555800784045910293368304706863370317909953687036313142136905145035923461684882237012444470624603324950525342723531350867347220681870482876998144413576696234307889695564386378507641438147676387327512816972488162619290220067572175960616418052216207456516160477378246666363877325851823689429475469383672825775159901117234555363911938490115559955086071530659273866145507400856136591391884526718884267990093630051614232280554396776513566245029154917966361698708629039129727327128483243363394841238956869151344974086425362274696045998136718784402364220587942046822063205137520791363319144
n3: 30411521910612406343993844830038303042143033746292579505901870953143975096282414718336718528037226099433670922614061664943892535514165683437199134278311973454116349060301041910849566746140890727885805721657086881479617492719586633881232556353366139554061188176830768575643015098049227964483233358203790768451798571704097416317067159175992894745746804122229684121275771877235870287805477152050742436672871552080666302532175003523693101768152753770024596485981429603734379784791055870925138803002395176578318147445903935688821423158926063921552282638439035914577171715576836189246536239295484699682522744627111615899081
e3: 65537
c3: 17407076170882273876432597038388758264230617761068651657734759714156681119134231664293550430901872572856333330745780794113236587515588367725879684954488698153571665447141528395185542787913364717776209909588729447283115651585815847333568874548696816813748100515388820080812467785181990042664564706242879424162602753729028187519433639583471983065246575409341038859576101783940398158000236250734758549527625716150775997198493235465480875148169558815498752869321570202908633179473348243670372581519248414555681834596365572626822309814663046580083035403339576751500705695598043247593357230327746709126221695232509039271637
```
Solution:
- Ý tưởng chính: RSA, number theory.
- N1 là tích của 2 số nguyên tố gần kề nhau, ta có thể phân tích N1 = P1 * Q1 thông qua Fermat Attack Decryption.
- N2 và N3 có ước chung lớn nhất là một số nguyên tố lớn -> đặt P2 = P3 = GCD(N2, N3); Q2 = N2 / P2; Q3 = N3 / P3;
- Giải RSA N1, N2 và N3, ghép 3 phần lại là ta được flag.
Script:
``` python = 0
from Crypto.Util.number import *
import math
n1 = 16895844090302140592659203092326754397916615877156418083775983326567262857434286784352755691231372524046947817027609871339779052340298851455825343914565349651333283551138205456284824077873043013595313773956794816682958706482754685120090750397747015038669047713101397337825418638859770626618854997324831793483659910322937454178396049671348919161991562332828398316094938835561259917841140366936226953293604869404280861112141284704018480497443189808649594222983536682286615023646284397886256209485789545675225329069539408667982428192470430204799653602931007107335558965120815430420898506688511671241705574335613090682013
n2 = 22160567763948492895090996477047180485455524932702696697570991168736807463988465318899280678030104758714228331712868417831523511943197686617200545714707332594532611440360591874484774459472586464202240208125663048882939144024375040954148333792401257005790372881106262295967972148685076689432551379850079201234407868804450612865472429316169948404048708078383285810578598637431494164050174843806035033795105585543061957794162099125273596995686952118842090801867908842775373362066408634559153339824637727686109642585264413233583449179272399592842009933883647300090091041520319428330663770540635256486617825262149407200317
n3 = 30411521910612406343993844830038303042143033746292579505901870953143975096282414718336718528037226099433670922614061664943892535514165683437199134278311973454116349060301041910849566746140890727885805721657086881479617492719586633881232556353366139554061188176830768575643015098049227964483233358203790768451798571704097416317067159175992894745746804122229684121275771877235870287805477152050742436672871552080666302532175003523693101768152753770024596485981429603734379784791055870925138803002395176578318147445903935688821423158926063921552282638439035914577171715576836189246536239295484699682522744627111615899081
e = 65537
c1 = 7818321254750334008379589501292325137682074322887683915464861106561934924365660251934320703022566522347141167914364318838415147127470950035180892461318743733126352087505518644388733527228841614726465965063829798897019439281915857574681062185664885100301873341937972872093168047018772766147350521571412432577721606426701002748739547026207569446359265024200993747841661884692928926039185964274224841237045619928248330951699007619244530879692563852129885323775823816451787955743942968401187507702618237082254283484203161006940664144806744142758756632646039371103714891470816121641325719797534020540250766889785919814382
c2 = 19690520754051173647211685164072637555800784045910293368304706863370317909953687036313142136905145035923461684882237012444470624603324950525342723531350867347220681870482876998144413576696234307889695564386378507641438147676387327512816972488162619290220067572175960616418052216207456516160477378246666363877325851823689429475469383672825775159901117234555363911938490115559955086071530659273866145507400856136591391884526718884267990093630051614232280554396776513566245029154917966361698708629039129727327128483243363394841238956869151344974086425362274696045998136718784402364220587942046822063205137520791363319144
c3 = 17407076170882273876432597038388758264230617761068651657734759714156681119134231664293550430901872572856333330745780794113236587515588367725879684954488698153571665447141528395185542787913364717776209909588729447283115651585815847333568874548696816813748100515388820080812467785181990042664564706242879424162602753729028187519433639583471983065246575409341038859576101783940398158000236250734758549527625716150775997198493235465480875148169558815498752869321570202908633179473348243670372581519248414555681834596365572626822309814663046580083035403339576751500705695598043247593357230327746709126221695232509039271637
g = 175136386393724074897068211302311758514344898633187862983126380556807924872210372704023620020763131468811275018725481764101835410780850364387004844957680252860643364609959757601263568806626614487575229052115194838589297358422557307359118854093864998895206960681533165623745478696564104830629591040860031236467
q2 = n2 // g
q3 = n3 // g
p = 129984014749130366259742130443330376923069118727641845190136006048911945242427603092160936004682857611235008521722596025476170673607376869837675885556290582081941522328978811710862857253777650447221864279732376499043513950683086803379743964370215090077032772967632331576620201195241241611325672953583711295127
q = n1 // p
phi = (p - 1) * (q - 1)
phi2 = (g - 1) * (q2 - 1)
phi3 = (g - 1) * (q3 - 1)
d = inverse(e, phi)
d2 = inverse(e, phi2)
d3 = inverse(e, phi3)
m1 = pow(c1, d, n1)
m2 = pow(c2, d2, n2)
m3 = pow(c3, d3, n3)
print (long_to_bytes(m1))
print (long_to_bytes(m2))
print (long_to_bytes(m3))
```
Flag: `utflag{oh_no_it_didnt_work_</3_i_guess_i_can_just_use_standard_libraries_in_the_future}`
## Cryptordle
>Just guess the word in 6 tries. What do you mean it's hard?
Attachment
* main.py
``` python = 0
#!/usr/bin/env python3
import random
wordlist = open('/src/wordlist.txt', 'r').read().split('\n')
for word in wordlist:
assert len(word) == 5
for letter in word:
assert letter in 'abcdefghijklmnopqrstuvwxyz'
for attempt in range(3):
answer = random.choice(wordlist)
num_guesses = 0
while True:
num_guesses += 1
print("What's your guess?")
guess = input().lower()
assert len(guess) == 5
for letter in guess:
assert letter in 'abcdefghijklmnopqrstuvwxyz'
if guess == answer:
break
response = 1
for x in range(5):
a = ord(guess[x]) - ord('a')
b = ord(answer[x]) - ord('a')
response = (response * (a-b)) % 31
print(response)
if num_guesses > 6:
print("Sorry, you took more than 6 tries. No flag for you :(")
exit()
else:
print("Good job! Onward...")
if num_guesses <= 6:
print('Nice! You got it :) Have a flag:')
flag = open('/src/flag.txt', 'r').read()
print(flag)
else:
print("Sorry, you took more than 6 tries. No flag for you :(")
```
Solution:
- Ý tưởng chính: Interactive, Brute Force, String
- Ta sẽ bắt được flag sau 3 lần đoán từ chính xác
- Mỗi lượt từ, ta sẽ có 6 lần đoán, ở đây thì mình sẽ tận dụng 5 lần đoán đầu tiên để tìm 5 ký tự sau đó ghép các ký tự vừa nhặt được thành 1 từ tiếng anh có nghĩa và nhập đáp án đó tại lần đoán thứ 6.
- Trong 5 lần đoán đầu tiên, mình sẽ đoán các xâu lần lượt là "aaaaa", "eeeee", "iiiii", "ooooo", "uuuuu" {mình lấy a, e, i, o, u vì đây là 5 nguyên âm trong tiếng anh}
- Sau đó mình sẽ nhập các lần lượt các số tự nhiên mà máy phản hồi vào input của chương trình C++ {Viết bởi dpduy123} dưới đây và ta sẽ nhặt được 5 ký tự và sau đó là vấn đề kỹ năng tiếng Anh.
Script:
``` c++ = 0
#include <bits/stdc++.h>
#define int long long
#define pii pair <int,int>
#define st first
#define nd second
#define vi vector <int>
#define vpii vector <pii>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define FILE ""
using namespace std;
const int oo = 1e18;
const int base = 311;
const int mod = 998244353;
const int N = 1e6 + 6;
int n, m, k, d, x;
int b[N], a[N];
string s;
void input()
{
cin >> b[1] >> b[2] >> b[3] >> b[4] >> b[5];
}
void btk(int i)
{
if (i > 5) {
int res = 1;
int res2 = 1;
int res3 = 1;
int res4 = 1;
int res5 = 1;
for (int i = 1; i <= 5; i++)
{
res *= (int) ('a' - 'a') - a[i];
res += 31 * 31;
res %= 31;
res2 *= (int) (('e' - 'a') - a[i]);
res2 += 31 * 31;
res2 %= 31;
res3 *= (int) (('i' - 'a') - a[i]);
res3 += 31 * 31;
res3 %= 31;
res4 *= (int) (('o' - 'a') - a[i]);
res4 += 31 * 31;
res4 %= 31;
res5 *= (int) (('u' - 'a') - a[i]);
res5 += 31 * 31;
res5 %= 31;
}
if (res == b[1] && res2 == b[2] && res3 == b[3] && res4 == b[4] && res5 == b[5]) {
for (int i = 1; i <= 5; i++)
cout << (char) (a[i] + 'a') << ""; cout << "\n";
}
return;
}
for (int j = 0; j <= 24; j++)
{
a[i] = j;
btk(i + 1);
}
}
void solve()
{
btk(1);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
input();
solve();
}
return 0;
}
/*
From Benq:
int overflow?
array bounds?
Special Cases (n = 1?)
Do something instead of nothing and stay organized
WRITE STUFF DOWN
DON'T GET STUCK ON ONE APPROACH
*/
```
Flag:... người đánh máy đã cướp flag của tác giả rồi ;-;
Sign in with Wallet
Connect another wallet