Cryptography-Digest Digest #501, Volume #9 Wed, 5 May 99 04:13:04 EDT
Contents:
Re: AES (SCOTT19U.ZIP_GUY)
Re: Triple DES cracked? NYT says so... (Matthew Skala)
Discrete Logarithm Question ("Vedat Hallac")
Massey-Omura cryptosystem added to web site (John Savard)
Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (Mok-Kong Shen)
Re: True Randomness & The Law Of Large Numbers (Hawkhaven)
Re: Some thoughts on Diffusion (Piso Mojado)
Re: Discrete Logarithm Question ("Vedat Hallac")
Re: Discrete Logarithm Question ("Vedat Hallac")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: AES (Terry Ritter)
Re: AES (wtshaw)
Re: AES ([EMAIL PROTECTED])
Re: Compact look-up table - weak? (wtshaw)
Re: Discrete Logarithm Question ("Antoine Joux")
----------------------------------------------------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: AES
Date: Tue, 04 May 1999 23:18:12 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> >and algorithm such as Triple-DES is proven
> >to be very secure.
>
> Agreed.
>
Really!
Just where is this proof that you seem to be talking
about. My guess is that you don't really know of such
a proof.
David Scott
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
to email me use address on WEB PAGE
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Triple DES cracked? NYT says so...
Date: 4 May 1999 16:20:04 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>claims that Drs. Eli Biham and Adi Shamir have discovered a way to
>reduce _Triple_ DES to the strength of single-DES in some cases.
I can reduce standard EDE 3DES to the strength of DES in 2^56 cases: those
are the cases where the two halves of the key are identical. Then a 3DES
encrypt is the same as a DES encrypt. I imagine that's not what's being
discussed here, though.
--
Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
GOD HATES SPAM
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Discrete Logarithm Question
Date: Wed, 5 May 1999 09:37:34 +1000
Hi everybody,
I wanted to know if there is a method to find x in
a_i^x == b_i ( mod N )
if I can calculate b_i for *every* 1 < a_i < N. And N is not a prime number.
I have checked out the net, and online papers I can get my hands on, but did
not find anything. I was just wondering whether there are any results on
this one or not.
My thanks in advance,
Vedat
[EMAIL PROTECTED]
(please remove the obvious parts from the address)
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Massey-Omura cryptosystem added to web site
Date: Tue, 04 May 1999 23:16:27 GMT
...in the chapter on public-key cryptography, under "Other methods". I
had heard of the system, but I had forgotten its name; I had thought
it was invented by Dr. Shamir contemporaneously with his origination
of the Shamir three-pass protocol, on which it is based.
The comments I make there are similar to some I had previously posted
some time back, but I acknowledged that there is a point of view that
classes this cryptosystem as something other than a public-key system.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO
Date: Thu, 29 Apr 1999 09:34:08 +0200
SCOTT19U.ZIP_GUY wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> ...
> >
> > I also don't understand your last sentences. The random bits are
> > discarded by the receiver. They involve some transmission expense,
> > but that's all.
> >
>
> Bullshit the receiver has to know where the random bits are
> to discard them. Write code if you CAN Mr. Shen and then we
> can discuss it. Until then it is obvious this is way over your
> head.
>
> Again I say. WRITE THE CODE AND SHOW EXAMPLES LIKE I DID.
Did you forget the context of our discussion? We were discussing
EOF. If you have EOF, then everything after EOF is stuff that
the receiver discards. Isn't that OBVIOUS to you?
M. K. Shen
------------------------------
From: Hawkhaven <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 4 May 1999 22:40:20 +0200
forgive me for jumping into this message as i have not as of yet read the
entire thread, but i could not help but notice that the subject of these
messages seem to imply that the law of large numbers somehow makes true
randomness impossible, if this has nothing to do with the thread then
ignore this message...
the problem with the reasoning that says that the law of large numbers in
any way makes a true random generator in any way predicable is that the
law of large numbers has nothing to do with prediction (consulst your
freshmen stat book to see that im right)...in fact it simply states that
given an infinate number of trials then the distribution of the random
results will be on the agregate perfectly "in-sink" with the probabilities
for each possible outcome of a trial...said in a more plain fashon, if i
have a "fair" coin then if i flip it an infinate number of times, or more
realisticly 1 billion times (any very large number should do, hense the
name), then the distribution of heads to tails should be about even, i.e.
1/2 billion heads, 1/2 billion tails...this is also true for a true random
number generator (if such a thing can exist, ill leave that one up to the
philosophers and quantum physicists), which is all well and good exept
that this in no way gives you any hint as to what the 1 billion and 1th
coin toss will be as every trial is independent...
--Hawkhaven
"Win if you can, lose if you must, but always, always cheat!"
On Tue, 4 May 1999, R. Knauer wrote:
> On Mon, 03 May 1999 08:14:59 -0600, "Tony T. Warnock"
> <[EMAIL PROTECTED]> wrote:
>
> >It would help if you would inhale.
>
> You have been silent for the most part - why not weigh in and give us
> your take of these experts' comments, which I have posted several
> times here.
>
> Bob Knauer
>
> "There is much to be said in favour of modern journalism. By giving us the opinions
> of the uneducated, it keeps us in touch with the ignorance of the community."
> -- Oscar Wilde
>
>
>
------------------------------
From: Piso Mojado <[EMAIL PROTECTED]>
Subject: Re: Some thoughts on Diffusion
Date: Tue, 04 May 1999 20:44:51 -1000
Look at :
http://csrc.nist.gov/encryption/aes/round1/conf2/papers/folmsbee.pdf
You need Adobe acrobat reader to view it. Avalanche (diffusion) is
quantified for all 15 algorithms.
Robert Scott wrote:
>
> While experimenting with different Feistel-like symmetric
> ciphers, I had some thoughts on ways of quantifying diffusion.
>
> While the overall security of a cipher can never be known
> for certain until it is broken, diffusion has been at least
> a good indicator of probable security. By diffusion I mean the
> action of an input data bit having an effect on a large
> part (hopefully all) of the output block. When applied to ciphers
> with rounds, I mean diffusion to apply specifically to the rate
> at which the effect of an input bit spreads as a function of
> rounds.
>
> In DES, for example, complete diffusion of the input data block
> occurs after 5 rounds. By this I mean that after 5 of the 16
> rounds, every input bit can potentially affect every output bit.
> To arrive at this conclusion you only need to consider the
> effect of a data bit in the Left Half (after the initial
> permuation) that does not get expanded into two bits by
> the 32 -> 48 bit expansion. After one round it has gone
> nowhere. After 5 rounds, its affect is everywhere. But it may
> not be a fair measure to consider only the worst case. After
> all, the diffusion was almost complete after 4 rounds. And
> is it fair to start counting rounds at the worst possible
> time for a particular bit? If you start counting rounds from
> the point where the bit in question first enters into the
> diffusion process, then I think it will turn out that diffusion
> in DES is complete after about 3.5 rounds. I don't know if this
> measure can be formalized, but if it can, then we can give DES
> a diffusion ratio of 16/3.5, or 4.57. It seems intuitive that
> the ratio of total rounds to rounds for complete diffusion is
> a good measure of security. I wonder what the diffuison ratio
> of the various AES candidates compares with 4.57?
>
> Diffusion should be analyzed separately in both the encrypting
> and decrypting directions. In DES, this distinction is almost
> nil, because the difference between encrypting and decrypting is
> essentially only in the key schedule. However, it is easy to
> construct ciphers in which this is not the case. For example,
> consider an encryption round to be:
>
> B[1] = B[1] ^ f(B[0])
> B[2] = B[2] ^ f(B[1])
> . . .
> B[7] = B[7] ^ f(B[6])
> B[0] = B[0] ^ f(B[7])
>
> where f is a key-determined lookup table. This design has been
> picked to optimize encryption diffusion, which is complete after
> about 1 round (2 rounds, worst case). But look what happens
> to decryption diffusion:
>
> B[0] = B[0] ^ f(B[7])
> B[7] = B[7] ^ f(B[6])
> . . .
> B[2] = B[2] ^ f(B[1])
> B[1] = B[1] ^ f(B[0])
>
> It is terrible! After 1 round, B[0] has affected only B[1]. After
> 2 rounds, the effect has spread to include B[2]. In fact, it
> takes 7 rounds to get complete diffusion in decryption.
>
> Bob Scott
> Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
> (My automatic return address is intentionally invalid.)
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Question
Date: Wed, 5 May 1999 14:24:46 +1000
I certainly need some sleep. Third reply in a row.
It seems I was wrong in my second message. In RSA you can find a_i for every
b_i in
a_i^x == b_i (mod N)
if x is the secret key, and you know the public key. This is certainly not
the same thing as finding b_i for all a_i (unless you find a very
cooperative user who would sign any value you send to him).
Sorry for the second and third messages. I am aware of the message pollution
I am creating over here, and I apologize. I promise I won't add more
unnecessary replies.
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Question
Date: Wed, 5 May 1999 13:39:13 +1000
Here I am replying to my own message. Too much maths I would say.. :-)
The question was quite stupid. It is quite obvious that there is no such
method. Otherwise we wouldn't be using RSA today.
Why is it that you see the obvious AFTER you post it?
Vedat Hallac wrote in message
>I wanted to know if there is a method to find x in
>
>a_i^x == b_i ( mod N )
>
>if I can calculate b_i for *every* 1 < a_i < N. And N is not a prime
number.
>
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Wed, 05 May 1999 04:42:07 GMT
On Tue, 04 May 1999 20:12:40 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>[...]
>- and if we insist on using 1000 different ciphers, some of them will
>be designed by laypersons.
>
>If this picture of the situation is true, it would seem to be a
>telling argument against your proposed design.
I see nothing "telling" about this argument. The truth is that we
simply do not have a satisfactory "vetting" arrangement for ciphers.
Academic papers record "results," and the strongest cipher may *have*
no results. Since we do not know how much effort was fruitlessly
spent or by whom, we don't even have a beginning of an understanding
cipher strength with respect to academics. We expect cipher strength
with respect to real opponents to always be less than that, and
potentially far less.
If we don't know the strength of a cipher, we simply don't know. We
don't know that the single cipher hasn't been broken from day one, and
the many-cipher system can't possibly use a cipher which is weaker
than that. We just don't know.
And while we may not be able to know whether we are wrong to use a
particular cipher, we *can* predict the potential consequences of
being wrong: In the many-cipher environment, a broken cipher exposes
a message, and the exposure is terminated by the use of the next
cipher. In the single-cipher environment, a broken cipher potentially
exposes all data ever sent and all data into the future until the
system is replaced.
>[...]
>And so this all boils down to how likely a cipher is to be bad, in a
>way that is easily detectable. The difficulty of cracking the cipher
>used to communicate which ciphers are being used is something I
>haven't touched on, and that will certainly contribute to the strength
>of the system.
I do have a state machine negotiation protocol. The basic idea is
fairly straightforward: We add a "control sub-channel" to the data
payload. Through this channel each side sends a list of desired
ciphers and a proposed cipher, by name; the received list is compared
to the list of ciphers that user will accept. If agreement can be
made, that cipher is loaded from store and used.
The process starts off with agreement on keys and cipher in the normal
way: either transported as a secure secret, or under a certified
public key. Instead of a cipher name, the cipher itself could be
sent, as C, binary, or whatever. Particular companies might specify a
cipher to use upon start-up to decide the issue. Unless Triple-DES
collapses, many users will start off with Triple-DES.
Any cipher we choose could be a "metacipher" which uses other ciphers
as components. It might even choose those components at random, using
the message key randomness, negotiation, and secure storage facilities
of the user interface.
Since negotiation takes place in the enciphered payload, that would
seem to be pretty secure. There would be no headers which indicate
ciphering or the type of cipher used. OF COURSE every message would
have a large, random message key. And if there was no desire to
change ciphers on each message, the name of the current cipher for
that connection (securely stored locally) obviously need not be
re-negotiated.
>[...]
>Then there's the issue of how a computer program intended to protect
>the security of messages should be "idiot-proof" if it hopes to
>deliver the promised security.
The first thing to do is to make sure that no public key can be used
without certification.
But cryptography can usefully hide only that information which is
otherwise hidden. This means that even in the best case users must
actively participate to keep secrets. In the usual case, papers
holding secrets must be guarded and destroyed. We might think of a
system which only has video information, thus limiting what must be
protected, but I doubt that would be practical in most cases. So
there simply must be an environment of security which goes far beyond
the simple use of a cryptosystem. There is no "idiot-proof" security.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: AES
Date: Wed, 05 May 1999 04:46:48 GMT
On Tue, 04 May 1999 21:39:14 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Bruce Schneier) wrote:
>On Fri, 30 Apr 1999 13:12:52 -0500, "Anthony King Ho"
><[EMAIL PROTECTED]> wrote:
>[...]
>>and algorithm such as Triple-DES is proven
>>to be very secure.
>
>Agreed.
Sorry. There is NO proof of strength for Triple-DES or any other
cipher in cryptography.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: AES
Date: Wed, 05 May 1999 00:11:24 -0600
In article <7gnv7g$56a$[EMAIL PROTECTED]>, SCOTT19U.ZIP_GUY
<[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Bruce Schneier) wrote:
>
> > >and algorithm such as Triple-DES is proven
> > >to be very secure.
> >
> > Agreed.
> >
>
> Really!
> Just where is this proof that you seem to be talking
> about. My guess is that you don't really know of such
> a proof.
>
> David Scott
>
All other factors aside, being able to confirm a key with a small amount
of ciphertext/plaintext does not bode well for an algorithm being really
strong.
Don't think me mean for mentioning what Shannon once was getting at; it's
just the way it is, and this corollary makes lots of sense.....you should
burden your attacker with having to process lots of data to prove or
disprove anything. Making the algorithm solvable with a block or two just
makes cracking more convenient; it that a reasonable goal for any but a
would be attacker to have?
--
If you think you are beaten, you are.
If you thing you dare not, you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES
Date: 5 May 1999 06:51:39 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Terry Ritter) writes:
>On Tue, 04 May 1999 21:39:14 GMT, in
><[EMAIL PROTECTED]>, in sci.crypt
>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>On Fri, 30 Apr 1999 13:12:52 -0500, "Anthony King Ho"
>><[EMAIL PROTECTED]> wrote:
>
>>[...]
>>>and algorithm such as Triple-DES is proven
>>>to be very secure.
>>
>>Agreed.
>
>Sorry. There is NO proof of strength for Triple-DES or any other
>cipher in cryptography.
There are two different meanings of the word "prove." One is the mathemtical
sense, and one is the empirical sense. I assume the poster was making an
empirical statement, in which case it is true that through extensive use
and analysis, Triple-DES has proven to be very secure. It has not, however,
been proved to be secure. Different uses of the verb "to prove."
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compact look-up table - weak?
Date: Wed, 05 May 1999 00:00:13 -0600
In article <7gnre4$1nu$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> <snip>
>
> The problem with small tables is that there is usually small entropy in the
> output. If you only have 256 possible outputs that is really small. For
> example in the blowfish algorithm there are 4 8*32 boxes, making for 2^32
> possible outputs.
>
> I think... hmmm.. well if you have a lot of small tables is that any better?
> I dunno.
>
In one version of the GVA, there are 2^56 possible outputs for each
plaintext for each key. The *table* is telescoped in a sort of graduated
use. The algorithm can be scaled down or up to any level. Having once
played with the idea, I probably should go back and do a junior sized
version of it for study.
To classify something as weak or strong is relative, relative to what; a
scaled down version is going to be weaker than a scaled up version...I
like scalability to demonstrate flexibility in a generic algorithm.
--
If you think you are beaten, you are.
If you thing you dare not, you don't.
------------------------------
From: "Antoine Joux" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Question
Date: Wed, 5 May 1999 09:14:21 +0200
Vedat Hallac a �crit dans le message
<7go05j$gsd$[EMAIL PROTECTED]>...
>I wanted to know if there is a method to find x in
>a_i^x == b_i ( mod N )
>if I can calculate b_i for *every* 1 < a_i < N. And N is not a prime
number.
In order to solve the discrete logarithm mod N, the only solution is to
factor N,
to solve the problem modulo each factor p_i, and finally to glue the partial
solutions
modulo Phi(p_i)=p_i-1, using the chinese remainder theorem .
A couple of remarks:
1) For the discrete logarithm modulo a prime, it is possible to choose the
base g, such
that for all y, g^x=y (mod p) has a unique solution. When working modulo N,
it is not longer
possible. This is due to the fact that the p_i-1 are not relatively prime,
and the chinese theorem
doesn't guarantee the existence of a solution.
2) In my answer, I assumed that N was square-free, i.e. N has no factor
p_i^e with e>1.
If it is not the case, you solve the problem mod p_i, lift the solution to
p_i^e. The partial solution
is modulo Phi(p-i^e)=(p_i-1)*p_i^(e-1) and is glued with the rest.
3) The fact that the only solution is to factor N, is easily proven. The
proof follows:
Assume that you find an algorithm which for any y, g modulo N outputs x such
that g^x=y (mod N). Then you can factor N. To do it, choose a large random
number r (eg N<r<2N), compute y=g^r, and ask for the log. of y say x. Then
D=r-x is a multiple of Phi(N). Write D as 2^t O where
O is odd. The final phase is to choose random values Z mod N, to compute
W=Z^O, and to repeatedly square W. With a little luck, you find an non
trivial square root of 1 and thus a factor
of N.
Antoine Joux
[EMAIL PROTECTED]
------------------------------
** 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
******************************
