FaCT: Constant Time Programming Language | Hacker News Reader

FaCT: Constant Time Programming Language

github.com

135 pointsducktective55 comments

Really interesting idea. I would be curious to see if this could be embedded into a proc macro in Rust, allowing one to do something like this:

    fn compare_hashes(a: &[u8], b: &[u8]) -> bool {
        let size = a.len();
        fact!{
            for (uint64 i from 0 to size) {
                if (x[i] != y[i]) { return -1; }
            }
            return 0;
        }
    }

It would get compiled into asm and inlined.

I'm also wondering how this interacts with bounds checking, which would introduce branches. I tried searching the paper (sorry, no time to read the whole thing today) for 'bounds' but did not get a result.

Semi-related. One (insufficient) option for dealing with timing leaks is to add a random delay. ie: `sleep_ms(rand(1,1000))`. The problem is that given N leaks an attacker can remove that noise. I have two questions here:

1. What is "N"?

2. Does that sleeping introduce any additional vulnerabilities? Basically, is this a "if you can afford that latency it won't hurt".

Rust has some great constant time libs already, for instance `subtle` [0]. A `derive(ConstantTimeEq)` might get you most of the way, but a constant-timeifier would be great for wrapping whole algos where you might not want to think too hard about timing side channels.

For your sleeping proposal, it sounds a little like differential privacy [1] where you can add some randomness to gain some privacy but spend some of the predetermined privacy budget. In that case, `N` depends on the (roughly) variance of the computation time, the noise amount, and your privacy budget. If you get it right, it has provable security properties. However, that doesn't work as well when the adversary has access to the machine and can observe the intermediate state (or side channel leaks thereof).

[0]: https://github.com/dalek-cryptography/subtle

[1]: https://blog.openmined.org/privacy-series-basics-definition/

For comparisons, the normal “trick” is to & a failure flag for every character in the hashes so you’ll always compare the same number of characters. At the end, the failure flag is returned. This may cost more time in obvious failure cases, but eliminates timing oracles (assuming comparison and & operations require the same number of cycles regardless of the operands).

If you add the same delay for the same input there's no statistical way to remove the noise because at that point it's no longer noise -- it's bias.

That said, it's fairly easy to tell if a CPU spends time sleeping or doing actual work, so it depends on who is in control of the CPU.

Oh, interest. So something like `sleep_ms(0, hash(input) % 1000)`

A better alternative is to sleep, not for a fixed time period after the end of the operation, but until a fixed amount of time after the start of the operation (assuming the operation never takes longer than that). That way, in theory, the total time taken is independent of any variability in the timing of the operation itself.

But there’s still a high risk of some side channel letting the attacker tell when the program is working and when it’s sleeping.

I do wonder if it is possible to truly be certain code runs in constant-time. The problem is that modern CPU translate their instruction set into internal micro-code. For example, the x86 CMOVE instruction (conditional move) could potentially become a branching path once translated to microcode. There are other instructions like multiplication or division that may end-up having different run time depending on input.

It can be done if you insert data dependencies everywhere and know which CPU it's running on.

It should be possible on microcontrollers at least. I don't believe most have a cache.

It's increasingly rare to see a uC without some kind of memory hierarchy nowadays. Even a barebones rpi2040 uses what's effectively an SRAM cache in front of the flash. Unless you have compelling use case that isn't solved by disabling caching (which any chip can do) or region attributes, it's basically a free spec boost for manufacturers.

Regardless, you probably don't want to do your fast-path cryptography on the slowest coprocessors imaginable.

The RPI2040 is enormous for a microcontroller. A typical microcontroller is something like an Arduino.

The Cortex-M0 used in the rpi2040 is also used by Arduino. More broadly, both the SAM and the AVR32 families have some level of support for caching. Only the AVR8s don't. I think it's fair to describe 8 bit uCs as "increasingly rare".

I think whatshisface means "ATMega328" when he says "Arduino".

I think there are more 8-bit μCs around than ever before, even though it's harder and harder to justify using one instead of a 32-bit μC. But lots of 32-bit μCs don't have caching either, or they have it to the extent of "you can run code from internal RAM, or more slowly from internal Flash, or much more slowly from QSPI-connected memory". But that doesn't introduce any nondeterminism into the timing, because your code has control over where it's running from.

I imagine we all agree that the entire idea of running crypto code from a dog-slow uC executing from flash is silly, but to continue the hypothetical...

