Gammon Software Solutions forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

Entire forum
MUSHclient
Lua
How to do AES encryption with Lua and MUSHclient

Home \| Users \| Search \| FAQ
Username:	Register forum user name
Password:	Forgotten password?

(New message)

Subject:	How to do AES encryption with Lua and MUSHclient
Name:	Your forum user name. Register forum user name
Password:	Your forum password. Forgotten password?
Message:	[quote=Nick Gammon] How to share a secret key I mentioned earlier the problem of sharing a secret key for use with symmetrical encryption, where you might be using an insecure channel. There is a solution to this, called the Diffie-Hellman Key Exchange Protocol. Basically this works by having each party generate a secret number (which they keep secret). They then generate a "public key" by doing this calculation: [code] public = g ^ private (mod p) [/code] That is, a generator (2 is a possible good choice) is raised to the power of the private key, modulus a large prime number p. The two parties exchange their public keys. Now they can each find a shared number by doing this calculation: [code] shared = other_public_key ^ my_private_key (mod p) [/code] For example, given a generator of 2, and a prime number: Prime number = 1012885251643 ("EBD4AA663B" in hex) Generator = 2 Alice generates a secret key = 79C68E818 (eg. by hashing a randomly chosen phrase) Alice works out her public key by doing this: [code] print (aes.dh ("2", "79C68E818", "EBD4AA663B" )) --> 7D458DBEF3 [/code] Alice sends this number (7D458DBEF3) to Bob. Meanwhile, Bob generates a secret key = 49560AEC2 Bob works out his public key by doing this: [code] print (aes.dh ("2", "49560AEC2", "EBD4AA663B" )) --> 7D8A6551EE [/code] Bob sends this number (7D8A6551EE) to Alice. Alice can now work out the shared key by using Bob's public key (7D8A6551EE) and her secret key (79C68E818): [code] print (aes.dh ("7D8A6551EE", "79C68E818", "EBD4AA663B" )) --> 317261C804 [/code] Bob can also work out the shared key using Alice's public key (7D458DBEF3) and his secret key (49560AEC2): [code] print (aes.dh ("7D458DBEF3", "49560AEC2", "EBD4AA663B" )) --> 317261C804 [/code] Notice how at the end of this session, both Alice and Bob have arrived at the same shared secret (317261C804). This can now be used by both of them for encrypting messages to each other. The strength of this system is based on the problem of working out what the exponent must have been in the original calculation. In practice, larger prime numbers are needed, otherwise an adversary to simply do an exhaustive search to find the key. One method I have found of generating large prime numbers is to obtain GPG (Gnu Privacy Guard) and type this: [code] gpg --gen-prime 1 1024 [/code] [mono] Output: BA0BB972EED88B2B2D8FB3BAB587CFA9FC5811DAE457C88BADB8690DB5D494EC6D91D6 B29F59EEECB42E4494A48F072AB61A490562F7E631D768E986EF56DE17BBE19BB8FC94F6EF07C1 5409427CA726C885E68502ABED8C63B9BBBF4E1568E4C8032E43C257CA4413E98B701CA4F8BD1C 9B61BE26014073244EF552FD386B8B [/mono] That was a 1024-bit prime number. However see caveat below - the prime number is supposed to have the property that (p-1)/2 is also prime. That particular prime does not have that property. I am now using the prime number recommended for the DNS system in RFC 2539. To make this work in practice, I found a C implementation of the Diffie-Hellman at this page: http://www.cypherspace.org/adam/rsa/dh-in-C.html That version was very compact, and designed as a stand-alone program. The version below has been pretty-printed up a bit, and designed to interface with Lua. I made a separate file in the aeslib project (dh.c) however you could simply add this code to the existing file given earlier in this post. [code]----- #include "lua.h" #include "lauxlib.h" #include <string.h> #define MAX_BYTES 1024 unsigned char prime\[MAX_BYTES\], generator\[MAX_BYTES\], exponent\[MAX_BYTES\], result\[MAX_BYTES\]; /* bytes = number of bytes in prime + 1 / static int n, v, d, z, bytes; static void a (unsigned char x, unsigned char * y, int o) { d = 0; for (v = bytes; v--;) { d += x\[v\] + y\[v\] * o; x\[v\] = d; d = d >> 8; } } static void s (unsigned char * x) { for (v = 0; (v < bytes - 1) && (x\[v\] == prime\[v\]);) v++; if (x\[v\] >= prime\[v\]) a (x, prime, -1); } static void r (unsigned char * x) { d = 0; for (v = 0; v < bytes;) { d \|= x\[v\]; x\[v++\] = d / 2; d = (d & 1) << 8; } } static void M (unsigned char * x, unsigned char * y) { unsigned char X\[MAX_BYTES\], Y\[MAX_BYTES\]; memcpy (X, x, bytes); memcpy (Y, y, bytes); memset (x, 0, bytes); for (z = bytes * 8; z--;) { if (X\[bytes - 1\] & 1) { a (x, Y, 1); s (x); } r (X); a (Y, Y, 1); s (Y); } } static void fromhex (char x, unsigned char y) { memset (y, 0, bytes); for (n = 0; x\[n\] > 0; n++) { for (z = 4; z--;) a (y, y, 1); x\[n\] \|= 32; y\[bytes - 1\] \|= x\[n\] - 48 - (x\[n\] > 96) * 39; } } static void output (lua_State * L, unsigned char * x) { char buff \[MAX_BYTES * 2 + 1\]; char * p = buff; for (n = 0; !x\[n\];) n++; for (; n < bytes; n++) p += sprintf (p, "%c%c", 48 + x\[n\] / 16 + (x\[n\] > 159) * 7, 48 + (x\[n\] & 15) + 7 * ((x\[n\] & 15) > 9)); lua_pushstring (L, buff); } /* dh generator exponent prime / int dh (lua_State L) { unsigned char p \[MAX_BYTES * 2\], g \[MAX_BYTES * 2\], e \[MAX_BYTES * 2\]; const unsigned char * generatorText; const unsigned char * exponentText; const unsigned char * primeText; /* get generator / generatorText = luaL_checkstring (L, 1); if ((strlen (generatorText) / 2) > (MAX_BYTES - 1)) luaL_error (L, "generator too long"); strcpy (g, generatorText); / get exponent / exponentText = luaL_checkstring (L, 2); if ((strlen (exponentText) / 2) > (MAX_BYTES - 1)) luaL_error (L, "exponent too long"); strcpy (e, exponentText); / get prime / primeText = luaL_checkstring (L, 3); if ((strlen (primeText) / 2) > (MAX_BYTES - 1)) luaL_error (L, "prime too long"); strcpy (p, primeText); if (strlen (exponentText) > strlen (primeText)) luaL_error (L, "exponent length > prime length"); if (strlen (generatorText) > strlen (primeText)) luaL_error (L, "generator length > prime length"); // bytes in prime number bytes = ((strlen (primeText) + 1) / 2) + 1; fromhex (g, generator); fromhex (e, exponent); fromhex (p, prime); memset (result, 0, bytes); result\[bytes - 1\] = 1; for (n = bytes 8; n--;) { if (exponent\[bytes - 1\] & 1) M (result, generator); M (generator, generator); r (exponent); } output (L, result); return 1; } [/code]----- You also need to add the dh function to the list of the functions exported to Lua: [code] /* table of operations */ static const struct luaL_reg aeslib \[\] = { // CBC encrypting {"encrypt", encrypt}, {"decrypt", decrypt}, // Diffie-Hellman {"dh", dh}, #ifdef TEST {"test", test}, #endif {NULL, NULL} }; [/code] I do not think this code would be subject to any export restrictions, it is simply C code to raise a number to a power and take the modulus of the result. The code on its own cannot be used to encrypt messages, it simply lets you establish a shared secret. Once this is successfully compiled, you can make a test for it. I did this test in the Immediate window of MUSHclient: ----- [mono] -- Diffie-Hellman Key Exchange -- See: http://www.cypherspace.org/adam/rsa/dh-in-C.html -- this took 29 seconds to run on my PC assert (package.loadlib ("aeslib.dll", "luaopen_aes")) () generator = "2" -- see RFC 4419 - "It is recommended to use 2 as generator" -- Prime number, got from RFC 2539 (also recommends 2 as the generator) prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" .. "8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D" .. "F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6" .. "F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF" .. "FFFFFFFF" -- 1024 bits Alice_secret = utils.hash ("Alice chooses some secret phrase that is her private key") Alice_secret = string.sub (Alice_secret, 1, #prime - 1) Alice_public = aes.dh (generator, Alice_secret, prime) print ("Alice secret key = ", Alice_secret) print ("Alice public key = ", Alice_public) -- work out the public key Bob sends to Alice Bob_secret = utils.hash ("Bob has a secret phrase we worked out from a book") Bob_secret = string.sub (Bob_secret, 1, #prime - 1) Bob_public = aes.dh (generator, Bob_secret, prime) print ("Bob secret key = ", Bob_secret) print ("Bob public key = ", Bob_public) -- work out the shared secret Shared_secret_A = aes.dh (Alice_public, Bob_secret, prime) print ("Shared secret - method A = ", Shared_secret_A) Shared_secret_B = aes.dh (Bob_public, Alice_secret, prime) print ("Shared secret - method B = ", Shared_secret_B) -- check the same assert (Shared_secret_A == Shared_secret_B) x = aes.encrypt ("Nick Gammon", Shared_secret_A) y = aes.decrypt (x, Shared_secret_A) print (y) --> Nick Gammon [/mono] ----- As noted in the code, this isn't the fastest algorithm in the world - it takes 29 seconds to run on my PC. However exchanging secret keys is something you don't do every minute. Also, the test above does the calculations for both parties (Alice and Bob), when in practice they would each do half of it. The output of the above test was: [mono] Alice secret key = 79c68e818a0c4d84f8c68d7904897200dfa488f2 Alice public key = 855F0FE034691F3B3D3B0FAE03A498D3820E6F50 CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F 423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3 B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3 5279BDAC1073AC94F82370EDC4A4A0AB5A9C Bob secret key = 49560aec25e73db6e2154f53c7c7b9f666b0d533 Bob public key = 74C1BA20B83E794F3243CCA924C48088EA7AA598E6 8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0 1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03 429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5 5B6CC0A236C3337885A110FB0DDFD6057F Shared secret - method A = A1E21E54817DDA58306CE8CA32CADB20 25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72 1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376 6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1 71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06 Shared secret - method B = A1E21E54817DDA58306CE8CA32CADB20 25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72 1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376 6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1 71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06 Nick Gammon [/mono] In practice, Alice would send a message (eg. an email) to Bob, saying: [mono] generator = "2" prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08 8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6 F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF FFFFFFFF" my_public_key = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50 CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F 423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3 B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3 5279BDAC1073AC94F82370EDC4A4A0AB5A9C" [/mono] Bob would use the same generator and prime, but make his own secret key, and then reply with: [mono] my_public_key = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6 8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0 1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03 429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5 5B6CC0A236C3337885A110FB0DDFD6057F" [/mono] Now they are both in a position to calculate the shared key, and use that to encrypt messages to each other. You can see from the test that both Alice and Bob end up with the same shared key. Of course, in practice, you would change the secret keys (Alice_secret and Bob_secret) to be something that only you know. One way would be to roll dice, look up words randomly in a book, get a bingo game, that sort of thing. For more information, search the web for "Diffie-Hellman" - you will find thousands of pages describing it, and various comments about it. According to the web page cited earlier: The time to calculate a modular exponent is roughly proportional to the cube of the number of bits, so if a 1024-bit number takes 5 minutes, a 2048-bit number will take 40 minutes, and a 4096-bit number would take about 5 hours. I found in my case that whilst using a 1024-bit prime number the above test took 29 seconds to run, with at 2048-bit prime number it took about 4 minutes. A larger prime number is certainly more secure, but the time taken to generate the public and shared keys is somewhat longer. However, as I said before, you only need to do this once per shared key you need to establish, it might not bother you if it takes an hour to work out the shared key. For more security you probably need a larger secret key (the hash algorithm only generates a 160-bit hash), you might consider using the sha256 hash to generate a longer hash. [/quote] Message to be posted (in English, please).
Forum codes:	Check this if your message uses 'forum codes' or templates (auto-detected for new posts). Forum codes Templates

