Bottleneck: easy obscurity "encryption" via xor

[Tino Lange]

Hi!

I identified a bottleneck in my programs.

I just want to "encrypt" data by easy xoring. Ok - that's no
encryption at all - I know. But it's hardly readable - and that's
enough :-) Just some quick obscurity.

It turns out not to be quick at all. I really didn't expect this to be
a bottleneck, but it takes quite some time.

Here's the code:

$ cat python/EasyCrypt.py
#! /usr/bin/env python
import operator
def xorcrypt(str, salt = 255):
if salt > 255:
raise "Invalid salt! Must be < 255!"
return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")
xor'ing medium sized-files takes long time. For example a 360
kByte-File takes:
$ time ./just_crypt.py Userdatan/ScanImage01.jpg > bert
real 1m52.138s
user 0m40.320s
sys 1m6.030s

on my 2.66 GHz P4 machine!

Hmmm, do you have some better implementation ideas? Some optimizing
tricks? (Besides coding in C to avoid immutable string problems)
I already took the operator module to speed up a bit - but it seems
that's not enough...

Thanks

Tino

[Irmen de Jong]

Tino Lange wrote:

It turns out not to be quick at all. I really didn't expect this to be
a bottleneck, but it takes quite some time.

return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")

Running this on a large string builds up a huge list of ints,
that you are converting to chars and then concatenating them
together using +... this creates a HUGE number of temporary
string objects.
The usual pattern of fast string joining is:

''.join(list-of-fragments)

So first try:

return ''.join(map(lambda char, _salt = salt: chr(operator.xor(ord(char), _salt)), string))

This runs MUCH faster already.

But the version I'd recommend is:

def xorcrypt(string, salt = 255):
if salt <0 or salt> 255:
raise "Invalid salt! Must be 0<=salt<=255!"
return ''.join( [ chr(ord(c) ^ salt) for c in string ] )

because
1) salt must be 0..255 not only <=255
2) forget about map & lambda, use a list comprehension.

That implementation runs about 20 times faster than your original one;
0.11 seconds for 100 Kb source data. (python 2.3)

HTH,
--Irmen de Jong

[Bengt Richter]

On Wed, 30 Jul 2003 00:25:59 +0200, Irmen de Jong <[e-mail]> wrote:

Tino Lange wrote:

It turns out not to be quick at all. I really didn't expect this to be
a bottleneck, but it takes quite some time.

return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")

Running this on a large string builds up a huge list of ints,
that you are converting to chars and then concatenating them
together using +... this creates a HUGE number of temporary
string objects.
The usual pattern of fast string joining is:

''.join(list-of-fragments)

So first try:

return ''.join(map(lambda char, _salt = salt: chr(operator.xor(ord(char), _salt)), string))

This runs MUCH faster already.

But the version I'd recommend is:

def xorcrypt(string, salt = 255):

def xorcrypt(s, salt = 255): # better name choice, even though string module may not be used if salt <0 or salt> 255:
raise "Invalid salt! Must be 0<=salt<=255!"
return ''.join( [ chr(ord(c) ^ salt) for c in string ] ) return s.translate(''.join([chr(ic^salt) for ic in xrange(256)]))
because
1) salt must be 0..255 not only <=255
2) forget about map & lambda, use a list comprehension. forget about list comprehension, use str.translate ;-)
That implementation runs about 20 times faster than your original one;
0.11 seconds for 100 Kb source data. (python 2.3)

s.translate ought to a good deal faster yet ;-)

Regards,
Bengt Richter

[Paul Rubin]

Tino Lange <tl*****@nexgo.de> writes:

Hmmm, do you have some better implementation ideas? Some optimizing
tricks? (Besides coding in C to avoid immutable string problems)
I already took the operator module to speed up a bit - but it seems
that's not enough...

Use the array module. See <http://www.nightsong.com/phr/crypto/p2.py>.

[Oren Tirosh]

On Wed, Jul 30, 2003 at 12:03:06AM +0200, Tino Lange wrote:

Hi!

I identified a bottleneck in my programs.

I just want to "encrypt" data by easy xoring. Ok - that's no
encryption at all - I know. But it's hardly readable - and that's
enough :-) Just some quick obscurity.

It turns out not to be quick at all. I really didn't expect this to be
a bottleneck, but it takes quite some time.

