Cryptography-Digest Digest #405, Volume #10 Wed, 13 Oct 99 10:13:03 EDT
Contents:
Re: where to put the trust ([EMAIL PROTECTED])
Re: Layperson Q: how long to crack 32-bit RSA? (Jerry Coffin)
Better than Diffie-Hellman? ([EMAIL PROTECTED])
Re: where to put the trust (Bill Unruh)
Re: Better than Diffie-Hellman? (Paul Rubin)
Re: Disappearing Inc. (Francois Grieu)
Re: CRYPTO/EUROCRYPT (Eric Hambuch)
KRYPTOS AGAIN ("collomb")
basic math help required to explain block cipher ([EMAIL PROTECTED])
need LFSR information ([EMAIL PROTECTED])
Re: classifying algorithms ([EMAIL PROTECTED])
Re: where to put the trust ([EMAIL PROTECTED])
Re: where to put the trust ([EMAIL PROTECTED])
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Re: basic math help required to explain block cipher
Re: basic math help required to explain block cipher (Tom St Denis)
Re: where to put the trust (Tom St Denis)
How many prime numbers? ("Reza Bohrani")
Re: RSA Algorithm (Bo Dömstedt)
Re: Newbie questions ("Dan Fogelberg")
Re: Newbie questions ("Dan Fogelberg")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: where to put the trust
Date: Wed, 13 Oct 1999 04:37:59 GMT
In article <7tvf0d$56o$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Patrick Juola) wrote:
> In article <[EMAIL PROTECTED]>, Terry Ritter
<[EMAIL PROTECTED]> wrote:
>>Bridges generally stay up precisely because engineers can unarguably
>>distinguish between a bridge which falls and one that does not.
>
>... Yeah. *After it has happened*, assuming there was anyone around
>to witness the fall. And even then, you need a team of experts to
>examine the wreckage to figure out if it was a design flaw, a
>construction flaw, or actual sabotage/demolition.
>
>Just like cryptography.
No, there is a difference. One can build a bridge with little
theoretical knowledge about mechanics and *test* to see if it works:
you just load the bridge with the maximum weight and see if it holds.
No such test is known for ciphers. Cryptography is the only engineering
field I know of, where you cannot actually test to see if what you
build fulfils its design requirements.
Still, the question remains: if we don't trust the experts then what is
the better alternative?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Layperson Q: how long to crack 32-bit RSA?
Date: Tue, 12 Oct 1999 22:46:43 -0600
In article <7u0uun$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> In article <7u0ahn$na1$[EMAIL PROTECTED]>,
> "Matthew Sullivan" <[EMAIL PROTECTED]> wrote:
>
> >A 550 Mhz PIII can do an equivilent piece of RC5- 64bit keyspace in under an
> >hour, 32bit RC4 should take less time.
>
> A 64bit keyspace in under an hour on a single processor? Either they are
> using a much-better-than-brute-force attack (which makes the analogy with
> RC4 invalid), or you are wrong.
Note where he says "an equivalent piece of". I'm reasonably certain
that means using some RC5 code, a 550 MHz PIII has checked roughly a
couple billion 64-bit RC-5 keys in under an hour. Given that RC-4 is
simpler, and we're also talking about 32-bit operations instead of 64-
bit operations, checking the same number of keys with RC-4 should be
faster still.
> Still, that doesn't change what the other posters are saying: a 32 bit
> keyspace can be searched in hours-weeks, based on the amount on computation
> the attacker has available
Actually, weeks would assume the attacker has extremely minimal
resources. Hours would assume only somewhat reasonable resources
(e.g. probably what I have sitting in my office would suffice).
To put this into perspective, consider that DES has roughly 16 million
TIMES as many keys and is still considered to have marginal security
at the present time. If we extrapolate from the cost and speed of
Deep Crack, then a machine to crack a 32-bit key in around a second
should only cost less than $20,000US or so to build. In reality,
given the simplicity of RC-4 compared to DES and the time since Deep
Crack was built, that can probably be reduced by at least a factor of
two.
In the end, we're talking about enough smaller project that
extrapolation probably isn't terribly accurate, but at least it should
give SOME idea of how small a task this is compared to breaking
ciphers of even marginal security.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Better than Diffie-Hellman?
Date: Wed, 13 Oct 1999 04:41:41 GMT
Diffie-Hellman can be used with fixed exponentials for key exchange.
The downside is that the shared secret key never changes. I don't like
to reuse the same key too often and changing the public keys is a
bother. The following variant produces different session keys:
Alice publishes: X = g^x mod n.
Bob publishes: Y = g^y mod n.
When Alice wants to initiate a session with Bob she chooses a random z,
computes Z = g^z mod n, and sends Z to Bob.
Now both Alice and Bob can compute two secret keys. The fixed S1 = g^
(xy) mod n and the variable S2 = g^(zy) mod n. I propose to compute the
session key a function of S1 and S2: S = Encrypt(key=S2,S1)
Here is my reasoning: S2 alone is not adequate because it does not
authenticate Alice. S1 authenticates both Alice and Bob but is fixed.
By encrypting S1 using S2 as a key we get a different key each time
that authenticates both.
Does this make any sense? Can this variant be weaker than the classical
DH that always produces the same S1?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: where to put the trust
Date: 13 Oct 1999 05:00:17 GMT
In <7u12b6$vsg$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>Still, the question remains: if we don't trust the experts then what is
>the better alternative?
"Trust many experts" is better. Ie, a cypher should be public, and should
have been looked at by a number of people. If Bruce Schneier sells you a
secret algorithm that noone else has looked at you might trust it more
than if I did. But I would far rather get one that he had published, and
had been looked at by a number of independent experts.
And I would not trust one, even from him, where he did not release the
source code for it as well.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Better than Diffie-Hellman?
Date: 13 Oct 1999 05:30:43 GMT
In article <7u12i4$63$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Alice publishes: X = g^x mod n.
>Bob publishes: Y = g^y mod n.
>When Alice wants to initiate a session with Bob she chooses a random z,
>computes Z = g^z mod n, and sends Z to Bob....
>
>Does this make any sense? Can this variant be weaker than the classical
>DH that always produces the same S1?
It doesn't provide forward secrecy. Authentication and cryptography
should be done with separate keys.
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Re: Disappearing Inc.
Date: Wed, 13 Oct 1999 09:16:58 +0200
Eric Smith <[EMAIL PROTECTED]> wrote:
> They claim that their system can encrypt email such that it
> can only be decrypted before a certain expiration date. I
Their exact claim is:
"at the end of the message lifecycle, Disappearing Inc. Universally
Deletes(tm) the message from the local PC, the mail server, and backup
tapes so that nobody can ever read it again."
They apparently assume they can prevent anyone from making a backup
copy of an email previously read. They ignore, or pretend to ignore,
the existence of utilities to capture the screen, or better the text
beeing rendered on the screen. I think they should limit their claim
to: "so that nobody can ever read it again without access to data
obtained from a previous reading".
Francois Grieu
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: CRYPTO/EUROCRYPT
Date: Wed, 13 Oct 1999 10:20:11 +0200
Jonathan Katz wrote:
>
> Anyone selling back issues of CRYPTO/EUROCRYPT proceedings? Please contact
> me...
Springer Verlag, Berlin, Germany.
try: http://www.springer.de
Eric
------------------------------
From: "collomb" <[EMAIL PROTECTED]>
Subject: KRYPTOS AGAIN
Date: 13 Oct 1999 08:42:29 GMT
KRYPTOS AGAIN
Hello
As opposed to what is be said beneath by Derek Bell answering to Bill on
10.12.99,
Kryptos was cracked.
The solution is published on the siteweb :
http://calvaweb.calvacom.fr/collomb /
It was said that to try to solve Kryptos, it takes much of skull sweat,
20 billions trials on computer and perhaps ten years of work …. to solve
the 97 last characters!
Not. This enigma was conceived to be able to be solved even by
non-cryptographers, for it must have – given the CIA fame world over -
universal
far-reaching consequencies.
Let us return at the base. The enigma was conceived by an artist who
worked with his own artist tools, i.e. with forms.
For the specialists the square of Vigenere is a succession of characters
in a certain order, for an artist, it is primarily a square.
My reasoning is thus based on squares which derive from each other.
The conceptors repetedly said that Kryptos is a puzzle.
A puzzle cannot be solved with billions of computer operations.
A puzzle is a collection of small pieces that should be connected each
other.
It is what I did.
I find <in fine> in Kryptos the struggle between Good and Evil, which
is an universal idea, that Americans like very much,
see the movie Star Wars ….
Best Regards
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: basic math help required to explain block cipher
Date: Wed, 13 Oct 1999 09:00:30 GMT
Hello
I was reading a paper on block ciphers and there is a line that says:
"It [block cipher/digital signature algorithm] can be viewed as a
mathematical object: typically, a function taking an input between 0
and 2N-1, and providing an output between 0 and 2M-1"
Note that the M and N are powers.
Could some explain this sentence to me please?
Viv
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: need LFSR information
Date: Wed, 13 Oct 1999 09:15:33 GMT
Please help!
Where can I find detailled information about the security
of Alternating Stop and Go Generator or similar PSRG.
Are the Eurocrypt'XX and Crypto'XX papers available online.
(Back to 85)
Where can i find a table of LFSR coefficients with maximum
length period.
Gransche
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: classifying algorithms
Date: Wed, 13 Oct 1999 09:49:43 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <7u01et$87e$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> >
> > Some people refer to stream algorithms as "adaptive" while block
> > algorithms are refered to as "statistical" (from "static").
> > The two are somewhat complementary.
> >
> ....
> >
> > An adaptive algorithm typically responds to each incoming sample.
> > whereas a block algorithm responds to batched samples. But adaptive
> > algorithms have memory so in effect have some statistical
information
> > (this is where the fundamental uncertainty principles come in-
again.
> > They are defined here exactly the same way as in quantum physics).
> >
> Then, the other choices are statistical stream algorithms and adaptive
> block ciphers.
>
> Actually, I do push a cipher that would fit into the fourth category.
I
> refer to such cipher as *inductive* that can produce a plethora of
> different outputs for a single input block with the same user keys.
There seem to be many dualistic dichotomies that are isomorphic
to the stream vs. block pardigm like deductive vs. inductive.
I'm not sure what you mean by different outputs here, are they
intermediary like recursive results ? Iterative vs. recursion might
also be an analog for stream vs. block ?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: where to put the trust
Date: Wed, 13 Oct 1999 10:47:21 GMT
In article <7u13l1$23l$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> In <7u12b6$vsg$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
> >Still, the question remains: if we don't trust the experts then what
is
> >the better alternative?
>
> "Trust many experts" is better. Ie, a cypher should be public, and
should
> have been looked at by a number of people. If Bruce Schneier sells
you a
> secret algorithm that noone else has looked at you might trust it
more
> than if I did. But I would far rather get one that he had published,
and
> had been looked at by a number of independent experts.
> And I would not trust one, even from him, where he did not release
the
> source code for it as well.
While "trust many experts" may be better than trusting any
one "expert," this still does not address the essence of the
problem: there can be no expertise on strength which applies
to our opponents.
In general, we must assume that our opponents know everything
in the open literature, plus whatever has been accumulated by
dedicated secret organizations of many bright people over long
time. Academic review simply provides no logical insight
about what true opponents know or can do. We are thus forced
to assume the worst.
Looking for expertise which cannot exist seems a rather
futile exercise, even if we collect as many opinions as we
can. Reality is not a vote.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: where to put the trust
Date: Wed, 13 Oct 1999 10:55:43 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] () wrote:
> Tom St Denis ([EMAIL PROTECTED]) wrote:
> : Well we trust experts.
>
> Yes, I think this *is* valid. If you've seen a recent thread where
I've
> been discussing this issue with Terry Ritter, you'll know that I do
think
> this is one of the most valid ways to determine which cipher systems
are
> likely to be strong.
And I think this is clearly wrong: What is this "expertise?"
Does it have any relationship to opponents who are almost
certainly more capable than any open expert, and who have
more time and more resources as well? I think not.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 13 Oct 99 11:30:21 GMT
Trevor Jackson, III ([EMAIL PROTECTED]) wrote:
: I doubt anyone would criticize you for concentrating your efforts on areas
: where you and your company can make a difference/contribution/profit. I
: doubt that finding uses for 3DES ranks high on your personal or corporate
: agenda.
It should be noted, though, that one doesn't have to pay royalties to use
Blowfish or Twofish; it's not as if Bruce has proprietary algorithms to
sell that 3-DES would take markets away from.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: basic math help required to explain block cipher
Date: 13 Oct 99 11:44:31 GMT
[EMAIL PROTECTED] wrote:
: "It [block cipher/digital signature algorithm] can be viewed as a
: mathematical object: typically, a function taking an input between 0
: and 2N-1, and providing an output between 0 and 2M-1"
: Could some explain this sentence to me please?
It doesn't say a lot, I'll warn you right now. (For block ciphers, as
opposed to digital signature algorithms, M=N.)
Here's an example of a way to code a message for transmission.
Second digit
0 1 2 3 4 5 6 7 8 9
0 = + - * / ( ) < >
1 0 1 2 3 4 5 6 7 8 9
2 A B C D E F G H I J
3 K L M N O P Q R S T
4 U V W X Y Z $ @ # %
5 a b c d e f g h i j
6 k l m n o p q r s t
7 u v w x y z _
8 . , : ; ! ? ' "
9 [ ] { }
Thus, a message like "Hi, I'm Fred" becomes a string of digits:
H i , I ' m F r e d
275881002886620025675453
Now, a block cipher applied to a message in the form of a string of digits
which is intended to leave it in the form of a string of digits would
take, for example, a string of digits from 00000000 to 99999999 as input,
and would produce a (usually different) string of digits from 00000000 to
99999999 as output.
Instead of thinking of these strings of digits just as chains of symbols,
we could also think of them as numbers...from 0 to 99999999. That is, as
numbers from 0 to 10^8 - 1.
So our example block cipher would be a function taking numbers from 0 to
10^8-1 as input, and giving such numbers as output.
So all that sentence is saying is that a block cipher or digital signature
algorithm takes N-bit strings as input, and gives M-bit strings as output,
and that these strings can be thought of as numbers in binary form. They
give 2^N instead of 10^N because while a digit has 10 values, a bit has
only two, 0 or 1.
John Savard
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: basic math help required to explain block cipher
Date: Wed, 13 Oct 1999 12:12:57 GMT
In article <7u1hnb$ao5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello
>
> I was reading a paper on block ciphers and there is a line that says:
>
> "It [block cipher/digital signature algorithm] can be viewed as a
> mathematical object: typically, a function taking an input between 0
> and 2N-1, and providing an output between 0 and 2M-1"
>
> Note that the M and N are powers.
>
> Could some explain this sentence to me please?
What cipher is it? I may have the paper and I could help.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: where to put the trust
Date: Wed, 13 Oct 1999 12:08:14 GMT
In article <7u12b6$vsg$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> No, there is a difference. One can build a bridge with little
> theoretical knowledge about mechanics and *test* to see if it works:
> you just load the bridge with the maximum weight and see if it holds.
> No such test is known for ciphers. Cryptography is the only engineering
> field I know of, where you cannot actually test to see if what you
> build fulfils its design requirements.
>
> Still, the question remains: if we don't trust the experts then what is
> the better alternative?
>
You trust whoever makes the best educated guestimate. Just like in medicine.
Do you honestly believe [for example] that the [advil, asprin, tylenol] you
take for a headache has no adverse effects on any other part of your body?
For all we know, it could be a cancernegen.
Same thing with engineering. Although we can test a bridge for fullload
capacity, we can't for example reliably predict what will happen in the face
of a natural disaster. I would admit that more practical knowledge is
avaible to engineers however cryptography is a rather rare trade and still
new in the modern era.
And BTW for all we know, we can test ciphers for fundamental flaws. We can
assume [for example] that RC5 is relatively strong because many people have
seen it, attacked it, and still the best attack is o(2^53). By contrast we
know [for example] FEAL is weak because the same style attacks will utterly
break it reasonably efficiently.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Reza Bohrani" <[EMAIL PROTECTED]>
Subject: How many prime numbers?
Date: Wed, 13 Oct 1999 14:44:16 +0200
If I decide to set the size of a number p, which is prime , to be exactly
100, then how many primes are there with the size 100?
------------------------------
From: [EMAIL PROTECTED] (Bo Dömstedt)
Subject: Re: RSA Algorithm
Reply-To: [EMAIL PROTECTED]
Date: Wed, 13 Oct 1999 13:39:10 GMT
Nicol So wrote:
>Based on what reasoning did they come to that conclusion?
Nice of you to bother about that -- how about the following
quote, taken from a link I have previously published:
>To break an RSA system it suffices to factorize a known large
>number specific to the instance of the system and known to be
>the product of two large prime numbers. If, when constructing
>the system, these prime numbers are chosen unskilfully, then it
>will be easy to break the system. The number of traps that need
>to avoided is increasing all the time and hence the problem
>of constructing an RSA system is getting harder.
This implies that even if 1024 keys are larger than 768 bit keys,
1024 bit keys may not be secure. They may have been
chosen "unskilfully".
./.
Bo Dömstedt
Protego Information AB
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: Newbie questions
Date: Wed, 13 Oct 1999 07:41:38 -0500
John,
All right you lost me in some of your response. What is Kasiski method and
what is Kappa test and looking for the period. I assume period is not the
little dot at the end of the sentence :-). Thank you for your reply.
--Dan
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Dan Fogelberg ([EMAIL PROTECTED]) wrote:
> : My question to you all is first how do I do a brute force attack?
>
> A brute-force attack is trying every possible password. That would take a
> very long time, and is not necessary.
>
> : I have
> : looked for repetions etc and it appears he has used a long password. Is
it
> : breakable if he used a 765 byte password?
>
> Not if every character was chosen absolutely at random. If the password
> were English text, though, it might be possible, but difficult.
>
> : How about if he used a 300 byte
> : one???
>
> Then more likely to be breakable.
>
> Instead of looking for coincidences (the Kasiski method), one could simply
> slide the message against itself, looking for the largest proportion of
> single-byte matches (the kappa test). Once you have found the period, at
> least in some cases it might be possible to determine what could be XORed
> to all the characters in a column to make them sensible. (The reply by J.
> Peschel mentioned a program that does this sort of thing automatically.
> His site has pointers to such resources.)
>
> John Savard
------------------------------
From: "Dan Fogelberg" <[EMAIL PROTECTED]>
Subject: Re: Newbie questions
Date: Wed, 13 Oct 1999 07:39:13 -0500
JPeschel, I think you are right...I am downloading VCrack now and will see
how it works. I am fairly certain he encrypted it as you say, a fairly
short key that is XORed with the plaintext. I will report back.
Thank you for you help and pointers.
JPeschel <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Arthur Dardia <[EMAIL PROTECTED]> writes:
>
> >From the looks of it, he encrypted it via a one time pad. I assume by
your
> >response, that vcrack brute forces and/or uses dictionary attacks on
them?
> >If
> >so, how efficient is it. Does a distributed computing client based on
its
> >src
> >exist?
>
> Has Fogelberg sent you the message, or are you just assuming that the
> cipher is using a key the length of the message?
>
> I am guessing that the key isn't as long as Fogelberg thinks. If I'm
right,
> then the cipher is likely a polyalphabetic substitution cipher with
> a repeating key XORed against the plaintext. Vcrack is neither a
brute-force
> nor dictionary-based cracker. Instead vcrack attempts to find the length
> of the key, does some analysis, and writes the decrypted message.
> It's author says it's 98.6% perfect. Takes about a second to decrypt a
> message.
>
> Joe
>
>
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
>
------------------------------
** 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
******************************
