From f3667e8a8056765c460aa3da1fd3ea655b54bf25 Mon Sep 17 00:00:00 2001
From: Frank Denis <github@pureftpd.org>
Date: Thu, 15 Oct 2020 16:39:39 +0200
Subject: std/crypto/25519: do cofactored ed25519 verification

This is slightly slower but makes our verification function compatible
with batch signatures. Which, in turn, makes blockchain people happy.
And we want to make our users happy.

Add convenience functions to substract edwards25519 points and to
clear the cofactor.
---
 lib/std/crypto/25519/curve25519.zig   |  5 +++++
 lib/std/crypto/25519/ed25519.zig      |  9 +++++----
 lib/std/crypto/25519/edwards25519.zig | 24 ++++++++++++++++++++++++
 3 files changed, 34 insertions(+), 4 deletions(-)

(limited to 'lib')

diff --git a/lib/std/crypto/25519/curve25519.zig b/lib/std/crypto/25519/curve25519.zig
index 94490f674c..7f180eac2f 100644
--- a/lib/std/crypto/25519/curve25519.zig
+++ b/lib/std/crypto/25519/curve25519.zig
@@ -39,6 +39,11 @@ pub const Curve25519 = struct {
         }
     }
 
+    /// Multiply a point by the cofactor
+    pub fn clearCofactor(p: Edwards25519) Edwards25519 {
+        return p.dbl().dbl().dbl();
+    }
+
     fn ladder(p: Curve25519, s: [32]u8, comptime bits: usize) !Curve25519 {
         var x1 = p.x;
         var x2 = Fe.one;
diff --git a/lib/std/crypto/25519/ed25519.zig b/lib/std/crypto/25519/ed25519.zig
index 9993afb6d2..784ba62de0 100644
--- a/lib/std/crypto/25519/ed25519.zig
+++ b/lib/std/crypto/25519/ed25519.zig
@@ -97,6 +97,7 @@ pub const Ed25519 = struct {
         try Curve.rejectNonCanonical(public_key);
         const a = try Curve.fromBytes(public_key);
         try a.rejectIdentity();
+        const expected_r = try Curve.fromBytes(r.*);
 
         var h = Sha512.init(.{});
         h.update(r);
@@ -106,11 +107,11 @@ pub const Ed25519 = struct {
         h.final(&hram64);
         const hram = Curve.scalar.reduce64(hram64);
 
-        const p = try a.neg().mul(hram);
-        const check = (try Curve.basePoint.mul(s.*)).add(p).toBytes();
-        if (mem.eql(u8, &check, r) == false) {
+        const ah = try a.neg().mul(hram);
+        const sb_ah = (try Curve.basePoint.mul(s.*)).add(ah);
+        if (expected_r.sub(sb_ah).clearCofactor().rejectIdentity()) |_| {
             return error.InvalidSignature;
-        }
+        } else |_| {}
     }
 };
 
diff --git a/lib/std/crypto/25519/edwards25519.zig b/lib/std/crypto/25519/edwards25519.zig
index 176e5337da..f98774542f 100644
--- a/lib/std/crypto/25519/edwards25519.zig
+++ b/lib/std/crypto/25519/edwards25519.zig
@@ -73,6 +73,11 @@ pub const Edwards25519 = struct {
         }
     }
 
+    /// Multiply a point by the cofactor
+    pub fn clearCofactor(p: Edwards25519) Edwards25519 {
+        return p.dbl().dbl().dbl();
+    }
+
     /// Flip the sign of the X coordinate.
     pub inline fn neg(p: Edwards25519) Edwards25519 {
         return .{ .x = p.x.neg(), .y = p.y, .z = p.z, .t = p.t.neg() };
@@ -114,6 +119,11 @@ pub const Edwards25519 = struct {
         };
     }
 
+    /// Substract two Edwards25519 points.
+    pub fn sub(p: Edwards25519, q: Edwards25519) Edwards25519 {
+        return p.add(q.neg());
+    }
+
     inline fn cMov(p: *Edwards25519, a: Edwards25519, c: u64) void {
         p.x.cMov(a.x, c);
         p.y.cMov(a.y, c);
@@ -217,3 +227,17 @@ test "edwards25519 packing/unpacking" {
         std.testing.expectError(error.WeakPublicKey, small_p.mul(s));
     }
 }
+
+test "edwards25519 point addition/substraction" {
+    var s1: [32]u8 = undefined;
+    var s2: [32]u8 = undefined;
+    try std.crypto.randomBytes(&s1);
+    try std.crypto.randomBytes(&s2);
+    const p = try Edwards25519.basePoint.clampedMul(s1);
+    const q = try Edwards25519.basePoint.clampedMul(s2);
+    const r = p.add(q).add(q).sub(q).sub(q);
+    try r.rejectIdentity();
+    std.testing.expectError(error.IdentityElement, r.sub(p).rejectIdentity());
+    std.testing.expectError(error.IdentityElement, p.sub(p).rejectIdentity());
+    std.testing.expectError(error.IdentityElement, p.sub(q).add(q).sub(p).rejectIdentity());
+}
-- 
cgit v1.2.3