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