Reply
Member
Curious Hazelnut
Posts: 195
0 Kudos

Encryption in LSL for prim to prim communications

[ Edited ]

I've recently been playing with the LSL functions that were clearly added for the purpose of building encrypted communications. As I went through them I found what I think are significant flaws in the design of the functions we are provided with. I'm wondering if there are others who have played with trying to implement practical encryption solutions in LSL?

I am aware of alternatives using trusted back-channels for communications (sending through a web server, using llemail) but my goal is more of an intellectual exercise.

So, first, the LSL functions we are provided for encryption, what are they for, and why are they wrong?

llModPow() is a somewhat odd function that is really only useful when implementing a public key cryptographic algorythm. The problem is that public key cryptosystems (such as RSA) are really only "secure" when they use a key size of 1024 bits or greater and ModPow() works with 32bit integers. Thus I have yet to find a use for this function.

llSHA1String() seams to be here for two purposes. First, as a message authentication tool and secondly as a key generation tool. These are both why SHA1 was created in the first place. The problem with this tool is that its output is in HEX. This is fine for message authentication but not practical if you are using it to generate one time pads (more on this later).

llXorBase64StringsCorrect() also really only serves one useful purpose and that is to implement one time pads. The problem with it is that it repeats the 2nd string passed to it if the 1st string is longer than the second string. As a chaining algroythim this is a bad idea (especially when using one time pads). Why is the repeating so bad? Because, a one time pad can only be used one time if it is to remain secure. Reuse of the same pad dramatically reduces the effectiveness of it to the point where even the LSL Wiki talks about how insecure it is.

llStringToBase64() and llIntegerToBase64() are here so that we can convert our strings and integers into Base 64 encoding, presumably for input into the above mentioned llXorBase64StringsCorrect().

What am I getting at with the above? Well simply put the obvious way to "encrypt" a string using the available LSL tools is with one time pads as follows:

string base_64_data = llStringToBase64(data);

string base_64_pad = llStringToBase64(pad);

string encrypted_data = llXorBase64StringsCorrect(base_64_data, base_64_pad);

 and, that would actually be incredibly secure if pad and data are exactly the same size (or pad is bigger).


This just leaves the problem of generating a PAD. And this is where SHA comes in. We share a secret (password) in advance and add to it some always changing value to generate the PAD with SHA1String. I've seen this implemented in commercial software that was vetted as "secure" by a standards organization. Of course, those get broken quite regularly but at least it's a starting point. We can think about generating our pad as:

string pad = SHA1String(password + salt);

but that has pad encoded in HEX when it is really a 160bit (20 byte) integer. We do have llIntegerToBase64(), maybe we can add that ...

string hex_pad = SHA1String(password + salt);

string pad = "0x" + llIntegerToBase64(hex_pad);

 Had to add the "0x" in front to let the LSL interpreter know the integer is encoded in HEX, not decimal. Otherwise it would truncate at the first letter it ran into. Unfortunately, this doesn't actually work. Our hex_pad is 160 bits but the size of an integer in LSL is 32 bits. So the pad is pretty much always going to be -1 (I tested this) because when a string is converted to an integer, if the resulting number exceeds the maximum size a 32-bit integer can be, it is set to -1.

So ... now we have to break our 16 bit hex encoded integer into 5 parts. I won't bother with the code at this point because it has yet another problem to overcome.

Base 64 encoding was created to convert binary data into printable characters (to get around transmission issues with some early protocols). In simple terms, it converts 3 bytes into 4 bytes but guarantees that those 4 bytes are all printable characters. So, if the size of your data is not divisble by 3, then there are 1 or 2 "extra" characters needed as filler. To note this, Base 64 encoding uses the equal sign (=) as a marker. You will see two equal signs at the end of the Base 64 encoded integer because a 32 bit integer is 4 bytes (hence add two useless bytes to get the multiple of 3).

What does all this mean for encryption? Well, if we take our 160 bit HEX encoded number, we need to break it into 5 equal parts, each of which can be represeted as a single integer and encoded. BUT we can't simply concatenate them because each of them have 2 equal signs indicating the unused bytes.

On top of that we haven't solved the "salt" issue to actually generate our pad.

If you've actually made it through my rant and understood it, have you got any thought comments or observation on encryption using LSL?

 

Member
Ela Talaj
Posts: 807
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Curious Hazelnut - view message

