XOR Encryption - surprising speed improvement

[Gary Beene]

To keep the casual prying eye at bay, I've been using the following XOR encryption on text files. It encrypts one character at a time and builds a new string from the encrypted characters.

Function EncryptMyString(text$, Psw$) As String
    Local i As Long, a As Long, temp$, c$, result$
    temp$ = text$
    For i = 1 To Len(text$)
        a = i Mod Len(Psw$)
        If a = 0 Then a = Len(Psw$)
        temp$ = temp$ + Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1)))
        ' Mid$(temp$,i) = (Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1))))
    Next i
    Function = temp$
End Function

I've used it only for small files (10K or less) so speed wasn't a factor. But last night I tried to encrypt a 1M file and after several minutes it was still running! I killed it.

I replaced the "temp$ = ..." line with the line that is commented out. The new code took only about 0.35 seconds. I guess it's not surprising that the new code was much faster, but I was very surprised at how slowly the original line of code worked.

It shows that the "temp$ = temp$ + " code is a poor choice for large strings. The timing results increased as the square of the string size.

It's a great example of how the choice of functions can significantly impact the speed of a program.

Anyone else have great examples of where simple changes made huge differences?

[Michael Mattias]

>but I was very surprised at how slowly the original line of code worked

You shouldn't be. Your original code does a string concatenation for each character of the source string. String concatenation is "known" to be something to be avoided when possible.

BTW, if you want it even faster, I suggest you look at BYTE PTR datatypes. All those ASC(CHR$(MID$()) calls ain't doing you no speed favors.

MCM

[Gary Beene]

Well, I knew concatenation to be slow, but not to the squared power!

Actually, I also tried to use the PowerBASIC Build$ function which is touted at a very efficient concatenation function. It made almost no difference in the result.

c$ =   Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1)))
temp$ = Build$( temp$,  c$)

A simple concatenation like these next two lines shows that Build$ is faster by 3x or so.

a$ = b$ + c$ 
a$ = Build$( b$, c$)

But it's the form of "temp$ = temp$ + " that seems to be making a difference.

And, to your point, I also tried taking out the "temp$ = temp$ + " and just did the asc/chr/mid$ stuff. The speed was excellent. Those functions may be slow, but were not a serious factor in the results.

[Gary Beene]

Actually, my first thought was to try a pointer solution. However my pointer experience is about zilch, so I looked elsewhere and found the "Mid$=" solution.

Generating a pointer version will be a good learning vehicle for me - so I'll go ahead and give it a try.

[Joseph Cote]

You might squeeze a little more out of it by replacing

a = i Mod Len(Psw$)
If a = 0 Then a = Len(Psw$)

with

a = ( i MOD LEN(Psw$) ) + 1

It will cycle through the Psw$ in a different order, but as long as encryption/decryption are identical, it wouldn't matter.

Or even better, do a one-time convert of the Psw$ into a numeric array and use that instead of doing the same conversions over and over. Assuming, of course, that LEN(Psw$) << LEN(Text$).

[Michael Mattias]

>Or even better, do a one-time convert of the Psw$ into a numeric array

  REDIM X(LEN(Psw$)-1) AS BYTE AT STRPTR(psw$)

Or (to get you started using pointers here) ...

  Z =  MID$(S,pos,1)

EQUALS

  LOCAL pb AS BYTE PTR 
  pb = STRPTR(S) 
  INCR  pb 
  Z  =  CHR$(@pb[pos])

MCM

[Brian Chirgwin]

To keep the casual prying eye at bay, I've been using the following XOR encryption on text files. It encrypts one character at a time and builds a new string from the encrypted characters.

Not so surprising when you understand what is going on behind the scenes.

If you watch the task manager you will also find that memory usage is much less using the second version. At least 50% less.

String concatenation one character at a time. This means the computer is doing the following (or something similar).

1. Allocate memory for the new temp$ + 1 character (actually, it might allocate a temp string + a second temp string (1 char) and then allocate memory for the full length of the new temp$)
2. Copy the temp string data to the new allocated memory (mem copy)
3. Add the new character to the end. (additional mem copy of a single byte)

A 4 character string is performing
1. Allocation
1 + 2 + 3 + 4. 4 separate allocations for a total of 10 bytes
2. Copy
4 copy operations a total of 10 bytes
3. Append New Char
4 copy operations a total of 4 bytes

A 8 character string
1. Allocation
1 + 2...+8 = 8 allocations for 36 bytes total
2. Copy
8 copy operations a total of 36 bytes
3. Append
8 copy operations a total of 8 bytes