The way old processors used to do XIP with constant random access latency is pretty much dead at this point for new designs. Semiengineering did a good article on this awhile back [1]. Even if there weren't usually a lot of invisible caching in the middle, flash cells usually don't have identical access latencies (worse, they change with age/write cycles!), and the AVR conditonal branch has data-dependent timings besides. At the design side, there's also a lot of decisions like burst modes that can introduce timing variations that can change with minor design revisions. Most of these aren't documented or even well understood by manufacturers. Truly eliminating architectural timing side channels is very, very difficult today.

[1] https://semiengineering.com/what-happened-to-execute-in-plac...

I don't think there's anything wrong with running crypto code from a dog-slow μC executing from Flash, except that sometimes you might prefer the Flash to be mask ROM.

This is a good article! I guess you're right that when you're running code loaded over a QSPI bus it's probably going to be cached unless you're using an old chip. So data processed by code loaded that way is subject to timing-channel leaks.

However, I think it's very unusual for embedded NOR memory in a μC to have detectable variable access latency. As the article says:

> As long as the operating frequency is slow enough that the flash access times can keep up, instructions can be fetched and executed directly out of the flash, otherwise known as executed in place. The original idea was that you didn’t need to buffer the instructions somewhere else before executing them. ¶ Embedded NOR memory is still alive and well, although today’s higher volumes are on nodes far from what would be considered leading-edge for logic.

So, on-chip Flash is probably still fine.

You probably don't want to try to make an AVR8 into an SSL accelerator, but there are plenty of applications where the ability to do crypto securely is valuable, even if it's very slow.

On-chip flash would still be susceptible to whether the CPU uses burst accesses or other weird microarchitectural details. The former manifests as the 8th or 16th instruction having slightly higher real latency, for example. This sort of stuff is endless, which is why stuff like TFA that gets around the issue by simply removing the data dependencies before they ever get to the hardware is a better general approach if you're not going to do ASICs.

Slightly higher real latency? Are you talking about asynchronous CPUs like the GreenArrays GA144? Or saying that if you're running off the internal RC oscillator the clock speed will vary because the supply voltage varies depending on memory access patterns? Or by "slightly higher real latency" do you mean that an instruction will take 2 clock cycles instead of 1 or 3 cycles instead of 2? I don't think any of those are true on things like the ATMega328 AVR8 mentioned above or the Padauk PMS150C. Maybe you mean something else?

Bitbanging protocols with tight timing requirements using cycle-accurate code is still a thing people routinely do on small microcontrollers, and it wouldn't work if instruction timing was as unpredictable as you're saying.

Nevertheless, I agree that removing data-dependent branches is a better way to close timing leaks.

Not really sure where you are getting your "typical" from, 32bit mcus dominate the market over old 8bitters like avrs in the arduino. And rpi2040 is not particularly enormous as far as ARM microcontrollers go, while it is dual-core the cores are tiny M0+ ones instead of bigger cores like M7 or M33

Yes, since every computer has finite memory.

If you bubble sort a list of bytes, say your algorithm runs in 10000+n^2 clock cycles. You have at most an exabyte of storage, so your code will run in at most 10^37 clock cycles! :p

As storage technology improves, of course the coefficient will increase, but at that point is should be considered a different algorithm. This one has undefined behaviour when you have more than an exabyte of storage.

This article has nothing to do with algorithm complexity and "constant time" big-O complexity class, this is about guarantees of code executing in absolutely constant time (i.e. exactly x clock cycles, not "at most") in an input-independent manner to ensure that execution time does not reveal any information about what the inputs/outputs were.

In essence, this is about a programming language that can ensure that execution time always equals the worst case; if there's branching, taking both branches and ignoring one of the results; if there's iteration, doing a constant maximum count of iterations no matter what the input data is, etc.

> For example, the x86 CMOVE instruction (conditional move) could potentially become a branching path once translated to microcode.

Would you have any links to more reading on this and when it happens? It's the first time I've heard it.

If the language spec says a piece of code must execute in constant-time, any deviation is a compiler bug.

But yes, that may mean the language can’t be implemented well on lots of modern hardware.

A lot probably can be done by avoiding some instructions, flushing caches very often, clearing branch prediction history (if possible), etc.

That would not make the language win performance shootouts, though.

There also is the problem that not all cores may be equal and that quite a few modern CPUs drop speed ‘at will’, depending on system load, core temperature, etc.

