Implementing better encryption

Okay, I've been toiling away for the past few days working on a Mono-LSL implementation of the big-integer functions required to perform RSA encryption, basing my code on LibTomMath (a pretty standard, open-source C library). However, the general crappiness of lists is making it a rather pointless endeavour, as I'm getting the following rough times:
18.4 seconds to encrypt using 93-bit encryption.
33.4 seconds to encrypt using 124-bit encryption.
54.3 seconds to encrypt using 155-bit encryption.
129.5 seconds to encrypt using 248-bit encryption.
879.8 seconds to encrypt using 527-bit encryption.

Unfortunately 527-bits was my target, well, 512-bits is but I'm using 31-bit integers to make up my big-integers.

Even utilising Diminished Radix Reduction only, opposed to Barrett or Montgomery reductions, the times are horrifying. 14 minutes isn't exactly zippy.

The main problem is that everything you do involving lists results in copies being created, if you so much as look at a list it's probably been copied as a result. If we had arrays and/or the ability to pass-by-reference these times could be reduced significantly =(

Anyway, the point of this thread is to get some feedback on other people's efforts in the encryption arena utilising the greater speed of Mono. It seems that proper RSA encryption is still beyond our grasp, what alternatives are there? I'm likely going to investigate some work-arounds that may speed up my current implementation, mostly to see if it can be done and how much of a difference it makes (if any). I will also be looking at alternative encryption methods that may be possible to implement within LSL.

My current thoughts are to use the Diffie-Hellman algorithm to generate a shared-key on both client and server, utilising what I've already done. While slow to generate, this algorithm is allows a shared-key to be generated securely at both ends. I can then use faster symmetric-key encryption algorithms to send data back and forth. This way it should be possible to mix costly public-key encryption with faster encryption methods.

Bug LL to implement it with llCalls.

Personally, I think it's a little silly that we don't have that already - if they want to allow SL to be a business platfrom, they should provide things like this. It'd probably be about a bazillion times more efficient in C/C++, too.

Hmm, I found one such JIRA issue here:
http://jira.secondlife.com/browse/SVC-1147

However, unfortunately we have to work under the assumption that even if LL do implement it that without several big businesses on our side to apply pressure, it will take minimum of about 5 years before they do add it.

Based on how quickly scripts can do the math, asking LL to do it still may be the fastest route.

I feel for you. RSA type encryption was a pain, though somewhat fun, to do just a 31-bit version for. It could certainly be extended, even to arbitrary-sized values, but it'll be pretty crazy in LSL. You might actually consider an intermediate stage with values as small as 8 bits. It might not be great performance-wise, but it would make the logic a LOT simpler.

See /54/df/140261/1.html

If you need strong encryption... it has been done in LSL.

http://wiki.secondlife.com/wiki/XTEA_Strong_Encryption_Implementation


And it is much faster when using Mono.

My library does arbitrary sized values as I say, it can handle 512-bit (ish) with memory to spare, it just takes 14 minutes to encrypt a message =)
That time would be significantly smaller (possible a hundred times or more) if I didn't have to constantly copy lists, I've migrated to using global variables to pass parameters with less overall cost, but it's still not great as it's the manipulations themselves that cost most =(

I've now got a working implementation of AES with support for 256-bit, it should in theory support higher as well but I'll have to read-up on any changes required that I'm not aware of, as the standard may be different for larger key-sizes or something. It works very well though, and encrypts 350 character messages in around a second (possibly faster, I haven't properly benchmarked it yet), my implementation isn't yet optimal as I'm trying to get it correct first. Key expansion (setup) takes about 0.1 seconds.
The only problem therefore is getting a key for AES to use. My thinking here is to use Diffie-Hellman, an asymmetric/public-key cryptography system that allows two machines to generate the same shared-key which AES can then use. It can utilise the same library I built for RSA; set-up will take ages, but once it has a key of sufficient length AES should be sufficient to encrypt the messages. I'm unsure what to do with signing at the moment, as RSA is out of the question.

XTEA and XXTEA are both nice-simple algorithms to implement, but have documented weaknesses. I'm not sure how far I'd trust them, and it's unclear what (if anything) the LSL implementation does to circumvent them. A good solution for LSO-LSL's limited memory space, but I'm aiming for a Mono implementation.

I've posted a preliminary implementation of AES within Mono-LSL (it's too big for LSO-LSL). It's provided as an encryption "client" that you can communicate with by passing in your encryption key to "prime" it, then simply passing in any data to encrypt/decrypt.