Save this message ...

Subject review (reverse sequence)

Pages: 1 2 3

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date

Mon 16 Aug 2010 03:48 AM (UTC) [ quote ]

Amended on Mon 16 Aug 2010 05:55 AM (UTC) by Nick Gammon

Message

There is a way of doing modular exponentiation with the bc library alone. In particular:


-- converts a hex string into a big number
function hex_to_bignum (h)
  local result = bc.number (0)
  local c, n
  assert (not string.match (h, "%X")) -- must be in hex
  for i = 1, #h do
    c = string.sub (h, i, i)  -- pull out digit
    n = tonumber (c, 16)      -- convert base-16 (hex) to decimal
    result = result * 16 + n  -- previous result 16 larger, then add in this digit
  end -- for
  
  return result
end -- function hex_to_bignum 

-- See: http://en.wikipedia.org/wiki/Modular_exponentiation
-- (Right-to-left binary method)

function modular_pow (base, exponent, modulus)
  local old_digits = bc.digits (0)  -- working with integers
  local result = bc.number (1)

  base = bc.number (base)
  exponent = bc.number (exponent)
  modulus = bc.number (modulus)
  
  while not bc.iszero (exponent) do
    if not bc.iszero (bc.mod (exponent, 2)) then
      result = bc.mod (result * base, modulus)
    end -- if
    exponent = exponent / 2
    base = bc.mod (base * base, modulus)
  end -- while
  
  bc.digits (old_digits)  -- back to old number of digits
  return result
