Debian Codegraph @

external/boringssl/ssl/test/runner/newhope/newhope.go

raw
1 // Copyright (c) 2016, Google Inc.
2 //
3 // Permission to use, copy, modify, and/or distribute this software for any
4 // purpose with or without fee is hereby granted, provided that the above
5 // copyright notice and this permission notice appear in all copies.
6 //
7 // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 // package newhope contains a post-quantum key agreement algorithm,
16 // reimplemented from the reference implementation at
17 // https://github.com/tpoeppelmann/newhope.
18 //
19 // Note that this package does not interoperate with the reference
20 // implementation.
21 package newhope
22
23 import (
24 "crypto/aes"
25 "crypto/cipher"
26 "errors"
27 "io"
28 )
29
30 const (
31 // q is the prime that defines the field.
32 q = 12289
33 // n is the number of coefficients in polynomials.
34 n = 1024
35 // k is the width of the noise distribution.
36 k = 16
37
38 // These values are used in the NTT calculation. See the paper for
39 // details about their origins.
40 omega = 49
41 invOmega = 1254
42 sqrtOmega = 7
43 invSqrtOmega = 8778
44 invN = 12277
45
46 // encodedPolyLen is the length, in bytes, of an encoded polynomial. The
47 // encoding uses 14 bits per coefficient.
48 encodedPolyLen = (n * 14) / 8
49
50 // offerMsgLen is the length, in bytes, of the offering (first) message of
51 // the key exchange.
52 OfferMsgLen = encodedPolyLen + 32
53
54 // acceptMsgLen is the length, in bytes, of the accepting (second) message
55 // of the key exchange.
56 AcceptMsgLen = encodedPolyLen + 256
57 )
58
59 // count16Bits returns the number of '1' bits in v.
60 func count16Bits(v uint16) (sum uint16) {
61 for i := 0; i < 16; i++ {
62 sum += v & 1
63 v >>= 1
64 }
65
66 return sum
67 }
68
69 // Poly is a polynomial of n coefficients.
70 type Poly [n]uint16
71
72 // Key is the result of a key agreement.
73 type Key [32]uint8
74
75 // sampleNoise returns a random polynomial where the coefficients are
76 // drawn from the noise distribution.
77 func sampleNoise(rand io.Reader) *Poly {
78 poly := new(Poly)
79 buf := make([]byte, 4)
80
81 for i := range poly {
82 if _, err := io.ReadFull(rand, buf); err != nil {
83 panic(err)
84 }
85 a := count16Bits(uint16(buf[0])<<8 | uint16(buf[1]))
86 b := count16Bits(uint16(buf[2])<<8 | uint16(buf[3]))
87 poly[i] = (q + a - b) % q
88 }
89
90 return poly
91 }
92
93 // randomPolynomial returns a random polynomial where the coefficients are
94 // drawn uniformly at random from the underlying field.
95 func randomPolynomial(rand io.Reader) *Poly {
96 poly := new(Poly)
97
98 buf := make([]byte, 2)
99 for i := range poly {
100 for {
101 if _, err := io.ReadFull(rand, buf); err != nil {
102 panic(err)
103 }
104
105 v := uint16(buf[1])<<8 | uint16(buf[0])
106 v &= 0x3fff
107
108 if v < q {
109 poly[i] = v
110 break
111 }
112 }
113 }
114
115 return poly
116 }
117
118 type zeroReader struct {
119 io.Reader
120 }
121
122 func (z *zeroReader) Read(dst []byte) (n int, err error) {
123 for i := range dst {
124 dst[i] = 0
125 }
126 return len(dst), nil
127 }
128
129 // seedToPolynomial uses AES-CTR to generate a pseudo-random polynomial given a
130 // 32-byte seed.
131 func seedToPolynomial(seed []byte) *Poly {
132 aes, err := aes.NewCipher(seed[0:16])
133 if err != nil {
134 panic(err)
135 }
136 stream := cipher.NewCTR(aes, seed[16:32])
137 reader := &cipher.StreamReader{S: stream, R: &zeroReader{}}
138 return randomPolynomial(reader)
139 }
140
141 // forwardNTT converts |in| into the frequency domain.
142 func forwardNTT(in *Poly) *Poly {
143 return ntt(in, omega, sqrtOmega, 1, 1)
144 }
145
146 // inverseNTT converts |in| into the time domain.
147 func inverseNTT(in *Poly) *Poly {
148 return ntt(in, invOmega, 1, invSqrtOmega, invN)
149 }
150
151 // ntt performs the number-theoretic transform (a discrete Fourier transform in
152 // a field) on in. Significant magic is in effect here. See the paper for the
153 // details of how this works.
154 func ntt(in *Poly, omega, preScaleBase, postScaleBase, postScale uint16) *Poly {
155 out := new(Poly)
156 omega_to_the_i := uint64(1)
157
158 for i := range out {
159 omegaToTheIJ := uint64(1)
160 preScale := uint64(1)
161 sum := uint64(0)
162
163 for j := range in {
164 t := (uint64(in[j]) * preScale) % q
165 sum += (t * omegaToTheIJ) % q
166 omegaToTheIJ = (omegaToTheIJ * omega_to_the_i) % q
167 preScale = (uint64(preScaleBase) * preScale) % q
168 }
169
170 out[i] = uint16((sum * uint64(postScale)) % q)
171
172 omega_to_the_i = (omega_to_the_i * uint64(omega)) % q
173 postScale = uint16((uint64(postScale) * uint64(postScaleBase)) % q)
174 }
175
176 return out
177 }
178
179 // encodeRec encodes the reconciliation data compactly, for use in the accept
180 // message.
181 func encodeRec(rec *reconciliationData) []byte {
182 var ret [n / 4]byte
183
184 for i := 0; i < n/4; i++ {
185 ret[i] = rec[4*i] | rec[4*i+1]<<2 | rec[4*i+2]<<4 | rec[4*i+3]<<6
186 }
187
188 return ret[:]
189 }
190
191 // decodeRec decodes reconciliation data from the accept message.
192 func decodeRec(message []byte) (rec *reconciliationData) {
193 rec = new(reconciliationData)
194
195 for i, b := range message {
196 rec[4*i] = b & 0x03
197 rec[4*i+1] = (b >> 2) & 0x3
198 rec[4*i+2] = (b >> 4) & 0x3
199 rec[4*i+3] = b >> 6
200 }
201
202 return rec
203 }
204
205 // encodePoly returns a byte array that encodes a polynomial compactly, with 14
206 // bits per coefficient.
207 func encodePoly(poly *Poly) []byte {
208 ret := make([]byte, encodedPolyLen)
209
210 for i := 0; i < n/4; i++ {
211 t0 := poly[4*i]
212 t1 := poly[4*i+1]
213 t2 := poly[4*i+2]
214 t3 := poly[4*i+3]
215
216 ret[7*i] = byte(t0)
217 ret[7*i+1] = byte(t0>>8) | byte(t1<<6)
218 ret[7*i+2] = byte(t1 >> 2)
219 ret[7*i+3] = byte(t1>>10) | byte(t2<<4)
220 ret[7*i+4] = byte(t2 >> 4)
221 ret[7*i+5] = byte(t2>>12) | byte(t3<<2)
222 ret[7*i+6] = byte(t3 >> 6)
223 }
224
225 return ret
226 }
227
228 // decodePoly inverts encodePoly.
229 func decodePoly(encoded []byte) *Poly {
230 ret := new(Poly)
231
232 for i := 0; i < n/4; i++ {
233 ret[4*i] = uint16(encoded[7*i]) | uint16(encoded[7*i+1]&0x3f)<<8
234 ret[4*i+1] = uint16(encoded[7*i+1])>>6 | uint16(encoded[7*i+2])<<2 | uint16(encoded[7*i+3]&0x0f)<<10
235 ret[4*i+2] = uint16(encoded[7*i+3])>>4 | uint16(encoded[7*i+4])<<4 | uint16(encoded[7*i+5]&0x03)<<12
236 ret[4*i+3] = uint16(encoded[7*i+5])>>2 | uint16(encoded[7*i+6])<<6
237 }
238
239 return ret
240 }
241
242 // Offer starts a new key exchange. It returns a message that should be
243 // transmitted to the peer, and a polynomial that must be retained in order to
244 // complete the exchange.
245 func Offer(rand io.Reader) (offerMsg []byte, sFreq *Poly) {
246 seed := make([]byte, 32)
247
248 if _, err := io.ReadFull(rand, seed); err != nil {
249 panic(err)
250 }
251
252 aFreq := seedToPolynomial(seed)
253 sFreq = forwardNTT(sampleNoise(rand))
254 eFreq := forwardNTT(sampleNoise(rand))
255
256 bFreq := new(Poly)
257 for i := range bFreq {
258 bFreq[i] = uint16((uint64(sFreq[i])*uint64(aFreq[i]) + uint64(eFreq[i])) % q)
259 }
260
261 offerMsg = encodePoly(bFreq)
262 offerMsg = append(offerMsg, seed[:]...)
263 return offerMsg, sFreq
264 }
265
266 // Accept processes a message generated by |Offer| and returns a reply message
267 // and the shared key.
268 func Accept(rand io.Reader, offerMsg []byte) (sharedKey Key, acceptMsg []byte, err error) {
269 if len(offerMsg) != OfferMsgLen {
270 return sharedKey, nil, errors.New("newhope: offer message has incorrect length")
271 }
272
273 bFreq := decodePoly(offerMsg)
274 seed := offerMsg[encodedPolyLen:]
275
276 aFreq := seedToPolynomial(seed)
277 sPrimeFreq := forwardNTT(sampleNoise(rand))
278 ePrimeFreq := forwardNTT(sampleNoise(rand))
279
280 uFreq := new(Poly)
281 for i := range uFreq {
282 uFreq[i] = uint16((uint64(sPrimeFreq[i])*uint64(aFreq[i]) + uint64(ePrimeFreq[i])) % q)
283 }
284
285 vFreq := new(Poly)
286 for i := range vFreq {
287 vFreq[i] = uint16((uint64(sPrimeFreq[i]) * uint64(bFreq[i])) % q)
288 }
289
290 v := inverseNTT(vFreq)
291 ePrimePrime := sampleNoise(rand)
292 for i := range v {
293 v[i] = uint16((uint64(v[i]) + uint64(ePrimePrime[i])) % q)
294 }
295
296 rec := helprec(rand, v)
297
298 sharedKey = reconcile(v, rec)
299 acceptMsg = encodePoly(uFreq)
300 acceptMsg = append(acceptMsg, encodeRec(rec)[:]...)
301 return sharedKey, acceptMsg, nil
302 }
303
304 // Finish processes the reply from the peer and returns the shared key.
305 func (sk *Poly) Finish(acceptMsg []byte) (sharedKey Key, err error) {
306 if len(acceptMsg) != AcceptMsgLen {
307 return sharedKey, errors.New("newhope: accept message has incorrect length")
308 }
309
310 uFreq := decodePoly(acceptMsg[:encodedPolyLen])
311 rec := decodeRec(acceptMsg[encodedPolyLen:])
312
313 for i, u := range uFreq {
314 uFreq[i] = uint16((uint64(u) * uint64(sk[i])) % q)
315 }
316 u := inverseNTT(uFreq)
317
318 return reconcile(u, rec), nil
319 }