https://kotlinlang.org logo
Join Slack
Powered by
Hi all! Are there any operations that are guarante...
# compiler
b
Hi all! Are there any operations that are guaranteed to be constant-time on all targets? I know for the JVM that ADD and CMOV can be made constant-time and the JVM gives you guarantees for a set of low-level operations to be constant-time (if done correctly), but I have not found any guarantees wrt. KMP or the Kotlin compiler in general. So my question is: Are there any guarantees in that respect for KMP?
e
I know for the JVM that ADD and CMIV can be made constant-time and the JVM gives you guarantees for a set of low-level operations to be constant-time (if done correctly)
that is not the case as far as I know
b
If that is true, then modern crypto in pure kotlin can never happen multiplatform. That would be really sad. We're still very much in the internal evaluation process, but if there is a realistic chance of getting something like that upstreamed, we might even consider contributing to the compiler
e
Java runtimes are outside of Kotlin's control
b
True, but there is a spec and for jvm we have the expertise in-house to ensure stuff is working as expected. Native is key
JS is not a priority for us at the moment and I'd assume wasm also offers constant-time operations
e
it's possible that some JVM implementations will have optimizers that add branching where you had none or replace your algorithms with something that works equivalent results but has different complexity. they are not specified to execute bytecode exactly as is in order.
b
Again, we know about JVM and what guarantees there are and aren't. What we don't know is about native. And I can't seem to find any info on this
e
the Kotlin native compiler doesn't have many optimizations, leaving it largely up to llvm
b
We'll probably first try cinterop with inline assembly for x86 and arm, respectively, if no such guarantees exist for native
e
which also doesn't guarantee… but at least with ahead-of-time compilation you can inspect the results
b
I would assume that this boils down to building the library (decoupled from KMP) with the correct switches, and then link it to the kmp library. But then again I have yet to look into native more
Since both x86 and arm come with a feature set specifically for constant-time execution of operations, I don't see the blocker. Is a library with cinterop not simply linked against?
e
yes. if you have an existing native library you can cinterop on native or jni/jna/etc. from jvm, no additional Kotlin features required
b
Yes, conceptually that is clear. It's a pity to have to jump through such hoops though, as is should be doable by the compiler with some annotations for a limited set of specific operations.
i
Hi! In Kotlin we have a 
const
keyword that is used like this
Copy code
const val a = 1 + 2
Compiler guarantees that 
1 + 2
will be evaluated at compile time into 
3
. It works the same on all targets. As for the list of supported operations, you can refer to the spec. Also, take a look at the following case
Copy code
fun main() {
    println(1 + 2) // It will be evaluated into `3`, but no guarantees
}
So, some expressions are evaluated, but it is not specified. We want to extend this feature in some future. I am really interested to hear about your use case and why you need it.
b
Thanks for the response, I'm very happy to see someone form JB jump onto this thread! However, what you describe is orthogonal to our use-case. We need to make sure that certain arithmetic expressions and conditional jumps performed at runtime are executed in constant time, regardless of input. Virtually all modern crypto algorithms (even some that build on established primitives), require such constant-time characteristics for certain operations to be secure against timing side-channels. Some proposed post-quantum crypto algorithms are extremely fragile in that respect, and even a teeny, tiny mishap will lead to leaking secrets. Without any guarantees from the Kotlin compiler in this regard, even implementing modern crypto constructions based on establishes primitives is a no-go in Kotlin. Which would be a shame, because we already have some fancy crypto algorithms implemented in Signum. Albeit in a private clone of the repo and we cannot, in good conscience, open-source them, because they are susceptible to side-channels.
e
for the record, there are basically no high-level programming languages that provide such guarantees, and certainly not C
even assembly is vulnerable. as https://bearssl.org/ctmul.html notes, the integer multiplication instruction does not execute in constant time for all values on some CPUs
none of JVM, WASM, JS, LLVM give promises about constant time operations so I find it hard to see what Kotlin could do
there is a https://github.com/WebAssembly/constant-time/blob/main/proposals/constant-time/Overview.md proposal but that hasn't gone anywhere as far as I can see
b
thank you very much! I was not aware of how tricky this is on ARM
i
Got it! Yeah, you said it right, my suggestion is not that you need. The same as @ephemient I personally don't know any languages that have such guarantees. From my expertise such guarantees comes from hardware and if you really need such guarantees you must write your program on C or assembler. An example of microcontroller that have time guarantees is Atmega328. You can check datasheet and instructions set at the end.
e
C doesn't provide guarantees, you can make a best effort to defeat compiler optimizations then verify the assembly output against your model of what the CPU will do. you could try to do that with Kotlin…
even Intel's Guidelines for Mitigating Timing Side Channels Against Cryptographic Implementations says
The 
CMOVcc
instruction runs in time independent of its arguments in all current x86 architecture processors. [...] Future versions of the architecture may introduce new addressing modes that do not exhibit this property.
so whatever you do, you're going to have to re-evaluate on each new CPU
i
C doesn't provide guarantees,
Yes of course. I meant that you can write some important logic using 
Inline assembly
and logic without time constraints in C.
so whatever you do, you're going to have to re-evaluate on each new CPU
Yes, that is also that I am talking about. You should take one specific microprocessor and write your program for it with time constraints. I don't know any other way.
👍 1
e
inline assembly isn't standard or portable. msvc doesn't have it at all 😛
👍 1
in any case, I found an interesting example: https://stackoverflow.com/a/37737277
JIT is not only allowed to do such optimizations, but it actually does so sometimes.
Here is a sample bug I've found in JMH, where a short circuit optimization resulted in unstable benchmark scores. JIT has optimized the evaluation of 
(bool == bool1 & bool == bool2)
, despite that 
&
was used rather than 
&&
, even when 
bool1
and 
bool2
were declared 
volatile
.
so yeah. even if you check that the compiler's output looks like it would be constant time, and even if you measure it to be when run on some JVM under some conditions, that doesn't mean that will be under all conditions
b
I was not aware of this. Thank you very much for digging into this
2 Views
Open in Slack
PreviousNext
Powered by