EdDSA: Explicit guard against infinite looping

5 files changed, 46 insertions, 14 deletions

diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs
index 7318a8a7e..1cd9ddd48 100644
--- a/crypto/src/math/ec/rfc8032/Ed25519.cs
+++ b/crypto/src/math/ec/rfc8032/Ed25519.cs
@@ -751,7 +751,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v1 = new uint[4];
 #endif
 
-            Scalar25519.ReduceBasisVar(nA, v0, v1);
+            if (!Scalar25519.ReduceBasisVar(nA, v0, v1))
+                throw new InvalidOperationException();
+
             Scalar25519.Multiply128Var(nS, v1, nS);
 
             Init(out PointAccum pZ);
@@ -852,7 +854,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v1 = new uint[4];
 #endif
 
-            Scalar25519.ReduceBasisVar(nA, v0, v1);
+            if (!Scalar25519.ReduceBasisVar(nA, v0, v1))
+                throw new InvalidOperationException();
+
             Scalar25519.Multiply128Var(nS, v1, nS);
 
             Init(out PointAccum pZ);
diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs
index aff9b5460..e5d49f45a 100644
--- a/crypto/src/math/ec/rfc8032/Ed448.cs
+++ b/crypto/src/math/ec/rfc8032/Ed448.cs
@@ -695,7 +695,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v1 = new uint[8];
 #endif
 
-            Scalar448.ReduceBasisVar(nA, v0, v1);
+            if (!Scalar448.ReduceBasisVar(nA, v0, v1))
+                throw new InvalidOperationException();
+
             Scalar448.Multiply225Var(nS, v1, nS);
 
             Init(out PointProjective pZ);
@@ -790,7 +792,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v1 = new uint[8];
 #endif
 
-            Scalar448.ReduceBasisVar(nA, v0, v1);
+            if (!Scalar448.ReduceBasisVar(nA, v0, v1))
+                throw new InvalidOperationException();
+
             Scalar448.Multiply225Var(nS, v1, nS);
 
             Init(out PointProjective pZ);
