Encryption with Python?

[Robert Kern]

Anthra Norell wrote:
> Thanks a lot for the feedback. This is certainly a great learning
> experience. It's a fascinating topic too. Without wishing to annoy, I'd be
> interested in knowing more. I insert questions below.
> 
> ----- Original Message -----
> From: "Robert Kern" <rkern at ucsd.edu>
> To: <python-list at python.org>
> Sent: Saturday, May 07, 2005 11:11 AM
> Subject: Re: Encryption with Python?
> 
> 
> 
>>Anthra Norell wrote:
>>
>>>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.
> 
>>>Frederic
>>>
>>>###
>>>
>>>def crypt (sequence, key):
>>>   import random
>>>   sign = (key > 0) * 2 - 1
>>>   random.seed (abs (key * sign))
>>>   s = ''
>>>   for i in xrange (len (sequence)):
>>>      r = random.randint (0, 255)
>>>      s += chr ((ord (sequence [i]) + r * sign) % 256)
>>>   return s
>>
>>The mind boggles.
>>
>>You do realize that if I have two ciphertexts encrypted with the same
>>key, I can subtract them? Then I have a sequence, that while not
>>immediately readable, is just a straightforward combination of the two
>>plaintexts without any encryption.
> 
> How do you know the same key was used?

I don't necessarily, but if the same key *is* used, I'll know. The 
differences of the ciphertexts will have distinctly non-random 
characteristics (well, assuming the plaintexts aren't one-time pads 
themselves).

> What if the messages aren't the same length?

Then I just look at the common portion.

> How does one reconstruct either or both of two messages from their
> difference?

Analyzing patterns, frequencies, and also using prior knowledge I may 
know or guess about the contents. This is only slightly worse (for the 
attacker) than tackling a straight substitution cipher.

>>This function is also vulnerable to a chosen-plaintext attack. The
>>underlying PRNG is definitely not suitable for cryptographic
>>applications. The documentation even says so!
> 
> What is a plain-text attack?

"Chosen-plaintext," please.

> Is it you give me a plain text. I encrypt it
> using the same keys and hand you the result?

More or less.

> Would I comply with the
> request?

Depending on how your cryptosystem is deployed, you may not have a 
choice. A cryptosystem ought to be resistent to chosen-plaintext attacks 
regardless of how you intend to deploy it.

>>http://docs.python.org/lib/module-random.html
>>"However, being completely deterministic, it is not suitable for all
>>purposes, and is completely unsuitable for cryptographic purposes."
> 
> The logic escapes me if it is understood to mean that cryptography, in order
> to be usable, has to be indeterministic.

The two characteristics "completely deterministic" and "unsuitable for 
cryptographic purposes" are only mildly related. One *definitely* 
wouldn't use any PRNG to generate keying material. You should rely on 
physical sources of randomness. Most modern OSes have some way to access 
reliable entropy from your machine. Unices usually have this as 
/dev/random. But that's a separate issue.

Additionally, one should not use the Mersenne Twister PRNG, which is 
what Python uses, as the PRNG for the stream cipher. Given a particular 
value or series of values, it is possible to determine one's position in 
the PRNG sequence and can, in essence derive the key. Some techniques 
can be used to hide actual current state of the PRNG like applying a 
cryptographic hash to the value from the PRNG. However, it's easier and 
far better to just use a cryptographically strong PRNG from the start.

> If, however, it is meant to suggest
> that it is the reversible, direct one-on-one relation between all the
> characters of a plain text and its encryption that falls short of
> state-of-the-art technology, I'd have no problem with that. That doesn't
> mean, however, that an exercise is required to measure up to
> state-of-the-art standards in order to be taken seriously. I do invent my
> own solutions for simple problems.

This is not a simple problem.

But fortunately, there *is* a relatively simple answer. Besides Paul 
Rubin's p3.py (which to my limited ability to determine is probably 
"best-of-breed" for the limits imposed upon it), there is a very 
simply-coded stream cipher that *is* cryptographically strong if the 
appropriate details are observed. It's called RC4 (or ARCFOUR). A 
reasonably good cryptosystem built around that cipher is called 
Ciphersaber-2.

http://ciphersaber.gurus.com/cryptanalysis.html

There are dozens of implementations floating around, but it's 
ridiculously easy to code up by yourself.

> I find it more challenging than stalking
> other people's solutions how ever superior and typically it also saves me
> time. It is not my ambition to excel in any field, nor to flaunt my
> erudition. It is my ambition to satisfy the requirements of a given task.
> And this, I think, my solution does. I can be wrong and if so, I'd
> appreciate being proven wrong. I have now received well-meaning advice for
> which I am grateful. But I haven't been proven wrong.

You haven't proved your claim that your cipher is "unbreakable." Your 
notion of "unbreakable" is also flawed; "indistinguishable from 'random' 
sequences" is only one part of cryptosystem security. For that matter, 
you haven't proven that the ciphertexts produced are "indistinguishable 
from random sequences." Note the plural. It's important.

You have a positive obligation to back your claim. I've pointed you to 
two obvious attacks that can be made against your system and also to 
resources that you can read to improve your knowledge of the issues. I 
*don't* have an obligation to spend more of my time meeting your 
arbitrary challenge. My reluctance to do so is not support for your claim.

> I claim that my
> solution satisfies the requirements of the task at hand and challenge anyone
> to prove the contrary. You can meet the challenge by deciphering the
> following tiny message, knowing now the encryption method, which in practice
> would not be known

Bull. And irrelevant.

Kerckhoffs' Principle
"A cryptosystem should be secure even if everything about the system, 
except the key, is public knowledge."

http://en.wikipedia.org/wiki/Kerckhoffs'_principle

> and, as it seems, would hardly be suspected by
> deciphering experts for its amateurishness.

This is not something to rely upon.

>>Do yourself a favor and don't try to roll your own cryptographic
>>functions. Do everyone else a favor and don't call something
>>"unbreakable" unless you actually have the domain expertise to make that
>>determination.
> 
> Here's the challenge. Prove this breakable
> 
> '\x10\x88d\x1d\xba\xa1\xdcK\x05w\x02/s\xa7Q0\xeb8\xb6Gx\xef\xcb\x1e=\xf5\x7f
> \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\x96\
> xc7\xab*\x0b\x996\x06\x86\x83(\x8dQ\x9eG\x8f$\xb2x)\xa9fv\x0c1B\x9b\r\xde\xf
> fc\x08'
 >
> When you give up we may try a plain-text attack. Okay?

I have better things to do with my time. It's not me that needs to prove 
anything. You came here and made a claim. I am asking you to back it up. 
Until you do so, you don't have much right to challenge me to prove 
anything.

>>And do read _Practical Cryptography_.
> 
> I certainly will.

-- 
Robert Kern
rkern at ucsd.edu

"In the fields of hell where the grass grows high
  Are the graves of dreams allowed to die."
   -- Richard Harter