No, I think. Much like your examples, I have in mind "False Data Dependencies" in the CPU. I came across this on StackOverflow several years ago. It is a long question and a long, informative thread about seemingly irrational performance differences: "https://stackoverflow.com/questions/25078285/replacing-a-32-..."

Hey, one of the paper authors here, this has been a serious problem in the past (and present), but is definitely improving. For example, intel’s docs state that cmove is constant-time on recent hardware. ARM’s DIT (data-independent timing) [1] extension provides hardware-level guarantees and intel has extensive docs on how to use their chips for constant-time coding [2]

[1]: https://developer.arm.com/documentation/ddi0601/2020-12/AArc...

[2]: https://www.intel.com/content/www/us/en/developer/articles/t...

There needs to be a law that every programming language README or homepage needs some sample code front-and-center.

While it would be nice, this is somewhat mitigated by the fact that they've got a top-level directory called "example."

https://github.com/PLSysSec/FaCT/blob/master/example/example...

true, I noticed that afterwards.

His presentation at Strange Loop:

https://www.thestrangeloop.com/2018/fact-a-new-language-for-...

https://youtu.be/kbn9UCRK2Qg

...cryptographic programming language...

Avi Shamir is the S in RSA, and his name has appeared on a multitude of papers about side channel attacks. Timing, current, and I think EMI. anything and everything you can measure to differentiate between what happens when you encode message A versus message B, or often worse, the same message with key A versus key B, which lets you reduce the search space for brute force guessing. Knocking n down a bit for a 2^n problem sometimes only reduces a problem from “heat death of the universe” to “nobody is around who could possibly care” but in other cases you can take something from a thousand years to a thousand hours, or all the memory in the US to all the memory in a single cluster.

Did you reply to the wrong comment?

>>> Constant Time Programming Language

>> ...cryptographic programming language...

> side channel attacks

I know what I’m about, son.

While that's clear from what you said, I also don't exactly see how it works as a reply to GP.

You know the rudeness is against guidelines, as well.

In some cultures, being asked if you belong here is considered passive aggressive, and in some cultures passive aggressive is the worst form of rude.

Tribal knowledge is always a danger. Which part did you guys think I lost the plot? Why code that runs slower is a feature for cryptography? Assuming people know what a side channel attack is? Why the co-creator of one of the longest surviving cipher systems who spent his career breaking other ciphers is relevant background information? Something else?

The summary for the linked package is:

> This is the compiler for the Flexible and Constant Time cryptographic programming language. FaCT is a domain-specific language that aids you in writing constant-time code for cryptographic routines that need to be free from timing side channels.

Are you offended that you were asked if you were replying to the wrong comment? I suppose this could be a cultural faux pas - we must be from different cultures.

I would also be inclined to ask if you meant to reply to another comment. Let me explain. To me the other option is to say that what you wrote makes no sense and I cannot understand why you wrote it. Asking if you meant to reply to another comment is my way of showing that I don't think you're a crank, but instead you just made a silly mistake any one of us could've. But if I wrote it the other way you might think that I think you're a crank. Y'know?

Anyway my understanding of the original comment is that it was meant as a clarification to the title. Hence why your first reply which starts explaining who Avi Shamir is confused me too.

Also related to tribal knowledge: One of the sins of technical writing is forgetting to tell people up front why they should care. The assumption that everyone who got here knows exactly why they are here doesn’t scale. You write enough docs and people are gonna click on the wrong one. Nobody wants to read half a page of text and get out a dictionary to find out they’re in the wrong space. You’ve dumped all of short term memory, for one thing.

A constant time programming language sounds like a ridiculous notion to most problem domains. It is a ridiculous notion. You only want code that always runs in exactly half a millisecond when you’re solving a very, very specific set of problems, like protecting secrets or opening airbags, and then it’s one of the most important things.

You don't even need constant time for opening airbags. Real time (upper bound, but no lower bound) will do the job. Pretty much it's just working with secrets that cares about constant time.

> One of the sins of technical writing is forgetting to tell people up front why they should care.

Hence our confusion of you mentioning Shamir. I went back to the site thinking he may have been a contributor.

A language like this one can be used to develop cryptography libraries like OpenSSL.

If two documents have the same length, but differ in the time it takes to encrypt them, then their encryption times leak information about their contents. In cryptography, this is an example of a "side channel" - and side channels are considered bad. A "constant time" language helps minimise the presence of such side channels, making it useful in cryptography.

