xor bytes

I was playing around a day or two ago with an xor encryption..... I had a small need to a faster way of doing it, so I went to an asm dll.

I didn't paste everything here, only whats needed. Can you make it better?

Code:

SAFEARRAYBOUND struct cElements DWORD ? ; Number of Elements lLbound DWORD ? ; Lower Boundary SAFEARRAYBOUND ends OLE_SAFEARRAY struct cDims WORD ? ; Number of dimensions fFeatures WORD ? ; Bitfield indicating attributes cbElements DWORD ? ; size of an element of the array cLocks DWORD ? ; lock counter 0=Locked pvData DWORD ? ; Pointer to data rgsabound SAFEARRAYBOUND <> ; Contains info for dimensions OLE_SAFEARRAY ends

Code:

xorbytes proc msg:DWORD, key:DWORD push ebx push esi push edi push ebp mov eax, msg mov ebx, key movd MM0, esp mov edx, [eax] mov ecx, [ebx] mov ebp, (OLE_SAFEARRAY ptr [edx]).rgsabound.cElements mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements mov edi, (OLE_SAFEARRAY ptr [edx]).pvData mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData cmp ebp, 0 je done cmp ebx, 0 je done xor ecx, ecx mov esp, esi add esp, ebx jmp For_Loop SetKeyBack: sub esi, ebx jmp lblCon align 16 For_Loop: cmp esi, esp je SetKeyBack lblCon: mov al, [esi] xor byte ptr [edi], al add edi, 1 add esi, 1 add ecx, 1 cmp ecx, ebp jne For_Loop done: movd esp, MM0 pop ebp pop edi pop esi pop ebx ret xorbytes endp

Re: xor bytes

this is the basic algorithm that I converted:

For i = 1 To Len(Message)
plainchar = Asc(Mid(Message, i, 1))
pk = Asc(Mid(key, (i Mod Len(key) + 1), 1))
buffer = buffer & Chr(plainchar Xor pk)
Next i

The only difference is that I got rid of the need for "MOD" (divisons are very epensive and I always try like hell to get rid of them) and buffer as the one in asm just xors the message that is passed to it.

Re: xor bytes

Thats good stuff. I wish I knew ASM. I bought a book but didn't get to far.

Just looking at that code makes you appreciate the greatness of high level languages.

Re: xor bytes

Quote:

Originally Posted by nkad

Thats good stuff. I wish I knew ASM. I bought a book but didn't get to far.

Just looking at that code makes you appreciate the greatness of high level languages.

It makes you thankful for all that code it saves you from typing. I must say though, I miss the power of asm in high level languages.

Re: xor bytes

The first comparison in the for loop (cmp esi, esp), can you find an alternative to that?

As you know, comparisons are expensive and to do one for every byte of the message/key may be slowing it down.... still, you must have a massive improvement over that hideous piece of VB code (that Im sure could also be improved)

Re: xor bytes

Quote:

Originally Posted by tailz

The first comparison in the for loop (cmp esi, esp), can you find an alternative to that?

As you know, comparisons are expensive and to do one for every byte of the message/key may be slowing it down.... still, you must have a massive improvement over that hideous piece of VB code (that Im sure could also be improved)

Compare instructions aren't too bad on my processor (p4):
Clocks : 0.334644

Anyway it's a lot cheaper then multiply wich is like 18 clock cycles and divide which is like 29 clock cycles.

Re: xor bytes

Here is the latest version.

Code:

xorbytes proc msg:DWORD, key:DWORD .data align 4 lblPtr dd L0, L1, L2, L3 keyPtr dd 0 keysize dd 0 counter dd 0 .code push ebx push esi push edi push ebp mov ebx, msg ; Message Array mov edx, key ; Key Array mov eax, [ebx] ; reference Message Array mov ecx, [edx] ; reference Key Array mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData mov ebp, (OLE_SAFEARRAY ptr [eax]).rgsabound.cElements mov edi, (OLE_SAFEARRAY ptr [eax]).pvData ; ------------------------------------------------------------------------- ; EBX = Len of Key ; ESI = Pointer to key data. ; EBP = Len of msg ; EDI = Pointer to msg data. ; ------------------------------------------------------------------------- ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« mov keyPtr, esi mov keysize, ebx cmp ebx, 4 jb singlebyte ; If keysize < 4 then load by single bytes only. xor edx, edx ; Clear edx for unsigned divison. mov eax, ebp ; Copy msgsize into eax div ebx ; Divide by keysize. push edx ; Save remainder mov ebp, eax ; ebp = number of times to loop through message mov ecx, ebx shr ecx, 2 ; Shift right 2 places (keeps it 4 byte alinged) mov eax, ecx shl eax, 2 sub ebx, eax ; Remainder bytes (Odd bytes) mov counter, ecx ; Save counter. ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« Loop1: jmp dword ptr [lblPtr + ebx * 4] ; Jump Table, will jump instantly to the correct label. L1: ; 1 odd Byte. mov al, byte ptr [esi] xor byte ptr [edi], al add esi, 1 add edi, 1 jmp L0 L2: ; 2 odd bytes mov ax, word ptr [esi] xor word ptr [edi], ax add esi, 2 add edi, 2 jmp L0 L3: ;3 odd bytes mov ax, word ptr [esi] mov dl, byte ptr [esi+2] xor word ptr [edi], ax xor byte ptr [edi+2], dl add esi, 3 add edi, 3 L0: ; Aligned by 4 mov eax, DWORD PTR [esi] xor DWORD PTR [edi], eax add esi, 4 add edi, 4 sub ecx, 1 jnz L0 mov ecx, counter ; Count used for L0 loop. mov esi, keyPtr ; Move to start pos of the key. sub ebp, 1 jnz Loop1 ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« pop ebp ; Number of bytes left in msg to xor. cmp ebp, 0 ; If none then goto done. je done mov ebx, keysize ; Move keysize into ebx. singlebyte: xor ecx, ecx ; Clear ecx (used for counter). sub ebx, 1 ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« looper: mov al, byte ptr [esi+ecx] ; Load key byte. xor byte ptr [edi], al ; xor msg byte with key byte and save. add edi, 1 ; Point to next byte in msg. cmp ecx, ebx ; if counter = keysize then jne S1 xor ecx, ecx jmp S2 S1: ;else add ecx, 1 ; add 1 to counter. S2: sub ebp, 1 jnz looper ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« done: xor eax, eax ; Clear Return pop ebp ; Restore Registers pop edi pop esi pop ebx ret ; Exit Function xorbytes endp

Re: xor bytes

I had to optimize the VB version:

VB Code:

'for comparison:
'    For i = 1 To Len(Message)
'        plainchar = Asc(Mid(Message, i, 1))
'        pk = Asc(Mid(key, (i Mod Len(key) + 1), 1))
'        buffer = buffer & Chr(plainchar Xor pk)
'    Next i
 
Public Function XorEncode(ByVal strMessage As String, ByVal strKey As String) As String
    Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
    Dim msgSize As Long, keySize As Long
    Dim I As Long
 
    'convert strings to byte arrays
    bArrMessage = strMessage
    bArrKey = strKey
 
    msgSize = UBound(bArrMessage) 'upper bound
    keySize = LenB(strKey) 'actual size (due to the way used with Mod)
 
    'prepare output buffer
    ReDim bArrOutput(msgSize)
 
    'without Unicode string support (step by two)
    For I = 0 To msgSize Step 2
        'simple Xor based on given key
        bArrOutput(I) = bArrMessage(I) Xor bArrKey(I Mod keySize)
    Next I
 
    'convert byte array to string
    XorEncode = bArrOutput
End Function

I don't know how well this can be compared to the ASM version, but shouldn't be too bad (considering it has to do string conversions, taking that functionality out and working with pure byte arrays would make it superb).

To make this faster:
- use SafeArray trick
- with a small trick, you can get rid of extra math required to use Mod, and so result in less overall math

Re: xor bytes

And here is the one with the later trick:
VB Code:
Public Function XorEncode2(ByVal strMessage As String, ByVal strKey As String) As String
    Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
    Dim msgSize As Long, keySize As Long
    Dim I As Long, A As Long, B As Byte
 
    'convert strings to byte arrays
    bArrMessage = strMessage
    bArrKey = strKey
 
    msgSize = UBound(bArrMessage) 'upper bound
    keySize = LenB(strKey) 'actual size (due to the way used with Mod)
 
    'prepare output buffer
    ReDim bArrOutput(msgSize)
 
    'without Unicode string support (step by two)
    For A = 0 To keySize - 1 Step 2
        B = bArrKey(A)
        For I = A To msgSize Step keySize
            bArrOutput(I) = bArrMessage(I) Xor B
        Next I
    Next A
 
    'convert byte array to string
    XorEncode2 = bArrOutput
