DEV Community: Ignat Korchagin

A Business Idea to Give Away: Fuel Delivery

Ignat Korchagin — Wed, 13 Oct 2021 15:11:23 +0000

It’s like Uber Eats but for car fuel

Recent petrol (or gasoline — for our US readers) crisis in the UK made me wondering if we can introduce new ways of how we refuel our cars. With so many things delivered to our doorsteps in a snap of our fingers (or more accurately, with a tap of our finger on a mobile screen) why car fuel can’t be one of them?

UK fuel shortage revisited

The crisis in the UK is mainly caused not by the lack of the fuel itself, but by a supply chain failure. Shortage of HGV (heavy goods vehicle) drivers is causing many fuel stations to run out of fuel, because they are not refilled in time. This in turn creates an avalanche effect as drivers, seeing many stations closed, begin stockpiling fuel and pushing the demand and consumption even higher.

Even with all the calls from the UK Government not to panic buy, car drivers keep creating lengthy queues at fuel stations and try to fill every available fuel can with petrol or diesel besides their car fuel tank. The market need is apparent here: car drivers want the ability to refuel their cars whenever they want and with whatever amount they want. Anything less is just not tolerated.

Solving the HGV driver shortage

A textbook approach for dealing with unavailable goods/services is to try to find substitutes. HGV drivers are a scarce resource as one needs a special license and training to drive huge trucks especially transporting flammable materials. But unlike cars or containers, for example, fuel is liquid and can be divided into unlimited amount of smaller shipments. So in the end there is no reason why fuel can’t be transported by smaller vehicles with a size of a large van. Of course, these “large vans” have to be adapted for fuel transportation, which might be a big upfront investment. However, that investment might be justifiable for a country-wide venture.

This is where fuel delivery comes into play: sending a fleet of “large vans” instead of a one big HGV to refuel a single petrol station might not be economically feasible. However, it might make sense to do so to cover a whole neighbourhood of potentially distributed customers, who want their fuel delivered to their doorsteps.

Taming the surging fuel demand

Another advantage of fuel home delivery is the ability to somewhat cope with the anxiety of car drivers not getting their fuel in time. As we established above, if drivers don’t get the chance to refill their tanks, when they want — they begin to panic. However, the surging demand can be partially solved not only by immediate delivery, but also by a promise to deliver the fuel at a certain time later.

Imagine, you’re a driver needing to get some fuel for your car “soon” and you know you might need to spend some time finding a petrol station as well as you’re facing some hours in the actual queue at the station. If you had an alternative — an app, which allows you to book a fuel delivery for later today, you would probably seriously consider it.

By having some kind of a slot system such booking app can flatten surging demand over a longer period of time as well as distribute consumption more evenly across space instead of all drivers in a highly populated area going to a single closest petrol station all at once. And by providing advanced bookings we mostly solve the panic buying problem, as being able to prebook fuel delivery reduces the drivers’ anxiety.

Will this venture be useful, when the crisis passes?

Probably. Many people are willing to pay extra to have their food delivered to their doorsteps. And we are not talking about fancy restaurant dishes, but also low-end fast food chains and coffee shops. Most of the time petrol stations are located close to shopping malls and food places, so if people are not willing to go themselves to food courts, they might reconsider wasting their time going to petrol station, should they get an alternative.

It is worth noting that even if fuel home delivery ends up not being viable, the fuel booking system may be useful on its own and probably requires much less upfront investment. How many times, even before the crisis, did you show up at a petrol station before the weekend or holidays just to find yourself in a queue, because everyone else did the same? What if instead you could just book a time slot at the station in the same way we book doctor appointments, and get your fuel without any waiting or other inconvenience? Definitely, sounds more appealing to me…

Is the idea new?

Not really. There are emergency or breakdown services available, which would also deliver small amounts of fuel in case of need. However, their use-case is limited to emergency road assistance.

Surprisingly, there was a startup in the UK — Zebra Fuel, which attempted exactly this idea in the past, however they ceased their operations in 2019. Somehow I’ve never heard about them previously, so it seems they never reached the viral marketing point. And it is not clear, why they pulled out of this seemingly successful business. Perhaps, the timing wasn’t just right and the current fuel crisis would have given them a rocket boost.

Do you think this business is viable? Why/why not? (Leave a comment)

How to execute an object file: Part 3

Ignat Korchagin — Mon, 13 Sep 2021 16:21:53 +0000

Dealing with external libraries

This is a repost of my post from the Cloudflare Blog

In the part 2 of our series we learned how to process relocations in object files in order to properly wire up internal dependencies in the code. In this post we will look into what happens if the code has external dependencies — that is, it tries to call functions from external libraries. As before, we will be building upon the code from part 2. Let's add another function to our toy object file:

obj.c:

#include <stdio.h>

...

void say_hello(void)
{
    puts("Hello, world!");
}

In the above scenario our say_hello function now depends on the puts function from the C standard library. To try it out we also need to modify our loader to import the new function and execute it:

loader.c:

...