A 100 character string
1. Allocation
1+2+...100 = 100 allocations of 5050 byte total
2. Copy
100 copy operations a total of 5050 bytes copied
3 Append
100 copy operations a total of 100 characters


I may be off on my numbers (if I am I'm lower than what actually occurs), but it gives you the general idea of what is going on behind the scenes. As you can see, by the time you get to a file size of 1M you will be allocating and copying many 1000s of times the size of the file.

Also each allocation must be contiguous section of memory the size asked for (strings must be contiguous). At the lower allocation sizes you might be fragmenting physical memory creating a bunch of tiny holes in memory as it is deallocated. At higher allocation sizes Windows might be compacting memory so it can create a contiguous section of memory for you.

Also, a 1 million byte file means 1 million memory allocations and at least 2 million memory copies. Even if each allocation were 1 byte this would take a while to perform.

Using Mid$, you are replacing the memory at the given location and removing memory allocation completely. As you found out, allocating memory takes most of the time to perform in this function. It makes total sense when you understand what is happening behind the scenes.

As suggested, remove mid and use pointers and it will be optimized even more. Since your down to .35 seconds the reduction will be little in comparison to what improvement you already have. 0.35 seconds or less; the difference won't be noticed. Of course, if this were a web site with a 100 million hits a day, the improvement can be well worth it.

Brian

[Tom Hanlin]

BUILD$ is intended to make it faster to concatenate a whole list of strings. It's not going to help any if you just have two strings at a time.

Given that you've already set temp$ = text$, though, it looks to me that most of those string actions are superfluous. Instead of this:

temp$ = temp$ + Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1)))

Try something like this:

Asc(temp$, i) = Asc(Psw$, a) Xor Asc(temp$, i)

...if I've grasped the intent properly. As Michael notes, you could do even better with pointers.

[Michael Mattias]

> Asc(temp$, i) = Asc(Psw$, a) Xor Asc(temp$, i)

I rather suspect the way this is implemented by the compiler savings from using BYTE PTR vars would be minimal.

