Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/bits: Add, Mul and Sub are not constant time #31229

Open
FiloSottile opened this Issue Apr 3, 2019 · 10 comments

Comments

Projects
None yet
6 participants
@FiloSottile
Copy link
Member

FiloSottile commented Apr 3, 2019

These functions were added in #24813 to be intrinsified for high performance code like cryptography.

Cryptography code also needs to be constant time most of the time, so it would be good for the Go fallbacks to try to be constant time. (I realize that a smart compiler can rewrite them.)

The fallbacks are going to be slow anyway, so I don’t think there’s a big performance concern.

@FiloSottile FiloSottile added the NeedsFix label Apr 3, 2019

@FiloSottile FiloSottile added this to the Go1.13 milestone Apr 3, 2019

@randall77

This comment has been minimized.

Copy link
Contributor

randall77 commented Apr 3, 2019

Mul looks to be constant time already.

@TuomLarsen

This comment has been minimized.

Copy link

TuomLarsen commented Apr 3, 2019

Constant time operations are only useful for crypto and the extra slowness is undesirable in every other domain. Just saying...

@randall77

This comment has been minimized.

Copy link
Contributor

randall77 commented Apr 3, 2019

This issue is only about the Go fallbacks when intrinsics are not available for the target architecture.
The intrinsics are already constant time.

If your architecture doesn't have intrinsics, your code will already be extra slow. The fix in that case is to implement the intrinsics.

@FiloSottile

This comment has been minimized.

Copy link
Member Author

FiloSottile commented Apr 3, 2019

The goal is to have fast and safe intrinsics, it's why these functions were added. In the meantime, I'd rather have slow fallbacks than unsafe ones, though.

@TuomLarsen

This comment has been minimized.

Copy link

TuomLarsen commented Apr 3, 2019

Not every architecture has add with carry, for example. If by "intrinsics" you mean e.g. ADC then it may very well happen that a non-constant time "fallback" will be faster than constant time implementation. What I try to say is that promising constant time fallbacks creates pressure for native implementations which except for crypto is not desirable, IMO.

@smasher164

This comment has been minimized.

Copy link
Contributor

smasher164 commented Apr 4, 2019

The branchless, constant-time versions of Add and Sub from Hacker's Delight were originally proposed, but it was faster to compute the sum normally, and check a condition to compute the carryOut and borrowOut.

I have the constant-time version here that I can send in as a CL:
https://github.com/smasher164/extprec/blob/master/extprec.go

@FiloSottile

This comment has been minimized.

Copy link
Member Author

FiloSottile commented Apr 4, 2019

@smasher164 please do, yeah.

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Apr 4, 2019

Change https://golang.org/cl/170758 mentions this issue: math/bits: make Add and Sub constant time

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Apr 10, 2019

Discussion on #31267 about whether to change these.

@rsc

This comment has been minimized.

Copy link
Contributor

rsc commented Apr 10, 2019

Also, if someone wants to double-check the math/bits Add64 benchmark, that would be helpful. If it is literally never executing the 'carryOut = true' case, then it's a bad benchmark. It should do a mix of operations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.