It's pretty fast, and can support messages up to around 1.5kb in size, encoded as base64 (so about 1.1kb of actual data), and supports pretty much any key size. Optimal key size is 128, 192, or 256-bits. However, you may (if you wish) use much larger keys, but as noted it's not certain if they are actually more secure, as the state may not be large enough to properly support larger keys. Larger keys probably won't hurt, but I won't guarantee that they're more secure =)

The code, and more thorough description can be found on the page I created for it on the Second Life wiki, it's currently only available through my user-page as I'm considering it a beta implementation. Please feel free to try it!
https://wiki.secondlife.com/wiki/AES_Strong_Encryption

thank you..I see I've a lot of reading to do this week..cheers

Oh, I should also note that the implementation is not the most optimal either, I based it on the example code given on Hoozi here:
http://www.hoozi.com/Articles/AESEncryption.htm

It's therefore an almost direct implementation of the actual AES specification, when I have time I will go over it looking for optimisations. The main changes in my implementation is the addition of block numbering to reduce the chances of identical blocks resulting in identical ciphers, and to add a basic padding mechanism.
I'm also thinking to investigate adding a larger state for better supporting larger keys, but I can't predict how that will turn out, as I'm using a set of 16 integers to model the current 4 x 4 state, the next size up I think is 8 x 8 which may require too much code, since I can't use loops to manipulate the state variables.

Like a buzzard to fresh kill, I'm working on an optimized version.

Here is my optimization of lslAESKeyExpansion. Note how I've removed the dependency on lslAESGetRConByte and LSLAES_RCON. It turns out because of how the inputs for lslAESGetRConByte are calculated, regardless of key length, they always fall in the interval [1, 8]. As it turns out the bytes corresponding to those values are: [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]. It would be [1, 32] if the len could be zero but then you would get a divide by zero on the modulo.

The fact that I can simplify this aspect of the algorithm at all makes me very uneasy. That big table was there for a reason and being able to remove it makes me think it was there for deception. I'm by no means the sharpest knife in the drawer, if I were I'd be working for the NSA cracking encryption algorithms and writing new ones with back doors, to come across something like this so easily scares me.

string lslAESKeyExpansion(list keyBytes) {
    // Don't need the bit-count and the first round key is the key itself
    integer len = ((lslAESRoundKey = llDeleteSubList((lslAESRoundKey = keyBytes = []) + keyBytes, 0, 0)) != []);

    if (!len || len & 7) {
        lslAESRoundKey = [];
        return "Invalid key size, must be a multiple of 256 bits!";
    }
 
    // Calculate the number of required rounds
    lslAESRounds = len | 6;//was a "+" but we can use "|" in this case.
 
    // All others are found from previous keys
    integer i = len;
    integer x = (len | 7) << 2;//was a "+" but we can use "|" in this case.
 
    integer t = llList2Integer(lslAESRoundKey, -1);
    
    do {//x initially is always greater than i, so we use a do-while instead
        if (!(i % len)) {
            // Rotate by 1 and SubWord
            t = (   (lslAESGetSBoxByte((t >> 16) & 0xFF) << 24) | 
                    (lslAESGetSBoxByte((t >>  8) & 0xFF) << 16) | 
                    (lslAESGetSBoxByte((t      ) & 0xFF) <<  8) |
                    (lslAESGetSBoxByte((t >> 24) & 0xFF)      )
                ) ^ (0x00800000 << (i / len));
        }
        else if ((i % len) == 4) {
            // SubWord
            t = (lslAESGetSBoxByte((t >> 24) & 0xFF) << 24) | 
                (lslAESGetSBoxByte((t >> 16) & 0xFF) << 16) | 
                (lslAESGetSBoxByte((t >>  8) & 0xFF) <<  8) |
                (lslAESGetSBoxByte((t      ) & 0xFF)      );
        }
        
        // XOR k with four previous RoundKey values And add the new entries, yay!
        lslAESRoundKey = (lslAESRoundKey = []) + lslAESRoundKey + 
            (t = (t ^ llList2Integer(lslAESRoundKey, i - len)));
    } while (++i < x);
 
    return "";
}

Deception is unlikely. Speed optimization, perhaps? One table lookup vs. several computations can sometimes be faster, though only if the computations are complex enough to have to go to memory anyway....

