Cryptography-Digest Digest #54, Volume #12 Sun, 18 Jun 00 04:13:01 EDT
Contents:
Re: Weight of Digital Signatures (John Savard)
AWFUL PUN (was: Why the golden ratio?) (John Savard)
Re: Cipher design a fading field? ("John A. Malley")
Re: Cipher design a fading field? (Benjamin Goldberg)
Re: Cipher design a fading field? (Benjamin Goldberg)
Re: AWFUL PUN (was: Why the golden ratio?) (Dave Seaman)
Re: AWFUL PUN (was: Why the golden ratio?) (Michael L. Siemon)
Re: MD5 Expansion ([EMAIL PROTECTED])
Re: Multiple encryptions (Mack)
Re: Announce: Catacomb 2.0.0 prerelease (Andru Luvisi)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Mixing Xor and Addition (Terry Ritter)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Weight of Digital Signatures
Date: Sun, 18 Jun 2000 03:45:48 GMT
On Sat, 17 Jun 2000 19:52:13 GMT, Greg <[EMAIL PROTECTED]> wrote,
in part:
> WASHINGTON, June 16 -- The Senate voted unanimously
> today to approve a bill that catapults electronic
> commerce to a new level by allowing consumers and
> businesses to sign contracts online and know that
> their e-signature is just as binding as one in ink.
> The bill, which passed 87 to 0, has already been
> approved by the House and now goes to President
> Clinton, who said today that he would sign it
> into law.
>Off topic a bit, but worth a mention. Kudos to all who have had any
>hand in helping the government see the light (finally)...
I really don't know if this is good news.
A law that makes a digital signature "just as binding as one in ink",
when it is so much easier to break into someone's house and read their
hard drive than forge their signature perfectly makes ordinary people
much more vulnerable to forgery than before.
If my private keys, which I use to sign things, exist only in
encrypted form on my computer - so that every time I sign something
digitally, I have to enter my pass phrase - then I have the level of
control needed.
Right now, though, a secure credit card transaction is merely one
encrypted by means of the vendor's public key: the person at the other
end is only transmitting a credit card number. What if the law is so
worded that this is considered a "digital signature", although no
private key on the part of the "signing" party is involved? That is,
what if a stolen credit card number now binds its legitimate owner as
strongly as a signature in pen and ink? It's entirely possible the
law, if it fails to discuss technical issues, could be so worded as to
create such a situation.
Even if that doesn't happen, it is almost certain that people will be
making signatures legally "just as binding as one in ink" using
whatever insecure software is provided by their bank or stockbroker or
utility company...with little real choice in the matter. Hence, this
law could lead to so many people being victimized by insecure systems
- _as to create a clamor for a secure system, designed by the NSA,
with built in key escrow_ as a *preferable* alternative!
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 03:53:29 GMT
On Sat, 17 Jun 2000 03:05:51 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>On Thu, 15 Jun 2000 01:15:02 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
>wrote, in part:
>>[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...
>Oh, dear: that should be Srinivasa 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.
>Well, if that's the case, then there's a mathematician who went around
>telling us that Ramanujan and his equations were really something
>quite remarkable. I suppose he owes all of us an ... _apology_.
Nobody commented on this awful pun? (As the mathematician in question
is deceased, I suppose he can't do anything but rest on his laurels.)
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 17 Jun 2000 21:23:57 -0700
wtshaw wrote:
>
> In article <[EMAIL PROTECTED]>, "John A. Malley"
>
> > And this brings out the eerie truth that when the plaintext comes from a
> > non-Turing-recognizable language, even when one gets the plaintext and
> > its ciphertext there is NO algorithm able to decide which instance of
> > the decryption (and thus the key) produced the correct decryption
> > (candidate plaintext equal to the original plaintext.)
>
> Figure that a person with a gut instinct that leads to a solution is a
> part of an implemented algorithm that he decides to use. If you dismiss
> this etherial ingredient as nonessential in your discssion, you support
> the loss of the warm art of cryptanalysis.
That's a interesting point, Mr. Shaw. Hunches based on an
appreciation/knowledge of the situation (political, economic, military,
etc.) requiring the message help narrow down possible subject matters
of the message and probable words in it. Knowledge of the sender's and
recipient's personnel speech/writing habits (pet phrases, stereotyped
openings or closings, etc.) interests, hobbies, etc., may help narrow
down possible words or phrases. This produces possible "known" plaintext
to aid in cryptanalysis. Hunches can lead to recognized key reuse or
key changes, too. Such important activity is not dismissed as
nonessential and fits within the scope of the questions of decidable
cryptanalysis by algorithms ( heuristics or search strategies are
algorithms.)
The special case cited in the post involves a most strange and wonderful
thing, a language that is not recognized by a Turing Machine. The
strings in such a language cannot be generated by a Turing Machine.
There's no computer program we can write to make the strings of such a
language. The theory of computations tells us such languages (sets of
strings) exist.
That immediately raises this question : Can we even encipher and cipher
plaintext strings of a Turing-unrecognized language?
John A. Malley
[EMAIL PROTECTED]
Post script:
Could the set of all unique infinite strings of random bits be a
Turing-unrecognized language?
Could a finite set of finite strings of random bits be a
Turing-unrecognized language?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 18 Jun 2000 04:27:32 GMT
How much does the problem change, if we consider English as a
ciphertext, and 'knowledge' or 'understanding' as it's corresponding
plaintext?
You string of letters is an encoding of English text which is in turn
an encoding of knowledge; To determine if we have a correct decryption
of ciphertext-string into english we can test to see if there is a
valid decryption of the possible-english-string into knowledge.
Does this meme seem useful, or am I completely out of my mind?
Ben Goldberg
--
Help spread the meme meme! Append this to your signature virus.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 18 Jun 2000 04:27:35 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
>
> > Mok-Kong Shen wrote:
> > >
> > > Benjamin Goldberg wrote:
> > >
> > > > Mok-Kong Shen wrote:
> > > > >
> > > > > John Savard wrote:
> > > > >
> > > > > > Well, if the size of the RAM available to a program is limited, not
> > > > > > just the size of the program itself, then a program with N bits of
> > > > > > storage available to it can have only 2^N distinct states. Hence, if
> > > > > > it doesn't halt after 2^N instructions, it is proven that it will
> > > > > > never halt.
> > > > >
> > > > > You probably mean that execution of each intruction must lead to a
> > > > > single unique successor state. How about the case that this doesn't
> > > > > hold, i.e. when the state transition depends on the history?
> >
> > Hmm, the program has N bits of RAM total [call this the state], and and
> > to determine what will be the next state, not only uses all of those N
> > bits, but it magically remembers what those N bits used to be, and uses
> > that, too.
> >
> > I *think* that's what you're claiming.
>
> I don't understand. A program that recursively computes x=f(x) may
> be very large. But its state is just the current value of x.
When we say that RAM is limited, we are including the instruction stack.
If you recursively compute something, you are essentially allocating
memory on the stack with each call.
------------------------------
From: [EMAIL PROTECTED] (Dave Seaman)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: 17 Jun 2000 23:33:44 -0500
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>>Well, if that's the case, then there's a mathematician who went around
>>telling us that Ramanujan and his equations were really something
>>quite remarkable. I suppose he owes all of us an ... _apology_.
>Nobody commented on this awful pun? (As the mathematician in question
>is deceased, I suppose he can't do anything but rest on his laurels.)
I can hard(l)y stan(d) it.
--
Dave Seaman [EMAIL PROTECTED]
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/mumia/021700amnesty.html>
------------------------------
From: [EMAIL PROTECTED] (Michael L. Siemon)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 01:01:44 -0400
In article <8ihjf8$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Dave Seaman) wrote:
+ In article <[EMAIL PROTECTED]>,
+ John Savard <[EMAIL PROTECTED]> wrote:
+ >>Well, if that's the case, then there's a mathematician who went around
+ >>telling us that Ramanujan and his equations were really something
+ >>quite remarkable. I suppose he owes all of us an ... _apology_.
+
+ >Nobody commented on this awful pun? (As the mathematician in question
+ >is deceased, I suppose he can't do anything but rest on his laurels.)
+
+ I can hard(l)y stan(d) it.
Are you looking for a laurel, for this utterance?
--
Michael L. Siemon We must know the truth, and we must
[EMAIL PROTECTED] love the truth we know, and we must act
according to the measure of our love.
-- Thomas Merton
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MD5 Expansion
Date: Sun, 18 Jun 2000 04:57:08 GMT
In article <10839b68.9f89254c@usw-ex0104-
031.remarq.com>,
tomstd <[EMAIL PROTECTED]> wrote:
> Andrew Bortz <[EMAIL PROTECTED]> wrote:
> >In the interest of increasing the size of a
MD5 hash, I have
> been
> >thinking of a fairly simple method:
> >
> >1) Calculate the MD5 hash of the data
> >2) Permute the data, preferable at the
beginning, in some small
> manner
> >3) Calculate the MD5 hash of the new data, and
append to the
> original
> >hash
> >4) Lather, rinse, repeat as necessary/paranoid
> >
> >It seems as though it would work, and using
the 256-bit variant
> (one new
> >hash) it would appear as though it yields huge
advances in
> protection,
> >utilizing the apparent collision-free nature
of MD5.
> >
> >Finally getting the root of my question...
Since the hash
> method in its
> >entirety will/must be disclosed, it will be
possible for
> attackers to
> >possibly utilize the two hashes in some attack
to reveal the
> data
> >originally hashed. My question is, is MD5
secure enough to
> withstand
> >giving an attacker a significant statistical
peep at the data
> that was
> >hashed?
>
> From what I gather you want todo this
>
> A = H(M)
> B = H(L(A))
>
> Where M is the original message, L is a linear
transform and H
> is the hash function.
>
> This is no more secure then the original
underlying hash
> function and I will show why.
>
> We know that a collision by the birthday
paradox will take 2^64
> effort against MD5 (since it's a 128-bit
hash). However, a
> collision in A is sufficient to find a
collision in the entire
> hash. In otherwords your 256-bit hash can be
broken in 2^64
> guesses which is far under the birthday paradox
limit for a 256-
> bit hash.
>
> Tom
>
> Got questions? Get answers over the phone at
Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
>
Sorry, my news server sucks, so I'm using Deja.
Anyway, Your logic evades me. Just because we can
find 2 messages that have the same MD5 hash
doesn't mean those two messages, run through the
linear function, will have the same 2nd hash!
That is where I see the security of using 2
hashes: Even when a collision is found in MD5, it
will rarely have a collision in the 2nd hash
because one bit change in the message will
(supposed to) change on average half the bits of
the hash. The attacker is back to searching...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Multiple encryptions
Date: 18 Jun 2000 05:54:15 GMT
[EMAIL PROTECTED] wrote:
>
>If E(D(T)) is somehow parallel to a function F(T) that takes less time
>than E(D()) then you have increased security, but not double. If F(T)
>takes equal time as E() or D(), you have not changed anything (except
>making it slower to decrypt for legitimate users). If F() is less than E
>() or D(), then you clearly have screwed up.
>
>Andrew
>
If F() is less than E() or D() you have found a significant weakness
in one or both ciphers.
Mack
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Announce: Catacomb 2.0.0 prerelease
Date: 17 Jun 2000 23:32:01 -0700
[EMAIL PROTECTED] writes:
[snip]
> Is there any way to unpack .tar in Windows?
[snip]
I use cygwin from sourceware.cygnus.com. Comes with tar.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 07:45:12 GMT
On 17 Jun 2000 17:34:22 -0700, in
<8ih5ee$l5v$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David A. Wagner) wrote:
>[...]
>Well, now I'm curious. What was wrong with the old article at
>the URL above? It looked correct to me. What am I missing?
>I'd love to hear a technical refutation, if there is one...
Sure. Very easy. Disproof by contrary example, or false case. All
we need to find is one false case and the claim (that X^2 mod N is
proven secure without short cycle checks) fails.
Call the parameter to X^2 mod N (and N = P*Q) as x0. Make each of the
possible parameter values a proof case. Most of those cases will in
fact select or "be on" a long cycle, and when they are, call each of
these cases "secure." The issue is whether the system is proven to be
secure, which is to say, is it secure in every possible case?
We know that some cases will *not* select a long cycle, and indeed
some of those will select a degenerate or one-state cycle, which is a
static result from what is supposed to be a dynamic value generator.
Such cases are obviously not secure. That means that any proof which
claims that X^2 mod N without the BB&S recipe is secure, is thus shown
to be false.
It not coincidence that the true BB&S recipe eliminates such cases, so
there will be no cases which are insecure due to short cycle length.
Thus we see that the true BB&S does in fact pass at least this simple
proof check.
---
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: small subgroups in Blum Blum Shub
Date: Sun, 18 Jun 2000 07:47:37 GMT
On 17 Jun 2000 17:41:09 -0700, in
<8ih5r5$l6j$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>> In practice,
>> selecting a short cycle would indeed be very, very unlikely. But
>> "unlikely" is *not* the same as "impossible."
>>
>> Instead, the discussion here is about the concept of "proof" itself:
>> I claim that if it is *POSSIBLE* to select a short cycle, it should be
>> self-evident that any *proof* of security must be false.
>
>Well, personally, I think you're wrong here.
>You can never prevent the adversary from winning if he can make a lucky guess.
>All you can do is make it exceedingly unlikely that the adversary wins.
You attempt to make the issue the same as the usual key selection, but
that is a false analogy. For most of our ciphers, key selection is
arbitrary. But here, key selection is *not* arbitrary, because weak
keys exist. So the enciphering end has the chance to screw things up
by selecting a weak key, or to avoid that by checking first.
This is not the same ordinary chance that opponents may happen on the
correct key, but is instead an *additional* chance that -- even if the
opponents do *not* find the correct key -- the result will be weak
*anyway*. This is weakness *beyond* key selection.
It is false to say that "All you can do is make it exceedingly
unlikely," because all we have to do is follow the BB&S recipe and
then we will not use weak keys. Likelihood does not enter into it.
Clearly, we *can* do something about this weakness, and, clearly, BB&S
themselves thought this weakness sufficiently important to form a
complex construction so this weakness could be avoided.
>For instance, clearly it is *POSSIBLE* for the adversary to guess a
>factor of N just by dumb luck, and then you've broken BBS, but such a
>lucky guess is extremely unlikely to happen. You might as well worry
>about getting struck by lightning over and over again.
Yes, but the issue is not *about* practical security. The issue is
whether the X^2 mod N generator -- without the BB&S recipe that
eliminates weak keys -- is "proven secure." But when a weak key is
chosen, X^2 mod N is weak without dispute. Any proof of security
which allows the choice of weak keys is thus simply false.
The implications of this are severe: They may mean that it is
impossible in practice for even advanced crypto people to properly
interpret the results of strength proofs. The results may mean that
such proofs simply cannot take into account the various additional
requirements that a real system may need. And, in this case, they may
mean that there are other additional requirements not yet known which
also negate the supposed "proof." Now we need a "proof" which clearly
shows that we must eliminate weak keys, and also a sub-proof that no
other limitations are needed.
>Fortunately, the definitions of what it means to be secure don't require
>us to do the impossible. Thus, a proof of security roughly means that
>we can bound the success probability as the adversary by a extremely small
>quantity, so small that it can be essentially ignored in practice.
>
>Absolute perfection here is neither required not attainable.
Absolute perfection in the avoidance of weak keys *is* attainable
simply by reading beyond the first part of the BB&S article, and there
may be easier ways to accomplish the same goal. But actively avoiding
weak keys is required to correctly state that X^2 mod N is "proven
secure" with no need for short-cycle checks.
---
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: Mixing Xor and Addition
Date: Sun, 18 Jun 2000 07:50:45 GMT
On 17 Jun 2000 22:21:24 GMT, in <8igtl4$crc$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] (John M. Gamble) wrote:
>[...]
>Slightly on-topic, but a while ago John Savard pointed out that
>since xor was, as you point out, bitwise modulo 2 addition then
>you could also write an xor-like function to do paired-bitwise
>modulo 4 addition.
>
>And if you are of a fanatical nature, you could even go beyond that.
The general form of such functions is the Latin square.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.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
******************************