Messages between objects never leave the SL servers grid, regardless if the objects are in the same region or not. In the latter case "email" between objects is actually implemented via instant messaging and therefore is even more secure than instant messaging between avatars, because those do leave the grid to end up in the viewer. The same applies to objects being in the same region and communicating via llRegionSayTo().

One should probably start thinking about secure communications when messages do leave the grid, which includes HTTP to off-world backends, like web servers etc but, to think of it, the gain of intercepting such communications is pretty miniscule as compared to effort.

Elegant Solutions by The Gold Club
Honored Member
Ciaran Laval
Posts: 4,101
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Ela Talaj - view message


Ela Talaj wrote:

One should probably start thinking about secure communications when messages do leave the grid, which includes HTTP to off-world backends, like web servers etc but, to think of it, the gain of intercepting such communications is pretty miniscule as compared to effort.


How about http communications between inworld objects? I've been playing with this and there's nothing I'm doing so far that requires secure comms for my testing, I wish there was an object DNS but that's a different issue.

 

Member
Ela Talaj
Posts: 807
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Ciaran Laval - view message

I don't really know how they impemented http between objects, that is whether it is a bona fide http via the cloud or some shortcut within the grid. It is a very interesting question.

Elegant Solutions by The Gold Club
Qie Niangao
Posts: 4,598
Registered: ‎02-25-2009
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Ela Talaj - view message

Well, I can't think why http packets between objects would get routed outside the LL internal network. The URLs are FQDNs in lindenlab.com, so if they're leaking out, there's a routing error somewhere.