I did some reading and code digging and I now know more about the table... not to mention fixed some bugs. As you know AES is just Rijndael with some of it's variables constrained or made constant. The "<< 2" as you know is a multiply by 4, that 4 is one of the variables that was hard coded for AES. I did some more digging and found that the "% 8" (which I had translated to "& 7" was wrong for AES, so in this revision I've changed it to a proper bounds check (I left out the "len & 1" thou). Anyway in Rijndael it was possible to configure it to use more of the table, in AES though it's trivial to optimize the table out.

I'm quite pleased with my new solution for the RCon calculation. It took a bunch of work to find a solution (it's good for [1, 12] now) that was light on operations, didn't need a branch, conditional operator, extra variable or any math duplication. The left and right shifts handle the truncation. You cannot combine them without taking on some extra math.

string lslAESKeyExpansion(list keyBytes) {
    // Don't need the bit-count and the first round key is the key itself
    integer len = ((lslAESRoundKey = llDeleteSubList((lslAESRoundKey = keyBytes = []) + keyBytes, 0, 0)) != []);

    if (len < 4 || len > 8) {
        lslAESRoundKey = [];
        return "Invalid key size, must be a multiple of 64 bits and in the range of 128 to 256 bits!";
    }
 
    // Calculate the number of required rounds
    lslAESRounds = len + 6;
    
    // All others are found from previous keys
    integer i = len;
    integer x = (len + 7) << 2;
 
    integer t = llList2Integer(lslAESRoundKey, -1);
    
    do {//x initially is always greater than i, so we use a do-while instead
        if (!(i % len)) {
            // Rotate by 1, SubWord and Nudge [0x01020408, 0x01020408, 0x1b366cd8]
            t = ((lslAESGetSBoxByte((t >> 16) & 0xFF) ^ (0x000D8080 >> (-8 ^ -(i / len)))) << 24) | 
                 (lslAESGetSBoxByte((t >>  8) & 0xFF) << 16) | 
                 (lslAESGetSBoxByte((t      ) & 0xFF) <<  8) |
                  lslAESGetSBoxByte((t >> 24) & 0xFF);
        }
        else if ((len > 6) && (i % len) == 4) {
            // SubWord
            t = (lslAESGetSBoxByte((t >> 24) & 0xFF) << 24) | 
                (lslAESGetSBoxByte((t >> 16) & 0xFF) << 16) | 
                (lslAESGetSBoxByte((t >>  8) & 0xFF) <<  8) |
                (lslAESGetSBoxByte((t      ) & 0xFF)      );
        }
        
        // XOR k with four previous RoundKey values And add the new entries, yay!
        lslAESRoundKey = (lslAESRoundKey = []) + lslAESRoundKey + 
            (t = (t ^ llList2Integer(lslAESRoundKey, i - len)));
    } while (++i < x);
 
    return "";
}

Great work and really appreciate your effort and enthusiasm Strife! I haven't time to look at it today (actually that's a lie, but I'm REALLY hungover), but I'll have a look at it tomorrow or something and in all likelihood add it to the code on the wiki-page, if it means I can get rid of another list, or significantly shrink it then great!

If there are any parts of the code that don't make complete sense, or which I've not commented and need it (there's probably a lot as I did very little commenting) then let me know and I'll explain. There are one or two things that I've changed specifically for LSL but can't now think for the life of me what they are, that is besides the main ones:
- 16 integer variables for state, since a 16-entry list would be significantly slower (llListReplaceList() *shudder*).
- Lists containing byte-data do so by packing 4 bytes to an integer, since we don't have a byte data-type and the overhead for list entries in Mono seems to be pretty high, so memory is really saved doing this =)
- Byte-data has a header (first-entry) to identify the number of bits it contains. This is done to allow correct serialisation back into a form which doesn't fit perfectly into 32-bit blocks. This is of course padded as mentioned.

I'm sure there are some other ones to look out for but I can't for the life of me think what they are at the moment.

Meanwhile, I've had some ideas on how to dramatically increase the speed of my big-integer implementation for RSA/Diffie Hellman. It still isn't likely to be very viable for message-passing (unless you do so infrequently) but should make it more viable to key-generation and message signing, I hope =)

[edit] The one thing I did notice about your code Strife, is that you change it to restrict key-size to specific limits (128 to 256). Is this really necessary? The algorithm works for smaller values (though I definitely wouldn't suggest using them) and also much larger ones. Do you know for certain that larger keys should not be accepted (if so, why please, I'm not sure =)

Anyway, great to have your help!

