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

Jump to bottom

crypto/subtle: change ConstantTimeLessOrEq to have less undefined behaviour #42685

Open
isislovecruft opened this issue Nov 18, 2020 · 7 comments
Open

crypto/subtle: change ConstantTimeLessOrEq to have less undefined behaviour #42685

isislovecruft opened this issue Nov 18, 2020 · 7 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Unplanned

Comments

@isislovecruft
Copy link

isislovecruft commented Nov 18, 2020 •
edited

What version of Go are you using (go version)?

$ go version
go1.11.6

Does this issue reproduce with the latest release?

Yes. (With apologies for my vintage go compiler.)

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/isis/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/isis/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/lib/go-1.11"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go-1.11/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build154905218=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I have a better algorithm for the ConstantTimeLessOrEq function which works for all inputs in [0, 2^32). Currently the ConstantTimeLessOrEq function only works (as documented) for inputs in [0, 2^31) and is UB for everything else (including negative signed integers, which it takes signed ints). Implementing the algorithm and testing it shows that it works for correctly for positive inputs, which means we could also change the interface to be ConstantTimeLessOrEq(x, y uint32) int which would remove all UB, but this is obviously a decision for the maintainers.

The algorithm is:

// ConstantTimeLessOrEq returns 1 if x <= y and 0 otherwise.                                                                                                                                                                                   
// Its behavior is undefined if x or y are negative.                                                                                                                                                                                           
func ConstantTimeLessOrEq(x, y int) int {                                                                                                                                                                                                      
    x32 := uint32(x)                                                                                                                                                                                                                           
    y32 := uint32(y)                                                                                                                                                                                                                           
                                                                                                                                                                                                                                               
    gtb := x32 & ^y32                                                                                                                                                                                                                          
    ltb := ^x32 & y32                                                                                                                                                                                                                          
                                                                                                                                                                                                                                               
    ltb = ltb | (ltb >> 1)                                                                                                                                                                                                                     
    ltb = ltb | (ltb >> 2)                                                                                                                                                                                                                     
    ltb = ltb | (ltb >> 4)                                                                                                                                                                                                                     
    ltb = ltb | (ltb >> 16)                                                                                                                                                                                                                    
                                                                                                                                                                                                                                               
    bit := gtb & ^ltb                                                                                                                                                                                                                          
                                                                                                                                                                                                                                               
    bit = bit | (bit >> 1)                                                                                                                                                                                                                     
    bit = bit | (bit >> 2)                                                                                                                                                                                                                     
    bit = bit | (bit >> 4)                                                                                                                                                                                                                     
    bit = bit | (bit >> 16)                                                                                                                                                                                                                    
                                                                                                                                                                                                                                               
    return int(^bit & 1)                                                                                                                                                                                                                       
}

What did you expect to see?

N/A.

What did you see instead?

EDIT: This is obvious but an example test case which (expectedly) fails the previous algorithm is:

    {1, 4294967295, 1},

EDIT #2: Perhaps less obvious, this algorithm also implements ConstantTimeGreater by changing the final line to return int(bit & 1), which is also useful for some of the algorithms in a few post-quantum cryptographic algorithms, particularly those which require a constant-time sorting network.
isislovecruft added a commit to isislovecruft/go that referenced this issue Nov 18, 2020
@isislovecruft
crypto/subtle: Change ConstantTimeLessOrEq to remove undefined behavi…
3a11355 
…our.

 * CLOSES golang#42685.
@isislovecruft isislovecruft mentioned this issue Nov 18, 2020
Closed
@gopherbot
Copy link

Change https://golang.org/cl/270959 mentions this issue: crypto/subtle: remove undefined behaviour from ConstantTimeLessOrEq

@mpx
Copy link
Contributor

mpx commented Nov 19, 2020

Cc @FiloSottile

@mvdan
Copy link
Member

mvdan commented Nov 19, 2020

As we're currently in a code freeze for Go 1.16, could you clarify if you intend this issue for 1.17 or 1.16? See https://github.com/golang/go/wiki/Go-Release-Cycle.

In particular, if this is considered a bug or a problem that the user can't easily work around, then you could probably argue it should be reviewed and merged during the freeze, and be released with 1.16 in two months. Otherwise, it would wait until 1.17 in eight months.

@cagedmantis cagedmantis changed the title crypto/subtle: Change ConstantTimeLessOrEq to have less undefined behaviour crypto/subtle: change ConstantTimeLessOrEq to have less undefined behaviour Nov 30, 2020
@cagedmantis cagedmantis added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 30, 2020
@cagedmantis cagedmantis added this to the Backlog milestone Nov 30, 2020
@cagedmantis
Copy link
Contributor

I've added this to the backlog milestone while @mvdan questions are answered.

@FiloSottile
Copy link
Contributor

Thank you @isislovecruft!

As you said, this is currently working as documented, so this should target Go 1.17, since Go 1.16 is in code freeze.

@FiloSottile FiloSottile modified the milestones: Backlog, Go1.17 Dec 1, 2020
@elagergren-spideroak
Copy link

elagergren-spideroak commented Feb 25, 2021 •
edited

Hi, I can't comment on the CL at the moment but I think the algorithm is incorrect. Haven't had a chance to look at it further.

``` $ cat x.go package main

import (
"crypto/subtle"
"fmt"
)

func main() {
x := 342
y := 255

fmt.Printf("x=%d, y=%d\n", x, y)
fmt.Printf("old: %d\n", subtle.ConstantTimeLessOrEq(x, y))
fmt.Printf("new: %d\n", ConstantTimeLessOrEq(x, y))

}

// golang.org/issues/42685
func ConstantTimeLessOrEq(x, y int) int {
x32 := uint32(x)
y32 := uint32(y)

gtb := x32 & ^y32
ltb := ^x32 & y32

ltb = ltb | (ltb >> 1)
ltb = ltb | (ltb >> 2)
ltb = ltb | (ltb >> 4)
ltb = ltb | (ltb >> 16)

bit := gtb & ^ltb

bit = bit | (bit >> 1)
bit = bit | (bit >> 2)
bit = bit | (bit >> 4)
bit = bit | (bit >> 16)

return int(^bit & 1)

}
$ go run x.go
x=342, y=255
old: 0
new: 1

</details>

@elagergren-spideroak
Copy link

Ah, not wrong per-se. Just missing ltb = ltb | (ltb >> 8), similarly with bit. Posted on the CL.

@FiloSottile FiloSottile modified the milestones: Go1.17, Unplanned Mar 17, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Unplanned
Development

Successfully merging a pull request may close this issue.

crypto/subtle: remove undefined behaviour from ConstantTimeLessOrEq isislovecruft/go
7 participants
@cagedmantis @isislovecruft @FiloSottile @mpx @mvdan @gopherbot @elagergren-spideroak