Generation of a static table at compile-time

help
1

Problem

I'm working on an implementation of a Galois field for a cryptographic library.
I would like to have precomputed tables for operations in Gf(256).

Existing implementations either use ONCE_INIT to generate the table when the program launches or have the table hardcoded in the source code.

I'm trying to generate the table (implemented as a struct) at compile time elegantly without having to hardcode it. I have looked into using macros but it appears that they alone won't be able to provide the operations I need to compute the table.

I started looking into compiler plugins, is that the right tool for the job? Or anyone has an alternative that wouldn't require me to move to experimental versions of the compiler?

2

You can write a build script to spit the source file with a table, and then include it as

#[path = "where_did_I_put_the_table.rs"]
mod table;

Generating strings is not as fancy as generating AST, but I think it will do the job in this case just fine.

3

Why not have a middleground and have the code for the table generated?

4

The lazy_static crate may also do the trick for you (which uses ONCE_INIT under the covers IIRC).

5

Do you have an example of this for generating a static struct?

6

I'm looking for something at compile-time, not runtime.

7

I think this might be what I'm gonna end up doing. Interested in @matklad's solution with build scripts.

8

No, I haven't used it myself.

LALRPOP uses this approach to generate parsers at compile time, but this is a terrible example. You basically need to generate a source code of the struct and write it to some file in src directory. I think you can avoid string manipulation if you use Debug:

#[derive(Debug)]
struct S {
    ...
}

fn main() {
    let s: S = compute();
    let source_code = format!("pub const precompiled_table: S = {:#?}", s);
    write_source_code_to_file_in_src("src/table.rs", &source_code);
}
1 Like
9

typenum also uses a build script to generate code.

1 Like
10

Kind of off-topic, but this is an extremely bad idea due to cache timing attacks (a perennial problem with AES and other GF(256) based ciphers), and the situation has very recently gotten much worse: recent Intel microarchtectures leak addresses at finer-than-cache-line granularity, and SharedArrayBuffer, which indirectly provides sub-nanosecond timing to all of the Javascript code running in your browser, seems to be getting traction.

11

Thanks @sorear for the links. Any recommendations? DJB's recommendations seem overly complex for my use case since a timing side-channel is not a major concern.

12

If you're using the AES S-box specifically on an x86-64 system made in the last 5-10 years, you can subvert the AES instruction set extensions into giving you the S-box; see Intel® Advanced Encryption Standard (AES) New Instructions Set p. 42.

Otherwise your best option is probably bit-slicing.

Are you expecting to avoid timing attacks by way of keeping a low profile (people target OpenSSL, not FeelingRustyCrypt) or is there a more specific reason you expect to be protected from side channels? Between cross-VM attacks and the steady increase of Javascript's capabilities, I'm rather pessimistic about the future of secret array indices.