end -- function modular_pow

Applied to the earlier example, it ran quite quickly:



generator = 2

prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" ..
"8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D" ..
"F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6" ..
"F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF" ..
"FFFFFFFF" -- 1024 bits


print ("prime (dec) = ", hex_to_bignum (prime))

Alice_secret = utils.hash ("Alice chooses some secret phrase that is her private key")
Alice_secret = string.sub (Alice_secret, 1, #prime - 1)

print ("Alice_secret (hex) =", Alice_secret)
print ("Alice_secret (dec) =", hex_to_bignum (Alice_secret))

Alice_public = modular_pow (generator, hex_to_bignum (Alice_secret), hex_to_bignum (prime))

print ("result = ", Alice_public)

expected = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50" ..
"CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F" .. 
"423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3" ..
"B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3" ..
"5279BDAC1073AC94F82370EDC4A4A0AB5A9C"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Alice_public == hex_to_bignum (expected))


-- work out the public key Bob sends to Alice
Bob_secret = utils.hash ("Bob has a secret phrase we worked out from a book")
Bob_secret = string.sub (Bob_secret, 1, #prime - 1)

print ("Bob_secret (hex) =", Bob_secret)
print ("Bob_secret (dec) =", hex_to_bignum (Bob_secret ))

Bob_public = modular_pow (generator, hex_to_bignum (Bob_secret), hex_to_bignum (prime))

print ("result = ", Bob_public )

expected = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6" .. 
"8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0" ..
"1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03" ..
"429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5" ..
"5B6CC0A236C3337885A110FB0DDFD6057F"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Bob_public == hex_to_bignum (expected))