The key size limits are those imposed by AES and Rijndael there is likely a good reason for them (like the math falling apart). My optimization is only good for a Len of 4 and higher, to get to Len 3 will require 1 more byte and to get that into the current footprint is going to be tricky, I'm going to need to come up with a more involved dance for the bits. Currently the code supports 12 bytes (though it only needs 10 for 4).

Here is the breakdown based on key Len with the number of RCon bytes needed.
0 - DivideByZero (A key size of zero is stupid anyway)
1 - 31
2 - 17
3 - 13
4 - 10
5 - 9
6 - 8
7 - 7
8 - 7

RCon range [1, 4 + 28.0/Len)

It's up to you, I'm only willing to declare support for up to 256-bit keys for the moment anyway. I'm going to integrate your new key expansion function into the script on the wiki as the new expansion times are impressive (0.05 seconds to expand a 256-bit key, opposed to around 0.2 seconds).

Personally, I just wish they would go ahead and provide LSL bindings to the OpenSSL library, stick a small enforced sleep after any significant function to prevent resource abuse, and be done with it.

LSL, even under Mono, is the absolute WORST way to do encryption. In addition, we shouldn't HAVE to reimplement existing algorithms. Not only does it have the potential to introduce errors, but also serious security weaknesses in the cryptosystem.

We don't need access to all of the bindings, just a couple in each category, offering both light-weight and heavy-duty variants.

But it's so much fun to reimplement them. Making the bits and bytes dance and scream in agony.

Does any mono encrypt/decrypt implementation run in under 1 second?

Oh, well, in that case, please proceed directly to the lexical torture chamber.

The AES one currently being discussed does, but like with anything it will depend on simulator load, message size etc.

I know there are LSL implementations of RC-4 and XTEA, which are likely faster, but are not generally considered as secure as AES, though they're plenty secure for many operations, it all depends what you want of it.

And I'm with Strife on re-implementing these things, LSL presents some unique challenges that other languages do not face, sure most of them are because things like lists are crap, but there's a certain pleasure to be gained from against all odds managing to get something to work efficiently in LSL =)
Besides-which, I don't think I've ever fully understood how asymmetric (public-key) encryption worked, but I know I'm fairly well versed in it. I've learned a hell of a lot about encryption in only a couple of weeks, so even if LL were to give us encryption functions tomorrow, I wouldn't consider it wasted effort!

Oh I agree 100%. I am not part of the "don't rewrite the wheel" crowd. There are most certainly valid reasons to do so, one of the most important of which you just elucidated on.

My point was mainly that, if LL were to give us LSL bindings into the OpenSSL library tomorrow, I would use them over any other LSL implementation. Failing that, I *HAVE* to write my own, because I have to be responsible for my own security, and LSL implementations just don't have enough bulletproof verification for me to trust otherwise. It's a personal thing, mainly. Security is something that has to start from known, verifiable bases, or you do it yourself to be sure, as far as I am concerned.

You know the old joke, there is the right way, the wrong way and the Army way? lslAESBytesToString is the Army way, perfectly valid but total overkill. Anywho, I've rewritten it, should be much faster... assuming it works at all (untested but heavily reviewed).
The bit count MUST be accurate, the list length is not used at all.

string lslAESBytesToString(list b, integer width, string alphabet) {
    integer bits = llList2Integer(b, 0);
    
    integer i = 0;
    integer mask = ~(-1 << width);
    integer shift = 32 - width;
    
    integer available = 0;
    integer prev = 0;
    integer buf;
    integer extra;
    integer value;
    
    string s = "";
    
    @lslAESBytesToStringLoop;
    if((bits -= 32) > -32)
    {
        available += 32 + (bits * (0 > bits));
        buf = llList2Integer(b, ++i);
        if(available >= width)
        {
            if(prev)
            {
                s = (s = "") + s + 
                    llGetSubString(
                        alphabet, 
                        value = (extra | ((buf >> (shift + prev)) & ~(-1 << (width - prev)))), 
                        value
                    );
                buf = buf << (width - prev);
                available -= width;
            }
            while(available >= width)
            {
                s = (s = "") + s + 
                    llGetSubString(
                        alphabet, 
                        value = ((buf >> shift) & mask),
                        value
                    );
                buf = buf << width;
                available -= width;
            }
            if((prev = available))
                extra = (buf >> shift) & mask;
            jump lslAESBytesToStringLoop;
        }
    }
    if(available)
    {
        mask = -1 << (width - prev);
        return (s = "") + s + 
            llGetSubString(
                alphabet, 
                value = ((extra & mask) | ((buf >> (shift + prev)) & ((-1 << (width - available)) ^ mask))), 
                value
            );
    }
    return (s = "") + s;
}