If you want higher performance always try to use things that operate
on larger chunks. When you do things byte-by-byte you start to notice the
fact that Python is really an interpreter.

As noted by Bengt Richter xoring with a constant value can be done by
str.translate. It doesn't work for variable values, though.

This code does around 250kb/second on a Pentium 800. XORing is done 32
bits at a time. Conversion to and from character strings is done in even
larger chunks using the array module instead of using ord() and chr().

Oren
from __future__ import generators

import sha

def xor_stream_to_arrays(fin, seed, hashfunc=sha):
""" fin is a file-like object.
yields arrays that may be written to a stream """
from array import array

h = hashfunc.new(seed)
maskchunk = h.digest()
chunksize = len(maskchunk)

while True:
datachunk = fin.read(chunksize)
if len(datachunk) < chunksize:
break
yield array('l', [x^y for (x,y) in zip(
array('l', maskchunk),
array('l', datachunk))])

h.update('x')
maskchunk = h.digest()

maskchunk = maskchunk[:len(datachunk)] # trim to length of remainder

# do the rest by bytes:
yield array('b', [x^y for (x,y) in zip(
array('b', maskchunk),
array('b', datachunk))])

def xor_stream_to_stream(fin, fout, seed):
""" fin, fout are file-like objects """
for a in xor_stream_to_arrays(fin, seed):
fout.write(buffer(a))

def xor_string_to_string(s, seed):
""" gets a string, returns a string """
from cStringIO import StringIO
fin = StringIO(s)
fout = StringIO()
xor_stream_to_stream(fin, fout, seed)
return fout.getvalue()

[Paul Rubin]

Tino Lange <tl*****@nexgo.de> writes:

And it seems that Bengt's reciepe is the fastest. For very small strings
(<255 chars) the method irmen2 should be the best choice - it doesn' have
to pre-create the translation-table and does everything on-the-fly.

You should be able to use the array module to do the xor's 4 bytes at
a time and get a speedup over the 1-byte version. The
string.translate version is the fastest, of course, but depends on
using the same translation table for every char in the string.

If you want to encrypt in python, try the p2.py that I posted; it's
been carefully designed with good algorithms and fairly well optimized
and should give much better security than some roll-your-own method.

[Bob Gailer]

At 12:25 AM 7/30/2003 +0200, Irmen de Jong wrote:

Tino Lange wrote:

It turns out not to be quick at all. I really didn't expect this to be
a bottleneck, but it takes quite some time.

return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char,
_salt = salt: operator.xor(ord(char), _salt), str), "")

Running this on a large string builds up a huge list of ints,
that you are converting to chars and then concatenating them
together using +... this creates a HUGE number of temporary
string objects.
The usual pattern of fast string joining is:

''.join(list-of-fragments)

So first try:

return ''.join(map(lambda char, _salt = salt:
chr(operator.xor(ord(char), _salt)), string))

This runs MUCH faster already.

But the version I'd recommend is:

def xorcrypt(string, salt = 255):
if salt <0 or salt> 255:
raise "Invalid salt! Must be 0<=salt<=255!"
return ''.join( [ chr(ord(c) ^ salt) for c in string ] )

Great minds think alike? I came up with (independently!):
return ''.join([chr(ord(char) ^ salt) for char in txt])
I also favor comprehension because it is more readable.
because
1) salt must be 0..255 not only <=255
2) forget about map & lambda, use a list comprehension.

That implementation runs about 20 times faster than your original one;
0.11 seconds for 100 Kb source data. (python 2.3)

HTH,
--Irmen de Jong
--
http://mail.python.org/mailman/listinfo/python-list


---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.500 / Virus Database: 298 - Release Date: 7/10/2003

Bob Gailer
bg*****@alum.rpi.edu
303 442 2625
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.500 / Virus Database: 298 - Release Date: 7/10/2003

[Paul Rubin]

Tino Lange <tl*****@nexgo.de> writes:

Thanks! But BTW your "time-bomb" and your comments in the file tell me that
this script must not be used anymore...

Oh yeah. The code is ok, I just want to rename the function and
release it as p3.py. I haven't gotten around to that because nobody
seems to be using it. I keep forgetting. Anyway I'd appreciate it if
you don't distribute p2.py to other people with the time bomb removed,
but feel free to remove it for your own use.