Right now constant time techniques are almost exclusively reserved for code that handles secret keys (e.g. for encryption or digital signatures).

But, sadly, there are applications where the secrets can't just be limited to keys: For example in an anonymous messaging system essentially all the data is secret, as they're usually constructed someone who could perform a timing/cache sidechannel attack against you could potentially determine which messages you were reading (or writing) and discover your identity.

So security with those anonymity tools critically depends on the participants being protected against observation-- which would be considered a fairly reckless security assumption if we were talking about the security of your AES disk encryption or ECDSA message signing.

I wouldn't go so far as to say that constant time programming is a solved problem for basic crypto-- the fact that languages and instruction sets make few guarantees remains an issue-- but the situation there isn't particularly dire. There are few enough basic primitives and the techniques needed to get protect keys from sidechannels in C are well known, so in practice things are usually pretty good (unless you get into people making crypto code in JS...).

But without better tools we can't even start to thinking about extending sidechannel security more elaborate cases. Domain specific languages might help.

error in the paper, chapter 4.1, deferred return:

transformed code, but insecure

    secret mut uint32 rval = 0;
    secret mut bool notRet = true;
    if (sec) { rval = 1; notRet = false; }
    if (notRet) {
    // long-running computation ...
    }
    return rval;

the long running block depends on the secret, thus leaks it.

Hey, one of the paper authors here. If the compiler stopped here, yes this would be an error, but subsequent transformations (described in section 4.2) eliminate the branch ensuring that timing is equivalent regardless of the value of notRet.

Related: New CPUs might be making fewer constant-time guarantees than you think.

https://news.ycombinator.com/item?id=33150179 Should Linux set the new constant-time mode CPU flags?

How do they control for timing in memory accesses, which can vary greatly depending on caching layers etc.

There is an example in the paper, where they say the compiler synthesizes masked array reads. Any branching on secrets will be eliminated via transformation to bitmask manipulation, so a memory read that was conditional on a secret will always be performed.

More generally, complex memory access patterns like reading/writing an array at a secret index are forbidden, you have to transform them into looping over the whole array and testing if the current index is equal to the secret index. It seems doing such transformations automatically is possible but FaCT just errors because the resulting code is slow.

Slightly offtopic sorry, but I remember seeing this project years ago for a compiler that emits only mov instructions:

https://github.com/xoreaxeaxeax/movfuscator

Since this is effectively branchless and every instruction would take the same number of micro ops, wouldn't this be a very safe way of writing cryptographic code free of side channels?

There is also a performance question:

https://youtu.be/kbn9UCRK2Qg?t=1228

Judging by the image of generated assembly code in movfuscator repo, I don't think the mov-only solution would be efficient.

Absolutely, the performance would be terrible, but under circumstances where you need to be sure there's no side channels (like in a secure element kind of chip) maybe that's acceptable.

If all you're doing is comparing two hash values it's probably a lot less important that it's fast and more important that it's side channel resistant.

Being both side channel resistant and fast would be even better though. Movfuscator is a cool project but there are definitely better ways to generate constant time code.

One of the authors of FaCT here. This is a great question, because at first blush it feels like it might. movfuscator creates a branch-less program. But my guess is that we’ll run into two key problems:

1. Leakage via cache. If our memory access patterns are influenced by secret data, then we can detect variance in execution time as a result of cache hits/misses. Movfuscator generates code that does lots of loads and stores using application data as addresses so my guess is that even if your source program didn’t depend on secrets in this way, the output code probably still would.

2. Termination rules. Movfuscator programs run inside a giant loop. Every execution of that loop drives execution forward, and every instruction is executed on every loop. Even if the body of this loop is constant-time (see above for why it’s probably not), we need to consider how the program actually terminates. For example if I write the following C code:

    for (int i = 0; password[i] != 0 && entry[i] != 0; i++) {
      if (password[i] != entry[i]) return false;
    }
    return true;

We can see that it takes fewer iterations to check entries which are incorrect earlier. For example, if the password is “foo” and the entry is “bar”, then we return in the first iteration, as opposed to the entry “fob” which returns on the third. Thus, if the programs termination time is affected by the secret value, could still detect timing variance because the full program would terminate faster even if each loop took the same amount of time.

This is a great answer, thank you.

This is lower tech but might also be interesting, for simple embedded apps:

https://github.com/tomahawkins/atom

https://pldb.com/languages/fact-lang.html

Wow, that’s quite a list of installation instructions.

Reply on news.ycombinator.com