I've integrated your updated function Strife, cheers for that! It's around 50% faster on most of the tests I made to check the previous one. I've made only a few cosmetic changes mainly for my benefit so I can see what's going on, as it isn't something I've had to code before. Mine was made flexible and correct with not much effort at being optimal as it wasn't the part I wanted to be working on =)
Regarding your comment on the bit-header being correct, this should not be an issue as the cipher function increases the header to account for any padding, the invertCipher function undoes that, and the lslAESStringToBytes() initialises the bit-header as a best guess. The only trouble to be had with the bit-header is when dealing with base64 input, as a 512-bit value in base64 is represented by 516-bits with no way to detect the original length. But worst that can happen here is that the value is output as the same 516-bit base64 string when it's decrypted, so the burden falls on whoever sent the input. I have a note somewhere not to use base64 for keys unless they're 192-bits in length (which can be represented correctly).


Also, I've hobbled together a little hashing function which use the AES cipher. It's mainly for my own benefit but others may find it useful, you can simply drop it into the existing code and add a link-message for it, or test it manually. It attempts to use all of the given data in generating a variable bit length hash, which should be cryptographically unique on account of how AES operates. My original intention was try and do the WHIRLPOOL hashing scheme, but this has it's own sets of pre-generated tables and has quite a large memory overhead so it would need to be its own project if it will fit into Mono's memory space at all.

Here's the hash-function for anyone interested. My current intention with it is to use it for signing messages. Basically you would pass your message in and get a hash for it using a signature key, you then add the signature to your message and pass the signed message in for encryption ready to send. Thus the receiving code, if it has the signature key, can verify your message. Technically signing should use asymmetric keys, but unfortunately asymmetric encryption is very performance intensive without proper arrays =(

// Calculate a length-bit hash using the currently expanded key. Length MUST 
// be a multiple of 32.
list lslAESHash(list data, integer length) {
    // First pad data to a length * 2
    integer l = llList2Integer(data, 0);
    integer i = 0;
    integer j = length << 1;
    
    // If too short, then add values
    if (l < j) {
        integer a = (j - l) / 32;
        do data = (data = []) + data + [llList2Integer(data, i)];
        while ((++i) < a);
        l = j;
    }
    
    // Irreversibly reduce to length by XORing
    j = l / length;
    integer w = j - 1;
    l = data != [];
    list t = [length];
    integer b = 0;
    i = 1;
    do {
        b = b ^ llList2Integer(data, i);
        if ((i % j) == w) {
            t = (t = []) + t + ;
            b = 0;
        }
    } while ((++i) < l);
    data = (data = t = []) + t;
    
    // Add any extra data
    if ((data != []) < (length / 32)) 
        data = (data = []) + data + ;
    
    // Calculate hash    
    data = lslAESCipher((data = []) + data);
    
    // Reduce to size
    l = (data != []) - (length / 32);
    return [length] + llList2List((data = []) + data, 1, -l);
}

I took a swing at your hash function. After you introduce the list variable in the scope you won't want to change the value of data much (it will cause you memory issues I suspect). I did a bit of creative condensing, it will need to be tested.

list lslAESHash(list data, integer length) {
    // First pad data to a length * 2
    integer bits = llList2Integer(data, 0);
    integer i = 0;
    integer j = length << 1;
 
    // If too short, then add values
    if (bits < j) {
        integer a = (j - bits) / 32;
        do data = (data = []) + data + llList2Integer(data, i);
        while ((++i) < a);
        bits = j;
    }
 
    // Irreversibly reduce to length by XORing
    integer w = (j = (bits / length)) - (i = 1);
    bits = data != [];
    list out = [length];
    integer b = 0;
    do {
        b = b ^ llList2Integer(data, i);
        if ((i % j) == w) {
            out = (out = []) + t + b;
            b = 0;
        }
    } while ((++i) < bits);
 
    // Add any extra data if necessary and calculate hash
    if ((out != []) < (length / 32)) 
        out = lslAESCipher((out = data = []) + out + b);
    else
        out = lslAESCipher((out = data = []) + out);
 
    // Reduce to size
    return length + llList2List(out, 1, (length / 32) + ((out = []) != out));
}