Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Hallo all,

For a test project I have tried to implement the (famous) Diffie Hellman algorithm for safe key exchange.

Now I have written this in C#:

using System;
using System.Collections;
using System.Collections.Generic;

namespace DiffieHellman.Cryptology
{
    public static class CentralAuthority
    {
        private static readonly List<Int32> _primes = new List<Int32>();

        public static void CreatePrimeTable()
        {
            const Int32 topNumber = Int32.MaxValue / 2;
            BitArray numbers = new BitArray(topNumber, true);

            for (Int32 i = 2; i < topNumber; i++)
            {
                if (!numbers[i])
                    continue;

                for (Int32 j = i * 2; j < topNumber; j += i)
                    numbers[j] = false;
            }

            for (Int32 i = 1; i < topNumber; i++)
            {
                if (numbers[i])
                    _primes.Add(i);
            }
        }

        /// <summary>
        /// Generate a random Prime Number.
        /// </summary>
        public static Int32 GeneratePrime()
        {
            Int32 p = Randomizer.GetRandom(1, _primes.Count);
            return _primes[p];
        }

        /// <summary>
        /// Generate a random base integer (g) less than the prime
        /// </summary>
        public static Int32 GenerateBase(
            Int32 prime)
        {
            return Randomizer.GetRandom(1, prime - 1);
        }
    }
}




using System;

namespace DiffieHellman.Cryptology
{
    public class CaDiffieHellman
    {
        public Int64 Key { get; private set; }
        public Int32 Prime { get; private set; }
        public Int32 Generator { get; private set; }
        public Int64 ExponentiationY { get; private set; }
        private Int32 _privateX;

        public void GenerateParameters(
            Int32 prime = 0,
            Int32 generator = 0)
        {
            if (prime < 1 && generator < 1)
            {
                prime = CentralAuthority.GeneratePrime();
                generator = CentralAuthority.GenerateBase(prime);
            }

            if (prime <= generator - 1)
                return;

            Prime = prime;
            Generator = generator;
            _privateX = Randomizer.GetRandom(1, Prime - 1);

            Int64 xor = Generator ^ _privateX;
            while (xor > Prime - 1
                || xor == _privateX)
            {
                _privateX = Randomizer.GetRandom(1, Prime - 1);
                xor = Generator ^ _privateX;
            }

            ExponentiationY = (xor) % Prime;
        }

        public void GenerateKey(
            Int64 exponentiationYOther)
        {
            Key = (exponentiationYOther ^ _privateX) % Prime;
        }
    }
}



using System;
using System.Security.Cryptography;

namespace DiffieHellman.Cryptology
{
    public static class Randomizer
    {
        /// <summary>
        /// Real random generator
        /// Slower then Random().Next()!
        /// </summary>
        public static Int32 GetRandom(
            Int32 max)
        {
            return GetRandom(0, max);
        }

        /// <summary>
        /// Real random generator
        /// Slower than Random().Next()!
        /// </summary>
        public static Int32 GetRandom(
            Int32 min,
            Int32 max)
        {
            // Start a slower but more acurate randomizer service
            RNGCryptoServiceProvider rngCryptoServiceProvider = new RNGCryptoServiceProvider();
            Byte[] randomBytes = new Byte[4];
            rngCryptoServiceProvider.GetBytes(randomBytes);
            Int32 seed = BitConverter.ToInt32(randomBytes, 0);

            return new Random(seed).Next(min, max);
        }
    }
}


using System;
using System.Diagnostics;
using DiffieHellman.Cryptology;

namespace DiffieHellman
{
    public class Program
    {
        private static readonly CaDiffieHellman _caDiffieHellmanServer = new CaDiffieHellman();
        private static readonly CaDiffieHellman _caDiffieHellmanClient = new CaDiffieHellman();

        static void Main()
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            CentralAuthority.CreatePrimeTable();
            stopwatch.Stop();
            Console.WriteLine("Create Prime Table: {0}ms", stopwatch.ElapsedMilliseconds);

