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" <[EMAIL PROTECTED]> > To: <python-list@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 [EMAIL PROTECTED] "In the fields of hell where the grass grows high Are the graves of dreams allowed to die." -- Richard Harter -- http://mail.python.org/mailman/listinfo/python-list
