ref: 39b688e8d0e8daee5eb55a207841001fae056287
parent: 92747b6c52dda775dcc85002c06efab36d88cc4d
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Feb 19 09:34:36 EST 2018
Add some constant time math helpers.
--- a/lib/crypto/bld.sub
+++ b/lib/crypto/bld.sub
@@ -20,6 +20,9 @@
entropy.myr # currently assumes a /dev/random
rand.myr
+ # constant time arithmetic
+ ct.myr
+
lib ../std:std
lib ../sys:sys
lib ../thread:thread
--- /dev/null
+++ b/lib/crypto/ct.myr
@@ -1,0 +1,59 @@
+use std
+
+pkg crypto =
+ /* These functions require unsigned inputs in order to work correctly */
+ generic not : (a : @t -> @t) :: integral,numeric @t
+ generic eq : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic ne : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic gt : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic lt : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic ge : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic le : (a : @t, b : @t -> @t) :: integral,numeric @t
+ generic mux : (x : @t, a : @t, b : @t ->@t) :: integral,numeric @t
+;;
+
+generic not = {a : @t :: integral,numeric @t+ -> a ^ 1
+}
+
+generic eq = {a : @t, b : @t :: integral,numeric @t+ const nshift = 8*sizeof(@t) - 1
+ var q = a ^ b
+ -> ((q | -q) >> nshift)^1
+}
+
+generic gt = {a : @t, b : @t :: integral,numeric @t+ /*
+ 3 cases:
+ - both top bits unset => check if result is -ve (top bit set)
+ - one top bit set: => one with top bit set is >
+ - both top bits set: => subtract, check if result is -ve
+ */
+ const nshift = 8*sizeof(@t) - 1
+ var z = (b - a)
+ -> (z ^ ((a ^ b) & (a ^ z))) >> nshift;
+}
+
+generic ge = {a, b+ -> lt(a, b) ^ 1
+}
+
+generic lt = {a, b+ const nshift = 8*sizeof(@t) - 1
+ var z = (a - b)
+ -> (z ^ ((b ^ a) & (b ^ a))) >> nshift;
+}
+
+generic le = {a, b+ -> gt(a, b) ^ 1
+}
+
+generic ne = {a, b+ const nshift = 8*sizeof(@t) - 1
+ var q = a ^ b
+ -> ((q | -q) >> nshift)^1
+}
+
+generic mux = {c, a, b+ -> b ^ (-c & (a ^ b))
+}
--- /dev/null
+++ b/lib/crypto/test/ct.myr
@@ -1,0 +1,34 @@
+use std
+use testr
+use crypto
+
+const main = {+ testr.run([
+ [.name="not-0", .fn={ctx; testr.eq(ctx, crypto.not(0ui), 1ui)}],+ [.name="not-1", .fn={ctx; testr.eq(ctx, crypto.not(1ui), 0ui)}],+
+ [.name="eq-t", .fn={ctx; testr.eq(ctx, crypto.eq(123ui, 123ui), 1)}],+ [.name="eq-f", .fn={ctx; testr.eq(ctx, crypto.eq(124ui, 123ui), 0)}],+
+ [.name="eq-~0-t", .fn={ctx; testr.eq(ctx, crypto.eq(~0ui, ~0ui), 1)}],+ [.name="eq-~0-t", .fn={ctx; testr.eq(ctx, crypto.eq(~0ui, ~0ui - 1), 0)}],+
+ [.name="gt-ss-1", .fn={ctx; testr.eq(ctx, crypto.gt(123ui, 23ui), 1)}],+ [.name="gt-ss-0", .fn={ctx; testr.eq(ctx, crypto.gt(23ui, 123ui), 0)}],+ [.name="gt-bs-0", .fn={ctx; testr.eq(ctx, crypto.gt(~0ui - 1, ~0ui), 0)}],+ [.name="gt-bs-1", .fn={ctx; testr.eq(ctx, crypto.gt(~0ui, 23ui), 1)}],+
+ [.name="gt-ss-1", .fn={ctx; testr.eq(ctx, crypto.gt(123ui, 23ui), 1)}],+ [.name="gt-ss-0", .fn={ctx; testr.eq(ctx, crypto.gt(23ui, 123ui), 0)}],+ [.name="gt-bs-1", .fn={ctx; testr.eq(ctx, crypto.gt(~0ui, 23ui), 1)}],+ [.name="gt-sb-0", .fn={ctx; testr.eq(ctx, crypto.gt(23ui, ~0ui), 0)}],+ [.name="gt-bb-0", .fn={ctx; testr.eq(ctx, crypto.gt(~0ui - 1, ~0ui), 0)}],+ [.name="gt-bb-1", .fn={ctx; testr.eq(ctx, crypto.gt(~0ui, ~0ui - 1), 1)}],+
+ [.name="lt-ss-1", .fn={ctx; testr.eq(ctx, crypto.lt(23ui, 123ui), 1)}],+ [.name="lt-ss-0", .fn={ctx; testr.eq(ctx, crypto.lt(123ui, 23ui), 0)}],+ [.name="lt-bs-1", .fn={ctx; testr.eq(ctx, crypto.lt(23ui, ~0ui), 1)}],+ [.name="lt-bb-0", .fn={ctx; testr.eq(ctx, crypto.lt(~0ui, ~0ui - 1), 0)}],+ [.name="lt-bb-1", .fn={ctx; testr.eq(ctx, crypto.lt(~0ui - 1, ~0ui), 1)}],+ ][:])
+}