diff options
Diffstat (limited to 'src/crypto/subtle')
-rw-r--r-- | src/crypto/subtle/constant_time.go | 62 | ||||
-rw-r--r-- | src/crypto/subtle/constant_time_test.go | 159 | ||||
-rw-r--r-- | src/crypto/subtle/xor.go | 24 | ||||
-rw-r--r-- | src/crypto/subtle/xor_amd64.go | 10 | ||||
-rw-r--r-- | src/crypto/subtle/xor_amd64.s | 56 | ||||
-rw-r--r-- | src/crypto/subtle/xor_arm64.go | 10 | ||||
-rw-r--r-- | src/crypto/subtle/xor_arm64.s | 69 | ||||
-rw-r--r-- | src/crypto/subtle/xor_generic.go | 64 | ||||
-rw-r--r-- | src/crypto/subtle/xor_ppc64x.go | 10 | ||||
-rw-r--r-- | src/crypto/subtle/xor_ppc64x.s | 87 | ||||
-rw-r--r-- | src/crypto/subtle/xor_test.go | 106 |
11 files changed, 657 insertions, 0 deletions
diff --git a/src/crypto/subtle/constant_time.go b/src/crypto/subtle/constant_time.go new file mode 100644 index 0000000..4e0527f --- /dev/null +++ b/src/crypto/subtle/constant_time.go @@ -0,0 +1,62 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package subtle implements functions that are often useful in cryptographic +// code but require careful thought to use correctly. +package subtle + +// ConstantTimeCompare returns 1 if the two slices, x and y, have equal contents +// and 0 otherwise. The time taken is a function of the length of the slices and +// is independent of the contents. If the lengths of x and y do not match it +// returns 0 immediately. +func ConstantTimeCompare(x, y []byte) int { + if len(x) != len(y) { + return 0 + } + + var v byte + + for i := 0; i < len(x); i++ { + v |= x[i] ^ y[i] + } + + return ConstantTimeByteEq(v, 0) +} + +// ConstantTimeSelect returns x if v == 1 and y if v == 0. +// Its behavior is undefined if v takes any other value. +func ConstantTimeSelect(v, x, y int) int { return ^(v-1)&x | (v-1)&y } + +// ConstantTimeByteEq returns 1 if x == y and 0 otherwise. +func ConstantTimeByteEq(x, y uint8) int { + return int((uint32(x^y) - 1) >> 31) +} + +// ConstantTimeEq returns 1 if x == y and 0 otherwise. +func ConstantTimeEq(x, y int32) int { + return int((uint64(uint32(x^y)) - 1) >> 63) +} + +// ConstantTimeCopy copies the contents of y into x (a slice of equal length) +// if v == 1. If v == 0, x is left unchanged. Its behavior is undefined if v +// takes any other value. +func ConstantTimeCopy(v int, x, y []byte) { + if len(x) != len(y) { + panic("subtle: slices have different lengths") + } + + xmask := byte(v - 1) + ymask := byte(^(v - 1)) + for i := 0; i < len(x); i++ { + x[i] = x[i]&xmask | y[i]&ymask + } +} + +// ConstantTimeLessOrEq returns 1 if x <= y and 0 otherwise. +// Its behavior is undefined if x or y are negative or > 2**31 - 1. +func ConstantTimeLessOrEq(x, y int) int { + x32 := int32(x) + y32 := int32(y) + return int(((x32 - y32 - 1) >> 31) & 1) +} diff --git a/src/crypto/subtle/constant_time_test.go b/src/crypto/subtle/constant_time_test.go new file mode 100644 index 0000000..033301a --- /dev/null +++ b/src/crypto/subtle/constant_time_test.go @@ -0,0 +1,159 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package subtle + +import ( + "testing" + "testing/quick" +) + +type TestConstantTimeCompareStruct struct { + a, b []byte + out int +} + +var testConstantTimeCompareData = []TestConstantTimeCompareStruct{ + {[]byte{}, []byte{}, 1}, + {[]byte{0x11}, []byte{0x11}, 1}, + {[]byte{0x12}, []byte{0x11}, 0}, + {[]byte{0x11}, []byte{0x11, 0x12}, 0}, + {[]byte{0x11, 0x12}, []byte{0x11}, 0}, +} + +func TestConstantTimeCompare(t *testing.T) { + for i, test := range testConstantTimeCompareData { + if r := ConstantTimeCompare(test.a, test.b); r != test.out { + t.Errorf("#%d bad result (got %x, want %x)", i, r, test.out) + } + } +} + +type TestConstantTimeByteEqStruct struct { + a, b uint8 + out int +} + +var testConstandTimeByteEqData = []TestConstantTimeByteEqStruct{ + {0, 0, 1}, + {0, 1, 0}, + {1, 0, 0}, + {0xff, 0xff, 1}, + {0xff, 0xfe, 0}, +} + +func byteEq(a, b uint8) int { + if a == b { + return 1 + } + return 0 +} + +func TestConstantTimeByteEq(t *testing.T) { + for i, test := range testConstandTimeByteEqData { + if r := ConstantTimeByteEq(test.a, test.b); r != test.out { + t.Errorf("#%d bad result (got %x, want %x)", i, r, test.out) + } + } + err := quick.CheckEqual(ConstantTimeByteEq, byteEq, nil) + if err != nil { + t.Error(err) + } +} + +func eq(a, b int32) int { + if a == b { + return 1 + } + return 0 +} + +func TestConstantTimeEq(t *testing.T) { + err := quick.CheckEqual(ConstantTimeEq, eq, nil) + if err != nil { + t.Error(err) + } +} + +func makeCopy(v int, x, y []byte) []byte { + if len(x) > len(y) { + x = x[0:len(y)] + } else { + y = y[0:len(x)] + } + if v == 1 { + copy(x, y) + } + return x +} + +func constantTimeCopyWrapper(v int, x, y []byte) []byte { + if len(x) > len(y) { + x = x[0:len(y)] + } else { + y = y[0:len(x)] + } + v &= 1 + ConstantTimeCopy(v, x, y) + return x +} + +func TestConstantTimeCopy(t *testing.T) { + err := quick.CheckEqual(constantTimeCopyWrapper, makeCopy, nil) + if err != nil { + t.Error(err) + } +} + +var lessOrEqTests = []struct { + x, y, result int +}{ + {0, 0, 1}, + {1, 0, 0}, + {0, 1, 1}, + {10, 20, 1}, + {20, 10, 0}, + {10, 10, 1}, +} + +func TestConstantTimeLessOrEq(t *testing.T) { + for i, test := range lessOrEqTests { + result := ConstantTimeLessOrEq(test.x, test.y) + if result != test.result { + t.Errorf("#%d: %d <= %d gave %d, expected %d", i, test.x, test.y, result, test.result) + } + } +} + +var benchmarkGlobal uint8 + +func BenchmarkConstantTimeByteEq(b *testing.B) { + var x, y uint8 + + for i := 0; i < b.N; i++ { + x, y = uint8(ConstantTimeByteEq(x, y)), x + } + + benchmarkGlobal = x +} + +func BenchmarkConstantTimeEq(b *testing.B) { + var x, y int + + for i := 0; i < b.N; i++ { + x, y = ConstantTimeEq(int32(x), int32(y)), x + } + + benchmarkGlobal = uint8(x) +} + +func BenchmarkConstantTimeLessOrEq(b *testing.B) { + var x, y int + + for i := 0; i < b.N; i++ { + x, y = ConstantTimeLessOrEq(x, y), x + } + + benchmarkGlobal = uint8(x) +} diff --git a/src/crypto/subtle/xor.go b/src/crypto/subtle/xor.go new file mode 100644 index 0000000..a8805ac --- /dev/null +++ b/src/crypto/subtle/xor.go @@ -0,0 +1,24 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package subtle + +// XORBytes sets dst[i] = x[i] ^ y[i] for all i < n = min(len(x), len(y)), +// returning n, the number of bytes written to dst. +// If dst does not have length at least n, +// XORBytes panics without writing anything to dst. +func XORBytes(dst, x, y []byte) int { + n := len(x) + if len(y) < n { + n = len(y) + } + if n == 0 { + return 0 + } + if n > len(dst) { + panic("subtle.XORBytes: dst too short") + } + xorBytes(&dst[0], &x[0], &y[0], n) // arch-specific + return n +} diff --git a/src/crypto/subtle/xor_amd64.go b/src/crypto/subtle/xor_amd64.go new file mode 100644 index 0000000..3bb2f08 --- /dev/null +++ b/src/crypto/subtle/xor_amd64.go @@ -0,0 +1,10 @@ +// Copyright 2018 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build !purego + +package subtle + +//go:noescape +func xorBytes(dst, a, b *byte, n int) diff --git a/src/crypto/subtle/xor_amd64.s b/src/crypto/subtle/xor_amd64.s new file mode 100644 index 0000000..8b04b58 --- /dev/null +++ b/src/crypto/subtle/xor_amd64.s @@ -0,0 +1,56 @@ +// Copyright 2018 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build !purego + +#include "textflag.h" + +// func xorBytes(dst, a, b *byte, n int) +TEXT ·xorBytes(SB), NOSPLIT, $0 + MOVQ dst+0(FP), BX + MOVQ a+8(FP), SI + MOVQ b+16(FP), CX + MOVQ n+24(FP), DX + TESTQ $15, DX // AND 15 & len, if not zero jump to not_aligned. + JNZ not_aligned + +aligned: + MOVQ $0, AX // position in slices + +loop16b: + MOVOU (SI)(AX*1), X0 // XOR 16byte forwards. + MOVOU (CX)(AX*1), X1 + PXOR X1, X0 + MOVOU X0, (BX)(AX*1) + ADDQ $16, AX + CMPQ DX, AX + JNE loop16b + RET + +loop_1b: + SUBQ $1, DX // XOR 1byte backwards. + MOVB (SI)(DX*1), DI + MOVB (CX)(DX*1), AX + XORB AX, DI + MOVB DI, (BX)(DX*1) + TESTQ $7, DX // AND 7 & len, if not zero jump to loop_1b. + JNZ loop_1b + CMPQ DX, $0 // if len is 0, ret. + JE ret + TESTQ $15, DX // AND 15 & len, if zero jump to aligned. + JZ aligned + +not_aligned: + TESTQ $7, DX // AND $7 & len, if not zero jump to loop_1b. + JNE loop_1b + SUBQ $8, DX // XOR 8bytes backwards. + MOVQ (SI)(DX*1), DI + MOVQ (CX)(DX*1), AX + XORQ AX, DI + MOVQ DI, (BX)(DX*1) + CMPQ DX, $16 // if len is greater or equal 16 here, it must be aligned. + JGE aligned + +ret: + RET diff --git a/src/crypto/subtle/xor_arm64.go b/src/crypto/subtle/xor_arm64.go new file mode 100644 index 0000000..65bab4c --- /dev/null +++ b/src/crypto/subtle/xor_arm64.go @@ -0,0 +1,10 @@ +// Copyright 2020 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build !purego + +package subtle + +//go:noescape +func xorBytes(dst, a, b *byte, n int) diff --git a/src/crypto/subtle/xor_arm64.s b/src/crypto/subtle/xor_arm64.s new file mode 100644 index 0000000..7632164 --- /dev/null +++ b/src/crypto/subtle/xor_arm64.s @@ -0,0 +1,69 @@ +// Copyright 2020 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build !purego + +#include "textflag.h" + +// func xorBytes(dst, a, b *byte, n int) +TEXT ·xorBytes(SB), NOSPLIT|NOFRAME, $0 + MOVD dst+0(FP), R0 + MOVD a+8(FP), R1 + MOVD b+16(FP), R2 + MOVD n+24(FP), R3 + CMP $64, R3 + BLT tail +loop_64: + VLD1.P 64(R1), [V0.B16, V1.B16, V2.B16, V3.B16] + VLD1.P 64(R2), [V4.B16, V5.B16, V6.B16, V7.B16] + VEOR V0.B16, V4.B16, V4.B16 + VEOR V1.B16, V5.B16, V5.B16 + VEOR V2.B16, V6.B16, V6.B16 + VEOR V3.B16, V7.B16, V7.B16 + VST1.P [V4.B16, V5.B16, V6.B16, V7.B16], 64(R0) + SUBS $64, R3 + CMP $64, R3 + BGE loop_64 +tail: + // quick end + CBZ R3, end + TBZ $5, R3, less_than32 + VLD1.P 32(R1), [V0.B16, V1.B16] + VLD1.P 32(R2), [V2.B16, V3.B16] + VEOR V0.B16, V2.B16, V2.B16 + VEOR V1.B16, V3.B16, V3.B16 + VST1.P [V2.B16, V3.B16], 32(R0) +less_than32: + TBZ $4, R3, less_than16 + LDP.P 16(R1), (R11, R12) + LDP.P 16(R2), (R13, R14) + EOR R11, R13, R13 + EOR R12, R14, R14 + STP.P (R13, R14), 16(R0) +less_than16: + TBZ $3, R3, less_than8 + MOVD.P 8(R1), R11 + MOVD.P 8(R2), R12 + EOR R11, R12, R12 + MOVD.P R12, 8(R0) +less_than8: + TBZ $2, R3, less_than4 + MOVWU.P 4(R1), R13 + MOVWU.P 4(R2), R14 + EORW R13, R14, R14 + MOVWU.P R14, 4(R0) +less_than4: + TBZ $1, R3, less_than2 + MOVHU.P 2(R1), R15 + MOVHU.P 2(R2), R16 + EORW R15, R16, R16 + MOVHU.P R16, 2(R0) +less_than2: + TBZ $0, R3, end + MOVBU (R1), R17 + MOVBU (R2), R19 + EORW R17, R19, R19 + MOVBU R19, (R0) +end: + RET diff --git a/src/crypto/subtle/xor_generic.go b/src/crypto/subtle/xor_generic.go new file mode 100644 index 0000000..7dc89e3 --- /dev/null +++ b/src/crypto/subtle/xor_generic.go @@ -0,0 +1,64 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build (!amd64 && !arm64 && !ppc64 && !ppc64le) || purego + +package subtle + +import ( + "runtime" + "unsafe" +) + +const wordSize = unsafe.Sizeof(uintptr(0)) + +const supportsUnaligned = runtime.GOARCH == "386" || + runtime.GOARCH == "amd64" || + runtime.GOARCH == "ppc64" || + runtime.GOARCH == "ppc64le" || + runtime.GOARCH == "s390x" + +func xorBytes(dstb, xb, yb *byte, n int) { + // xorBytes assembly is written using pointers and n. Back to slices. + dst := unsafe.Slice(dstb, n) + x := unsafe.Slice(xb, n) + y := unsafe.Slice(yb, n) + + if supportsUnaligned || aligned(dstb, xb, yb) { + xorLoop(words(dst), words(x), words(y)) + if uintptr(n)%wordSize == 0 { + return + } + done := n &^ int(wordSize-1) + dst = dst[done:] + x = x[done:] + y = y[done:] + } + xorLoop(dst, x, y) +} + +// aligned reports whether dst, x, and y are all word-aligned pointers. +func aligned(dst, x, y *byte) bool { + return (uintptr(unsafe.Pointer(dst))|uintptr(unsafe.Pointer(x))|uintptr(unsafe.Pointer(y)))&(wordSize-1) == 0 +} + +// words returns a []uintptr pointing at the same data as x, +// with any trailing partial word removed. +func words(x []byte) []uintptr { + n := uintptr(len(x)) / wordSize + if n == 0 { + // Avoid creating a *uintptr that refers to data smaller than a uintptr; + // see issue 59334. + return nil + } + return unsafe.Slice((*uintptr)(unsafe.Pointer(&x[0])), n) +} + +func xorLoop[T byte | uintptr](dst, x, y []T) { + x = x[:len(dst)] // remove bounds check in loop + y = y[:len(dst)] // remove bounds check in loop + for i := range dst { + dst[i] = x[i] ^ y[i] + } +} diff --git a/src/crypto/subtle/xor_ppc64x.go b/src/crypto/subtle/xor_ppc64x.go new file mode 100644 index 0000000..760463c --- /dev/null +++ b/src/crypto/subtle/xor_ppc64x.go @@ -0,0 +1,10 @@ +// Copyright 2018 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build (ppc64 || ppc64le) && !purego + +package subtle + +//go:noescape +func xorBytes(dst, a, b *byte, n int) diff --git a/src/crypto/subtle/xor_ppc64x.s b/src/crypto/subtle/xor_ppc64x.s new file mode 100644 index 0000000..72bb80d --- /dev/null +++ b/src/crypto/subtle/xor_ppc64x.s @@ -0,0 +1,87 @@ +// Copyright 2018 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build (ppc64 || ppc64le) && !purego + +#include "textflag.h" + +// func xorBytes(dst, a, b *byte, n int) +TEXT ·xorBytes(SB), NOSPLIT, $0 + MOVD dst+0(FP), R3 // R3 = dst + MOVD a+8(FP), R4 // R4 = a + MOVD b+16(FP), R5 // R5 = b + MOVD n+24(FP), R6 // R6 = n + + CMPU R6, $32, CR7 // Check if n ≥ 32 bytes + MOVD R0, R8 // R8 = index + CMPU R6, $8, CR6 // Check if 8 ≤ n < 32 bytes + BLT CR6, small // Smaller than 8 + BLT CR7, xor16 // Case for 16 ≤ n < 32 bytes + + // Case for n ≥ 32 bytes +preloop32: + SRD $5, R6, R7 // Setup loop counter + MOVD R7, CTR + MOVD $16, R10 + ANDCC $31, R6, R9 // Check for tailing bytes for later +loop32: + LXVD2X (R4)(R8), VS32 // VS32 = a[i,...,i+15] + LXVD2X (R4)(R10), VS34 + LXVD2X (R5)(R8), VS33 // VS33 = b[i,...,i+15] + LXVD2X (R5)(R10), VS35 + XXLXOR VS32, VS33, VS32 // VS34 = a[] ^ b[] + XXLXOR VS34, VS35, VS34 + STXVD2X VS32, (R3)(R8) // Store to dst + STXVD2X VS34, (R3)(R10) + ADD $32, R8 // Update index + ADD $32, R10 + BC 16, 0, loop32 // bdnz loop16 + + BEQ CR0, done + + MOVD R9, R6 + CMP R6, $8 + BLT small +xor16: + CMP R6, $16 + BLT xor8 + LXVD2X (R4)(R8), VS32 + LXVD2X (R5)(R8), VS33 + XXLXOR VS32, VS33, VS32 + STXVD2X VS32, (R3)(R8) + ADD $16, R8 + ADD $-16, R6 + CMP R6, $8 + BLT small +xor8: + // Case for 8 ≤ n < 16 bytes + MOVD (R4)(R8), R14 // R14 = a[i,...,i+7] + MOVD (R5)(R8), R15 // R15 = b[i,...,i+7] + XOR R14, R15, R16 // R16 = a[] ^ b[] + SUB $8, R6 // n = n - 8 + MOVD R16, (R3)(R8) // Store to dst + ADD $8, R8 + + // Check if we're finished + CMP R6, R0 + BGT small + RET + + // Case for n < 8 bytes and tailing bytes from the + // previous cases. +small: + CMP R6, R0 + BEQ done + MOVD R6, CTR // Setup loop counter + +loop: + MOVBZ (R4)(R8), R14 // R14 = a[i] + MOVBZ (R5)(R8), R15 // R15 = b[i] + XOR R14, R15, R16 // R16 = a[i] ^ b[i] + MOVB R16, (R3)(R8) // Store to dst + ADD $1, R8 + BC 16, 0, loop // bdnz loop + +done: + RET diff --git a/src/crypto/subtle/xor_test.go b/src/crypto/subtle/xor_test.go new file mode 100644 index 0000000..7d89b83 --- /dev/null +++ b/src/crypto/subtle/xor_test.go @@ -0,0 +1,106 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package subtle_test + +import ( + "bytes" + "crypto/rand" + . "crypto/subtle" + "fmt" + "io" + "testing" +) + +func TestXORBytes(t *testing.T) { + for n := 1; n <= 1024; n++ { + if n > 16 && testing.Short() { + n += n >> 3 + } + for alignP := 0; alignP < 8; alignP++ { + for alignQ := 0; alignQ < 8; alignQ++ { + for alignD := 0; alignD < 8; alignD++ { + p := make([]byte, alignP+n, alignP+n+10)[alignP:] + q := make([]byte, alignQ+n, alignQ+n+10)[alignQ:] + if n&1 != 0 { + p = p[:n] + } else { + q = q[:n] + } + if _, err := io.ReadFull(rand.Reader, p); err != nil { + t.Fatal(err) + } + if _, err := io.ReadFull(rand.Reader, q); err != nil { + t.Fatal(err) + } + + d := make([]byte, alignD+n, alignD+n+10) + for i := range d { + d[i] = 0xdd + } + want := make([]byte, len(d), cap(d)) + copy(want[:cap(want)], d[:cap(d)]) + for i := 0; i < n; i++ { + want[alignD+i] = p[i] ^ q[i] + } + + if XORBytes(d[alignD:], p, q); !bytes.Equal(d, want) { + t.Fatalf("n=%d alignP=%d alignQ=%d alignD=%d:\n\tp = %x\n\tq = %x\n\td = %x\n\twant %x\n", n, alignP, alignQ, alignD, p, q, d, want) + } + } + } + } + } +} + +func TestXorBytesPanic(t *testing.T) { + mustPanic(t, "subtle.XORBytes: dst too short", func() { + XORBytes(nil, make([]byte, 1), make([]byte, 1)) + }) + mustPanic(t, "subtle.XORBytes: dst too short", func() { + XORBytes(make([]byte, 1), make([]byte, 2), make([]byte, 3)) + }) +} + +func min(a, b []byte) int { + n := len(a) + if len(b) < n { + n = len(b) + } + return n +} + +func BenchmarkXORBytes(b *testing.B) { + dst := make([]byte, 1<<15) + data0 := make([]byte, 1<<15) + data1 := make([]byte, 1<<15) + sizes := []int64{1 << 3, 1 << 7, 1 << 11, 1 << 15} + for _, size := range sizes { + b.Run(fmt.Sprintf("%dBytes", size), func(b *testing.B) { + s0 := data0[:size] + s1 := data1[:size] + b.SetBytes(int64(size)) + for i := 0; i < b.N; i++ { + XORBytes(dst, s0, s1) + } + }) + } +} + +func mustPanic(t *testing.T, expected string, f func()) { + t.Helper() + defer func() { + switch msg := recover().(type) { + case nil: + t.Errorf("expected panic(%q), but did not panic", expected) + case string: + if msg != expected { + t.Errorf("expected panic(%q), but got panic(%q)", expected, msg) + } + default: + t.Errorf("expected panic(%q), but got panic(%T%v)", expected, msg, msg) + } + }() + f() +} |