Diffie-Hellman Key Exchange (peripheral: 40: too long without yielding)

Hello all,

I have been working on a secure key exchange. The framework is uses is initialized by this file (init.lua). It worked for some time, but now it gives me this:

First computer:


Second computer:






Some specifications:

Both computers run the same code; the relevant part is this function, more specifically after line 77. So why exactly do I get this error? I hope the debug messages can help you help me. The function that appears to be raising the error is when I send the message where they exchange their respective secret numbers.


Thanks to all in advance,

Creator.

I'm no expert to be fair, but some input may possibly be helpful.

From what i am aware of this error then it is that your program has been running for too long without actually doing something, like it's stuck or running an infinite loop, something along those lines.

Hope this is some help to you, if not hey ho i tried haha :')

Actually that is not the issue. Or at least it should not be. The error happens somewhere here:

if order == 1 then
  modem.transmit(AUTH_CHANNEL,KEY_EXCHANGE_PORT,mySecret)
  debugPrint("Sent my secret...") --HERE
  repeat
   event = generateEvent(os.pullEvent())
   debugPrint("Got an event: ", textutils.serialize(event))
  until event[1] == "modem_message" and event[3] == AUTH_CHANNEL and event[4] == KEY_EXCHANGE_PORT and checkDist(dist,event)
  hisSecret = event[5]
elseif order == 2 then
  repeat
   event = generateEvent(os.pullEvent())
   debugPrint("Got an event: ", textutils.serialize(event))
  until event[1] == "modem_message" and event[3] == AUTH_CHANNEL and event[4] == KEY_EXCHANGE_PORT and checkDist(dist,event)
  hisSecret = event[5]
  modem.transmit(AUTH_CHANNEL,KEY_EXCHANGE_PORT,mySecret)
  debugPrint("Sent my secret...") --HERE or here
end

The questions why is the peripheral erroring?

The peripheral isn't. It's the peripheral API.

Just made another test, the error happens for both computers after the "end" statement, at the bottom of the above code sample.

H4X0RZ, on 10 February 2016 - 09:47 PM said:

The peripheral isn't. It's the peripheral API.

I also checked the code line, and nothing seems to be wrong.

Taking a scatter gun approach:

Pull some dummy events as much as you can near where it stops.

os.queueEvent("I am a fake event") --#well not that fake
os.pullEvent()

obviously this may cause issues if you actually need these events

Apparently, it is because the BigNum needs a lot of time to process. However, I still cannot figure out what the peripheral api has to do with it. It kinda works now.

Lupus590, on 10 February 2016 - 09:49 PM said:

Taking a scatter gun approach:

Pull some dummy events as much as you can near where it stops.

os.queueEvent("I am a fake event") --#well not that fake
os.pullEvent()

obviously this may cause issues if you actually need these events

I added sleeps.

Thanks guys!

I would insert debug messages before and after line 94
Also, why not getting the "call stack" by putting some pcalls/errors at places you might assume the error?
:ph34r:/> strikes again

Added an event queue and pull just before line 94.

After adding these events, one of the computers computes the key, while the other's screen turns black.

How long is the message you are sending? Just a guess, but the modem may not be able to send it.

Here's line 40 of the peripheral API: https://github.com/alekso56/ComputercraftLua/blob/master/rom/apis/peripheral#L40

Have you tried running it again, because if I remember correctly, too long without yielding error doesn't return the erroring line, but rather the last line it tried to execute before being interrupted, and technically, this line should change if you run it again, I might be wrong, but it just makes sense to me.
Also make sure your BigNum api returns the correct numbers for exponentiation and modulo, maybe try doing the key exchange manually in the console.

Anavrins, on 11 February 2016 - 01:39 AM said:

Have you tried running it again, because if I remember correctly, too long without yielding error doesn't return the erroring line, but rather the last line it tried to execute before being interrupted, and technically, this line should change if you run it again, I might be wrong, but it just makes sense to me.
Also make sure your BigNum api returns the correct numbers for exponentiation and modulo, maybe try doing the key exchange manually in the console.

How? a lua console?

What might be the reason for it taking so long is the fact you are exponentiating first and then finding the modulus after (both on line 43 and line 96 in DH.lua):

BigNum.mt.div((base^secret),prime)

It would be quicker to write a 'powerModulus' function that takes the modulus as you go along, especially if you plan on using larger primes at some point. At a minimum, try adding a yield into the main while loop in the 'BigNum.div' function.

I wrote my own bigInteger API based on the same one you are currently using with help from the "Handbook of Applied Cryptography" (Chapter 14 is where all the multiple precision arithmetic is found). Feel free to try it out.

blunty666, on 11 February 2016 - 03:45 PM said:

What might be the reason for it taking so long is the fact you are exponentiating first and then finding the modulus after (both on line 43 and line 96 in DH.lua):

BigNum.mt.div((base^secret),prime)

It would be quicker to write a 'powerModulus' function that takes the modulus as you go along, especially if you plan on using larger primes at some point. At a minimum, try adding a yield into the main while loop in the 'BigNum.div' function.

I wrote my own bigInteger API based on the same one you are currently using with help from the "Handbook of Applied Cryptography" (Chapter 14 is where all the multiple precision arithmetic is found). Feel free to try it out.

Thanks, mate. This actually seems like a good idea! Will try it ASAP.

I looked over the code, and it seems pretty nice. One thing is bugging me however. When you queue and event, and you wait for it, maybe put the other events in a table, and when the operation is done, queue them.

Creator, on 11 February 2016 - 03:54 PM said:

One thing is bugging me however. When you queue and event, and you wait for it, maybe put the other events in a table, and when the operation is done, queue them.

That's not a bad solution, I'll have to take a look. You'd need to be careful when you had other programs running at the same time as they would end up seeing the events twice when you requeue them.

Tbh I was trying to implement RSA key exchange and the reason I didn't pursue it further was the long amount of time the calculations took. I could generate 128 bit primes no problem, but it took about a minute to do so!!!

blunty666, on 11 February 2016 - 04:08 PM said:

Creator, on 11 February 2016 - 03:54 PM said:

One thing is bugging me however. When you queue and event, and you wait for it, maybe put the other events in a table, and when the operation is done, queue them.

That's not a bad solution, I'll have to take a look. You'd need to be careful when you had other programs running at the same time as they would end up seeing the events twice when you requeue them.

Tbh I was trying to implement RSA key exchange and the reason I didn't pursue it further was the long amount of time the calculations took. I could generate 128 bit primes no problem, but it took about a minute to do so!!!

You can overwrite the local pullEvent function to keep an event for later use if the second argument is true.

blunty666, on 11 February 2016 - 03:45 PM said:

What might be the reason for it taking so long is the fact you are exponentiating first and then finding the modulus after (both on line 43 and line 96 in DH.lua):

BigNum.mt.div((base^secret),prime)

This is indeed why it is taking so long, the solution is to implement a modular exponentiation function (commonly called modexp)
for example, this psudocode from wikipedia has O(log(n)) time complexity:

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
	    if (exponent mod 2 == 1):
		   result := (result * base) mod modulus
	    exponent := exponent >> 1
	    base := (base * base) mod modulus
    return result

PixelToast, on 11 February 2016 - 07:39 PM said:

blunty666, on 11 February 2016 - 03:45 PM said:

What might be the reason for it taking so long is the fact you are exponentiating first and then finding the modulus after (both on line 43 and line 96 in DH.lua):

BigNum.mt.div((base^secret),prime)

This is indeed why it is taking so long, the solution is to implement a modular exponentiation function (commonly called modexp)
for example, this psudocode from wikipedia has O(log(n)) time complexity:

function modular_pow(base, exponent, modulus)
	if modulus = 1 then return 0
	Assert :: (modulus - 1) * (modulus - 1) does not overflow base
	result := 1
	base := base mod modulus
	while exponent > 0
		if (exponent mod 2 == 1):
		   result := (result * base) mod modulus
		exponent := exponent >> 1
		base := (base * base) mod modulus
	return result

I will look into it. Thanks! By adding a sleep after the exp operation, the code does not error anymore.