End Function
Comparison on my machine (compiled, all advanced optimizations) with 100 000 iterations:
- XorEncode: 320 ms
- XorEncode2: 275 ms
- just the string conversion stuff, reserving of memory and function call: 260 ms

Note I really had a long pause between coding it, I did it because I had nothing better to do at the time :D

Another note for those who might come and claim using For...Next loops are slower than Do loops: in this case and use, For loops are slightly faster. No major speed difference can be gained using Do loops instead.

Edit Simplified it a bit while the speed remained the same.
Edit Slight optimization, increase in overall speed by 10ms.

Re: xor bytes

Quote:
Originally Posted by Merri
And here is the one with the later trick:
VB Code:
Public Function XorEncode2(ByVal strMessage As String, ByVal strKey As String) As String
    Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
    Dim msgSize As Long, keySize As Long
    Dim I As Long, A As Long, B As Byte
 
    'convert strings to byte arrays
    bArrMessage = strMessage
    bArrKey = strKey
 
    msgSize = UBound(bArrMessage) 'upper bound
    keySize = LenB(strKey) 'actual size (due to the way used with Mod)
 
    'prepare output buffer
    ReDim bArrOutput(msgSize)
 
    'without Unicode string support (step by two)
    For A = 0 To keySize - 1 Step 2
        B = bArrKey(A)
        For I = A To msgSize Step keySize
            bArrOutput(I) = bArrMessage(I) Xor B
        Next I
    Next A
 
    'convert byte array to string
    XorEncode2 = bArrOutput
End Function
Comparison on my machine (compiled, all advanced optimizations) with 100 000 iterations:
- XorEncode: 320 ms
- XorEncode2: 275 ms
- just the string conversion stuff, reserving of memory and function call: 260 ms

Note I really had a long pause between coding it, I did it because I had nothing better to do at the time :D

Another note for those who might come and claim using For...Next loops are slower than Do loops: in this case and use, For loops are slightly faster. No major speed difference can be gained using Do loops instead.

Edit Simplified it a bit while the speed remained the same.
Edit Slight optimization, increase in overall speed by 10ms.
right now I'm doing 1,000,001 iterations at:

90-130

Reason for such a big difference is because I don't have the algorithm testing for miss-aligned data. So its running 90 on aligned bytes and 130 on unalinged. =/ You get kicked in the balls if you don't align your data when loading 4 bytes at a time.

I also need to get it running in Parallel. Get another nice little speed boast doing that. Definitely need to get rid of that 2nd loop.

Anyway we'll be some xoring mofo's if I ever get that done. Setting up the loop to do all that is the trouble.

1 Attachment(s)

Re: xor bytes

I'm growing board with this so this will be the final version. I've attached the source and exe's.

Code:

xorbytes proc msg:DWORD, key:DWORD .data align 4 byte_4_counter dd 0 .code push ebx push esi push edi push ebp mov ebx, msg ; Message Array mov edx, key ; Key Array mov eax, [ebx] ; reference Message Array mov ecx, [edx] ; reference Key Array mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData mov ebp, (OLE_SAFEARRAY ptr [eax]).rgsabound.cElements mov edi, (OLE_SAFEARRAY ptr [eax]).pvData ; ------------------------------------------------------------------------- ; EBX = Len of Key ; ESI = Pointer to key data. ; EBP = Len of msg ; EDI = Pointer to msg data. ; ------------------------------------------------------------------------- ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« xor edx, edx ; Clear Edx mov eax, ebp ; Set eax to size of msg div ebx ; Divide by keysize sub ebp, edx ; Minus odd bytes push edx ; Save Remainder (Odd bytes). mov eax, ebx ; Move eax len of key shr eax, 2 ; Divide by 4 mov byte_4_counter, eax ; Save how many times to load by 4 shl eax, 2 ; shift it back mov ecx, ebx sub ecx, eax ; Subtract xor edx, edx ; ------------------------------------------------------------------------- ; Ecx now has the odd byte count for our key ; ------------------------------------------------------------------------- cmp ecx, 0 ; If no odd bytes je byte_4 cmp ecx, 2 ; If 2 odd bytes je byte_2 cmp ecx, 3 ; if 3 odd bytes je byte_3 ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« ; ------------------------------------------------------------------------- ; XOR ONE BYTE AT A TIME. ; ------------------------------------------------------------------------- byte_1: xor ecx, ecx ; Clear counter movzx eax, byte ptr [esi] ; Load the key char into al L1: xor byte ptr [edi+ecx], al ; Xor msg by key char add ecx, ebx ; add keysize to msg cmp ecx, ebp jb L1 mov edx, 1 jmp byte_4 ; ------------------------------------------------------------------------- ; XOR TWO BYTES AT A TIME. ; ------------------------------------------------------------------------- byte_2: xor ecx, ecx ; Clear Counter mov dx, word ptr [esi] L2: xor word ptr [edi+ecx], dx ; Xor msg by key charecters add ecx, ebx ; add keysize to counter cmp ecx, ebp ; if ecx >= msg then goto byte_4 jb L2 mov edx, 2 jmp byte_4 ; ------------------------------------------------------------------------- ; XOR THREE BYTES AT A TIME. ; ------------------------------------------------------------------------- byte_3: xor ecx, ecx ; Clear Counter mov ax, word ptr [esi] ; Load 2 bytes into ax mov dl, byte ptr [esi+2] ; load 1 byte into dl L3: xor word ptr [edi+ecx], ax ; xor 3 bytes xor byte ptr [edi+ecx+2], dl add ecx, ebx cmp ecx, ebp ; if ecx >= msg then goto byte_4 jb L3 mov edx, 3 ; ------------------------------------------------------------------------- ; XOR FOUR BYTES AT A TIME. ; ------------------------------------------------------------------------- byte_4: mov ecx, byte_4_counter ; Get number of times to load by 4. cmp ecx, 0 ; If 0 then jump to byte_8 je PassTwo L4: mov ecx, edx ; Clear Ecx mov eax, dword ptr [esi+edx] ; load 4 bytes L5: xor dword ptr [edi+ecx], eax ; xor 4 bytes of msg. add ecx, ebx ; add keysize to ecx cmp ecx, ebp jb L5 add edx, 4 sub byte_4_counter, 1 ; For each load of 4 bytes, loop. jnz L4 ; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««« PassTwo: pop edx ; Get odd bytes in message cmp edx, 0 ; If none then we are finished. je done ;comment * ----------------------------------------------------- oddbytes: mov al, byte ptr [esi] ; Load key byte. add esi, 1 xor byte ptr [edi+ebp], al ; xor msg byte with key byte and save. add ebp, 1 ; Point to next byte in msg. sub edx, 1 jnz oddbytes ;------------------------------------------------------- * done: xor eax, eax pop ebp pop edi pop esi pop ebx ret xorbytes endp

1 Attachment(s)

Re: xor bytes