-- work out the shared secret
Shared_secret_A = modular_pow (Alice_public, hex_to_bignum (Bob_secret), hex_to_bignum (prime))

print ("Shared secret - method A = ", Shared_secret_A)

Shared_secret_B = modular_pow (Bob_public, hex_to_bignum (Alice_secret), hex_to_bignum (prime))

print ("Shared secret - method B = ", Shared_secret_B)

expected = "A1E21E54817DDA58306CE8CA32CADB20" ..
"25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72" ..
"1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376" ..
"6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1" ..
"71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06"

print ("expected = ", hex_to_bignum (expected))

print ("expected == actual?", Shared_secret_B == hex_to_bignum (expected))

Results (omitting the long numbers):



expected == actual? true

expected == actual? true

expected == actual? true

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date Thu 19 Apr 2007 07:20 AM (UTC) [ quote ]

Message

Some compile notes for Lua 5.1.2.

I copied a few .h files from the Lua distribution, plus the Lua 5.1 DLL, as follows:


aes.h     lua.h       luaconf.h   sha256.h
aes.c     aeslib.c    lauxlib.h   lua5.1.dll  sha256.c

(Copied files in bold)

In the file aeslib.c I changed the line:


#define LUA_API __declspec(dllexport)

to read:


#define LUA_BUILD_AS_DLL
#define LUA_LIB

I then compiled like this (under Cygwin):



gcc -mno-cygwin -shared -o aeslib.dll aes.c sha256.c aeslib.c lua5.1.dll

This gave a 44 Kb file: aeslib.dll

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date

Mon 02 Oct 2006 08:16 AM (UTC) [ quote ]

Amended on Mon 02 Oct 2006 08:32 AM (UTC) by Nick Gammon

Message

I eventually found a program to test for primality on this page:

http://primes.utm.edu/links/programs/large_arithmetic/

I downloaded the "factor.exe" program, and ran it against the number mentioned in RFC 2539 above. Converted to decimal that number is:



17976931348623159077083915679378745319786029604875601170644442368419

71802161585193689478337958649255415021805654859805036464405481992391

00050792877003355816639229553136239076508735759914822574862575007425

30207744771258955095793777842444242661733472762929938766870920560605

0270810842907692932019128194467627007

Testing that gave this result:



factor -d310 17976931348623159077083915679378745319786029

60487560117064444236841971802161585193689478337958649255415021805654859805036464

40548199239100050792877003355816639229553136239076508735759914822574862575007425

30207744771258955095793777842444242661733472762929938766870920560605027081084290

7692932019128194467627007

this number is prime!

I then calculated (p-1)/2, namely:



89884656743115795385419578396893726598930148024378005853222211842098

59010807925968447391689793246277075109028274299025182322027409961955

00253964385016779083196147765681195382543678799574112874312875037126

51038723856294775478968889212221213308667363814649693834354602803025

135405421453846466009564097233813503

According to the factor program, that is also prime, which is what we want.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date Mon 02 Oct 2006 07:07 AM (UTC) [ quote ]

Message

I am having trouble confirming whether the prime number generated by GPG is suitable for use with this algorithm.

For security it might be wise to use the 1024-bit prime number mentioned in RFC 2539 (just remove the spaces to use it):



FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381 FFFFFFFF FFFFFFFF

According to various sources the prime number should not only be prime, but (p-1)/2 should also be prime. I am not sure of an easy way of calculating that for an arbitrary prime number

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by

Nick Gammon Australia (18,772 posts)

bio Forum Administrator

Date

Mon 02 Oct 2006 01:44 AM (UTC) [ quote ]

Amended on Mon 02 Oct 2006 06:27 AM (UTC) by Nick Gammon

Message

I should point out that the Diffie-Hellman protocol is vulnerable to the "man in the middle" attack. This is where a 3rd party intercepts both sides of the communication, pretending to be Bob (to Alice) and Alice (to Bob). If he can manage to do that, then the Alice and Bob are really sharing a secret with the middleman, who then reads all their messages, re-encrypts with his own key, and forwards it on.

However it is much harder to do the man-in-the-middle attack than to simply eavesdrop on network traffic. Monitoring network traffic is pretty trivial, but setting up the man-in-the-middle attack involves spoofing IP addresses and a lot more mucking around.

A potential way of avoiding this attack is to "sign" the messages that are forwarded (the public keys). You can sign messages with PGP or GPG, if you want to install those.

Or, you could confirm the public keys by hashing them and sending the hash (or simply the keys themselves) by another means (eg. snail mail, post on a forum page, that sort of thing).

You obviously also do not "confirm we got the same secret key" by sending a copy to each other. ;)

