Cryptography-Digest Digest #696, Volume #11 Wed, 3 May 00 13:13:02 EDT
Contents:
Re: Silly way of generating randm numbers? (Julio =?iso-8859-1?Q?C=E9sar?=)
RC6 as a Feistel Cipher (Francois Grieu)
Two questions about the design of the MD Hashing algorithms (MD4 and 5) (Chris
MacPherson)
Re: Any good attorneys? (Kent Briggs)
Re: A naive question ("Douglas A. Gwyn")
Re: A naive question ("Tony T. Warnock")
Re: Deciphering Playfair (long) (William Rowden)
Last Chance? (John)
Re: Cascading Crypto Attack (wtshaw)
Re: STU-III (Doug Stell)
Re: Any good attorneys? (Eric Lee Green)
Re: GPS encryption turned off (Paul Koning)
Re: Any good attorneys? (Jeffrey Williams)
Re: quantum computation FAQ? (Mike Rosing)
Re: GPS encryption turned off (Paul Rubin)
Re: Any good attorneys? ("Trevor L. Jackson, III")
Re: RC6 as a Feistel Cipher ("Scott Fluhrer")
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on (Andoni)
Re: RC6 as a Feistel Cipher (David A. Wagner)
----------------------------------------------------------------------------
From: Julio =?iso-8859-1?Q?C=E9sar?= <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Wed, 03 May 2000 15:38:23 +0200
JCA wrote:
> Reminded the other day about Shanks and his mistake when computing
> pi to more
> than 700 decimal places (apparently only the 500-odd first ones are
> correct) I
> couldn't help wondering if this might provide a way to generate strings
> of random
> integers:
>
> Start the computation of pi to some given precision and at some
> (pseudo)
> randomly chosen step make a deliberate arithmetic mistake a la Shanks.
> The digits
> generated from that point onwards are of course not part of pi any more
> (at least not
> in that particular position), and could in principle be used as random
> digits.
>
> Now it is not clear that this procedure might not lead to a
> trivially predictable
> strings of digits (short period strings) but it is true that Shanks came
> up with
> something that looks convincingly random all right.
>
> Is this completely preposterous?
I dont know if this could help, but pi is in no way random.
Julio César Hernández
Carlos III University
Madrid, Spain
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: RC6 as a Feistel Cipher
Date: Wed, 03 May 2000 16:21:20 +0200
I'm trying to solve an exercise proposed by Bob Silverman in another
thread:
(..) try PROVING that RC6 is a Feistel Cipher (..)
The RC6 round function goes like
t = (B*(2*B+1)) <<< 5
u = (D*(2*D+1)) <<< 5
A = ((A ^ t) <<< u) + S[2*i]
C = ((C ^ u) <<< t) + S[2*i+1]
(A; B; C; D) = (B; C; D; A)
where
everything is 32 bit quantities, clipped to 32 bits
the 128 bit block is (A; B; C; D)
<<< is rotation on 32 bits (the low 5 bits of the right
parameter specify the rotation amount)
S[] contain the round subkeys, derived from the key.
At first glance, this does not look like a Feistel Cipher
(where at each round one half goes unchanged, and the other
is XORed with a keyed function of input).
However, I believe (without reference) any cipher can be reduced to a
Feistel Cipher with enough rounds and appropriate choice of round
function among the 2^(64*(2^64)) possible at each round and for each key.
If this is true, then Bob's puzzle has provably a solution.
Question: is there a simple explicit transformation of RC6 into
a Feistel Cipher ?
Francois Grieu
------------------------------
Date: Wed, 03 May 2000 10:36:07 -0400
From: Chris MacPherson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Two questions about the design of the MD Hashing algorithms (MD4 and 5)
Part of my work for my upcoming thesis focuses on Rivest MD4 hashing
algorithm, and there are two parts of the algorithm that confuse me.
Specifically I am looking at Hans Dobbertin's article The Cryptanalysis
of MD4 (J. Cryptology, 1998). Rivest's RFC 1186 on the MD4 message
algorithm can be found here:
http://www.andrew2.andrew.cmu.edu/rfc/rfc1186.html
QUESTION 1
In RFC 1186, pg. 2, where Rivest is describing the MD4 algorithm, step 4
of computing the message digest confuse me.
Step. 4 Process message in 16-word blocks.
We first define three auxiliary functions that each take as
input three 32-bit words and produce as
output one 32-bit word
f(X,Y,Z) = XY v not(X)Z
g(X,Y,Z) = XY v XZ v YZ
h(X,Y,Z) = X xor Y xor Z
I understand the F and G are selection and majority
functions; my question is where do these functions come from? How does
he derive them? Rivest never explains that. I feel like this might be a
standard convention in writing hashing algorithms, and I am missing this
fact because of my inexperience.
QUESTION 2
This goes along the same lines as my previous question. In
the 3 rounds of the algorithm, the steps of each round have the one of
the numbers {3,7,11,19} in round 1, {3,5,9,13} in round 2, and
{3,9,11,15} in round 3 appear at the end of each step function. Again,
I am confused as to where these numbers came from. Is this another
standard convention in 3 round hashing algorithms that I am missing/
Thank you
chris
--
*********************
chris macpherson AIM: drummer80y
[EMAIL PROTECTED] ICQ: 490889
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 14:44:55 GMT
Eric Lee Green wrote:
> Tom St Denis wrote:
> > I just need a DH pro to talk to (i.e how to minimize the ciphertext size
> > but remain relatively secure).
>
> Huh? Diffie-Hellman is a key exchange mechanism, not an encryption algorithm,
> right? Or are we talking about a different thing?
See my Puffer program or my Order Maven program (web site listed below) for
examples of how to use Diffie-Hellman in an offline mode. Note that RSA is just a
"key exchange mechanism" the way it's used in PGP.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Wed, 03 May 2000 14:54:33 GMT
"Tony T. Warnock" wrote:
> Joseph Ashwood wrote:
> > The problem with that theory is that using that theory, a
> > OTP on top of English is no longer perfect (and the same
> > qualification should apply to what I responded to Shen),
> > because there is only 1 bit of entropy per character. This
> > means that the probability of plaintexts is extremely
> > slanted. To the point where brute forcing this entire
> > message would only be a matter of around 400 bits, instead
> > of the 3200 bits that it should be.
> The probability of plaintexts in English is independent of the
> encryption method. The probability of the plaintext given the cyphertext
> is uniform if using a one time pad. (Once, not 1+epsilon, see Venona.)
No, the probability of a given plaintext is *not* uniform.
If all that is known about the PT is that it is telegraphic
English, then "Nothing to report" is much more probable than
"Waverly wonderful", which is vastly more probable than
"Mstroupsipfhwwmgj".
Given a perfect-OTP-enciphered ciphertext of 17 characters
and no further information, the likelihood of each possible
17-character plaintext is proportional to its probability in
the parent population (telegraphic English).
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Wed, 03 May 2000 09:02:28 -0600
Reply-To: [EMAIL PROTECTED]
"Douglas A. Gwyn" wrote:
> "Tony T. Warnock" wrote:
> > Joseph Ashwood wrote:
> > > The problem with that theory is that using that theory, a
> > > OTP on top of English is no longer perfect (and the same
> > > qualification should apply to what I responded to Shen),
> > > because there is only 1 bit of entropy per character. This
> > > means that the probability of plaintexts is extremely
> > > slanted. To the point where brute forcing this entire
> > > message would only be a matter of around 400 bits, instead
> > > of the 3200 bits that it should be.
> > The probability of plaintexts in English is independent of the
> > encryption method. The probability of the plaintext given the cyphertext
> > is uniform if using a one time pad. (Once, not 1+epsilon, see Venona.)
>
> No, the probability of a given plaintext is *not* uniform.
> If all that is known about the PT is that it is telegraphic
> English, then "Nothing to report" is much more probable than
> "Waverly wonderful", which is vastly more probable than
> "Mstroupsipfhwwmgj".
> Given a perfect-OTP-enciphered ciphertext of 17 characters
> and no further information, the likelihood of each possible
> 17-character plaintext is proportional to its probability in
> the parent population (telegraphic English).
That's correct; what I should have said is that the probability of the
plaintext is not changed by knowing the cyphertext. Using a one time pad, all
cyphertexts are equally probable.
------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: Deciphering Playfair (long)
Date: Wed, 03 May 2000 15:12:35 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Message 2:
> Ciphertext:
>
FWFUIVGXVCZOWZYLEOXPIAPDUGNMLOAYXNQLQLTDNLYWXTOWXLYFVOUTZIAYEYWIYQOLYQV
Is there a typo in this post? Or does the ciphertext really have an odd
number (71) of letters?
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Last Chance?
From: John <[EMAIL PROTECTED]>
Date: Wed, 03 May 2000 08:22:00 -0700
Check...
http://www.aasp.net/~speechfb
I can only say I am beta-testing EspKline. The code is VERY
intriguing. If you want in, hurry, as they are only taking
applications for testing until May 15th. Oh, click on DEMOs and
the free encryption software link when you get there. There
other stuff is OK, too, if you like talking computers.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cascading Crypto Attack
Date: Wed, 03 May 2000 08:27:04 -0600
In article <[EMAIL PROTECTED]>, Richard Heathfield
<[EMAIL PROTECTED]> wrote:
> If this is so, I have a suggested attack for any crypto system ever.
>
> Given any ciphertext, progressively weaken it by applying more and more
> encryptions of different kinds to it, until eventually the plaintext is
> revealed.
>
> Like the well-loved 1 == 2 proofs, this is (a) counter-intuitive and (b)
> surely wrong. Yet it proceeds logically from the proposal that
> successive encryptions weaken security.
>
> Where is the flaw?
>
The flaw is in the *different kinds* area. But the saving grace for the
attacker is that most will not use drastically different kinds.
In my jargon, an inductive algorithm works against running into yourself
by never returning a previous location as in the GVA. If the length of
ciphertext is ever so much more than plaintext, you should be able to
visualize this.
Not forgetting another option, the bases for Pt/Ct in my base translation
algorithms increase the amount of output information as a combination of
base and groupsize.
While the GVA is sufficient unto itself for strong encryption that your
attack cannot touch, a base translation scheme can simply be included as a
layer in what many are already doing, and give any attacker a bad hair
day, if shortly later he has any left.
--
Laughter is often the most pleasing result of successful analysis.
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: STU-III
Date: Wed, 03 May 2000 15:18:21 GMT
On Wed, 03 May 2000 09:09:10 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
Thanks.
>> What's a STU-III ?? This sounds all mystic...
>> Type I algorithm ? Hmm sometimes one really wishes to be able to read
>> other people's mind ! ;-)
>
>I think Doug Stell was assuming that anyone who asked the
>question would understand the terminology.
I did, in deed, assume that.
>STU III -- a secure telephone, using a "crypto ignition key"
>to authenticate the user, with a centralized Key Management
>Center located in Maryland. A newer secure telephone (with
>backward compatibility) is supposed to be fielded soon.
The CIK accomplishes other things as well. It binds a specific user to
a specific phone. You CIK works in your phone and in no other phone.
You carry your CIK on your person, whereas the phone is in a fixed
location. The CIK also allows detection of someone making a copy of
your CIK and using your phone with the copied CIK.
>Type I encryption -- high-grade encryption authorized by
>NSA/CSS for protection of the most sensitive information.
>A Type I algorithm is designed to withstand the best
>cryptanalytic efforts expected for several decades.
Good definition of Type 1.
Now for the benefit of our readers, here are unofficial definitions of
the other major Types.
Type 2 is medium-grade encryption authorized by NSA/CSS for the
protection of Sensitive But Unclassified (SBU) data. The now
declassified SKIPJACK and KEA are Type 2 algorithms. Before their
declassification they here implemented in hardware via the FORTEZZA
card.
Type 3 is a commonly used term, but doesn't really exist. It is
commercial-grade encryption. IDEA, RSA, CAST and the usual stuff
talked about in this forum are in this category.
Type 4 use to also be a commonly used term, but also doesn't really
exist. It was whatever the U.S. would allow to be broadly exported.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 15:44:53 GMT
Tom St Denis wrote:
> > You can then feed the resulting shared key to md5 and use the resulting
> Sorry I wasn't clear I was planning on doing ElGamal not DH. However I
> don't think adding DH to CB is a bad idea either.
>
> What about this modification to DH encryption...
>
> You have a private key x, and public key y=g^x
y=g^x mod M, of course... I assume you left out the "over prime field M" for
short-hand.
> if I want to send a message I make up a 'j', (and send y^j) and use the
> hash of y^j as the symmetric key. This means the ciphertext will be the
No no! You use the shared key or some derivative thereof as the symmetric key.
Then you can either a) handshake a session key via a symmetric algorithm using
the derived key, or b) just use the derived key using your session key.
> Any ideas to speedup size-reduce signatures? I don't want to reduce the
> size of the group though (i.e DSS).
DH, alas, cannot be used as a classic RSA "signature" algorithm (i.e., where
the signature can be decrypted by the public key to verify that it was
produced by the private key), since it requires that the recipient's public
key be available to the sender. DH-derivative ElGamal, as you've noted, can be
used that way but has a rather bulky signature (as you've also noted). You may
wish to check the IEEE 1363 site, though, http://grouper.ieee.org/1363/ , for
an elliptic curve version of ElGamal that has a more compact signature. Mike
Rosing's book "Implementing Elliptic Curve Cryptography" ISBN 1-884777-69-4)
is also an excellent tutorial. Check out his coverage of the Nyberg-Rueppel
signature scheme in chapter 10 (Advanced protocols, signatures). If you have
trouble finding the book, leave me EMAIL.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: GPS encryption turned off
Date: Wed, 03 May 2000 11:37:37 -0400
Paul Rubin wrote:
>
> This is being discussed to death on sci.geo.satellite-nav.
>
> Quick summary: there are *two* GPS signals (separate frequencies),
> the C/A (course acquisition) signal, and the P/Y (precision) signal.
>
> The C/A signal's inherent accuracy is about 15-20 meters, but until
> yesterday it had been intentionally fuzzed ("Selective Availability"
> or SA) to 50 meter accuracy or so, to impede accurate targeting of
> homemade cruise missiles and other nasty uses.
Interestingly enough, SA has been turned off before. For
example, during the Gulf War, so the US military could use
commercial off the shelf GPS units and get good accuracy.
(Apparently they couldn't get enough P/Y units.)
>... Yesterday the inaccuracy was removed, almost certainly
> permanently.
I wonder on which you base that "almost certainly". It was
trivial to turn off; it's equally trivial to turn back on.
paul
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 11:20:21 -0500
Well, yes and no. By all means stand and fight. When it is a fight worth
fighting. Given that Tom can acquiesce today and add RSA back into
CryptoBag at the end of September, when the patent expires, it's hard
to justify fighting. While he would **likely** win in court, unless he
counter-sued and won the countersuit, he might well be out serious
money. Which means that he'd lose.
I'd be inclined to not only acquiesce now, but as soon as the patent expires,
add RSA back into CryptoBag and send a copy of it to the RSA goon (or
is the correct term moron? Technical terms like that often escape me) who
sent the "cease and desist" letter.
Choose your fights wisely. Very few people can take on the world and win.
"Trevor L. Jackson, III" wrote:
> > It's called I am an 18 year old kid. Why would I throw my life away
> > just to have RSA patented technology?
>
> If you react to any threat with compliance, you make your self a victim.
> That's throwing your life away.
>
> >
> >
> > I can get by with Cryptobag and PB3 by using other algorithms.
>
> Notice the terms you are using. Is it your intention to "get by", meaning
> merely achieve the bare minimum, in the other important things in your life?
> If your life is worth living is it worth living _well_. That means doing the
> right thing in the face of conflict. Read some Churchill.
--
Jeff Williams
Software Design Engineer
DNA Enterprise, Inc
1240 E Campbell Rd, Richardson, TX, 75081
972 671 1972 x265
[EMAIL PROTECTED]
Did you know that there is enough sand in
north Africa to cover the entire Sahara?
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: quantum computation FAQ?
Date: Wed, 03 May 2000 10:24:24 -0500
John A. Sidles wrote:
>
> See also Peter Schor's review article, released today,
> on the xxx.lanl.gov preprint server:
>
> http://xxx.lanl.gov/abs/quant-phys/0005003
^^
delete the ys and it'll work better.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: GPS encryption turned off
Date: 3 May 2000 16:20:39 GMT
Paul Koning <[EMAIL PROTECTED]> wrote:
>Interestingly enough, SA has been turned off before. For example,
>during the Gulf War, so the US military could use commercial off the
>shelf GPS units and get good accuracy. (Apparently they couldn't get
>enough P/Y units.)
The Gulf War was before GPS was declared fully operational. The
military has plenty of P/Y units now. (Yes I know about the Warthog
incident in 1997 too, but that was of very brief duration, unannounced,
and until recently, officially unconfirmed).
>>... Yesterday the inaccuracy was removed, almost certainly permanently.
>
>I wonder on which you base that "almost certainly". It was
>trivial to turn off; it's equally trivial to turn back on.
It is only trivial to turn on and off in the sense that it's done
(figuratively) by flipping a switch. It was very difficult
politically to turn it off, and I think it will be politically
impossible to turn it back on, once enough civilian services depend on
it. There's also supposed to be no need to turn it off any more. The
delay in turning it off (up til now) was while the military developed
equipment for locally jamming the signal.
See sci.geo.satellite-nav for much more about all of this.
------------------------------
Date: Wed, 03 May 2000 12:34:07 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
"David Formosa (aka ? the Platypus)" wrote:
> On Wed, 03 May 2000 08:20:20 -0400, Trevor L. Jackson, III
> <[EMAIL PROTECTED]> wrote:
> >Tom St Denis wrote:
>
> [...]
>
> >> It's called I am an 18 year old kid. Why would I throw my life away
> >> just to have RSA patented technology?
> >
> >If you react to any threat with compliance, you make your self a victim.
> >That's throwing your life away.
>
> Its easy for you to say your not the one taking the risks.
What risks do you perceive (other than letters from lawyers)?
If Tom is using techniques not patented in Canada he is not exposed to risks.
If he _is_ using techniques that are patented in Canada, he should cease doing
so for ethical reasons rather than "risks".
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC6 as a Feistel Cipher
Date: Wed, 3 May 2000 09:18:01 -0700
Francois Grieu <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> However, I believe (without reference) any cipher can be reduced to a
> Feistel Cipher with enough rounds and appropriate choice of round
> function among the 2^(64*(2^64)) possible at each round and for each key.
This is known not to be (strictly) true.
Feistel Networks are known to generate only even permutations. Therefore,
the "block cipher" that (for a particular key) did the permutation:
000...0000 -> 000...0001
000...0001 -> 000...0000
Everything else encrypts to itself
Then, there is no Feistel Network of any length that could simulate that.
However, this has no relevance to your question on RC/6, which is an even
permutation. And, it is known that any even permutation can be generated by
a Feistel Network.
--
poncho
------------------------------
Date: Wed, 03 May 2000 17:54:15 +0100
From: Andoni <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on
judging by the amount we're f*cked out of our wages in this country by
all the tax we pay im surprised you said that. they must have tons of
paper stuff lying around to throw at security and it systems.
Dan Day wrote:
>
> On Tue, 02 May 2000 15:16:50 GMT, [EMAIL PROTECTED] (JimD) wrote:
> >>
> >>This crap is getting out of hand.
> >
> >Yes. But they won't have the staff, technical or financial
> >resources to do it.
>
> Once they have the means, they'll make sure they solve the
> resource problem...
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: RC6 as a Feistel Cipher
Date: 3 May 2000 09:23:30 -0700
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
> However, I believe (without reference) any cipher can be reduced to a
> Feistel Cipher with enough rounds and appropriate choice of round
> function among the 2^(64*(2^64)) possible at each round and for each key.
I must admit I don't see it. Why should this be true? I'm skeptical...
------------------------------
** 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
******************************
