Diffie Hellman Question
in [Cryptography]
|
Prev: Public & Private Key
Next: Encryption & Authentication
From: Res on 17 Dec 2009 10:39 Not a cryptography expert, so please bear with me. I am trying to use Diffie Helman to solve an authenticated communication problem rather than an encryption problem. Bob needs to send some instructions to Alice. The instructions are very important for Alice so that she can figure out what to do next. However, first she has to make sure that the instructions really came from Bob. They cannot use regular forms of authentication & hence I am trying to use DH to solve this issue. Taking a basic algorithm to clarify terms so that further explanation is clear. Alice & Bob are going to use a prime (P) & a base (G). Alice generates Secret Key a & Bob generates Secret key b Alice sends Bob A = (G^a) mod P Bob sends Alice B = (G^b) mod P Alice computes S = (B^a) mod P Bob computes S = (A^b) mod P Bob takes instructions "Please do task XYZ at time TT with MM" Bob encrypts this using S & sends it to Alice. Now, in my use case, - Mallory intercepting Bob's B or Alice A when they are sent to each other & subtituting it with a different one is not a problem for me. This is fully prevented by other ways - i.e. Mallory cannot substitute anything during the initial phase. - Bob & Alice do not mutually authenticate each other - this is not possible for me. So integrity of the message is very important for me. Currently, I solve this by decrypting the message at Alice end's & make sure it follows a particular pattern. I do not want Mallory to be able to change the message to "Please do task XYZ at time T1 with N" or "Please do task ABC at time TT with MM". - Ideally Mallory should not be able to decrypt & read the instructions - but for me that this relatively less important than Mallory substituting it with his own instructions. - My maximum session duration is somewhere between a few minutes to 1 day. i.e. Alice & Bob do the initial DH thing but the actual instructions may be sent by Bob to Alice upto 24 hours after they arrive at the session key. - Only 1 instruction is sent per session (the plain text instruction may be 20-30 characters long). Considering these use cases - how should go about chosing the size/lengths of P, G, a & b. 1) The Wikipedia page on DH says G need to be large at all - it's usually 2 or 5. I am assuming the 2 or 5 here refers to the actual number G rather than the length of the number G. Considering this, can Alice & Bob both pre-agree that they will always use 5 as G till the end of time - any disadvantages in this over everything agreeing upon a new value of G. 2) Can P also be hardcoded at both Alice & Bob's end or is it better to use a new P each time? If I have to do a new P each time, what is the way to figure out how long P should be? I would like P to be as short as possible without compromising security heavily if I cannot hardcode P at both ends. 3) How long should a & b be? What are the considerations here for my usecase. If anyone can help with these questions it would be great.
From: Joseph Ashwood on 18 Dec 2009 03:40 "Res" <res(a)pk.com> wrote in message news:hgdjc3$1f4$1(a)news.eternal-september.org... > Not a cryptography expert, so please bear with me. Not a problem. > - Bob & Alice do not mutually authenticate each other - this is not > possible > for me. So integrity of the message is very important for me. Currently, I > solve this > by decrypting the message at Alice end's & make sure it follows a > particular > pattern. I do not want Mallory to be able to change the message to > "Please do task XYZ at time T1 with N" or "Please do task ABC at time TT > with MM". Bad idea. What prevents Mallory from repeating instructions? Many other issues, I'll just cover the fix later. > Considering these use cases - how should go about chosing the size/lengths > of > P, G, a & b. > > 1) The Wikipedia page on DH says G need to be large at all - it's usually > 2 or 5. > I am assuming the 2 or 5 here refers to the actual number G rather than > the length > of the number G. > Considering this, can Alice & Bob both pre-agree that they will always use > 5 as G > till the end of time - any disadvantages in this over everything agreeing > upon a new > value of G. There's nothing gained in changing G, as long as it is a generator the difficulty is the same. If G isn't a generator then the system is very weak. Just make sure it's a generator. > 2) Can P also be hardcoded at both Alice & Bob's end or is it better to > use a new P > each time? A single P of 2048 bits is good for a long time. > 3) How long should a & b be? What are the considerations here for my > usecase. a & b should be long enough that they are harder to figure out then to solve the discrete logarithm. Since you're not an expert, go with half the length of P. Now about the way it should be implemented, you're actually using the incomplete tool. You want DSA with ElGamal. Since your instructions are only 30 characters long, I'll be using the shared value directly instead of building a symmetric key from it. If your instructions grow in length change this immediately. Bob and Alice exchange long term public keys Alice_Pub.{A,P,G,Q} Bob_Pub.{B,P,G,Q} BOB: INST = {Time & Date, Instruction to Alice} K = Random number, same length as Alice_Pub.P X = Alice_Pub.A^K mod Alice_Pub.P STK = Alice_Pub.G^K mod Alice_Pub.P C = INST XOR X R&S = DSA(SHA-512, INST, Bob_Priv} This is the step that requires Q Bob sends to Alice { Alice_Pub.A, Alice_Pub.P, C, STK, R&S } Alice Verify that Alice_Pub.A and Alice_Pub.P are correct X = STK^Alice_Priv mod Alice_Pub.P INST = C XOR X Verified = DSA-Verify(SHA-512, INST, Bob_Pub) If Verified = TRUE then verify INST.Time&Date is now+/-1 hour This only requires one-way communication, and semi-synchronized clocks. For a reference on this, it is similar to S/MIME. DSA is described several places I like the NIST description but that's personal preference, the SHA-512 version is not widely described, just substitute SHA-512 for SHA-1, Q needs to be 512 bits long. Joe
From: Peter Pearson on 18 Dec 2009 19:40 On Fri, 18 Dec 2009 17:01:45 +0530, Res <res(a)pk.com> wrote: > "Joseph Ashwood" <ashwood(a)msn.com> wrote in message > news:uAHWm.396$8e4.97(a)newsfe03.iad... >> >> A single P of 2048 bits is good for a long time. > > This is a huge pain point for me. > > I have a maximum of somewhere around 8 to 10 bytes which can be > transferred from Alice to Bob (as a request). Hence my request is > essentially > going to be Alice transmitting her calculated > (g ** Random Number) mod Prime. > This means that the Prime cannot be a huge number like you suggest. By using the equivalent elliptic-curve system, you can get the sizes of the quantities down to 400 bits or so. If you're really limited to 10 bytes, I don't believe any public-key system will save you. I'm sorry to say the unwelcome guild-member thing, but if it's important that this system be secure against an intelligent and resourceful adversary, you really need the committed involvement of someone well experienced in the field. There are too many subtle mistakes to make, too many unconscious assumptions, for a casual design approach to stand any good chance of success. -- To email me, substitute nowhere->spamcop, invalid->net.
From: Res on 18 Dec 2009 22:10 "Peter Pearson" <ppearson(a)nowhere.invalid> wrote in message news:7p2lnbF6joU1(a)mid.individual.net... > On Fri, 18 Dec 2009 17:01:45 +0530, Res <res(a)pk.com> wrote: >> "Joseph Ashwood" <ashwood(a)msn.com> wrote in message >> news:uAHWm.396$8e4.97(a)newsfe03.iad... >>> >>> A single P of 2048 bits is good for a long time. >> >> This is a huge pain point for me. >> >> I have a maximum of somewhere around 8 to 10 bytes which can be >> transferred from Alice to Bob (as a request). Hence my request is >> essentially >> going to be Alice transmitting her calculated >> (g ** Random Number) mod Prime. >> This means that the Prime cannot be a huge number like you suggest. > > By using the equivalent elliptic-curve system, you can get > the sizes of the quantities down to 400 bits or so. If you're > really limited to 10 bytes, I don't believe any public-key > system will save you. Peter, I am really not using DH for secure communication here. Hence my question whether a smaller prime number will do? I am not really worried about whether my message can be deciphered. My big concern is whether Mallory can craft a message to send to Alice - my understanding is that even I take a prime which much smaller, I can prevent - I am just trying to validate that. Anyway, I will look with elliptic-curve system. > > I'm sorry to say the unwelcome guild-member thing, but if > it's important that this system be secure against an > intelligent and resourceful adversary, you really need the > committed involvement of someone well experienced in the > field. There are too many subtle mistakes to make, too > many unconscious assumptions, for a casual design approach > to stand any good chance of success.
From: Paul Rubin on 19 Dec 2009 04:16
"Res" <res(a)pk.com> writes: > Peter, I am really not using DH for secure communication here. > Hence my question whether a smaller prime number will do? It will not do. The security comes from the large size of the prime. Why do you want to use DH at all? Why not a shared secret key? The benefit of public key is when there are a large number of communicating parties, or when strangers want to talk to each other. If it's just two parties and they know each other, then use secret keys. |