From 1e96ddd13bf69786c1b8a0a2f826059c26047a41 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 14 Mar 2024 20:19:25 +0700 Subject: EdDSA: Explicit guard against infinite looping --- crypto/src/math/ec/rfc8032/Ed25519.cs | 8 ++++++-- crypto/src/math/ec/rfc8032/Ed448.cs | 8 ++++++-- crypto/src/math/ec/rfc8032/Scalar25519.cs | 16 ++++++++++++++-- crypto/src/math/ec/rfc8032/Scalar448.cs | 16 ++++++++++++++-- crypto/src/math/ec/rfc8032/ScalarUtilities.cs | 12 ++++++------ 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 k, Span z0, Span z1) + internal static bool ReduceBasisVar(ReadOnlySpan k, Span z0, Span 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 v0 = stackalloc uint[4]; v0.CopyFrom(k); Span 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 k, Span z0, Span z1) + internal static bool ReduceBasisVar(ReadOnlySpan k, Span z0, Span 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 v0 = stackalloc uint[8]; v0.CopyFrom(k); Span 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; -- cgit 1.4.1