6 ms·
FaCT: Constant Time Programming Language
- andsoitis 4y ago...cryptographic programming language...
- hinkley 4y agoAvi 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.
- ascar 4y agoDid you reply to the wrong comment?
- hinkley 4y ago>>> Constant Time Programming Language >> ...cryptographic programming language... > side channel attacks I know what I’m about, son.
- samatman 4y agoWhile 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.
- hinkley 4y agoIn 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.
- cole-k 4y agoAre 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.
- hinkley 4y agoAlso 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.
- ogogmad 4y agoA 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.
- c7DJTLrn 4y agoSlightly offtopic sorry, but I remember seeing this project years ago for a compiler that emits only mov instructions: https://github.com/xoreaxeaxeax/movfuscator 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?
- ducktective 4y agoThere is also a performance question: https://youtu.be/kbn9UCRK2Qg?t=1228 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.
- c7DJTLrn 4y agoAbsolutely, 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.
- insanitybit 4y agoIf 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.
- WJW 4y agoBeing 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.
- djrenren 4y agoOne 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.
- ducktective 4y agoHis presentation at Strange Loop: https://www.thestrangeloop.com/2018/fact-a-new-language-for-constant-time-programming.html https://www.thestrangeloop.com/2018/fact-a-new-language-for-... https://youtu.be/kbn9UCRK2Qg https://youtu.be/kbn9UCRK2Qg
- insanitybit 4y agoReally 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".
- _nhynes 4y agoRust 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 https://github.com/dalek-cryptography/subtle [1]: https://blog.openmined.org/privacy-series-basics-definition/ https://blog.openmined.org/privacy-series-basics-definition/
- jonhohle 4y agoFor 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).
- ajkjk 4y agoThere needs to be a law that every programming language README or homepage needs some sample code front-and-center.
- bee_rider 4y agoWhile 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.fact https://github.com/PLSysSec/FaCT/blob/master/example/example...
- ajkjk 4y agotrue, I noticed that afterwards.
- nynx 4y agoWow, that’s quite a list of installation instructions.
- pierrebai 4y agoI 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.
- mhh__ 4y agoIt can be done if you insert data dependencies everywhere and know which CPU it's running on.
- mysterydip 4y agoIt should be possible on microcontrollers at least. I don't believe most have a cache.
- AlotOfReading 4y agoIt'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.
- whatshisface 4y agoThe RPI2040 is enormous for a microcontroller. A typical microcontroller is something like an Arduino.
- AlotOfReading 4y agoThe 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".
- breck 4y agohttps://pldb.com/languages/fact-lang.html https://pldb.com/languages/fact-lang.html
- throwaway81523 4y agoThis is lower tech but might also be interesting, for simple embedded apps: https://github.com/tomahawkins/atom https://github.com/tomahawkins/atom
- rurban 4y agoerror 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.
- djrenren 4y agoHey, 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.
- amelius 4y agoHow do they control for timing in memory accesses, which can vary greatly depending on caching layers etc.
- Mathnerd314 4y agoThere 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.
- nullc 4y agoRight 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.
- yencabulator 4y agoRelated: New CPUs might be making fewer constant-time guarantees than you think. https://news.ycombinator.com/item?id=33150179 https://news.ycombinator.com/item?id=33150179 Should Linux set the new constant-time mode CPU flags?