(Of course it's proprietary. This is a GUESS. But I will bet it is a GOOD guess).

[Mel Bishop]

...Of course it's proprietary...

So who owns it?

I would hate to think I've been using a proprietray technique for years without paying royalities.

[Michael Mattias]

I would hate to think I've been using a proprietray technique for years without paying royalities.

HUH?

Your $199.00 or whatever it was you paid for the compiler purchased a LICENSE to use it.

Um, you DID pay for your compiler, right?

MCM

[John Gleason]

Anyone else have great examples of where simple changes made huge differences?

Here's one I recently learned about:

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
    LOCAL lineo AS STRING, ii AS LONG, time AS SINGLE
    
    OPEN "c:\fileTestSpeedOfLineInput.txt" FOR OUTPUT AS #1
    lineo = STRING$(20, 50) & $CRLF
    lineo = REPEAT$(3200, lineo)

    'make a text file ~70MB with 3.2M records
    FOR ii = 1 TO 1000
       PRINT #1, lineo;
    NEXT

    CLOSE #1
'
'-------- Try each of the two OPEN versions and note the below loop speed difference---------------------
'   OPEN "c:\fileTestSpeedOfLineInput.txt" FOR INPUT LOCK SHARED AS #1
    OPEN "c:\fileTestSpeedOfLineInput.txt" FOR INPUT AS #1              'simply removing LOCK SHARED speeds the below
                                                                        'LINE INPUT loop 4.5x on my computer
'--------------------------------------------------------------------------------------------------------
    ? "Test file has been created. Here we go..."
    time = TIMER
    FOR ii = 1 TO 3200000
       LINE INPUT #1, lineo       '4.5x faster on my computer if file is not LOCK SHARED.
    NEXT                          'LOCK SHARED allows no buffering so LINE INPUT is slower.
    ? STR$(TIMER - time)
    
    CLOSE #1
    KILL "c:\fileTestSpeedOfLineInput.txt"  'erase our big test file
    
END FUNCTION

[John Gleason]

Also Gary, you can often use the below technique to get the speed of pointers without using any pointers, and simplify your code, by using "overlay" arrays (absolute arrays). You don't have to use any pointers except for the "AT STRPTR(string)" part of the DIM statement.

What happens is the BYTE arrays in this case match exactly one-to-one with each byte of the 3 strings, overlaying them so to speak, making all their individual bytes accessible by array subscripts, eg. tempArr(15) is the 15th byte of temp$, tempArr(125) is the 125th byte of temp$, and so on.

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
     LOCAL txt, psw, encrStr AS STRING
     
     txt = REPEAT$(4, CHR$(1 TO 255))
     psw = "alwaysMakeAstrongPass!wor!d ;-)"
     encrStr = EncryptMyString(txt, Psw)
     REPLACE ANY CHR$($NUL,$CR,$LF,$TAB,$SPC) WITH "0DA9." IN encrStr  'format so we can view it
     REPLACE ANY CHR$($NUL,$CR,$LF,$TAB,$SPC) WITH "0DA9." IN txt
     
     ? txt & $CRLF & $CRLF & $CRLF & encrStr

END FUNCTION

FUNCTION EncryptMyString(text$, Psw$) AS STRING
   LOCAL i AS LONG, a AS LONG, temp$, c$, result$
   temp$ = text$
   
   'This shows how you can overlay the three strings with three easy to access arrays:
   DIM textArr(1 TO LEN(text$)) AS BYTE AT STRPTR(text$) 'These are the 3 key lines. Now you can access each byte to
   DIM tempArr(1 TO LEN(temp))  AS BYTE AT STRPTR(temp)  'encode by using array subscripts directly. No pointers
   DIM  pswArr(1 TO LEN( psw$)) AS BYTE AT STRPTR(psw$)  'are necessary and it's approx. equal in speed to pointers.
   
   FOR i = 1 TO LEN(text$)
      a = i MOD LEN(Psw$)
      IF a = 0 THEN a = LEN(Psw$)
      
      tempArr(i) = textArr(i) XOR pswArr(a)
      
      'temp$ = temp$ + Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1)))
      'Mid$(temp$,i) = (Chr$(Asc(Mid$(Psw$,a,1)) Xor Asc(Mid$(text$,i,1))))
   NEXT i
   FUNCTION = temp$
END FUNCTION

[Michael Mattias]

>As you found out, allocating memory takes most of the time to perform in this function

FWIW, it's actually the DE-allocation which is the fly in the ointment. (Sounds counter-intuitive, huh?)

If you really want to 'check it out' (i.e, verify with your own BS meter) and don't feel like designing a test program, there's is some code floating around here which demos this. Search for "private heap" or the "CreateHeap()" Win API function. The use of a private heap is is one of the ways one can combat the time it takes for many small allocations/deallocations... assuming you can't - as you can here - just faggedaboutit by not doing that.

MCM

[Wayne Diamond]

This is pretty much about as fast as it gets, at least when operating on one byte at a time. It operates directly on the text - not a copy of the text (obviously it's easy enough to make a copy first if you need).

You can enhance the speed further by processing 32bits at a time rather than 8 (or 64 if you have the hardware), although the catch with that is that both your key and the text need to be of length divisible by 4. (So, simply pad the text before encryption if necessary and ensure you choose an appropriate key)

#COMPILE EXE
 
'// 8 bits at a time. Text and Key can be any length.
SUB XORText(sText AS STRING, sKey AS STRING)  
LOCAL i AS DWORD, tPtr AS BYTE PTR, kPtr AS BYTE PTR, kEnd AS DWORD
IF LEN(sText) = 0 OR LEN(sKey) = 0 THEN EXIT SUB
tPtr = STRPTR(sText): kPtr = STRPTR(sKey)
kEnd = kPtr + LEN(sKey)
FOR i = 1 TO LEN(sText)
    @tPtr = @tPtr XOR @kPtr
    INCR tPtr: INCR kPtr
    IF kPtr = kEnd THEN kPtr = STRPTR(sKey)
NEXT i
END SUB

'// 32 bits at a time. Both Text and Key lengths must be divisible by 4.
SUB XORText32(sText AS STRING, sKey AS STRING)  
LOCAL i AS DWORD, tPtr AS DWORD PTR, kPtr AS DWORD PTR, kEnd AS DWORD
IF LEN(sText) = 0 OR LEN(sKey) = 0 THEN EXIT SUB
IF LEN(sText) MOD 4 <> 0 OR LEN(sKey) MOD 4 <> 0 THEN EXIT SUB
tPtr = STRPTR(sText): kPtr = STRPTR(sKey)
kEnd = STRPTR(sKey) + LEN(sKey)
FOR i = 1 TO LEN(sText) / 4
    @tPtr = @tPtr XOR @kPtr
    INCR tPtr: INCR kPtr
    IF kPtr = kEnd THEN kPtr = STRPTR(sKey)
NEXT i
END SUB
 
FUNCTION PBMAIN() AS LONG
LOCAL sText AS STRING, sKey AS STRING
sText = "This is the message!"
sKey = "Secret!!"
'// Both sText and sKey must be of length divisible by 4 if using XORText32(),
'// but can be of any length if using XORText()
 
IF LEN(sText) MOD 4 <> 0 THEN sText = sText & STRING$(4 - (LEN(sText) MOD 4), CHR$(0))  '// Pad string if needed
 
STDOUT "Plaintext=" & sText
XORText32(sText, sKey)
STDOUT "Encrypted=" & sText
XORText32(sText, sKey)
STDOUT "Decrypted=" & sText

WAITKEY$
END FUNCTION

On my old AMD Sempron (~1758mhz), encrypting 16,000,000 bytes 20 times (so 320,000,000 bytes total) required 15-16 seconds for the 8bit version (20.6mb/sec) and 9 seconds for the 32bit version (35.5mbs/sec). The 1 megabyte file you're wanting to encrypt takes approximately 30 milliseconds for one pass.

I made an inline assembly version of the 32bit one, it's quicker still ... only 450 milliseconds to do the 20 passes instead of 9 seconds, so that's about half a gigabyte per second. There are probably still some optimisations that can be made:

'// 32bit inline asm version. Both sText and sKey must be of length divisible by 4.
SUB XORText32asm(sText AS STRING, sKey AS STRING)
#REGISTER NONE
LOCAL kEnd AS DWORD, dwLen AS DWORD
IF LEN(sText) = 0 OR LEN(sKey) = 0 THEN EXIT SUB
IF LEN(sText) MOD 4 <> 0 OR LEN(sKey) MOD 4 <> 0 THEN EXIT SUB
kEnd = STRPTR(sKey) + LEN(sKey)
dwLen = LEN(sText) / 4
! mov edi, sText           ;edi=Text to crypt
! mov edi, [edi]           ;Now point to the address it contains
! mov esi, sKey            ;esi=Key
! mov esi, [esi]           ;Now point to the address it contains
! mov ebx, dwLen           ;ebx=Number of dwords
! mov edx, kEnd            ;edx=End of key
NextDword:
  ! mov eax, [esi]         ;eax=Next dword from the key
  ! xor [edi], eax         ;XOR the dword at edi (Text) with eax
  ! dec ebx                ;We've now processed one more dword
  ! jz EndXORText32asm     ;Any dwords left? If not we're done
  ! add edi, 4             ;Point to next dword in the Text
  ! add esi, 4             ;Point to next dword in the Key
  ! cmp esi, edx           ;Have we reached the end of the Key?
  ! jne NextDword          ;Jump to NextDword if not
  ! mov esi, sKey          ;esi=Pointer to the stsrt of the key
  ! mov esi, [esi]         ;And point to the address it contains
  ! jmp NextDword          ;Now go do the next dword!
EndXORText32asm:
END SUB

Btw you're probably already aware, but it's worth mentioning that XOR is about as weak as it gets, even when used with a multibyte string for a key rather than a single byte. It is vulnerable to many different attacks including frequency analysis, and because your key will no doubt be relatively small it would be easy for me to just create a large file full of say "A"'s, encrypt it, and within about 2 minutes I'd know your secret key. This is a known-plaintext attack. However, if it's just to prevent casual viewing by people who'd be clueless about such things and speed of encryption/decryption is more important than overall security then it may be sufficient. One thing you can easily do to add a little extra protection is to encrypt several times with keys of differing lengths, use 'random looking' keys rather than plaintext phrases, and ensure the keys aren't stored as-is in your .exe or somebody can simply view it with a Hex Editor and be able to see the keys.

For more ciphers see www.pbcrypto.com

[Gary Beene]

Hi Wayne,
Thanks for the post. I'll be trying out the code you posted. I haven't gotten around to a pointer version yet so your code is very timely for me.

As for XOR, yes I was aware of it's limitations. But as I noted, it's just:

To keep the casual prying eye at bay,

But you bring up an interesting question - does anyone actually have experience with an XOR encrypted file, where someone actually decrypted it?

For example, if my wife or almost any one of our circle of friends found an XOR encrypted file (lost flash drive?) they'd be clueless on how to proceed.

Whereas if any of the active forum poster found it, as you say, a decrypt if almost certain.

So, what is the percentage of can/cannot decrypt population? And is that the right % to think about?

Is the XOR weakness a probable decryption of an improbable occurrence?

Either way, I wouldn't use it for financial data, but the question of probable loss is interesting. I don't have any experience to know if the XOR weakness is a "distinction without difference", or an example of something that happens all the time.

[Michael Mattias]

I use simple XOR encryption in my shelfware products to "hide" serial numbers, licensed options, demo version yes/no , etc. (I'm not looking for 'unbreakable' I'm just looking to keep the flies off. )

Of course, no one would ever go out of their way to report a 'crack' to me.

[Wayne Diamond]

Hi Wayne,
You bring up an interesting question - does anyone actually have experience with an XOR encrypted file, where someone actually decrypted it?

In the late 90s/early 00s I did a lot of virus analysis, and it's very common for viruses/trojans/worms etc to use weak ciphers such as simple XORs to conceal strings because often they simply need obscurity (not real security), and with minimal code to do so as viruses like to be small. It's surprising how often a single-byte key is used, as you can literally brute-force a result from those with just 255 decryption attempts, which is just a matter of milliseconds.

When multibyte keys are used it becomes slightly more tricky - a bit more effort anyway, but generally still quite trivial simply because XOR doesn't offer any genuine security that you can prove with a mathematical algorithm - it's essentially just obscurity.

When i was young i enjoyed one of the very first PC plane simulators - Ace Of Aces ... my Dad ended up with some ridiculously high score that seemed impossible (like several million compared to my two thousand), and as he never told me how he did it I thought i'd never find out - I thought about it on and off over the years. He passed away in 1999 and i think it was in about 2001, now armed with some skills to be able to take a proper look at it, where I started wondering that maybe I could still find out how he'd done it. I searched the legacy game archives of the web and downloaded Ace Of Aces (virus scanning it first to ensure it didnt have Brain, Jerusalem or any of the good old 80s viruses!)

I played one quick game, saved my score and made a copy of the high scores file, taking note of my score. I played a second game, and again noted my score and made another copy of the high scores file. This is essentially a known-plaintext attack because I knew my scores, so by comparing my two scores with how they were saved in the file it was very easy to determine that the scores were being saved as a 32bit field XOR'd with a static value. As this was the mid-late 80s I'm assuming my Dad would've used debug.com and some hex editor, and probably a pocket calculator
SoftICE was available from 1987, initially for $386, but I dont think he used it whereas I know he used debug.com a fair bit.

So, what is the percentage of can/cannot decrypt population? And is that the right % to think about?

Depends what the target population is ...

[Gary Beene]

Just because I started this post in 2009 doesn't mean I'm still not interested! :laugh:

Looking back on this post, I see that I let a few gems pass me by. So I'm making up for it with a public thank you, as well as a speed analysis of the 4 approaches discussed. I put the compilable code in the source code forum:

These are the times for XOR encryption of roughly 1M characters.

Mid$      1.00s
Asc       0.14s
Overlay   0.07s
Ptr       0.07s
Ptr-Indx   0.03s

Joseph Cote:
Thanks for this, which took two lines down to one. At the time you posted it, I didn't respond. But I'm using it now.

a = (i Mod Len(Psw$)) + 1        'Joseph Cote

Tom Hanlin:
And thank you for this:

Asc(temp$,i) = Asc(psw$,a) Xor Asc(temp$,i)

I didn't understand it at the time - didn't catch on to the fact that ASC can be used to replace a character in a string. I had always used ASC just to get the Ascii value of a character, and had not caught the feature added by PowerBASIC. Very cool. It was about 6 times faster than the Mid$ approach I was using.

MCM/Wayne Diamond:
Thanks for the pointer suggestions. In 2009 I hadn't worked with pointers at all, so your suggestions didn't get my attention at the time. They did today.

John Gleason:
It's only been in the last few months that I've understood, and really liked, the use of overlay arrays - which is also why I didn't jump up and down at your post. It really is pointer fast.

PS. I've noticed several times where folks gave me advice, especially 2009 when I was new to PowerBASIC, that didn't ring a bell for me. It makes me want to be back and re-read every post I've every done, to see what else I didn't capture at the time!

[Ross Boyd]

Hi Gary,
Some tweaks to the ptr version made it about 7 times faster again on my old Q6600. The PB pointers seem to prefer indexes.
Cheers
Ross

function Encrypt_PTR(txt$, psw$) as long  
   local i as long, tPtr, kPtr as byte ptr, j as long,kEnd as long
   tPtr = strptr(txt$)
   kPtr = strptr(psw$)
   kEnd = len(psw$) - 1
    for i = 0 to len(txt$) - 1
        @tPtr[i] xor= @kPtr[j]
        if j = kEnd then j = 0 else incr j
    next i
end function