Cryptography-Digest Digest #154, Volume #12 Mon, 3 Jul 00 19:13:01 EDT
Contents:
Quantum Computing (Was: Newbie question about factoring) ("Paul E. Black")
Re: Decrypting MD5 (Steve Rush)
Re: cray and time needed to attack (Jerry Coffin)
Re: A thought on OTPs (Simon Johnson)
Re: Cooking up MAC keys (David A. Wagner)
Re: cray and time needed to attack (jungle)
Re: Hashing Function (not cryptographically secure) (David A. Wagner)
Re: Hashing Function (not cryptographically secure) (David A. Wagner)
Re: cray and time needed to attack ("Douglas A. Gwyn")
Re: Blowfish for signatures? (David A Molnar)
Re: Security of this F-Function (David A. Wagner)
Re: A thought on OTPs ("Tony T. Warnock")
Re: A thought on OTPs ("Joseph Ashwood")
TC5 Completed Paper (tomstd)
Re: A thought on OTPs (S. T. L.)
Re: Encryption and IBM's 12 teraflop MPC...... ("Harvey Rook")
Re: Security of this F-Function (Simon Johnson)
Re: A thought on OTPs ("Douglas A. Gwyn")
Re: Compression & Encryption in FISHYLAND (Kurt Shoens)
Re: TC5 Completed Paper ("Joseph Ashwood")
Re: SCOTT19U.ZIP_GUY **** PLONK! **** (Simon Johnson)
Re: Quantum Computing (Was: Newbie question about factoring) (Nick Maclaren)
Re: Security of this F-Function ("Joseph Ashwood")
----------------------------------------------------------------------------
From: "Paul E. Black" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Quantum Computing (Was: Newbie question about factoring)
Date: Mon, 03 Jul 2000 15:20:31 -0400
Nick Maclaren wrote:
> However, some people believe that building a quantum computer is
> an exponentially complex problem,
Interesting. Could you give more details, for instance, who believes
that or what goes into it? For instance, is it that designing a
quantum computer is exponentially complicated, or constructing it
(an exponential number of steps needed)?
-paul-
--
Paul E. Black ([EMAIL PROTECTED])
------------------------------
From: [EMAIL PROTECTED] (Steve Rush)
Subject: Re: Decrypting MD5
Date: 03 Jul 2000 20:31:07 GMT
>Eh ? Where did you get that idea from ?
>
>A hard to predict key schedule is in no way a guarantee for a good
>cipher,
But I was referring to cyphers built around secure hash functions. These are
essentially stream cyphers that use the hash function to generate the
keystream. If you do it right, you get a good cypher.
==========================================================================
==============
If it's spam, it's a scam. Don't do business with Net abusers.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Mon, 3 Jul 2000 14:36:57 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> i want to know how many time is need to a cray to crack a:
> 1° 128 bit key with idea
> 2° 1024 bit key with blowfish
A Cray would NOT be the weapon of choice in either of these attacks.
Instead, you'd want to use specialized custom hardware. Unless
somebody finds a HUGE break in the ciphers themselves it doesn't make
any real difference though: it would take millions of years to
exhaust the keyspace of either one. Oh, and just FWIW, Blowfish only
accepts keys of up to 448 bits, but even at that nothing approaching
a practical attack is known at the present time.
> 3° 128 bit key with RSA
By contrast, this is so trivial that there's no real reason to use a
Cray at all -- with an average desktop or laptop, factoring a 128-bit
number will take less time than it takes you to type in the number.
If you intended to say 128 decimal digits instead of 128 bits, then
at least you've got something secure enough that you might consider
sing it. Somebody with plenty of talent and money could still break
it, but the best people and computers available would still take a
few months to do the job.
> 4° 1024 bit key with DH
This borders on being theoretically possible with present technology,
but the attacker would have to be willing to dump millions of dollars
into the project, and even at that it would NOT be completed very
quickly -- think in terms of years, not months.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 03 Jul 2000 20:30:51 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Darren New wrote:
> > As I said, this doesn't really change anything, but for people who
have
> > trouble seeing why the OTP is provably secure, the idea that the
first thing
> > you generate is the cyphertext and the second thing you generate is
the key
> > might be interesting.
>
> More likely it is just confusing, since it abuses the standard
> usage for the terms "key" and "ciphertext".
>
I agree with you, but i, and i'm sure the original poster does, find it
hard to put it down in writing how the OTP is secure. Does anyone know
of a clear cut explanation for me to copy :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Cooking up MAC keys
Date: 3 Jul 2000 12:54:32 -0700
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> Is the method of using the session key (key used to actually encrypt the
> data to be sent) with every other nibble complemented (XORed with
> 0xf0f0f0f...) a good way of generating a key for use as a MAC using the
> same encryption algorithm (in CBC-MAC mode) used to encrypt the data
> itself?
No.
Use independent encryption and MAC keys. It's cheap, it's easy,
it's safe -- I see no reason to do anything else.
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Mon, 03 Jul 2000 16:43:04 -0400
Mist wrote:
> a friend told me it need less than a week to crack a 128 bit IDEA key
> with a cray, does its right?
no ...
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Hashing Function (not cryptographically secure)
Date: 3 Jul 2000 13:04:08 -0700
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> It's bad ... don't use it; use a 64-bit CRC instead.
No, no, don't use a CRC for cryptographic purposes; in most
cryptographic contexts, CRC's are insecure.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Hashing Function (not cryptographically secure)
Date: 3 Jul 2000 13:07:44 -0700
In article <[EMAIL PROTECTED]>,
Mack <[EMAIL PROTECTED]> wrote:
> Since the CRC-16 and CRC-CCITT (0x11005 & 0x11021) both detect all
> 2 bit changes that is impossible.
Nonsense. No fixed-output-length checksum can detect all 2-bit changes
on all arbitrary-length inputs, as can be verified with a straightforward
information-theoretic argument.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Mon, 3 Jul 2000 20:26:33 GMT
Doug Kuhlman wrote:
> The whole question kind of revolves around what you mean by "to crack",
> what methods are being used, etc. Which Cray?
More importantly, whose Cray?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Blowfish for signatures?
Date: 3 Jul 2000 20:45:09 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Yes. Look up `Rabin's One-Time Signature Scheme' in a good crypto book,
> such as HAC. With a symmetric cipher (such as Blowfish), and a hash
> function (such as Blowfish in abreast Davies-Meyer, if you've got all
> day spare), you can use this cunning signature system which will allow
> you to sign one message for each key, which may be verified once.
Isn't that Merkle's one-time signature scheme? Or was it just Merkle who
came up with the idea of hash trees to make this efficient given a single
published value?
-dmolnar
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Security of this F-Function
Date: 3 Jul 2000 13:13:20 -0700
In article <8jql2f$t51$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> I was asked by a friend to design a cheap and nasty encryption
> algorithm for his computing project.
Then you've probably already lost the battle for security, if you try
to fulfill this request.
Answering the question your friend asked would probably be a disservice.
Instead, I strongly recommend him to use a standard encryption algorithm,
such as 3DES or Blowfish or RC4 or TEA. What's the matter with them?
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 03 Jul 2000 15:10:48 -0600
Reply-To: [EMAIL PROTECTED]
Simon Johnson wrote:
> I agree with you, but i, and i'm sure the original poster does, find it
> hard to put it down in writing how the OTP is secure. Does anyone know
> of a clear cut explanation for me to copy :)
A simple version is to note that the characters of the key are independent
and identically uniformly distributed. Thus the probability of getting a
particular cyphertext character is independent of the corresponding
plaintext character and of the position in the message. This is based on
the fact that a convolution of a uniform distribution and any other
distribution on a circle is the uniform distribution.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 3 Jul 2000 14:09:29 -0700
What kind of person do you want this explanation for? It is easy to write a
definition targeted at each type of person, that will lead them to see why
it should be secure, but each one will be such that it will be difficult for
others to see. For example:
a XOR b can not decrease the entropy of the value below the entropy of a
a XOR b can not decrease the entropy of the value below the entropy of b
is quite clear for a mathematically educated person, for a layman however it
is quite unclear, for a layman the statement:
a XOR b produces a value at least as random as a and b
is more clear and will have approximately the desired meaning, although the
mathematically inclined will almost immediately realize that the statement
is false.
The desired stament is a very important step in establishing OTP as secure
(when using XOR). It definitely needs to have a target audience.
Joe
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:8jqt5r$3d8$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > Darren New wrote:
> > > As I said, this doesn't really change anything, but for people who
> have
> > > trouble seeing why the OTP is provably secure, the idea that the
> first thing
> > > you generate is the cyphertext and the second thing you generate is
> the key
> > > might be interesting.
> >
> > More likely it is just confusing, since it abuses the standard
> > usage for the terms "key" and "ciphertext".
> >
> I agree with you, but i, and i'm sure the original poster does, find it
> hard to put it down in writing how the OTP is secure. Does anyone know
> of a clear cut explanation for me to copy :)
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Subject: TC5 Completed Paper
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 03 Jul 2000 14:15:57 -0700
At my website you can find the completed TC5 paper and
cryptanalysis. The package includes TC5 optimized and reference
C source code and the paper describes conventional cryptanalysis
of the cipher.
So far it's immune to conventional cryptanalysis.
http://www.geocities.com/tomstdenis/files/tc5.zip
and the paper separately
http://www.geocities.com/tomstdenis/files/tc5.ps
Please CC comments to "[EMAIL PROTECTED]" since I am still on
an inet blackout.
And Adam please add TC5 to the contest. Thanks.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: A thought on OTPs
Date: 03 Jul 2000 21:26:41 GMT
If you need such a cruddy explanation to understand the OTP, then you do not
understand the OTP.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
Pages up: 407 Quotes, 31 reviews of 168 science books, and a review of
the Foundation series. Newest Page: S.T.L.'s Fighter Jet Paper Airplane!
------------------------------
From: "Harvey Rook" <[EMAIL PROTECTED]>
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Mon, 3 Jul 2000 14:45:46 -0700
"Casper H.S. Dik - Network Security Engineer" <[EMAIL PROTECTED]>
wrote in message news:8jlgi8$n6p$[EMAIL PROTECTED]...
> "Harvey Rook" <[EMAIL PROTECTED]> writes:
>
> >If someone put this thing to work brute forcing passwords, it could break
40
> >bit RC4 in a second.
>
> Only if it had an "rc4 & compare result" instruction (or could do so
> in 8 instructions)
>
> (But a "very short time to crack RC4-40" would be correct)
>
True, but the calculations are certainly off by no more than 100 orders of
magnitude. 100 seconds is still enough to pronounce 40 bit keys as very
insecure.
Harv.
------------------------------
Subject: Re: Security of this F-Function
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Mon, 03 Jul 2000 14:52:10 -0700
>Answering the question your friend asked would probably be a
disservice.
>Instead, I strongly recommend him to use a standard encryption
algorithm,
>such as 3DES or Blowfish or RC4 or TEA. What's the matter with
them?
In normal senerio's, yup, you're 100% correct. Examinations
however, are quite different from real world cryptography.
Here we've got a Mircosoft Access Database with 50 Fake names
and addresses in it, and all my friend wants is a mark for
saying the database is encrypted, and showing documentation on
the algorithm. Your not gonna implement 3-DES for that, since
the data is worth nothing, and you would get same number of
marks for using XOR. Okay, so why not use XOR? The catch is, the
algorithm has to be original or the marks can be deducted. Hence
a cheap and nasty algorithm has the optiminal in this situation.
I'm sorry, i've ranted on about trivial stuff :)
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Mon, 3 Jul 2000 21:21:31 GMT
Simon Johnson wrote:
> I agree with you, but i, and i'm sure the original poster does, find it
> hard to put it down in writing how the OTP is secure. Does anyone know
> of a clear cut explanation for me to copy :)
David Kahn gives a very good one in "The Codebreakers".
------------------------------
From: [EMAIL PROTECTED] (Kurt Shoens)
Subject: Re: Compression & Encryption in FISHYLAND
Date: 3 Jul 2000 15:10:55 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>For example, it's easy to visualise circumstances where the keyspace is
>reduced so that a brute-force search would is possible, but fails for
>lack of a halting criterion that uniquely establishes the correct plaintext.
>This might happen (for example) if the plaintext is relatively short.
So let's make sure I understand your point: using 1-1 compression is
useful in cases where:
a) You've done such a poor job of key management that brute force is
practical
... and ...
b) The uncompressed plaintext of the message is indistinguishable
from random
This confirms my suspicion that 1-1 compression is a solution in search
of a problem.
There's really no recovery from poor key management. If you give your
adversaries the possibility of brute force search, you've lost the
battle. Why bother encrypting at all then?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: TC5 Completed Paper
Date: Mon, 3 Jul 2000 15:16:55 -0700
I've taken a brief look at it, and I must say that except for the speed
(which can be worked on), it's actually a rather nice cipher. I do slightly
disagree with some of your analysis (I showed you before that the equations
for even linear analysis aren't always correct), so for security I'd
recommend upping the rounds to 10, which would of course slow it more, but
it looks like a good amount of hardware could be thrown at it easily. It's
definitely a very good cipher for such a relatively early development for
you (in terms of your age, and in terms of you time spent learning). I'll do
some more looking at it tonight.
Joe
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> At my website you can find the completed TC5 paper and
> cryptanalysis. The package includes TC5 optimized and reference
> C source code and the paper describes conventional cryptanalysis
> of the cipher.
>
> So far it's immune to conventional cryptanalysis.
>
> http://www.geocities.com/tomstdenis/files/tc5.zip
>
> and the paper separately
>
> http://www.geocities.com/tomstdenis/files/tc5.ps
>
> Please CC comments to "[EMAIL PROTECTED]" since I am still on
> an inet blackout.
>
> And Adam please add TC5 to the contest. Thanks.
>
> Tom
>
>
> -----------------------------------------------------------
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
------------------------------
Subject: Re: SCOTT19U.ZIP_GUY **** PLONK! ****
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Mon, 03 Jul 2000 15:22:20 -0700
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>Come on, don't do that, just think of it as humor, besides it's
at least
>more interesting than Szopa. Actually DS occassionally says
something
>interesting, occassionally comes up with something above a 3rd
grade level,
>occassionally gives us reason to believe he's a psychotic 9
year old, or
>maybe to believe he just needs some psychological counseling,
but I don't
>think it's worth PLONKing him over. Just laugh and skim what he
writes for
>something worth thinking about, and ignore the personal insults
he sputters
>out, unless you're the target, then it's a right of passage.
> Joe
>
>"Guy Macon" <[EMAIL PROTECTED]> wrote in message
>news:8jo49p$[EMAIL PROTECTED]...
>> **** PLONK! ****
i can't remember who said it but this is and excellent
situtation to use:
#include <stdinsult.h>
:) - From the posts i've read by him, he seems slightly
arrogant, but hey, who isn't? - Remeber he is entitled to his
opinion, if you really don't like him, then don't read his posts.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 3 Jul 2000 22:27:55 GMT
In article <[EMAIL PROTECTED]>,
Paul E. Black <[EMAIL PROTECTED]> wrote:
>Nick Maclaren wrote:
>> However, some people believe that building a quantum computer is
>> an exponentially complex problem,
>
>Interesting. Could you give more details, for instance, who believes
>that or what goes into it? For instance, is it that designing a
>quantum computer is exponentially complicated, or constructing it
>(an exponential number of steps needed)?
It is some of my physicist colleagues. The problem is converting
a sequence of bits (i.e. an integer) into the same number of
predetermined simultaneous quantum states. And, of course, the
converse. It is less than clear how to do this, or how complex a
problem it is.
I believe that the current state of the art is 4 bits, but the
limit may have been pushed a bit further since I heard.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Security of this F-Function
Date: Mon, 3 Jul 2000 15:54:03 -0700
Well, if you don't mind hedging a bit on what is done, hijack the f() from
another algorithm, but if there's no need for security, go ahead and use the
f() you gave, it's not gonna offer great security, but it'll offer enough to
get the points.
Joe
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> >Answering the question your friend asked would probably be a
> disservice.
> >Instead, I strongly recommend him to use a standard encryption
> algorithm,
> >such as 3DES or Blowfish or RC4 or TEA. What's the matter with
> them?
>
> In normal senerio's, yup, you're 100% correct. Examinations
> however, are quite different from real world cryptography.
> Here we've got a Mircosoft Access Database with 50 Fake names
> and addresses in it, and all my friend wants is a mark for
> saying the database is encrypted, and showing documentation on
> the algorithm. Your not gonna implement 3-DES for that, since
> the data is worth nothing, and you would get same number of
> marks for using XOR. Okay, so why not use XOR? The catch is, the
> algorithm has to be original or the marks can be deducted. Hence
> a cheap and nasty algorithm has the optiminal in this situation.
>
> I'm sorry, i've ranted on about trivial stuff :)
>
>
> -----------------------------------------------------------
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
