Cryptography-Digest Digest #521, Volume #10 Sun, 7 Nov 99 17:13:03 EST
Contents:
Re: addition chains ? (David A Molnar)
Re: Best Asymetric Key System? (David A Molnar)
Re: Proposal: Inexpensive Method of "True Random Data" Generation
Re: What sort of noise should encrypted stuff look like?
Re: Some humble thoughts on block chaining (SCOTT19U.ZIP_GUY)
Re: PGP Cracked ? (Jerry Coffin)
Re: The Code Book Mailing List (Jerry Coffin)
Re: XOR Knapsacks (Oh no! not again?) ("Douglas A. Gwyn")
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: Passwords - the weak link ("John E. Kuslich")
Re: XOR Knapsacks (Oh no! not again?) (David Wagner)
Re: secrecy/generation of IV (David Wagner)
Re: secrecy/generation of IV (Allen Landsidel)
Re: Lenstra on key sizes ("Roger Schlafly")
Re: What sort of noise should encrypted stuff look like? (fungus)
Re: Lenstra on key sizes (fungus)
Understanding Cryptograpy--Where to start? (AIfred E Neuman)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: addition chains ?
Date: 7 Nov 1999 14:35:42 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
> It's not worth messing with this. There is a long section about
> addition chains in Knuth vol 2. Two-line summary:
> 1) finding the best possible addition chain is NP-hard, so don't bother.
> 2) The best possible chain is hardly ever more than slightly better
> than the obvious chain.
Thanks much.
Not only this, but I realized last night that they aren't appropriate for
my application -- the Miller-Rabin test seems to require looking at all
the intermediate products of a square-and-multiply to see if they are
nontrivial square roots of 1. Using an addition chain would generally skip
consecutive squares, which is bad...
Thanks,
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Best Asymetric Key System?
Date: 7 Nov 1999 14:38:28 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <803392$dup$[EMAIL PROTECTED]>,
> David A Molnar <[EMAIL PROTECTED]> wrote:
>> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> > I think ELGAMMA is the buzzword of the month now.
>>
>> YM Elgamal HTH,
> What does that mean?
I'm being snarky. YM = "You mean", HTH = "Hope that helps".
It's because I've never heard of ELGAMMA. I have heard of the _Elgamal_
public key cryptosystem, and I am assuming that's what you meant as
"buzzword of the month". If that's not it, what is ELGAMMA?
Sorry for the confusion,
-David
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: 7 Nov 99 15:13:29 GMT
Douglas Zare ([EMAIL PROTECTED]) wrote:
: John Savard wrote:
: > [EMAIL PROTECTED] (Alan Morgan) wrote, in part:
: >
: > >Not true (or rather, unknown). No one knows if there are 41 quintillion
: > >zeros in a row after the quintillionth digit.
: >
: > Apparently there IS a proof that this can't happen.
: >
: > For the square root of 2, there is a maximum limit to how good any
: > rational approximation to it can be, because its continued fraction is
: > repeating.
: >
: > For pi, there apparently is also a limit, called Mahler's theorem,
: > which says that for any rational number p/q, | pi - p/q | is greater
: > than q to the -42 power.
: > [...]
: Are you sure that this is the result, or just that this is the case for all
: q sufficiently large? (I don't just mean q>1.) Reviews of improvements such
: as (from Mathsicnet) 94b:11063 11J82 Hata, Masayoshi(J-KYOTY) "A lower bound
: for rational approximations to $\pi$." (English. English summary) _J. Number
: Theory_ 43 (1993), no. 1, 51--67 do not mention effective bounds. If one
: knows that only finitely many rationals are too close for some exponent,
: then there is some exponent we don't know such that it works for all q>1,
: but we still would not have any bound on that exponent, or the number of 0's
: that can occur after the nth place.
I was afraid of that, but I should have mentioned the qualification: that
*if the rec.puzzles archive had correctly reported the result*, this was a
true statement about pi.
Here, it is still true...but only after an immensely long stretch of
digits of unknown extent, and therefore not necessarily the case for any
particular finite stretch of pi that one might name.
: In a much more elementary sense, one might not view the digits of pi as
: uniformly distributed on the possibilities. First nonzero digits of
: constants are not uniformly distributed on {1,2,...,9} and there are reasons
: to believe that these should follow the induced measure from the uniform
: measure on the circle. The effect is smaller, but it is also more likely for
: a second digit to be 0 than 1, 1 than 2, etc. The total amount of usable
: information this gives one is finite, but so would either statement about
: rational approximations.
Actually, although that is the only scale-invariant law, it hasn't been
proved there is a law of first digits, and there are good reasons to
believe this doesn't apply to things like pi.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: What sort of noise should encrypted stuff look like?
Date: 7 Nov 99 15:08:39 GMT
Lincoln Yeoh ([EMAIL PROTECTED]) wrote:
: I have the impression most encrypted material look like white noise.
: Why not some other noise? e.g. pink noise and so on.
: Of course if there is precompression then we should make it follow the
: compressed stuff.
Well, because of the way in which information is transmitted, a
transmission that has the statistical properties of pink noise can be
transmitted more efficiently if it is compressed, and the result of the
compression will be something that looks like white noise.
If one has an analog channel instead of a digital one, and the noise level
in the channel is not uniform by frequency, then something other than the
characteristics of white noise may be optimal for a signal. But a digital
channel has a fixed resolution, and thus it acts like it has a constant
noise floor.
John Savard
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Some humble thoughts on block chaining
Date: Sun, 07 Nov 1999 16:40:30 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] () wrote:
>This isn't that crazy a notion; for that matter, David Scott's notion that
>large, key dependent S-boxes are useful isn't crazy either: witness
>Blowfish. His problem is that he makes unsupportable claims, such as that
>S-boxes with 65,536 entries or more are genuinely _necessary_ for adequate
>security, and IDEA is trivially weak, and things like that. Not only does
>he make such claims, he asserts them forcefully.
>
>John Savard
I think that when it comes to encryption one should never underestimate
the enemy. If is foolhardy to use something barely secure when history is
littered with broken codes that experts preached as secure. If one wants
to be secure one needs to use things that are by there very natures hard
to crack. The danger with most short keyed methods is that they are subject
to many forms of reduction by math experts. It is very hard to reduce a random
large S-box. So yes I recommend using simple encryption that always is on
the limits of the machine. True my large S-boxes my seem like over kill but
how long will the AES candidate of day hold up against future quatom compters.
Can one really say with honesty the NSA does not have such devices today.
Today I still mostly use encryption based on my 65,536 entry S box only
becasue I am still using my 486. When I get my K7 when ever that is you can
beat that I will being using much larger S-boxes. As machines get faster and
memmory cheaper I will try to be on the edge. Not just a few thousands bits
safer but millions.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: PGP Cracked ?
Date: Sun, 7 Nov 1999 09:56:39 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Jerry Coffin wrote:
> > Like Ken, AFAIK, he's never said _anything_ to confirm (or,
> > admittedly, deny) that it was actually done.
>
> I could swear that they have said the experiment was actually done,
> just that it was not in any of the UNIX distributions.
Well, obviously I haven't followed him around for the last 30 years to
verify everything he's ever said about it, but I just re-read the text
of the talk, and there he talks about what you _could_ do, how you
_would_ do, and so on, but carefully never says that it was ever
actually done. Since Mr. Ritchie has been kind enough to jump in
already, perhaps he'll be kind enough to clarify this as well; even if
he wasn't responsible for it in the first place, my guess is that if
it was done, he at least knew something about it...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: The Code Book Mailing List
Date: Sun, 7 Nov 1999 10:30:44 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Douglas A. Gwyn wrote:
>
> > "Trevor Jackson, III" wrote:
> > > Sure. Doug Gwyn specializes in factoring primes of arbitrary size
> > > into their two prime factors.
> >
> > Delete the "two" and you'll have it right.
>
> I consider One a prime because it is only divisible by one and itself.
He meant the "two" in "two prime factors". IOW, he means that if you
give him a prime of arbitrary size, he'll tell you it's prime
factorization quickly and easily (so will I for that matter).
Of course, finding the prime factorization of a prime is trivial --
what's difficult is finding the prime factorization of a large,
arbitrarily chosen composite that has at least a few prime factors
that are quite large.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: XOR Knapsacks (Oh no! not again?)
Date: Sun, 07 Nov 1999 17:55:27 GMT
Gary wrote:
> Can the subset creating Z be found?
Not unless there is a lot of special structure in X.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 7 Nov 1999 06:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: Passwords - the weak link
Date: Sun, 07 Nov 1999 10:35:51 -0700
Legend has it that the ancient king offered a reward to one of his
subjects. He was so generous that the king allowed the subject to
specify the reward himself, promising to grant anything within reason.
The subject simply asked for a standard checkerboard with 64 squares,
and some rice. A mere one kernel of rice on the first square, two
kernels on the second square, four kernels on the third etc. according
to that pattern until each of the 64 squares had been accounted for.
The king looking at the small number of squares and the tiny size of the
rice kernel quickly agreed to the subject's request. Certainly this
could not amount to more than a few pounds of rice...
Wrong. This is the nature of exponential increase. It defies
intuition. The amount of rice for the 64th square could not be contained
by all the granaries on the planet. Likewise, an alphabet of 256
symbols even for a few small words can quickly amount to such a large
number of keys that exhaustive search is impossible.
The problem is remembering the "well chosen - random looking" password
without writing it down and changing it every thirty days because some
system administrator insists on this policy - of course, each of the
twenty five systems to which you have access require the same security
procedure. Also, don't forget all those password protected documents.
Have you ever tried to remember the password for a document two or thre
years after applying the password? Remember, it was your first
girlfriend's bra size...no it was your dog's favorite food...er..no it
was you mother's maden name...no it was your first born's first
word...no it is your wife's pet name for...
Maybe the government should enforce key escrow after all...you know, for
our own good.
...NAAAHH!
Password recovery software...that's the answer :--)
http://www.crak.com
JK
Raddatz Peter wrote:
>
> I'm a relative Newbie to Cryptography, but after doing some research I
> seem to come full circle to the same result. - "The weak link to ANY
> encryption algo is the PASSWORD."
> Here, in this Newsgroup, I've always seen the quote "what if your enemy
> has access to the same program that you are using...". Well, that being
> the case then any algo is just as weak as any other because it is
> susceptible to a password attack.
> Provided that the user is using one of the AES compliant algos it should
> be equally secure or insecure.
> Given the same program and the cipher an attack on the password should
> be able to decrypt the file in question. There is a finite number of
> combinations of chars, nums & other symbols that 256 symbols can yield.
> With today's highspeed computers these combinations should be able to be
> explored in no time flat.
> What am I missing here?
> Peter Raddatz
--
John E. Kuslich
Password Recovery Software
CRAK Software
http://www.crak.com
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR Knapsacks (Oh no! not again?)
Date: 7 Nov 1999 11:37:37 -0800
In article <803nj1$dpd$[EMAIL PROTECTED]>,
Gary <[EMAIL PROTECTED]> wrote:
> Given a set X={x0,x1,...,xn} of mn bit numbers where m>=2.
> S is a randomly selected subset.
> Z is the XOR of all elements of the subset S.
> Can the subset creating Z be found?
Sure, just use Gaussian elimination.
Write X as a mn by n+1 matrix, whose columns are the x's.
Write S as a n+1 bit column vector which is one in the j-th
position just if S includes the j-th element of X.
Write Z as a mn bit column vector.
Note that we have the equation XS = Z, which is linear over GF(2).
Note that X and Z are known.
Now just solve for S using linear algebra.
It should take cubic time at most (perhaps faster).
Hope I didn't make any mistakes.
FYI: you may find old sci.crypt posts on this topic by visiting
Dejanews.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: secrecy/generation of IV
Date: 7 Nov 1999 11:41:28 -0800
In article <[EMAIL PROTECTED]>,
Allen Landsidel <[EMAIL PROTECTED]> wrote:
> How important is it to keep the IV secret?
IV's may be public; there is usually very little reason to keep them secret.
> With that assumption in mind, is there any kind of general
> drawback to using, say, the first 64bits of the secret key as the IV,
> if the required IV is 64bits?
Yes, that's dangerous. There are chosen-ciphertext attacks which can
reveal the IV. If the IV contains part of the key material, you've just
allowed the adversary to get access to part of your key.
(Yes, Kerberos gets this wrong.)
Don't do it. Keep the key and the IV secret.
------------------------------
From: [EMAIL PROTECTED] (Allen Landsidel)
Subject: Re: secrecy/generation of IV
Date: Sun, 07 Nov 1999 19:48:08 GMT
On 7 Nov 1999 11:41:28 -0800, [EMAIL PROTECTED]
(David Wagner) wrote:
>IV's may be public; there is usually very little reason to keep them secret.
Ah, thats cool..
>Yes, that's dangerous. There are chosen-ciphertext attacks which can
>reveal the IV. If the IV contains part of the key material, you've just
>allowed the adversary to get access to part of your key.
>
>(Yes, Kerberos gets this wrong.)
>
>Don't do it. Keep the key and the IV secret.
Heh.. I thought you just said I don't need to keep the IV secret..
although I think it would be a good idea to do so.. one more step for
the possible interceptor to have to deal with figuring out.
I suppose D/H could be used to agree on IVs during a session just as
easily as using it to generate the key..
Thanks for the quick response.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Lenstra on key sizes
Date: Sun, 7 Nov 1999 10:56:41 -0800
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The mentality of the builders of the Titanic remains with us. ...
>
> A probably very stupid question concerning symmetric ciphers: Does
> it cost terribly more if one uses 512 bits of key instead of 256 bits?
Yes, apparently the Titanic mentality is still with us. Huge key
size does not make you invincible.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: What sort of noise should encrypted stuff look like?
Date: Sun, 07 Nov 1999 12:15:17 +0100
Lincoln Yeoh wrote:
>
> I have the impression most encrypted material look like white noise.
>
> Why not some other noise? e.g. pink noise and so on.
>
The "white noise" is only there because you're looking at the
output as a digitally encoded signal, which it isn't.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Lenstra on key sizes
Date: Sun, 07 Nov 1999 12:27:06 +0100
Mok-Kong Shen wrote:
>
> > It was, with the technology at that time. Then it was estimated to
> > take a few billion years to factor a 512-bit RSA modulus. Today,
> > 25 years later, it can be done in 7 months...
> >
> > This should be of great concern to anyone claiming some encryption
> > will take billions of years to crack, and where it's relly important
> > no-one will be able to crack it during at lest the next few decades...
>
> The mentality of the builders of the Titanic remains with us.
>
> A probably very stupid question concerning symmetric ciphers: Does
> it cost terribly more if one uses 512 bits of key instead of 256 bits?
>
You're confusing factoring with brute force searching, don't.
One system is based on assumptions in number theory, the other
is based on time taken to count to a high number (no shortcuts),
they are two different things.
Building a machine to count to 2^256 using today's technology
is impossible.
A future machine may be able to crack 256 bit ciphers, but the
same machine may also be able to crack your 512 bit cipher just
as easily. You can speculate about whether 512 bits is better
but at the end of the day that's all it is, speculation.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (AIfred E Neuman)
Subject: Understanding Cryptograpy--Where to start?
Date: 07 Nov 1999 20:36:22 GMT
Hello,
I'd like to develop an understanding of encryption technologies and am hoping
that this newsgroup can give me a place to start. What reference materials
should I access? Thanks in advance.
Alfred E. Neuman
------------------------------
** 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
******************************
