Encryption with Python?

Tue May 24 14:27:38 EDT 2005

For your own good, please change your credit card number now! You have 
obviously lost your mind. Please read Applied Cryptography if you are 
wondering why I would say this. I am not trying to be mean.

For example:

I have access to 80 Pentium 3 cpus (at ~1.8 GHz) and have engineered a simple 
brute force on this (in pure python) that can check 2**31 integers overnight. 
I timed it. I used absolutely NO optimization. Also, beyond these 2**31 
integers, I stopped trying because I have other things to do--I had no 
incentive. Now your credit card info is on the line. I'm a rank ammy and I'm 
sure a skilled programmer could speed it up 100 to 1000 fold (1000 ~ 2**10). 
Also, this was for your first message about which I knew positively nothing. 
You have made the job now several times easier (lets say 10 ~ 2**3) by 
disclosing the nature of the plain text. If you think that there are lots of 
"keys" that map some part of your cipher text to a set of 16 numbers (+/-) 
separators, you are right. But they would be some small fraction of the total 
keyspace. 10**6 such keys could be stored easily and so second and later 
rounds of analysis would be trivial.

So lets do some math. Say someone had the same computing power as I do. Say, 
we could start with 2**32 keys in 24 hours or 1 day. Now lets say they are a 
good programmer: 2**32 * 2**10 keys/day. Now lets say they take full 
advantage of knowing the nature of the plain text: 3**32 * 2**10 * 2**3. Lets 
say they put 2 weeks of computing time into it: 14 days ~ 2**4 days.

Of course both + and - integers are possible, so we'll divide our final answer 
by 2 later.

So, say you had a highly motivated, reasonably adept programmer whose lack of 
cryptanalysis knowledge limited himself to brute force--but he had a lot of 
computers and 2 weeks to work with--and was checking both + and - integers:

2**(32+10+3+4-1) = 281474976710656

That's 15 digits. That is a telephone number (with area code) and a 5 digit 
zip. That's 2 birthdays, easy. That is easily the hash of any hashable python 
object (only 2**32 possibilities for these). Do you get the point? Basically, 
these 15 digits are about the limit of any managable key.

Now, lets say you have someone skilled at cryptanalysis. Well, they are 
probably already trying to figure out what they want to buy first. Normally I 
wouldn't warn you of this, but I am positively certain that someone smarter 
than me will be spending on your credit card and I want to spoil their 
holiday.

James

