From 899732a43256a5d6fb779917f597b32939ca4ba4 Mon Sep 17 00:00:00 2001 From: "dependabot[bot]" <49699333+dependabot[bot]@users.noreply.github.com> Date: Tue, 19 Dec 2023 00:08:14 +0000 Subject: [PATCH 1/3] build(deps): bump golang.org/x/crypto Bumps [golang.org/x/crypto](https://github.com/golang/crypto) from 0.3.1-0.20221117191849-2c476679df9a to 0.17.0. - [Commits](https://github.com/golang/crypto/commits/v0.17.0) --- updated-dependencies: - dependency-name: golang.org/x/crypto dependency-type: direct:production ... Signed-off-by: dependabot[bot] --- go.mod | 4 ++-- go.sum | 8 ++++---- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/go.mod b/go.mod index 3c9038c26..b172460a3 100644 --- a/go.mod +++ b/go.mod @@ -4,6 +4,6 @@ go 1.19 require ( github.com/bwesterb/go-ristretto v1.2.3 - golang.org/x/crypto v0.3.1-0.20221117191849-2c476679df9a - golang.org/x/sys v0.3.0 + golang.org/x/crypto v0.17.0 + golang.org/x/sys v0.15.0 ) diff --git a/go.sum b/go.sum index e48cb252d..a328e6986 100644 --- a/go.sum +++ b/go.sum @@ -1,6 +1,6 @@ github.com/bwesterb/go-ristretto v1.2.3 h1:1w53tCkGhCQ5djbat3+MH0BAQ5Kfgbt56UZQ/JMzngw= github.com/bwesterb/go-ristretto v1.2.3/go.mod h1:fUIoIZaG73pV5biE2Blr2xEzDoMj7NFEuV9ekS419A0= -golang.org/x/crypto v0.3.1-0.20221117191849-2c476679df9a h1:diz9pEYuTIuLMJLs3rGDkeaTsNyRs6duYdFyPAxzE/U= -golang.org/x/crypto v0.3.1-0.20221117191849-2c476679df9a/go.mod h1:hebNnKkNXi2UzZN1eVRvBB7co0a+JxK6XbPiWVs/3J4= -golang.org/x/sys v0.3.0 h1:w8ZOecv6NaNa/zC8944JTU3vz4u6Lagfk4RPQxv92NQ= -golang.org/x/sys v0.3.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg= +golang.org/x/crypto v0.17.0 h1:r8bRNjWL3GshPW3gkd+RpvzWrZAwPS49OmTGZ/uhM4k= +golang.org/x/crypto v0.17.0/go.mod h1:gCAAfMLgwOJRpTjQ2zCCt2OcSfYMTeZVSRtQlPC7Nq4= +golang.org/x/sys v0.15.0 h1:h48lPFYpsTvQJZF4EKyI4aLHaev3CxivZmv7yZig9pc= +golang.org/x/sys v0.15.0/go.mod h1:/VUhepiaJMQUp4+oa/7Zr1D23ma6VTLIYjOOTFZPUcA= From 75ef91e8a2f438e6ce2b6e620d236add8be1887d Mon Sep 17 00:00:00 2001 From: Bas Westerbaan Date: Sat, 30 Dec 2023 13:47:10 +0100 Subject: [PATCH 2/3] kyber: remove division by q in ciphertext compression On some platforms, division by q leaks some information on the ciphertext by its timing. If a keypair is reused, and an attacker has access to a decapsulation oracle, this reveals information on the private key. This is known as "kyberslash2". Note that this does not affect to the typical ephemeral usage in TLS. --- pke/kyber/internal/common/poly.go | 28 ++++--- pke/kyber/internal/common/poly_test.go | 105 +++++++++++++++++++++++++ 2 files changed, 123 insertions(+), 10 deletions(-) diff --git a/pke/kyber/internal/common/poly.go b/pke/kyber/internal/common/poly.go index d72f35d36..f580e9150 100644 --- a/pke/kyber/internal/common/poly.go +++ b/pke/kyber/internal/common/poly.go @@ -166,7 +166,7 @@ func (p *Poly) CompressMessageTo(m []byte) { // Set p to Decompress_q(m, 1). // -// Assumes d is in {3, 4, 5, 10, 11}. p will be normalized. +// Assumes d is in {4, 5, 10, 11}. p will be normalized. func (p *Poly) Decompress(m []byte, d int) { // Decompress_q(x, d) = ⌈(q/2ᵈ)x⌋ // = ⌊(q/2ᵈ)x+½⌋ @@ -244,20 +244,28 @@ func (p *Poly) Decompress(m []byte, d int) { // Writes Compress_q(p, d) to m. // -// Assumes p is normalized and d is in {3, 4, 5, 10, 11}. +// Assumes p is normalized and d is in {4, 5, 10, 11}. func (p *Poly) CompressTo(m []byte, d int) { // Compress_q(x, d) = ⌈(2ᵈ/q)x⌋ mod⁺ 2ᵈ // = ⌊(2ᵈ/q)x+½⌋ mod⁺ 2ᵈ // = ⌊((x << d) + q/2) / q⌋ mod⁺ 2ᵈ // = DIV((x << d) + q/2, q) & ((1<>e, where a/(2^e) ≈ 1/q. + // For d in {10,11} we use 20,642,679/2^36, which computes division by x/q + // correctly for 0 ≤ x < 41,522,616, which fits (q << 11) + q/2 comfortably. + // For d in {4,5} we use 315/2^20, which doesn't compute division by x/q + // correctly for all inputs, but it's close enough that the end result + // of the compression is correct. The advantage is that we do not need + // to use a 64-bit intermediate value. switch d { case 4: var t [8]uint16 idx := 0 for i := 0; i < N/8; i++ { for j := 0; j < 8; j++ { - t[j] = uint16(((uint32(p[8*i+j])<<4)+uint32(Q)/2)/ - uint32(Q)) & ((1 << 4) - 1) + t[j] = uint16((((uint32(p[8*i+j])<<4)+uint32(Q)/2)*315)>> + 20) & ((1 << 4) - 1) } m[idx] = byte(t[0]) | byte(t[1]<<4) m[idx+1] = byte(t[2]) | byte(t[3]<<4) @@ -271,8 +279,8 @@ func (p *Poly) CompressTo(m []byte, d int) { idx := 0 for i := 0; i < N/8; i++ { for j := 0; j < 8; j++ { - t[j] = uint16(((uint32(p[8*i+j])<<5)+uint32(Q)/2)/ - uint32(Q)) & ((1 << 5) - 1) + t[j] = uint16((((uint32(p[8*i+j])<<5)+uint32(Q)/2)*315)>> + 20) & ((1 << 5) - 1) } m[idx] = byte(t[0]) | byte(t[1]<<5) m[idx+1] = byte(t[1]>>3) | byte(t[2]<<2) | byte(t[3]<<7) @@ -287,8 +295,8 @@ func (p *Poly) CompressTo(m []byte, d int) { idx := 0 for i := 0; i < N/4; i++ { for j := 0; j < 4; j++ { - t[j] = uint16(((uint32(p[4*i+j])<<10)+uint32(Q)/2)/ - uint32(Q)) & ((1 << 10) - 1) + t[j] = uint16((uint64((uint32(p[4*i+j])<<10)+uint32(Q)/2)* + 20642679)>>36) & ((1 << 10) - 1) } m[idx] = byte(t[0]) m[idx+1] = byte(t[0]>>8) | byte(t[1]<<2) @@ -302,8 +310,8 @@ func (p *Poly) CompressTo(m []byte, d int) { idx := 0 for i := 0; i < N/8; i++ { for j := 0; j < 8; j++ { - t[j] = uint16(((uint32(p[8*i+j])<<11)+uint32(Q)/2)/ - uint32(Q)) & ((1 << 11) - 1) + t[j] = uint16((uint64((uint32(p[8*i+j])<<11)+uint32(Q)/2)* + 20642679)>>36) & ((1 << 11) - 1) } m[idx] = byte(t[0]) m[idx+1] = byte(t[0]>>8) | byte(t[1]<<3) diff --git a/pke/kyber/internal/common/poly_test.go b/pke/kyber/internal/common/poly_test.go index fcce5fa78..350bef961 100644 --- a/pke/kyber/internal/common/poly_test.go +++ b/pke/kyber/internal/common/poly_test.go @@ -1,6 +1,7 @@ package common import ( + "bytes" "crypto/rand" "fmt" "testing" @@ -273,3 +274,107 @@ func TestNormalizeAgainstGeneric(t *testing.T) { } } } + +func (p *Poly) OldCompressTo(m []byte, d int) { + switch d { + case 4: + var t [8]uint16 + idx := 0 + for i := 0; i < N/8; i++ { + for j := 0; j < 8; j++ { + t[j] = uint16(((uint32(p[8*i+j])<<4)+uint32(Q)/2)/ + uint32(Q)) & ((1 << 4) - 1) + } + m[idx] = byte(t[0]) | byte(t[1]<<4) + m[idx+1] = byte(t[2]) | byte(t[3]<<4) + m[idx+2] = byte(t[4]) | byte(t[5]<<4) + m[idx+3] = byte(t[6]) | byte(t[7]<<4) + idx += 4 + } + + case 5: + var t [8]uint16 + idx := 0 + for i := 0; i < N/8; i++ { + for j := 0; j < 8; j++ { + t[j] = uint16(((uint32(p[8*i+j])<<5)+uint32(Q)/2)/ + uint32(Q)) & ((1 << 5) - 1) + } + m[idx] = byte(t[0]) | byte(t[1]<<5) + m[idx+1] = byte(t[1]>>3) | byte(t[2]<<2) | byte(t[3]<<7) + m[idx+2] = byte(t[3]>>1) | byte(t[4]<<4) + m[idx+3] = byte(t[4]>>4) | byte(t[5]<<1) | byte(t[6]<<6) + m[idx+4] = byte(t[6]>>2) | byte(t[7]<<3) + idx += 5 + } + + case 10: + var t [4]uint16 + idx := 0 + for i := 0; i < N/4; i++ { + for j := 0; j < 4; j++ { + t[j] = uint16(((uint32(p[4*i+j])<<10)+uint32(Q)/2)/ + uint32(Q)) & ((1 << 10) - 1) + } + m[idx] = byte(t[0]) + m[idx+1] = byte(t[0]>>8) | byte(t[1]<<2) + m[idx+2] = byte(t[1]>>6) | byte(t[2]<<4) + m[idx+3] = byte(t[2]>>4) | byte(t[3]<<6) + m[idx+4] = byte(t[3] >> 2) + idx += 5 + } + case 11: + var t [8]uint16 + idx := 0 + for i := 0; i < N/8; i++ { + for j := 0; j < 8; j++ { + t[j] = uint16(((uint32(p[8*i+j])<<11)+uint32(Q)/2)/ + uint32(Q)) & ((1 << 11) - 1) + } + m[idx] = byte(t[0]) + m[idx+1] = byte(t[0]>>8) | byte(t[1]<<3) + m[idx+2] = byte(t[1]>>5) | byte(t[2]<<6) + m[idx+3] = byte(t[2] >> 2) + m[idx+4] = byte(t[2]>>10) | byte(t[3]<<1) + m[idx+5] = byte(t[3]>>7) | byte(t[4]<<4) + m[idx+6] = byte(t[4]>>4) | byte(t[5]<<7) + m[idx+7] = byte(t[5] >> 1) + m[idx+8] = byte(t[5]>>9) | byte(t[6]<<2) + m[idx+9] = byte(t[6]>>6) | byte(t[7]<<5) + m[idx+10] = byte(t[7] >> 3) + idx += 11 + } + default: + panic("unsupported d") + } +} + +func TestCompressFullInputFirstCoeff(t *testing.T) { + for _, d := range []int{4, 5, 10, 11} { + d := d + t.Run(fmt.Sprintf("d=%d", d), func(t *testing.T) { + var p, q Poly + bound := (Q + (1 << uint(d))) >> uint(d+1) + buf := make([]byte, (N*d-1)/8+1) + buf2 := make([]byte, len(buf)) + for i := int16(0); i < Q; i++ { + p[0] = i + p.CompressTo(buf, d) + p.OldCompressTo(buf2, d) + if !bytes.Equal(buf, buf2) { + t.Fatalf("%d", i) + } + q.Decompress(buf, d) + diff := sModQ(p[0] - q[0]) + if diff < 0 { + diff = -diff + } + if diff > bound { + t.Logf("%v\n", buf) + t.Fatalf("|%d - %d mod^± q| = %d > %d", + p[0], q[0], diff, bound) + } + } + }) + } +} From c48866b3068dfa83721c021dec03c777ba91abab Mon Sep 17 00:00:00 2001 From: armfazh Date: Sun, 31 Dec 2023 21:20:43 -0800 Subject: [PATCH 3/3] Releasing CIRCL v1.3.7 --- CITATION.cff | 4 ++-- README.md | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/CITATION.cff b/CITATION.cff index 35616cbbe..53c96566b 100644 --- a/CITATION.cff +++ b/CITATION.cff @@ -1,6 +1,6 @@ --- cff-version: 1.2.0 -version: 1.3.6 +version: 1.3.7 title: "Introducing CIRCL: An Advanced Cryptographic Library" license: BSD-3-Clause abstract: > @@ -25,6 +25,6 @@ keywords: - golang repository-code: "https://github.com/cloudflare/circl/" type: software -message: "Available at https://github.com/cloudflare/circl. v1.3.6 Accessed Oct, 2023." +message: "Available at https://github.com/cloudflare/circl. v1.3.7 Accessed Dec, 2023." contact: - name: "Cloudflare, Inc." diff --git a/README.md b/README.md index 4d8c9984b..1f24168ad 100644 --- a/README.md +++ b/README.md @@ -159,7 +159,7 @@ APA Style ``` Faz-Hernández, A. and Kwiatkowski, K. (2019). Introducing CIRCL: An Advanced Cryptographic Library. Cloudflare. Available at -https://github.com/cloudflare/circl. v1.3.6 Accessed Oct, 2023. +https://github.com/cloudflare/circl. v1.3.7 Accessed Dec, 2023. ``` Bibtex Source @@ -174,7 +174,7 @@ Bibtex Source of this library is to be used as a tool for experimental deployment of cryptographic algorithms targeting Post-Quantum (PQ) and Elliptic Curve Cryptography (ECC).}}, - note = {Available at \url{https://github.com/cloudflare/circl}. v1.3.6 Accessed Oct, 2023}, + note = {Available at \url{https://github.com/cloudflare/circl}. v1.3.7 Accessed Dec, 2023}, month = jun, year = {2019} }