The way to confirm you arrived at the same key is to encrypt a small message (eg. "test") with the derived secret key, and send a copy to each other, to make sure it decrypts to that word at the other end.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date

Mon 02 Oct 2006 01:08 AM (UTC) [ quote ]

Amended on Mon 02 Oct 2006 08:38 AM (UTC) by Nick Gammon

Message

How to share a secret key

I mentioned earlier the problem of sharing a secret key for use with symmetrical encryption, where you might be using an insecure channel.

There is a solution to this, called the Diffie-Hellman Key Exchange Protocol.

Basically this works by having each party generate a secret number (which they keep secret).

They then generate a "public key" by doing this calculation:


public = g ^ private (mod p)

That is, a generator (2 is a possible good choice) is raised to the power of the private key, modulus a large prime number p.

The two parties exchange their public keys.

Now they can each find a shared number by doing this calculation:


shared = other_public_key ^ my_private_key (mod p)

For example, given a generator of 2, and a prime number:

Prime number = 1012885251643 ("EBD4AA663B" in hex)
Generator = 2

Alice generates a secret key = 79C68E818 (eg. by hashing a randomly chosen phrase)

Alice works out her public key by doing this:


print (aes.dh ("2", "79C68E818", "EBD4AA663B" )) --> 7D458DBEF3

Alice sends this number (7D458DBEF3) to Bob.

Meanwhile, Bob generates a secret key = 49560AEC2

Bob works out his public key by doing this:


print (aes.dh ("2", "49560AEC2", "EBD4AA663B" )) --> 7D8A6551EE

Bob sends this number (7D8A6551EE) to Alice.

Alice can now work out the shared key by using Bob's public key (7D8A6551EE) and her secret key (79C68E818):


print (aes.dh ("7D8A6551EE", "79C68E818", "EBD4AA663B" )) --> 317261C804

Bob can also work out the shared key using Alice's public key (7D458DBEF3) and his secret key (49560AEC2):


print (aes.dh ("7D458DBEF3", "49560AEC2", "EBD4AA663B" )) --> 317261C804

Notice how at the end of this session, both Alice and Bob have arrived at the same shared secret (317261C804).

This can now be used by both of them for encrypting messages to each other.

The strength of this system is based on the problem of working out what the exponent must have been in the original calculation.

In practice, larger prime numbers are needed, otherwise an adversary to simply do an exhaustive search to find the key.

One method I have found of generating large prime numbers is to obtain GPG (Gnu Privacy Guard) and type this:


gpg --gen-prime 1 1024



Output: BA0BB972EED88B2B2D8FB3BAB587CFA9FC5811DAE457C88BADB8690DB5D494EC6D91D6

B29F59EEECB42E4494A48F072AB61A490562F7E631D768E986EF56DE17BBE19BB8FC94F6EF07C1

5409427CA726C885E68502ABED8C63B9BBBF4E1568E4C8032E43C257CA4413E98B701CA4F8BD1C

9B61BE26014073244EF552FD386B8B

That was a 1024-bit prime number. However see caveat below - the prime number is supposed to have the property that (p-1)/2 is also prime. That particular prime does not have that property. I am now using the prime number recommended for the DNS system in RFC 2539.

To make this work in practice, I found a C implementation of the Diffie-Hellman at this page:

http://www.cypherspace.org/adam/rsa/dh-in-C.html

That version was very compact, and designed as a stand-alone program. The version below has been pretty-printed up a bit, and designed to interface with Lua.

I made a separate file in the aeslib project (dh.c) however you could simply add this code to the existing file given earlier in this post.


#include "lua.h"
#include "lauxlib.h"

#include <string.h>

#define MAX_BYTES 1024

unsigned char prime[MAX_BYTES], 
              generator[MAX_BYTES], 
              exponent[MAX_BYTES], 
              result[MAX_BYTES];

/* bytes = number of bytes in prime + 1 */
static int n, v, d, z, bytes;

static void a (unsigned char * x, unsigned char * y, int o)
{
  d = 0;
  for (v = bytes; v--;)
    {
      d += x[v] + y[v] * o;
      x[v] = d;
      d = d >> 8;
    }
}

static void s (unsigned char * x)
{
  for (v = 0; (v < bytes - 1) && (x[v] == prime[v]);)
    v++;
  if (x[v] >= prime[v])
    a (x, prime, -1);
}

static void r (unsigned char * x)
{
  d = 0;
  for (v = 0; v < bytes;)
    {
      d |= x[v];
      x[v++] = d / 2;
      d = (d & 1) << 8;
    }
}

static void M (unsigned char * x, unsigned char * y)
{
  unsigned char X[MAX_BYTES], Y[MAX_BYTES];
  memcpy (X, x, bytes);
  memcpy (Y, y, bytes);
  memset (x, 0, bytes);
  for (z = bytes * 8; z--;)
    {
    if (X[bytes - 1] & 1)
      {
        a (x, Y, 1);
        s (x);
      }
    r (X);
    a (Y, Y, 1);
    s (Y);
    }
}

static void fromhex (char *x, unsigned char * y)
{
  memset (y, 0, bytes);
  for (n = 0; x[n] > 0; n++)
    {
    for (z = 4; z--;)
      a (y, y, 1);
    x[n] |= 32;
    y[bytes - 1] |= x[n] - 48 - (x[n] > 96) * 39;
    }
}

static void output (lua_State * L, unsigned char * x)
{
char buff [MAX_BYTES * 2 + 1];
char * p = buff;

  for (n = 0; !x[n];)
    n++;
  for (; n < bytes; n++)
    p += sprintf (p, "%c%c", 48 + x[n] / 16 + (x[n] > 159) * 7,
      48 + (x[n] & 15) + 7 * ((x[n] & 15) > 9));
lua_pushstring (L, buff);
}

/* dh generator exponent prime */

int dh (lua_State * L)
{
unsigned char p [MAX_BYTES * 2], 
              g [MAX_BYTES * 2], 
              e [MAX_BYTES * 2];

const unsigned char * generatorText;
const unsigned char * exponentText;
const unsigned char * primeText;

  /* get generator */
  generatorText = luaL_checkstring (L, 1);
  if ((strlen (generatorText) / 2) > (MAX_BYTES - 1))
    luaL_error (L, "generator too long");
  strcpy (g, generatorText);

  /* get exponent */
  exponentText = luaL_checkstring (L, 2);
  if ((strlen (exponentText) / 2) > (MAX_BYTES - 1))
    luaL_error (L, "exponent too long");
  strcpy (e, exponentText);

  /* get prime */
  primeText = luaL_checkstring (L, 3);
  if ((strlen (primeText) / 2) > (MAX_BYTES - 1))
    luaL_error (L, "prime too long");
  strcpy (p, primeText);

  if (strlen (exponentText) > strlen (primeText))
    luaL_error (L, "exponent length > prime length");

  if (strlen (generatorText) > strlen (primeText))
    luaL_error (L, "generator length > prime length");
  
  // bytes in prime number
  bytes = ((strlen (primeText) + 1) / 2) + 1;

  fromhex (g, generator);
  fromhex (e, exponent);
  fromhex (p, prime);
  memset (result, 0, bytes);
  result[bytes - 1] = 1;
  for (n = bytes * 8; n--;)
    {
    if (exponent[bytes - 1] & 1)
      M (result, generator);
    M (generator, generator);
    r (exponent);
    }
  output (L, result);
  return 1;
}

You also need to add the dh function to the list of the functions exported to Lua:


/* table of operations */
static const struct luaL_reg aeslib [] = 
  {
  // CBC encrypting
  {"encrypt", encrypt},
  {"decrypt", decrypt},

  // Diffie-Hellman
  {"dh", dh},

#ifdef TEST
  {"test", test},
#endif

  {NULL, NULL}
  };

I do not think this code would be subject to any export restrictions, it is simply C code to raise a number to a power and take the modulus of the result. The code on its own cannot be used to encrypt messages, it simply lets you establish a shared secret.

Once this is successfully compiled, you can make a test for it. I did this test in the Immediate window of MUSHclient:



-- Diffie-Hellman Key Exchange



-- See: http://www.cypherspace.org/adam/rsa/dh-in-C.html



-- this took 29 seconds to run on my PC



assert (package.loadlib ("aeslib.dll", "luaopen_aes")) ()



generator = "2" -- see RFC 4419 - "It is recommended to use 2 as generator"



-- Prime number, got from  RFC 2539 (also recommends 2 as the generator)



prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08" .. 

"8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D" ..

"F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6" ..

"F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF" ..

"FFFFFFFF" -- 1024 bits



Alice_secret = utils.hash ("Alice chooses some secret phrase that is her private key")



