Fix for timing-dependent HMAC signature equality check.

3 files changed, 100 insertions, 3 deletions

diff --git a/src/DotNetOpenAuth.Test/Messaging/MessagingUtilitiesTests.cs b/src/DotNetOpenAuth.Test/Messaging/MessagingUtilitiesTests.cs
index 2b0e8f9..71a8e14 100644
--- a/src/DotNetOpenAuth.Test/Messaging/MessagingUtilitiesTests.cs
+++ b/src/DotNetOpenAuth.Test/Messaging/MessagingUtilitiesTests.cs
@@ -4,11 +4,11 @@
 // </copyright>
 //-----------------------------------------------------------------------
 
-namespace DotNetOpenAuth.Test.Messaging
-{
+namespace DotNetOpenAuth.Test.Messaging {
 	using System;
 	using System.Collections.Generic;
 	using System.Collections.Specialized;
+	using System.Diagnostics;
 	using System.IO;
 	using System.Net;
 	using System.Text.RegularExpressions;
@@ -216,5 +216,65 @@ namespace DotNetOpenAuth.Test.Messaging
 		public void GetHttpDeliveryMethodOutOfRangeTest() {
 			MessagingUtilities.GetHttpDeliveryMethod("UNRECOGNIZED");
 		}
+		/// <summary>
+		/// Verifies that the time-independent string equality check works accurately.
+		/// </summary>
+		[TestCase]
+		public void EqualsConstantTime() {
+			this.EqualsConstantTimeHelper(null, null);
+			this.EqualsConstantTimeHelper(null, string.Empty);
+			this.EqualsConstantTimeHelper(string.Empty, string.Empty);
+			this.EqualsConstantTimeHelper(string.Empty, "a");
+			this.EqualsConstantTimeHelper(null, "a");
+			this.EqualsConstantTimeHelper("a", "a");
+			this.EqualsConstantTimeHelper("a", "A");
+			this.EqualsConstantTimeHelper("A", "A");
+			this.EqualsConstantTimeHelper("ab", "ab");
+			this.EqualsConstantTimeHelper("ab", "b");
+		}
+
+		/// <summary>
+		/// Verifies that EqualsConstantTime actually has the same execution time regardless of how well a value matches.
+		/// </summary>
+		[TestCase]
+		public void EqualsConstantTimeIsActuallyConstantTime() {
+			string expected = new string('A', 5000);
+			string totalmismatch = new string('B', 5000);
+			string almostmatch = new string('A', 4999) + 'B';
+
+			const int iterations = 4000;
+			var totalMismatchTimer = new Stopwatch();
+			totalMismatchTimer.Start();
+			for (int i = 0; i < iterations; i++) {
+				MessagingUtilities.EqualsConstantTime(expected, totalmismatch);
+			}
+			totalMismatchTimer.Stop();
+
+			var almostMatchTimer = new Stopwatch();
+			almostMatchTimer.Start();
+			for (int i = 0; i < iterations; i++) {
+				MessagingUtilities.EqualsConstantTime(expected, almostmatch);
+			}
+			almostMatchTimer.Stop();
+
+			const double toleranceFactor = 0.06;
+			long averageTimeTicks = (totalMismatchTimer.ElapsedTicks + almostMatchTimer.ElapsedTicks) / 2;
+			var tolerableDifference = TimeSpan.FromTicks((long)(averageTimeTicks * toleranceFactor));
+			var absoluteDifference = TimeSpan.FromTicks(Math.Abs(totalMismatchTimer.ElapsedTicks - almostMatchTimer.ElapsedTicks));
+			double actualFactor = (double)absoluteDifference.Ticks / averageTimeTicks;
+			Assert.IsTrue(absoluteDifference <= tolerableDifference, "A total mismatch took {0} but a near match took {1}, which is too different to be indistinguishable.  The tolerable difference is {2} but the actual difference is {3}.  This represents a difference of {4}%, beyond the tolerated {5}%.", totalMismatchTimer.Elapsed, almostMatchTimer.Elapsed, tolerableDifference, absoluteDifference, Math.Round(actualFactor * 100), Math.Round(toleranceFactor * 100));
+			Console.WriteLine("The equality test execution time difference was only {0}%, within the tolerable {1}%", Math.Round(100 * actualFactor), Math.Round(toleranceFactor * 100));
+		}
+
+		/// <summary>
+		/// Verifies that the time-independent string equality check works for a given pair of strings.
+		/// </summary>
+		/// <param name="value1">The first value.</param>
+		/// <param name="value2">The second value.</param>
+		private void EqualsConstantTimeHelper(string value1, string value2) {
+			bool expected = string.Equals(value1, value2, StringComparison.Ordinal);
+			Assert.AreEqual(expected, MessagingUtilities.EqualsConstantTime(value1, value2));
+			Assert.AreEqual(expected, MessagingUtilities.EqualsConstantTime(value2, value1));
+		}
 	}
 }
diff --git a/src/DotNetOpenAuth/Messaging/MessagingUtilities.cs b/src/DotNetOpenAuth/Messaging/MessagingUtilities.cs
index 6a55bc9..7c25f73 100644
--- a/src/DotNetOpenAuth/Messaging/MessagingUtilities.cs
+++ b/src/DotNetOpenAuth/Messaging/MessagingUtilities.cs
@@ -298,6 +298,43 @@ namespace DotNetOpenAuth.Messaging {
 		}
 
 		/// <summary>
+		/// Compares to string values for ordinal equality in such a way that its execution time does not depend on how much of the value matches.
+		/// </summary>
+		/// <param name="value1">The first value.</param>
+		/// <param name="value2">The second value.</param>
+		/// <returns>A value indicating whether the two strings share ordinal equality.</returns>
+		/// <remarks>
+		/// In signature equality checks, a difference in execution time based on how many initial characters match MAY
+		/// be used as an attack to figure out the expected signature.  It is therefore important to make a signature
+		/// equality check's execution time independent of how many characters match the expected value.
+		/// See http://codahale.com/a-lesson-in-timing-attacks/ for more information.
+		/// </remarks>
+		internal static bool EqualsConstantTime(string value1, string value2) {
+			// If exactly one value is null, they don't match.
+			if (value1 == null ^ value2 == null) {
+				return false;
+			}
+
+			// If both values are null (since if one is at this point then they both are), it's a match.
+			if (value1 == null) {
+				return true;
+			}
+
+			if (value1.Length != value2.Length) {
+				return false;
+			}
+
+			// This looks like a pretty crazy way to compare values, but it provides a constant time equality check,
+			// and is more resistant to compiler optimizations than simply setting a boolean flag and returning the boolean after the loop.
+			int result = 0;
+			for (int i = 0; i < value1.Length; i++) {
+				result |= value1[i] ^ value2[i];
+			}
+
+			return result == 0;
+		}
+
+		/// <summary>
 		/// Adds a set of HTTP headers to an <see cref="HttpResponse"/> instance,
 		/// taking care to set some headers to the appropriate properties of
 		/// <see cref="HttpResponse" />
diff --git a/src/DotNetOpenAuth/OpenId/ChannelElements/SigningBindingElement.cs b/src/DotNetOpenAuth/OpenId/ChannelElements/SigningBindingElement.cs
index 3f4a998..30310ac 100644
--- a/src/DotNetOpenAuth/OpenId/ChannelElements/SigningBindingElement.cs
+++ b/src/DotNetOpenAuth/OpenId/ChannelElements/SigningBindingElement.cs
@@ -134,7 +134,7 @@ namespace DotNetOpenAuth.OpenId.ChannelElements {
 				Association association = this.GetSpecificAssociation(signedMessage);
 				if (association != null) {
 					string signature = this.GetSignature(signedMessage, association);
-					if (!string.Equals(signedMessage.Signature, signature, StringComparison.Ordinal)) {
+					if (!MessagingUtilities.EqualsConstantTime(signedMessage.Signature, signature)) {
 						Logger.Bindings.Error("Signature verification failed.");
 						throw new InvalidSignatureException(message);
 					}