For basic transmission integrity of external traffic, we get SSL just for the asking, with llRequestSecureURL() (not that I've ever actually needed it).

I assume the OP had other uses of encryption in mind.

Member 16
Member
16
Posts: 2,853
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Curious Hazelnut - view message


Curious Hazelnut wrote:

Base 64 encoding was created to convert binary data into printable characters (to get around transmission issues with some early protocols). In simple terms, it converts 3 bytes into 4 bytes but guarantees that those 4 bytes are all printable characters. So, if the size of your data is not divisble by 3, then there are 1 or 2 "extra" characters needed as filler. To note this, Base 64 encoding uses the equal sign (=) as a marker. You will see two equal signs at the end of the Base 64 encoded integer because a 32 bit integer is 4 bytes (hence add two useless bytes to get the multiple of 3).

What does all this mean for encryption? Well, if we take our 160 bit HEX encoded number, we need to break it into 5 equal parts, each of which can be represeted as a single integer and encoded. BUT we can't simply concatenate them because each of them have 2 equal signs indicating the unused bytes.

 


i just pick up on this part

one way is can fill your data before encrypting so length is divisible by 3 (or whichever length)

say

length = 3 then fill 2 random bytes length = 5

length = 2 then fill 0 random bytes length = 2

length = 1 then fill 1 random bytes length = 2

can then use/append "random" number modulus 3 as a last byte to know how many to strip after decrypt

or can fill them to front. or even use password as seed for prng to make some "random" position insertions into data for the fillers

when use "random" fillers then can always make length(data) = length(pad) 

Member
Curious Hazelnut
Posts: 195
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to Ciaran Laval - view message

RE: HTTPS

I did actually consider HTTPS communications as an option. When reading the wiki page about it, I noticed that the server URL for the receiving prim changes periodically (like for region reboots).

RE: my reasons

My discussion here was mostly academic because the idea of secure communications fascinates me (I've read quite a bit on the subject). It did come about as the result of an actual project. I'm fiddling with a sort of role play HUD for SL. Something to compliment the combat huds I've seen. My thought (and I've seen other systems that do this too) is to add farming/mining/gathering and production/selling as elements that can be used within an RP environment. Or, if you prefer, add the "grinding" elements of traditional MMOs as an optional add-on to SL role play. The challenge is that any sort of system that would support this would be very open to cheating by replaying information being passed from object to hud. So, encrypt the communications. But that means quick encryption and low-lag communications (which pretty much limits me to llSay() and friends).

Member
Curious Hazelnut
Posts: 195
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to 16 - view message


16 wrote:

Curious Hazelnut wrote:

Base 64 encoding was created to convert binary data into printable characters (to get around transmission issues with some early protocols). In simple terms, it converts 3 bytes into 4 bytes but guarantees that those 4 bytes are all printable characters. So, if the size of your data is not divisble by 3, then there are 1 or 2 "extra" characters needed as filler. To note this, Base 64 encoding uses the equal sign (=) as a marker. You will see two equal signs at the end of the Base 64 encoded integer because a 32 bit integer is 4 bytes (hence add two useless bytes to get the multiple of 3).

What does all this mean for encryption? Well, if we take our 160 bit HEX encoded number, we need to break it into 5 equal parts, each of which can be represeted as a single integer and encoded. BUT we can't simply concatenate them because each of them have 2 equal signs indicating the unused bytes.

 


i just pick up on this part

one way is can fill your data before encrypting so length is divisible by 3 (or whichever length)

say

length = 3 then fill 2 random bytes length = 5

length = 2 then fill 0 random bytes length = 2

length = 1 then fill 1 random bytes length = 2

can then use/append "random" number modulus 3 as a last byte to know how many to strip after decrypt

or can fill them to front. or even use password as seed for prng to make some "random" position insertions into data for the fillers

when use "random" fillers then can always make length(data) = length(pad) 


If you notice the original statement, I need to convert one 160 bit integer represented in HEX. The only way I can see to convert it to something usable by llIntegerToBase64() is to break it into 5 32-bit integers. So the question becomes how to re-combine them for use in a subsequent call to llXorBase64....

Good idea except where the dummy data can't be allowed to be predictable (like when used as an encryption key or part of a one-time-pad).

 

Member 16
Member
16
Posts: 2,853
0 Kudos

Re: Encryption in LSL for prim to prim communications

[ Edited ]

Reply to Curious Hazelnut - view message

yes sorry

i kinda missed that you had a specific requirement. was just more thinking about the general case

+

have a look at this wiki example

http://wiki.secondlife.com/wiki/LlXorBase64StringsCorrect#Cryptography

bc you got a 160bit hex value then can mod this to suit

like to start can convert the 160bit hex value into a hex string before encrypt and after decrypt

Member 16
Member
16
Posts: 2,853
0 Kudos

Re: Encryption in LSL for prim to prim communications

Reply to 16 - view message

ps. i just add here for you and anyone else interested

am not sure what you mean by not predictable when a cipher is encoded only with XOR

by example here is the table for 2 bits

0:0=0 0:1=1 0:2=2 0:3=3 
1:0=1 1:1=0 1:2=3 1:3=2 
2:0=2 2:1=3 2:2=0 2:3=1 
3:0=3 3:1=2 3:2=1 3:3=0

 here is the countertable

1:0=1 1:1=0 1:2=3 1:3=2 
0:0=0 0:1=1 0:2=2 0:3=3 
3:0=3 3:1=2 3:2=1 3:3=0
2:0=2 2:1=3 2:2=0 2:3=1

can see that is only ever 4 result sets reachable by XOR out of factorial(4) 24 total. bc XOR is a bijective method. can trivial break this encoding

for the cipher to be unpredictable then need a method to choose/encode from all possible 24 sets

is same same for factorial(power(2, 160)) scaled up

is why XOR is most always used in combination with some other method

+

on a 160bit cipher then i probably use a feistel network mixer with say 4 or more rounds. a feistel mixer algo output is provably indistinguishable from "random" after 4 rounds. here is a ref:

http://en.wikipedia.org/wiki/Feistel_cipher

or even easier bc is small and can easy fit in memory then a knuth (fisher-yates) shuffle

http://en.wikipedia.org/wiki/Knuth_shuffle

+

if was me then i would do this on 4bit boundaries so can mix 2 times as many hex chars than bytes. if expand the data by salt with some "random" chars as well then the mixer will hide the data better

after mixing then encrypt/encode as base64 like in the wiki example code ref in my before to transmit. reverse to decrypt/decode/demix

+

the other thing with the lsl base64 methods as shown in the wiki code example then can do rounds on that as well

some pcode:

// encode     
for rounds = 1 to 4
  secret = llXorBase64StringsCorrect(llStringToBase64(secret), llStringToBase64(pad))

// decode
for rounds = 1 to 4     
 secret = llBase64ToString(llXorBase64StringsCorrect(secret, llStringToBase64(pad)))

 this works bc XOR is a bijection like i say above. is not crypto-secure all by itself tho