search

riscv / riscv-crypto

RISC-V cryptography extensions standardisation work.
https://wiki.riscv.org/x/MVcF
Creative Commons Attribution 4.0 International
360 stars 83 forks source link

Instruction latency of non-multiply arithmetic #87

Closed WildCryptoFox closed 3 years ago

WildCryptoFox commented 3 years ago

Asynchronous circuit based RISC-V implementations will likely use data-dependent O(log log n) adders.

Why is the latency constraint only applied against (carry-less) multiplies? ADD, SUB, SLT, SLL, SRL, SRA can all be faster in variable time.

Not constraining these operations is asking for software to assume they are constant time and hardware to be forced to discard optimizations.

ben-marshall commented 3 years ago

Asynchronous circuit design is a fascinating and exciting technology. My understanding (which may be wrong) is that it is very niche, and the vast majority of commercial designs use synchronous designs.

We are in the process of revising our constant time proposals, the latest draft of which is available here. It includes a much larger list of core instructions, and aims to be much simpler. That is, you either are constant time or not. You can't switch it on or off.

I hope this helps address any concern you might have?

WildCryptoFox commented 3 years ago

The issue for asynchronous circuits is that the typical tooling has been built around synchronous circuits and thus is unsuitable to implement asynchronous circuits. This tooling issue has largely been resolved by the Yale Asynchronous VLSI and Architecture Group et al.

There is nothing niche about asynchronous circuits. Only reduced exposure. Often paying only a little extra area, asynchronous circuits are typically substantially more energy efficient and performant. I.e. Logical operations do not need to be as slow as the worst case time for addition or multiplication. There is no global clock line heating the entire chip. Any timing variations due to thermals or manufacturing imperfections are tolerated while processing all the data as fast as possible -- slowing down only to respect thermal thresholds.

Or in the case of cryptography, slowing down by ignoring the shortcut signals.

WildCryptoFox commented 3 years ago

Oh I forgot to confirm. Yes, the draft suffices for all the other operations.

WildCryptoFox commented 3 years ago

Hmm. I guess this issue should remain open until the draft makes it into the next version.

WildCryptoFox commented 3 years ago

@ben-marshall LB, LH, LW, LD should be added to zkt-list.adoc. Otherwise the timing from sign extending may leak the high bit. This affects the timing of the output but remains independent to the inputs.

ben-marshall commented 3 years ago

Hmm. I guess this issue should remain open until the draft makes it into the next version.

I agree, I like to leave issues like this open until things get solved my a major release of the spec. Thanks.

LB, LH, LW, LD should be added to zkt-list.adoc. Otherwise the timing from sign extending may leak the high bit. This affects the timing of the output but remains independent to the inputs.

That's a very good point. The rationale for leaving loads off the list was that of course you shouldn't be doing secret dependent loads anyway, which focuses on leakage from the address. But yes, you are right, implementations should not leak the MS bit of the thing they are loading based on doing sign extension or not. I'm not sure how common signed loads are in cryptographic code?

I suspect @mjosaarinen will have thoughts on this. We don't want to have loads in the list in the same sense as other instructions. If anything is needed at all, it might just be a sentence explaining this?

About the asynchronous logic styles - I am in total agreement with you about the pros of asynchronous logic. Forgive my semantics, by "niche", I really meant "not as commonly found compared to synchronous designs". Which hopefully will change one day.

ben-marshall commented 3 years ago

I'm going to consider this issue closed with release v0.9.2, which contains the newly expressed Zkt extension. Please open new issues for subsequent constant-time related discussions. Thank you for your input! :+1: