Information Security Asked by Roger Far on January 2, 2022

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!

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 '*g ^{a}*' to say "

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.)

Answered by Thomas Pornin on January 2, 2022

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.

Answered by frankodwyer on January 2, 2022

2 Asked on October 28, 2021 by stone-true

8 Asked on October 28, 2021

2 Asked on October 28, 2021 by kepotx

2 Asked on October 28, 2021 by nemanja-martinovic

2 Asked on October 28, 2021 by tomi-begher

1 Asked on October 28, 2021 by ian-warburton

2 Asked on October 28, 2021 by alehandro

man in the middle session management vpn vulnerability assessment

0 Asked on October 28, 2021

1 Asked on October 28, 2021 by user238715

4 Asked on October 28, 2021 by m-vencel

2 Asked on October 28, 2021 by sellarafaeli

3 Asked on October 28, 2021 by nkl

account security data leakage encryption passwords web browser

1 Asked on March 9, 2021 by reedghost

1 Asked on March 3, 2021

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir