5 ms·

The issue with writing crypto code in anything above assembly is that there's a risk that optimizing compilers could turn your finely crafted constant time, con

The issue with writing crypto code in anything above assembly is that there's a risk that optimizing compilers could turn your finely crafted constant time, constant power code into something which is not that.

woodruffw 3y ago
Generally speaking, an optimizing compiler is not going to introduce a branch (especially a data-dependent branch) where one doesn't exist in the code. To my knowledge, the bigger reasons for writing assembly for low-level cryptography are (1) performance, and (2) avoiding UB. The latter, particularly around C's type promotion and signed integer shifting rules, are a significant source of bugs[1]. [1]: https://blog.regehr.org/archives/1054 https://blog.regehr.org/archives/1054
- the8472 3y ago
  Afaik there's no guarantee that the compiler won't perform such changes. Even if it happens to generate the expected instructions today it could change with the next compiler release. I think on some x86 cpu tuning levels this can happen around 1bit integers (aka bools) when the cost model says it's cheaper for whatever reason (carry: bool, c: u64) = a.carrying_add(b) d += carry as u64 could be turned into (carry: bool, c: u64) = a.carrying_add(b) if carry d += 1 And I recall doing some bittwiddling to get something like a cmov but the compiler recognized the pattern and turned it back into a branch (this was for performance optimization, not crypto, but still...)
- pizlonator 3y ago
  > Generally speaking, an optimizing compiler is not going to introduce a branch (especially a data-dependent branch) where one doesn't exist in the code. You can't count on that, especially if you give the compiler a loop that has a versioning opportunity.
- GrumpySloth 3y ago
  I’ve had rustc turn my branchless code consisting purely of bitwise operations into branching code. There was probably nothing rustc-specific about it. Just LLVM estimating that branches would be faster in that case.

woodruffw 3y ago

Generally speaking, an optimizing compiler is not going to introduce a branch (especially a data-dependent branch) where one doesn't exist in the code. To my knowledge, the bigger reasons for writing assembly for low-level cryptography are (1) performance, and (2) avoiding UB. The latter, particularly around C's type promotion and signed integer shifting rules, are a significant source of bugs[1]. [1]: https://blog.regehr.org/archives/1054 https://blog.regehr.org/archives/1054

the8472 3y ago
Afaik there's no guarantee that the compiler won't perform such changes. Even if it happens to generate the expected instructions today it could change with the next compiler release. I think on some x86 cpu tuning levels this can happen around 1bit integers (aka bools) when the cost model says it's cheaper for whatever reason (carry: bool, c: u64) = a.carrying_add(b) d += carry as u64 could be turned into (carry: bool, c: u64) = a.carrying_add(b) if carry d += 1 And I recall doing some bittwiddling to get something like a cmov but the compiler recognized the pattern and turned it back into a branch (this was for performance optimization, not crypto, but still...)
pizlonator 3y ago
> Generally speaking, an optimizing compiler is not going to introduce a branch (especially a data-dependent branch) where one doesn't exist in the code. You can't count on that, especially if you give the compiler a loop that has a versioning opportunity.
GrumpySloth 3y ago
I’ve had rustc turn my branchless code consisting purely of bitwise operations into branching code. There was probably nothing rustc-specific about it. Just LLVM estimating that branches would be faster in that case.