Alice_secret = string.sub (Alice_secret, 1, #prime - 1)



Alice_public = aes.dh (generator, Alice_secret, prime)



print ("Alice secret key = ", Alice_secret)

print ("Alice public key = ", Alice_public)



-- work out the public key Bob sends to Alice

Bob_secret = utils.hash ("Bob has a secret phrase we worked out from a book")

Bob_secret = string.sub (Bob_secret, 1, #prime - 1)



Bob_public = aes.dh (generator, Bob_secret, prime)



print ("Bob secret key = ", Bob_secret)

print ("Bob public key = ", Bob_public)



-- work out the shared secret

Shared_secret_A = aes.dh (Alice_public, Bob_secret, prime)



print ("Shared secret - method A = ", Shared_secret_A)



Shared_secret_B = aes.dh (Bob_public, Alice_secret, prime)



print ("Shared secret - method B = ", Shared_secret_B)



-- check the same

assert (Shared_secret_A == Shared_secret_B)



x = aes.encrypt ("Nick Gammon", Shared_secret_A)

y = aes.decrypt (x, Shared_secret_A)

print (y) --> Nick Gammon

As noted in the code, this isn't the fastest algorithm in the world - it takes 29 seconds to run on my PC. However exchanging secret keys is something you don't do every minute. Also, the test above does the calculations for both parties (Alice and Bob), when in practice they would each do half of it.

The output of the above test was:



Alice secret key =  79c68e818a0c4d84f8c68d7904897200dfa488f2

Alice public key =  855F0FE034691F3B3D3B0FAE03A498D3820E6F50

CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F

423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3

B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3

5279BDAC1073AC94F82370EDC4A4A0AB5A9C

Bob secret key =  49560aec25e73db6e2154f53c7c7b9f666b0d533

Bob public key =  74C1BA20B83E794F3243CCA924C48088EA7AA598E6

8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0

1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03

429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5

5B6CC0A236C3337885A110FB0DDFD6057F

Shared secret - method A =  A1E21E54817DDA58306CE8CA32CADB20

25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72

1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376

6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1

71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06

Shared secret - method B =  A1E21E54817DDA58306CE8CA32CADB20

25DE23417DAE8B684F7CA4E0EF040C89730AE58096B3F83C4D7E819B5E72

1FC16AE5FEA96317D41507C5C4CE9C68BDABC33518DB367ECDCD5CC86376

6AE9812A9EABECAACB6995493FF0AE1F6AB74FCAD631440FA0DA158791A1

71EF49FC669DE64EF307FB9DA4730CE8880EE623CF06

Nick Gammon

In practice, Alice would send a message (eg. an email) to Bob, saying:



generator = "2"



prime = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08 

8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6D

F25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6

F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFF

FFFFFFFF" 



my_public_key = "855F0FE034691F3B3D3B0FAE03A498D3820E6F50

CFAE9C1DD24D7351CFF64D21168A6A6D1CFE4C3D0DF681C29E01475E136F

423A5AEF091DA5BB8B9F41059C93A41F3B97091582C41C7F4D68A73E69D3

B3A5DCEF9C82806424A149549BDCB858EB7CAC55733F17F4B2D4B8FE96C3

5279BDAC1073AC94F82370EDC4A4A0AB5A9C"

Bob would use the same generator and prime, but make his own secret key, and then reply with:



my_public_key = "74C1BA20B83E794F3243CCA924C48088EA7AA598E6

8A42B3218048C70DF6340C84EB97D15766CA539E2D9F18BA1F8DB406E3A0

1BCCA394B91200C8C16402FCEC5037B46B6FAD73048F9A8B168A420ECE03

429C21C52B19EEF5257BADF9637A0853F75371A5126D11A31B38EE6599A5

5B6CC0A236C3337885A110FB0DDFD6057F"

Now they are both in a position to calculate the shared key, and use that to encrypt messages to each other. You can see from the test that both Alice and Bob end up with the same shared key.

Of course, in practice, you would change the secret keys (Alice_secret and Bob_secret) to be something that only you know. One way would be to roll dice, look up words randomly in a book, get a bingo game, that sort of thing.

For more information, search the web for "Diffie-Hellman" - you will find thousands of pages describing it, and various comments about it.

According to the web page cited earlier: The time to calculate a modular exponent is roughly proportional to the cube of the number of bits, so if a 1024-bit number takes 5 minutes, a 2048-bit number will take 40 minutes, and a 4096-bit number would take about 5 hours.

I found in my case that whilst using a 1024-bit prime number the above test took 29 seconds to run, with at 2048-bit prime number it took about 4 minutes.

A larger prime number is certainly more secure, but the time taken to generate the public and shared keys is somewhat longer. However, as I said before, you only need to do this once per shared key you need to establish, it might not bother you if it takes an hour to work out the shared key.

For more security you probably need a larger secret key (the hash algorithm only generates a 160-bit hash), you might consider using the sha256 hash to generate a longer hash.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date

Thu 23 Dec 2004 11:41 PM (UTC) [ quote ]

Amended on Thu 23 Dec 2004 11:42 PM (UTC) by Nick Gammon

Message

Version 3.61 adds the ability to seed the Mersenne Twister with a table of seeds, rather than a single number, like this:


t = { 1234, 5678, 9876, 5432 }
MtSrand (t) -- seed with table of seeds

Conceivably you could get a reasonably long sequence of pseudo-random numbers by:

Generate a genuinely-random sequence of seeds manually (eg. with dice, using the Bingo game).
Use that to seed the Mersenne Twister algorithm, as in the example above.
Take the output from the Mersenne Twister and hash it as described earlier.

The resulting sequence should be pretty hard for someone to predict (as they wouldn't have any way of guessing the starting seeds), and by choosing enough seed values (say, 20 of them) the PRNG generator should be in a state that would be hard to establish.

Then by hashing the output you make it virtually impossible to deduce what the state of the PRNG generator is.

However, I am not a cryptographic expert, there may be a flaw in that plan. :)

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by Nick Gammon Australia (18,772 posts) bio Forum Administrator

Date Thu 23 Dec 2004 10:48 PM (UTC) [ quote ]

Message

Just out of curiosity, I tried to see what would happen if I generated the random numbers, and then hashed them. If the hashing has problems you would expect a worse result on the ent test than the non-hashed version. However it went quite well.


function randtest ()

f = io.open ("mt.txt", "wb")
MtSrand (5679)
for i = 1, 627000 do
  s = ""

  -- generate 32 random numbers
  for j = 1, 32 do
    s = s .. string.char (MtRand () * 256)
  end -- j loop

  s = utils.sha256 (s)	-- hash it
  f:write (s)
end -- i loop
f:close ()	
print "Done"

end -- randtest

The code above generates a 20,064,000 byte file, which is roughly the same size as the earlier samples. This uses the sha256 hash (256 bit SHA hash) which is in the latest version of MUSHclient.

Running that file through ent gives:




Entropy = 7.999991 bits per byte.



Optimum compression would reduce the size of this 20064000 byte file by 0 percent.



Chi square distribution for 20064000 samples is 257.00, and randomly would exceed this value 50.00 percent of the times.



Arithmetic mean value of data bytes is 127.4930 (127.5 = random).

Monte Carlo value for Pi is 3.142032297 (error 0.01 percent).

Serial correlation coefficient is -0.000304 (totally uncorrelated = 0.0).

The value for pi seems slightly better, and the other figures are certainly acceptable.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by

Poromenos Greece (1,037 posts)

bio

Date

Thu 23 Dec 2004 09:29 PM (UTC) [ quote ]

Message

True, but I might want to say "The admin is an asshole." I don't want it to appear in plaintext, and it's not like the admin is going to try and crack XOR (as simple as it may be) to see that I called him names...

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!

top

Posted by

Nick Gammon Australia (18,772 posts)

bio Forum Administrator

Date

Thu 23 Dec 2004 07:33 PM (UTC) [ quote ]

Message

Interesting point. The problem with XOR is that it isn't at all secure. I used to think that XORing against a password was pretty smart, but I now see from reading various books about encryption that it is easily broken.

Most people would know that a simple substitution cypher (A=M, B=N etc.) can be broken by simply counting letter frequencies.

However if you have an XOR cypher especially with a short password (eg. BORIS), all you have done is make it into 5 substitution cyphers. (eg. every 5th letter is transformed by B, the next 5 by O, the next 5 by R and so on). So you break up the message into batches of 5, and do a frequency count on each batch. I think there are even automated tools to do that.

My point is, if it is secret enough (or private enough) to encrypt in the first place, you may as well choose a system that can't easily be broken, otherwise there isn't a huge amount of point.

It is possible to get overconfident, and exchange data (eg. credit card numbers) that you normally wouldn't because you think "it's safe, I have encryption".

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by

Poromenos Greece (1,037 posts)

bio

Date

Thu 23 Dec 2004 01:51 PM (UTC) [ quote ]

Message

I agree 100% with Nick. I DO mean MC, obviously sensitive data should be encrypted, but it's not like I exchange corporate secrets chatting in the MUD. Still, everyone has (and should excercise) their right to privacy. I'm all for PGP, GPG, etc, but I don't NEED them for 99% of my emails. Anyway, I was just pointing out that AES is much more secure than anyone will ever need while MUDding.

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!

top

Posted by

Nick Gammon Australia (18,772 posts)

bio Forum Administrator

Date

Wed 22 Dec 2004 11:40 PM (UTC) [ quote ]

Message

He probably means in MUSHclient?

I agree that most of us expect that commerce sites are secure, however my personal experience has been that practically no-one is interested in swapping (say) encrypted emails with me.

However, having easy access to encryption (say, as a scripting option) may encourage its use. I think the idea of encrypted chat sessions has some merit, especially if you are on a network that might have people eavesdropping on packets.

I think there is a lot to be said for trying to increase one's privacy. It is not that you intend to do anything wrong, however you would be outraged if you knew the government opened (say) every piece of mail you sent and read it "just in case". However that is probably what is happening to a lot of messages that fly around on the Internet.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

Posted by

David Haley USA (3,881 posts)

bio Moderator

Date

Wed 22 Dec 2004 11:08 PM (UTC) [ quote ]

Message

Quote:
I don't think that 99.9999% of the people have any use for that strong encryption though

Speak for yourself - I can see many reasons why electronic commerce and voting should be as cryptographically secure as possible. :) Who exactly are you talking about?

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org

top

Posted by

Poromenos Greece (1,037 posts)

bio

Date

Wed 22 Dec 2004 10:30 PM (UTC) [ quote ]

Message

Yes, or hash multiple outputs for better security. I don't think that 99.9999% of the people have any use for that strong encryption though, Rijndael is way more secure than anything I need (hell, XOR is more secure than I need).

Vidi, Vici, Veni.
http://porocrom.poromenos.org/ Read it!

top

Posted by

Nick Gammon Australia (18,772 posts)

bio Forum Administrator

Date

Wed 22 Dec 2004 09:39 PM (UTC) [ quote ]

Message

The Mersenne Twister docs suggets you hash the output if you want to use it for cryptographic purposes. Then you can't deduce where in the generator sequence you are.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

18,575 views.

This is page 1, subject is 3 pages long: 1 2 3

Reply to this subject Start a new subject Refresh page

Go to topic: Search the forum

top

Comments to: Gammon Software support
Forum RSS feed ( http://www.gammon.com.au/rss/forum.xml )