Cryptography-Digest Digest #327, Volume #10 Tue, 28 Sep 99 23:13:02 EDT
Contents:
Re: public/private/session keys (jerome)
Re: books on discrete logarithm problem (Jerry Coffin)
Re: Help me! Please give me CAVE algorithm. (David Wagner)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (Richard D.
Latham)
Re: Electronic envelopes ("Richard Parker")
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (David Wagner)
Re: msg for Dave Scott (jerome)
Re: Need advice for encrypting information (Tom St Denis)
Re: Perfect Shuffle Algorithm? ("David Franklin")
Re: Please review proposed rebuttal... (jerome)
Re: msg for Dave Scott (JPeschel)
Re: Increasing password security dramatically without making it harder to remember
(Johnny Bravo)
Re: Compress before Encryption (Tim Tyler)
ECDL and distinguished points (jerome)
Re: hidden channel in Peekboo (wtshaw)
Re: Relating cyrptology to factoring? (wtshaw)
Re: Requirement for Uniqueness in Decryption Keys (wtshaw)
Re: Perfect Shuffle Algorithm? (wtshaw)
Re: Perfect Shuffle Algorithm? (Johnny Bravo)
Re: Perfect Shuffle Algorithm? (Johnny Bravo)
Re: Perfect Shuffle Algorithm? (Johnny Bravo)
Re: msg for Dave Scott (JPeschel)
Re: msg for Dave Scott (Tom St Denis)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: public/private/session keys
Reply-To: [EMAIL PROTECTED]
Date: Tue, 28 Sep 1999 23:23:05 GMT
how both part can have the same salt ?
i wonder because the salt depend on the current time.
On Tue, 28 Sep 1999 16:51:34 GMT, Tom St Denis wrote:
>
>Si = SHA(k + SALTi)
>
>Where i is the current index into the salt. Think of it this way. The salt
>is 64-bits this means you can have 2^64 variations (or session keys) as long
>as there are no collisions in SHA.
>
>In Peekboo the SALT is found by xoring some of the hash + time to get
>
>SALT1 = h1 xor h2 xor h3 xor time_in_seconds
>SALT2 = h4 xor h5 xor time_in_milliseconds
>
>SALT = SALT1 + SALT2 (concatenation)
>
>I hope this clears it up, and if anybody has any questions or comments plase
>ask me here or in private. BTW I know about the bday paradox and I figured
>nobody is going to send the avg 2^32 messages to make it a problem anyways..
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: books on discrete logarithm problem
Date: Tue, 28 Sep 1999 17:18:47 -0600
In article <45bI3.37$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> > Have you read through chapter three of "Handbook of Applied
> > Cryptography" ? That would be an obvious place to start, especially
> > since it's available online for free.
>
> Now that it is completely free, I have to wonder what I payed $70+ US for.
A nice, readable copy that you don't have to sit at the computer (or
spend ridiculous time at the laser printer) to read. In addition, (at
least IMO) the price of a good book is usually a reasonable price to
pay for supporting the production of more good books. At the same
time, doing our best to buy only good books gives publishers incentive
to weed out the garbage instead of publishing everything and seeing
which ones we'll buy...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Help me! Please give me CAVE algorithm.
Date: 28 Sep 1999 16:09:54 -0700
In article <f9lkWsXC$[EMAIL PROTECTED]>, bee16 <[EMAIL PROTECTED]> wrote:
> I need articles about CAVE algo.
Here are two:
Millan, W., ``Cryptanalysis of the Alleged CAVE Algorithm,''
ICISC'98, Korea, December, 1998.
http://www.replay.com/mirror/cave/index.html
Next time do a literature search first!
------------------------------
From: [EMAIL PROTECTED] (Richard D. Latham)
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 18:33:13 -0500
[EMAIL PROTECTED] (DJohn37050) writes:
> The known best method to attack a 512-bit RSA key took less total work than the
> known best method to attack a 97-bit ECC key. And the ECC attack was lucky.
> Don Johnson
Don, I understand that you can't really draw much of a curve from one
data-point ... but doesn't it worry you just slightly that a challenge
encypherment from someone who is assumed to be quite knowledgeable in
the details of the cryptosystem in question turns out to "just
happened to be 1 to 2 orders of magnitude easier" than you'd have
predicted, a priori ?
... or is there some inherent lack of strength with this cryptosystem
that only begins surfacing at key-sizes above ~9x bits ?
More significantly, I guess, is "if the next ECDL challenge cipher
turned out to be solved with significantly ( 1 to 2 OOM ) lower work
factor than predicted", would you then be getting nervous ?
--
#include <disclaimer.std> /* I don't speak for IBM ... */
/* Heck, I don't even speak for myself */
/* Don't believe me ? Ask my wife :-) */
Richard D. Latham [EMAIL PROTECTED]
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Electronic envelopes
Date: Tue, 28 Sep 1999 23:33:36 GMT
"Richard Parker" <[EMAIL PROTECTED]> wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>> Could the vulnerability of the (presumably continued) connection
>> between the time server and the client be an issue?
>
> The protocol does not require a persistent connection between the time
> server and the message receiver. The receiver need only communicate
> with the time server on or after the release-time.
It is probably obvious to you, but I guess I should point out that an
adversary who can intercept and modify the communications between the
time server and the receiver can prevent the receiver from opening the
envelope. This adversary, however, can not read the message because
to do so also requires the receiver's private key.
-Richard
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 28 Sep 1999 16:16:18 -0700
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> The strange thing is that the press release claims that this
> shows that cracking a 97-bit EC system is harder than cracking
> a 512-bit RSA system. Unless there is some breakthrough
> theorem I haven't yet heard of (please enlighten me if so),
> what was shown is that the *particular methods of attack*
> being compared obey that relationship, not that the EC
> problem intrinsically *requires* a higher work factor.
Right. And the difference in running time between the two successful
cracks was only a factor of two, according to the results I read, so
it's hard to imagine how to draw any useful conclusions from the two
experiments, even if you do assume that they used the best attacks.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: msg for Dave Scott
Reply-To: [EMAIL PROTECTED]
Date: Tue, 28 Sep 1999 23:42:56 GMT
On Tue, 28 Sep 1999 16:28:27 GMT, Tom St Denis wrote:
>
>Ok name one popular symmetric algorithm that can be solved without using
>brute force?
>
if 'brute force' means to try all the possible keys, DES only needs to try
2^55 keys and not 2^56 because of a special property called 'reflexive'
or something close. if brute force means something else, please define it.
you can argue that caesar cypher isn't popular but you can't with DES :)
about your software(this thread was about it at the begining), i suggest
you to read sci.crypt.research faq. the answer 3 explains how to present
a new system.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Need advice for encrypting information
Date: Tue, 28 Sep 1999 23:48:03 GMT
In article <[EMAIL PROTECTED]>,
James Felling <[EMAIL PROTECTED]> wrote:
l quibble. It is possible that you get lucky and have two messages
> in a row have the same salt( you are picking randomly aren't you?). I think
> what you neant is that the probability of two messages having the same salt+
> password combo is 1- (( 1 - (2^(-n)) )^m). where m = number of nessages
> sent. Your n/2 figure sounds like you are expecting a birthday type
> coincidence -- actually in theory you could send n messages and never have a
> duplicate key used -- mind you it is so unlikely as to be ludicrious for any
> reasonable sized n)
So if I send say 1000 messages I have a 1 - ((1 - (2^-64)))^1000) chance of
seeing the same salt twice?
Hmm ok... well I don't think most users will send anything more then 1000
messages or so so I don't see it as a big risk... Any thoughts?
Should I make the salt larger? (my calc sucks so I am assuming the result is
small).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "David Franklin" <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Wed, 29 Sep 1999 00:58:41 +0100
Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
>Dr D F Holt wrote:
>> The easiest approach, which would certainly solve the problem fast, is
>> to program the case of finding the order of an arbitrary permutation of
the
>> set {1,2,3,...,n} (in your case n=1001). Just write the permutation in
>> cycles, and then the order is the least common multiple of the cycle
>> lengths.
>
>Yes, that is workable; nice answer! So the program sought would
>simulate the shuffle only once, to build the permutation (not
>hard), then would decompose the perm. into cycles (not hard),
>then find the LCM of the cycle lengths (not hard). Perhaps the
>interviewer's purpose was to probe the applicant's experience in
>working with things very like this. In which case, turning to
>the net means he has not met the criteria.
Two points to ponder...
Firstly, I knocked up a brute force program to do this (took
about 5 mins to write), and got the same answer as Clive Tooth
(97020); the running time was just under 1 second. Which leads
me to wonder about the LCM solution being "much simpler and
faster" as the original interviewer apparently said. When the run
time is 1 second, it's hard to justify spending time speeding it
up (as a one-off problem at any rate). For either the brute force
or LCM solution, the hardest part is probably making *sure*
you get the permutation correct with no off-by-one errors and
so on.
Secondly, it seems the original poster, and at least one person
who followed up was unable to even get the brute force solution
to work. Not too impressive really...
Dave
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Please review proposed rebuttal...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 29 Sep 1999 00:09:58 GMT
On 28 Sep 1999 22:41:47 GMT, Bill Unruh wrote:
>
>Probably, but I also wonder how well it would work on a "supercluser"
>Ie, Cray class machines are now, for certain problems at least much much
>cheaper than 5-10M. ( ie a few hundred thousand will buy you a pretty
>powerful Beowulf cluster.)
>
for that, you need to paralelize the matrix processing...
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: msg for Dave Scott
Date: 29 Sep 1999 00:35:48 GMT
[EMAIL PROTECTED] (jerome) wrote in part:
>if 'brute force' means to try all the possible keys, DES only needs to try
>2^55 keys and not 2^56 because of a special property called 'reflexive'
>or something close. if brute force means something else, please define it.
>
>
Brute-force means trying all the possible keys until you find
the correct key. When you brute-force a cipher, DES, for instance,
you are likely to find the correct key after searching through half of
the possible keys: 2^55 keys.
>you can argue that caesar cypher isn't popular
I suppose you could, but take a look at the crypto puzzles in many Sunday
newspapers.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Increasing password security dramatically without making it harder to
remember
Date: Tue, 28 Sep 1999 21:06:04 GMT
On Tue, 28 Sep 1999 22:58:43 +0100, "Gary" <[EMAIL PROTECTED]> wrote:
>
>Johnny Bravo wrote in message <[EMAIL PROTECTED]>...
>>On Tue, 28 Sep 1999 14:08:51 +0100, "Gary" <[EMAIL PROTECTED]> wrote:
>
>
>> That's assuming that the attacker is only using one computer as slow as
>yours.
>
>Yes you're right. This method is open to parallel attack.
>However in <http://www.counterpane.com/low-entropy.html> kindly linked by
>David Wagner in this thread, a solution is outlined.
>
>For everyday passwords this does deter your average resourced/funded
>attacker.
A 40 bit key being stretched might be sufficient against a very small scale
attack. The idea I was replying to was just to do a SHA-160 hash for 10 seconds
on your PC means that an attacker would need an extra 10 seconds per key to test
the keys. I was just pointing out that you can't assume your attacker will need
the same amount of time as your PC to do that operation.
Given the computing technology available, using a 40 bit key leaves you very
open to an attacker using a precomputed attack, as SHA is very efficient to
implement at a hardware level. Without using a bigger key, the security of this
method would be very limited without additional modifications. There are some
good ideas in the paper you mentioned above, though some of them won't
sufficiently protect a 40 bit key against an attack at above the small group of
PC user level.
Johnny Bravo
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compress before Encryption
Reply-To: [EMAIL PROTECTED]
Date: Wed, 29 Sep 1999 01:09:35 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Hasn't this holy war gone on long enough? When do you ever quit?
: What I don't get is almost EVERYONE agrees that compression before
: encryption is a good idea. So why is he carrying this on?
Perhaps because he has recently developed the only vaugely sensible
compression product targetted at encrypted data that anyone knows of?
As he mentions, using an unsuitable compression routine may actually
weaken the encryption.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Today's subliminal message is
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: ECDL and distinguished points
Reply-To: [EMAIL PROTECTED]
Date: Wed, 29 Sep 1999 01:17:00 GMT
i just read the faq in http://pauillac.inria.fr/~harley/ecdl6/faq.html.
written by robert harley and i think i don't understand the
distinguished points.
The purpose seems make the centralisation easier reporting only
the distinguished point or not the others. But apparently for
ECC2-97, only 1 point in 2^30 is 'distinguished'.
1. does this reduce the efficiency of the algorithm ? (at first sight,
to report only 1 point in 2^30 greatly reduce the possibility of
collisions)
2. does a big computer can be much faster than the distributed algorithm
used for EC2-97 ?
i probably missed something obvious here :)
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: hidden channel in Peekboo
Date: Tue, 28 Sep 1999 19:36:53 -0600
In article <7sok2f$rpm$[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
> Hehehe playing with the source today, I noticed there is a hidden channel in
> the SALT calculation that can be used to send 64-bits of info to the
> receiving end. I don't know what you would do with it but it's there.
>
...
> Any ideas of what this could be used for?
>
An algorithm with a build-in back-door.....ah, something to please a
wayward mind if the source was unavailable or purposefully corrupted.
--
Still a good idea from Einstein: If you can't explain something clearly to a child,
you do not understand it well enough.
So much for models of trust, they generally are ill-founded.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Relating cyrptology to factoring?
Date: Tue, 28 Sep 1999 19:47:12 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> > With the exception of DES and lucifer there are no 'real' prior efforts.
>
> You seem to be confusing "symmetric" with "block".
> Until at least the 1960s, *all* cipher systems were symmetric.
Still, forever and always, a poor choice of names.
--
Still a good idea from Einstein: If you can't explain something clearly to a child,
you do not understand it well enough.
So much for models of trust, they generally are ill-founded.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Requirement for Uniqueness in Decryption Keys
Date: Tue, 28 Sep 1999 19:32:16 -0600
In article <7soj67$ub8$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Patrick Juola) wrote:
> In article <8E4E88373rcarbol@news>, Roger Carbol <[EMAIL PROTECTED]> wrote:
> >In the Handbook of Applied Cryptography:
> >An encryption scheme consists of a set of encryption
> >transformations and a corresponding set of decryption
> >transformations with the property that for each e there
> >is a unique key d such that
> >[d decrypts the message that e encrypted.]
> >I don't understand the requirement for d, the decryption
> >key, to be unique, although I can clearly see why it
> >might be a good idea.
> >
> >Is it, in fact, a rigourous requirement for d to be unique?
> >Or may the set of decryption keys be larger than the set
> >of encryption keys, in a general sense?
>
> I don't think it's a strict requirement; the Caesar cypher is
> still well-defined, even for offsets over 26 letters.
>
Looking at inductive algorithms, a good question is whether the idea that
many ciphertext can be decripted to a single plaintext is allowed by the
description. If not, then it is bad. If you understood d could allow a
set of random outputs, then it would be OK, or true.
If your idea of symmetry revolves around one ciphertext being tied to one
plaintext, then you are really unprepared for truly asymetrical algorithms
that have nothing to do with public key, and have missed one of the
greatest, and one of the oldest ideas, in crypto.
--
Note the latest ad from Apple reflecting the government's
philosophy that good computers should not be exported. It is
interests of our government that foreign computers be vulnerable.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 19:42:30 -0600
In article <7sp3cs$6k0$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> I was given a problem for a job interview for a computer programming
> job. I was to write a routine that cuts a computer simulated deck and
> performs a perfect shuffle.
>From a gaming point of view, a perfect shuffle is one by which noone can
gain an advantage, sort of like perfect randomness. Otherwise, it is a
cheat to be able to predict the cards.
--
Still a good idea from Einstein: If you can't explain something clearly to a child,
you do not understand it well enough.
So much for models of trust, they generally are ill-founded.
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 21:22:33 GMT
On Wed, 29 Sep 1999 00:58:41 +0100, "David Franklin" <[EMAIL PROTECTED]>
wrote:
>Secondly, it seems the original poster, and at least one person
>who followed up was unable to even get the brute force solution
>to work. Not too impressive really...
>
>Dave
I didn't even bother to check for the completion at first, I was just
interested in seeing how fast it ran. The LCM and brute force solutions would
both take less than a second, and the brute force in this case would be easier
to code. :)
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 21:18:46 GMT
On Tue, 28 Sep 1999 21:22:30 +0200, Jean-Jacques Quisquater <[EMAIL PROTECTED]>
wrote:
>> what does this have to
>> do with crypto. <plonk - killfiled>
>>
>> Post follow ups to dev/null.
>
>Well, do you know this nice book?
>
>"Magic tricks, card shuffling and dynamic computer memories"
>by S. Brent Morris (NSA)
>MAA, 1998.
>
>see http://www.maa.org/pubs/books/cards.html
>
>link with crypto is immediate (see our paper at CRYPTO 83 :-)
>
>Jean-Jacques Quisquater,
He is asking us to help him get a job. That's what I found irrelevant. :)
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Tue, 28 Sep 1999 21:20:16 GMT
On Tue, 28 Sep 1999 14:54:37 -0700, "karl malbrain" <[EMAIL PROTECTED]> wrote:
>If you look back to the history of PUBLISHING circa 1500, you'll find
>TRAVELLING JOURNEYMEN offering to reproduce all sorts of things from the
>back of their wagons -- in other words, taking inspiration from the NET is
>no barrier to PARTICIPATION.
You didn't see those Journeymen wandering though the town shouting out
question on how to do his job either. :)
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: msg for Dave Scott
Date: 29 Sep 1999 02:34:46 GMT
Tom St Denis <[EMAIL PROTECTED]> writes:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (JPeschel) wrote:
>> >Tom St Denis [EMAIL PROTECTED] writes:
>>
>> >In article <[EMAIL PROTECTED]>,
>> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>> >> Tom St Denis wrote:
>> >> > So generally a 'blind' keysearch is the only way.
>> >>
>> >> Not even close.
>> >
>> >Ok name one popular symmetric algorithm that can be solved without using
>> >brute force?
>>
>> Caesar cipher -- you did say one popular symmetric algorithm.
>
>Hey smartass, shut up. Sorry but the comment is moot. The OTP is
'popular'
>in your view I bet, but it CANNOT be broken. So what. I am talking
about
>real life crypto algorithms used in real life programs today.
>
>Tom
>
I answered your question. Why the name-calling?
I didn't say anything about an OTP.
Yes, Caesar ciphers are used in "real life programs."
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Wed, 29 Sep 1999 01:52:00 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> >Tom St Denis [EMAIL PROTECTED] writes:
>
> >In article <[EMAIL PROTECTED]>,
> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> >> Tom St Denis wrote:
> >> > So generally a 'blind' keysearch is the only way.
> >>
> >> Not even close.
> >
> >Ok name one popular symmetric algorithm that can be solved without using
> >brute force?
>
> Caesar cipher -- you did say one popular symmetric algorithm.
Hey smartass, shut up. Sorry but the comment is moot. The OTP is 'popular'
in your view I bet, but it CANNOT be broken. So what. I am talking about
real life crypto algorithms used in real life programs today.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