Just for comparison between VB6 and ASM performance (though it is still possible to optimize the VB6 code but I'm too lazy to do it).

I made them as comparable as possible, working just about the same way, removed a sub call from the faster VB one (because calling a sub in VB costs too much time in benchmarking).

VB one is about two times slower.

Re: xor bytes

Quote:

Originally Posted by Merri

Just for comparison between VB6 and ASM performance (though it is still possible to optimize the VB6 code but I'm too lazy to do it).

I made them as comparable as possible, working just about the same way, removed a sub call from the faster VB one (because calling a sub in VB costs too much time in benchmarking).

VB one is about two times slower.

You have to convert mine to asci first.

IE:

tmpMsg = StrConv(MAINMSG, vbFromUnicode)
tmpKey = StrConv(MAINKEYWORD, vbFromUnicode)

Quote:

You'll notice that as you increase the message size, the difference between the vb code and the asm code gets larger.

Just leave everything like it is and set the msg to that quote and you'll see the difference.

Re: xor bytes

Uh, but that's not optimal at all! Doing the extra StrConv just uses extra processing power for nothing. You can actually run it in the Unicode insanely fast (as you can see from the test). No need to use slow StrConv beforehand.

The thing is, the pure VB code is still pretty fast, considering how much extra coding you had to do just to make it do that simple thing. Also, there is no need for an extra DLL (which most people prefer to avoid while making their application). And the one side being, you have to be sure you're making something compatible with all processors while coding in ASM.

I'd understand this if you were making it for something that processes several megabytes of data and you'd need to do it fast. Since you are doing only simple XOR, which pretty much everyone with some knowledge can crack, I see no real point in your project except the possibility to learn ASM.

My general point being here is that you can code fast enough code with VB. I mostly wanted to do the optimized VB code after seeing you were comparing ASM to the String-mode VB6 code with Asc and Mid, which with just one call is slower than calling the ASM code million times... :)

Re: xor bytes

Quote:

Originally Posted by Merri

Uh, but that's not optimal at all! Doing the extra StrConv just uses extra processing power for nothing. You can actually run it in the Unicode insanely fast (as you can see from the test). No need to use slow StrConv beforehand.

The thing is, the pure VB code is still pretty fast, considering how much extra coding you had to do just to make it do that simple thing. Also, there is no need for an extra DLL (which most people prefer to avoid while making their application). And the one side being, you have to be sure you're making something compatible with all processors while coding in ASM.

I'd understand this if you were making it for something that processes several megabytes of data and you'd need to do it fast. Since you are doing only simple XOR, which pretty much everyone with some knowledge can crack, I see no real point in your project except the possibility to learn ASM.

My general point being here is that you can code fast enough code with VB. I mostly wanted to do the optimized VB code after seeing you were comparing ASM to the String-mode VB6 code with Asc and Mid, which with just one call is slower than calling the ASM code million times... :)

I wanted to work with it in ascii for a reason actually. When using it with other ciphers you can't have the unicde in there or you would open your message up to a freq attack. Eventually I'd like to create a set of high speed crypto functions. But that I'm afraid is a long ways off. I can program in asm but I can't completely bend it to my will as of yet. There is a whole bunch of stuff you have to know in order to really optimizing the living daylights out of code. You have to worry about latency, cpu cache, memory and code alignment, register dependencies, and various other things. Anyway I've seen people who are great at it take a good c algorithm and just simply smoke it. Eventually I wanna be able to do that lol.

Well it's not really all that much code honestly, you have to remember that ASM is a one to one with machine language. As far as dlls goes, I never did have a problem using them. As long as you don't modify the interface to the dll, you don't even have to re-compile your program.

You have processor directives that keep up with what processor your code will run on. .386 for example, will run on any 32 bit processor. It's when you start using special instructions that you have to test for processors. Examples would be: MMX, SSE, SSE2, SSE3, and 3DNow, etc.

I completely dissagree about visual basic being fast enough. Ask any user in the world, it's never fast enough.

Re: xor bytes

Actually, I just asked on IRC and everyone said something similar to "yes, Visual Basic is fast enough" :) Of course it depends on what you're doing, but on most needs, VB really is enough. And VB6 isn't running all that slow compared to C/C++ as the compiler of VB6 is a hacked C/C++ compiler... :)

Re: xor bytes

Quote:

Originally Posted by Merri

Actually, I just asked on IRC and everyone said something similar to "yes, Visual Basic is fast enough" :) Of course it depends on what you're doing, but on most needs, VB really is enough. And VB6 isn't running all that slow compared to C/C++ as the compiler of VB6 is a hacked C/C++ compiler... :)

What irc channel do you hang out in?

I think many people get too hung up in a language. Languages solve different needs and one should always gard against being too conservative in their choices of languages.

Visual basic and C++ works quite a bit differently. In C++ you are responsable for a lot more then what you are in visual basic. That and a very long history of optimization by many people other then microsoft are what make C and C++ so much faster then visual basic. The same is going to be true for the .net enviroment according to Microsoft.

Speed isn't a virtue you look for in visual basic. What you do look for is how easy it is to use. When you're programming in visual basic, you really don't have any worries. Just about every single aspect of visual basic is point and click. I think some visual basic programmer would be shocked to find out how much visual basic actually does for you. That is the best thing about visual basic though and I think microsoft did a great job at it. So if I was going to say visual basic solves a need, I would say it solves the need to do some programming work quickly and easily.

If you want to do a major application though, visual basic isn't really enough.