I found a few modules out there, but they seem to be all but abandoned.
Most seem to have died several years ago. The most promising package
is A.M. Kuchling's Python Cryptography Toolkit
(http://www.amk.ca/python/code/crypto.html).
Is this the defacto Python encryption solution? What does everyone
else use? Any other suggestions? The SSLCrypto package
(http://www.freenet.org.nz/python/SSLCrypto/) may be a good alternative
too, but I am not sure if it is actively maintained.
Thanks,
Blake
http://www.nightsong.com/phr/crypto/p3.py
It uses SHA1 in OFB mode and is fairly fast for a pure Python function.
> I found a few modules out there, but they seem to be all but abandoned.
> Most seem to have died several years ago. The most promising package
> is A.M. Kuchling's Python Cryptography Toolkit
> (http://www.amk.ca/python/code/crypto.html).
Nice toolkit, more flexible and powerful than p3.py, but also more
complicated.
> I found a few modules out there, but they seem to be all but abandoned.
> Most seem to have died several years ago.
a lack of recent releases can also mean that they just work...
> Is this the defacto Python encryption solution? What does everyone
> else use? Any other suggestions?
http://sandbox.rulemaker.net/ngps/m2/
is actively maintained, as far as I can tell.
you might also be able to find some useful stuff inside:
(see the utils package for a pure-python AES implementation)
</F>
There's a pure python Blowish implementation at:
http://bofh.concordia.ca/blowfish.py
(It looks like you'll have to divide your data in 8 byte blocks
yourself, and pad the last block)
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
###
If unauthrorized use of the machine is a concern, crypt might not be an
appropriate name for the function. To help an intruder understand it, a doc
string such as the following one might be useful:
def cyrep (sequence, key):
"""
Cyclic Redundancy Preprocessor
Cyclic redundancy checks often fail to differentiate relatively
short
sequences that contain sequences of binary zeroes of different
length.
This preporcessor applies a keyed randomizing filter to improve the
capability of the cyclic redundancy algorithm. Use the output of
this
function as input to a CRC routine.
Negative keys cannot be used. If passed they are positivized
rather
than rejected.
"""
###
You're using the built-in random module which is designed to provide
only statistical randomness and not cryptographic security. It should
not be used for encryption. The math paper describing the function is
quite clear about that. There is a lot of subtlety to this stuff and
it's easy to make mistakes even if you know what you're doing. Even
using well-tested block ciphers (various people mentioned DES, AES,
and Blowfish modules) it's easy to make mistakes in choosing operation
modes, thinking you don't need authentication when you really do,
etc., etc. The book "Practical Cryptography" by Bruce Schneier and
Niels Ferguson is worth looking at if you want to see what you're
getting yourself into.
I hate to come across as plugging my own stuff too much, but
http://www.nightsong.com/phr/crypto/p3.py
is designed to take care of most of the tricky issues for you while
still having a very simple interface, and also be reasonably fast
(much faster for large messages than any of the pure Python block
cipher modules). Just use p3_encrypt(plain) to encrypt and
p3_decrypt(cipher) to decrypt. The main penalty you pay is that the
ciphertext is a couple dozen bytes longer than the plaintext. There
are cryptographically important reasons for that; don't try to escape
it without knowing exactly what's going on.
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.
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!
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."
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.
And do read _Practical Cryptography_.
--
Robert Kern
rk...@ucsd.edu
"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter
How do you know the same key was used?
What if the messages aren't the same length?
How does one reconstruct either or both of two messages from their
difference?
> 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? Is it you give me a plain text. I encrypt it
using the same keys and hand you the result? Would I comply with the
request?
> 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. 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. 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. 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 and, as it seems, would hardly be suspected by
deciphering experts for its amateurishness.
> 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?
> And do read _Practical Cryptography_.
I certainly will.
> --
> Robert Kern
> rk...@ucsd.edu
>
> "In the fields of hell where the grass grows high
> Are the graves of dreams allowed to die."
> -- Richard Harter
>
Jim
> 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.
There is a lot of information about the issues on the net. Before asking
questions, isn't it better to make some research? For example, your last
question is perfectly answered here:
<http://www.faqs.org/faqs/cryptography-faq/part02/>
"""
2.3. How do I present a new encryption scheme in sci.crypt?
``I just came up with this neat method of encryption. Here's some
ciphertext: FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it strong?'' Without a
doubt questions like this are the most annoying traffic on sci.crypt.
...
"""
I'd suggest you to start your education here before you invent yet
another "simple" solutions for a complex problem:
<http://www.faqs.org/faqs/cryptography-faq/part01/>
HTH.
--
Sergei.
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.
Regards,
Philippe
----- Original Message -----
From: "Robert Kern" <rk...@ucsd.edu>
To: <pytho...@python.org>
Sent: Saturday, May 07, 2005 3:18 PM
Subject: Re: Encryption with Python?
( snip )
> >>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).
The non-randomness of the difference is evidence of having guessed the key,
right? Why then do I need two samples? If I hack away at a single sample I
get a probably more conspicuous non-randomness twice as fast.
( snip )
> 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.
I don't doubt that, given a series (long enough), the postion can be
derived. I doubt, though, that a series is knowable, if another, unknown,
series has been added to it.
> > 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.
I thought the problem was concealing passwords from ones kids or
collaborators.
>
> 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.
I believe that a randomly distributed series utterly obliterates any
non-randomness or regularity of a second series, if the two are added. I
don't know how to produce a formal proof. It is just a hunch. It's actually
more than a hunch. It is a conviction. Not a certainty; a conviction. I'd be
delighted to be proved wrong (or right). The fact may be significant that we
module overflow back into the range.
So, if the distribution of my code is indeed random, it will display
no clue about the key and can only be broken with a brute-force attack. This
imposes a second requirement, which is that a brute-force attack outtries
the patience of a teraflop machine. The function I posted, quite obviously,
does not satisfy this second requirement. The function can easily be applied
in a manner, though, that takes care of that.
A third rquirement I cannot think of.
> 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 am not aiming at a Nobel prize and certainly don't presume to impose on
your priorities. So the term 'obligation' seems not very useful here.
>
> > 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.
Irrelevant okay, if the OP agrees.
( snip )
Best regards,
Frederic
No. Let's say you encrypt two ascii strings with the same key. The
high bit of each byte in the plaintext is zero. Therefore if you xor
the two ciphertexts together, the high bit of each byte of the result
xor'd ciphertexts will be zero. So just check for that and you've
immediately spotted the non-randomness.
> I don't doubt that, given a series (long enough), the postion can be
> derived. I doubt, though, that a series is knowable, if another, unknown,
> series has been added to it.
You have to assume that the attacker has access to known
plaintext-ciphertext pairs. For example, you might not tell someone
the password you use now, but what about some old password that you
don't use any more? If the attacker knows your old password (maybe
because your sysop set it to some default value and had you change it
on your first login), and has the encrypted version, there's a known
plaintext.
> I thought the problem was concealing passwords from ones kids or
> collaborators.
Encryption is supposed to conceal data from knowledgable attackers
willing to burn significant resources to get at the data. That might
or might not describe your friends and collaborators.
> I believe that a randomly distributed series utterly obliterates any
> non-randomness or regularity of a second series, if the two are added.
This is a meaningless statement since you don't give any definition of
"randomly distributed series".
> I don't know how to produce a formal proof. It is just a hunch. It's
> actually more than a hunch. It is a conviction. Not a certainty; a
> conviction. I'd be delighted to be proved wrong (or right).
If the keystream really can't be distinguished from random, then correct,
though there's still issues with key management (you mustn't use the same
key twice) and authentication.
Generating keystreams that are indistinguishable from random is an
extremely tricky subject, there are books and papers written about it, etc.
> The fact may be significant that we module overflow back into the
> range. So, if the distribution of my code is indeed random,
Your code used the Python built-in PRNG algorithm which is designed to
make output with similar statistical properties as actual random numbers,
for the purpose of running stuff like simulations. It makes no attempt
at all to be secure against attackers trying to figure out whether the
output is really random.
I thank you too for your response. Let me just tell you what goes
through my mind.
----- Original Message -----
From: "Paul Rubin" <"http://phr.cx"@NOSPAM.invalid>
Newsgroups: comp.lang.python
To: <pytho...@python.org>
Sent: Monday, May 09, 2005 9:45 PM
Subject: Re: Encryption with Python?
> "Anthra Norell" <anthra...@tiscalinet.ch> writes:
> > The non-randomness of the difference is evidence of having guessed the
key,
> > right? Why then do I need two samples? If I hack away at a single sample
I
> > get a probably more conspicuous non-randomness twice as fast.
>
> No. Let's say you encrypt two ascii strings with the same key. The
> high bit of each byte in the plaintext is zero. Therefore if you xor
> the two ciphertexts together, the high bit of each byte of the result
> xor'd ciphertexts will be zero. So just check for that and you've
> immediately spotted the non-randomness.
I don't follow. There is no bitwise correlation between a plain-text
character and its encoded equivalent. What's more, there is no detectable
correlation at all. Take a highly ordered plain text, such as a sting of
identical characters, e.g. 'AAAAAAAAAAAAAAA' and sequentially add a
deterministically generated random series (module 256 to keep them within
range), what you get is, quite obviously, a series of numbers that differs
from the added random series in only one respect: all values are shifted by
ord ('A'). The intervals from one byte to the next remain unchanged,
allowance made for the module 256 wrap-around. The intervals remaining
unchanged, the distribution and hence the randomness of the encryption
remains unchanged. Quite obviously, each one of the identical plain-text
characters very likely will be encrypted differently. Repeats would occur,
but they would occur randomly once every 256 times on an average.
> > I don't doubt that, given a series (long enough), the postion can be
> > derived. I doubt, though, that a series is knowable, if another,
unknown,
> > series has been added to it.
>
> You have to assume that the attacker has access to known
> plaintext-ciphertext pairs. For example, you might not tell someone
> the password you use now, but what about some old password that you
> don't use any more? If the attacker knows your old password (maybe
> because your sysop set it to some default value and had you change it
> on your first login), and has the encrypted version, there's a known
> plaintext.
Password management is certainly a problem, but of course is totally
unrelated to the quality of an encryption method.
> > I thought the problem was concealing passwords from ones kids or
> > collaborators.
>
> Encryption is supposed to conceal data from knowledgable attackers
> willing to burn significant resources to get at the data. That mightof
> or might not describe your friends and collaborators.
I agree. Depending on a situation, a solution might or might not be
adequate.
> > I believe that a randomly distributed series utterly obliterates any
> > non-randomness or regularity of a second series, if the two are added.
>
> This is a meaningless statement since you don't give any definition of
> "randomly distributed series".
No, in fact I don't. I am quite confident that the library module 'random'
produces random distributions. As to the distribution of a non-random series
added to a random series, my intuition tells me that it remains random.
> > I don't know how to produce a formal proof. It is just a hunch. It's
> > actually more than a hunch. It is a conviction. Not a certainty; a
> > conviction. I'd be delighted to be proved wrong (or right).
I don't think it would be difficult for a mathematician to prove or disprove
the hypothesis. I did come up with an informal proof. It is a function I
will add at the bottom of this message. You can copy and run it, if you have
the Image package installed.
>
> If the keystream really can't be distinguished from random, then correct,
> though there's still issues with key management (you mustn't use the same
> key twice) and authentication.
The key is the seed of the random generator.
> Generating keystreams that are indistinguishable from random is an
> extremely tricky subject, there are books and papers written about it,
etc.
I agree. I wouldn't know how to design a random generator. Fortunately I
don't need to. I can use ready made ones.
> > The fact may be significant that we module overflow back into the
> > range. So, if the distribution of my code is indeed random,
> Your code used the Python built-in PRNG algorithm which is designed to
> make output with similar statistical properties as actual random numbers,
> for the purpose of running stuff like simulations. It makes no attempt
> at all to be secure against attackers trying to figure out whether the
> output is really random.
Try out the following function. You need the Image package.
Regards
Frederic
###############################################
def informal_proof_of_randomness (text_file_name): # File must be longer
than 60K
X = 0
Y = 1
import random
NUMBER_OF_DOTS = 30000
# Make three lists to collect coordinate pairs
random_coordinates = NUMBER_OF_DOTS * [None]
plain_text_coordinates = NUMBER_OF_DOTS * [None]
encoded_text_coordinates = NUMBER_OF_DOTS * [None]
# Fill one with random numbers
for i in xrange (NUMBER_OF_DOTS):
x = random.randint (0,255)
y = random.randint (0,255)
random_coordinates [i] = ((x,y))
# Fill a second one with ascii codes (plain text)
f = file (text_file_name, 'rb')
for i in xrange (NUMBER_OF_DOTS):
# No check if file runs out prematurely. Make sure it's at least 60K
x = ord (f.read (1))
y = ord (f.read (1))
plain_text_coordinates [i] = ((x,y))
f.close ()
# Fill a third one with the sum of the two previous ones (proposed cipher
text)
for i in xrange (NUMBER_OF_DOTS):
encoded_text_coordinates [i] = \
(random_coordinates [i][X] + plain_text_coordinates [i][X]) % 256,
\
(random_coordinates [i][Y] + plain_text_coordinates [i][Y]) % 256
import Image
WHITE = 1
BLACK = 0
# Make three images to visualize the distribution
random_image = Image.new ('1', (256,256), WHITE)
text_image = Image.new ('1', (256,256), WHITE)
encoded_text_image = Image.new ('1', (256,256), WHITE)
for coordinate in random_coordinates:
random_image.putpixel (coordinate, BLACK)
for coordinate in plain_text_coordinates:
text_image.putpixel (coordinate, BLACK)
for coordinate in encoded_text_coordinates:
encoded_text_image.putpixel (coordinate, BLACK)
# Visualize the distributions
random_image.show () # Looks like rain on a pavement
text_image.show () # Does not at all
encoded_text_image.show () # See for yourself
##############
Your question was how could you tell if two ciphertexts were encrypted
with the same key. Answer: suppose both plaintext are ascii strings.
Then both plaintexts have 0 as the top bit of every byte. So do this:
x = ciphertext1 xor ciphertext2
If ciphertext1 and ciphertext2 were encrypted with two different keys,
the top bit of x's bytes will be random-looking. If ciphertext1 and
ciphertext2 were encrypted with the same key, the top bit of each of
x's bytes will be 0. So just check whether the top bit of x is always
0. If it is, then ciphertexts 1 and 2 were probably encrypted with
the same key.
> Password management is certainly a problem, but of course is totally
> unrelated to the quality of an encryption method.
You're ignoring your own question. With a good encryption scheme,
finding out an old password doesn't tell you anything about new
messages. With your encryption scheme, finding out an old password
leaks information about the new one.
> I agree. Depending on a situation, a solution might or might not be
> adequate.
Since good encryption schemes that don't have significant performance
penalties are widely available, why mess with a crap scheme EVER? Why
use a solution that "might or might not be adequate" when you can use
one that's definitely ok?
> No, in fact I don't. I am quite confident that the library module 'random'
> produces random distributions.
The author of the algorithm doesn't agree with you. The documentation
is very explicit, it's no good for cryptography, and if you study how
it works you can see that it's easily distinguishable from random.
> I don't think it would be difficult for a mathematician to prove or
> disprove the hypothesis.
It's true of a genuine random keystream, but that's not what we're
talking about. We're talking about the output of python's random
module, which is not of cryptographic quality. It's fine for
statistical simulations in that it doesn't have correlations that are
likely to accidentally cause trouble. It's no good for defeating
adversaries who are looking for correlations on purpose. Lots of
people don't understand the difference. Please see the book "Security
Engineering" by Ross Anderson to get an idea of what you're up against.
> > Generating keystreams that are indistinguishable from random is an
> > extremely tricky subject, there are books and papers written about
> > it, etc.
>
> I agree. I wouldn't know how to design a random generator. Fortunately I
> don't need to. I can use ready made ones.
There are good ready ones available, but the one you're proposing to
use is not one of them and was not designed to be.
> Try out the following function. You need the Image package.
That doesn't prove a thing.
> ......
> Since good encryption schemes that don't have significant performance
> penalties are widely available, why mess with a crap scheme EVER? Why
> use a solution that "might or might not be adequate" when you can use
> one that's definitely ok?
> ......
Why indeed?---Why run a marathon? Why have kids? Why shave? Why play chess?
Why sprinkle the lawn? Or as my friend Sergio's favorite line went: Why you
jerks cook your own muck when there are so many good restaurants in town?
His was definitely the best when it went out of business.
Regards
Frederic
To demonstrate your physical supremacy over your inferiors.
> Why have kids?
Because you forgot to wear protection.
> Why shave?
Your wife insists? Mine does...
> Why play chess?
To demonstrate your intellectual supremacy over your inferiors.
> Why sprinkle the lawn?
Too much beer and there's a line-up to use the john?
> Or as my friend Sergio's favorite line went: Why you
> jerks cook your own muck when there are so many good restaurants in town?
To demonstrate your culinary supremacy over your inferiors?
> His was definitely the best when it went out of business.
(Hmm... so is my business doing merely "well" if it's losing money?)
Back to Paul's question then: why use an unreliable and
probably-useless-for-all-but-spawning-lengthy-but-educational-threads
encryption method when there are relatively reliable and, uh, less
discussed and non-edifying, uh... well, you get the picture. ;-)
-Peter
> Back to Paul's question then: why use an unreliable and
> probably-useless-for-all-but-spawning-lengthy-but-educational-threads
> encryption method when there are relatively reliable and, uh, less
> discussed and non-edifying, uh... well, you get the picture. ;-)
Well, I'd say ARCFOUR has been discussed a hell of a lot more than what
this thread ever mustered up. I also submit that implementing ARCFOUR or
studying p3.py would be a hell of a lot more educational than posting a
lousy algorithm, calling it unbreakable, and responding to criticisms
with "I don't understand so you must be wrong."
Education is a process one must engage in. You don't just step in it.
The education to which I was referring was that which _most_ of us just
received by reading Paul's and your replies, not from anything in the
OP's postings. ;-)
-Peter
>>Education is a process one must engage in. You don't just step in it.
>
> The education to which I was referring was that which _most_ of us just
> received by reading Paul's and your replies, not from anything in the
> OP's postings. ;-)
Okay, I'll buy that. :-)
>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'
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...
You can google your questions and you will find them out answered in
many
cryptography FAQs. For a less mathematical, but entertaining treatise
on
cryptography, read Simon Singh's "The Code Book". You will definitely
appreciate how the various crypto algorithms through the history of
mankind
were broken and what is the state of the art in the field.
I am a very happy user of http://www.amk.ca/python/code/crypto.html
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\xed
*\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\x0
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" <tz...@sil-tec.gr>
Newsgroups: comp.lang.python
To: <pytho...@python.org>
Sent: Friday, May 13, 2005 11:06 AM
Subject: Re: Encryption with Python?
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
>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."""
> > --
> > http://mail.python.org/mailman/listinfo/python-list
--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095
>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.
I would never whack someone over the head (WSOTH) who tries to develop
an idea of his own, and never will (intentionally at least --I myself
like reinventing the wheel once in a while just to make sure my synapses
still work). However I do WSOTH for
>>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.
So, to be clear, my reason was your declaring that "I consider the
encryption unbreakable, as it...", and that is why I actually challenged
you to either support the unbreakability of your algorithm by supplying
sensitive data for you, or back off and simply say "ok guys, my words
were a *little* over the top".
That's all. I see you took up the challenge and indirectly replied to
my last question, and in good spirit I say you earned a little respect
from me, at least for standing up to your words. Now I hope no-one
gives a try to your data (for your own sake :)
I don't think the challenge was really accepted. The algorithm
changed between when you issued the challenge, and when the sensitive
data went up. A good algorithm doesn't need to change depending on
the data. I agree with the poster who said that the strength of
either one of the algorithms is irrelevant, if the keyspace is just 32
bits.
You are correct; the algorithm changed, and the OP admitted it himself
in the post with the encrypted credit card data.
However, on a practical level: before posting, I did a quick comparison,
and the only effective change to OP's algorithm was a the addition of a
`random.shuffle(sequence)', which AFAIU has no practical consequences as
to whether his algorithm is unbreakable or not.
I could say that "hey, you changed the algorithm, and that means your
previous declaration of unbreakability wasn't." but honestly I was
overwhelmed by the audacity (and foolishness, if these are truly his
credit card data) of Frederic.
ObSF: DNA; The Restaurant At The End Of The Universe; Marvin the
paranoid android faces a gigantic black tank in the H2G2 HQ.
Isn't it remarkable that it takes "foolishness" to earn "a little
respect".
Anyway, even as I write this, my account balance stands unchanged at
... no, come to think of it, the account balance is definitely not a part of
the problem. I will volunteer the information, though, that the credit card
is a debit card and is good for up to the balance of the account. In
addition, I did contemplate a brute force attack. I also contemplated my
belief that it takes no more than a few lines of code to keep a teraflop
machine busy for a few billion years. So I would not discourage decoding
attempts but will state that the game as I understand it does not have any
implicit rules.
Regards
Frederic
(I am not the OP. The OP was Blake T. Garretson who never returned, but
whose problem I still consider the standard by which I wish my idea to be
judged. I never intended to dabble in commercial cryptography.)
----- Original Message -----
From: "Christos TZOTZIOY Georgiou" <tz...@sil-tec.gr>
Newsgroups: comp.lang.python
To: <pytho...@python.org>
Sent: Friday, May 27, 2005 11:52 AM
Subject: Re: Encryption with Python?