• Announcements

    • Xiola Linden

      The New Community Platform   03/21/2017

      We are still working on making adjustments and changes to the new platform. Thanks  to everyone who has been sending in feedback and filing any bugs you've encountered! 
Sign in to follow this  
Followers 0
Curious Hazelnut

Encryption in LSL for prim to prim communications

13 posts in this topic

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?

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites


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.

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites


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) 

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites


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).

 

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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=02: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))// decodefor 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

Share this post


Link to post
Share on other sites

Regarding https, yeah, it's a pain to deal with the ephemeral URLs of http server scripts. Ciaran rightly notes that a kind of DNS / registry service would make this a lot less kludgy. As is, the only alternatives I know are to use llEmail to re-negotiate comms in-world, or to go outside the LL network to an external registry server.

There are indeed other reasons for encryption. One with possible relevance to a roleplay application might be secrecy of only part of a message, while other parts can (or must) be public.

Although I use llRegionSayTo() a lot these days, confident in its ability to exclude all but the intended recipient, there is always room for bugs -- such as the recent case of an Aditi pile-on test where people ended up wearing each other's HUDs. That's just unreleased code on the test grid (and has naught to do with encryption), but... well, I wouldn't be writing any banking applications in SL just yet.

Share this post


Link to post
Share on other sites

Thanks 16, looks like I've got some reading to do. I know XOR alone is not crypto secure. That's more or less why I started this thread. To see if there were any creative solutions out there.


16 wrote:

[...]

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:

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

[...]

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

 

 

Share this post


Link to post
Share on other sites

fyi

other time i made a demo of arithmetic feistel network mixer in lsl. to generate "random" permutations for channel hoppers, gift givers, dance AOs, trivia games, etc

is here: http://community.secondlife.com/t5/General-Discussion-Forum/What-will-you-do-with-the-Advanced-Creator-Tools-Launched-Today/m-p/1630455#M73684

can see how it works and mod as you like if you want

+

just some notes

the demo only use 1 lfsr seed . for industrial use then best to use at least 3 and swap them out. so will use 3 x 31 bits instead of 1 x 31 as in the demo. just to make a longer period

also the demo use galois lfsr to make noise. but galois is actual too perfectly uniform  for crypto. so best to mod and use a mersenne type prng for that

 

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  
Followers 0