From e3c47c352852395f42109b5f158fa73ef38e527a Mon Sep 17 00:00:00 2001
From: "Jason A. Donenfeld" <Jason@zx2c4.com>
Date: Thu, 26 Jul 2018 20:05:47 +0200
Subject: keygen-html: bring back pure javascript implementation
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This reverts commit 9d5baf7d1d14ca7eb0852b41566330259229d489.

Benoît Viguier has proofs that values will stay well within 2^53. We
also have an improved carry function that's much simpler.
---
 contrib/examples/keygen-html/Makefile              |   6 -
 contrib/examples/keygen-html/README                |   8 -
 contrib/examples/keygen-html/keygen.html           |   4 +-
 .../examples/keygen-html/src/curve25519_generate.c |  98 -----------
 contrib/examples/keygen-html/src/glue.js           |  25 ---
 contrib/examples/keygen-html/wireguard.js          | 184 +++++++++++++++++++++
 6 files changed, 186 insertions(+), 139 deletions(-)
 delete mode 100644 contrib/examples/keygen-html/Makefile
 delete mode 100644 contrib/examples/keygen-html/src/curve25519_generate.c
 delete mode 100644 contrib/examples/keygen-html/src/glue.js
 create mode 100644 contrib/examples/keygen-html/wireguard.js

diff --git a/contrib/examples/keygen-html/Makefile b/contrib/examples/keygen-html/Makefile
deleted file mode 100644
index a3acec0..0000000
--- a/contrib/examples/keygen-html/Makefile
+++ /dev/null
@@ -1,6 +0,0 @@
-curve25519_generate.js: src/curve25519_generate.c src/glue.js
-	emcc -O2 --memory-init-file 0 --closure 1 --post-js src/glue.js -s 'EXTRA_EXPORTED_RUNTIME_METHODS=["Pointer_stringify"]' -o $@ src/curve25519_generate.c
-clean:
-	rm -f curve25519_generate.js
-all: curve25519_generate.js
-.PHONY: clean all
diff --git a/contrib/examples/keygen-html/README b/contrib/examples/keygen-html/README
index eaa4244..f1c3412 100644
--- a/contrib/examples/keygen-html/README
+++ b/contrib/examples/keygen-html/README
@@ -17,11 +17,3 @@ introduces interesting side-channel attacks.
 Secrets aren't zerored after use. Maybe you can get around this with
 some tricks taking advantage of browser allocator behavior and different
 processes, but it seems pretty hard.
