summaryrefslogtreecommitdiff
path: root/lib/crypto
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2018-02-19 14:34:36 -0800
committerOri Bernstein <ori@eigenstate.org>2018-02-19 14:34:36 -0800
commit39b688e8d0e8daee5eb55a207841001fae056287 (patch)
tree41f330d76ff6c4cdf2c12fe381177ac541707330 /lib/crypto
parent92747b6c52dda775dcc85002c06efab36d88cc4d (diff)
downloadmc-39b688e8d0e8daee5eb55a207841001fae056287.tar.gz
Add some constant time math helpers.
Diffstat (limited to 'lib/crypto')
-rw-r--r--lib/crypto/bld.sub3
-rw-r--r--lib/crypto/ct.myr59
-rw-r--r--lib/crypto/test/ct.myr34
3 files changed, 96 insertions, 0 deletions
diff --git a/lib/crypto/bld.sub b/lib/crypto/bld.sub
index f398c55..cf53bee 100644
--- a/lib/crypto/bld.sub
+++ b/lib/crypto/bld.sub
@@ -20,6 +20,9 @@ lib crypto =
entropy.myr # currently assumes a /dev/random
rand.myr
+ # constant time arithmetic
+ ct.myr
+
lib ../std:std
lib ../sys:sys
lib ../thread:thread
diff --git a/lib/crypto/ct.myr b/lib/crypto/ct.myr
new file mode 100644
index 0000000..2b976f4
--- /dev/null
+++ b/lib/crypto/ct.myr
@@ -0,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))
+}
diff --git a/lib/crypto/test/ct.myr b/lib/crypto/test/ct.myr
new file mode 100644
index 0000000..968da3b
--- /dev/null
+++ b/lib/crypto/test/ct.myr
@@ -0,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)}],
+ ][:])
+}