On Tuesday 24 May 2005 01:16 am, Anthra Norell wrote:
> I wasn't going to pursue this any further. Actually, I am quite
> disappointed about the belligerent style of some correspondents. It's not
> necessary. It spoils the fun. It cloggs bandwidth.
>    Why whack someone over the head who tries to develop an idea of his own.
> Such an approach isn't uncommon to earn extra credit in educational
> settings.
>    True, I have also been offered good advice and being able to extract it
> from between insuslts I have expressed my appreciation for it. In return of
> the favor I offer a little anecdote about the nature of creativeness.
>    The connection between candor and creativeness has always fascinated me.
> At some point, almost thirty years ago, I came across an article in a hang
> glider magazine by one Dr. Paul MacCready who had just won the Kremer Prize
> with his human-powered Gossamer Condor, a prize that had been standing for
> decades despite innumerable unsuccessful attempts to win it. In that
> article MacCready explained that it was the advent of hang gliders that
> gave him the idea to go for the Kremer prize. Namely, he immediately
> realized that hang gliders dissipated less energy in stable flight than any
> other aircraft in existence, not because the flew so well--they didn't--but
> because of their low weight. He calculated that a twenty-kilogram hang
> glider with a wing span of close to thirty meters would dissipate no more
> than one third of a horse power or thereabout and that is an amount of
> energy a competition cyclist generates over the course of a race.
>     After winning the prize, MacCready challenged himself to fly across the
> English channel and started building an improved second version of his
> airplane. Passing through Los Angeles I went to see the project in a Long
> Beach hangar and took the opportunity to pick MacCready's brain for the
> benefit of our own magazine. Referring to his article I confessed my
> surprise that a scientist of his caliber would be inspried by such crude
> aeronautical engineering hacks as hang gliders unquestionably were. His
> reply was this:
>     "I also consider myself an amateur. I have a PhD in aeronautics, but
> not in aeronautical engineering. But this just might have been my
> advantage. All these many previous failed attempts had been made by people
> with better engineering credentials. If their conception of possible
> solutions was better defined, it was probably also more constrained by
> their knowledge of what an airplane is supposed to be."
>     We went on talking about creativeness and MacCready's conclusion still
> rings in my ears: "Our education system encourages us to be critical. This
> is a great pity. It reinforces our habit to focus on other people's
> weaknesses and failures, when we could learn from observing their
> strengths."
>
> Frederic
>
> (Robert Kern could have embarrassed me with a plain-text attack, although
> his bounty wouldn't have been my credit card details. I tought about
> plain-text attacks and found that in addition to changing the values of
> bytes I also needed to shuffle them a little. So I added a few lines,
> encoded my credit card details and here it is, program, credit card
> details, everything but the key.)
>
> 1. The credit card details:
>
> string =
> '\x84ue\x8d\xec\x98\x02\xba<n\t\xc6\xa6\xd2\xcc\xe4O\x11\xd7\xf5\xe7\x9c\xe
>d
> *\x05\x1e\xb3h\x97V\xf8\x9a"%\xec\x14\x03r\xdd\xda\x18\xc0\x9fc\x04&J\xefF\
>x
> cd\xbc\x81\xad\xfe\xb4SV\x1a7[l\x12\xfd\xc9w\xc3u\xf4\x83tK\x1e]{\xf5/\xbfJ
>\
> x8a\xde\x18\xc2jj\xe8er\x10\x99\x1e\xeb\xa3\x86\xf0f\xb9\x95\xb5\xd8\xaaY\x
>0 8\xb8\xcdf.'
>
> 2. The decoding program
>
> def cyrep (string, key):
>
>    """To encrypt use a numeric value as the key. To decrypt use the
> negative value of the same number."""
>
>    import random
>
>    CHUNK  = 32
>
>    def process_sequence (sequence):
>       s = ''
>       for i in xrange (len (sequence)):
>          r = random.randint (0, 255)
>          s += chr ((ord (sequence [i]) + r * sign) % 256)
>       return s
>
>    def preprocess_sequence (sequence):
>       random.shuffle (sequence)
>       return sequence
>
>    sign = (key > 0) * 2 - 1
>    random.seed (abs (key * sign))
>
>    i = 0
>    s = ''
>
>    if sign > 0:
>       while i < len (string):
>          chunk = random.randint (0, CHUNK)
>          s_ = preprocess_sequence (list (string [i:i+chunk]))
>          s += ''.join (process_sequence (s_))
>          i += len (s_)
>
>    else:
>       while i < len (string):
>          chunk = random.randint (0, CHUNK)
>          s_ = list (string [i:i+chunk])
>          l = len (s_)
>          l_ = range (l)
>          s__ = l * [None]
>          o  = preprocess_sequence (l_)
>          s_ = process_sequence (s_)
>          for ii in l_:
>             s__ [o[ii]] = s_ [ii]
>          s += ''.join (s__)
>          i += l
>
>    return s
>
>
>
> ----- Original Message -----
> From: "Christos TZOTZIOY Georgiou" <tzot at sil-tec.gr>
> Newsgroups: comp.lang.python
> To: <python-list at python.org>
> Sent: Friday, May 13, 2005 11:06 AM
> Subject: Re: Encryption with Python?
>
> > On Sat, 7 May 2005 13:51:40 +0200, rumours say that "Anthra Norell"
> >
> > <anthra.norell at tiscalinet.ch> might have written:
> > >Here's the challenge. Prove this breakable
> >
> >'\x10\x88d\x1d\xba\xa1\xdcK\x05w\x02/s\xa7Q0\xeb8\xb6Gx\xef\xcb\x1e=\xf5\x
> >7
>
> f
>
> >\x9bI\xcb(\x87>\xa5\x04\xc1soF\xfd\xc6\xc6\xd9|\x971\xdb\xcdT\tw#\x86a\xdc
> >\
>
> x
>
> >b8P\xfb=n\xda\x80\x9f\x84m\x12\x98\x98\xca=o\x0b\x8e\x08O\xb7\x0b\x04SC\x9
> >6
>
> \
>
> >xc7\xab*\x0b\x996\x06\x86\x83(\x8dQ\x9eG\x8f$\xb2x)\xa9fv\x0c1B\x9b\r\xde\
> >x
>
> f
>
> > >fc\x08'
> >
> > and given that
> >
> > >I rolled my own for relatively short sequences, like passwords. The key
>
> is
>
> > >an integer. To decrypt use the negative encryption key. I consider the
> > >encryption unbreakable, as it is indistinguishable from a random
>
> sequence.
>
> > can we suppose that the encrypted text above are the details of your
> > credit card (number, name as written on it, expiry date, billing address
> > and your first dog's name)?  Do you trust the 'unbreakability' of your
> > algorithm that much?
> > --
> > TZOTZIOY, I speak England very best.
> > "Be strict when sending and tolerant when receiving." (from RFC1958)
> > I really should keep that in mind when talking with people, actually...
> > --
> > http://mail.python.org/mailman/listinfo/python-list

-- 
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/