Cryptography-Digest Digest #31, Volume #12 Thu, 15 Jun 00 00:13:00 EDT
Contents:
Re: small subgroups in Blum Blum Shub (lordcow77)
Re: Why the golden ratio? ("Douglas A. Gwyn")
Re: Cipher design a fading field? ("Trevor L. Jackson, III")
Re: Cryptographic voting (Greg)
Re: Interesting Magazine Article (Mike, Copperhead) ("Trevor L. Jackson, III")
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Generating Keys for 3DES on the fly... ("Brian McKeever")
Re: Evidence Eliminator Dis-Information Center ([EMAIL PROTECTED])
Re: Is Gretchen down? (Patrick Farrell)
Re: On using compression as proper means of encryption ("John A. Malley")
Re: Maurer & Massey's result on cascade ciphers (was: Multiple (Nicol So)
Re: small subgroups in Blum Blum Shub (Nicol So)
Re: small subgroups in Blum Blum Shub (tomstd)
----------------------------------------------------------------------------
Subject: Re: small subgroups in Blum Blum Shub
From: lordcow77 <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 18:08:23 -0700
Essentially, the existence of exploitable cycles in BBS would
neccesarily lead to an efficient algorithm for decomposing RSA
moduli into primes. As such, if you believe that the factoring
of numbers in that range is a difficult problem, you need not
loose sleep over the miniscule probability that you will land in
a short cycle. The nonsense about choosing "strong primes" or
good initialization values is a remnant to the past where it was
thought that a relatively small prime (if well chosen) would be
adaquately strong. These days (thanks to the NFS and related
algorithms), everybody should use large moduli as a matter of
course.
* 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: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Why the golden ratio?
Date: Thu, 15 Jun 2000 01:15:02 GMT
[EMAIL PROTECTED] wrote:
> However, there is a formula like what you have mentioned: it isn't all
> that simple, and it is due to Srinavasa Ramanujan...
> http://mathworld.wolfram.com/GoldenRatio.html
Hm, okay, that's not exactly trivial, but I bet one could find a
similar identity for almost any similar irrational number.
phi(phi-1) = 1
tau(tau-2) = 1
etc. I.e. I don't think it points up anything special about phi.
------------------------------
Date: Wed, 14 Jun 2000 21:30:34 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
"Douglas A. Gwyn" wrote:
> "Trevor L. Jackson, III" wrote:
> > "Douglas A. Gwyn" wrote:
> > > Tim Tyler wrote:
> > > > If the size of the program is constrained, a halting determination program
> > > > could be written which enumerates all programs of that size or shorter and
> > > > lists whether they halt or not.
> > > It "lists" them how?
> > Turing programs can be written as input to a UTM. Such inputs are a sequence of
> > ones and zeros, so they are an integer. The list is ordered by the respective
> > integer values.
>
> You missed the point
Could be, but I doubt it.
> -- *how* does it determine whether they halt?
It doesn't. It simply reports the facts that are encoded by the author. Essentially
it's a lookup function. The key question becomes whether the program can be written
small enough to fit within itself (this is a data compression issue). If so then the
Halting Problem can't be constructed because such a lookup program will halt after
reporting that it will do so.
>
>
> > ... Is there any reason to believe that the growth in our
> > understanding of the universe will stop in the near future?
>
> No, but that is not a counterargument. All knowledge is contextual,
> and if some physical knowledge has been properly validated, it holds
> in the context for which it was established, even if more is
> discovered later. For our most fundamental physical principles,
> that is already a wide context indeed.
I suspect you have missed this point. Of the knowledge that was known to science over
the last 500 years most of it was wrong. Some of the problems were of the form of
limited context, such as the extension of Newtonian mechanics near the speed of light,
and some of it was simply incorrect, such as epicycles, tomatoes are poisonous due to
their similarity to nightshade, bleeding the sick allows bad humors to escape, black
holes are black, charge is conserved, the coldest spot in the solar system is the back
of Mercury. The former's correctness can be preserved by bounding the valid
contexts. The latter's correctness cannot be preserved.
The fact is that _everything_ is subject to revision in light of new information. Any
other attitude is a religious one.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Thu, 15 Jun 2000 01:20:19 GMT
> Now, obviously this isn't going to work in California, but most
> of the rest of the country doesn't support voting fraud and it
> should work there.
Now what on earth leads you to believe this? Read Vote Scam by
Devvy Kidd. She talked about running for office in a state other
than CA (IIRC) and she discusses many problems across this nation.
See www.devvy.com for more information.
Again, unless you know how many people should and did vote, you
have no idea which votes are legitimate. Our system of secret
ballot forces us to trust someone and that usually leads to
corruption. And would you expect to know about it if it exists?
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Wed, 14 Jun 2000 21:50:37 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Interesting Magazine Article (Mike, Copperhead)
Anton Stiglic wrote:
> Mok-Kong Shen wrote:
> >
> > John Savard wrote:
> >
> > > An "Invention and Technology" special by American Heritage magazine
> > > has an article on "Breaking Codes Without Computers", which talks
> > > about many of the special-purpose codebreaking machines used by the
> > > U.S. during World War II. The author has a book coming out this
> > > October.
> >
> > I tend to consider 'special-purpose machines' to be 'computers'. What
> > we commonly call 'computers' are 'general-purpose computers', while
> > there are 'special-purpose computers', e.g. for solving some problems
> > in physics more efficiently. I guess it is certainly very interesting to
> > know
>
> A hardware implementation of Twinkle would be a 'special-purpose
> machine"
> for factoring.
> Hardware computing DES is a special-purpose machine for encrypting or
> decrypting with DES. A supercomputer is
> a 'special-purpose machine' for doing parallel computations.
> A pentium III in which you run a program for factoring is *not* a
> special-purpose machine.
Welllll, maybe. Consider that Microsoft(tm) has been advising Intel on
architectural issues for a long time now. I don't think it would be too great
a stretch to characterize a Pentium III as a special purpose machine for
running Windoze software. ;-)
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 01:39:29 GMT
On Wed, 14 Jun 2000 18:08:23 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt lordcow77
<[EMAIL PROTECTED]> wrote:
>Essentially, the existence of exploitable cycles in BBS would
>neccesarily lead to an efficient algorithm for decomposing RSA
>moduli into primes. As such, if you believe that the factoring
>of numbers in that range is a difficult problem, you need not
>loose sleep over the miniscule probability that you will land in
>a short cycle. The nonsense about choosing "strong primes" or
>good initialization values is a remnant to the past where it was
>thought that a relatively small prime (if well chosen) would be
>adaquately strong.
I think your interpretation is wrong, and I recommend the BB&S paper
to you:
Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
Plenum Press: New York. 61-78.
BB&S did expect large primes; the requirement for "special" primes was
to guarantee that the system had cycles of some long, known and
computable length. The existence of cycles of known length made it
possible to efficiently check that any particular initial value x0 was
on such a cycle, and to choose another x0 if not. Short cycles
certainly do exist in BB&S, and short cycles are "exploitable." The
selection procedure thus eliminates the possibility that x0 is on a
short cycle, and so provides a *guarantee* of that form of strength.
That sort of a *guarantee* is simply not present when we just choose
x0 at random and hope for the best, even if x0 is very, very likely to
be on a long cycle.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Brian McKeever" <[EMAIL PROTECTED]>
Subject: Re: Generating Keys for 3DES on the fly...
Date: Wed, 14 Jun 2000 19:15:58 -0700
"Rich Beaudry" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hello,
>
> My company has a product that requires user logon. The username/password
is
> stored in a database (in cleartext ... please don't laugh!).
>
> I could probably just SHA the passwords, and store that, but I am required
> to use 3DES for the final encryption (don't ask...)
This is what is generally done, since it is rarely necessary (and often
undesirable) to be able to go backwards (ie to retrieve the user's password
given the entry in the DB). Usually, you just want to verify that what they
entered now is the same as what they entered before, so you compare hashes.
One option you have is to use 3DES as a hash function (like Unix hash()),
where you would encrypt a fixed/known string with a key derived from the
user's password.
Your other suggestions sound like they would amount to using 3DES to hash
(rather than "encrypt", since "encrypt" implies invertibility) the password.
If this is what you do, you are better off using a standard method than
cooking up your own. There are many ways to make bad hashes out of good
ciphers.
> And while I have your attention, the vendor of the encryption libraries
> touts them as certified by NIST to be "cryptographically correct". That
> impressed my boss, but does it impress you?
Maybe. It depends how loosely they mean that. It could mean anything from
"we checked it against test vectors published by NIST" (I should hope so!)
to "a team from NIST checked our source and compiled it to binary for us in
case there were trojan horses in our own compilers" (fairly impressive, if
excessive and paranoid)
HTH,
Brian
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Evidence Eliminator Dis-Information Center
Date: Wed, 14 Jun 2000 19:33:00 -0700
EE Detractor - speaking for us all, protector of newbies, patron saint of
widows and small children
EE Detractor-ooney, making coffee....
"EE Detractor" wrote
> Rather than merely disrupting the newsgroup, his goal is apparently to
> increase sales by snagging the constant influx of newcomers. He's not
> your typical troll but a spammer who trolls to advertise his product
> and make money. Keeping quiet, as we would with a normal troll, only
> works in his favor by letting him pitch his product without challenge.
------------------------------
From: Patrick Farrell <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Is Gretchen down?
Date: Wed, 14 Jun 2000 21:50:15 -0500
Reply-To: [EMAIL PROTECTED]
Thanks for the input on the first few points.
Well you would think that they would need permission from the carriers to do
this. I mean you can't even splice into a 10baseT connection without issues, I
don't see how you could tap into a fiber connection without having the carrier
do it for you, but maybe they just don't release that technology to the public
:)
If they were having the carriers do it, I would find it hard to believe that
with the ammount of people that would be involved at each major carrier that
they could keep the secret of these taps from the public.
Patrick
Joseph Ashwood wrote:
>
> > A) you need a pipe equivilant to the sum of the major backbones.
> Not if you have a significant computer present at each of those backbones
> that performs a significant portion of the filtering for you, then you would
> only need a much smaller pipe. Also remember that the vast majority of hose
> pipes remain unfilled almost all the time.
>
> >
> > B) you need a computer or cluster that can read and filter on the fly this
> > ammount of information
> Which can be done, for proof I simply point to the fact that these pipelines
> are running, so it can obviously be read. The traffic is being generated by
> a small portion of the cpu in a small portion of the computers in the world,
> a trojan would be an ideal way to get the processor time needed, after all
> the attack is obviously not bounded by lawfulness.
>
> >
> > C) you need a network interface for a data pipe that doesn't exist.
> Except that by segmenting the necessities you require much smaller network
> interface, on a much smaller pipe.
>
> >
> > D) how does a system with IP range A, on subnet B, see data between
> systems C
> > and D with completely seperate subnets when the data is never even routed
> across
> > A's network. Unless you are implying that they have a vampire tap on
> every
> > major circuit and subcircuit that duplicates all traffic and then reroutes
> it to
> > their hosts.
> They would be forced to have a vampire on each of the major backbones, or at
> least the ones with anything of interest. It would be a massive undertaking,
> cost a hundred million dollars or so (just a very rough guess), but it is
> possible. The next questions should be: what are the necessary backbones?
> where is the best location to tap them?
> Joe
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Wed, 14 Jun 2000 20:28:06 -0700
Mok-Kong Shen wrote:
>
> However, a compression algorithm can be employed in such a
> way that secret informations not available to the opponent
> are necessary to decompress in order to recover the
> original plaintext. Thus to regard compression to be not a
> full-fledged element in the toolbox of crypto designers is
> clearly misguided. I like therefore to describe in the
> following a concrete encryption scheme based on compression:
>
Mr. Shen -
I recommend Mojdeh Mohtashemi's Master's Thesis "On the Cryptanalysis of
Huffman Codes."
She provides some general results on the difficulty of the
cryptanalysis.
http://theory.lcs.mit.edu/~cis/theses/mohtashemi-masters.ps
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Maurer & Massey's result on cascade ciphers (was: Multiple
Date: Wed, 14 Jun 2000 23:30:00 -0400
Reply-To: see.signature
"David A. Wagner" wrote:
>
> In article <[EMAIL PROTECTED]>, Nicol So <see.signature> wrote:
> >
> > I've had a problem with the result of Maurer and Massey for a long time.
> > Basically, I think the result is "wrong". The (counter-)example they
> > gave in the paper does not demonstrate the informal statement of the
> > result. The definition of a secure cipher implicitly used in the paper
> > is, in my opinion, unnatural. For a cipher to be secure, it should be
> > secure w.r.t. all distributions of inputs. That's not the case with the
> > "secure" ciphers in their example.
>
> It sounds like you don't care too much for their definitions; you prefer
> different ones. That's ok. Their point remains. If all we care about
> is ciphertext-only security when the plaintext is distributed like ASCII
> English, and if the _only_ way we ever measure security is via this threat
> model, then a cascade of two ciphers may be weaker (_under this metric_)
> than the second cipher.
>
> I agree that, as you say, in practice our metrics are much more demanding.
> We insist that our ciphers be secure not just against plaintext distributed
> like English is, but against plaintext that is _chosen by the attacker_.
> Note that the chosen-plaintext security requirement is an even stronger
> requirement than just insisting that the cipher be secure for all plaintext
> distributions, since in the chosen-plaintext model the attacker usually is
> free to _adaptively_ choose the plaintexts.
Maurer and Massey's informal statement of their result sounds more
surprising that it really is. On the surface, it contradicts a "folklore
theorem" of cryptology, which Even and Goldreich proved in their paper
"On the Power of Cascade Ciphers". Simple, unqualified informal
statements often have profound implications, and when improperly
understood, can produce profound misunderstanding.
"Acceptable input distribution" is not part of the usual models of a
cipher. When a cipher is described as "secure", it is natural for people
to expect it to be secure w.r.t. all input distributions. When I said
that a secure cipher should be secure w.r.t. to all input distributions,
I wasn't suggesting that being so is sufficient for security. Rather, I
was pointing out that the property is expected of all secure ciphers
with no concept of "acceptable input distributions".
If add the concept of "acceptable input distribution" to the usual
models of a cipher, then a natural question to ask when cascading two
ciphers would be: does the output distribution of the first cipher match
the acceptable input distribution of the second? If we look at Maurer
and Massey's example in this light, it is hardly surprising that the
composition fails to be secure. There is an obvious interface mismatch
problem! Things not used as designed are not expected to work!
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 14 Jun 2000 23:56:51 -0400
Reply-To: see.signature
Terry Ritter wrote:
>
> On Wed, 14 Jun 2000 18:08:23 -0700, in
> <[EMAIL PROTECTED]>, in sci.crypt lordcow77
> <[EMAIL PROTECTED]> wrote:
>
> >Essentially, the existence of exploitable cycles in BBS would
> >neccesarily lead to an efficient algorithm for decomposing RSA
> >moduli into primes. As such, if you believe that the factoring
> >of numbers in that range is a difficult problem, you need not
> >loose sleep over the miniscule probability that you will land in
> >a short cycle. The nonsense about choosing "strong primes" or
> >good initialization values is a remnant to the past where it was
> >thought that a relatively small prime (if well chosen) would be
> >adaquately strong.
>
> I think your interpretation is wrong, and I recommend the BB&S paper
> to you:
>
> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
> Plenum Press: New York. 61-78.
>
> BB&S did expect large primes; the requirement for "special" primes was
> to guarantee that the system had cycles of some long, known and
> computable length. The existence of cycles of known length made it
> possible to efficiently check that any particular initial value x0 was
> on such a cycle, and to choose another x0 if not. Short cycles
> certainly do exist in BB&S, and short cycles are "exploitable." The
> selection procedure thus eliminates the possibility that x0 is on a
> short cycle, and so provides a *guarantee* of that form of strength.
> That sort of a *guarantee* is simply not present when we just choose
> x0 at random and hope for the best, even if x0 is very, very likely to
> be on a long cycle.
lordcow77's interpretation is correct. The safety of using randomly
chosen primes of appropriate sizes is built into the underlying
intractability assumption. To put things in perspective, the whole point
of using cryptography is to reduce the probability of "bad things
happening" to some acceptably low level, say 2^{-L} for some
sufficiently large L. (There's no defense against dumb luck on the part
of the adversary). Not using special primes may affect the value of L
for a given choice of security parameter (so you may have to adjust your
security parameter), but it does not affect the asymptotic behavior of
security as a function of the security parameter.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
Subject: Re: small subgroups in Blum Blum Shub
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 21:06:01 -0700
In article <[EMAIL PROTECTED]>, Nicol So
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Wed, 14 Jun 2000 18:08:23 -0700, in
>> <[EMAIL PROTECTED]>, in sci.crypt
lordcow77
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Essentially, the existence of exploitable cycles in BBS would
>> >neccesarily lead to an efficient algorithm for decomposing
RSA
>> >moduli into primes. As such, if you believe that the
factoring
>> >of numbers in that range is a difficult problem, you need not
>> >loose sleep over the miniscule probability that you will
land in
>> >a short cycle. The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it
was
>> >thought that a relatively small prime (if well chosen) would
be
>> >adaquately strong.
>>
>> I think your interpretation is wrong, and I recommend the
BB&S paper
>> to you:
>>
>> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-
Random
>> Number Generators. Advances in Cryptology: CRYPTO '82
Proceedings.
>> Plenum Press: New York. 61-78.
>>
>> BB&S did expect large primes; the requirement for "special"
primes was
>> to guarantee that the system had cycles of some long, known
and
>> computable length. The existence of cycles of known length
made it
>> possible to efficiently check that any particular initial
value x0 was
>> on such a cycle, and to choose another x0 if not. Short
cycles
>> certainly do exist in BB&S, and short cycles
are "exploitable." The
>> selection procedure thus eliminates the possibility that x0
is on a
>> short cycle, and so provides a *guarantee* of that form of
strength.
>> That sort of a *guarantee* is simply not present when we just
choose
>> x0 at random and hope for the best, even if x0 is very, very
likely to
>> be on a long cycle.
>
>lordcow77's interpretation is correct. The safety of using
randomly
>chosen primes of appropriate sizes is built into the underlying
>intractability assumption. To put things in perspective, the
whole point
>of using cryptography is to reduce the probability of "bad
things
>happening" to some acceptably low level, say 2^{-L} for some
>sufficiently large L. (There's no defense against dumb luck on
the part
>of the adversary). Not using special primes may affect the
value of L
>for a given choice of security parameter (so you may have to
adjust your
>security parameter), but it does not affect the asymptotic
behavior of
>security as a function of the security parameter.
I don't know why people still consider the BBS generator. It's
not very safe.
Let's ask some questions:
1. How do you use it? Well construct "special" primes and use
a relatively prime root. I have seen to use 3 mod 4 primes and
p- strong primes...
2. What is the period? Gosh-geez I dunno, pretty darn big!
3. How fast is it? Well at 2kb/sec we now have the fastest
prng.
Woopy. It's hard to use, big and slow. BAD IDEA!
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** 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
******************************
