One matter upon which I have been thinking recently is the matter of Authentication between Objects within Second Life.
For many systems it is necessary for them to be able to communicate with each other only if they share a common secret - a “password” is an example, and one used here. For instance, with a combat system, a cannonball should only be able to tell a ship that it has been struck and should take damage if it is part of the same “network”, or game (though clearly Piracy is Not A Game) as the ship itself.
In cases where all items are owned by the same person this is simple - one merely checks that the owner keys, which are I believe unforgeable, are the same, using some line such as if (llGetOwnerKey(id) != llGetOwner()) return; in one’s listen() event, when hearing a command. However, when objects may be owned by pretty much anyone, this will not work, and merely having the objects communicating on an unusual channel (-894029345, say) will not provide complete security, as listening devices exist which can scan for these things.
I was thinking of something a little more secure, yet remaining in-world and not requiring awkward and slow communication with, say, a server that keeps a record of permitted owners. To this end I created a small script this afternoon which demonstrates a challenge-response system between objects.
The basic functioning works thusly: each object holds a password, and when object A wishes to instruct object B to do something, B says “Hold on a second! I don’t know who you are. We must compare passwords. But clearly we cannot do so on an open channel - anyone might be listening. Here is a random integer for you as a challenge, to use as a salt in an MD5 function.”
A hears this integer and applies that salt to the password, then says the resulted salted password again. The important point about the function llMD5String and MD5 encryption in general is that, when a string is encrypted with a particular salt, there is no practical way to return to the original string given the result. So, even if someone is listening in and hears the salted password, it is of no use in determining the original password - but B can also salt the password with the same integer and compare the two to see if the original passwords were the same.
If B manages to do this it then says “right, you seem to know the password properly, I will allow you to instruct me” and, for the next minute, allows communications from that key to act on it. A then must repeat whatever command was issued.
The above may seem a little baffling if one has never heard of this sort of thing but I dare say examination of the script may make it clearer. Contrariwise, I confess that I really do not know an awful lot about this stuff compared to the experts and would welcome comments. I have posted the script on my Scripting Colloquium for simpler discussion, but here is as good a place as any too I suppose.
16 comments
Comments feed for this article
Trackback link
http://ordinalmalaprop.com/engine/2007/10/23/secure-inworld-password-nonsense/trackback/
October 23, 2007 at 10:11 pm
Patchouli Woollahra
It makes great sense there, Ordinal. in fact, salting password hashes seems to be the new hotness. Every additional pinch of salt exponentially increases the difficulty of cracking such a hash.
Of course, it’s still not perfect. I blame entropy and the people who had so much time, they put together ‘rainbow tables’ (precompiled MD5 hashes - amazing what can be used to break an egg)
Keep going.
October 23, 2007 at 10:27 pm
Deanfred Brandeis
The password thing is nice, and I’ve used exactly this scheme to authenticate cookies before outside of SL, but in this case, it does require that all objects in the network share the same password. I can’t think of a method that would be practical in SL that would surmount this problem, though.
A system of signing small RSA keys might work. A master certificate signs all participants’ keys. Then when B challenges A with an integer, A signs it with his private key and transmits it with his public key. B then can determine that A did, indeed sign it and that A’s key was signed by the master key. Part of the problem here, though, is that small RSA keys might be able to be taken out-of-world and cracked. IIRC, encryption with small RSA keys (
October 23, 2007 at 10:49 pm
Patchouli Woollahra
There are few highly-reusable encryption schemes that are low on computational power requirements, sadly. most of them demand much more than the 16kb total made available for each LSL (sub-)process and its stored data. The problem of encryption on a tiny footprint has been a bit of a bugbear, and I don’t think it’ll be solved totally anytime soon unless that footprint gets bigger. (i.e. better mobile CPUs and storage)
October 24, 2007 at 9:27 am
Ordinal Malaprop
One advantage of communication within SL, mind you, is that the identity of both parties (i.e. key) is always known and unforgeable, at least when it is via chat or sensor or any of the other Detected events. This makes some tasks which might require security in RL trivial. The Big Red Button that destroys one’s secret underground laboratory can be protected from the hero by simply using llDetectedKey(0) == llGetOwner() on one’s touch_start() event. If only that were possible in RL, the state of Mad Science would be considerably more advanced.
October 24, 2007 at 9:23 pm
Kasumi Ghia
note: I know encryption, not LSL, so all following code is jsut pseudocode in no particular language.
1 flaw I see. (This may or may not actually be a problem in practice, but it’s easy to fix, so I see no reason not to)
I (bad guy) create an object C that starts at 1, and counts up with every attempt for A to tell it to do somwthing. I record the responces somewhere.
I then arrange for A to try to tell C to do lots of things.
Once I have a sufficient sample of responces (100% is best, but lower precentages will be usefull) I then go tell object B to do something. If B uses one of the integers I have a response to, then I sent it and I’m in. Oherwise I keep asking B till I get one.
There are variations on this that may be actually practicable in LSL. The problem is that A’s responce Is the same if it’s said by C or D, so it’s vulnerable to man-in-the-middle attacks. (ex, C asks B, gets integer, arranges for A to ask C to do something, gives it the integer that B used, then just forwards the responce to B)
You can fix this by having A’s responce include it’s key in the MD5 process.
(so instead of md5(salt.password) use md5(key.salt.password))
That way the responce is only usefull to the sender, and not some 3rd party listening in/etc.)
Or you could have B’s request be md5(key,password), integer. and have A verify that the md5 is correct before it responds. but this takes 2 more MD5 operations. , so I assume it’s less usefull.
–
-Kasumi Ghia-
October 24, 2007 at 10:06 pm
Ordinal Malaprop
Let me see. if A tells C to do something, C issues a challenge, and A will only be able to command C if A has the original password and can salt it with C’s challenge. Otherwise it will get no response.
Listening in on the channel _will_ provide different mappings from salt to salted password, yes, and if B can listen in on enough of them, every now and then it may be presented with a challenge which it knows the answer to. There are two billion different challenges, but eventually someone could build up a lot of them if sufficiently dedicated.
I _think_ that I see the point - including the key of the sender in the hash makes the hash useless for anyone but the sender, as keys can’t be forged and C, the receiver, can always tell what the key of the sender is and check whether it is right. Hm. That seems like a good addition.
October 24, 2007 at 10:27 pm
Kasumi Ghia
I’ve thought of a good example of a senario where this change is absolutly necessary.
A is a gun with the appropriate password.
B is a avatar’s target/hud/etc where you want to shoot him. (with the password)
C is my evil helper object.
I use A to shoot C (send a message to C to try to hit it)
C then passes on that same message to B (making any necessary changes in target, etc).
B responds to C with integer.
C responds to A with same integer.
A sends authentication to C.
C passes that authentication to B which responds to C with “you missed”
C is now authenticated to A.
C now shoots A repeatidly in a tight loop until C hits and A dies.
I win the game and the 100,000L$ prize :-)
–
-Kasumi Ghia-
October 24, 2007 at 10:29 pm
Kasumi Ghia
“C is now authenticated to A” should be
“C is now authenticated to B”
“C now shoots A repeatidly in a tight loop until C hits and A dies”
should be
“C now shoots B repeatidly in a tight loop until C hits and B dies”
October 24, 2007 at 11:05 pm
Ordinal Malaprop
You are quite right there. Including the key of the object as well as the password in the hash for the response should be a simple enough way to defeat that.
You see, this is why I post this sort of thing publicly, I really don’t know a lot about encryption and need other people to set me straight!
October 26, 2007 at 9:55 pm
Ordinal Malaprop
Right, yes, I have modified it now to require the object key in the hash. That should work I think.
October 27, 2007 at 9:44 am
Tyken Hightower
Using the requesting object’s key in the hash it generates to respond to the challenge isn’t entirely necessary; the important thing is that the object waiting for the response to its challenge is only listening to chatter from the key of the object which made the request in the first place.
As far as rainbow tables and issues with response prediction, use a larger key space. Instead of generating a single integer to put into the MD5 function’s integer parameter (because this integer is merely concatenated to the string input anyway!), just generate multiple integers which are directly concatenated into the string. At this point, the amount of storage space needed to generate all the possible results and the time needed to search them all becomes absurd. Either way, as long as you use a strong enough password coded into the script which can’t be found, you should still be safe.
October 27, 2007 at 9:56 am
Tyken Hightower
More specifically, by not using the challenge integer (or integers!) as the actual function parameter, you can mix it into the hidden password in a way that will be unknown to outside observers, which is what makes it harder to generate rainbow tables even in the case where the shared password string is known.
November 2, 2007 at 11:22 am
Augren Ferguson
Is it not a problem that the salt crosses the ether, then so will the salt-hashed password? If one listens in to enough of those exchanges, would it not be possible to bring the salt in relation with the password? Or am I misunderstanding something there?
Please elaborate if you would :)
November 4, 2007 at 1:38 am
Dalien Talbot
Ordinal, interesting idea. However, given that you can know the key of the object that sent the message, why not simply use that as a salt ? (As you mentioned, the identity of the sender is always known)
So, assuming A needs to command B, it takes the string “shared password | A’s key | command”, and sends the resulting the hash together with the command.
B takes the command, takes the key of A from the event, builds the string: “shared password | A’s key | command”, hashes it, and verifies the hash. If the hash is the same as the received one, it can proceed to act, otherwise it can silently drop the message.
The sniffed information will be useless for anyone else since they will have a different sender key to start with.
For the extra fanciness and to make the miscreants’ life really interesting, you can add a time-dependant pseudorandom component into the string that is being hashed, for example, md5( current_date_and_time_in_minutes | secret) - this value you can also easily recompute on the receiver side and use for the verification.
The only problem arises if the sender has sent the message just before the minute change, but it is easily tackled on the receiver by performing the two checks - for the current minute and for the previous minute. If either of them succeeds, the command is from a valid source and is acceptable.
This should be reasonably simple code and would save 1 roundtrip of message exchanges, imho :-)
November 4, 2007 at 11:25 am
Ordinal Malaprop
Augren: In practice, when combined with the key being included in with the password, it would not be practical for anyone to listen long enough to be able to get back to the original password, I believe.
Dalien: I originally put the salt in as I was not using the key as well. My instinct says that yes, sending a hash of key + password “salt-free” would be secure, as the key of the sender is always known, but I have been proved wrong on this sort of thing in the past…
November 20, 2007 at 9:33 am
Luke
Thankyou for this script I nearly lost hope of making a combat system due to security. I cant get it to work when I attach it to my avatar. Two prims on the ground each with this script will respond to each other but when I attach one of the prims to my avatar the prim on the ground will not get a responce from the attachment, but the attachment will get a response from the one on the ground. Any help greatly appreciated.