|
If I replace '__int64' with 'unsigned long', doesn't that reduce the key size, and therefore also the security level ?
|
|
|
|
|
Yes it sure will. It all depends on how secure you want your communication. It's probably best to get your hands on the GMP libraries (free on sourceforge.net). And you can then assign your integers to a massive number of digits.
|
|
|
|
|
Hello again,
I wrote a small sample app to use it with Bruce Schneier's Blowfish implementation.
It seems the resulting encryption key is not the same for the sender and the recipient.
(see the commented exit(-1) statement below)
Could you tell me what I do wrong ?
#include "DrmCrypto.h"
#include "BLOWFISH.H"
struct KeyData
{
__int64 Generator;
__int64 Modulus;
__int64 InterKey;
__int64 EncryptionKey;
};
int _tmain(int argc, _TCHAR* argv[])
{
KeyData SenderKeyData, RecipientKeyData;
CDrmCrypto Sender, Recipient;
Sender.CreateKeys(SenderKeyData.Generator, SenderKeyData.Modulus);
Recipient.CreateKeys(RecipientKeyData.Generator, RecipientKeyData.Modulus);
Sender.CreateSenderInterKey(SenderKeyData.InterKey);
Recipient.CreateRecipientInterKey( RecipientKeyData.InterKey, RecipientKeyData.Generator,
RecipientKeyData.Modulus);
Sender.CreateSenderEncryptionKey( SenderKeyData.EncryptionKey, RecipientKeyData.InterKey);
Recipient.CreateRecipientEncryptionKey( RecipientKeyData.EncryptionKey, SenderKeyData.InterKey);
if (SenderKeyData.EncryptionKey != RecipientKeyData.EncryptionKey)
{
printf("Sender & Recipient encryption keys do not match.\n");
// exit(-1);
}
if (InitializeBlowfish((char*)&SenderKeyData.EncryptionKey, (short)sizeof(SenderKeyData.EncryptionKey) ))
{
printf("InitializeBlowfish returned an error.\n");
exit(-1);
}
unsigned long xl1 = 123456789;
unsigned long xr1 = 987654321;
unsigned long xl2 = xl1;
unsigned long xr2 = xr1;
Blowfish_encipher(&xl1,&xr1);
Blowfish_decipher(&xl1,&xr1);
if (xl1 != xl2 || xr1 != xr2)
{
printf("Encryption failed.\n");
exit(-1);
}
printf("Done.\n");
return 0;
}
|
|
|
|
|
You are using the class incorrectly. The sender is the only one that calls createkeys. The sender then creates the sender interim key. The reciever then uses the sender's interim, and public keys (ones generated from createkeys), to make his interim key. The reciever can now call CreateRecipientEncryptionKey, and the sender can call CreateSenderEncryptionKey (and pass the reciever's interim key). Both parties should now have the same encryption key.
Please read the example usage notes (i think they should make it clear what needs to be done).
Have fun.
Best Regards,
Lee Griffiths
|
|
|
|
|
Ever wanted to use encryption, but got stuck trying to get the encrption key to the recipient? A real chicken and egg problem. The solution is that you can use Diffie-Hellman-Merkle key exchange.
Diffie-Hellman-Merkle key exchange uses y = g^x (mod p) to create a once-off shared secret encryption key of arbitrary length. This secret key can then be used to exchange data encrypted using the key. What makes DH key exchange fascinating is that is is not necessary to exchange secret information in order to 'share' the encryption key. Anyone evesdropping on the line cannot derive the key from the information exchanged during the negotiation process.
Security is based on the fact that it is mathematically infeasible to discover the key IF THE VALUES ARE LARGE ENOUGH. Adequate security typically utilizes keys in of 1000 bits. Security is enhanced due to the fact that a new, unique encryption key is generated each time.
The primary limitation is in performing large-integer arithmetic. Fortunately there are public/free implementations available. Or you can read Knuth and write one yourself. Check out the BigDigits library at www.di-mgt.com.au. Be aware that using this code it is possible to create arbitrarily long keys, which may have legal implications in your area. The key buffer is hard-limited to 51 4-byte integers (51*4=204bytes=1632bits), and will crash if you use a larger key buffer, so be warned.
The Way It Works
DH key exchange uses the following pattern (Bob (recipient) and Alice (sender) exchange messages, with Eve evesdropping).
First, the key format. This consists of three components g, x, and p.
g is the GENERATOR. Use a small prime, say 2, 3, 5, 7 etc.
x is the EXPONENT. This is the key, a random number of, say, 1024 bits.
p is the MODULUS. This is a large prime, typically of the same order as x (1024 bits).
Use CryptoApi, .NET crypto or any other service provider to create secure values and primes of this magnitude. Do not use Rnd!
1. Bob chooses a private key. (g, x1, and p) (generates these values)
The magnitude of x1 is equivalent to the resulting encryption key size.
x1 must be kept secret.
2. Bob calculates a new x2 value using x2 = g ^ x1 (mod p)
Publishes this key (in a directory, web page, or email).
g, x2, p
[ EVE INTERCEPTS ]
3. Alice wants to send Bob secure data. She requires an encryption key.
She can establish a secret key with Bob, over a public medium, this way:
Alice chooses a new random x3 value of the same order of magnitude as x2.
She uses Bob's g and p values, leaving her with g, x3, p.
x3 must be kept secret.
4. Alice calculates a public key x4 = g ^ x3 (mod p).
She sends this to Bob over a public medium (g, x4, p). Bob aleady knows the values of g and p, since they are of his choosing. This can be a validation step - the values must match.
[ EVE INTERCEPTS ]
5. Alice generates the encryption key x5 = x2 ^ x3 (mod p)
Bob generates the encryption key x5 = x4 ^ x1 (mod p).
Alice and bob are now in possession of the same secret key. Eve intercepts all exchanges, but cannot (unless she is NSA!) derive the key value.
How does it work? To use an analogy from Simon Singh's The Code Book:
Say that keys are paint, in 3-pint tins. Alice and Bob agree on a public key - one pint of yellow paint. They each pick a secret color. Bob mixes one pint of yellow with 1 pint of his secret color, and sends this to Alice.
Alice mixes one pint of yellow with her secret color, and sends this to Bob.
Then Alice adds a pint of her secret color to Bob's tin, and Bob adds a pint of his secret color to Alice's tin.
Both tins are now the same color.
Eve can intercept the tins as they pass to and fro, she can even know that the public key is a pint of yellow. But she cannot determine the secret color because mixing paint is a one-way function.
Test Case (ALL NUMBERS IN HEX)
Follow this test case to see it working - note that in the real world, keys of 1000 bits or more would be used.
The symbol => refers to the result of calculating g ^ x (mod p). g, p are carried over.
g=3 x1=9A2E p=10001 (Bob's private key, reused)<br />
=> g=3 x2=C366 p=10001 (Bob's public key, published, reused)<br />
<br />
g=3 x3=4C20 p=10001 (Alice's once-off random key, using Bob's g, p)<br />
=> g=3 x4=6246 p=10001 (Alice publishes this to Bob)<br />
<br />
g=C366 x1=4C20 p=10001 (Alice calculates x2 ^ x3 (mod p))<br />
=> x5=DED4<br />
<br />
g=6246 x4=9A2E p=10001 (Bob calculates x4 ^ x1 (mod p))<br />
=> x5=DED4
Alice and Bob have both arrived at the same value: DED4. This is the key! Alice encrypts the data using this secret key, and sends the encrypted data to Bob, along with the public value x4, which Bob uses to calculate the key. Eve cannot take advantage of this information due to the one-way function g^x(mod p).
Web Services Secure Exchange Example
The following schematic shows how DHM key exchange could be used in a distributed environment, say between Web Services.
Note: x is the private key on each side. This is not exchanged. p is the public key which is exchanged.
ALICE (CLIENT) BOB (SERVER)
--------------------- ---------------------
b = acquire_dh_key(bob) -> get_dh_public( return p; )
x = make_dh_private(b)
p = make_dh_public(b,x)
c = make_dh_crypt(b,x)
encrypt_data(c)
send_data_and_key(bob,p,data) -> c = make_dh_crypt(p,x)
decrypt_data(c)
In this way, one request is made to determine the server's public key, another is made to transfer the encrypted data along with the public info required for the server to calculate the encryption key. If the server's public key is known/cached, then the data can be sent using a single method-call each time. It is up to Alice to select a random message key (x) each time data is sent.
Since encryption keys are not reused, security is enhanced.
Implementations
Be aware that you will likely write flaws into your encryption code if you implement it all yourself. If possible, use a service from an established CSP (Crypto Service Provider). The CryptoAPI on Win32 supports creating and calculating DH keys, so take a look around and see what use you can make of existing code, even if it's just the secure random number generators. .NET supports various key exchange mechanisms, but they rely on asymetric algorithms such as RSA to keep the actual key safe whilst in transit.
DH key exchange never transmits the actual encryption key. This is what makes it useful, and well suited to a distributed environment. Use a proper encryption algorithm like Rijndael (AES), but derive and transmit the key using DH mechanisms.
One possible implementation is to use a simple XML framework to transmit the data/key package, possibly similar to the following:
<br />
<?xml version="1.0" ?><br />
<encryptedpackage><br />
<key>NK89FNOF8LNKASDFW0934LNF09VNOECR3M089DFCMFHE7823JRS==</key><br />
<data>FGKMSDFVCFN879EC89SDFASDFUHNOGS7834RMIUSHDF78T3BOLKJ34289=</data><br />
</encryptedpackage><br />
Key and Data values are base64 encoded for embedding in an XML document.
Happy coding.
Caractacus
www.caradoc.co.za
Ah, yes, I thought so.
|
|
|
|
|
Thanks for the post. CP could do with a bit more in the way of crypto articles.
I've not looked at your source code, but I'm curious what if anything you do to mitigate small subgroup attacks? In particular, do you generate safe primes (prime p such that (p-1)/2 is also prime) or small subgroups (p-1) = kq for some integer k and prime q of length 256 bits? Absent such protections, DH key exchange can be attacked fairly easily by sending a g^x which is a member of a small subgroup.
See Practical Cryptography by Schneier and Ferguson for details.
Adam
|
|
|
|
|
Thanks for the reply. You are correct in noting that the diffie-hellman key exchange can suffer from certain types of attacks if the numbers or chosen badly. In the code I have posted it only generates 64-bit primes, and keys. Obviously this is not of a sufficient size for good security, but it serves as a demonstration of how it could be employed, and besides for general applications; for instance if someone wrote their own messenger this level of security would be adequate. I have not as yet generated "safe" primes, but it would be very simple to test this, and generate ones that are safe - I will modify my code shortly to encompass that (cheers  ). There is further trouble with diffie-hellman key exchange in that it suffers the man-in-the-middle attack which can only be resolved by use of digital signatures for authenticity checking.
I am looking into generating larger primes, and keys (i.e. 256-bit, and so on), but since the largest type you can have in c in __int64, I'd have to write my own number representation and calculation functions, do you have any suggestions of how this can be done?
When I find a way of representing and calculating in larger values, I will repost the code, and also add the "safe" prime checking, that way it should be of a good security level. I've read that 128-bit keys can be broken fairly trivially - do you know what of 256-bit or 512-bit (ignoring export controls for now!)?
Anyway, thanks for the post (it's nice to see some people on CP that take an interest in Cryptography).
Best Regards,
Lee Griffiths
|
|
|
|
|
MrLeeGriffiths wrote:
Thanks for the reply. You are correct in noting that the diffie-hellman key exchange can suffer from certain types of attacks if the numbers or chosen badly. In the code I have posted it only generates 64-bit primes, and keys. Obviously this is not of a sufficient size for good security, but it serves as a demonstration of how it could be employed, and besides for general applications; for instance if someone wrote their own messenger this level of security would be adequate.
I don't think 64-bit primes provide ANY security beyond the dangerous notional security that comes from "using encryption". Recall that the difficulty of brute-forcing x given g^x mod p distills to the computation of discrete logs in a finite field. There exist algorithms for this purpose which are sub-exponential; see the seminal work by Lenstra, Verheul [click the "PDF" link to view the document itself. Given the approximate algorithmic complexity of computing a discrete log over a finite field, a 64-bit prime is easily breakable on commodity hardware.
MrLeeGriffiths wrote:
There is further trouble with diffie-hellman key exchange in that it suffers the man-in-the-middle attack which can only be resolved by use of digital signatures for authenticity checking.
True, however this can be mitigated in a number of ways, depending upon the requirements and thread model of the application. For example, if both sides can pre-share their public keys with eachother, or the client knows the server's public key depending upon requirements, MiTM can be mitigated, albeit at increased management cost.
MrLeeGriffiths wrote:
I am looking into generating larger primes, and keys (i.e. 256-bit, and so on), but since the largest type you can have in c in __int64, I'd have to write my own number representation and calculation functions, do you have any suggestions of how this can be done?
I recently finished writing an arbitrary precision integer math library for my company [I assure you, I had valid reasons for not reusing existing libs], and having done that I can assure you that you'd be well-advised to find an open source bignum library instead 
Libtommath is a decent bignum library written by the infamous crypto curmudgeon Tom St. Dennis of sci.crypt fame. MIRACL is a more comprehensive bignum library, which includes plenty of stuff you don't need for DH, but it is well-optimized and well-understood. Myriad other libs exist, including the bignum impl "bn" in the OpenSSL source tree (personally I don't like this one, as it's pretty well obfuscated, however it is good enough for the OpenSSL team...).
MrLeeGriffiths wrote:
When I find a way of representing and calculating in larger values, I will repost the code, and also add the "safe" prime checking, that way it should be of a good security level. I've read that 128-bit keys can be broken fairly trivially - do you know what of 256-bit or 512-bit (ignoring export controls for now!)?
I urge you to avoid the fallacy of comparing asymmetric cipher key sizes (DH, RSA, etc) with those of symmetric ciphers (DES, AES, etc). A 256-bit AES key is very secure; a 256-bit DH key is laughably insecure.
Having said that, Schneier and Ferguson (I also urge you to read and memorize Practical Cryptography, or failing that, Handbook of Applied Cryptography, which can be downloaded off the Web) recommend prime modulus lengths of at least 2048 bits. However, in practice, the key size you need depends upon what you are protecting; if you're using DH to exchange an 80-bit SKIPJACK key, or a 64-bit DES key, you may be able to get away with DH keys roughly equivalent in difficulty to an 80- or 64-bit symmetric key; if you're using AES-256, then equivalently-difficult DH will run about 15k bits, which obviously is untenable.
Recently I've done a bit of work with Elliptic Curve Cryptography, which is a family of asymmetric ciphers based on the mathematics of elliptic curves. Scalar multiplication of a point on a curve distills to the DLP, however without any known subexponential attack. Therefore, a 15k-bit DH key is (very, very roughly) equivalent in difficulty using known techniques as a 512-bit ECC key.
Practical Crypto doesn't have much to say about ECC; Certicom has a fair bit of ECC material (Scott Vanstone, a co-founder of Certicom, has done seminal work in the realm of EC and EC-based crypto), and the IEEE P1363 crypto std also has a decent bit of material.
Hope this helps.
Adam
|
|
|
|
|
Hi,
I should thank both of you for all these informations.
I am currently working on implementing a schema for the undeniable signature between two ipaqs on Pocket PC 2002, as a development tool I am using Embedded Visual C++ 3.0
I need to use big prime numbers (512 bits in average) and __int64 integers are not enough, I also need the miller-rabin primality test.
I was looking for some libraries written in C++ to generate big prime number for my algorithm that can work in an Pocket PC, but so far I did not find any,
If anyone has an idea on how to do that and which tools to use, I would be very greatuful.
Marouane
|
|
|
|
|
I would suggest finding out about LINT (Large INTeger). There should be plenty of references for it on the internet, it's essentially a big toolkit for working with very massive integers, and it also has functions like the Miller-Rabin primality test, generation of prime numbers, and all of the useful things you need to do key exchange and encryption.
Although I do remember that perhaps it isn't open source, so I would HIGHLY recommend purchasing the book "Cryptograhpy in C and C++" by Michael Welschenbach. The LINT stuff is most definitely in there - check it out at
Cryptography in C and C++, by Michael Welschenbach
That book along with its companion CD should do everything you need.
Hope this helps,
Good luck.
P.S. If you would like to work together in making a good solid encryption library I would be happy to do so. That goes for anyone else reading this also - drop me an email.
|
|
|
|
|
Hi,
Thanks a lot for your help, I found the book and the CD, there is indeed all I need to implement my algorithm.
However since I am working on Windows 3.0 for PocketPC 2002, I could not yet add the library to my project. Actually, many files are not present in the windows CE development environment, like istream.h, time.h and so on...
So I added the missing files to the project and it finally compiles, but there are still some linking problems, I don t know if it is possible for the LINT library to work on Windows CE, but I will try again and again...
Maybe you have an idea about this...
It would be interesting to work on a encryption library, but I would like to know why you wanna make a new one since there many others existing already.
For now I don t have the time to do it (deadlines...) but maybe in the future.
Anyway thank you for you help.
Have a good one
Marouane
|
|
|
|
|
Well as for time.h, I don't think you really need this do you - unless it's used in a random number generator. The only way I could help is for you to send me what you already have (you can of course remove anything confidential). As for the encryption project - I would not neccesarily like to invent my own encryption, just a library with everything from key exchange to implementing current encryption standards (AES etc). I would also like to work on channel blocking between API calls.
Anyway if you'd like to send me your code, I'd be happy to spend a little time trying to help you out - I remember programming for the PocketPC a while back and it lacked many of the functions and API calls you come to expect and rely on with standard Windows - so I know the annoying feeling!
|
|
|
|
|
In addition to Westerbach's LINT, there are plenty of bignum and RM primarity impls around. When I wrote my embedded crypto library, I found the bignum library in OpenSSL to be of some use, as was libtommath, a somewhat simpler library by Tom St. Dennis. I'd also point out the CryptoAPI in PPC 2k2; it provides an implementation of the major symmetric and asymmetric ciphers, all exposed via a hard-to-use and confusing API
btw, I found Westerbach's book and code to be somewhat wanting; the only reason _Cryptography in C and C++_ is of any value is the utter absence of any comparable books. In particular, the translation from German to English resulted in somewhat incoherent prose, which doesn't go well with the obtuse maths.
Adam
|
|
|
|
|
Adam Nelson wrote: written by the infamous crypto curmudgeon Tom St. Dennis of sci.crypt fame
TSD has nearly ruined sci.crypt - and the spam bots are feasting on the remains...
|
|
|
|
|
Jeffrey Walton wrote: TSD has nearly ruined sci.crypt - and the spam bots are feasting on the remains...
Hehe. I stopped reading sci.crypt years ago. The SNR was just too damned low.
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
