Posts Tagged ‘security’
Secure Remote Password protocol (SRP)
The Secure Remote Password Protocol (SRP) is a password-authenticated key agreement protocol. Before, I used digest algorithm (similar to Digest access authentication) to authenticate my users. As I had to add encryption to my message system (not 100% encrytion means only some messages are confidential) I decided to implement SRP as it
- allows to securly authenticate a user
- creates a common key that can be used as an encryption key
- is something new to implement as I like to implement new stuff
Before I start, some helpful extensions I will be using along the way:
namespace System.IO
{
public static class StreamExtension
{
public static void Write(this Stream s, byte[] buffer)
{
s.Write(buffer, 0, buffer.Length);
}
public static int Read(this Stream s, byte[] buffer)
{
return s.Read(buffer, 0, buffer.Length);
}
}
}
using System.Runtime.InteropServices;
namespace System.Security
{
public static class SecureStringExtension
{
public static string ConvertToUnsecureString(this SecureString securePassword)
{
if (securePassword == null)
throw new ArgumentNullException("securePassword");
IntPtr unmanagedString = IntPtr.Zero;
try
{
unmanagedString = Marshal.SecureStringToGlobalAllocUnicode(securePassword);
return Marshal.PtrToStringUni(unmanagedString);
}
finally
{
Marshal.ZeroFreeGlobalAllocUnicode(unmanagedString);
}
}
}
}
Implementing SRP involves a lot of BigInteger calculations, such as multiplying and taking the exponent of some large number. The .Net framework does not yet implement such a BigInteger class, so I’m using some classes from Mono. I included Mono.Math.BigInteger, Mono.Math.Prime.ConfidenceFactor and .PrimalityTests, Mono.Math.Prime.Generator.NextPrimeFinder, .PrimeGeneratorBase, and .SequentialSearchPrimeGeneratorBase.
As the protocol description says, it all starts with N and g:
N should be a secure prime, which means that N is calculated by N=2q + 1 where q is also a prime. Finding such an N is easy but takes a lot of time specially if N should be greater than 1024 bits. N and g don’t have to be secure, so you can just define them once.
Here is a N of bit length 2048 encoded as Base64
string N_Base64 = "rGvbQTJKmpvxZt5eE4lYL69ytmUZh+4H/DGSlD21YFCjcynLtKCZ7YGT4HV3Z6E91SMSq0s" + "DMQ3Nf0ip2gT9UOgIOWntt2ewz2CVF5oWOrNmGgX71fqq6CkYqZYvC5O4Vfl5k+yXXuqoDX" + "QK2/T/dHNZ0EHVwz6nHSgeRGsUdzvKl7Q6I/uAFna9IHpDbGSB8dK5B4cXRhpbnTLmiPh3S" + "FRFI7UksNV9Xqd6J3XS7PoDLPvb9S+zeGFgJ5AE5Xrmr4dOcwPOUymczAQce8MI2CpWmPOo" + "0MOCca41+Onb+7aUtcgD2J965DXeI21SX1R1m2XjcvzWjvIPpxEfnkr/cw=="; BigInteger N = new BigInteger(Convert.FromBase64String(N_Base64));
g is just a generator of the multiplicative group. So, it is used in caluclations like g^x where x is very large. Most people would probably choose g=2. But i’m not “most people”, so i set g=3.
As you look further into the description, you’ll see the that there are a lot of variables needed on both sides (server and client side). To make life easier, let’s define a base class for that:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Security;
using System.Security.Cryptography;
using Mono.Math;
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
// initialize some random number generaror
private static RandomNumberGenerator s_rng = RandomNumberGenerator.Create();
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPBase(BigInteger N, BigInteger g)
{
if (N == null)
throw new ArgumentNullException("N");
if (g == null)
throw new ArgumentNullException("g");
this.N = N;
this.g = g;
}
/// <summary>
/// N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible
/// </summary>
public BigInteger N { get; private set; }
/// <summary>
/// g is a generator of the multiplicative group
/// </summary>
public BigInteger g { get; private set; }
}
}
The next parameter that will be defined is k. k is a parameter derived by both sides; for example, k = H(N, g), where H() is a hash function; e.g., SHA-256. This goes into our SRPBase class:
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
private BigInteger m_k;
/// <summary>
/// k is a parameter derived by both sides; for example, k = H(N, g).
/// </summary>
public BigInteger k
{
get
{
if (m_k == null)
{
byte[] both = SRPHelper.JoinArrays(this.N.GetBytes(), this.g.GetBytes());
byte[] hash = SRPHelper.ShaInstance.ComputeHash(both);
m_k = new BigInteger(hash);
}
return m_k;
}
}
}
}
s, the small salt, is calculated on the server side and send to the client. So s has to be a getter/setter property.
We also extend our constructor to be able to pass s as a parameter, and define I and p (Username and Password of the user to authenticate).
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
private BigInteger m_s;
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPBase(string userName, SecureString password, BigInteger N, BigInteger g)
: this(userName, password, null, N, g) { }
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="s">s is a small salt.</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPBase(string userName, SecureString password, byte[] s, BigInteger N, BigInteger g)
{
if (N == null)
throw new ArgumentNullException("N");
if (g == null)
throw new ArgumentNullException("g");
if (string.IsNullOrEmpty(userName))
throw new ArgumentNullException("userName");
if (password == null)
throw new ArgumentNullException("password");
this.UserName = userName;
this.Password = password.Copy();
this.s = s;
this.N = N;
this.g = g;
}
/// <summary>
/// I, is an identifying username.
/// </summary>
public string UserName { get; private set; }
private SecureString Password { get; set; }
public byte[] s
{
get
{
// not set yet, generate some random data
if (m_s == null)
{
m_s = new byte[16];
lock (s_rng) { s_rng.GetNonZeroBytes(m_s); }
}
return m_s;
}
set { m_s = value; }
}
}
}
Now we have everything to calculate x = H(s, p), and the host password verifier v = g^x. Hint: If you do not want to store the password on the server side as clear text, you can store only v and s only. If you plan to change g, you better off to store g along as well.
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
private BigInteger m_x, m_v;
/// <summary>
/// x = H(s, p)
/// </summary>
public BigInteger x
{
get
{
if (m_x == null)
{
byte[] innerBytes = Encoding.UTF8.GetBytes(this.UserName + ":" + this.Password.ConvertToUnsecureString());
byte[] bytes = SRPHelper.JoinArrays(this.s, innerBytes);
byte[] hash = SRPHelper.ShaInstance.ComputeHash(bytes);
m_x = new BigInteger(hash);
}
return m_x;
}
}
/// <summary>
/// v is the host's password verifier, v = g^x, x = H(s,p).
/// </summary>
public BigInteger v
{
get
{
if (m_v == null)
m_v = this.g.ModPow(this.x, this.N);
return m_v;
}
}
}
}
Let’s go on. A and B are both calculated. A is calculated on the client side as A = g^a, and B is calculated on the server side as B = kv + g^b. But values are exchanged; so at some time, both sides contain A and B, so we make some stub implementation for both properties and at them to our constructors.
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
private byte[] m_K;
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="A">A = g^a, calculated by the client, send to the server</param>
/// <param name="B">B = kv + g^b, calculated by the server, send to the client</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPBase(string userName, SecureString password, BigInteger A, BigInteger B, BigInteger N, BigInteger g)
: this(userName, password, null, A, B, N, g) { }
/// <summary>
///
/// </summary>
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="s">s is a small salt.</param>
/// <param name="A">A = g^a, calculated by the client, send to the server</param>
/// <param name="B">B = kv + g^b, calculated by the server, send to the client</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPBase(string userName, SecureString password, byte[] s, BigInteger A, BigInteger B, BigInteger N, BigInteger g)
{
if (N == null)
throw new ArgumentNullException("N");
if (g == null)
throw new ArgumentNullException("g");
if (string.IsNullOrEmpty(userName))
throw new ArgumentNullException("userName");
if (password == null)
throw new ArgumentNullException("password");
this.N = N;
this.g = g;
this.A = A;
this.B = B;
this.s = s;
this.UserName = userName;
this.Password = password.Copy();
}
/// <summary>
/// Carol calculates A = g^a and sends it to Steve
/// </summary>
public virtual BigInteger A
{
get; set;
}
/// <summary>
/// Steve calculates B = kv + g^b and sends it to Carol
/// </summary>
public virtual BigInteger B
{
get; set;
}
/// <summary>
/// Secret
/// </summary>
public abstract BigInteger S { get; }
/// <summary>
/// Strong Session Key
/// </summary>
public byte[] K
{
get
{
if (m_K == null)
m_K = SRPHelper.ShaInstance.ComputeHash(this.S.GetBytes());
return m_K;
}
}
}
}
As you noticed, we added two more properties: the abstract getter property S as well as K. S is the secret that is calculated on both sides and must never be exchanged. The client calculates S as S=(B – kg^x)^(a + ux), and the client defines S=(Av^u)^b. a and b are both random numbers, generated on client and server and also get never exchanged. Funny is, that S on both sides are equal. Well, it’s not funny it’s pure math and it took me some time to convince myself that both equations for S are equivalent.
K is just K=H(S). K can later be used as an encryption key.
To finish up our SRPBase class, we are now able to define M1 and M2. M1 is first send to the server. The server itself calculates M1 with the information it collected and compares the received M1 with it’s own M1. If both are equal, the server has proof that the client knows the right username + password combination. It then sends M2 to the client. Client does the same thing now. It calculates its own M2, compares and verifies. We go in detail later.
namespace Esskar.Security.Authen.SRP
{
public abstract class SRPBase
{
/// <summary>
/// M1, Carol sends M1 to Steve
/// M1 = H(H(N) XOR H(g) | H(I) | s | A | B | K)
/// </summary>
public virtual byte[] M1
{
get
{
byte[] hg = SRPHelper.ShaInstance.ComputeHash(this.g.GetBytes());
byte[] hN = SRPHelper.ShaInstance.ComputeHash(this.N.GetBytes());
byte[] gNXorBytes = SRPHelper.XorArrays(hN, hg);
byte[] userNameBytes = Encoding.UTF8.GetBytes(this.UserName);
byte[] hUserNameBytes = SRPHelper.ShaInstance.ComputeHash(userNameBytes);
using (MemoryStream ms = new MemoryStream())
{
ms.Write(gNXorBytes);
ms.Write(hUserNameBytes);
ms.Write(this.s);
ms.Write(this.A.GetBytes());
ms.Write(this.B.GetBytes());
ms.Write(this.K);
return SRPHelper.ShaInstance.ComputeHash(ms.ToArray());
}
}
}
/// <summary>
/// M2, Steve sends M2 to Carol
/// M2 = H(A | M1 | K).
/// </summary>
public byte[] M2
{
get
{
using (MemoryStream ms = new MemoryStream())
{
ms.Write(this.A.GetBytes());
ms.Write(this.M1);
ms.Write(this.K);
return SRPHelper.ShaInstance.ComputeHash(ms.ToArray());
}
}
}
}
}
Now, we define our client side, class SRPRequest:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security;
using System.Text;
using Mono.Math;
namespace Esskar.Security.Authen.SRP
{
public class SRPRequest : SRPBase
{
private BigInteger m_a, m_S;
/// <summary>
/// SRP Request, constructed on the client side
/// </summary>
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPRequest(string userName, SecureString password, BigInteger N, BigInteger g)
: base(userName, password, null, null, N, g) { }
/// <summary>
/// a is random
/// </summary>
private BigInteger a
{
get
{
if(m_a == null)
m_a = BigInteger.GenerateRandom(1024);
return m_a;
}
}
/// <summary>
/// A = g^a
/// </summary>
public override BigInteger A
{
get
{
if (base.A == null)
base.A = this.g.ModPow(this.a, this.N);
return base.A;
}
}
/// <summary>
/// Secret calculated on the client, (B - kg^x)^(a + ux)
/// </summary>
public override BigInteger S
{
get
{
if (m_S == null)
m_S = (this.B + (this.N - ((this.k * this.g.ModPow(this.x, this.N)) % this.N))).ModPow(this.a + this.u * this.x, this.N);
return m_S;
}
}
}
}
and our ServerSide, class SRPReply
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security;
using System.Security.Cryptography;
using System.Text;
using Mono.Math;
namespace Esskar.Security.Authen.SRP
{
public class SRPReply : SRPBase
{
private BigInteger m_b;
/// <summary>
/// SRP Reply, constructed on the server side
/// </summary>
/// <param name="userName">I is an identifying username.</param>
/// <param name="password">p is the user's password.</param>
/// <param name="A">A = g^a, calculated by the client, send to the server</param>
/// <param name="N">N is a safe prime. Must be large enough so that computing discrete logarithms modulo N is infeasible</param>
/// <param name="g">g is a generator of the multiplicative group</param>
public SRPReply(string userName, SecureString password, BigInteger A, BigInteger N, BigInteger g)
: base(userName, password, A, null, N, g) { }
/// <summary>
/// random number
/// </summary>
private BigInteger b
{
get
{
if (m_b == null)
m_b = BigInteger.GenerateRandom(1024);
return m_b;
}
}
/// <summary>
/// B = kv + g^b
/// </summary>
public override BigInteger B
{
get
{
if (base.B == null)
base.B = (this.k * this.v + this.g.ModPow(this.b, this.N)) % this.N;
return base.B;
}
}
/// <summary>
/// Secret calculated on the server: (Av^u)^b
/// </summary>
public override BigInteger S
{
get { return (this.A * this.v.ModPow(this.u, this.N)).ModPow(this.b, this.N); }
}
}
}
Nice. We now have everything to authenticate our users.
Here a little test. (Note that this test does not send any data, it just verifies that our client and server calculate the right things).
public static class SRPTester
{
private static string N_Base64 = "rGvbQTJKmpvxZt5eE4lYL69ytmUZh+4H/DGSlD21YFCjcynLtKCZ7YGT4HV3Z6E91SMSq0s"
+ "DMQ3Nf0ip2gT9UOgIOWntt2ewz2CVF5oWOrNmGgX71fqq6CkYqZYvC5O4Vfl5k+yXXuqoDX"
+ "QK2/T/dHNZ0EHVwz6nHSgeRGsUdzvKl7Q6I/uAFna9IHpDbGSB8dK5B4cXRhpbnTLmiPh3S"
+ "FRFI7UksNV9Xqd6J3XS7PoDLPvb9S+zeGFgJ5AE5Xrmr4dOcwPOUymczAQce8MI2CpWmPOo"
+ "0MOCca41+Onb+7aUtcgD2J965DXeI21SX1R1m2XjcvzWjvIPpxEfnkr/cw==";
private static Mono.Math.BigInteger g = new Mono.Math.BigInteger(3);
public static SRPRequest ClientRequest(string userName, SecureString password)
{
return new SRPRequest(userName, password, new BigInteger(Convert.FromBase64String(N_Base64)), g);
}
public static SRPReply ServerReply(string userName, SecureString password, BigInteger A)
{
return new SRPReply(userName, password, A, new BigInteger(Convert.FromBase64String(N_Base64)), g);
}
static void Main(string[] args)
{
string userName = "foo";
SecureString password = new SecureString();
SRPRequest srpRequest = SRPTester.ClientRequest(userName, password);
// We generated the request, and have to send A to the server. Somehow.
// The server takes A to initialize it's reply
SRPReply srpReply = SRPTester.ServerReply(userName, password, srpRequest.A);
if ((srpRequest.A % srpReply.N) == 0) // safeguard 1
throw new Exception("A mod N is zero.");
// The server sends now s and B to the client, the client adds them to its object
if ((srpReply.B % srpRequest.N) == 0) // safeguard 2
throw new Exception("B mod N is zero.");
srpRequest.B = srpReply.B;
srpRequest.s = srpReply.s;
if (srpRequest.u == 0) // safeguard 3
throw new Exception("u is zero.");
// now, the client sends M1 to the server and it verifies that its M1 is equal to the M1 of the client
if (!SRPHelper.Equals<byte>(srpRequest.M1, srpReply.M1))
throw new Exception("M1 not equal M1.");
// if everything looks good, the server sends now its M2 to the client and the client verifies M2
if (!SRPHelper.Equals<byte>(srpRequest.M2, srpReply.M2))
throw new Exception("M2 not equal M2.");
}
}
To make this post complete, here is the code of the SRPHelper class:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
namespace Esskar.Security.Authen.SRP
{
/// <summary>
/// Some useful functions used frequently
/// </summary>
public static class SRPHelper
{
/// <summary>
/// Sha256 Instance used to compute hashes
/// </summary>
public static SHA256 ShaInstance = SHA256.Create();
/// <summary>
/// Joins two byte arrays to one single byte array by concating them
/// </summary>
/// <param name="b1">first byte array</param>
/// <param name="b2">second byte array</param>
/// <returns></returns>
public static byte[] JoinArrays(byte[] b1, byte[] b2)
{
byte[] ba = new byte[b1.Length + b2.Length];
Buffer.BlockCopy(b1, 0, ba, 0, b1.Length);
Buffer.BlockCopy(b2, 0, ba, b1.Length, b2.Length);
return ba;
}
/// <summary>
/// XORs the elements of two arrays and returns the resulting array
/// </summary>
/// <param name="array1"></param>
/// <param name="array2"></param>
/// <returns></returns>
public static byte[] XorArrays(byte[] b1, byte[] b2)
{
if (b1 == null)
throw new ArgumentNullException("b1");
if (b2 == null)
throw new ArgumentNullException("b2");
if (b1.Length == 0)
throw new ArgumentOutOfRangeException("b1 can not be zero length.");
if (b1.Length != b2.Length)
throw new ArgumentOutOfRangeException("b1.Length != b2.Length");
byte[] ba = new byte[b1.Length];
for (int i = 0; i < b1.Length; i++)
ba[i] = (byte)(b1[i] ^ b2[i]);
return ba;
}
/// <summary>
/// Checks if the elements of two arrays are equal
/// </summary>
public static bool Equals<T>(IList<T> a, IList<T> b) where T : IComparable<T>
{
if (a == null)
throw new ArgumentNullException("a");
if (b == null)
throw new ArgumentNullException("b");
bool retval = a.Count == b.Count;
if (retval)
{
for (int i = 0; retval && i < a.Count; i++)
retval = a[i].CompareTo(b[i]) == 0;
}
return retval;
}
}
}