diff --git a/crypto/src/math/ec/rfc8032/Scalar25519.cs b/crypto/src/math/ec/rfc8032/Scalar25519.cs
index 4fb2fd2da..08ab80607 100644
--- a/crypto/src/math/ec/rfc8032/Scalar25519.cs
+++ b/crypto/src/math/ec/rfc8032/Scalar25519.cs
@@ -595,7 +595,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 #endif
 
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        internal static void ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1)
+        internal static bool ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1)
         {
             /*
              * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L.
@@ -612,11 +612,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             Span<uint> v0 = stackalloc uint[4];     v0.CopyFrom(k);
             Span<uint> v1 = stackalloc uint[4];     v1[0] = 1U;
 
+            // Conservative upper bound on the number of loop iterations needed
+            int iterations = TargetLength * 4;
             int last = 15;
             int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv);
 
             while (len_Nv > TargetLength)
             {
+                if (--iterations < 0)
+                    return false;
+
                 int len_p = ScalarUtilities.GetBitLength(last, p);
                 int s = len_p - len_Nv;
                 s &= ~(s >> 31);
@@ -646,9 +651,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             // v1 * k == v0 mod L
             v0.CopyTo(z0);
             v1.CopyTo(z1);
+            return true;
         }
 #else
-        internal static void ReduceBasisVar(uint[] k, uint[] z0, uint[] z1)
+        internal static bool ReduceBasisVar(uint[] k, uint[] z0, uint[] z1)
         {
             /*
              * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L.
@@ -665,11 +671,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v0 = new uint[4];        Array.Copy(k, v0, 4);
             uint[] v1 = new uint[4];        v1[0] = 1U;
 
+            // Conservative upper bound on the number of loop iterations needed
+            int iterations = TargetLength * 4;
             int last = 15;
             int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv);
 
             while (len_Nv > TargetLength)
             {
+                if (--iterations < 0)
+                    return false;
+
                 int len_p = ScalarUtilities.GetBitLength(last, p);
                 int s = len_p - len_Nv;
                 s &= ~(s >> 31);
@@ -699,6 +710,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             // v1 * k == v0 mod L
             Array.Copy(v0, z0, 4);
             Array.Copy(v1, z1, 4);
+            return true;
         }
 #endif
 
diff --git a/crypto/src/math/ec/rfc8032/Scalar448.cs b/crypto/src/math/ec/rfc8032/Scalar448.cs
index d53f0b669..c3f91eef2 100644
--- a/crypto/src/math/ec/rfc8032/Scalar448.cs
+++ b/crypto/src/math/ec/rfc8032/Scalar448.cs
@@ -1114,7 +1114,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 #endif
 
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        internal static void ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1)
+        internal static bool ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1)
         {
             /*
              * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L.
@@ -1131,11 +1131,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             Span<uint> v0 = stackalloc uint[8];     v0.CopyFrom(k);
             Span<uint> v1 = stackalloc uint[8];     v1[0] = 1U;
 
+            // Conservative upper bound on the number of loop iterations needed
+            int iterations = TargetLength * 4;
             int last = 27;
             int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv);
 
             while (len_Nv > TargetLength)
             {
+                if (--iterations < 0)
+                    return false;
+
                 int len_p = ScalarUtilities.GetBitLength(last, p);
                 int s = len_p - len_Nv;
                 s &= ~(s >> 31);
@@ -1168,9 +1173,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             // v1 * k == v0 mod L
             v0.CopyTo(z0);
             v1.CopyTo(z1);
+            return true;
         }
 #else
-        internal static void ReduceBasisVar(uint[] k, uint[] z0, uint[] z1)
+        internal static bool ReduceBasisVar(uint[] k, uint[] z0, uint[] z1)
         {
             /*
              * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L.
@@ -1187,11 +1193,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             uint[] v0 = new uint[8];        Array.Copy(k, v0, 8);
             uint[] v1 = new uint[8];        v1[0] = 1U;
 
+            // Conservative upper bound on the number of loop iterations needed
+            int iterations = TargetLength * 4;
             int last = 27;
             int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv);
 
             while (len_Nv > TargetLength)
             {
+                if (--iterations < 0)
+                    return false;
+
                 int len_p = ScalarUtilities.GetBitLength(last, p);
                 int s = len_p - len_Nv;
                 s &= ~(s >> 31);
@@ -1224,6 +1235,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             // v1 * k == v0 mod L
             Array.Copy(v0, z0, 8);
             Array.Copy(v1, z1, 8);
+            return true;
         }
 #endif
 
diff --git a/crypto/src/math/ec/rfc8032/ScalarUtilities.cs b/crypto/src/math/ec/rfc8032/ScalarUtilities.cs
index fca4a0232..41d7f2696 100644
--- a/crypto/src/math/ec/rfc8032/ScalarUtilities.cs
+++ b/crypto/src/math/ec/rfc8032/ScalarUtilities.cs
@@ -71,11 +71,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             }
             else
             {
-                // Keep the original value of p in t
+                // Copy the low limbs of the original p
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-                t[..(last + 1)].CopyFrom(p);
+                t[..last].CopyFrom(p);
 #else
-                Array.Copy(p, 0, t, 0, last + 1);
+                Array.Copy(p, 0, t, 0, last);
 #endif
 
                 int sWords = s >> 5, sBits = s & 31;
@@ -288,11 +288,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             }
             else
             {
-                // Keep the original value of p in t
+                // Copy the low limbs of the original p
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-                t[..(last + 1)].CopyFrom(p);
+                t[..last].CopyFrom(p);
 #else
-                Array.Copy(p, 0, t, 0, last + 1);
+                Array.Copy(p, 0, t, 0, last);
 #endif
 
                 int sWords = s >> 5, sBits = s & 31;