            stopwatch = Stopwatch.StartNew();
            for (Int32 i = 0; i < Int32.MaxValue; i++)
            {
                // Generate random prime and generator at server
                _caDiffieHellmanServer.GenerateParameters();

                // Send prime and generator to client
                _caDiffieHellmanClient.GenerateParameters(_caDiffieHellmanServer.Prime, _caDiffieHellmanServer.Generator);

                // Calculate the key
                _caDiffieHellmanServer.GenerateKey(_caDiffieHellmanClient.ExponentiationY);

                // Calculate the key
                _caDiffieHellmanClient.GenerateKey(_caDiffieHellmanServer.ExponentiationY);

                if (_caDiffieHellmanServer.Key != _caDiffieHellmanClient.Key)
                    Console.WriteLine("Error ({0}): wrong key", i);

                if (_caDiffieHellmanServer.Key == 0 || _caDiffieHellmanClient.Key == 0)
                    Console.WriteLine("Error ({0}): key 0", i);

                if (i % 10000 == 0)
                    Console.WriteLine("Progress: {0}, {1}ms, {2}", i, stopwatch.ElapsedMilliseconds, _caDiffieHellmanServer.Key);
            }
            stopwatch.Stop();
            Console.WriteLine("Loop: {0}ms", stopwatch.ElapsedMilliseconds);

            Console.ReadKey();
        }
    }
}

Now my main concern is that I did not use the standard formula: g pow(a) mod p = A, but g XOR a mod p. The pow(a) does not work if it goes outside the int64 value.

Is this a safety concern?

This implementation has only 1 bug: when both parties generate the same privateX, it will fail, but with the large amount of base numbers generated this only happens once in about 50 million times.

I would like to discuss the strength of this method and potential pitfalls!

Thanks!

share|improve this question
7  
I'll let a cryptography expert explain just how this is broken, but as a basic principle, you never ever change a cryptographic algorithm unless you have a degree in cryptography. (And if you do you don't start using your new version until it's had serious peer review.) Here, you need to implement modular exponentiation. –  Gilles May 2 '11 at 9:03
    
and for speed concerns, don't use C# for this kind algo which can have a lot of iterations. C++ or C would be preferred... You also better use some already existing code or lib for that, search for open stuff, lots of chance you will find something better and safer. –  jokoon May 2 '11 at 12:59
    
"you never ever change a cryptographic algorithm" - People implement cryptographic algorithms for educational purposes too you know. –  Alan Zeino May 4 '11 at 3:14
    
@jokoon I've implemented ECC in C# and it's not much slower than equivalent standard C code. C only pulls significantly ahead once you use Int128 language extensions. –  CodesInChaos Aug 15 '13 at 7:57
add comment

2 Answers

up vote 9 down vote accepted

What you implemented is not Diffie-Hellman, and has no strength at all. You are being confused with the use of the '^' character.

In C-like programming languages, '^' is the operator for a bitwise exclusive-or (a "XOR").

When writing mathematics in ASCII, it is customary to denotes exponentiation with the '^' character -- and it is not a XOR at all ! This notation comes from LaTeX, a typesetting system which is the de facto standard among mathematicians. In this message, I can use HTML tags and write 'ga' to say "g to the power a", but if I were to write in plain ASCII (e.g. on Usenet), I would have to write: 'g^a'.

Moreover, Diffie-Hellman uses modular exponentation on big integers -- typical size being 1024 bits or more. 32-bit or 64-bit integers will not be enough to achieve any kind of security, and, in any case, modular exponentiation is not what pow() implements (in algebraic terms, you want to work over a finite field, not plain integers or real numbers). In C# (.NET 4.0), you would want to use the System.Numerics.BigInteger class, and in particular its ModPow() method. But first, if you ever want to do that, you first have to understand the underlying mathematics. You can begin by reading the first three chapters of the Handbook of Applied Cryptography (no relation whatsoever with Schneier's "Applied Cryptography", and, in my view, the "Handbook" is a far more useful book). It may seem a bit harsh, but you cannot hope to implement Diffie-Hellman properly unless you master the mathematics described in those first three chapters.

(And, of course, implementing cryptographic algorithms has other pitfalls, related to side-channel leaks, so even if you do understand what happens mathematically, making your own implementation is not necessarily a good idea.)

share|improve this answer
1  
Thanks for the clarification! I used this code from somebody else which I made it to work, but as I am not a cryptology nor mathematical expert I needed somebody to look at this. I got the original source for this guy, but because I saw the change in XOR and POW I decided to ask the real experts. dotnetslackers.com/articles/security/… –  Rogier21 May 2 '11 at 22:05
add comment

Diffie-Hellman is based on modular exponentiation, so by using a different function in this code you haven't implemented Diffie-Hellman at all but something else.

Also the 63/64-bit numbers you're using are too small in any case.

You should read a basic text on cryptography, e.g. Schneier's Applied Cryptography.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.