static void execute_funcs(void)
{
    /* pointers to imported functions */
    int (*add5)(int);
    int (*add10)(int);
    const char *(*get_hello)(void);
    int (*get_var)(void);
    void (*set_var)(int num);
    void (*say_hello)(void);

...

    say_hello = lookup_function("say_hello");
    if (!say_hello) {
        fputs("Failed to find say_hello function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing say_hello...");
    say_hello();
}
...

Let's run it:

$ gcc -c obj.c
$ gcc -o loader loader.c
$ ./loader
No runtime base address for section

Seems something went wrong when the loader tried to process relocations, so let's check the relocations table:

$ readelf --relocs obj.o

Relocation section '.rela.text' at offset 0x3c8 contains 7 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000a00000004 R_X86_64_PLT32    0000000000000000 add5 - 4
00000000002d  000a00000004 R_X86_64_PLT32    0000000000000000 add5 - 4
00000000003a  000500000002 R_X86_64_PC32     0000000000000000 .rodata - 4
000000000046  000300000002 R_X86_64_PC32     0000000000000000 .data - 4
000000000058  000300000002 R_X86_64_PC32     0000000000000000 .data - 4
000000000066  000500000002 R_X86_64_PC32     0000000000000000 .rodata - 4
00000000006b  001100000004 R_X86_64_PLT32    0000000000000000 puts - 4
...

The compiler generated a relocation for the puts invocation. The relocation type is R_X86_64_PLT32 and our loader already knows how to process these, so the problem is elsewhere. The above entry shows that the relocation references 17th entry (0x11 in hex) in the symbol table, so let's check that:

$ readelf --symbols obj.o

Symbol table '.symtab' contains 18 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS obj.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
     6: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    3 var
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    7
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    8
     9: 0000000000000000     0 SECTION LOCAL  DEFAULT    6
    10: 0000000000000000    15 FUNC    GLOBAL DEFAULT    1 add5
    11: 000000000000000f    36 FUNC    GLOBAL DEFAULT    1 add10
    12: 0000000000000033    13 FUNC    GLOBAL DEFAULT    1 get_hello
    13: 0000000000000040    12 FUNC    GLOBAL DEFAULT    1 get_var
    14: 000000000000004c    19 FUNC    GLOBAL DEFAULT    1 set_var
    15: 000000000000005f    19 FUNC    GLOBAL DEFAULT    1 say_hello
    16: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
    17: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND puts

Oh! The section index for the puts function is UND (essentially 0 in the code), which makes total sense: unlike previous symbols, puts is an external dependency, and it is not implemented in our obj.o file. Therefore, it can't be a part of any section within obj.o.
So how do we resolve this relocation? We need to somehow point the code to jump to a puts implementation. Our loader actually already has access to the C library puts function (because it is written in C and we've used puts in the loader code itself already), but technically it doesn't have to be the C library puts, just some puts implementation. For completeness, let's implement our own custom puts function in the loader, which is just a decorator around the C library puts:

loader.c:

...

/* external dependencies for obj.o */
static int my_puts(const char *s)
{
    puts("my_puts executed");
    return puts(s);
}
...

Now that we have a puts implementation (and thus its runtime address) we should just write logic in the loader to resolve the relocation by instructing the code to jump to the correct function. However, there is one complication: in part 2 of our series, when we processed relocations for constants and global variables, we learned we're mostly dealing with 32-bit relative relocations and that the code or data we're referencing needs to be no more than 2147483647 (0x7fffffff in hex) bytes away from the relocation itself. R_X86_64_PLT32 is also a 32-bit relative relocation, so it has the same requirements, but unfortunately we can't reuse the trick from part 2 as our my_puts function is part of the loader itself and we don't have control over where in the address space the operating system places the loader code.

Luckily, we don't have to come up with any new solutions and can just borrow the approach used in shared libraries.

Exploring PLT/GOT

Real world ELF executables and shared libraries have the same problem: often executables have dependencies on shared libraries and shared libraries have dependencies on other shared libraries. And all of the different pieces of a complete runtime program may be mapped to random ranges in the process address space. When a shared library or an ELF executable is linked together, the linker enumerates all the external references and creates two or more additional sections (for a refresher on ELF sections check out the part 1 of our series) in the ELF file. The two mandatory ones are the Procedure Linkage Table (PLT) and the Global Offset Table (GOT).

We will not deep-dive into specifics of the standard PLT/GOT implementation as there are many other great resources online, but in a nutshell PLT/GOT is just a jumptable for external code. At the linking stage the linker resolves all external 32-bit relative relocations with respect to a locally generated PLT/GOT table. It can do that, because this table would become part of the final ELF file itself, so it will be "close" to the main code, when the file is mapped into memory at runtime. Later, at runtime the dynamic loader populates PLT/GOT tables for every loaded ELF file (both the executable and the shared libraries) with the runtime addresses of all the dependencies. Eventually, when the program code calls some external library function, the CPU "jumps" through the local PLT/GOT table to the final code:

Why do we need two ELF sections to implement one jumptable you may ask? Well, because real world PLT/GOT is a bit more complex than described above. Turns out resolving all external references at runtime may significantly slow down program startup time, so symbol resolution is implemented via a "lazy approach": a reference is resolved by the dynamic loader only when the code actually tries to call a particular function. If the main application code never calls a library function, that reference will never be resolved.

Implementing a simplified PLT/GOT

For learning and demonstrative purposes though we will not be reimplementing a full-blown PLT/GOT with lazy resolution, but a simple jumptable, which resolves external references when the object file is loaded and parsed. First of all we need to know the size of the table: for ELF executables and shared libraries the linker will count the external references at link stage and create appropriately sized PLT and GOT sections. Because we are dealing with raw object files we would have to do another pass over the .rela.text section and count all the relocations, which point to an entry in the symbol table with undefined section index (or 0 in code). Let's add a function for this and store the number of external references in a global variable:

loader.c:

...

/* number of external symbols in the symbol table */
static int num_ext_symbols = 0;
...
static void count_external_symbols(void)
{
    const Elf64_Shdr *rela_text_hdr = lookup_section(".rela.text");
    if (!rela_text_hdr) {
        fputs("Failed to find .rela.text\n", stderr);
        exit(ENOEXEC);
    }

    int num_relocations = rela_text_hdr->sh_size / rela_text_hdr->sh_entsize;
    const Elf64_Rela *relocations = (Elf64_Rela *)(obj.base + rela_text_hdr->sh_offset);

    for (int i = 0; i < num_relocations; i++) {
        int symbol_idx = ELF64_R_SYM(relocations[i].r_info);

        /* if there is no section associated with a symbol, it is probably
         * an external reference */
        if (symbols[symbol_idx].st_shndx == SHN_UNDEF)
            num_ext_symbols++;
    }
}
...

This function is very similar to our do_text_relocations function. Only instead of actually performing relocations it just counts the number of external symbol references.

Next we need to decide the actual size in bytes for our jumptable. num_ext_symbols has the number of external symbol references in the object file, but how many bytes per symbol to allocate? To figure this out we need to design our jumptable format. As we established above, in its simple form our jumptable should be just a collection of unconditional CPU jump instructions — one for each external symbol. However, unfortunately modern x64 CPU architecture does not provide a jump instruction, where an address pointer can be a direct operand. Instead, the jump address needs to be stored in memory somewhere "close" — that is within 32-bit offset — and the offset is the actual operand. So, for each external symbol we need to store the jump address (64 bits or 8 bytes on a 64-bit CPU system) and the actual jump instruction with an offset operand (6 bytes for x64 architecture). We can represent an entry in our jumptable with the following C structure:

loader.c:

...

struct ext_jump {
    /* address to jump to */
    uint8_t *addr;
    /* unconditional x64 JMP instruction */
    /* should always be {0xff, 0x25, 0xf2, 0xff, 0xff, 0xff} */
    /* so it would jump to an address stored at addr above */
    uint8_t instr[6];
};

struct ext_jump *jumptable;
...

We've also added a global variable to store the base address of the jumptable, which will be allocated later. Notice that with the above approach the actual jump instruction will always be constant for every external symbol. Since we allocate a dedicated entry for each external symbol with this structure, the addr member would always be at the same offset from the end of the jump instruction in instr: -14 bytes or 0xfffffff2 in hex for a 32-bit operand. So instr will always be {0xff, 0x25, 0xf2, 0xff, 0xff, 0xff}: 0xff and 0x25 is the encoding of the x64 jump instruction and its modifier and 0xfffffff2 is the operand offset in little-endian format.

Now that we have defined the entry format for our jumptable, we can allocate and populate it when parsing the object file. First of all, let's not forget to call our new count_external_symbols function from the parse_obj to populate num_ext_symbols (it has to be done before we allocate the jumptable):

loader.c:

...

static void parse_obj(void)
{
...

    count_external_symbols();

    /* allocate memory for `.text`, `.data` and `.rodata` copies rounding up each section to whole pages */
    text_runtime_base = mmap(NULL, page_align(text_hdr->sh_size)...
...
}

Next we need to allocate memory for the jumptable and store the pointer in the jumptable global variable for later use. Just a reminder that in order to resolve 32-bit relocations from the .text section to this table, it has to be "close" in memory to the main code. So we need to allocate it in the same mmap call as the rest of the object sections. Since we defined the table's entry format in struct ext_jump and have num_ext_symbols, the size of the table would simply be sizeof(struct ext_jump) * num_ext_symbols:

loader.c:

...

static void parse_obj(void)
{
...

    count_external_symbols();

    /* allocate memory for `.text`, `.data` and `.rodata` copies and the jumptable for external symbols, rounding up each section to whole pages */
    text_runtime_base = mmap(NULL, page_align(text_hdr->sh_size) + \
                                   page_align(data_hdr->sh_size) + \
                                   page_align(rodata_hdr->sh_size) + \
                                   page_align(sizeof(struct ext_jump) * num_ext_symbols),
                                   PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (text_runtime_base == MAP_FAILED) {
        perror("Failed to allocate memory");
        exit(errno);
    }

...
    rodata_runtime_base = data_runtime_base + page_align(data_hdr->sh_size);
    /* jumptable will come after .rodata */
    jumptable = (struct ext_jump *)(rodata_runtime_base + page_align(rodata_hdr->sh_size));

...
}
...

Finally, because the CPU will actually be executing the jump instructions from our instr fields from the jumptable, we need to mark this memory readonly and executable (after do_text_relocations earlier in this function has completed):

loader.c:

...

static void parse_obj(void)
{
...

    do_text_relocations();

...

    /* make the jumptable readonly and executable */
    if (mprotect(jumptable, page_align(sizeof(struct ext_jump) * num_ext_symbols), PROT_READ | PROT_EXEC)) {
        perror("Failed to make the jumptable executable");
        exit(errno);
    }
}
...

At this stage we have our jumptable allocated and usable — all is left to do is to populate it properly. We’ll do this by improving the do_text_relocations implementation to handle the case of external symbols. The No runtime base address for section error from the beginning of this post is actually caused by this line in do_text_relocations:

loader.c:

...

static void do_text_relocations(void)
{
...
    for (int i = 0; i < num_relocations; i++) {
...
        /* symbol, with respect to which the relocation is performed */
        uint8_t *symbol_address = = section_runtime_base(&sections[symbols[symbol_idx].st_shndx]) + symbols[symbol_idx].st_value;
...
}
...

Currently we try to determine the runtime symbol address for the relocation by looking up the symbol's section runtime address and adding the symbol's offset. But we have established above that external symbols do not have an associated section, so their handling needs to be a special case. Let's update the implementation to reflect this:

loader.c:

...

static void do_text_relocations(void)
{
...
    for (int i = 0; i < num_relocations; i++) {
...
        /* symbol, with respect to which the relocation is performed */
        uint8_t *symbol_address;

        /* if this is an external symbol */
        if (symbols[symbol_idx].st_shndx == SHN_UNDEF) {
            static int curr_jmp_idx = 0;

            /* get external symbol/function address by name */
            jumptable[curr_jmp_idx].addr = lookup_ext_function(strtab +  symbols[symbol_idx].st_name);

            /* x64 unconditional JMP with address stored at -14 bytes offset */
            /* will use the address stored in addr above */
            jumptable[curr_jmp_idx].instr[0] = 0xff;
            jumptable[curr_jmp_idx].instr[1] = 0x25;
            jumptable[curr_jmp_idx].instr[2] = 0xf2;
            jumptable[curr_jmp_idx].instr[3] = 0xff;
            jumptable[curr_jmp_idx].instr[4] = 0xff;
            jumptable[curr_jmp_idx].instr[5] = 0xff;

            /* resolve the relocation with respect to this unconditional JMP */
            symbol_address = (uint8_t *)(&jumptable[curr_jmp_idx].instr);

            curr_jmp_idx++;
        } else {
            symbol_address = section_runtime_base(&sections[symbols[symbol_idx].st_shndx]) + symbols[symbol_idx].st_value;
        }
...
}
...

If a relocation symbol does not have an associated section, we consider it external and call a helper function to lookup the symbol's runtime address by its name. We store this address in the next available jumptable entry, populate the x64 jump instruction with our fixed operand and store the address of the instruction in the symbol_address variable. Later, the existing code in do_text_relocations will resolve the .text relocation with respect to the address in symbol_address in the same way it does for local symbols in part 2 of our series.

The only missing bit here now is the implementation of the newly introduced lookup_ext_function helper. Real world loaders may have complicated logic on how to find and resolve symbols in memory at runtime. But for the purposes of this article we'll provide a simple naive implementation, which can only resolve the puts function:

loader.c:

...

static void *lookup_ext_function(const char *name)
{
    size_t name_len = strlen(name);

    if (name_len == strlen("puts") && !strcmp(name, "puts"))
        return my_puts;

    fprintf(stderr, "No address for function %s\n", name);
    exit(ENOENT);
}
...

Notice though that because we control the loader logic we are free to implement resolution as we please. In the above case we actually "divert" the object file to use our own "custom" my_puts function instead of the C library one. Let's recompile the loader and see if it works:

$ gcc -o loader loader.c
$ ./loader
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52
Executing get_hello...
get_hello() = Hello, world!
Executing get_var...
get_var() = 5
Executing set_var(42)...
Executing get_var again...
get_var() = 42
Executing say_hello...
my_puts executed
Hello, world!

Hooray! We not only fixed our loader to handle external references in object files — we have also learned how to "hook" any such external function call and divert the code to a custom implementation, which might be useful in some cases, like malware research.

As in the previous posts, the complete source code from this post is available on GitHub.

How to execute an object file: Part 2

Ignat Korchagin — Fri, 02 Apr 2021 20:56:32 +0000

Handling relocations

This is a repost of my post from the Cloudflare Blog

In the previous post, we learned how to parse an object file and import and execute some functions from it. However, the functions in our toy object file were simple and self-contained: they computed their output solely based on their inputs and didn't have any external code or data dependencies. In this post we will build upon the code from part 1, exploring additional steps needed to handle code with some dependencies.

As an example, we may notice that we can actually rewrite our add10 function using our add5 function:

obj.c:

int add5(int num)
{
    return num + 5;
}

int add10(int num)
{
    num = add5(num);
    return add5(num);
}

Let's recompile the object file and try to use it as a library with our loader program:

$ gcc -c obj.c
$ ./loader
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 42

Whoa! Something is not right here. add5 still produces the correct result, but add10 does not . Depending on your environment and code composition, you may even see the loader program crashing instead of outputting incorrect results. To understand what happened, let's investigate the machine code generated by the compiler. We can do that by asking the objdump tool to disassemble the .text section from our obj.o:

$ objdump --disassemble --section=.text obj.o

obj.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <add5>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   8b 45 fc                mov    -0x4(%rbp),%eax
   a:   83 c0 05                add    $0x5,%eax
   d:   5d                      pop    %rbp
   e:   c3                      retq

000000000000000f <add10>:
   f:   55                      push   %rbp
  10:   48 89 e5                mov    %rsp,%rbp
  13:   48 83 ec 08             sub    $0x8,%rsp
  17:   89 7d fc                mov    %edi,-0x4(%rbp)
  1a:   8b 45 fc                mov    -0x4(%rbp),%eax
  1d:   89 c7                   mov    %eax,%edi
  1f:   e8 00 00 00 00          callq  24 <add10+0x15>
  24:   89 45 fc                mov    %eax,-0x4(%rbp)
  27:   8b 45 fc                mov    -0x4(%rbp),%eax
  2a:   89 c7                   mov    %eax,%edi
  2c:   e8 00 00 00 00          callq  31 <add10+0x22>
  31:   c9                      leaveq
  32:   c3                      retq

You don't have to understand the full output above. There are only two relevant lines here: 1f: e8 00 00 00 00 and 2c: e8 00 00 00 00. These correspond to the two add5 function invocations we have in the source code and objdump even conveniently decodes the instruction for us as callq. By looking at descriptions of the callq instruction online (like this one), we can further see we're dealing with a "near, relative call", because of the 0xe8 prefix:

Call near, relative, displacement relative to next instruction.

According to the description, this variant of the callq instruction consists of 5 bytes: the 0xe8 prefix and a 4-byte (32 bit) argument. This is where "relative" comes from: the argument should contain the “distance” between the function we want to call and the current position — because the way how x86 works this distance is calculated from the next instruction and not our current callq instruction. objdump conveniently outputs each machine instruction's offset in the output above, so we can easily calculate the needed argument. For example, for the first callq instruction (1f: e8 00 00 00 00) the next instruction is at offset 0x24. We know we should be calling the add5 function, which starts at offset 0x0 (beginning of our .text section). So the relative offset is 0x0 - 0x24 = -0x24. Notice, we have a negative argument, because the add5 function is located before our calling instruction, so we would be instructing the CPU to "jump backwards" from its current position. Lastly, we have to remember that negative numbers — at least on x86 systems — are presented by their two's complements, so a 4-byte (32 bit) representation of -0x24 would be 0xffffffdc. In the same way we can calculate the callq argument for the second add5 call: 0x0 - 0x31 = -0x31, two's complement - 0xffffffcf:

It seems the compiler does not generate the right callq arguments for us. We've calculated the expected arguments to be 0xffffffdc and 0xffffffcf, but the compiler has just left 0x00000000 in both places. Let's check first if our expectations are correct by patching our loaded .text copy before trying to execute it:

loader.c:

...

static void parse_obj(void)
{
...
    /* copy the contents of `.text` section from the ELF file */
    memcpy(text_runtime_base, obj.base + text_hdr->sh_offset, text_hdr->sh_size);

    /* the first add5 callq argument is located at offset 0x20 and should be 0xffffffdc:
     * 0x1f is the instruction offset + 1 byte instruction prefix
     */
    *((uint32_t *)(text_runtime_base + 0x1f + 1)) = 0xffffffdc;

    /* the second add5 callq argument is located at offset 0x2d and should be 0xffffffcf */
    *((uint32_t *)(text_runtime_base + 0x2c + 1)) = 0xffffffcf;

    /* make the `.text` copy readonly and executable */
    if (mprotect(text_runtime_base, page_align(text_hdr->sh_size), PROT_READ | PROT_EXEC)) {
...

And now let's test it out:

$ gcc -o loader loader.c 
$ ./loader 
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52

Clearly our monkey-patching helped: add10 executes fine now and produces the correct output. This means our expected callq arguments, which we calculated, are correct. So why did the compiler emit wrong callq arguments?

Relocations

The problem with our toy object file is that both functions are declared with external linkage — the default setting for all functions and global variables in C. And, although both functions are declared in the same file, the compiler is not sure where the add5 code will end up in the target binary. So the compiler avoids making any assumptions and doesn’t calculate the relative offset argument of the callq instructions. Let's verify this by removing our monkey patching and declaring the add5 function as static:

loader.c:

...

    /* the first add5 callq argument is located at offset 0x20 and should be 0xffffffdc:
     * 0x1f is the instruction offset + 1 byte instruction prefix
     */
    /* *((uint32_t *)(text_runtime_base + 0x1f + 1)) = 0xffffffdc; */

    /* the second add5 callq argument is located at offset 0x2d and should be 0xffffffcf */
    /* *((uint32_t *)(text_runtime_base + 0x2c + 1)) = 0xffffffcf; */

...

obj.c:

/* int add5(int num) */
static int add5(int num)
...

Recompiling and disassembling obj.o gives us the following:

$ gcc -c obj.c
$ objdump --disassemble --section=.text obj.o

obj.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <add5>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   8b 45 fc                mov    -0x4(%rbp),%eax
   a:   83 c0 05                add    $0x5,%eax
   d:   5d                      pop    %rbp
   e:   c3                      retq

000000000000000f <add10>:
   f:   55                      push   %rbp
  10:   48 89 e5                mov    %rsp,%rbp
  13:   48 83 ec 08             sub    $0x8,%rsp
  17:   89 7d fc                mov    %edi,-0x4(%rbp)
  1a:   8b 45 fc                mov    -0x4(%rbp),%eax
  1d:   89 c7                   mov    %eax,%edi
  1f:   e8 dc ff ff ff          callq  0 <add5>
  24:   89 45 fc                mov    %eax,-0x4(%rbp)
  27:   8b 45 fc                mov    -0x4(%rbp),%eax
  2a:   89 c7                   mov    %eax,%edi
  2c:   e8 cf ff ff ff          callq  0 <add5>
  31:   c9                      leaveq
  32:   c3                      retq

Because we re-declared the add5 function with internal linkage, the compiler is more confident now and calculates callq arguments correctly (note that x86 systems are little-endian, so multibyte numbers like 0xffffffdc will be represented with least significant byte first). We can double check this by recompiling and running our loader test tool:

$ gcc -o loader loader.c
$ ./loader
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52

Even though the add5 function is declared as static, we can still call it from the loader tool, basically ignoring the fact that it is an "internal" function now. Because of this, the static keyword should not be used as a security feature to hide APIs from potential malicious users.

But let's step back and revert our add5 function in obj.c to the one with external linkage:

obj.c:

int add5(int num)
...

$ gcc -c obj.c
$ ./loader
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 42

As we have established above, the compiler did not compute proper callq arguments for us because it didn't have enough information. But later stages (namely the linker) will have that information, so instead the compiler leaves some clues on how to fix those arguments. These clues — or instructions for the later stages — are called relocations. We can inspect them with our friend, the readelf utility. Let's examine obj.o sections table again:

$ readelf --sections obj.o
There are 12 section headers, starting at offset 0x2b0:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       0000000000000033  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  000001f0
       0000000000000030  0000000000000018   I       9     1     8
  [ 3] .data             PROGBITS         0000000000000000  00000073
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  00000073
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .comment          PROGBITS         0000000000000000  00000073
       000000000000001d  0000000000000001  MS       0     0     1
  [ 6] .note.GNU-stack   PROGBITS         0000000000000000  00000090
       0000000000000000  0000000000000000           0     0     1
  [ 7] .eh_frame         PROGBITS         0000000000000000  00000090
       0000000000000058  0000000000000000   A       0     0     8
  [ 8] .rela.eh_frame    RELA             0000000000000000  00000220
       0000000000000030  0000000000000018   I       9     7     8
  [ 9] .symtab           SYMTAB           0000000000000000  000000e8
       00000000000000f0  0000000000000018          10     8     8
  [10] .strtab           STRTAB           0000000000000000  000001d8
       0000000000000012  0000000000000000           0     0     1
  [11] .shstrtab         STRTAB           0000000000000000  00000250
       0000000000000059  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

We see that the compiler created a new section called .rela.text. By convention, a section with relocations for a section named .foo will be called .rela.foo, so we can see that the compiler created a section with relocations for the .text section. We can examine the relocations further:

$ readelf --relocs obj.o

Relocation section '.rela.text' at offset 0x1f0 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000800000004 R_X86_64_PLT32    0000000000000000 add5 - 4
00000000002d  000800000004 R_X86_64_PLT32    0000000000000000 add5 - 4

Relocation section '.rela.eh_frame' at offset 0x220 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0
000000000040  000200000002 R_X86_64_PC32     0000000000000000 .text + f

Let's ignore the relocations from the .rela.eh_frame section because they are out of scope of this post. Instead, let’s try to understand the relocations from the .rela.text:

Offset column tells us exactly where in the target section (.text in this case) the fix/adjustment is needed. Note that these offsets are exactly the same as in our self-calculated monkey-patching above.
Info is a combined value: the upper 32 bits — only 16 bits are shown in the output above — represent the index of the symbol in the symbol table, with respect to which the relocation is performed. In our example it is 8 and if we run readelf --symbols obj.o we will see that it points to an entry corresponding to the add5 function. The lower 32 bits (4 in our case) is a relocation type (see Type below).
Type describes the relocation type. This is a pseudo-column: readelf actually generates it from the lower 32 bits of the Info field. Different relocation types have different formulas we need to apply to perform the relocation.
Sym. Value may mean different things depending on the relocation type, but most of the time it is the symbol offset with respect to which we perform the relocation. The offset is calculated from the beginning of that symbol’s section.
Addend is a constant we may need to use in the relocation formula. Depending on the relocation type, readelf actually adds the decoded symbol name to the output, so the column name is Sym. Name + Addend above but the actual field stores the addend only.

In a nutshell, these entries tell us that we need to patch the .text section at offsets 0x20 and 0x2d. To calculate what to put there, we need to apply the formula for the R_X86_64_PLT32 relocation type. Searching online, we can find different ELF specifications — like this one — which will tell us how to implement the R_X86_64_PLT32 relocation. The specification mentions that the result of this relocation is word32 — which is what we expect because callq arguments are 32 bit in our case — and the formula we need to apply is L + A - P, where:

L is the address of the symbol, with respect to which the relocation is performed (add5 in our case)
A is the constant addend (4 in our case)
P is the address/offset, where we store the result of the relocation

When the relocation formula references some symbol addresses or offsets, we should use the actual — runtime in our case — addresses in the calculations. For example, we will be using text_runtime_base + 0x2d as P for the second relocation and not just 0x2d. So let's try to implement this relocation logic in our object loader:

loader.c:

...

/* from https://elixir.bootlin.com/linux/v5.11.6/source/arch/x86/include/asm/elf.h#L51 */
#define R_X86_64_PLT32 4

...

static uint8_t *section_runtime_base(const Elf64_Shdr *section)
{
    const char *section_name = shstrtab + section->sh_name;
    size_t section_name_len = strlen(section_name);

    /* we only mmap .text section so far */
    if (strlen(".text") == section_name_len && !strcmp(".text", section_name))
        return text_runtime_base;

    fprintf(stderr, "No runtime base address for section %s\n", section_name);
    exit(ENOENT);
}

static void do_text_relocations(void)
{
    /* we actually cheat here - the name .rela.text is a convention, but not a
     * rule: to figure out which section should be patched by these relocations
     * we would need to examine the rela_text_hdr, but we skip it for simplicity
     */
    const Elf64_Shdr *rela_text_hdr = lookup_section(".rela.text");
    if (!rela_text_hdr) {
        fputs("Failed to find .rela.text\n", stderr);
        exit(ENOEXEC);
    }

    int num_relocations = rela_text_hdr->sh_size / rela_text_hdr->sh_entsize;
    const Elf64_Rela *relocations = (Elf64_Rela *)(obj.base + rela_text_hdr->sh_offset);

    for (int i = 0; i < num_relocations; i++) {
        int symbol_idx = ELF64_R_SYM(relocations[i].r_info);
        int type = ELF64_R_TYPE(relocations[i].r_info);

        /* where to patch .text */
        uint8_t *patch_offset = text_runtime_base + relocations[i].r_offset;
        /* symbol, with respect to which the relocation is performed */
        uint8_t *symbol_address = section_runtime_base(&sections[symbols[symbol_idx].st_shndx]) + symbols[symbol_idx].st_value;

        switch (type)
        {
        case R_X86_64_PLT32:
            /* L + A - P, 32 bit output */
            *((uint32_t *)patch_offset) = symbol_address + relocations[i].r_addend - patch_offset;
            printf("Calculated relocation: 0x%08x\n", *((uint32_t *)patch_offset));
            break;
        }
    }
}

static void parse_obj(void)
{
...

    /* copy the contents of `.text` section from the ELF file */
    memcpy(text_runtime_base, obj.base + text_hdr->sh_offset, text_hdr->sh_size);

    do_text_relocations();

    /* make the `.text` copy readonly and executable */
    if (mprotect(text_runtime_base, page_align(text_hdr->sh_size), PROT_READ | PROT_EXEC)) {

...
}

...

We are now calling the do_text_relocations function before marking our .text copy executable. We have also added some debugging output to inspect the result of the relocation calculations. Let's try it out:

$ gcc -o loader loader.c 
$ ./loader 
Calculated relocation: 0xffffffdc
Calculated relocation: 0xffffffcf
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52

Great! Our imported code works as expected now. By following the relocation hints left for us by the compiler, we've got the same results as in our monkey-patching calculations in the beginning of this post. Our relocation calculations also involved text_runtime_base address, which is not available at compile time. That's why the compiler could not calculate the callq arguments in the first place and had to emit the relocations instead.

Handling constant data and global variables

So far, we have been dealing with object files containing only executable code with no state. That is, the imported functions could compute their output solely based on the inputs. Let's see what happens if we add some constant data and global variables dependencies to our imported code. First, we add some more functions to our obj.o:

obj.c:

...

const char *get_hello(void)
{
    return "Hello, world!";
}

static int var = 5;

int get_var(void)
{
    return var;
}

void set_var(int num)
{
    var = num;
}

get_hello returns a constant string and get_var/set_var get and set a global variable respectively. Next, let's recompile the obj.o and run our loader:

$ gcc -c obj.c
$ ./loader 
Calculated relocation: 0xffffffdc
Calculated relocation: 0xffffffcf
No runtime base address for section .rodata

Looks like our loader tried to process more relocations but could not find the runtime address for .rodata section. Previously, we didn't even have a .rodata section, but it was added now because our obj.o needs somewhere to store the constant string Hello, world!:

$ readelf --sections obj.o
There are 13 section headers, starting at offset 0x478:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000005f  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  00000320
       0000000000000078  0000000000000018   I      10     1     8
  [ 3] .data             PROGBITS         0000000000000000  000000a0
       0000000000000004  0000000000000000  WA       0     0     4
  [ 4] .bss              NOBITS           0000000000000000  000000a4
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .rodata           PROGBITS         0000000000000000  000000a4
       000000000000000d  0000000000000000   A       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  000000b1
       000000000000001d  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  000000ce
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  000000d0
       00000000000000b8  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  00000398
       0000000000000078  0000000000000018   I      10     8     8
  [10] .symtab           SYMTAB           0000000000000000  00000188
       0000000000000168  0000000000000018          11    10     8
  [11] .strtab           STRTAB           0000000000000000  000002f0
       000000000000002c  0000000000000000           0     0     1
  [12] .shstrtab         STRTAB           0000000000000000  00000410
       0000000000000061  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

We also have more .text relocations:

$ readelf --relocs obj.o

Relocation section '.rela.text' at offset 0x320 contains 5 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000a00000004 R_X86_64_PLT32    0000000000000000 add5 - 4
00000000002d  000a00000004 R_X86_64_PLT32    0000000000000000 add5 - 4
00000000003a  000500000002 R_X86_64_PC32     0000000000000000 .rodata - 4
000000000046  000300000002 R_X86_64_PC32     0000000000000000 .data - 4
000000000058  000300000002 R_X86_64_PC32     0000000000000000 .data - 4
...

The compiler emitted three more R_X86_64_PC32 relocations this time. They reference symbols with index 3 and 5, so let's find out what they are:

$ readelf --symbols obj.o

Symbol table '.symtab' contains 15 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS obj.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
     6: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    3 var
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    7
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    8
     9: 0000000000000000     0 SECTION LOCAL  DEFAULT    6
    10: 0000000000000000    15 FUNC    GLOBAL DEFAULT    1 add5
    11: 000000000000000f    36 FUNC    GLOBAL DEFAULT    1 add10
    12: 0000000000000033    13 FUNC    GLOBAL DEFAULT    1 get_hello
    13: 0000000000000040    12 FUNC    GLOBAL DEFAULT    1 get_var
    14: 000000000000004c    19 FUNC    GLOBAL DEFAULT    1 set_var

Entries 3 and 5 don't have any names attached, but they reference something in sections with index 3 and 5 respectively. In the output of the section table above, we can see that the section with index 3 is .data and the section with index 5 is .rodata. For a refresher on the most common sections in an ELF file check out our previous post. To import our newly added code and make it work, we also need to map .data and .rodata sections in addition to the .text section and process these R_X86_64_PC32 relocations.

There is one caveat though. If we check the specification, we'll see that R_X86_64_PC32 relocation produces a 32-bit output similar to the R_X86_64_PLT32 relocation. This means that the "distance" in memory between the patched position in .text and the referenced symbol has to be small enough to fit into a 32-bit value (1 bit for the positive/negative sign and 31 bits for the actual data, so less than 2147483647 bytes). Our loader program uses mmap system call to allocate memory for the object section copies, but mmap may allocate the mapping almost anywhere in the process address space. If we modify the loader program to call mmap for each section separately, we may end up having .rodata or .data section mapped too far away from the .text section and will not be able to process the R_X86_64_PC32 relocations. In other words, we need to ensure that .data and .rodata sections are located relatively close to the .text section at runtime:

One way to achieve that would be to allocate the memory we need for all the sections with one mmap call. Then, we’d break it in chunks and assign proper access permissions to each chunk. Let's modify our loader program to do just that:

loader.c:

...

/* runtime base address of the imported code */
static uint8_t *text_runtime_base;
/* runtime base of the .data section */
static uint8_t *data_runtime_base;
/* runtime base of the .rodata section */
static uint8_t *rodata_runtime_base;

...

static void parse_obj(void)
{
...

    /* find the `.text` entry in the sections table */
    const Elf64_Shdr *text_hdr = lookup_section(".text");
    if (!text_hdr) {
        fputs("Failed to find .text\n", stderr);
        exit(ENOEXEC);
    }

    /* find the `.data` entry in the sections table */
    const Elf64_Shdr *data_hdr = lookup_section(".data");
    if (!data_hdr) {
        fputs("Failed to find .data\n", stderr);
        exit(ENOEXEC);
    }

    /* find the `.rodata` entry in the sections table */
    const Elf64_Shdr *rodata_hdr = lookup_section(".rodata");
    if (!rodata_hdr) {
        fputs("Failed to find .rodata\n", stderr);
        exit(ENOEXEC);
    }

    /* allocate memory for `.text`, `.data` and `.rodata` copies rounding up each section to whole pages */
    text_runtime_base = mmap(NULL, page_align(text_hdr->sh_size) + page_align(data_hdr->sh_size) + page_align(rodata_hdr->sh_size), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (text_runtime_base == MAP_FAILED) {
        perror("Failed to allocate memory");
        exit(errno);
    }

    /* .data will come right after .text */
    data_runtime_base = text_runtime_base + page_align(text_hdr->sh_size);
    /* .rodata will come after .data */
    rodata_runtime_base = data_runtime_base + page_align(data_hdr->sh_size);

    /* copy the contents of `.text` section from the ELF file */
    memcpy(text_runtime_base, obj.base + text_hdr->sh_offset, text_hdr->sh_size);
    /* copy .data */
    memcpy(data_runtime_base, obj.base + data_hdr->sh_offset, data_hdr->sh_size);
    /* copy .rodata */
    memcpy(rodata_runtime_base, obj.base + rodata_hdr->sh_offset, rodata_hdr->sh_size);

    do_text_relocations();

    /* make the `.text` copy readonly and executable */
    if (mprotect(text_runtime_base, page_align(text_hdr->sh_size), PROT_READ | PROT_EXEC)) {
        perror("Failed to make .text executable");
        exit(errno);
    }

    /* we don't need to do anything with .data - it should remain read/write */

    /* make the `.rodata` copy readonly */
    if (mprotect(rodata_runtime_base, page_align(rodata_hdr->sh_size), PROT_READ)) {
        perror("Failed to make .rodata readonly");
        exit(errno);
    }
}

...

Now that we have runtime addresses of .data and .rodata, we can update the relocation runtime address lookup function:

loader.c:

...

static uint8_t *section_runtime_base(const Elf64_Shdr *section)
{
    const char *section_name = shstrtab + section->sh_name;
    size_t section_name_len = strlen(section_name);

    if (strlen(".text") == section_name_len && !strcmp(".text", section_name))
        return text_runtime_base;

    if (strlen(".data") == section_name_len && !strcmp(".data", section_name))
        return data_runtime_base;

    if (strlen(".rodata") == section_name_len && !strcmp(".rodata", section_name))
        return rodata_runtime_base;

    fprintf(stderr, "No runtime base address for section %s\n", section_name);
    exit(ENOENT);
}

And finally we can import and execute our new functions:

loader.c:

...

static void execute_funcs(void)
{
    /* pointers to imported functions */
    int (*add5)(int);
    int (*add10)(int);
    const char *(*get_hello)(void);
    int (*get_var)(void);
    void (*set_var)(int num);

...

    printf("add10(%d) = %d\n", 42, add10(42));

    get_hello = lookup_function("get_hello");
    if (!get_hello) {
        fputs("Failed to find get_hello function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing get_hello...");
    printf("get_hello() = %s\n", get_hello());

    get_var = lookup_function("get_var");
    if (!get_var) {
        fputs("Failed to find get_var function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing get_var...");
    printf("get_var() = %d\n", get_var());

    set_var = lookup_function("set_var");
    if (!set_var) {
        fputs("Failed to find set_var function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing set_var(42)...");
    set_var(42);

    puts("Executing get_var again...");
    printf("get_var() = %d\n", get_var());
}
...

Let's try it out:

$ gcc -o loader loader.c 
$ ./loader 
Calculated relocation: 0xffffffdc
Calculated relocation: 0xffffffcf
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52
Executing get_hello...
get_hello() = ]�UH��
Executing get_var...
get_var() = 1213580125
Executing set_var(42)...
Segmentation fault

Uh-oh! We forgot to implement the new R_X86_64_PC32 relocation type. The relocation formula here is S + A - P. We already know about A and P. As for S (quoting from the spec):

“the value of the symbol whose index resides in the relocation entry"

In our case, it is essentially the same as L for R_X86_64_PLT32. We can just reuse the implementation and remove the debug output in the process:

loader.c:

...

/* from https://elixir.bootlin.com/linux/v5.11.6/source/arch/x86/include/asm/elf.h#L51 */
#define R_X86_64_PC32 2
#define R_X86_64_PLT32 4

...

static void do_text_relocations(void)
{
    /* we actually cheat here - the name .rela.text is a convention, but not a
     * rule: to figure out which section should be patched by these relocations
     * we would need to examine the rela_text_hdr, but we skip it for simplicity
     */
    const Elf64_Shdr *rela_text_hdr = lookup_section(".rela.text");
    if (!rela_text_hdr) {
        fputs("Failed to find .rela.text\n", stderr);
        exit(ENOEXEC);
    }

    int num_relocations = rela_text_hdr->sh_size / rela_text_hdr->sh_entsize;
    const Elf64_Rela *relocations = (Elf64_Rela *)(obj.base + rela_text_hdr->sh_offset);

    for (int i = 0; i < num_relocations; i++) {
        int symbol_idx = ELF64_R_SYM(relocations[i].r_info);
        int type = ELF64_R_TYPE(relocations[i].r_info);

        /* where to patch .text */
        uint8_t *patch_offset = text_runtime_base + relocations[i].r_offset;
        /* symbol, with respect to which the relocation is performed */
        uint8_t *symbol_address = section_runtime_base(&sections[symbols[symbol_idx].st_shndx]) + symbols[symbol_idx].st_value;

        switch (type)
        {
        case R_X86_64_PC32:
            /* S + A - P, 32 bit output, S == L here */
        case R_X86_64_PLT32:
            /* L + A - P, 32 bit output */
            *((uint32_t *)patch_offset) = symbol_address + relocations[i].r_addend - patch_offset;
            break;
        }
    }
}

...

Now we should be done. Another try:

$ gcc -o loader loader.c 
$ ./loader 
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52
Executing get_hello...
get_hello() = Hello, world!
Executing get_var...
get_var() = 5
Executing set_var(42)...
Executing get_var again...
get_var() = 42

This time we can successfully import functions that reference static constant data and global variables. We can even manipulate the object file’s internal state through the defined accessor interface. As before, the complete source code for this post is available on GitHub.

In the next post, we will look into importing and executing object code with references to external libraries. Stay tuned!

How to execute an object file: Part 1

Ignat Korchagin — Mon, 08 Mar 2021 21:21:03 +0000

Calling a simple function without linking

This is a repost of my post from the Cloudflare Blog

When we write software using a high-level compiled programming language, there are usually a number of steps involved in transforming our source code into the final executable binary:

First, our source files are compiled by a compiler translating the high-level programming language into machine code. The output of the compiler is a number of object files. If the project contains multiple source files, we usually get as many object files. The next step is the linker: since the code in different object files may reference each other, the linker is responsible for assembling all these object files into one big program and binding these references together. The output of the linker is usually our target executable, so only one file.

However, at this point, our executable might still be incomplete. These days, most executables on Linux are dynamically linked: the executable itself does not have all the code it needs to run a program. Instead it expects to "borrow" part of the code at runtime from shared libraries for some of its functionality:

This process is called runtime linking: when our executable is being started, the operating system will invoke the dynamic loader, which should find all the needed libraries, copy/map their code into our target process address space, and resolve all the dependencies our code has on them.

One interesting thing to note about this overall process is that we get the executable machine code directly from step 1 (compiling the source code), but if any of the later steps fail, we still can't execute our program. So, in this series of blog posts we will investigate if it is possible to execute machine code directly from object files skipping all the later steps.

Why would we want to execute an object file?

There may be many reasons. Perhaps we're writing an open-source replacement for a proprietary Linux driver or an application, and want to compare if the behaviour of some code is the same. Or we have a piece of a rare, obscure program and we can't link to it, because it was compiled with a rare, obscure compiler. Maybe we have a source file, but cannot create a full featured executable, because of the missing build time or runtime dependencies. Malware analysis, code from a different operating system etc - all these scenarios may put us in a position, where either linking is not possible or the runtime environment is not suitable.

A simple toy object file

For the purposes of this article, let's create a simple toy object file, so we can use it in our experiments:

obj.c:

int add5(int num)
{
    return num + 5;
}

int add10(int num)
{
    return num + 10;
}

Our source file contains only 2 functions, add5 and add10, which adds 5 or 10 respectively to the only input parameter. It's a small but fully functional piece of code, and we can easily compile it into an object file:

$ gcc -c obj.c 
$ ls
obj.c  obj.o

Loading an object file into the process memory

Now we will try to import the add5 and add10 functions from the object file and execute them. When we talk about executing an object file, we mean using an object file as some sort of a library. As we learned above, when we have an executable that utilises external shared libraries, the dynamic loader loads these libraries into the process address space for us. With object files, however, we have to do this manually, because ultimately we can't execute machine code that doesn't reside in the operating system's RAM. So, to execute object files we still need some kind of a wrapper program:

loader.c:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

static void load_obj(void)
{
    /* load obj.o into memory */
}

static void parse_obj(void)
{
    /* parse an object file and find add5 and add10 functions */
}

static void execute_funcs(void)
{
    /* execute add5 and add10 with some inputs */
}

int main(void)
{
    load_obj();
    parse_obj();
    execute_funcs();

    return 0;
}

Above is a self-contained object loader program with some functions as placeholders. We will be implementing these functions (and adding more) in the course of this post.

First, as we established already, we need to load our object file into the process address space. We could just read the whole file into a buffer, but that would not be very efficient. Real-world object files might be big, but as we will see later, we don't need all of the object's file contents. So it is better to mmap the file instead: this way the operating system will lazily read the parts from the file we need at the time we need them. Let's implement the load_obj function:

loader.c:

...
/* for open(2), fstat(2) */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

/* for close(2), fstat(2) */
#include <unistd.h>

/* for mmap(2) */
#include <sys/mman.h>

/* parsing ELF files */
#include <elf.h>

/* for errno */
#include <errno.h>

typedef union {
    const Elf64_Ehdr *hdr;
    const uint8_t *base;
} objhdr;

/* obj.o memory address */
static objhdr obj;

static void load_obj(void)
{
    struct stat sb;

    int fd = open("obj.o", O_RDONLY);
    if (fd <= 0) {
        perror("Cannot open obj.o");
        exit(errno);
    }

    /* we need obj.o size for mmap(2) */
    if (fstat(fd, &sb)) {
        perror("Failed to get obj.o info");
        exit(errno);
    }

    /* mmap obj.o into memory */
    obj.base = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (obj.base == MAP_FAILED) {
        perror("Maping obj.o failed");
        exit(errno);
    }
    close(fd);
}
...

If we don't encounter any errors, after load_obj executes we should get the memory address, which points to the beginning of our obj.o in the obj global variable. It is worth noting we have created a special union type for the obj variable: we will be parsing obj.o later (and peeking ahead - object files are actually ELF files), so will be referring to the address both as Elf64_Ehdr (ELF header structure in C) and a byte pointer (parsing ELF files involves calculations of byte offsets from the beginning of the file).

A peek inside an object file

To use some code from an object file, we need to find it first. As I've leaked above, object files are actually ELF files (the same format as Linux executables and shared libraries) and luckily they’re easy to parse on Linux with the help of the standard elf.h header, which includes many useful definitions related to the ELF file structure. But we actually need to know what we’re looking for, so a high-level understanding of an ELF file is needed.

ELF segments and sections

Segments (also known as program headers) and sections are probably the main parts of an ELF file and usually a starting point of any ELF tutorial. However, there is often some confusion between the two. Different sections contain different types of ELF data: executable code (which we are most interested in in this post), constant data, global variables etc. Segments, on the other hand, do not contain any data themselves - they just describe to the operating system how to properly load sections into RAM for the executable to work correctly. Some tutorials say "a segment may include 0 or more sections", which is not entirely accurate: segments do not contain sections, rather they just indicate to the OS where in memory a particular section should be loaded and what is the access pattern for this memory (read, write or execute):

Furthermore, object files do not contain any segments at all: an object file is not meant to be directly loaded by the OS. Instead, it is assumed it will be linked with some other code, so ELF segments are usually generated by the linker, not the compiler. We can check this by using the readelf command:

$ readelf --segments obj.o

There are no program headers in this file.

Object file sections

The same readelf command can be used to get all the sections from our object file:

$ readelf --sections obj.o
There are 11 section headers, starting at offset 0x268:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000001e  0000000000000000  AX       0     0     1
  [ 2] .data             PROGBITS         0000000000000000  0000005e
       0000000000000000  0000000000000000  WA       0     0     1
  [ 3] .bss              NOBITS           0000000000000000  0000005e
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .comment          PROGBITS         0000000000000000  0000005e
       000000000000001d  0000000000000001  MS       0     0     1
  [ 5] .note.GNU-stack   PROGBITS         0000000000000000  0000007b
       0000000000000000  0000000000000000           0     0     1
  [ 6] .eh_frame         PROGBITS         0000000000000000  00000080
       0000000000000058  0000000000000000   A       0     0     8
  [ 7] .rela.eh_frame    RELA             0000000000000000  000001e0
       0000000000000030  0000000000000018   I       8     6     8
  [ 8] .symtab           SYMTAB           0000000000000000  000000d8
       00000000000000f0  0000000000000018           9     8     8
  [ 9] .strtab           STRTAB           0000000000000000  000001c8
       0000000000000012  0000000000000000           0     0     1
  [10] .shstrtab         STRTAB           0000000000000000  00000210
       0000000000000054  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

There are different tutorials online describing the most popular ELF sections in detail. Another great reference is the Linux manpages project. It is handy because it describes both sections’ purpose as well as C structure definitions from elf.h, which makes it a one-stop shop for parsing ELF files. However, for completeness, below is a short description of the most popular sections one may encounter in an ELF file:

.text: this section contains the executable code (the actual machine code, which was created by the compiler from our source code). This section is the primary area of interest for this post as it should contain the add5 and add10 functions we want to use.
.data and .bss: these sections contain global and static local variables. The difference is: .data has variables with an initial value (defined like int foo = 5;) and .bss just reserves space for variables with no initial value (defined like int bar;).
.rodata: this section contains constant data (mostly strings or byte arrays). For example, if we use a string literal in the code (for example, for printf or some error message), it will be stored here. Note, that .rodata is missing from the output above as we didn't use any string literals or constant byte arrays in obj.c.
.symtab: this section contains information about the symbols in the object file: functions, global variables, constants etc. It may also contain information about external symbols the object file needs, like needed functions from the external libraries.
.strtab and .shstrtab: contain packed strings for the ELF file. Note, that these are not the strings we may define in our source code (those go to the .rodata section). These are the strings describing the names of other ELF structures, like symbols from .symtab or even section names from the table above. ELF binary format aims to make its structures compact and of a fixed size, so all strings are stored in one place and the respective data structures just reference them as an offset in either .shstrtab or .strtab sections instead of storing the full string locally.

The `.symtab` section

At this point, we know that the code we want to import and execute is located in the obj.o's .text section. But we have two functions, add5 and add10, remember? At this level the .text section is just a byte blob - how do we know where each of these functions is located? This is where the .symtab (the "symbol table") comes in handy. It is so important that it has its own dedicated parameter in readelf:

$ readelf --symbols obj.o

Symbol table '.symtab' contains 10 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS obj.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    2
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    6
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     8: 0000000000000000    15 FUNC    GLOBAL DEFAULT    1 add5
     9: 000000000000000f    15 FUNC    GLOBAL DEFAULT    1 add10

Let's ignore the other entries for now and just focus on the last two lines, because they conveniently have add5 and add10 as their symbol names. And indeed, this is the info about our functions. Apart from the names, the symbol table provides us with some additional metadata:

The Ndx column tells us the index of the section, where the symbol is located. We can cross-check it with the section table above and confirm that indeed these functions are located in .text (section with the index 1).
Type being set to FUNC confirms that these are indeed functions.
Size tells us the size of each function, but this information is not very useful in our context. The same goes for Bind and Vis.
Probably the most useful piece of information is Value. The name is misleading, because it is actually an offset from the start of the containing section in this context. That is, the add5 function starts just from the beginning of .text and add10 is located from 15th byte and onwards.

So now we have all the pieces on how to parse an ELF file and find the functions we need.

Finding and executing a function from an object file

Given what we have learned so far, let's define a plan on how to proceed to import and execute a function from an object file:

Find the ELF sections table and .shstrtab section (we need .shstrtab later to lookup sections in the section table by name).
Find the .symtab and .strtab sections (we need .strtab to lookup symbols by name in .symtab).
Find the .text section and copy it into RAM with executable permissions.
Find add5 and add10 function offsets from the .symtab.
Execute add5 and add10 functions.

Let's start by adding some more global variables and implementing the parse_obj function:

loader.c:

...

/* sections table */
static const Elf64_Shdr *sections;
static const char *shstrtab = NULL;

/* symbols table */
static const Elf64_Sym *symbols;
/* number of entries in the symbols table */
static int num_symbols;
static const char *strtab = NULL;

...

static void parse_obj(void)
{
    /* the sections table offset is encoded in the ELF header */
    sections = (const Elf64_Shdr *)(obj.base + obj.hdr->e_shoff);
    /* the index of `.shstrtab` in the sections table is encoded in the ELF header
     * so we can find it without actually using a name lookup
     */
    shstrtab = (const char *)(obj.base + sections[obj.hdr->e_shstrndx].sh_offset);

...
}

...

Now that we have references to both the sections table and the .shstrtab section, we can lookup other sections by their name. Let's create a helper function for that:

loader.c:

...

static const Elf64_Shdr *lookup_section(const char *name)
{
    size_t name_len = strlen(name);

    /* number of entries in the sections table is encoded in the ELF header */
    for (Elf64_Half i = 0; i < obj.hdr->e_shnum; i++) {
        /* sections table entry does not contain the string name of the section
         * instead, the `sh_name` parameter is an offset in the `.shstrtab`
         * section, which points to a string name
         */
        const char *section_name = shstrtab + sections[i].sh_name;
        size_t section_name_len = strlen(section_name);

        if (name_len == section_name_len && !strcmp(name, section_name)) {
            /* we ignore sections with 0 size */
            if (sections[i].sh_size)
                return sections + i;
        }
    }

    return NULL;
}

...

Using our new helper function, we can now find the .symtab and .strtab sections:

loader.c:

...

static void parse_obj(void)
{
...

    /* find the `.symtab` entry in the sections table */
    const Elf64_Shdr *symtab_hdr = lookup_section(".symtab");
    if (!symtab_hdr) {
        fputs("Failed to find .symtab\n", stderr);
        exit(ENOEXEC);
    }

    /* the symbols table */
    symbols = (const Elf64_Sym *)(obj.base + symtab_hdr->sh_offset);
    /* number of entries in the symbols table = table size / entry size */
    num_symbols = symtab_hdr->sh_size / symtab_hdr->sh_entsize;

    const Elf64_Shdr *strtab_hdr = lookup_section(".strtab");
    if (!strtab_hdr) {
        fputs("Failed to find .strtab\n", stderr);
        exit(ENOEXEC);
    }

    strtab = (const char *)(obj.base + strtab_hdr->sh_offset);

...
}

...

Next, let's focus on the .text section. We noted earlier in our plan that it is not enough to just locate the .text section in the object file, like we did with other sections. We would need to copy it over to a different location in RAM with executable permissions. There are several reasons for that, but these are the main ones:

Many CPU architectures either don't allow execution of the machine code, which is unaligned in memory (4 kilobytes for x86 systems), or they execute it with a performance penalty. However, the .text section in an ELF file is not guaranteed to be positioned at a page aligned offset, because the on-disk version of the ELF file aims to be compact rather than convenient.
We may need to modify some bytes in the .text section to perform relocations (we don't need to do it in this case, but will be dealing with relocations in future posts). If, for example, we forget to use the MAP_PRIVATE flag, when mapping the ELF file, our modifications may propagate to the underlying file and corrupt it.
Finally, different sections, which are needed at runtime, like .text, .data, .bss and .rodata, require different memory permission bits: the .text section memory needs to be both readable and executable, but not writable (it is considered a bad security practice to have memory both writable and executable). The .data and .bss sections need to be readable and writable to support global variables, but not executable. The .rodata section should be readonly, because its purpose is to hold constant data. To support this, each section must be allocated on a page boundary as we can only set memory permission bits on whole pages and not custom ranges. Therefore, we need to create new, page aligned memory ranges for these sections and copy the data there.

To create a page aligned copy of the .text section, first we actually need to know the page size. Many programs usually just hardcode the page size to 4096 (4 kilobytes), but we shouldn't rely on that. While it's accurate for most x86 systems, other CPU architectures, like arm64, might have a different page size. So hard coding a page size may make our program non-portable. Let's find the page size and store it in another global variable:

loader.c:

...

static uint64_t page_size;

static inline uint64_t page_align(uint64_t n)
{
    return (n + (page_size - 1)) & ~(page_size - 1);
}

...

static void parse_obj(void)
{
...

    /* get system page size */
    page_size = sysconf(_SC_PAGESIZE);

...
}

...

Notice, we have also added a convenience function page_align, which will round up the passed in number to the next page aligned boundary. Next, back to the .text section. As a reminder, we need to:

Find the .text section metadata in the sections table.
Allocate a chunk of memory to hold the .text section copy.
Actually copy the .text section to the newly allocated memory.
Make the .text section executable, so we can later call functions from it.

Here is the implementation of the above steps:

loader.c:

...

/* runtime base address of the imported code */
static uint8_t *text_runtime_base;

...

static void parse_obj(void)
{
...

    /* find the `.text` entry in the sections table */
    const Elf64_Shdr *text_hdr = lookup_section(".text");
    if (!text_hdr) {
        fputs("Failed to find .text\n", stderr);
        exit(ENOEXEC);
    }

    /* allocate memory for `.text` copy rounding it up to whole pages */
    text_runtime_base = mmap(NULL, page_align(text_hdr->sh_size), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (text_runtime_base == MAP_FAILED) {
        perror("Failed to allocate memory for .text");
        exit(errno);
    }

    /* copy the contents of `.text` section from the ELF file */
    memcpy(text_runtime_base, obj.base + text_hdr->sh_offset, text_hdr->sh_size);

    /* make the `.text` copy readonly and executable */
    if (mprotect(text_runtime_base, page_align(text_hdr->sh_size), PROT_READ | PROT_EXEC)) {
        perror("Failed to make .text executable");
        exit(errno);
    }
}

...

Now we have all the pieces we need to locate the address of a function. Let's write a helper for it:

loader.c:

...

static void *lookup_function(const char *name)
{
    size_t name_len = strlen(name);

    /* loop through all the symbols in the symbol table */
    for (int i = 0; i < num_symbols; i++) {
        /* consider only function symbols */
        if (ELF64_ST_TYPE(symbols[i].st_info) == STT_FUNC) {
            /* symbol table entry does not contain the string name of the symbol
             * instead, the `st_name` parameter is an offset in the `.strtab`
             * section, which points to a string name
             */
            const char *function_name = strtab + symbols[i].st_name;
            size_t function_name_len = strlen(function_name);

            if (name_len == function_name_len && !strcmp(name, function_name)) {
                /* st_value is an offset in bytes of the function from the
                 * beginning of the `.text` section
                 */
                return text_runtime_base + symbols[i].st_value;
            }
        }
    }

    return NULL;
}

...

And finally we can implement the execute_funcs function to import and execute code from an object file:

loader.c:

...

static void execute_funcs(void)
{
    /* pointers to imported add5 and add10 functions */
    int (*add5)(int);
    int (*add10)(int);

    add5 = lookup_function("add5");
    if (!add5) {
        fputs("Failed to find add5 function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing add5...");
    printf("add5(%d) = %d\n", 42, add5(42));

    add10 = lookup_function("add10");
    if (!add10) {
        fputs("Failed to find add10 function\n", stderr);
        exit(ENOENT);
    }

    puts("Executing add10...");
    printf("add10(%d) = %d\n", 42, add10(42));
}

...

Let's compile our loader and make sure it works as expected:

$ gcc -o loader loader.c 
$ ./loader 
Executing add5...
add5(42) = 47
Executing add10...
add10(42) = 52

Voila! We have successfully imported code from obj.o and executed it. Of course, the example above is simplified: the code in the object file is self-contained, does not reference any global variables or constants, and does not have any external dependencies. In future posts we will look into more complex code and how to handle such cases.

Security considerations

Processing external inputs, like parsing an ELF file from the disk above, should be handled with care. The code from loader.c omits a lot of bounds checking and additional ELF integrity checks, when parsing the object file. The code is simplified for the purposes of this post, but most likely not production ready, as it can probably be exploited by specifically crafted malicious inputs. Use it only for educational purposes!

The complete source code from this post can be found here.

Probably the simplest way to install Debian/Ubuntu in QEMU

Ignat Korchagin — Tue, 12 Jan 2021 23:30:58 +0000

Without downloading any installation media

Sometimes you might need to quickly spin up a VM for some testing or safe experiments. The typical way to do this is to download the installation media (usually some ISO image), attach it to the VM instance and start the installation process. However, there is a much simpler solution to bootstrap Debian/Ubuntu installation in QEMU over the network without downloading a single ISO.

Debian/Ubuntu installation media types

When it comes to installation media Debian (and its derivative distribution Ubuntu) provides various installation media types for different needs:

full installation CD and DVD images
CD images for network install
even smaller CD images for network install (also known as mini.iso)

Full CDs/DVDs

Debian generally offers two flavours of these: a CD image, which is around 650 MB (actually, for amd64 the current stable "Buster" image is 694 MB) and a bunch of DVD images up to 4.4 GB in size. For a simple standard installation we should be fine with a CD image. Even if we require extra packages and need to use the DVD, Debian recommends downloading only the first DVD image (1 of 3 at the time of this writing) and download the rest, if required by the installer.

Ubuntu images are categorised a bit differently: the project offers a "Desktop" image, which is around 2.6 GB for the current 20.04.1 LTS "Focal Fossa" release and a "Server" image, which is around 914 MB! Desktop images are... well if we want to install Ubuntu on a desktop and server images, as you may have guessed already, are for server installations. The main difference is desktop images will install a graphical user interface by default, while server images will not (although we can install one later). It is also worth mentioning that Ubuntu installation images are live CDs: we can run Ubuntu directly from the CD without needing to install it. Finally, Ubuntu also offers variations of a "desktop" image with alternative graphical user interfaces: Kubuntu with a KDE based desktop, Xubuntu with a Xfce based desktop etc. The default desktop for Ubuntu is GNOME by the way.

Network install images

Using a full CD/DVD is usually useful only in specific scenarios, for example:

we want to provision many machines at once (so we download the software once and use it multiple times).
installing Linux on a machine not connected to the Internet (very unlikely use case in today's connected world - probably, only useful for some security critical setup).

For a simple one-off single setup in almost all other cases we may be better off with the installation over the network. There are two major reasons for this:

with network install we only download packages we actually need: for example, if we want to run a simple HTTP server, we don't need to download the GNOME desktop (which would be included in the full installation CD).
software updates: modern Linux distributions regularly publish software updates (usually much more often than they produce installation CDs), so right after the installation from the CD is complete we would likely need to check for updates and download new versions of some packages. With network install we get the latest and greatest from the start and don't download packages just to immediately overwrite them with a newer version.

So if the network install is much better, why do we have "network install CDs"? Well, an empty machine (or a VM) can't just do complex OS installation on its own, because it is empty (has no software). We need the installer software to solve the chicken and egg problem of installing software. These "network install CDs" provide just that: a minimal live operating system (Linux as well) to launch the installer, which will download and install the full operating system for us (often allowing us to customise and personalise the installation in the process).

If we search for Debian network install, most likely we'll find this page offering us to download a "minimal bootable CD" for Debian installation over the network. Debian claims these CDs should be between 150 MB and 300 MB in size depending on the architecture, but the current "Buster" image for amd64 is 336 MB (still a lot, but more than half the size of the full CD).

The mini.iso

If you're wondering why do we need a 336 MB CD image just to bootstrap a simple installer, which downloads packages from the Internet, you're not alone. However, both Debian and Ubuntu provide another variant of the installation media, known as mini.iso (you can get the Debian Buster one here). These are indeed much smaller (only 48 MB for Debian Buster installation on amd64), but do the job of network installation equally well. They are a bit tricky to find though as there are not many links from the official documentation pointing to those images. Nevertheless, if you need to install Debian/Ubuntu and you have to use an ISO, I recommend the mini.iso as it provides a truly minimal installer bootstrap.

Installing Debian/Ubuntu in QEMU without any installation media

48 MB is good, but what is better? 0 MB, of course! In addition to downloading less we get the benefit of not having these leftover garbage ISO files lying around after the installation is complete. This is not always possible though, but for a specific use case of "bootstrapping a Debian/Ubuntu VM in QEMU" is quite doable.

Let's create a QEMU disk image, which will host our installation (we're creating a 16 GB image below, but you may adjust the capacity for your needs):

$ qemu-img create -f qcow2 test.img 16G

Now if we start a QEMU VM with this disk image, we would see something like below:

$ qemu-system-x86_64 -nographic -m 4G -hda test.img
SeaBIOS (version 1.12.0-1)


iPXE (http://ipxe.org) 00:03.0 C980 PCI2.10 PnP PMM+BFF900F0+BFED00F0 C980



Booting from Hard Disk...
Boot failed: not a bootable disk

Booting from Floppy...
Boot failed: could not read the boot disk

Booting from DVD/CD...
Boot failed: Could not read from CDROM (code 0003)
Booting from ROM...
iPXE (PCI 00:03.0) starting execution...ok
iPXE initialising devices...ok



iPXE 1.0.0+git-20190125.36a4c85-1 -- Open Source Network Boot Firmware -- http:/
/ipxe.org
Features: DNS HTTP iSCSI NFS TFTP AoE ELF MBOOT PXE bzImage Menu PXEXT

net0: 52:54:00:12:34:56 using 82540em on 0000:00:03.0 (open)
  [Link:up, TX:0 TXE:0 RX:0 RXE:0]
Configuring (net0 52:54:00:12:34:56)...... ok
net0: 10.0.2.15/255.255.255.0 gw 10.0.2.2
net0: fec0::5054:ff:fe12:3456/64 gw fe80::2
net0: fe80::5054:ff:fe12:3456/64
Nothing to boot: No such file or directory (http://ipxe.org/2d03e13b)
No more network devices

No bootable device.

Our QEMU VM tried to boot from the disk first, but obviously failed, because the disk is new and empty. Next, it tried to boot from a... floppy 💾! Although, there is even an emoji for it, I will not cover anything about floppies here (and if someone doesn't know what a floppy is, just click here). Next, it tried to boot from a CD/DVD, but we did not attach any ISO images to this VM, so failed again. Finally, it tried to PXE-boot - a standardised form of machine network boot, but it requires supporting infrastructure on the local network: properly configured DHCP and TFTP servers. QEMU can actually emulate those for us with tftp= and bootfile= options (for details, see QEMU networking documentation), but we still need to provide the actual bootfiles, so in the end this option is not better than just attaching a mini.iso to our VM.

We may notice though, that the PXE-boot option in QEMU is implemented via iPXE - a popular open source bootloader and network card firmware. The nice thing about iPXE is that it is much "smarter" than the traditional network card firmware and can communicate over more common HTTP protocol rather than the very old PXE-boot protocols, suitable only for the local network. And that means we can just use iPXE to boot our VM straight from the Internet over HTTP!

We'll use just that to bootstrap our Debian/Ubuntu installation. But where do we get the installer from? The same online folder, which hosts the mini.iso also has a folder named debian-installer, which has an architecture specific folder inside (currently amd64 only). There we will find a bunch of files, but we need only two: linux - the installation environment Linux kernel image, and initrd.gz - the userspace portion of the installation environment (the installer itself). Now let's try to get these into QEMU directly with iPXE.

Start the QEMU (we're using the -nographic command line option to leave the console output in the terminal instead of the default QEMU-emulated monitor - this is useful to be able to copy-paste long debian installer HTTP links later):

$ qemu-system-x86_64 -nographic -m 4G -hda test.img

When it gets to the PXE-boot stage we will briefly see:

Press Ctrl-B for the iPXE command line...

We need to quickly press Ctrl+B here to interrupt the PXE-boot stage and get into the iPXE shell (if you missed the opportunity, just reboot the VM and retry):

iPXE>

Now we can direct iPXE to download the Debian installer from the Internet and launch it. But first, we need to configure the network card in iPXE. If you're using the default QEMU user networking mode (like we do here), QEMU will simulate a DHCP server for you and the VM will be NAT-ed to the Internet through the host machine. So all we need to do, is DHCP the network interface:

iPXE> dhcp net0
Configuring (net0 52:54:00:12:34:56)...... ok

Next we will instruct iPXE to download the installer kernel (linux) and the initrd (initrd.gz) directly from the online netboot folder via HTTP:

iPXE> kernel http://ftp.debian.org/debian/dists/buster/main/installer-amd64/curr
ent/images/netboot/debian-installer/amd64/linux console=ttyS0
http://ftp.debian.org/debian/dists/buster/main/installer-amd64/current/images/ne
tboot/debian-installer/amd64/linux... ok
iPXE> initrd http://ftp.debian.org/debian/dists/buster/main/installer-amd64/curr
ent/images/netboot/debian-installer/amd64/initrd.gz
http://ftp.debian.org/debian/dists/buster/main/installer-amd64/current/images/ne
tboot/debian-installer/amd64/initrd.gz... ok

Notice that we've added the console=ttyS0 command line option for the kernel. This is because we run QEMU with the -nographic option and our VM input/output is done via an emulated serial port. So we need to tell the booting kernel to redirect its primary console to this serial port as well.

Finally, let's boot the downloaded installer:

iPXE> boot
Probing EDD (edd=off to disable)... o
[    0.000000] Linux version 4.19.0-13-amd64 (debian-kernel@lists.debian.org) ()
[    0.000000] Command line: console=ttyS0
[    0.000000] x86/fpu: x87 FPU will use FXSAVE
[    0.000000] BIOS-provided physical RAM map:
[    0.000000] BIOS-e820: [mem 0x0000000000000000-0x000000000009fbff] usable
[    0.000000] BIOS-e820: [mem 0x000000000009fc00-0x000000000009ffff] reserved
[    0.000000] BIOS-e820: [mem 0x00000000000f0000-0x00000000000fffff] reserved
[    0.000000] BIOS-e820: [mem 0x0000000000100000-0x00000000bffdffff] usable
[    0.000000] BIOS-e820: [mem 0x00000000bffe0000-0x00000000bfffffff] reserved
[    0.000000] BIOS-e820: [mem 0x00000000fffc0000-0x00000000ffffffff] reserved
[    0.000000] BIOS-e820: [mem 0x0000000100000000-0x000000013fffffff] usable
[    0.000000] NX (Execute Disable) protection: active
[    0.000000] SMBIOS 2.8 present.
[    0.000000] DMI: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.12.0-1 04/014
...

When it finally boots, we will see the familiar Debian installation window:

At this point we can proceed with the installation as if we've booted from the mini.iso, but we've downloaded only 34 MB (5 MB for linux and 29 MB for initrd.gz) and won't have any leftover ISO files lying around, when the installation is complete.

It is worth noting that the same approach works, if we run QEMU in UEFI mode.

Security considerations

One downside of this approach is that we've downloaded the installer over non-encrypted HTTP: even though the upstream iPXE supports HTTPS, it is not enabled in the QEMU builds as of now. This means we might not be able to fully trust the running software on our VM, but it is probably OK for simple testing and experiments. If you're concerned about the security of the installation, use the mini.iso approach instead.

Passkb: how to reliably and securely bypass password paste blocking

Ignat Korchagin — Sun, 13 Dec 2020 17:08:06 +0000

Originally published at pqsec.org

These days passwords have to be really strong to withstand all modern passwords attacks. Not only passwords have to be long and complex, with all the data breaches around the world it is also very critical not to reuse the same password on several websites. As a result there is no way a human can memorize all the strong passwords for all the online services they need to access.

This is where password managers come into play: instead of memorising all the passwords we only need to remember one strong password and the password manager will remember the rest for us by storing our service passwords in an encrypted database. However, some websites try to make using a password manager particularly inconvenient by blocking the ability to paste passwords on their password input forms.

Why block password paste

Most websites, which block password paste, think they improve their security by doing so, when in fact they make it even worse, especially for their users. I will not list the details here, just recommend to read this although dated but still quite relevant post from Troy Hunt. In a nutshell, disabling paste on password input fields is just a "security theatre" and even some government organisations advise against it.

Unfortunately, though, not all website owners recognise the counter-reasons for blocking paste and still do it. This is very annoying, if you use a password manager, because passwords in a password manager are usually randomly generated and you have to somehow type each character by hand peeking on the password plaintext. And sometimes you can miss a character, fat finger or whatever and it is not immediately apparent where the typo is.

Unblocking password paste

There are many articles online (like this one) on how to restore paste functionality on password fields that block it. However, they boil down to two approaches:

if you're using Firefox, you can set dom.event.clipboardevents.enabled to false in about:config
on both Chrome and Firefox, you can install this (or any other similar) browser extension, which should unblock the paste functionality for you

But there are shortcomings of these approaches. First, they are browser dependent: what if you use Safari, Opera or MS Edge? Secondly, the idea behind both approaches is to somehow disable/rewrite some JavaScript on pages with password input fields, because paste blocking is usually implemented by this JavaScript. But this is a bit like "cracking a nut with a sledgehammer", because modern Web applications extensively use JavaScript for many other primary functionality and just messing with it can potentially break the whole application.

Security considerations for browser extensions

While a functionally broken Web application is a mere inconvenience, there are some security risks involved when using a browser extension to unblock password paste. For example, when you install this popular extension in Chrome, you get a warning like below:

Let's reiterate: this extension would be able to read and modify all your browsing data on the fly. And this is not some kind of a bug, this is by design as the extension needs this functionality to do its job. Moreover, remember that browser extensions process the data after the TLS termination, so even if you browse HTTPS resources, these extensions still see full plaintext data. Finally, browser extensions run in the browser's context - a process with full network access, so these extensions not only see all your browsing data, but can potentially leak it over the network. What could go wrong?

Just to be clear, I'm not implying that all these extensions are evil by design. Most of them are even open-source and you can check that the author's intention is indeed only to unblock password paste functionality and nothing else. However, it is the environment that is risky: browser extensions (like the Web applications themselves) are mostly written in JavaScript. And in JavaScript ecosystem developers tend to heavily rely on NPM registry (and similar code repositories) for their code dependencies. However, sometimes these dependencies themselves may become compromised (for example, due to the maintainers' account takeover/hijack), thus all dependent projects suddenly start distributing potentially malicious code. And on top of that, as we've learned above, this code runs in a privileged context having full access to your browsing data and the Internet.

Rethinking paste unblock

Let's zoom out for a bit and take a look at the current paste unblock methods. From a high-level perspective they follow the same path: we know that password paste blocking is implemented via some JavaScript code in the Web application and the above mentioned methods try to somehow neutralise or break this code.

What if we take a different approach? Instead of trying to disable the paste blocking code we will just present the password input in the form the Web application expects - by typing it in. However, the typing doesn't have to be performed by the operator - we can have a program, which will instruct the operating system to type the complex password on our behalf. The ability to simulate keystrokes exists in modern operating systems for a while now to support different accessibility applications, virtual keyboards, voice input etc. So why not use it to our advantage and "ask" the operating system to type a password for us (if it is otherwise cumbersome to type manually)?

Introducing passkb

Passkb is a simple command line application, which helps to type complex passwords. The workflow is pretty simple: if you encounter a Web application, which blocks password paste, you can paste your password into passkb and passkb will type it in for you:

We don't need to run third-party browser extensions or mess with browser settings anymore - this approach works for every browser and for any Web application. Moreover, because passkb emulates typing, Web applications can never block it, as they have to allow typing by design. Another notable security advantage is that passkb runs as a separate process in the operating system, so it can be easily sandboxed and denied network access (after all, we're trusting it with our passwords). The only downside is that there is a slight inconvenience of switching several windows to "copy-type" a password and you have to do it in a timely manner: by default you have 5 seconds (but it is configurable) to put the cursor in the right place for the tool to type the password in the needed form. Otherwise, it will type the password to wherever the cursor and the focus currently is.

Linux specifics

While on both Windows and Mac OS passkb uses standard APIs to generate typing events, Linux may require some additional config to make the tool usable. On Linux the tool uses the special /dev/uinput device, thus it has to be present in the system. Most popular Linux distributions already support this special device file (although you might have to run modprobe uinput), but if you compile your own kernel, make sure to enable CONFIG_INPUT_UINPUT in the kernel configuration file.

Additionally, to generate typing events through this interface the process needs read/write access for /dev/uinput. However, by default, only the root user is allowed to read and write to the file. Probably, the best way to reconfigure this is:

create a dedicated group
change the group ownership of the /dev/uinput to our newly created group
change the access bits on /dev/uinput to 660 (group can read/write as well)
add yourself (and any other system users, who would use the tool) to the group

And remember: permission and ownership changes to the device filesystem do not persist, so will reset on reboot. You need some kind of a startup script or a systemd udev rule to adjust the ownership and the permission bits of /dev/uinput on each boot.

Potential future improvements

It would be nice to improve the user experience of the tool and not to confine the user to 5 seconds (or any other timeout) to type the password in the correct place. One way to do so is to figure out, if some keyboard shortcuts could be registered for the tool, which can trigger the typing of the provided password. This way the user may have the familiar experience of Ctrl/Cmd+C/Ctrl/Cmd+V, but Ctrl/Cmd+V may be replaced by some other key combo and will type the password instead of pasting it. If you have any ideas on how to implement this, pull requests are welcome.

Sandboxing in Linux with zero lines of code

Ignat Korchagin — Wed, 08 Jul 2020 13:02:32 +0000

Sandboxing in Linux with zero lines of code

This is a repost of my post from the Cloudflare Blog

Modern Linux operating systems provide many tools to run code more securely. There are namespaces (the basic building blocks for containers), Linux Security Modules, Integrity Measurement Architecture etc.

In this post we will review Linux seccomp and learn how to sandbox any (even a proprietary) application without writing a single line of code.

Tux by Iwan Gabovitch, GPL
Sandbox, Simplified Pixabay License

Linux system calls

System calls (syscalls) is a well-defined interface between userspace applications and the operating system (OS) kernel. On modern operating systems most applications provide only application-specific logic as code. Applications do not, and most of the time cannot, directly access low-level hardware or networking, when they need to store data or send something over the wire. Instead they use system calls to ask the OS kernel to do specific hardware and networking tasks on their behalf:

Apart from providing a generic high level way for applications to interact with the low level hardware, the system call architecture allows the OS kernel to manage available resources between applications as well as enforce policies, like application permissions, networking access control lists etc.

Linux seccomp

Linux seccomp is yet another syscall on Linux, but it is a bit special, because it influences how the OS kernel will behave when the application uses other system calls. By default, the OS kernel has almost no insight into userspace application logic, so it provides all the possible services it can. But not all applications require all services. Consider an application which converts image formats: it needs the ability to read and write data from disk, but in its simplest form probably does not need any network access. Using seccomp an application can declare its intentions in advance to the Linux kernel. For this particular case it can notify the kernel that it will be using the read and write system calls, but never the send and recv system calls (because its intent is to work with local files and never with the network). It’s like establishing a contract between the application and the OS kernel:

But what happens if the application later breaks the contract and tries to use one of the system calls it promised not to use? The kernel will “penalise” the application, usually by immediately terminating it. Linux seccomp also allows less restrictive actions for the kernel to take:

instead of terminating the whole application, the kernel can be requested to terminate only the thread, which issued the prohibited system call
the kernel may just send a SIGSYS signal to the calling thread
the seccomp policy can specify an error code, which the kernel will then return to the calling application instead of executing the prohibited system call
if the violating process is under ptrace (for example executing under a debugger), the kernel can notify the tracer (the debugger) that a prohibited system call is about to happen and let the debugger decide what to do
the kernel may be instructed to allow and execute the system call, but log the attempt: this is useful, when we want to verify that our seccomp policy is not too tight without the risk of terminating the application and potentially creating an outage

Although there is a lot of flexibility in defining the potential penalty for the application, from a security perspective it is usually best to stick with the complete application termination upon seccomp policy violation. The reason for that will be described later in the examples in the post.

So why would the application take the risk of being abruptly terminated and declare its intentions beforehand, if it can just be “silent” and the OS kernel will allow it to use any system call by default? Of course, for a normal behaving application it makes no sense, but it turns out this feature is quite effective to protect from rogue applications and arbitrary code execution exploits.

Imagine our image format converter is written in some unsafe language and an attacker was able to take control of the application by making it process some malformed image. What the attacker might do is to try to steal some sensitive information from the machine running our converter and send it to themselves via the network. By default, the OS kernel will most likely allow it and a data leak will happen. But if our image converter “confined” (or sandboxed) itself beforehand to only read and write local data the kernel will terminate the application when the latter tries to leak the data over the network thus preventing the leak and locking out the attacker from our system!

Integrating seccomp into the application

To see how seccomp can be used in practice, let’s consider a toy example program

myos.c:

#include <stdio.h>
#include <sys/utsname.h>

int main(void)
{
    struct utsname name;

    if (uname(&name)) {
        perror("uname failed: ");
        return 1;
    }

    printf("My OS is %s!\n", name.sysname);
    return 0;
}

This is a simplified version of the uname command line tool, which just prints your operating system name. Like its full-featured counterpart, it uses the uname system call to actually get the name of the current operating system from the kernel. Let’s see it action:

$ gcc -o myos myos.c
$ ./myos
My OS is Linux!

Great! We’re on Linux, so can further experiment with seccomp (it is a Linux-only feature). Notice that we’re properly handling the error code after invoking the uname system call. However, according to the man page it can only fail, when the passed in buffer pointer is invalid. And in this case the set error number will be “EINVAL”, which translates to invalid parameter. In our case, the “struct utsname” structure is being allocated on the stack, so our pointer will always be valid. In other words, in normal circumstances the uname system call should never fail in this particular program.

To illustrate seccomp capabilities we will add a “sandbox” function to our program before the main logic

myos_raw_seccomp.c:

#include <linux/seccomp.h>
#include <linux/filter.h>
#include <linux/audit.h>
#include <sys/ptrace.h>
#include <sys/prctl.h>

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <sys/utsname.h>
#include <errno.h>
#include <unistd.h>
#include <sys/syscall.h>

static void sandbox(void)
{
    struct sock_filter filter[] = {
        /* seccomp(2) says we should always check the arch */
        /* as syscalls may have different numbers on different architectures */
        /* see https://fedora.juszkiewicz.com.pl/syscalls.html */
        /* for simplicity we only allow x86_64 */
        BPF_STMT(BPF_LD | BPF_W | BPF_ABS, (offsetof(struct seccomp_data, arch))),
        /* if not x86_64, tell the kernel to kill the process */
        BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, AUDIT_ARCH_X86_64, 0, 4),
        /* get the actual syscall number */
        BPF_STMT(BPF_LD | BPF_W | BPF_ABS, (offsetof(struct seccomp_data, nr))),
        /* if "uname", tell the kernel to return EPERM, otherwise just allow */
        BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, SYS_uname, 0, 1),
        BPF_STMT(BPF_RET | BPF_K, SECCOMP_RET_ERRNO | (EPERM & SECCOMP_RET_DATA)),
        BPF_STMT(BPF_RET | BPF_K, SECCOMP_RET_ALLOW),
        BPF_STMT(BPF_RET | BPF_K, SECCOMP_RET_KILL),
    };

    struct sock_fprog prog = {
        .len = (unsigned short) (sizeof(filter) / sizeof(filter[0])),
        .filter = filter,
    };

    /* see seccomp(2) on why this is needed */
    if (prctl(PR_SET_NO_NEW_PRIVS, 1, 0, 0, 0)) {
        perror("PR_SET_NO_NEW_PRIVS failed");
        exit(1);
    };

    /* glibc does not have a wrapper for seccomp(2) */
    /* invoke it via the generic syscall wrapper */
    if (syscall(SYS_seccomp, SECCOMP_SET_MODE_FILTER, 0, &prog)) {
        perror("seccomp failed");
        exit(1);
    };
}

int main(void)
{
    struct utsname name;

    sandbox();

    if (uname(&name)) {
        perror("uname failed");
        return 1;
    }

    printf("My OS is %s!\n", name.sysname);
    return 0;
}

To sandbox itself the application defines a BPF program, which implements the desired sandboxing policy. Then the application passes this program to the kernel via the seccomp system call. The kernel does some validation checks to ensure the BPF program is OK and then runs this program on every system call the application makes. The results of the execution of the program is used by the kernel to determine if the current call complies with the desired policy. In other words the BPF program is the “contract” between the application and the kernel.

In our toy example above, the BPF program simply checks which system call is about to be invoked. If the application is trying to use the uname system call we tell the kernel to just return a EPERM (which stands for “operation not permitted”) error code. We also tell the kernel to allow any other system call. Let’s see if it works now:

$ gcc -o myos myos_raw_seccomp.c
$ ./myos
uname failed: Operation not permitted

uname failed now with the EPERM error code and EPERM is not even described as a potential failure code in the uname manpage! So we know now that this happened because we “told” the kernel to prohibit us using the uname syscall and to return EPERM instead. We can double check this by replacing EPERM with some other error code, which is totally inappropriate for this context, for example ENETDOWN (“network is down”). Why would we need the network to be up to just get the currently executing OS? Yet, recompiling and rerunning the program we get:

$ gcc -o myos myos_raw_seccomp.c
$ ./myos
uname failed: Network is down

We can also verify the other part of our “contract” works as expected. We told the kernel to allow any other system call, remember? In our program, when uname fails, we convert the error code to a human readable message and print it on the screen with the perror function. To print on the screen perror uses the write system call under the hood and since we can actually see the printed error message, we know that the kernel allowed our program to make the write system call in the first place.

seccomp with libseccomp

While it is possible to use seccomp directly, as in the examples above, BPF programs are cumbersome to write by hand and hard to debug, review and update later. That’s why it is usually a good idea to use a more high-level library, which abstracts away most of the low-level details. Luckily such a library exists: it is called libseccomp and is even recommended by the seccomp man page.

Let’s rewrite our program’s sandbox() function to use this library instead:

myos_libseccomp.c:

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <sys/utsname.h>
#include <seccomp.h>
#include <err.h>

static void sandbox(void)
{
    /* allow all syscalls by default */
    scmp_filter_ctx seccomp_ctx = seccomp_init(SCMP_ACT_ALLOW);
    if (!seccomp_ctx)
        err(1, "seccomp_init failed");

    /* kill the process, if it tries to use "uname" syscall */
    if (seccomp_rule_add_exact(seccomp_ctx, SCMP_ACT_KILL, seccomp_syscall_resolve_name("uname"), 0)) {
        perror("seccomp_rule_add_exact failed");
        exit(1);
    }

    /* apply the composed filter */
    if (seccomp_load(seccomp_ctx)) {
        perror("seccomp_load failed");
        exit(1);
    }

    /* release allocated context */
    seccomp_release(seccomp_ctx);
}

int main(void)
{
    struct utsname name;

    sandbox();

    if (uname(&name)) {
        perror("uname failed: ");
        return 1;
    }

    printf("My OS is %s!\n", name.sysname);
    return 0;
}

Our sandbox() function not only became shorter and much more readable, but also provided the ability to reference syscalls in our rules by names and not internal numbers as well as not having to deal with other quirks, like setting PR_SET_NO_NEW_PRIVS bit and dealing with system architectures.

It is worth noting we have modified our seccomp policy a bit. In the raw seccomp example above we instructed the kernel to return an error code when the application tries to execute a prohibited syscall. This is good for demonstration purposes, but in most cases a stricter action is required. Just returning an error code and allowing the application to continue gives the potentially malicious code a chance to bypass the policy. There are many syscalls in Linux and some of them do the same or similar things. For example, we might want to prohibit the application to read data from disk, so we deny the read syscall in our policy and tell the kernel to return an error code instead. However, if the application does get exploited, the exploit code/logic might look like below:

…
if (-1 == read(fd, buf, count)) {
    /* hm… read failed, but what about pread? */
    if (-1 == pread(fd, buf, count, offset) {
        /* what about readv? */ ...
    }
    /* bypassed the prohibited read(2) syscall */
}
…

Wait what?! There is more than one read system call? Yes, there are read, pread, readv as well as more obscure ones, like io_submit and io_uring_enter. Of course, it is our fault for providing incomplete seccomp policy, which does not block all possible read syscalls. But if at least we had instructed the kernel to terminate the process immediately upon violation of the first plain read, the malicious code above would not have the chance to be clever and try other options.

Given the above in the libseccomp example we have a stricter policy now, which tells the kernel to terminate the process upon the policy violation. Let’s see if it works:

$ gcc -o myos myos_libseccomp.c -lseccomp
$ ./myos
Bad system call

Notice that we need to link against libseccomp when compiling the application. Also, when we run the application, we don’t see the uname failed: Operation not permitted error output anymore, because we don’t give the application the ability to even print a failure message. Instead, we see a Bad system call message from the shell, which tells us that the application was terminated with a SIGSYS signal. Great!

zero code seccomp

The previous examples worked fine, but both of them have one disadvantage: we actually needed to modify the source code to embed our desired seccomp policy into the application. This is because seccomp syscall affects the calling process and its children, but there is no interface to inject the policy from “outside”. It is expected that developers will sandbox their code themselves as part of the application logic, but in practice this rarely happens. When developers are starting a new project, most of the time the focus is on primary functionality and security features are usually either postponed or omitted altogether. Also, most real-world software is usually written using some high-level programming language and/or a framework, where the developers do not deal with the system calls directly and probably are even unaware which system calls are being used by their code.

On the other hand we have system operators, sysadmins, SRE and other folks, who run the above code in production. They are more incentivized to keep production systems secure, thus would probably want to sandbox the services as much as possible. But most of the time they don’t have access to the source code. So there are mismatched expectations: developers have the ability to sandbox their code, but are usually not incentivized to do so and operators have the incentive to sandbox the code, but don’t have the ability.

This is where “zero code seccomp” might help, where an external operator can inject the desired sandbox policy into any process without needing to modify any source code. Systemd is one of the popular implementations of a “zero code seccomp” approach. Systemd-managed services can have a SystemCallFilter= directive defined in their unit files listing all the system calls the managed service is allowed to make. As an example, let’s go back to our toy application without any sandboxing code embedded:

$ gcc -o myos myos.c
$ ./myos
My OS is Linux!

Now we can run the same code with systemd, but prohibit the application for using uname without changing or recompiling any code (we’re using systemd-run to create an ephemeral systemd service unit for us):

$ systemd-run --user --pty --same-dir --wait --collect --service-type=exec --property="SystemCallFilter=~uname" ./myos
Running as unit: run-u0.service
Press ^] three times within 1s to disconnect TTY.
Finished with result: signal
Main processes terminated with: code=killed/status=SYS
Service runtime: 6ms

We don’t see the normal My OS is Linux! output anymore and systemd conveniently tells us that the managed process was terminated with a SIGSYS signal. We can even go further and use another directive SystemCallErrorNumber= to configure our seccomp policy not to terminate the application, but return an error code instead as in our first seccomp raw example:

$ systemd-run --user --pty --same-dir --wait --collect --service-type=exec --property="SystemCallFilter=~uname" --property="SystemCallErrorNumber=ENETDOWN" ./myos
Running as unit: run-u2.service
Press ^] three times within 1s to disconnect TTY.
uname failed: Network is down
Finished with result: exit-code
Main processes terminated with: code=exited/status=1
Service runtime: 6ms

systemd small print

Great! We can now inject almost any seccomp policy into any process without the need to write any code or recompile the application. However, there is an interesting statement in the systemd documentation:

...Note that the execve, exit, exit_group, getrlimit, rt_sigreturn, sigreturn system calls and the system calls for querying time and sleeping are implicitly whitelisted and do not need to be listed explicitly...

Some system calls are implicitly allowed and we don’t have to list them. This is mostly related to the way how systemd manages processes and injects the seccomp policy. We established earlier that seccomp policy applies to the current process and its children. So, to inject the policy, systemd forks itself, calls seccomp in the forked process and then execs the forked process into the target application. That’s why always allowing the execve system call is necessary in the first place, because otherwise systemd cannot do its job as a service manager.

But what if we want to explicitly prohibit some of these system calls? If we continue with the execve as an example, that can actually be a dangerous system call most applications would want to prohibit. Seccomp is an effective tool to protect the code from arbitrary code execution exploits, remember? If a malicious actor takes over our code, most likely the first thing they will try is to get a shell (or replace our code with any other application which is easier to control) by directing our code to call execve with the desired binary. So, if our code does not need execve for its main functionality, it would be a good idea to prohibit it. Unfortunately, it is not possible with the systemd SystemCallFilter= approach...

Introducing Cloudflare sandbox

We really liked the “zero code seccomp” approach with systemd SystemCallFilter= directive, but were not satisfied with its limitations. We decided to take it one step further and make it possible to prohibit any system call in any process externally without touching its source code, so came up with the Cloudflare sandbox. It’s a simple standalone toolkit consisting of a shared library and an executable. The shared library is supposed to be used with dynamically linked applications and the executable is for statically linked applications.

sandboxing dynamically linked executables

For dynamically linked executables it is possible to inject custom code into the process by utilizing the LD_PRELOAD environment variable. The libsandbox.so shared library from our toolkit also contains a so-called initialization routine, which should be executed before the main logic. This is how we make the target application sandbox itself:

LD_PRELOAD tells the dynamic loader to load our libsandbox.so as part of the application, when it starts
the runtime executes the initialization routine from the libsandbox.so before most of the main logic
our initialization routine configures the sandbox policy described in special environment variables
by the time the main application logic begin executing, the target process has the configured seccomp policy enforced

Let’s see how it works with our myos toy tool. First, we need to make sure it is actually a dynamically linked application:

$ ldd ./myos
    linux-vdso.so.1 (0x00007ffd8e1e3000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f339ddfb000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f339dfcf000)

Yes, it is . Now, let’s prohibit it from using the uname system call with our toolkit:

$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libsandbox.so SECCOMP_SYSCALL_DENY=uname ./myos
adding uname to the process seccomp filter
Bad system call

Yet again, we’ve managed to inject our desired seccomp policy into the myos application without modifying or recompiling it. The advantage of this approach is that it doesn’t have the shortcomings of the systemd’s SystemCallFilter= and we can block any system call (luckily Bash is a dynamically linked application as well):

$ /bin/bash -c 'echo I will try to execve something...; exec /usr/bin/echo Doing arbitrary code execution!!!'
I will try to execve something...
Doing arbitrary code execution!!!
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libsandbox.so SECCOMP_SYSCALL_DENY=execve /bin/bash -c 'echo I will try to execve something...; exec /usr/bin/echo Doing arbitrary code execution!!!'
adding execve to the process seccomp filter
I will try to execve something...
Bad system call

The only problem here is that we may accidentally forget to LD_PRELOAD our libsandbox.so library and potentially run unprotected. Also, as described in the man page, LD_PRELOAD has some limitations. We can overcome all these problems by making libsandbox.so a permanent part of our target application:

$ patchelf --add-needed /usr/lib/x86_64-linux-gnu/libsandbox.so ./myos
$ ldd ./myos
    linux-vdso.so.1 (0x00007fff835ae000)
    /usr/lib/x86_64-linux-gnu/libsandbox.so (0x00007fc4f55f2000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fc4f5425000)
    /lib64/ld-linux-x86-64.so.2 (0x00007fc4f5647000)

Again, we didn’t need access to the source code here, but patched the compiled binary instead. Now we can just configure our seccomp policy as before without the need of LD_PRELOAD:

$ ./myos
My OS is Linux!
$ SECCOMP_SYSCALL_DENY=uname ./myos
adding uname to the process seccomp filter
Bad system call

sandboxing statically linked executables

The above method is quite convenient and easy, but it doesn’t work for statically linked executables:

$ gcc -static -o myos myos.c
$ ldd ./myos
    not a dynamic executable
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libsandbox.so SECCOMP_SYSCALL_DENY=uname ./myos
My OS is Linux!

This is because there is no dynamic loader involved in starting a statically linked executable, so LD_PRELOAD has no effect. For this case our toolkit contains a special application launcher, which will inject the seccomp rules similarly to the way systemd does it:

$ sandboxify ./myos
My OS is Linux!
$ SECCOMP_SYSCALL_DENY=uname sandboxify ./myos
adding uname to the process seccomp filter

Note that we don’t see the Bad system call shell message anymore, because our target executable is being started by the launcher instead of the shell directly. Unlike systemd however, we can use this launcher to block dangerous system calls, like execve, as well:

$ sandboxify /bin/bash -c 'echo I will try to execve something...; exec /usr/bin/echo Doing arbitrary code execution!!!'
I will try to execve something...
Doing arbitrary code execution!!!
SECCOMP_SYSCALL_DENY=execve sandboxify /bin/bash -c 'echo I will try to execve something...; exec /usr/bin/echo Doing arbitrary code execution!!!'
adding execve to the process seccomp filter
I will try to execve something...

sandboxify vs libsandbox.so

From the examples above you may notice that it is possible to use sandboxify with dynamically linked executables as well, so why even bother with libsandbox.so? The difference becomes visible, when we start using not the “denylist” policy as in most examples in this post, but rather the preferred “allowlist” policy, where we explicitly allow only the system calls we need, but prohibit everything else.

Let’s convert our toy application back into the dynamically-linked one and try to come up with the minimal list of allowed system calls it needs to function properly:

$ gcc -o myos myos.c
$ ldd ./myos
    linux-vdso.so.1 (0x00007ffe027f6000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f4f1410a000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f4f142de000)
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libsandbox.so SECCOMP_SYSCALL_ALLOW=exit_group:fstat:uname:write ./myos
adding exit_group to the process seccomp filter
adding fstat to the process seccomp filter
adding uname to the process seccomp filter
adding write to the process seccomp filter
My OS is Linux

So we need to allow 4 system calls: exit_group:fstat:uname:write. This is the tightest “sandbox”, which still doesn’t break the application. If we remove any system call from this list, the application will terminate with the Bad system call message (try it yourself!).

If we use the same allowlist, but with the sandboxify launcher, things do not work anymore:

$ SECCOMP_SYSCALL_ALLOW=exit_group:fstat:uname:write sandboxify ./myos
adding exit_group to the process seccomp filter
adding fstat to the process seccomp filter
adding uname to the process seccomp filter
adding write to the process seccomp filter

The reason is sandboxify and libsandbox.so inject seccomp rules at different stages of the process lifecycle. Consider the following very high level diagram of a process startup:

In a nutshell, every process has two runtime stages: “runtime init” and the “main logic”. The main logic is basically the code, which is located in the program main() function and other code put there by the application developers. But the process usually needs to do some work before the code from the main() function is able to execute - we call this work the “runtime init” on the diagram above. Developers do not write this code directly, but most of the time this code is automatically generated by the compiler toolchain, which is used to compile the source code.

To do its job, the “runtime init” stage uses a lot of different system calls, but most of them are not needed later at the “main logic” stage. If we’re using the “allowlist” approach for our sandboxing, it does not make sense to allow these system calls for the whole duration of the program, if they are only used once on program init. This is where the difference between libsandbox.so and sandboxify comes from: libsandbox.so enforces the seccomp rules usually after the “runtime init” stage has already executed, so we don’t have to allow most system calls from that stage. sandboxify on the other hand enforces the policy before the “runtime init” stage, so we have to allow all the system calls from both stages, which usually results in a bigger allowlist, thus wider attack surface.

Going back to our toy myos example, here is the minimal list of all the system calls we need to allow to make the application work under our sandbox:

$ SECCOMP_SYSCALL_ALLOW=access:arch_prctl:brk:close:exit_group:fstat:mmap:mprotect:munmap:openat:read:uname:write sandboxify ./myos
adding access to the process seccomp filter
adding arch_prctl to the process seccomp filter
adding brk to the process seccomp filter
adding close to the process seccomp filter
adding exit_group to the process seccomp filter
adding fstat to the process seccomp filter
adding mmap to the process seccomp filter
adding mprotect to the process seccomp filter
adding munmap to the process seccomp filter
adding openat to the process seccomp filter
adding read to the process seccomp filter
adding uname to the process seccomp filter
adding write to the process seccomp filter
My OS is Linux!

It is 13 syscalls vs 4 syscalls, if we’re using the libsandbox.so approach!

Conclusions

In this post we discussed how to easily sandbox applications on Linux without the need to write any additional code. We introduced the Cloudflare sandbox toolkit and discussed the different approaches we take at sandboxing dynamically linked applications vs statically linked applications.

Having safer code online helps to build a Better Internet and we would be happy if you find our sandbox toolkit useful. Looking forward to the feedback, improvements and other contributions!

Import Markdown into Medium in 4 clicks

Ignat Korchagin — Mon, 25 May 2020 19:19:23 +0000

Or my first web app in 10 years: what could go wrong?

Originally published at pqsec.org

TL;DR: if you're just looking for the tool itself, it is here

I write my personal posts on my own blog, but to reach a wider audience I followed the advice on the Internet to cross-post my posts on popular publishing platforms. In the end I couldn't select between Medium and dev.to, so decided to use both.

My own blog is hosted on GitHub Pages, so I write my posts in Markdown. Luckily, dev.to supports Markdown natively as well, so I can just copy-paste posts there. Medium, however, is not very Markdown friendly: they heavily promote the usage of their superior editor, which is great indeed, but completely useless when it comes to cross-posting.

Markdown to Medium prior art

There is always the official Medium import tool, but when I tried to use it on one of my posts, it completely omitted all the code blocks. It's probably OK, if you have one or two of those and you can re-add them manually, but quickly becomes tiresome for a heavy code oriented post.

The second thing I found was this method of using the official import tool on a GitHub gist, but this produced the same result for me as above. The post also mentions this automated tool, which goes one step further: it creates a separate GitHub gist for every code block in the post and apparently tries to use Medium gist auto expansion, which again did not work for me as all gist links remained not expanded in the editor. I quickly noticed the downsides of the approach as well: when parsing my post Fixing weak crypto in OpenSSL based applications, it created more than 20 gists in my GitHub account and that's for a single post! GitHub gists do not have the concept of "folders", so your account might quickly become messy because of all these gists. Finally, I prefer for all post contents to be hosted in one place. Otherwise, if GitHub is having problems for example, parts of your post suddenly become unreadable, which might frustrate the audience. For completness, I would like to mention Markdium - I didn't try it myself, but according to the demo it uses the same automated GitHub gist approach, but also provides a nice Markdown editor directly in the browser.

Next, there is this browser based tool: it claims to generate html, which is compatible with Medium's editor. So the workflow is like this: you copy-paste the Markdown into the tool, the tool renders it and produces html and you copy-paste this html directly into the Medium's editor. The tool worked as described, when I tried it - I didn't find any inconsistencies and all the code blocks were in place. There are also no gists or giving away your GitHub credentials involved. The only downside is that you have to copy-paste twice. The other potential concern is while the tool produces "compatible" html now, there is no guarantee it would stay that way as Medium might change the way it handles the input any time.

Finally, I found Mdium - a small python tool, which can publish a Markdown post via... Medium API! But the surprise came not from the tool itself, rather (quoting from the tool's post):

It’s 2019 and their editor doesn’t support Markdown, but their API does?

Wait, what? Medium does support Markdown natively, but API only? Heading to the official Medium API documentation we see:

contentFormat: The format of the "content" field. There are two valid values, "html", and "markdown"

I didn't try the Mdium python tool to be honest, just took the previously mentioned Fixing weak crypto in OpenSSL based applications Markdown source, generated myself an API token and posted it as a draft with curl. And voila! The post was nicely imported with all code blocks intact!

A browser based import tool

Importing posts with curl is not a sustainable solution and, if there is an API, I was hoping there would be some ready tools providing this feature. But a quick search did not yield any results except the previously mentioned Mdium. There is nothing wrong with Mdium, but it just didn't tick all the boxes for me: probably, like many other modern Internet users, I have multiple devices with different operating systems, some of them are mobile tablets without straightforward access to python or terminal. Thanks to modern "cloud technologies" I can use any of those to start a new post or continue writing an existing one directly in the browser without the need to manually synchronise any data or installing any applications. I would like the same level of convenience for publishing posts as well, so it would be nice to have a small browser application to hit the Medium API without the need to install anything. And since I didn't find one, I decided to try to create it myself.

Selecting a UI framework

I mostly do system programming and last time I did something around a non-console UI was more than 10 years ago. And that was not without horror stories. At the time .NET Framework was quite popular as the primary tool to write Windows GUI applications. Microsoft also made a push to extend the technology to the Web with ASP.NET - a server side scripting support for .NET Framework. One could even write a Web UI in ASP.NET with Web forms - basically, a bunch of ready made .NET components, which rendered into HTML elements. Once I used the technology to write a simple website, but the result was interesting: the site looked great and rendered fine in every modern browser at the time, except... Microsoft's own Internet Explorer 🤦. I didn't touch a Web UI ever since...

Based on the above experience I was expecting that writing a Web UI would be the biggest challenge (and, oh my I was wrong!). I did hear there are numerous tools and frameworks for writing modern Web applications, which would hopefully take most of the pain away, but which one to choose? I read about Material Design and web frameworks like React, Angular and Vue. These seem to be great tools to write complex Web applications, but each of them is not a complete solution. For example, you need to understand how to properly combine Material Design and Vue or use some other third-party metaframework, like vuematerial.io.

My requirements for the app were quite simple: a small web form and some backing Javascript, which makes JSON requests to the Medium API. I also wanted to get away from installing Node JS, which seems to be required to follow any reasonable tutorials for the above technologies. It was just too much of a curve to write a simple web form. Then I looked at Bootstrap and it seemed to be the right tool: a simple "all-in-one" solution, which allows to write plain familiar HTML directly in the browser and provide a reasonable cross-browser friendly UI. It also doesn't force you into a particular Javascript framework, so you don't even have to use any for simple things. In the end I was able to compose a small web form and draft simple UI notifications within hours with no prior experience with Bootstrap. My job was almost done...

Hello, CORS!

... Or not! During the development of my Web app I even hacked a small local mock Medium API to test the whole flow and it worked great. I thought all I have to do now is to replace the API url with the real one and the app is ready. I was soon disappointed to see nothing happens, when I target my app at the real Medium API. Browser debugging tools showed my requests are simply being blocked because of Cross-origin resource sharing (CORS) violation!

This post will not deep dive into CORS as there are better tutorials, specs and detailed resources out there, but in a nutshell, CORS is a way to block by default most (especially authenticated!) cross-origin requests in modern browsers. During the testing with the mock Medium API it was fine, because requests originated from my localhost "origin" and where hitting my mock server running on localhost as well. In order for this to work with real Medium API, the API needs to reply with special CORS headers as well as support special "HTTP preflight requests". A proper combination of these gives the browser the "permission" to perform the API request - otherwise the browser will not do it as it happened in my case.

I reached out to Medium support about CORS on their API in case I was doing something wrong, but they confirmed CORS is not supported as well as there are no plans to support it in the future. I don't quite understand why would anyone provide a public HTTP API, but make it usable from anything except the browser (if you know - please, reach out to me on Twitter), but it is what it is. Without proper CORS support from the API publisher it seems the only way to make the API accessible in the browser is to use a third-pary CORS proxy, which will inject proper CORS headers.

Implementing a CORS proxy

There are number of ready-made public CORS proxies, but probably one of the most popular one is CORS anywhere running at https://cors-anywhere.herokuapp.com/. Unfortunately, it doesn't work for our use-case: the proxy injects a special CORS header Access-Control-Allow-Origin with a * (wildcard responce). This is good enough for most cases as it tells the browser that the server (or proxy in this case) allows cross-origin requests from any origin. Medium API, however, obviously requires authentication and looks for the presense of the Authorization header in incoming requests with the Medium API token. CORS dictates that browsers will only send cross-origin Authorization header, if the origin was explicitly allowed (listed) by the server in Access-Control-Allow-Origin, that is wildcard response is not good enough for these "authenticated" requests.

Of course, one could grab the sources of CORS anywhere, make the relevant changes and republish the proxy with proper Authorization support, but I wanted something simpler than running my app in a public cloud. Then I remembered about Cloudflare Workers, which are more than ideal for this kind of task. Moreover, Cloudflare Worker Templates resource already has a barebone CORS proxy. The template, however, has similar limitations as CORS anywhere, so requires slight adjustments:

the template sets Access-Control-Allow-Origin to * in the preflight response the same way as CORS anywhere - we need to replace this with something like request.headers.get('Origin'), so the requester will always get their origin explicitly "allowed"
we need to make Access-Control-Allow-Methods dynamic as well to "allow" the browser to send the Authorization header
finally, we need to add Access-Control-Allow-Credentials: true header to the preflight response to explicitly allow the browser to make authenticated requests

In addition to the above I also removed the test page from the template and, unlike CORS anywhere, where you have to specify the proxied URL via a query string, my implementation takes it from a custom X-Corsify-Url request header. The full code is listed below:

async function handleRequest(request) {
  const url = new URL(request.url)
  const apiurl = request.headers.get('X-Corsify-Url')
  const origin = url.origin
  // Rewrite request to point to API url. This also makes the request mutable
  // so we can add the correct Origin header to make the API server think
  // that this request isn't cross-site.
  request = new Request(apiurl, request)
  request.headers.set('Origin', new URL(apiurl).origin)
  request.headers.set('Host', new URL(apiurl).hostname)
  request.headers.delete('X-Corsify-Url')
  let response = await fetch(request)
  // Recreate the response so we can modify the headers
  response = new Response(response.body, response)
  // Set CORS headers
  response.headers.set('Access-Control-Allow-Origin', '*')
  // Append to/Add Vary header so browser will cache response correctly
  response.headers.append('Vary', 'Origin')
  return response
}
function handleOptions(request) {
  // Make sure the necessary headers are present
  // for this to be a valid pre-flight request
  if (
    request.headers.get('Origin') !== null &&
    request.headers.get('Access-Control-Request-Method') !== null &&
    request.headers.get('Access-Control-Request-Headers') !== null
  ) {
    let corsHeaders = {
      'Access-Control-Allow-Origin': request.headers.get('Origin'),
      'Access-Control-Allow-Methods': 'GET, HEAD, POST, OPTIONS',
      'Access-Control-Allow-Headers': request.headers.get('Access-Control-Request-Headers'),
      'Access-Control-Allow-Credentials': true,
      'Vary': 'Origin',
    }
    return new Response(null, {
      headers: corsHeaders,
    })
  } else {
    // Handle standard OPTIONS request.
    // If you want to allow other HTTP Methods, you can do that here.
    return new Response(null, {
      headers: {
        Allow: 'GET, HEAD, POST, OPTIONS',
      },
    })
  }
}
addEventListener('fetch', event => {
  const request = event.request
  const url = new URL(request.url)
  // if (url.pathname.startsWith(proxyEndpoint)) {
    if (request.method === 'OPTIONS') {
      // Handle CORS preflight requests
      event.respondWith(handleOptions(request))
    } else if (
      request.method === 'GET' ||
      request.method === 'HEAD' ||
      request.method === 'POST'
    ) {
      // Handle requests to the API server
      event.respondWith(handleRequest(request))
    } else {
      event.respondWith(async () => {
        return new Response(null, {
          status: 405,
          statusText: 'Method Not Allowed',
        })
      })
    }
})

After several iterations of testing and slight adjustments to my Medium import web application everything worked 🎉.

CORS proxy security considerations

There is definitely some risk in passing your requests, especially the ones with an API token, through a proxy. Because CORS proxies operate on the layer 7 of the OSI model, they see request plaintext data, even if the original request was sent encrypted via HTTPS. Rogue proxies can steal your credentials as well as modify the request/response data in any way they wish and not only inject proper CORS headers. In case of Medium, anyone with your token can publish posts in your name and do all the other things covered by the API, so make sure understand the risk of using a CORS proxy. This is, by the way, true for any other third-pary Medium integration mentioned in this post as all of them get your API token one way or the other, and some get a GitHub one as well.

So, can you trust my proxy? I say "definitely yes", but if I was the casual reader of this post - a simple "yes" might not be enough for me. That's why for extra cautious I made the CORS proxy configurable in the UI, so you can point the app at your own instance. You can easily run one for free on Cloudflare Workers, which allows up to 100K requests per day (and I think no-one publishes 100K posts a day, so should be enough) with no need to think about applications, regions or instances. You can also opt for a more traditional approach and run a CORS anywhere-like application in some public cloud or even on premise.

Can we trust Cloudflare to run our proxy? I would be biased here to provide an opinion, so instead I would encourage interested readers to use CDN finder tools, such as this and check which CDN is used by Medium for more objective information.

If you don't want to bother with running proxies, but still not comfortable with giving away your API token, the alternative approach would be to use one-time tokens. It seems there is no limit in how many Medium tokens you can generate and you can also easily revoke any token. So the workflow would be as simple as:

generate a new integration token
publish a post using this token and any CORS proxy
immediately revoke this token afterwards

Final words

By creating this simple app I learned that writing a simple Web UI with modern Web frameworks is not that scary anymore. Please, do note, I'm not a Web developer, so if you see some non-idiomatic Javascript code, don't shame me, but provide improvement suggestions or, even better, send a pull request on GitHub.

I also learned a lot about CORS, but what I failed to understand is why many public APIs do not support it. At first glance it may seem that non-CORS API is more secure as it prevents malicious websites to impersonate users of the API. However, when a public API does not support CORS, most developers seem to turn to third-party CORS proxies, like the ones mentioned in this post, thus probably even increasing the risk of a token leak should the proxy go rogue. Please, reach out on Twitter, if you think otherwise.

If you're reading this post on Medium, it was published from Markdown using this Markdown to Medium tool. If you found it useful, send your comments or improvement suggestions on Twitter.

Using Go as a scripting language in Linux

Ignat Korchagin — Sat, 18 Apr 2020 21:40:21 +0000

This is a repost of my post from the Cloudflare Blog

At Cloudflare we like Go. We use it in many in-house software projects as well as parts of bigger pipeline systems. But can we take Go to the next level and use it as a scripting language for our favourite operating system, Linux?

gopher image CC BY 3.0 Renee French
Tux image CC0 BY OpenClipart-Vectors

Why consider Go as a scripting language

Short answer: why not? Go is relatively easy to learn, not too verbose and there is a huge ecosystem of libraries which can be reused to avoid writing all the code from scratch. Some other potential advantages it might bring:

Go-based build system for your Go project: go build command is mostly suitable for small, self-contained projects. More complex projects usually adopt some build system/set of scripts. Why not have these scripts written in Go then as well?
Easy non-privileged package management out of the box: if you want to use a third-party library in your script, you can simply go get it. And because the code will be installed in your GOPATH, getting a third-party library does not require administrative privileges on the system (unlike some other scripting languages). This is especially useful in large corporate environments.
Quick code prototyping on early project stages: when you're writing the first iteration of the code, it usually takes a lot of edits even to make it compile and you have to waste a lot of keystrokes on "edit->build->check" cycle. Instead you can skip the "build" part and just immediately execute your source file.
Strongly-typed scripting language: if you make a small typo somewhere in the middle of the script, most scripts will execute everything up to that point and fail on the typo itself. This might leave your system in an inconsistent state. With strongly-typed languages many typos can be caught at compile time, so the buggy script will not run in the first place.

Current state of Go scripting

At first glance Go scripts seem easy to implement with Unix support of shebang lines for scripts. A shebang line is the first line of the script, which starts with #! and specifies the script interpreter to be used to execute the script (for example, #!/bin/bash or #!/usr/bin/env python), so the system knows exactly how to execute the script regardless of the programming language used. And Go already supports interpreter-like invocation for .go files with go run command, so it should be just a matter of adding a proper shebang line, something like #!/usr/bin/env go run, to any .go file, setting the executable bit and we're good to go.

However, there are problems around using go run directly. This great post describes in detail all the issues around go run and potential workarounds, but the gist is:

go run does not properly return the script error code back to the operating system and this is important for scripts, because error codes are one of the most common ways multiple scripts interact with each other and the operating system environment.
you can't have a shebang line in a valid .go file, because Go does not know how to process lines starting with #. Other scripting languages do not have this problem, because for most of them # is a way to specify comments, so the final interpreter just ignores the shebang line, but Go comments start with // and go run on invocation will just produce an error like:

package main:
helloscript.go:1:1: illegal character U+0023 '#'

The post describes several workarounds for above issues including using a custom wrapper program gorun as an interpreter, but all of them do not provide an ideal solution. You either:

have to use non-standard shebang line, which starts with //. This is technically not even a shebang line, but the way how bash shell processes executable text files, so this solution is bash specific. Also, because of the specific behaviour of go run, this line is rather complex and not obvious (see original post for examples).
have to use a custom wrapper program gorun in the shebang line, which works well, however, you end up with .go files, which are not compilable with standard go build command because of the illegal # character.

How Linux executes files

OK, it seems the shebang approach does not provide us with an all-rounder solution. Is there anything else we could use? Let's take a closer look how Linux kernel executes binaries in the first place. When you try to execute a binary/script (or any file for that matter which has executable bit set), your shell in the end will just use Linux execve system call passing it the filesystem path of the binary in question, command line parameters and currently defined environment variables. Then the kernel is responsible for correct parsing of the file and creating a new process with the code from the file. Most of us know that Linux (and many other Unix-like operating systems) use ELF binary format for its executables.

However, one of the core principles of Linux kernel development is to avoid "vendor/format lock-in" for any subsystem, which is part of the kernel. Therefore, Linux implements a "pluggable" system, which allows any binary format to be supported by the kernel - all you have to do is to write a correct module, which can parse the format of your choosing. And if you take a closer look at the kernel source code, you'll see that Linux supports more binary formats out of the box. For example, for the recent 4.14 Linux kernel we can see that it supports at least 7 binary formats (in-tree modules for various binary formats usually have binfmt_ prefix in their names). It is worth to note the binfmt_script module, which is responsible for parsing above mentioned shebang lines and executing scripts on the target system (not everyone knows that the shebang support is actually implemented in the kernel itself and not in the shell or other daemon/process).

Extending supported binary formats from userspace

But since we concluded that shebang is not the best option for our Go scripting, seems we need something else. Surprisingly Linux kernel already has a "something else" binary support module, which has an appropriate name binfmt_misc. The module allows an administrator to dynamically add support for various executable formats directly from userspace through a well-defined procfs interface and is well-documented.

Let's follow the documentation and try to setup a binary format description for .go files. First of all the guide tells you to mount special binfmt_misc filesystem to /proc/sys/fs/binfmt_misc. If you're using relatively recent systemd-based Linux distribution, it is highly likely the filesystem is already mounted for you, because systemd by default installs special mount and automount units for this purpose. To double-check just run:

$ mount | grep binfmt_misc
systemd-1 on /proc/sys/fs/binfmt_misc type autofs (rw,relatime,fd=27,pgrp=1,timeout=0,minproto=5,maxproto=5,direct)

Another way is to check if you have any files in /proc/sys/fs/binfmt_misc: properly mounted binfmt_misc filesystem will create at least two special files with names register and status in that directory.

Next, since we do want our .go scripts to be able to properly pass the exit code to the operating system, we need the custom gorun wrapper as our "interpreter":

$ go get github.com/erning/gorun
$ sudo mv ~/go/bin/gorun /usr/local/bin/

Technically we don't need to move gorun to /usr/local/bin or any other system path as binfmt_misc requires full path to the interpreter anyway, but the system may run this executable with arbitrary privileges, so it is a good idea to limit access to the file from security perspective.

At this point let's create a simple toy Go script helloscript.go and verify we can successfully "interpret" it. The script:

package main

import (
    "fmt"
    "os"
)

func main() {
    s := "world"

    if len(os.Args) > 1 {
        s = os.Args[1]
    }

    fmt.Printf("Hello, %v!", s)
    fmt.Println("")

    if s == "fail" {
        os.Exit(30)
    }
}

Checking if parameter passing and error handling works as intended:

$ gorun helloscript.go
Hello, world!
$ echo $?
0
$ gorun helloscript.go gopher
Hello, gopher!
$ echo $?
0
$ gorun helloscript.go fail
Hello, fail!
$ echo $?
30

Now we need to tell binfmt_misc module how to execute our .go files with gorun. Following the documentation we need this configuration string: :golang:E::go::/usr/local/bin/gorun:OC, which basically tells the system: "if you encounter an executable file with .go extension, please, execute it with /usr/local/bin/gorun interpreter". The OC flags at the end of the string make sure, that the script will be executed according to the owner information and permission bits set on the script itself, and not the ones set on the interpreter binary. This makes Go script execution behaviour same as the rest of the executables and scripts in Linux.

Let's register our new Go script binary format:

$ echo ':golang:E::go::/usr/local/bin/gorun:OC' | sudo tee /proc/sys/fs/binfmt_misc/register
:golang:E::go::/usr/local/bin/gorun:OC

If the system successfully registered the format, a new file golang should appear under /proc/sys/fs/binfmt_misc directory. Finally, we can natively execute our .go files:

$ chmod u+x helloscript.go
$ ./helloscript.go
Hello, world!
$ ./helloscript.go gopher
Hello, gopher!
$ ./helloscript.go fail
Hello, fail!
$ echo $?
30

That's it! Now we can edit helloscript.go to our liking and see the changes will be immediately visible the next time the file is executed. Moreover, unlike the previous shebang approach, we can compile this file any time into a real executable with go build.

Fixing weak crypto in OpenSSL based applications

Ignat Korchagin — Sat, 18 Apr 2020 21:37:58 +0000

Originally published at pqsec.org

Why crypto becomes weak

No one designs weak cryptographic algorithms on purpose. Well, almost no one - sometimes state intelligence agencies try to backdoor crypto for their own purposes, but hopefully this is an exception and in general people have best intentions in mind.

So, why does some crypto suddenly become weak? All practical cryptographic algorithms are designed around some hard computational problems. That is, it is practically hard (but not impossible!) to efficiently execute the algorithm without knowing some secret information (the key). The basic assumptions of strong crypto are:

an efficient algorithm, which allows to do a specific information transformation (for example, decryption or signing) without possessing the key does not exist
all existing algorithms, which allow to do the above, require substantial resources (usually compute time and/or memory), which makes them impractical, because using current technology it will either require hundreds or thousands of years to crack a single byte or the whole world just does not have enough memory to accommodate the algorithm's state

A specific cryptographic algorithm becomes weak, when one of these assumptions or even both do not hold anymore. The first assumption might be broken, when some researcher invents and publishes an algorithm, which makes a hard computational problem not hard anymore: the published approach might significantly reduce compute/memory requirements to crack the protected information. For example, see why RC4 cipher is not used in TLS anymore.

The second assumption is broken naturally over time, mostly because of rapid technological advancements. Not only computers grow more powerful every day and more compute and memory resources are available, but also completely new technologies emerge, which allow to fully break some of the modern and most secure asymmetric cryptosystems in an instant.

Hypothetical case study

Imagine you are a security engineer at a SaaS company, which provides cloud document storage as one of its offerings. Your cloud runs a third-party proprietary software stack from some vendor. All documents in the system are indexed by their IDs, which are generated, when the document is first uploaded. Your third-party software vendor decided that the simplest way to generate this ID for a document is to just compute its SHA-1 value.

One day you come to the office and see chaos: the world is not the same anymore, because SHA-1 was officially declared broken in practice (and this part is real!). Your company reached out to the vendor to provide a fix, but, as often happens with vendors, they either said it would take them months or years to provide a fix or that the attack "is not applicable to the software security model". Either way your company disagrees and your job is to provide a hotfix, while the business is looking into alternatives.

Tool analysis

We previously agreed that the third-party vendor software is proprietary, but for the purposes of this exercise (and so you can compile and run this at home) here is the source version of the hypothetical tool:

customhash.c:

#include <stdio.h>
#include <errno.h>

#include <openssl/evp.h>
#include <openssl/sha.h>

static int hash(FILE *f)
{
    int err, i;
    unsigned char md[SHA_DIGEST_LENGTH];
    unsigned int md_size;

    unsigned char buf[4096], *pos;
    size_t bytes_read;

    pos = buf;
    bytes_read = fread(buf, 1, buf + sizeof(buf) - pos, f);
    while (bytes_read && pos < (buf + sizeof(buf)))
    {
        pos += bytes_read;
        bytes_read = fread(buf, 1, buf + sizeof(buf) - pos, f);
    }

    if (!feof(f))
    {
        errno = EIO;
        return errno;
    }

    if (!EVP_Digest(buf, pos - buf, md, &md_size, EVP_sha1(), NULL))
    {
        errno = EFAULT;
        return errno;
    }

    for (i = 0; i < md_size; i++)
        printf("%02x", md[i]);
    puts("");

    return 0;
}
int main(int argc, char **argv)
{
    int err;
    FILE *f = stdin;
    if (argc > 1) {
        f = fopen(argv[1], "rb");
        if (!f) {
            perror(NULL);
            return errno;
        }
    }

    err = hash(f);
    if (err)
        perror(NULL);

    if (argc > 1)
        fclose(f);

    return err;
}

So, in a nutshell, the tool just reads the contents of a file into a buffer and computes its SHA-1. Let's verify it works by comparing its output to a well-known SHA-1 implementation:

$ gcc -o customhash customhash.c -lcrypto
$ echo abc | ./customhash
03cfd743661f07975fa2f1220c5194cbaff48451
$ echo abc | sha1sum
03cfd743661f07975fa2f1220c5194cbaff48451  -

Works indeed. But remember: we did not compile the tool ourselves - it is proprietary. However, we can check if the tool was linked statically or dynamically and what libraries it uses in the latter case:

$ ldd ./customhash
    linux-vdso.so.1 (0x00007ffc26bea000)
    libcrypto.so.1.1 => /lib/x86_64-linux-gnu/libcrypto.so.1.1 (0x00007f6350798000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f63505d7000)
    libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f63505d2000)
    libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f63505b1000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f6350a94000)

We're in luck: it was linked dynamically and it uses OpenSSL. The reason we're focusing on OpenSSL in this post is because OpenSSL is a de-facto cryptographic library of choice in many applications, even proprietary ones, because of its maturity and permissive license.

Hooking crypto with LD_PRELOAD

LD_PRELOAD is a powerful instrument to modify the behaviour of a dynamically linked application: it is possible to override almost any library function by defining an environment variable and writing some code. In our case we want to replace SHA-1 computation in our toy proprietary tool with more secure SHA-256. But first we need to actually know which function to "hook" (replace that is):

$ nm -D ./customhash | grep 'U '
                 U __errno_location
                 U EVP_Digest
                 U EVP_sha1
                 U fclose
                 U feof
                 U fopen
                 U fread
                 U __libc_start_main
                 U perror
                 U printf
                 U puts

The above command outputs all the functions our customhash tool uses from linked dynamic libraries ("U" stands for "uses" probably). Most functions are from libc, but EVP_Digest and EVP_sha1 come from OpenSSL (if we google those, we get directed to the OpenSSL online man page). At this point we need to write a small dynamic library, which exports same functions with same signatures, but compute SHA-256 instead. In fact we need to replace only EVP_Digest as EVP_sha1 just returns the internal OpenSSL SHA-1 algorithm ID. One potential implementation might look like below:

cryptofix.c:

#define _GNU_SOURCE /* for RTLD_NEXT */
#include <dlfcn.h>
#include <stdio.h>
#include <string.h>

#include <openssl/evp.h>
#include <openssl/sha.h>

int EVP_Digest(const void *data, size_t count, unsigned char *md, unsigned int *size, const EVP_MD *type, ENGINE *impl)
{
    unsigned char sha256_md[SHA256_DIGEST_LENGTH];
    unsigned int sha256_md_size, err;

    static int (*real_fn)(const void *data, size_t count, unsigned char *md, unsigned int *size, const EVP_MD *type, ENGINE *impl) = NULL;
    if (!real_fn)
    {
        real_fn = dlsym(RTLD_NEXT, "EVP_Digest");
        if (!real_fn)
        {
            fputs("cannot find EVP_Digest", stderr);
            exit(1);
        }
    }

    if (type == EVP_sha1())
    {
        err = real_fn(data, count, sha256_md, &sha256_md_size, EVP_sha256(), impl);
        fputs("replacing SHA1 with SHA256\n", stderr);
        memcpy(md, sha256_md, SHA_DIGEST_LENGTH);
        *size = SHA_DIGEST_LENGTH;
        return err;
    }
    else
        return real_fn(data, count, md, size, type, impl);
}

There are couple of things to note from the above implementation: first of all, we need to get a pointer to the real OpenSSL EVP_Digest function, so we can forward calls to it. We obtain the address using the RTLD_NEXT trick from libdl. This is needed because EVP_Digest is a wrapper function, which computes any hash algorithm supported by OpenSSL. So we can't just replace it with a SHA-256 implementation, because the calling application might rely on different hash algorithms at once and use the same function for all of them. So in our implementation we "filter out" the calls, which request SHA-1 computations and pass the rest as is.

Secondly, we don't want to write a SHA-256 implementation ourselves. We already know that the application is using OpenSSL, so when our code runs, we have access to OpenSSL library in our process address space. Moreover, we already have OpenSSL EVP_Digest address obtained from above, so we just call OpenSSL to compute SHA-256 for us.

Finally, the output of SHA-1 is just 20 bytes, but SHA-256 produces 32 bytes. OpenSSL returns the result to the caller allocated buffer, but at this point we can't assume the calling application allocated enough memory to store the full SHA-256 result, because it is expecting a SHA-1 hash. To be safe and not introduce a buffer overflow we will strip the extra 12 bytes from the computed SHA-256 before returning the result to the caller. Some security researches may argue that truncating hash results decreases security and they will be correct. However, for this use case, it is still more secure to use a secure hash algorithm with a truncated result rather than insecure hash algorithm.

Let's check if everything works correctly:

$ gcc -shared -fPIC -o cryptofix.so ;.c
$ echo abc | LD_PRELOAD=./cryptofix.so ./customhash
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | sha256sum
edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb  -

Hurray! We successfully replaced weak SHA-1 with stronger SHA-256 without touching any code in the original application.

The vendor strikes back

While the vendor may find reasons to refuse fixing our insecure algorithm, they are obliged to fix bugs. If we examine our toy customhash.c tool, we may notice it has a bug: it can't compute hashes of files larger than 4096 bytes because of the static buffer in the hash function:

$ printf 'a%.0s' {1..4095} | ./customhash
10236568a284fb3733bd87c15280af95bd528839
$ printf 'a%.0s' {1..4096} | ./customhash
Input/output error

So the vendor fixes it and delivers the updated tool (because their code is nicely decoupled, they left the main function as is and just rewrote the hash function implementation with the same prototype):

customhashv2.c:

...
static int hash(FILE *f)
{
    int err, i;
    unsigned char md[SHA_DIGEST_LENGTH];
    unsigned int md_size;

    unsigned char buf[256];
    size_t bytes_read;

    EVP_MD_CTX *ctx = EVP_MD_CTX_new();
    if (!ctx)
    {
        errno = ENOMEM;
        return errno;
    }

    if (!EVP_DigestInit(ctx, EVP_sha1()))
    {
        EVP_MD_CTX_free(ctx);
        errno = EFAULT;
        return errno;
    }

    bytes_read = fread(buf, 1, sizeof(buf), f);
    while (bytes_read)
    {
        if (!EVP_DigestUpdate(ctx, buf, bytes_read))
        {
            EVP_MD_CTX_free(ctx);
            errno = EFAULT;
            return errno;
        }
        bytes_read = fread(buf, 1, sizeof(buf), f);
    }

    if (!feof(f))
    {
        EVP_MD_CTX_free(ctx);
        errno = EIO;
        return errno;
    }

    if (!EVP_DigestFinal(ctx, md, &md_size))
    {
        EVP_MD_CTX_free(ctx);
        errno = EFAULT;
        return errno;
    }

    for (i = 0; i < md_size; i++)
        printf("%02x", md[i]);
    puts("");

    return 0;
}
...

Let's check if it works:

$ gcc -o customhashv2 customhashv2.c -lcrypto
$ echo abc | ./customhashv2
03cfd743661f07975fa2f1220c5194cbaff48451
$ echo abc | sha1sum
03cfd743661f07975fa2f1220c5194cbaff48451  -
$ printf 'a%.0s' {1..4096} | ./customhashv2
8c51fb6a0b587ec95ca74acfa43df7539b486297
$ printf 'a%.0s' {1..4096} | sha1sum
8c51fb6a0b587ec95ca74acfa43df7539b486297  -

Good! The bug is fixed, but does our hack work:

$ echo abc | LD_PRELOAD=./cryptofix.so ./customhashv2
03cfd743661f07975fa2f1220c5194cbaff48451

We don't see our "replacing SHA1 with SHA256" message anymore and the new tool clearly computes SHA-1. This is because the updated tool uses different functions from OpenSSL to do its job and we did not hook those:

$ nm -D ./customhashv2 | grep 'U '
                 U __errno_location
                 U EVP_DigestFinal
                 U EVP_DigestInit
                 U EVP_DigestUpdate
                 U EVP_MD_CTX_free
                 U EVP_MD_CTX_new
                 U EVP_sha1
                 U fclose
                 U feof
                 U fopen
                 U fread
                 U __libc_start_main
                 U perror
                 U printf
                 U puts

To support arbitrary length files the tool now uses an interface, which processes the data iteratively. But we need to update our hooking library:

cryptofixv2.c:

#define _GNU_SOURCE /* for RTLD_NEXT */
#include <dlfcn.h>
#include <stdio.h>
#include <string.h>

#include <openssl/evp.h>
#include <openssl/sha.h>

int EVP_DigestInit(EVP_MD_CTX *ctx, const EVP_MD *type)
{
    static int (*real_fn)(EVP_MD_CTX *ctx, const EVP_MD *type) = NULL;
    if (!real_fn)
    {
        real_fn = dlsym(RTLD_NEXT, "EVP_DigestInit");
        if (!real_fn)
        {
            fputs("cannot find EVP_DigestInit", stderr);
            exit(1);
        }
    }

    if (type == EVP_sha1())
        return real_fn(ctx, EVP_sha256());
    else
        return real_fn(ctx, type);
}

int EVP_DigestFinal(EVP_MD_CTX *ctx, unsigned char *md, unsigned int *s)
{
    static int (*real_fn)(EVP_MD_CTX *ctx, unsigned char *md, unsigned int *s) = NULL;
    if (!real_fn)
    {
        real_fn = dlsym(RTLD_NEXT, "EVP_DigestFinal");
        if (!real_fn)
        {
            fputs("cannot find EVP_DigestFinal", stderr);
            exit(1);
        }
    }

    if (EVP_MD_CTX_md(ctx) == EVP_sha256())
    {
        unsigned char sha256_md[SHA256_DIGEST_LENGTH];
        unsigned int sha256_md_size, err;

        err = real_fn(ctx, sha256_md, &sha256_md_size);
        fputs("replacing SHA1 with SHA256\n", stderr);
        memcpy(md, sha256_md, SHA_DIGEST_LENGTH);
        *s = SHA_DIGEST_LENGTH;
        return err;
    }
    else
        return real_fn(ctx, md, s);
}

Now we hook two functions:

as before, in EVP_DigestInit we detect when the caller requests SHA-1 calculation and instead request SHA-256 calculation from OpenSSL
in EVP_DigestFinal we truncate the results of any SHA-256 calculation to 20 bytes and return the results to the caller

For simplicity, this implementation assumes that the calling application never requests SHA-256 hash calculations on its own. If that's not the case, the hooking library might become more complex, as we have to track somehow (for example, in a set) the OpenSSL context objects we "patched" in EVP_DigestInit, so we only truncate the original-to-be SHA-1 results in the EVP_DigestFinal.

Checking if it works:

$ gcc -shared -fPIC -o cryptofixv2.so cryptofixv2.c
$ echo abc | LD_PRELOAD=./cryptofixv2.so ./customhashv2
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | sha256sum
edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb  -

OK, we're good! Did we cover all possible cases? Here is another potential update from the vendor:

customhashv3.c:

...
static int hash(FILE *f)
{
    int err, i;
    unsigned char md[SHA_DIGEST_LENGTH];
    unsigned int md_size = sizeof(md);

    unsigned char buf[256];
    int bytes_read;

    BIO *filebio, *sha1bio;

    filebio = BIO_new_fp(f, BIO_NOCLOSE);
    if (!filebio)
    {
        errno = ENOMEM;
        return errno;
    }

    sha1bio = BIO_new(BIO_f_md());
    if (!sha1bio)
    {
        BIO_free(filebio);
        errno = ENOMEM;
        return errno;
    }

    BIO_set_md(sha1bio, EVP_sha1());
    BIO_push(sha1bio, filebio);

    bytes_read = BIO_read(sha1bio, buf, sizeof(buf));
    while (bytes_read > 0)
    {
        bytes_read = BIO_read(sha1bio, buf, sizeof(buf));
    }

    if (bytes_read < 0)
    {
        BIO_free_all(sha1bio);
        errno = EIO;
        return errno;
    }

    if (BIO_gets(sha1bio, md, sizeof(md)) <= 0)
    {
        BIO_free_all(sha1bio);
        errno = EFAULT;
        return errno;
    }

    BIO_free_all(sha1bio);

    for (i = 0; i < md_size; i++)
        printf("%02x", md[i]);
    puts("");

    return 0;
}
...

It works as the previous one:

$ gcc -o customhashv3 customhashv3.c -lcrypto
$ echo abc | ./customhashv3
03cfd743661f07975fa2f1220c5194cbaff48451

But we may already guess our hooking library will not work anymore just by looking at:

$ nm -D ./customhashv3 | grep 'U '
                 U BIO_ctrl
                 U BIO_f_md
                 U BIO_free
                 U BIO_free_all
                 U BIO_gets
                 U BIO_new
                 U BIO_new_fp
                 U BIO_push
                 U BIO_read
                 U __errno_location
                 U EVP_sha1
                 U fclose
                 U fopen
                 U __libc_start_main
                 U perror
                 U printf
                 U puts

The calling application uses yet another set of function calls to compute the SHA-1 digest and we have to come up with a new fix:

cryptofixv3.c:

#define _GNU_SOURCE /* for RTLD_NEXT */
#include <dlfcn.h>
#include <stdio.h>
#include <string.h>

#include <openssl/evp.h>
#include <openssl/sha.h>

long BIO_ctrl(BIO *bp, int cmd, long larg, void *parg)
{
    static long (*real_fn)(BIO *bp, int cmd, long larg, void *parg) = NULL;
    if (!real_fn)
    {
        real_fn = dlsym(RTLD_NEXT, "BIO_ctrl");
        if (!real_fn)
        {
            fputs("cannot find BIO_ctrl", stderr);
            exit(1);
        }
    }

    if (cmd == BIO_C_SET_MD && parg == EVP_sha1())
        return real_fn(bp, cmd, larg, (void *)EVP_sha256());
    else
        return real_fn(bp, cmd, larg, parg);
}

int BIO_gets(BIO *bp, char *buf, int size)
{
    EVP_MD *md = NULL;
    static int (*real_fn)(BIO *bp, char *buf, int size) = NULL;
    if (!real_fn)
    {
        real_fn = dlsym(RTLD_NEXT, "BIO_gets");
        if (!real_fn)
        {
            fputs("cannot find BIO_gets", stderr);
            exit(1);
        }
    }

    if (BIO_method_type(bp) == BIO_TYPE_MD && BIO_get_md(bp, &md))
    {
        if (md == EVP_sha256()) {
            char sha256_md[SHA256_DIGEST_LENGTH];
            int err;

            if (size < SHA_DIGEST_LENGTH)
                return 0;

            err = real_fn(bp, sha256_md, sizeof(sha256_md));
            fputs("replacing SHA1 with SHA256\n", stderr);
            memcpy(buf, sha256_md, size);
            return err;
        }
    }

    return real_fn(bp, buf, size);
}

It up to the reader to verify the above code works, but it is worth noting it suffers from same limitations and assumptions as v2.

At this point it is clear that OpenSSL has a rather diverse API and the same thing can be implemented in many different ways. This makes OpenSSL algorithm hooking hard as it is almost impossible to account for all cases and combinations.

OpenSSL engines to the rescue

While we can't provide reliable algorithm replacement for any cryptographic library, if the application uses OpenSSL, we can do better than above with OpenSSL engines.

OpenSSL engines are third-party extensions anyone can write to provide a custom implementation of any cryptographic algorithm. They are used primarily for two cases:

integrating different hardware cryptographic devices into OpenSSL and OpenSSL-based applications
introduce new cryptographic algorithms into OpenSSL and make them available via generic OpenSSL EVP_x API

But we will abuse the framework a bit: we will write an "alternative" implementation of SHA-1 algorithm, which will do SHA-256 computations (the code below is based on the example from OpenSSL blog):

sha1-sha256.c:

#include <string.h>

#include <openssl/engine.h>
#include <openssl/evp.h>
#include <openssl/sha.h>

static const char *engine_id = "sha1-sha256";
static const char *engine_name =
    "An engine, which converts SHA1 to SHA256 for better security";

static int digest_init(EVP_MD_CTX *ctx) {
  return SHA256_Init(EVP_MD_CTX_md_data(ctx));
}

static int digest_update(EVP_MD_CTX *ctx, const void *data, size_t count) {
  return SHA256_Update(EVP_MD_CTX_md_data(ctx), data, count);
}

static int digest_final(EVP_MD_CTX *ctx, unsigned char *md) {
  char sha256_md[SHA256_DIGEST_LENGTH];
  int err;

  err = SHA256_Final(sha256_md, EVP_MD_CTX_md_data(ctx));
  fputs("replacing SHA1 with SHA256\n", stderr);
  memcpy(md, sha256_md, SHA_DIGEST_LENGTH);
  return err;
}

static EVP_MD *digest_meth = NULL;
static int digest_nids[] = {NID_sha1, 0};
static int digests(ENGINE *e, const EVP_MD **digest, const int **nids,
                   int nid) {
  if (!digest) {
    *nids = digest_nids;
    return (sizeof(digest_nids) - 1) / sizeof(digest_nids[0]);
  }
  switch (nid) {
  case NID_sha1:
    if (digest_meth == NULL) {
      digest_meth = EVP_MD_meth_new(NID_sha1, NID_sha1WithRSAEncryption);
      if (!digest_meth) {
        return 0;
      }
      if (!EVP_MD_meth_set_result_size(digest_meth, SHA_DIGEST_LENGTH) ||
          !EVP_MD_meth_set_flags(digest_meth, EVP_MD_FLAG_DIGALGID_ABSENT) ||
          !EVP_MD_meth_set_init(digest_meth, digest_init) ||
          !EVP_MD_meth_set_update(digest_meth, digest_update) ||
          !EVP_MD_meth_set_final(digest_meth, digest_final) ||
          !EVP_MD_meth_set_cleanup(digest_meth, NULL) ||
          !EVP_MD_meth_set_ctrl(digest_meth, NULL) ||
          !EVP_MD_meth_set_input_blocksize(digest_meth, SHA_CBLOCK) ||
          !EVP_MD_meth_set_app_datasize(
              digest_meth, sizeof(EVP_MD *) + sizeof(SHA256_CTX)) ||
          !EVP_MD_meth_set_copy(digest_meth, NULL)) {

        goto err;
      }
    }
    *digest = digest_meth;
    return 1;
  default:
    *digest = NULL;
    return 0;
  }

err:
  if (digest_meth) {
    EVP_MD_meth_free(digest_meth);
    digest_meth = NULL;
  }
  return 0;
}

static int engine_init(ENGINE *e) {
  return 1;
}

static int engine_finish(ENGINE *e) {
  if (digest_meth) {
    EVP_MD_meth_free(digest_meth);
    digest_meth = NULL;
  }
  return 1;
}

static int bind(ENGINE *e, const char *id) {
  if (!ENGINE_set_id(e, engine_id)) {
    goto err;
  }
  if (!ENGINE_set_name(e, engine_name)) {
    goto err;
  }
  if (!ENGINE_set_init_function(e, engine_init)) {
    goto err;
  }
  if (!ENGINE_set_finish_function(e, engine_finish)) {
    goto err;
  }
  if (!ENGINE_set_digests(e, digests)) {
    goto err;
  }
  return 1;
err:
  return 0;
}

IMPLEMENT_DYNAMIC_BIND_FN(bind)
IMPLEMENT_DYNAMIC_CHECK_FN()

The engine above declares itself to OpenSSL as a SHA-1 implementation, but reuses the OpenSSL itself and calculates SHA-256 instead. It also truncates the output to 20 bytes not to confuse applications expecting a SHA-1 result. Let's test it:

$ gcc -shared -fPIC -o cryptofix_engine.so sha1-sha256.c
$ echo abc | openssl sha1
(stdin)= 03cfd743661f07975fa2f1220c5194cbaff48451
$ echo abc | openssl sha1 -engine ./cryptofix_engine.so
engine "sha1-sha256" set.
replacing SHA1 with SHA256
(stdin)= edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | sha256sum
edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb  -

Seems working as expected. Let's try it with our proprietary tool:

$ echo abc | LD_PRELOAD=./cryptofix_engine.so ./customhashv3
03cfd743661f07975fa2f1220c5194cbaff48451

Hmm... Nothing changed: we don't get our debug message and still have a SHA-1 as a result. The reason is: to make the engine available we also need to call some OpenSSL API to load and configure it! So not all OpenSSL based applications are engine aware. Obviously, the command line openssl utility we used above is: the engine config API is invoked when we specify the -engine parameter. There are others, like NGINX and OpenVPN - they have some directives in the configuration files, where the user can specify the desired OpenSSL engine. But most are not - developers just use OpenSSL as a crypto library and don't expect users to replace the crypto algorithms.

Injecting code on process startup

As we established above our custom tool is not OpenSSL engine aware, so we somehow need to make it call the OpenSSL engine configuration API before it starts computing its first SHA-1. We could probably hook some other function, even from libc, and hope it will be used before the OpenSSL ones, but we would be subject to the above problem of a vendor update potentially breaking our hotfix.

A better way is to just implement the desired engine configuration in a function and mark it as an "initialisation routine":

autoload.c:

#define _GNU_SOURCE /* for dladdr and Dl_info */
#include <dlfcn.h>
#include <stdio.h>

#include <openssl/engine.h>

static void fatal(const char *msg) {
  fputs(msg, stderr);
  exit(1);
}

static __attribute__((constructor)) void engine_preload(void) {
  // OpenSSL dynamic engine needs a filesystem path to the engine
  // so we determine our own filesystem path first
  Dl_info dinfo;
  int res = dladdr((const void *)engine_preload, &dinfo);
  if (0 == res) {
    fatal("failed to query engine module info");
  }
  if (NULL == dinfo.dli_fname) {
    fatal("failed to determine engine filesystem path");
  }
  ENGINE_load_dynamic();
  ENGINE *e = ENGINE_by_id("dynamic");
  if (NULL == e) {
    fatal("failed to load OpenSSL dynamic engine");
  }

  res = ENGINE_ctrl_cmd_string(e, "SO_PATH", dinfo.dli_fname, 0);
  if (res <= 0) {
    fatal("failed to set SO_PATH parameter for dynamic engine");
  }
  res = ENGINE_ctrl_cmd_string(e, "ID", "sha1-sha256", 0);
  if (res <= 0) {
    fatal("failed to set ID parameter for dynamic engine");
  }
  res = ENGINE_ctrl_cmd_string(e, "LOAD", NULL, 0);
  if (res <= 0) {
    fatal("failed to LOAD sha1-sha256 engine");
  }
  res = ENGINE_set_default(e, ENGINE_METHOD_ALL);
  if (res <= 0) {
    fatal("failed to set algorithms from sha1-sha256 engine as default");
  }
}

OpenSSL engine configuration API needs a filesystem path to the desired engine. We assume that the above code will be part of our cryptofix_engine.so library, so we just get the filesystem path for the currently executing module and pass it to the OpenSSL engine configuration API. But the magic here is in the function declaration: notice the __attribute__((constructor)) in the prototype. It marks this code as an "initialisation routine", so it will be automatically executed on process startup even before the main function. And the beauty of this approach is that we don't rely on hooking any function in the target application. In fact, this code will always be executed regardless of the application logic as long as the application loads our shared library.

Let's recompile our cryptofix_engine.so including this function and test it:

$ gcc -shared -fPIC -o cryptofix_engine.so autoload.c sha1-sha256.c
$ echo abc | LD_PRELOAD=./cryptofix_engine.so ./customhashv3
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | sha256sum
edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb  -

It worked! But because we replaced the algorithm via an OpenSSL engine it also works for every previous version of the tool and most likely for any future one:

$ echo abc | LD_PRELOAD=./cryptofix_engine.so ./customhashv2
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | LD_PRELOAD=./cryptofix_engine.so ./customhash
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3

So our hotfix is much more reliable now and future-proof.

Getting rid of LD_PRELOAD

So far we have a reliable hotfix for our weak proprietary hasing tool, however we need to ensure our code will always be loaded by specifying the LD_PRELOAD environment variable, when the tool is being executed. This is not only error prone (we might just forget to define the variable, when invoking the tool), but also does not work in all cases (for example, the environment variable is ignored when invoking executables with setuid/setgid bit set).

We can permanently patch the custom tool without recompiling it and add our cryptofix_engine.so shared library as a runtime dependency:

$ patchelf --add-needed ./cryptofix_engine.so ./customhashv3
$ ldd ./customhashv3
    linux-vdso.so.1 (0x00007ffd40977000)
    ./cryptofix_engine.so (0x00007faf1d1ce000)
    libcrypto.so.1.1 => /lib/x86_64-linux-gnu/libcrypto.so.1.1 (0x00007faf1ced9000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007faf1cd18000)
    libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007faf1cd13000)
    libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007faf1ccf2000)
    /lib64/ld-linux-x86-64.so.2 (0x00007faf1d1db000)

From now on our cryptofix_engine.so will be part of the customhashv3 tool and will always be loaded, when executing the binary even without any LD_PRELOAD definitions:

$ echo abc | ./customhashv3
replacing SHA1 with SHA256
edeaaff3f1774ad2888673770c6d64097e391bc3
$ echo abc | sha256sum
edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb  -

Conclusions

This post, although based on imaginary scenario, reflects some of the real world use cases and experiences. It also covers some powerful runtime code patching approaches, which are useful even without the need to replace weak crypto in proprietary code and can be adopted separately or together. All code from the post is published here.

Speeding up Linux disk encryption

Ignat Korchagin — Sat, 18 Apr 2020 21:31:09 +0000

This is a repost of my post from the Cloudflare Blog

Data encryption at rest is a must-have for any modern Internet company. Many companies, however, don't encrypt their disks, because they fear the potential performance penalty caused by encryption overhead.

Encrypting data at rest is vital for Cloudflare with more than 200 data centres across the world. In this post, we will investigate the performance of disk encryption on Linux and explain how we made it at least two times faster for ourselves and our customers!

Encrypting data at rest

When it comes to encrypting data at rest there are several ways it can be implemented on a modern operating system (OS). Available techniques are tightly coupled with a typical OS storage stack. A simplified version of the storage stack and encryption solutions can be found on the diagram below:

On the top of the stack are applications, which read and write data in files (or streams). The file system in the OS kernel keeps track of which blocks of the underlying block device belong to which files and translates these file reads and writes into block reads and writes, however the hardware specifics of the underlying storage device is abstracted away from the filesystem. Finally, the block subsystem actually passes the block reads and writes to the underlying hardware using appropriate device drivers.

The concept of the storage stack is actually similar to the well-known network OSI model, where each layer has a more high-level view of the information and the implementation details of the lower layers are abstracted away from the upper layers. And, similar to the OSI model, one can apply encryption at different layers (think about TLS vs IPsec or a VPN).

For data at rest we can apply encryption either at the block layers (either in hardware or in software) or at the file level (either directly in applications or in the filesystem).

Block vs file encryption

Generally, the higher in the stack we apply encryption, the more flexibility we have. With application level encryption the application maintainers can apply any encryption code they please to any particular data they need. The downside of this approach is they actually have to implement it themselves and encryption in general is not very developer-friendly: one has to know the ins and outs of a specific cryptographic algorithm, properly generate keys, nonces, IVs etc. Additionally, application level encryption does not leverage OS-level caching and Linux page cache in particular: each time the application needs to use the data, it has to either decrypt it again, wasting CPU cycles, or implement its own decrypted “cache”, which introduces more complexity to the code.

File system level encryption makes data encryption transparent to applications, because the file system itself encrypts the data before passing it to the block subsystem, so files are encrypted regardless if the application has crypto support or not. Also, file systems can be configured to encrypt only a particular directory or have different keys for different files. This flexibility, however, comes at a cost of a more complex configuration. File system encryption is also considered less secure than block device encryption as only the contents of the files are encrypted. Files also have associated metadata, like file size, the number of files, the directory tree layout etc., which are still visible to a potential adversary.

Encryption down at the block layer (often referred to as disk encryption or full disk encryption) also makes data encryption transparent to applications and even whole file systems. Unlike file system level encryption it encrypts all data on the disk including file metadata and even free space. It is less flexible though - one can only encrypt the whole disk with a single key, so there is no per-directory, per-file or per-user configuration. From the crypto perspective, not all cryptographic algorithms can be used as the block layer doesn't have a high-level overview of the data anymore, so it needs to process each block independently. Most common algorithms require some sort of block chaining to be secure, so are not applicable to disk encryption. Instead, special modes were developed just for this specific use-case.

So which layer to choose? As always, it depends... Application and file system level encryption are usually the preferred choice for client systems because of the flexibility. For example, each user on a multi-user desktop may want to encrypt their home directory with a key they own and leave some shared directories unencrypted. On the contrary, on server systems, managed by SaaS/PaaS/IaaS companies (including Cloudflare) the preferred choice is configuration simplicity and security - with full disk encryption enabled any data from any application is automatically encrypted with no exceptions or overrides. We believe that all data needs to be protected without sorting it into "important" vs "not important" buckets, so the selective flexibility the upper layers provide is not needed.

Hardware vs software disk encryption

When encrypting data at the block layer it is possible to do it directly in the storage hardware, if the hardware supports it. Doing so usually gives better read/write performance and consumes less resources from the host. However, since most hardware firmware is proprietary, it does not receive as much attention and review from the security community. In the past this led to flaws in some implementations of hardware disk encryption, which render the whole security model useless. Microsoft, for example, started to prefer software-based disk encryption since then.

We didn't want to put our data and our customers' data to the risk of using potentially insecure solutions and we strongly believe in open-source. That's why we rely only on software disk encryption in the Linux kernel, which is open and has been audited by many security professionals across the world.

Linux disk encryption performance

We aim not only to save bandwidth costs for our customers, but to deliver content to Internet users as fast as possible.

At one point we noticed that our disks were not as fast as we would like them to be. Some profiling as well as a quick A/B test pointed to Linux disk encryption. Because not encrypting the data (even if it is supposed-to-be a public Internet cache) is not a sustainable option, we decided to take a closer look into Linux disk encryption performance.

Device mapper and dm-crypt

Linux implements transparent disk encryption via a dm-crypt module and dm-crypt itself is part of device mapper kernel framework. In a nutshell, the device mapper allows pre/post-process IO requests as they travel between the file system and the underlying block device.

dm-crypt in particular encrypts "write" IO requests before sending them further down the stack to the actual block device and decrypts "read" IO requests before sending them up to the file system driver. Simple and easy! Or is it?

Benchmarking setup

For the record, the numbers in this post were obtained by running specified commands on an idle Cloudflare G9 server out of production. However, the setup should be easily reproducible on any modern x86 laptop.

Generally, benchmarking anything around a storage stack is hard because of the noise introduced by the storage hardware itself. Not all disks are created equal, so for the purpose of this post we will use the fastest disks available out there - that is no disks.

Instead Linux has an option to emulate a disk directly in RAM. Since RAM is much faster than any persistent storage, it should introduce little bias in our results.

The following command creates a 4GB ramdisk:

$ sudo modprobe brd rd_nr=1 rd_size=4194304
$ ls /dev/ram0

Now we can set up a dm-crypt instance on top of it thus enabling encryption for the disk. First, we need to generate the disk encryption key, "format" the disk and specify a password to unlock the newly generated key.

$ fallocate -l 2M crypthdr.img
$ sudo cryptsetup luksFormat /dev/ram0 --header crypthdr.img

WARNING!
========
This will overwrite data on crypthdr.img irrevocably.

Are you sure? (Type uppercase yes): YES
Enter passphrase:
Verify passphrase:

Those who are familiar with LUKS/dm-crypt might have noticed we used a LUKS detached header here. Normally, LUKS stores the password-encrypted disk encryption key on the same disk as the data, but since we want to compare read/write performance between encrypted and unencrypted devices, we might accidentally overwrite the encrypted key during our benchmarking later. Keeping the encrypted key in a separate file avoids this problem for the purposes of this post.

Now, we can actually "unlock" the encrypted device for our testing:

$ sudo cryptsetup open --header crypthdr.img /dev/ram0 encrypted-ram0
Enter passphrase for /dev/ram0:
$ ls /dev/mapper/encrypted-ram0
/dev/mapper/encrypted-ram0

At this point we can now compare the performance of encrypted vs unencrypted ramdisk: if we read/write data to /dev/ram0, it will be stored in plaintext. Likewise, if we read/write data to /dev/mapper/encrypted-ram0, it will be decrypted/encrypted on the way by dm-crypt and stored in ciphertext.

It's worth noting that we're not creating any file system on top of our block devices to avoid biasing results with a file system overhead.

Measuring throughput

When it comes to storage testing/benchmarking Flexible I/O tester is the usual go-to solution. Let's simulate simple sequential read/write load with 4K block size on the ramdisk without encryption:

$ sudo fio --filename=/dev/ram0 --readwrite=readwrite --bs=4k --direct=1 --loops=1000000 --name=plain
plain: (g=0): rw=rw, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.16
Starting 1 process
...
Run status group 0 (all jobs):
   READ: io=21013MB, aggrb=1126.5MB/s, minb=1126.5MB/s, maxb=1126.5MB/s, mint=18655msec, maxt=18655msec
  WRITE: io=21023MB, aggrb=1126.1MB/s, minb=1126.1MB/s, maxb=1126.1MB/s, mint=18655msec, maxt=18655msec

Disk stats (read/write):
  ram0: ios=0/0, merge=0/0, ticks=0/0, in_queue=0, util=0.00%

The above command will run for a long time, so we just stop it after a while. As we can see from the stats, we're able to read and write roughly with the same throughput around 1126 MB/s. Let's repeat the test with the encrypted ramdisk:

$ sudo fio --filename=/dev/mapper/encrypted-ram0 --readwrite=readwrite --bs=4k --direct=1 --loops=1000000 --name=crypt
crypt: (g=0): rw=rw, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.16
Starting 1 process
...
Run status group 0 (all jobs):
   READ: io=1693.7MB, aggrb=150874KB/s, minb=150874KB/s, maxb=150874KB/s, mint=11491msec, maxt=11491msec
  WRITE: io=1696.4MB, aggrb=151170KB/s, minb=151170KB/s, maxb=151170KB/s, mint=11491msec, maxt=11491msec

Whoa, that's a drop! We only get ~147 MB/s now, which is more than 7 times slower! And this is on a totally idle machine!

Maybe, crypto is just slow

The first thing we considered is to ensure we use the fastest crypto. cryptsetup allows us to benchmark all the available crypto implementations on the system to select the best one:

$ sudo cryptsetup benchmark
# Tests are approximate using memory only (no storage IO).
PBKDF2-sha1      1340890 iterations per second for 256-bit key
PBKDF2-sha256    1539759 iterations per second for 256-bit key
PBKDF2-sha512    1205259 iterations per second for 256-bit key
PBKDF2-ripemd160  967321 iterations per second for 256-bit key
PBKDF2-whirlpool  720175 iterations per second for 256-bit key
#  Algorithm | Key |  Encryption |  Decryption
     aes-cbc   128b   969.7 MiB/s  3110.0 MiB/s
 serpent-cbc   128b           N/A           N/A
 twofish-cbc   128b           N/A           N/A
     aes-cbc   256b   756.1 MiB/s  2474.7 MiB/s
 serpent-cbc   256b           N/A           N/A
 twofish-cbc   256b           N/A           N/A
     aes-xts   256b  1823.1 MiB/s  1900.3 MiB/s
 serpent-xts   256b           N/A           N/A
 twofish-xts   256b           N/A           N/A
     aes-xts   512b  1724.4 MiB/s  1765.8 MiB/s
 serpent-xts   512b           N/A           N/A
 twofish-xts   512b           N/A           N/A

It seems aes-xts with a 256-bit data encryption key is the fastest here. But which one are we actually using for our encrypted ramdisk?

$ sudo dmsetup table /dev/mapper/encrypted-ram0
0 8388608 crypt aes-xts-plain64 0000000000000000000000000000000000000000000000000000000000000000 0 1:0 0

We do use aes-xts with a 256-bit data encryption key (count all the zeroes conveniently masked by dmsetup tool - if you want to see the actual bytes, add the --showkeys option to the above command). The numbers do not add up however: cryptsetup benchmark tells us above not to rely on the results, as "Tests are approximate using memory only (no storage IO)", but that is exactly how we've set up our experiment using the ramdisk. In a somewhat worse case (assuming we're reading all the data and then encrypting/decrypting it sequentially with no parallelism) doing back-of-the-envelope calculation we should be getting around (1126 * 1823) / (1126 + 1823) =~696 MB/s, which is still quite far from the actual 147 * 2 = 294 MB/s (total for reads and writes).

dm-crypt performance flags

While reading the cryptsetup man page we noticed that it has two options prefixed with --perf-, which are probably related to performance tuning. The first one is --perf-same_cpu_crypt with a rather cryptic description:

Perform encryption using the same cpu that IO was submitted on.  The default is to use an unbound workqueue so that encryption work is automatically balanced between available CPUs.  This option is only relevant for open action.

So we enable the option

$ sudo cryptsetup close encrypted-ram0
$ sudo cryptsetup open --header crypthdr.img --perf-same_cpu_crypt /dev/ram0 encrypted-ram0

Note: according to the latest man page there is also a cryptsetup refresh command, which can be used to enable these options live without having to "close" and "re-open" the encrypted device. Our cryptsetup however didn't support it yet.

Verifying if the option has been really enabled:

$ sudo dmsetup table encrypted-ram0
0 8388608 crypt aes-xts-plain64 0000000000000000000000000000000000000000000000000000000000000000 0 1:0 0 1 same_cpu_crypt

Yes, we can now see same_cpu_crypt in the output, which is what we wanted. Let's rerun the benchmark:

$ sudo fio --filename=/dev/mapper/encrypted-ram0 --readwrite=readwrite --bs=4k --direct=1 --loops=1000000 --name=crypt
crypt: (g=0): rw=rw, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.16
Starting 1 process
...
Run status group 0 (all jobs):
   READ: io=1596.6MB, aggrb=139811KB/s, minb=139811KB/s, maxb=139811KB/s, mint=11693msec, maxt=11693msec
  WRITE: io=1600.9MB, aggrb=140192KB/s, minb=140192KB/s, maxb=140192KB/s, mint=11693msec, maxt=11693msec

Hmm, now it is ~136 MB/s which is slightly worse than before, so no good. What about the second option --perf-submit_from_crypt_cpus:

Disable offloading writes to a separate thread after encryption.  There are some situations where offloading write bios from the encryption threads to a single thread degrades performance significantly.  The default is to offload write bios to the same thread.  This option is only relevant for open action.

Maybe, we are in the "some situation" here, so let's try it out:

$ sudo cryptsetup close encrypted-ram0
$ sudo cryptsetup open --header crypthdr.img --perf-submit_from_crypt_cpus /dev/ram0 encrypted-ram0
Enter passphrase for /dev/ram0:
$ sudo dmsetup table encrypted-ram0
0 8388608 crypt aes-xts-plain64 0000000000000000000000000000000000000000000000000000000000000000 0 1:0 0 1 submit_from_crypt_cpus

And now the benchmark:

$ sudo fio --filename=/dev/mapper/encrypted-ram0 --readwrite=readwrite --bs=4k --direct=1 --loops=1000000 --name=crypt
crypt: (g=0): rw=rw, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.16
Starting 1 process
...
Run status group 0 (all jobs):
   READ: io=2066.6MB, aggrb=169835KB/s, minb=169835KB/s, maxb=169835KB/s, mint=12457msec, maxt=12457msec
  WRITE: io=2067.7MB, aggrb=169965KB/s, minb=169965KB/s, maxb=169965KB/s, mint=12457msec, maxt=12457msec

~166 MB/s, which is a bit better, but still not good...

Asking the community

Being desperate we decided to seek support from the Internet and posted our findings to the dm-crypt mailing list, but the response we got was not very encouraging:

If the numbers disturb you, then this is from lack of understanding on your side. You are probably unaware that encryption is a heavy-weight operation...

We decided to make a scientific research on this topic by typing "is encryption expensive" into Google Search and one of the top results, which actually contains meaningful measurements, is... our own post about cost of encryption, but in the context of TLS! This is a fascinating read on its own, but the gist is: modern crypto on modern hardware is very cheap even at Cloudflare scale (doing millions of encrypted HTTP requests per second). In fact, it is so cheap that Cloudflare was the first provider to offer free SSL/TLS for everyone.

Digging into the source code

When trying to use the custom dm-crypt options described above we were curious why they exist in the first place and what is that "offloading" all about. Originally we expected dm-crypt to be a simple "proxy", which just encrypts/decrypts data as it flows through the stack. Turns out dm-crypt does more than just encrypting memory buffers and a (simplified) IO traverse path diagram is presented below:

When the file system issues a write request, dm-crypt does not process it immediately - instead it puts it into a workqueue named "kcryptd". In a nutshell, a kernel workqueue just schedules some work (encryption in this case) to be performed at some later time, when it is more convenient. When "the time" comes, dm-crypt sends the request to Linux Crypto API for actual encryption. However, modern Linux Crypto API is asynchronous as well, so depending on which particular implementation your system will use, most likely it will not be processed immediately, but queued again for "later time". When Linux Crypto API will finally do the encryption, dm-crypt may try to sort pending write requests by putting each request into a red-black tree. Then a separate kernel thread again at "some time later" actually takes all IO requests in the tree and sends them down the stack.

Now for read requests: this time we need to get the encrypted data first from the hardware, but dm-crypt does not just ask for the driver for the data, but queues the request into a different workqueue named "kcryptd_io". At some point later, when we actually have the encrypted data, we schedule it for decryption using the now familiar "kcryptd" workqueue. "kcryptd" will send the request to Linux Crypto API, which may decrypt the data asynchronously as well.

To be fair the request does not always traverse all these queues, but the important part here is that write requests may be queued up to 4 times in dm-crypt and read requests up to 3 times. At this point we were wondering if all this extra queueing can cause any performance issues. For example, there is a nice presentation from Google about the relationship between queueing and tail latency. One key takeaway from the presentation is:

A significant amount of tail latency is due to queueing effects

So, why are all these queues there and can we remove them?

Git archeology

No-one writes more complex code just for fun, especially for the OS kernel. So all these queues must have been put there for a reason. Luckily, the Linux kernel source is managed by git, so we can try to retrace the changes and the decisions around them.

The "kcryptd" workqueue was in the source since the beginning of the available history with the following comment:

Needed because it would be very unwise to do decryption in an interrupt context, so bios returning from read requests get queued here.

So it was for reads only, but even then - why do we care if it is interrupt context or not, if Linux Crypto API will likely use a dedicated thread/queue for encryption anyway? Well, back in 2005 Crypto API was not asynchronous, so this made perfect sense.

In 2006 dm-crypt started to use the "kcryptd" workqueue not only for encryption, but for submitting IO requests:

This patch is designed to help dm-crypt comply with the new constraints imposed by the following patch in -mm: md-dm-reduce-stack-usage-with-stacked-block-devices.patch

It seems the goal here was not to add more concurrency, but rather reduce kernel stack usage, which makes sense again as the kernel has a common stack across all the code, so it is a quite limited resource. It is worth noting, however, that the Linux kernel stack has been expanded in 2014 for x86 platforms, so this might not be a problem anymore.

A first version of "kcryptd_io" workqueue was added in 2007 with the intent to avoid:

starvation caused by many requests waiting for memory allocation...

The request processing was bottlenecking on a single workqueue here, so the solution was to add another one. Makes sense.

We are definitely not the first ones experiencing performance degradation because of extensive queueing: in 2011 a change was introduced to conditionally revert some of the queueing for read requests:

If there is enough memory, code can directly submit bio instead queuing this operation in a separate thread.

Unfortunately, at that time Linux kernel commit messages were not as verbose as today, so there is no performance data available.

In 2015 dm-crypt started to sort writes in a separate "dmcrypt_write" thread before sending them down the stack:

On a multiprocessor machine, encryption requests finish in a different order than they were submitted. Consequently, write requests would be submitted in a different order and it could cause severe performance degradation.

It does make sense as sequential disk access used to be much faster than the random one and dm-crypt was breaking the pattern. But this mostly applies to spinning disks, which were still dominant in 2015. It may not be as important with modern fast SSDs (including NVME SSDs).

Another part of the commit message is worth mentioning:

...in particular it enables IO schedulers like CFQ to sort more effectively...

It mentions the performance benefits for the CFQ IO scheduler, but Linux schedulers have improved since then to the point that CFQ scheduler has been removed from the kernel in 2018.

The same patchset replaces the sorting list with a red-black tree:

In theory the sorting should be performed by the underlying disk scheduler, however, in practice the disk scheduler only accepts and sorts a finite number of requests. To allow the sorting of all requests, dm-crypt needs to implement its own sorting.

The overhead associated with rbtree-based sorting is considered negligible so it is not used conditionally.

All that make sense, but it would be nice to have some backing data.

Interestingly, in the same patchset we see the introduction of our familiar "submit_from_crypt_cpus" option:

There are some situations where offloading write bios from the encryption threads to a single thread degrades performance significantly

Overall, we can see that every change was reasonable and needed, however things have changed since then:

hardware became faster and smarter
Linux resource allocation was revisited
coupled Linux subsystems were rearchitected

And many of the design choices above may not be applicable to modern Linux.

The "clean-up"

Based on the research above we decided to try to remove all the extra queueing and asynchronous behaviour and revert dm-crypt to its original purpose: simply encrypt/decrypt IO requests as they pass through. But for the sake of stability and further benchmarking we ended up not removing the actual code, but rather adding yet another dm-crypt option, which bypasses all the queues/threads, if enabled. The flag allows us to switch between the current and new behaviour at runtime under full production load, so we can easily revert our changes should we see any side-effects. The resulting patch can be found on the Cloudflare GitHub Linux repository.

Synchronous Linux Crypto API

From the diagram above we remember that not all queueing is implemented in dm-crypt. Modern Linux Crypto API may also be asynchronous and for the sake of this experiment we want to eliminate queues there as well. What does "may be" mean, though? The OS may contain different implementations of the same algorithm (for example, hardware-accelerated AES-NI on x86 platforms and generic C-code AES implementations). By default the system chooses the "best" one based on the configured algorithm priority. dm-crypt allows overriding this behaviour and request a particular cipher implementation using the capi: prefix. However, there is one problem. Let us actually check the available AES-XTS (this is our disk encryption cipher, remember?) implementations on our system:

$ grep -A 11 'xts(aes)' /proc/crypto
name         : xts(aes)
driver       : xts(ecb(aes-generic))
module       : kernel
priority     : 100
refcnt       : 7
selftest     : passed
internal     : no
type         : skcipher
async        : no
blocksize    : 16
min keysize  : 32
max keysize  : 64
--
name         : __xts(aes)
driver       : cryptd(__xts-aes-aesni)
module       : cryptd
priority     : 451
refcnt       : 1
selftest     : passed
internal     : yes
type         : skcipher
async        : yes
blocksize    : 16
min keysize  : 32
max keysize  : 64
--
name         : xts(aes)
driver       : xts-aes-aesni
module       : aesni_intel
priority     : 401
refcnt       : 1
selftest     : passed
internal     : no
type         : skcipher
async        : yes
blocksize    : 16
min keysize  : 32
max keysize  : 64
--
name         : __xts(aes)
driver       : __xts-aes-aesni
module       : aesni_intel
priority     : 401
refcnt       : 7
selftest     : passed
internal     : yes
type         : skcipher
async        : no
blocksize    : 16
min keysize  : 32
max keysize  : 64

We want to explicitly select a synchronous cipher from the above list to avoid queueing effects in threads, but the only two supported are xts(ecb(aes-generic)) (the generic C implementation) and __xts-aes-aesni (the x86 hardware-accelerated implementation). We definitely want the latter as it is much faster (we're aiming for performance here), but it is suspiciously marked as internal (see internal: yes). If we check the source code:

Mark a cipher as a service implementation only usable by another cipher and never by a normal user of the kernel crypto API

So this cipher is meant to be used only by other wrapper code in the Crypto API and not outside it. In practice this means, that the caller of the Crypto API needs to explicitly specify this flag, when requesting a particular cipher implementation, but dm-crypt does not do it, because by design it is not part of the Linux Crypto API, rather an "external" user. We already patch the dm-crypt module, so we could as well just add the relevant flag. However, there is another problem with AES-NI in particular: x86 FPU. "Floating point" you say? Why do we need floating point math to do symmetric encryption which should only be about bit shifts and XOR operations? We don't need the math, but AES-NI instructions use some of the CPU registers, which are dedicated to the FPU. Unfortunately the Linux kernel does not always preserve these registers in interrupt context for performance reasons (saving/restoring FPU is expensive). But dm-crypt may execute code in interrupt context, so we risk corrupting some other process data and we go back to "it would be very unwise to do decryption in an interrupt context" statement in the original code.

Our solution to address the above was to create another somewhat "smart" Crypto API module. This module is synchronous and does not roll its own crypto, but is just a "router" of encryption requests:

if we can use the FPU (and thus AES-NI) in the current execution context, we just forward the encryption request to the faster, "internal" __xts-aes-aesni implementation (and we can use it here, because now we are part of the Crypto API)
otherwise, we just forward the encryption request to the slower, generic C-based xts(ecb(aes-generic)) implementation

Using the whole lot

Let's walk through the process of using it all together. The first step is to grab the patches and recompile the kernel (or just compile dm-crypt and our xtsproxy modules).

Next, let's restart our IO workload in a separate terminal, so we can make sure we can reconfigure the kernel at runtime under load:

$ sudo fio --filename=/dev/mapper/encrypted-ram0 --readwrite=readwrite --bs=4k --direct=1 --loops=1000000 --name=crypt
crypt: (g=0): rw=rw, bs=4K-4K/4K-4K/4K-4K, ioengine=psync, iodepth=1
fio-2.16
Starting 1 process
...

In the main terminal make sure our new Crypto API module is loaded and available:

$ sudo modprobe xtsproxy
$ grep -A 11 'xtsproxy' /proc/crypto
driver       : xts-aes-xtsproxy
module       : xtsproxy
priority     : 0
refcnt       : 0
selftest     : passed
internal     : no
type         : skcipher
async        : no
blocksize    : 16
min keysize  : 32
max keysize  : 64
ivsize       : 16
chunksize    : 16

Reconfigure the encrypted disk to use our newly loaded module and enable our patched dm-crypt flag (we have to use low-level dmsetup tool as cryptsetup obviously is not aware of our modifications):

$ sudo dmsetup table encrypted-ram0 --showkeys | sed 's/aes-xts-plain64/capi:xts-aes-xtsproxy-plain64/' | sed 's/$/ 1 force_inline/' | sudo dmsetup reload encrypted-ram0

We just "loaded" the new configuration, but for it to take effect, we need to suspend/resume the encrypted device:

$ sudo dmsetup suspend encrypted-ram0 && sudo dmsetup resume encrypted-ram0

And now observe the result. We may go back to the other terminal running the fio job and look at the output, but to make things nicer, here's a snapshot of the observed read/write throughput in Grafana:

Wow, we have more than doubled the throughput! With the total throughput of ~640 MB/s we're now much closer to the expected ~696 MB/s from above. What about the IO latency? (The await statistic from the iostat reporting tool):

The latency has been cut in half as well!

To production

So far we have been using a synthetic setup with some parts of the full production stack missing, like file systems, real hardware and most importantly, production workload. To ensure we’re not optimising imaginary things, here is a snapshot of the production impact these changes bring to the caching part of our stack:

This graph represents a three-way comparison of the worst-case response times (99th percentile) for a cache hit in one of our servers. The green line is from a server with unencrypted disks, which we will use as baseline. The red line is from a server with encrypted disks with the default Linux disk encryption implementation and the blue line is from a server with encrypted disks and our optimisations enabled. As we can see the default Linux disk encryption implementation has a significant impact on our cache latency in worst case scenarios, whereas the patched implementation is indistinguishable from not using encryption at all. In other words the improved encryption implementation does not have any impact at all on our cache response speed, so we basically get it for free! That’s a win!

We're just getting started

This post shows how an architecture review can double the performance of a system. Also we reconfirmed that modern cryptography is not expensive and there is usually no excuse not to protect your data.

We are going to submit this work for inclusion in the main kernel source tree, but most likely not in its current form. Although the results look encouraging we have to remember that Linux is a highly portable operating system: it runs on powerful servers as well as small resource constrained IoT devices and on many other CPU architectures as well. The current version of the patches just optimises disk encryption for a particular workload on a particular architecture, but Linux needs a solution which runs smoothly everywhere.

That said, if you think your case is similar and you want to take advantage of the performance improvements now, you may grab the patches and hopefully provide feedback. The runtime flag makes it easy to toggle the functionality on the fly and a simple A/B test may be performed to see if it benefits any particular case or setup. These patches have been running across our wide network of more than 200 data centres on five generations of hardware, so can be reasonably considered stable. Enjoy both performance and security from Cloudflare for all!

Update (October 11, 2020)

The main patch from this blog (in a slightly updated form) has been merged into mainline Linux kernel and is available since version 5.9 and onwards. The main difference is the mainline version exposes two flags instead of one, which provide the ability to bypass dm-crypt workqueues for reads and writes independently. For details, see the official dm-crypt documentation.

DEV Community: Ignat Korchagin

A Business Idea to Give Away: Fuel Delivery

It’s like Uber Eats but for car fuel

UK fuel shortage revisited

Solving the HGV driver shortage

Taming the surging fuel demand

Will this venture be useful, when the crisis passes?

Is the idea new?

How to execute an object file: Part 3

Dealing with external libraries

Exploring PLT/GOT

Implementing a simplified PLT/GOT

How to execute an object file: Part 2

Handling relocations

Relocations

Handling constant data and global variables

How to execute an object file: Part 1

Calling a simple function without linking

Why would we want to execute an object file?

A simple toy object file

Loading an object file into the process memory

A peek inside an object file

ELF segments and sections

Object file sections

The .symtab section

Finding and executing a function from an object file

Security considerations

Probably the simplest way to install Debian/Ubuntu in QEMU

Without downloading any installation media

Debian/Ubuntu installation media types

Full CDs/DVDs

Network install images

The mini.iso

Installing Debian/Ubuntu in QEMU without any installation media

Security considerations

Passkb: how to reliably and securely bypass password paste blocking

Why block password paste

Unblocking password paste

Security considerations for browser extensions

Rethinking paste unblock

Introducing passkb

Linux specifics

Potential future improvements

Sandboxing in Linux with zero lines of code

Sandboxing in Linux with zero lines of code

Linux system calls

Linux seccomp

Integrating seccomp into the application

seccomp with libseccomp

zero code seccomp

systemd small print

Introducing Cloudflare sandbox

sandboxing dynamically linked executables

sandboxing statically linked executables

sandboxify vs libsandbox.so

Conclusions

Import Markdown into Medium in 4 clicks

Or my first web app in 10 years: what could go wrong?

Markdown to Medium prior art

A browser based import tool

Selecting a UI framework

Hello, CORS!

Implementing a CORS proxy

CORS proxy security considerations

Final words

Using Go as a scripting language in Linux

Why consider Go as a scripting language

Current state of Go scripting

How Linux executes files

Extending supported binary formats from userspace

Fixing weak crypto in OpenSSL based applications

Why crypto becomes weak

Hypothetical case study

Tool analysis

Hooking crypto with LD_PRELOAD

The vendor strikes back

OpenSSL engines to the rescue

Injecting code on process startup

Getting rid of LD_PRELOAD

Conclusions

The `.symtab` section