-
-Building
---------
-
-In order to use the example `keygen.html` file, you must first build
-the C sources using emscripten. Simply run:
-
-    $ make
diff --git a/contrib/examples/keygen-html/keygen.html b/contrib/examples/keygen-html/keygen.html
index af2a545..939e637 100644
--- a/contrib/examples/keygen-html/keygen.html
+++ b/contrib/examples/keygen-html/keygen.html
@@ -1,4 +1,4 @@
-<script src="curve25519_generate.js" onError='document.write("<h3>Did you forget to run \"make\" to compile curve25519_generate.js?</h3><!--");'></script>
+<script src="wireguard.js"></script>
 <script>
 /* SPDX-License-Identifier: GPL-2.0
  *
@@ -26,7 +26,7 @@ function sendPubkeyToServer(pubkey, username, password)
 
 function downloadNewConfiguration()
 {
-	var keypair = WireGuard.generateKeypair();
+	var keypair = wireguard.generateKeypair();
 	var serverResponse = sendPubkeyToServer(keypair.publicKey, "zx2c4", "supersecretpassword");
 
 	var config = [];
diff --git a/contrib/examples/keygen-html/src/curve25519_generate.c b/contrib/examples/keygen-html/src/curve25519_generate.c
deleted file mode 100644
index 6329c57..0000000
--- a/contrib/examples/keygen-html/src/curve25519_generate.c
+++ /dev/null
@@ -1,98 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0
-/*
- * Copyright (C) 2018-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
- */
-
-#include <emscripten.h>
-
-typedef unsigned long long  u64;
-typedef unsigned int u32;
-typedef unsigned char u8;
-typedef u32 __le32;
-
-enum { CURVE25519_KEY_SIZE = 32 };
-
-#ifndef __always_inline
-#define __always_inline __inline __attribute__((__always_inline__))
-#endif
-#ifndef noinline
-#define noinline __attribute__((noinline))
-#endif
-#ifndef __aligned
-#define __aligned(x) __attribute__((aligned(x)))
-#endif
-#ifndef __force
-#define __force
-#endif
-
-#if __BYTE_ORDER == __LITTLE_ENDIAN
-#define le32_to_cpup(a) (*(a))
-#else
-#define le32_to_cpup(a) __builtin_bswap32(*(a))
-#endif
-#define get_unaligned_le32(a) le32_to_cpup((u32 *)(a))
-
-#define memset(a, b, c) __builtin_memset(a, b, c)
-#define memcpy(a, b, c) __builtin_memcpy(a, b, c)
-#define memmove(a, b, c) __builtin_memmove(a, b, c)
-/* We don't even attempt to deal with this in javascript. */
-#define memzero_explicit(a, b)
-
-static __always_inline void normalize_secret(u8 secret[CURVE25519_KEY_SIZE])
-{
-	secret[0] &= 248;
-	secret[31] &= 127;
-	secret[31] |= 64;
-}
-
-#include "../../../../src/crypto/zinc/curve25519/curve25519-fiat32.c"
-
-EMSCRIPTEN_KEEPALIVE void curve25519_generate_public(u8 public[static 32], const u8 private[static 32])
-{
-	static const u8 basepoint[32] = { 9 };
-
-	curve25519_generic(public, private, basepoint);
-}
-
-EMSCRIPTEN_KEEPALIVE void curve25519_generate_private(u8 private[static 32])
-{
-	int i;
-
-	EM_ASM({
-		/* Same trick as libsodium */
-		var getRandomValue = function() {
-			var buf = new Uint32Array(1);
-			window.crypto.getRandomValues(buf);
-			return buf[0] >>> 0;
-		};
-		Module.getRandomValue = getRandomValue;
-	});
-	
-	for (i = 0; i < 32; ++i)
-		private[i] = EM_ASM_INT_V({ return Module.getRandomValue(); });
-	normalize_secret(private);
-}
-
-static inline void encode_base64(char dest[static 4], const u8 src[static 3])
-{
-	const u8 input[] = { (src[0] >> 2) & 63, ((src[0] << 4) | (src[1] >> 4)) & 63, ((src[1] << 2) | (src[2] >> 6)) & 63, src[2] & 63 };
-
-	for (unsigned int i = 0; i < 4; ++i)
-		dest[i] = input[i] + 'A'
-			  + (((25 - input[i]) >> 8) & 6)
-			  - (((51 - input[i]) >> 8) & 75)
-			  - (((61 - input[i]) >> 8) & 15)
-			  + (((62 - input[i]) >> 8) & 3);
-
-}
-
-EMSCRIPTEN_KEEPALIVE void key_to_base64(char base64[static 45], const u8 key[static 32])
-{
-	unsigned int i;
-
-	for (i = 0; i < 32 / 3; ++i)
-		encode_base64(&base64[i * 4], &key[i * 3]);
-	encode_base64(&base64[i * 4], (const u8[]){ key[i * 3 + 0], key[i * 3 + 1], 0 });
-	base64[45 - 2] = '=';
-	base64[45 - 1] = '\0';
-}
diff --git a/contrib/examples/keygen-html/src/glue.js b/contrib/examples/keygen-html/src/glue.js
deleted file mode 100644
index 5bd2511..0000000
--- a/contrib/examples/keygen-html/src/glue.js
+++ /dev/null
@@ -1,25 +0,0 @@
-/*! SPDX-License-Identifier: GPL-2.0
- *
- * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
- */
-window["WireGuard"] = {
-	"generateKeypair": function() {
-		var privateKey = Module["_malloc"](32);
-		var publicKey = Module["_malloc"](32);
-		Module["_curve25519_generate_private"](privateKey);
-		Module["_curve25519_generate_public"](publicKey, privateKey);
-		var privateBase64 = Module["_malloc"](45);
-		var publicBase64 = Module["_malloc"](45);
-		Module["_key_to_base64"](privateBase64, privateKey);
-		Module["_key_to_base64"](publicBase64, publicKey);
-		Module["_free"](privateKey);
-		Module["_free"](publicKey);
-		var keypair = {
-			publicKey: Module["Pointer_stringify"](publicBase64),
-			privateKey: Module["Pointer_stringify"](privateBase64)
-		};
-		Module["_free"](privateBase64);
-		Module["_free"](publicBase64);
-		return keypair;
-	}
-};
diff --git a/contrib/examples/keygen-html/wireguard.js b/contrib/examples/keygen-html/wireguard.js
new file mode 100644
index 0000000..e96da3e
--- /dev/null
+++ b/contrib/examples/keygen-html/wireguard.js
@@ -0,0 +1,184 @@
+/*! SPDX-License-Identifier: GPL-2.0
+ *
+ * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
+ */
+
+(function() {
+	function gf(init) {
+		var r = new Float64Array(16);
+		if (init) {
+			for (var i = 0; i < init.length; ++i)
+				r[i] = init[i];
+		}
+		return r;
+	}
+
+	function pack(o, n) {
+		var b, m = gf(), t = gf();
+		for (var i = 0; i < 16; ++i)
+			t[i] = n[i];
+		carry(t);
+		carry(t);
+		carry(t);
+		for (var j = 0; j < 2; ++j) {
+			m[0] = t[0] - 0xffed;
+			for (var i = 1; i < 15; ++i) {
+				m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
+				m[i - 1] &= 0xffff;
+			}
+			m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
+			b = (m[15] >> 16) & 1;
+			m[14] &= 0xffff;
+			cswap(t, m, 1 - b);
+		}
+		for (var i = 0; i < 16; ++i) {
+			o[2 * i] = t[i] & 0xff;
+			o[2 * i + 1] = t[i] >> 8;
+		}
+	}
+
+	function carry(o) {
+		var c;
+		for (var i = 0; i < 16; ++i) {
+			o[(i + 1) % 16] += (i < 15 ? 1 : 38) * Math.floor(o[i] / 65536);
+			o[i] &= 0xffff;
+		}
+	}
+
+	function cswap(p, q, b) {
+		var t, c = ~(b - 1);
+		for (var i = 0; i < 16; ++i) {
+			t = c & (p[i] ^ q[i]);
+			p[i] ^= t;
+			q[i] ^= t;
+		}
+	}
+
+	function add(o, a, b) {
+		for (var i = 0; i < 16; ++i)
+			o[i] = (a[i] + b[i]) | 0;
+	}
+
+	function subtract(o, a, b) {
+		for (var i = 0; i < 16; ++i)
+			o[i] = (a[i] - b[i]) | 0;
+	}
+
+	function multmod(o, a, b) {
+		var t = new Float64Array(31);
+		for (var i = 0; i < 16; ++i) {
+			for (var j = 0; j < 16; ++j)
+				t[i + j] += a[i] * b[j];
+		}
+		for (var i = 0; i < 15; ++i)
+			t[i] += 38 * t[i + 16];
+		for (var i = 0; i < 16; ++i)
+			o[i] = t[i];
+		carry(o);
+		carry(o);
+	}
+
+	function invert(o, i) {
+		var c = gf();
+		for (var a = 0; a < 16; ++a)
+			c[a] = i[a];
+		for (var a = 253; a >= 0; --a) {
+			multmod(c, c, c);
+			if (a !== 2 && a !== 4)
+				multmod(c, c, i);
+		}
+		for (var a = 0; a < 16; ++a)
+			o[a] = c[a];
+	}
+
+	function normalizeKey(z) {
+		z[31] = (z[31] & 127) | 64;
+		z[0] &= 248;
+	}
+
+	function generatePublicKey(privateKey) {
+		var r, z = new Uint8Array(32);
+		var a = gf([1]),
+			b = gf([9]),
+			c = gf(),
+			d = gf([1]),
+			e = gf(),
+			f = gf(),
+			_121665 = gf([0xdb41, 1]),
+			_9 = gf([9]);
+		for (var i = 0; i < 32; ++i)
+			z[i] = privateKey[i];
+		normalizeKey(z);
+		for (var i = 254; i >= 0; --i) {
+			r = (z[i >>> 3] >>> (i & 7)) & 1;
+			cswap(a, b, r);
+			cswap(c, d, r);
+			add(e, a, c);
+			subtract(a, a, c);
+			add(c, b, d);
+			subtract(b, b, d);
+			multmod(d, e, e);
+			multmod(f, a, a);
+			multmod(a, c, a);
+			multmod(c, b, e);
+			add(e, a, c);
+			subtract(a, a, c);
+			multmod(b, a, a);
+			subtract(c, d, f);
+			multmod(a, c, _121665);
+			add(a, a, d);
+			multmod(c, c, a);
+			multmod(a, d, f);
+			multmod(d, b, _9);
+			multmod(b, e, e);
+			cswap(a, b, r);
+			cswap(c, d, r);
+		}
+		invert(c, c);
+		multmod(a, a, c);
+		pack(z, a);
+		return z;
+	}
+
+	function generatePresharedKey() {
+		var privateKey = new Uint8Array(32);
+		window.crypto.getRandomValues(privateKey);
+		return privateKey;
+	}
+
+	function generatePrivateKey() {
+		var privateKey = generatePresharedKey();
+		normalizeKey(privateKey);
+		return privateKey;
+	}
+
+	function encodeBase64(dest, src) {
+		var input = Uint8Array.from([(src[0] >> 2) & 63, ((src[0] << 4) | (src[1] >> 4)) & 63, ((src[1] << 2) | (src[2] >> 6)) & 63, src[2] & 63]);
+		for (var i = 0; i < 4; ++i)
+			dest[i] = input[i] + 65 +
+			(((25 - input[i]) >> 8) & 6) -
+			(((51 - input[i]) >> 8) & 75) -
+			(((61 - input[i]) >> 8) & 15) +
+			(((62 - input[i]) >> 8) & 3);
+	}
+
+	function keyToBase64(key) {
+		var i, base64 = new Uint8Array(44);
+		for (i = 0; i < 32 / 3; ++i)
+			encodeBase64(base64.subarray(i * 4), key.subarray(i * 3));
+		encodeBase64(base64.subarray(i * 4), Uint8Array.from([key[i * 3 + 0], key[i * 3 + 1], 0]));
+		base64[43] = 61;
+		return String.fromCharCode.apply(null, base64);
+	}
+
+	window.wireguard = {
+		generateKeypair: function() {
+			var privateKey = generatePrivateKey();
+			var publicKey = generatePublicKey(privateKey);
+			return {
+				publicKey: keyToBase64(publicKey),
+				privateKey: keyToBase64(privateKey)
+			};
+		}
+	};
+})();
-- 
cgit v1.2.3-59-g8ed1b