Assign the RebelAlliance hybrid handshake proposal a number.

1 files changed, 764 insertions, 0 deletions

diff --git a/proposals/270-newhope-hybrid-handshake.txt b/proposals/270-newhope-hybrid-handshake.txt
new file mode 100644
index 0000000..ccf3390
--- /dev/null
+++ b/proposals/270-newhope-hybrid-handshake.txt
@@ -0,0 +1,764 @@
+Filename: 270-newhope-hybrid-handshake.txt
+Title: RebelAlliance: A Post-Quantum Secure Hybrid Handshake Based on NewHope
+Author: Isis Lovecruft, Peter Schwabe
+Created: 16 Apr 2016
+Updated: 22 Jul 2016
+Status: Draft
+Depends: prop#220 prop#249 prop#264 prop#270
+
+§0. Introduction
+
+  RebelAlliance is a post-quantum secure hybrid handshake, comprised of an
+  alliance between the X25519 and NewHope key exchanges.
+
+  NewHope is a post-quantum-secure lattice-based key-exchange protocol based
+  on the ring-learning-with-errors (Ring-LWE) problem.  We propose a hybrid
+  handshake for Tor, based on a combination of Tor's current NTor handshake
+  and a shared key derived through a NewHope ephemeral key exchange.
+
+  For further details on the NewHope key exchange, the reader is referred to
+  "Post-quantum key exchange - a new hope" by Alkim, Ducas, Pöppelmann, and
+  Schwabe [0][1].
+
+  For the purposes of brevity, we consider that NTor is currently the only
+  handshake protocol in Tor; the older TAP protocol is ignored completely, due
+  to the fact that it is currently deprecated and nearly entirely unused.
+
+
+§1. Motivation
+
+  An attacker currently monitoring and storing circuit-layer NTor handshakes
+  who later has the ability to run Shor's algorithm on a quantum computer will
+  be able to break Tor's current handshake protocol and decrypt previous
+  communications.
+
+  It is unclear if and when such attackers equipped with large quantum
+  computers will exist, but various estimates by researchers in quantum
+  physics and quantum engineering give estimates of only 1 to 2 decades.
+  Clearly, the security requirements of many Tor users include secrecy of
+  their messages beyond this time span, which means that Tor needs to update
+  the key exchange to protect against such attackers as soon as possible.
+
+
+§2. Design
+
+  An initiator and responder, in parallel, conduct two handshakes:
+
+  - An X25519 key exchange, as described in the description of the NTor
+    handshake in Tor proposal #216.
+  - A NewHope key exchange.
+
+  The shared keys derived from these two handshakes are then concatenated and
+  used as input to the SHAKE-256 extendable output function (XOF), as described
+  in FIPS-PUB-202 [2], in order to produce a shared key of the desired length.
+  The testvectors in §C assume that this key has a length of 32 bytes, but the
+  use of a XOF allows arbitrary lengths to easily support future updates of
+  the symmetric primitives using the key. See also §3.3.1.
+
+
+§3. Specification
+
+§3.1. Notation
+
+  Let `a || b` be the concatenation of a with b.
+
+  Let `a^b` denote the exponentiation of a to the bth power.
+
+  Let `a == b` denote the equality of a with b, and vice versa.
+
+  Let `a := b` be the assignment of the value of b to the variable a.
+
+  Let `H(x)` be 32-bytes of output of the SHAKE-256 XOF (as described in
+  FIPS-PUB-202) applied to message x.
+
+  Let X25519 refer to the curve25519-based key agreement protocol described
+  in RFC7748 §6.1. [3]
+
+  Let `EXP(a, b) == X25519(., b, a)` with `g == 9`. Let X25519_KEYGEN() do
+  the appropriate manipulations when generating the secret key (clearing the
+  low bits, twidding the high bits).  Additionally, EXP() MUST include the
+  check for all-zero output due to the input point being of small
+  order (cf. RFC7748 §6).
+
+  Let `X25519_KEYID(B) == B` where B is a valid X25519 public key.
+
+  When representing an element of the Curve25519 subgroup as a byte string,
+  use the standard (32-byte, little-endian, x-coordinate-only) representation
+  for Curve25519 points.
+
+  Let `ID` be a router's identity key taken from the router microdescriptor.
+  In the case for relays possessing Ed25519 identity keys (cf. Tor proposal
+  #220), this is a 32-byte string representing the public Ed25519 identity key.
+  For backwards and forwards compatibility with routers which do not possess
+  Ed25519 identity keys, this is a 32-byte string created via the output of
+  H(ID).
+
+  We refer to the router as the handshake "responder", and the client (which
+  may be an OR or an OP) as the "initiator".
+
+
+  ID_LENGTH      [32 bytes]
+  H_LENGTH       [32 bytes]
+  G_LENGTH       [32 bytes]
+
+  PROTOID  :=    "pqtor-x25519-newhope-shake256-1"
+  T_MAC    :=    PROTOID || ":mac"
+  T_KEY    :=    PROTOID || ":key_extract"
+  T_VERIFY :=    PROTOID || ":verify"
+
+  (X25519_SK, X25519_PK) := X25519_KEYGEN()
+
+
+§3.2. Protocol
+
+ ========================================================================================
+ |                                                                                      |
+ | Fig. 1: The NewHope-X25519 Hybrid Handshake.                                         |
+ |                                                                                      |
+ | Before the handshake the Initiator is assumed to know Z, a public X25519 key for     |
+ | the Responder, as well as the Responder's ID.                                        |
+ ----------------------------------------------------------------------------------------
+ |                                                                                      |
+ | Initiator                             Responder                                      |
+ |                                                                                      |
+ | SEED         := H(randombytes(32))                                                   |
+ | x, X         := X25519_KEYGEN()                                                      |
+ | a, A         := NEWHOPE_KEYGEN(SEED)                                                 |
+ | CLIENT_HDATA := ID || Z || X || A                                                    |
+ |                                                                                      |
+ |               --- CLIENT_HDATA --->                                                  |
+ |                                                                                      |
+ |                                       y, Y           := X25519_KEYGEN()              |
+ |                                       NTOR_KEY, AUTH := NTOR_SHAREDB(X,y,Y,z,Z,ID,B) |
+ |                                       M, NEWHOPE_KEY := NEWHOPE_SHAREDB(A)           |
+ |                                       SERVER_HDATA   := Y || AUTH || M               |
+ |                                       sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)       |
+ |                                                                                      |
+ |               <-- SERVER_HDATA ----                                                  |
+ |                                                                                      |
+ | NTOR_KEY    := NTOR_SHAREDA(x, X, Y, Z, ID, AUTH)                                    |
+ | NEWHOPE_KEY := NEWHOPE_SHAREDA(M, a)                                                 |
+ | sk := SHAKE-256(NTOR_KEY || NEWHOPE_KEY)                                             |
+ |                                                                                      |
+ ========================================================================================
+
+
+§3.2.1. The NTor Handshake
+
+§3.2.1.1. Prologue
+
+  Take a router with identity ID. As setup, the router generates a secret key z,
+  and a public onion key Z with:
+
+    z, Z := X25519_KEYGEN()
+
+  The router publishes Z in its server descriptor in the "ntor-onion-key" entry.
+  Henceforward, we refer to this router as the "responder".
+
+
+§3.2.1.2. Initiator
+
+  To send a create cell, the initiator generates a keypair:
+
+    x, X := X25519_KEYGEN()
+
+  and creates the NTor portion of a CREATE2V cell's HDATA section:
+
+    CLIENT_NTOR    := ID || Z || X                   [96 bytes]
+
+  The initiator includes the responder's ID and Z in the CLIENT_NTOR so that, in
+  the event the responder OR has recently rotated keys, the responder can
+  determine which keypair to use.
+
+  The initiator then concatenates CLIENT_NTOR with CLIENT_NEWHOPE (see §3.2.2),
+  to create CLIENT_HDATA, and creates and sends a CREATE2V cell (see §A.1)
+  to the responder.
+
+    CLIENT_NEWHOPE                                   [1824 bytes]  (see §3.2.2)
+    CLIENT_HDATA   := CLIENT_NTOR || CLIENT_NEWHOPE  [1920 bytes]
+
+  If the responder does not respond with a CREATED2V cell, the initiator SHOULD
+  NOT attempt to extend the circuit through the responder by sending fragmented
+  EXTEND2 cells, since the responder's lack of support for CREATE2V cells is
+  assumed to imply the responder also lacks support for fragmented EXTEND2
+  cells.  Alternatively, for initiators with a sufficiently late consensus
+  method, the initiator MUST check that "proto" line in the responder's
+  descriptor (cf. Tor proposal #264) advertises support for the "Relay"
+  subprotocol version 3 (see §5).
+
+
+§3.2.1.3. Responder
+
+  The responder generates a keypair of y, Y = X25519_KEYGEN(), and does
+  NTOR_SHAREDB() as follows:
+
+  (NTOR_KEY, AUTH) ← NTOR_SHAREDB(X, y, Y, z, Z, ID, B):
+    secret_input := EXP(X, y) || EXP(X, z) || ID || B || Z || Y || PROTOID
+    NTOR_KEY     := H(secret_input, T_KEY)
+    verify       := H(secret_input, T_VERIFY)
+    auth_input   := verify || ID || Z || Y || X || PROTOID || "Server"
+    AUTH         := H(auth_input, T_MAC)
+
+  The responder sends a CREATED2V cell containing:
+
+    SERVER_NTOR    := Y || AUTH                      [64 bytes]
+    SERVER_NEWHOPE                                   [2048 bytes]  (see §3.2.2)
+    SERVER_HDATA   := SERVER_NTOR || SERVER_NEWHOPE  [2112 bytes]
+
+  and sends this to the initiator.
+
+
+§3.2.1.4. Finalisation
+
+  The initiator then checks Y is in G^* [see NOTE below], and does
+  NTOR_SHAREDA() as follows:
+
+  (NTOR_KEY) ← NTOR_SHAREDA(x, X, Y, Z, ID, AUTH)
+    secret_input := EXP(Y, x) || EXP(Z, x) || ID || Z || X || Y || PROTOID
+    NTOR_KEY     := H(secret_input, T_KEY)
+    verify       := H(secret_input, T_VERIFY)
+    auth_input   := verify || ID || Z || Y || X || PROTOID || "Server"
+    if AUTH == H(auth_input, T_MAC)
+       return NTOR_KEY
+
+  Both parties now have a shared value for NTOR_KEY.  They expand this into
+  the keys needed for the Tor relay protocol.
+
+  [XXX We think we want to omit the final hashing in the production of NTOR_KEY
+  here, and instead put all the inputs through SHAKE-256. --isis, peter]
+
+  [XXX We probably want to remove ID and B from the input to the shared key
+  material, since they serve for authentication but, as pre-established
+  "prologue" material to the handshake, they should not be used in attempts to
+  strengthen the cryptographic suitability of the shared key.  Also, their
+  inclusion is implicit in the DH exponentiations.  I should probably ask Ian
+  about the reasoning for the original design choice.  --isis]
+
+
+§3.2.2. The NewHope Handshake
+
+§3.2.2.1. Parameters & Mathematical Structures
+
+  Let ℤ be the ring of rational integers. Let ℤq, for q ≥ 1, denote the quotient
+  ring ℤ/qℤ.  We define R = ℤ[X]/((X^n)+1) as the ring of integer polynomials
+  modulo ((X^n)+1), and Rq = ℤq[X]/((X^n)+1) as the ring of integer polynomials
+  modulo ((X^n)+1) where each coefficient is reduced modulo q. When we refer to
+  a polynomial, we mean an element of Rq.
+
+    n := 1024
+    q := 12289
+
+    SEED         [32 Bytes]
+    NEWHOPE_POLY [1792 Bytes]
+    NEWHOPE_REC  [256 Bytes]
+    NEWHOPE_KEY  [32 Bytes]
+
+    NEWHOPE_MSGA := (NEWHOPE_POLY || SEED)
+    NEWHOPE_MSGB := (NEWHOPE_POLY || NEWHOPE_REC)
+
+
+§3.2.2.2. High-level Description of Newhope API Functions
+
+  For a description of internal functions, see §B.
+
+    (NEWHOPE_POLY, NEWHOPE_MSGA) ← NEWHOPE_KEYGEN(SEED):
+        â    := gen_a(seed)
+        s    := poly_getnoise()
+        e    := poly_getnoise()
+        ŝ    := poly_ntt(s)
+        ê    := poly_ntt(e)
+        b̂    := pointwise(â, ŝ) + ê
+        sp   := poly_tobytes(ŝ)
+        bp   := poly_tobytes(b̂)
+        return (sp, (bp || seed))
+
+    (NEWHOPE_MSGB, NEWHOPE_KEY) ← NEWHOPE_SHAREDB(NEWHOPE_MSGA):
+        s'   := poly_getnoise()
+        e'   := poly_getnoise()
+        e"   := poly_getnoise()
+        b̂    := poly_frombytes(bp)
+        â    := gen_a(seed)
+        ŝ'   := poly_ntt(s')
+        ê'   := poly_ntt(e')
+        û    := poly_pointwise(â, ŝ') + ê'
+        v    := poly_invntt(poly_pointwise(b̂,ŝ')) + e"
+        r    := helprec(v)
+        up   := poly_tobytes(û)
+        k    := rec(v, r)
+        return ((up || r), k)
+
+    NEWHOPE_KEY ← NEWHOPE_SHAREDA(NEWHOPE_MSGB, NEWHOPE_POLY):
+        û    := poly_frombytes(up)
+        ŝ    := poly_frombytes(sp)
+        v'   := poly_invntt(poly_pointwise(û, ŝ))
+        k    := rec(v', r)
+        return k
+
+  When a client uses a SEED within a CREATE2V cell, the client SHOULD NOT use
+  that SEED in any other CREATE2V or EXTEND2 cells.  See §4 for further
+  discussion.
+
+
+§3.3. Key Expansion
+
+  The client and server derive a shared key, SHARED, by:
+
+    HKDFID := "THESE ARENT THE DROIDS YOURE LOOKING FOR"
+    SHARED := SHAKE_256(HKDFID || NTorKey || NewHopeKey)
+
+
+§3.3.1. Note on the Design Choice
+
+  The reader may wonder why one would use SHAKE-256 to produce a 256-bit
+  output, since the security strength in bits for SHAKE-256 is min(d/2,256)
+  for collision resistance and min(d,256) for first- and second-order
+  preimages, where d is the output length.
+
+  The reasoning is that we should be aiming for 256-bit security for all of
+  our symmetric cryptography.  One could then argue that we should just use
+  SHA3-256 for the KDF.  We choose SHAKE-256 instead in order to provide an
+  easy way to derive longer shared secrets in the future without requiring a
+  new handshake.  The construction is odd, but the future is bright.
+  As we are already using SHAKE-256 for the 32-byte output hash, we are also
+  using it for all other 32-byte hashes involved in the protocol. Note that
+  the only difference between SHA3-256 and SHAKE-256 with 32-byte output is
+  one domain-separation byte.
+
+  [XXX why would you want 256-bit security for the symmetric side? Are you
+  talking pre- or post-quantum security? --peter]
+
+
+§4. Security & Anonymity Implications
+
+  This handshake protocol is one-way authenticated.  That is, the server is
+  authenticated, while the client remains anonymous.
+
+  The client MUST NOT cache and reuse SEED.  Doing so gives non-trivial
+  adversarial advantages w.r.t. all-for-the-price-of-one attacks during the
+  caching period.  More importantly, if the SEED used to generate NEWHOPE_MSGA
+  is reused for handshakes along the same circuit or multiple different
+  circuits, an adversary conducting a sybil attack somewhere along the path(s)
+  will be able to correlate the identity of the client across circuits or
+  hops.
+
+
+§5. Compatibility
+
+  Because our proposal requires both the client and server to send more than
+  the 505 bytes possible within a CREATE2 cell's HDATA section, it depends
+  upon the implementation of a mechanism for allowing larger CREATE cells
+  (cf. Tor proposal #249).
+
+  We reserve the following handshake type for use in CREATE2V/CREATED2V and
+  EXTEND2V/EXTENDED2V cells:
+
+    0x0003            [NEWHOPE + X25519 HYBRID HANDSHAKE]
+
+  We introduce a new sub-protocol number, "Relay=3", (cf. Tor proposal #264
+  §5.3) to signify support this handshake, and hence for the CREATE2V and
+  fragmented EXTEND2 cells which it requires.
+
+  There are no additional entries or changes required within either router
+  descriptors or microdescriptors to support this handshake method, due to the
+  NewHope keys being ephemeral and derived on-the-fly, and due to the NTor X25519
+  public keys already being included within the "ntor-onion-key" entry.
+
+  Add a "UseNewHopeKEX" configuration option and a corresponding consensus
+  parameter to control whether clients prefer using this NewHope hybrid
+  handshake or some previous handshake protocol.  If the configuration option
+  is "auto", clients SHOULD obey the consensus parameter.  The default
+  configuration SHOULD be "auto" and the consensus value SHOULD initially be "0".
+
+
+§6. Implementation
+
+  The paper by Alkim, Ducas, Pöppelmann and Schwabe describes two software
+  implementations of NewHope, one C reference implementation and an optimized
+  implementation using AVX2 vector instructions. Those implementations are
+  available at [1].
+
+  Additionally, there are implementations in Go by Yawning Angel, available
+  from [4] and in Rust by Isis Lovecruft, available from [5].
+
+  The software used to generate the test vectors in §C is based on the C
+  reference implementation and available from:
+
+  https://code.ciph.re/isis/newhope-tor-testvectors
+  https://github.com/isislovecruft/newhope-tor-testvectors
+
+
+§7. Performance & Scalability
+
+  The computationally expensive part in the current NTor handshake is the
+  X25519 key-pair generation and the X25519 shared-key computation. The
+  current implementation in Tor is a wrapper to support various highly optimized
+  implementations on different architectures. On Intel Haswell processors, the
+  fastest implementation of X25519, as reported by the eBACS benchmarking
+  project [6], takes 169920 cycles for key-pair generation and 161648 cycles
+  for shared-key computation; these add up to a total of 331568 cycles on each
+  side (initiator and responder).
+
+  The C reference implementation of NewHope, also benchmarked on Intel
+  Haswell, takes 358234 cycles for the initiator and 402058 cycles for the
+  Responder. The core computation of the proposed combination of NewHope and
+  X25519 will thus mean a slowdown of about a factor of 2.1 for the Initiator
+  and a slowdown by a factor of 2.2 for the Responder compared to the current
+  NTor handshake. These numbers assume a fully optimized implementation of the
+  NTor handshake and a C reference implementation of NewHope. With optimized
+  implementations of NewHope, such as the one for Intel Haswell described in
+  [0], the computational slowdown will be considerably smaller than a factor
+  of 2.
+
+
+§8. References
+
+[0]: https://cryptojedi.org/papers/newhope-20160328.pdf
+[1]: https://cryptojedi.org/crypto/#newhope
+[2]: http://www.nist.gov/customcf/get_pdf.cfm?pub_id=919061
+[3]: https://tools.ietf.org/html/rfc7748#section-6.1
+[4]: https://github.com/Yawning/newhope
+[5]: https://code.ciph.re/isis/newhopers
+[6]: http://bench.cr.yp.to
+
+
+§A. Cell Formats
+
+§A.1. CREATE2V Cells
+
+  The client portion of the handshake should send CLIENT_HDATA, formatted
+  into a CREATE2V cell as follows:
+
+    CREATE2V {                                              [2114 bytes]
+      HTYPE   := 0x0003                                     [2 bytes]
+      HLEN    := 0x0780                                     [2 bytes]
+      HDATA   := CLIENT_HDATA                               [1920 bytes]
+      IGNORED := 0x00                                       [194 bytes]
+    }
+
+  [XXX do we really want to pad with IGNORED to make CLIENT_HDATA the
+  same number of bytes as SERVER_HDATA? --isis]
+
+§A.2. CREATED2V Cells
+
+  The server responds to the client's CREATE2V cell with SERVER_HDATA,
+  formatted into a CREATED2V cell as follows:
+
+    CREATED2V {                                             [2114 bytes]
+      HLEN    := 0x0800                                     [2 bytes]
+      HDATA   := SERVER_HDATA                               [2112 bytes]
+      IGNORED := 0x00                                       [0 bytes]
+    }
+
+§A.3. Fragmented EXTEND2 Cells
+
+  When the client wishes to extend a circuit, the client should fragment
+  CLIENT_HDATA into four EXTEND2 cells:
+
+    EXTEND2 {
+      NSPEC := 0x02 {                                     [1 byte]
+        LINK_ID_SERVER                                    [22 bytes] XXX
+        LINK_ADDRESS_SERVER                               [8 bytes]  XXX
+      }
+      HTYPE := 0x0003                                     [2 bytes]
+      HLEN  := 0x0780                                     [2 bytes]
+      HDATA := CLIENT_HDATA[0,461]                        [462 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := CLIENT_HDATA[462,954]                      [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := CLIENT_HDATA[955,1447]                     [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := CLIENT_HDATA[1448,1919] || 0x00[20]        [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := 0x00[172]                                  [172 bytes]
+    }
+
+  The client sends this to the server to extend the circuit from, and that
+  server should format the fragmented EXTEND2 cells into a CREATE2V cell, as
+  described in §A.1.
+
+§A.4. Fragmented EXTENDED2 Cells
+
+    EXTENDED2 {
+      NSPEC := 0x02 {                                     [1 byte]
+        LINK_ID_SERVER                                    [22 bytes] XXX
+        LINK_ADDRESS_SERVER                               [8 bytes]  XXX
+      }
+      HTYPE := 0x0003                                     [2 bytes]
+      HLEN  := 0x0800                                     [2 bytes]
+      HDATA := SERVER_HDATA[0,461]                        [462 bytes]
+    }
+    EXTENDED2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := SERVER_HDATA[462,954]                      [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := SERVER_HDATA[955,1447]                     [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := SERVER_HDATA[1448,1939]                    [492 bytes]
+    }
+    EXTEND2 {
+      NSPEC := 0x00                                       [1 byte]
+      HTYPE := 0xFFFF                                     [2 bytes]
+      HLEN  := 0x0000                                     [2 bytes]
+      HDATA := SERVER_HDATA[1940,2112]                    [172 bytes]
+    }
+
+
+§B. NewHope Internal Functions
+
+  gen_a(SEED):                  returns a uniformly random poly
+  poly_getnoise():              returns a poly sampled from a centered binomial
+  poly_ntt(poly):               number-theoretic transform; returns a poly
+  poly_invntt(poly):            inverse number-theoretic transform; returns a poly
+  poly_pointwise(poly, poly):   pointwise multiplication; returns a poly
+  poly_tobytes(poly):           packs a poly to a NEWHOPE_POLY byte array
+  poly_frombytes(NEWHOPE_POLY): unpacks a NEWHOPE_POLY byte array to a poly
+
+  helprec(poly):                returns a NEWHOPE_REC byte array
+  rec(poly, NEWHOPE_REC):       returns a NEWHOPE_KEY
+
+
+  --- Description of the Newhope internal functions ---
+
+  gen_a(SEED seed) receives as input a 32-byte (public) seed.  It expands
+  this seed through SHAKE-128 from the FIPS202 standard. The output of SHAKE-128
+  is considered a sequence of 16-bit little-endian integers. This sequence is
+  used to initialize the coefficients of the returned polynomial from the least
+  significant (coefficient of X^0) to the most significant (coefficient of
+  X^1023) coefficient. For each of the 16-bit integers first eliminate the
+  highest two bits (to make it a 14-bit integer) and then use it as the next
+  coefficient if it is smaller than q=12289.
+  Note that the amount of output required from SHAKE to initialize all 1024
+  coefficients of the polynomial varies depending on the input seed.
+  Note further that this function does not process any secret data and thus does
+  not need any timing-attack protection.
+
+
+  poly_getnoise() first generates 4096 bytes of uniformly random data. This can
+  be done by reading these bytes from the system's RNG; efficient
+  implementations will typically only read a 32-byte seed from the system's RNG
+  and expand it through some fast PRG (for example, ChaCha20 or AES-256 in CTR
+  mode). The output of the PRG is considered an array of 2048 16-bit integers
+  r[0],...,r[2047]. The coefficients of the output polynomial are computed as
+  HW(r[0])-HW(r[1]), HW(r[2])-HW(r[3]),...,HW(r[2046])-HW(r[2047]), where HW
+  stands for Hamming weight.
+  Note that the choice of RNG is a local decision; different implementations are
+  free to use different RNGs.
+  Note further that the output of this function is secret; the PRG (and the
+  computation of HW) need to be protected against timing attacks.
+
+
+  poly_ntt(poly f): For a mathematical description of poly_ntt see the [0]; a
+  pseudocode description of a very naive in-place transformation of an input
+  polynomial f = f[0] + f[1]*X + f[2]*X^2 + ... + f[1023]*X^1023 is the
+  following code (all arithmetic on coefficients performed modulo q):
+
+    psi   = 7
+    omega = 49
+
+    for i in range(0,n):
+      t[i] = f[i] * psi^i
+
+    for i in range(0,n):
+      f[i] = 0
+      for j in range(0,n):
+        f[i] += t[j] * omega^((i*j)%n)
+
+  Note that this is not how poly_ntt should be implemented if performance is
+  an issue; in particular, efficient algorithms for the number-theoretic
+  transform take time O(n*log(n)) and not O(n^2)
+  Note further that all arithmetic in poly_ntt has to be protected against
+  timing attacks.
+
+
+  poly_invntt(poly f): For a mathematical description of poly_invntt see the
+  [0]; a pseudocode description of a very naive in-place transformation of an
+  input polynomial f = f[0] + f[1]*X + f[2]*X^2 + ... + f[1023]*X^1023 is the
+  following code (all arithmetic on coefficients performed modulo q):
+
+    invpsi = 8778;
+    invomega = 1254;
+    invn = 12277;
+
+    for i in range(0,n):
+      t[i] = f[i];
+
+    for i in range(0,n):
+      f[i]=0;
+      for j in range(0,n):
+        f[i] += t[j] * invomega^((i*j)%n)
+      f[i] *= invpsi^i
+      f[i] *= invn
+
+  Note that this is not how poly_invntt should be implemented if performance
+  is an issue; in particular, efficient algorithms for the inverse
+  number-theoretic transform take time O(n*log(n)) and not O(n^2)
+  Note further that all arithmetic in poly_invntt has to be protected against
+  timing attacks.
+
+
+  poly_pointwise(poly f, poly g) performs pointwise multiplication of the two
+  polynomials.  This means that for f = (f0 + f1*X + f2*X^2 + ... +
+  f1023*X^1023) and g = (g0 + g1*X + g2*X^2 + ... + g1023*X^1023) it computes
+  and returns h = (h0 + h1*X + h2*X^2 + ... + h1023*X^1023) with h0 = f0*g0,
+  h1 = f1*g1,..., h1023 = f1023*g1023.
+
+
+  poly_tobytes(poly f) first reduces all coefficents of f modulo q, i.e.,
+  brings them to the interval [0,q-1]. Denote these reduced coefficients as
+  f0,..., f1023; note that they all fit into 14 bits. The function then packs
+  those coefficients into an array of 1792 bytes r[0],..., r[1792] in "packed
+  little-endian representation", i.e.,
+  r[0]     = f[0] & 0xff;
+  r[1]     = (f[0] >>  8) & ((f[1] & 0x03) << 6)
+  r[2]     = (f[1] >>  2) & 0xff;
+  r[3]     = (f[1] >> 10) & ((f[2] & 0x0f) << 4)
+  .
+  .
+  .
+  r[1790]  = (f[1022]) >> 12) & ((f[1023] & 0x3f) << 2)
+  r[1791]  = f[1023] >> 6
+  Note that this function needs to be protected against timing attacks. In
+  particular, avoid non-constant-time conditional subtractions (or other
+  non-constant-time expressions) in the reduction modulo q of the coefficients.
+
+
+  poly_frombytes(NEWHOPE_POLY b) is the inverse of poly_tobytes; it receives
+  as input an array of 1792 bytes and coverts it into the internal
+  representation of a poly. Note that poly_frombytes does not need to check
+  whether the coefficients are reduced modulo q or reduce coefficients modulo
+  q. Note further that the function must not leak any information about its
+  inputs through timing information, as it is also applied to the secret key
+  of the initiator.
+
+
+  helprec(poly f) computes 256 bytes of reconciliation information from the
+  input poly f. Internally, one byte of reconciliation information is computed
+  from four coefficients of f by a function helprec4. Let the input polynomial f
+  = (f0 + f1*X + f2*X^2 + ... + f1023*X^1023); let the output byte array be
+  r[0],...r[256]. This output byte array is computed as
+  r[0]   = helprec4(f0,f256,f512,f768)
+  r[1]   = helprec4(f1,f257,f513,f769)
+  r[2]   = helprec4(f2,f258,f514,f770)
+  .
+  .
+  .
+  r[255] = helprec4(f255,f511,f767,f1023), where helprec4 does the following:
+
+    helprec4(x0,x1,x2,x3):
+      b = randombit()
+      r0,r1,r2,r3 = CVPD4(8*x0+4*b,8*x1+4*b,8*x2+4*b,8*x3+4*b)
+      r = (r0 & 0x03) | ((r1 & 0x03) << 2) | ((r2 & 0x03) << 4) | ((r3 & 0x03) << 6)
+      return r
+
+  The function CVPD4 does the following:
+
+    CVPD4(y0,y1,y2,y3):
+      v00 = round(y0/2q)
+      v01 = round(y1/2q)
+      v02 = round(y2/2q)
+      v03 = round(y3/2q)
+      v10 = round((y0-1)/2q)
+      v11 = round((y1-1)/2q)
+      v12 = round((y2-1)/2q)
+      v13 = round((y3-1)/2q)
+      t   = abs(y0 - 2q*v00)
+      t  += abs(y1 - 2q*v01)
+      t  += abs(y2 - 2q*v02)
+      t  += abs(y3 - 2q*v03)
+      if(t < 2q):
+        v0 = v00
+        v1 = v01
+        v2 = v02
+        v3 = v03
+        k  = 0
+      else
+        v0 = v10
+        v1 = v11
+        v2 = v12
+        v3 = v13
+        r  = 1
+      return (v0-v3,v1-v3,v2-v3,k+2*v3)
+
+  In this description, round(x) is defined as ⌊x + 0.5⌋, where ⌊x⌋ rounds to
+  the largest integer that does not exceed x; abs() returns the absolute
+  value.
+  Note that all computations involved in helprec operate on secret data and must
+  be protected against timing attacks.
+
+
+  rec(poly f, NEWHOPE_REC r) computes the pre-hash (see paper) Newhope key from
+  f and r. Specifically, it computes one bit of key from 4 coefficients of f and
+  one byte of r. Let f = f0 + f1*X + f2*X^2 + ... + f1023*X^1023 and let r =
+  r[0],r[1],...,r[255]. Let the bytes of the output by k[0],...,k[31] and let
+  the bits of the output by k0,...,k255, where
+  k0   = k[0] & 0x01
+  k1   = (k[0] >> 1) & 0x01
+  k2   = (k[0] >> 2) & 0x01
+  .
+  .
+  .
+  k8   = k[1] & 0x01
+  k9   = (k[1] >> 1) & 0x01
+  .
+  .
+  .
+  k255 = (k[32] >> 7)
+  The function rec computes k0,...,k255 as
+  k0   = rec4(f0,f256,f512,f768,r[0])
+  k1   = rec4(f1,f257,f513,f769,r[1])
+  .
+  .
+  .
+  k255 = rec4(f255,f511,f767,f1023,r[255])
+
+  The function rec4 does the following:
+
+    rec4(y0,y1,y2,y3,r):
+      r0 = r & 0x03
+      r1 = (r >> 2) & 0x03
+      r2 = (r >> 4) & 0x03
+      r3 = (r >> 6) & 0x03
+      Decode(8*y0-2q*r0, 8*y1-2q*r1, 8*y2-2q*r2, 8*y3-q*r3)
+
+  The function Decode does the following:
+
+    Decode(v0,v1,v2,v3):
+      t0 = round(v0/8q)
+      t1 = round(v1/8q)
+      t2 = round(v2/8q)
+      t3 = round(v3/8q)
+      t  = abs(v0 - 8q*t0)
+      t += abs(v0 - 8q*t0)
+      t += abs(v0 - 8q*t0)
+      t += abs(v0 - 8q*t0)
+      if(t > 1) return 1
+      else return 0
+
+
+§C. Test Vectors