Cryptography-Digest Digest #66, Volume #12 Mon, 19 Jun 00 21:13:01 EDT
Contents:
Re: MD5 Expansion (tomstd)
Re: Encryption on missing hard-drives (Albert P. Belle Isle)
Re: Extended Euclidean Algorithm ([EMAIL PROTECTED])
Re: obfuscating the RSA private key (Dave Ahn)
Re: Observer 4/6/2000: "Your privacy ends here" (Dave Howe)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: quantum cryptography at nytimes.com (zzapzing)
----------------------------------------------------------------------------
Subject: Re: MD5 Expansion
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 19 Jun 2000 15:59:08 -0700
Arthur Dardia <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>
>> 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.
>
>I'm a newbie, so here it goes:
>
>Instead of doing what the original poster came up with. Why
can't you
>just hash the original message with MD5. Use the output as the
input to
>another hash algorithm (say SHA-1), and then to be safe repeat
the same
>thing replacing TIGER/192 for SHA-1.
>
>A=MD5(M);
>B=SHA-1(MD5(M));
>C=TIGER/192(SHA-1(MD5(M)));
>
>C would be the final output.
>
>How does this increase security, by what percentage, if it does
at all?
Let's see the collection of A,B,C forms the new hash output and
it's 480 bits in length. By the b-day paradox we should find a
collsion after about 2^240 attempts... that's pretty good.
However, I can find a collision in A with 2^64 work, and a
collision in SHA with 2^80 work, that's about 2^80 work total
since after 2^80 trials we are bound to see quite abit of MD5
collisions.
Again after 2^96 trials to break Tiger we should see quite a bit
of SHA collisions. So with about 2^96 hash operations we
should see collisions in all three. That's hardly 2^240.
The attack would work like this.
1. Try random pair of messages
2. Check if their hashes are equal for all three
3. If yes you win.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Albert P. Belle Isle <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
Date: Mon, 19 Jun 2000 19:20:01 -0400
Reply-To: [EMAIL PROTECTED]
On Mon, 19 Jun 2000 22:19:46 GMT, [EMAIL PROTECTED] wrote:
>Paul Rubin <[EMAIL PROTECTED]> wrote:
>
>Even if it was, it would be classified with a classified algorithm,
>not DES. I suspect it wasn't, however, given the nature of the
>disks. The burning question in my mind is the FBI's statement that
>they're examining the disks to see if the information on them was
>altered or accessed. Is it possible to reliably tell if the
>information's been accessed in the case of a missing drive?
Only if whoever took them was stupid enough to boot a machine from the
copy of Windows on one of these drives, rather than plugging the drive
into the drive controller cable of an already-bootable machine to read
it as a second, slave drive (as any "computer forensics" guy would to
make a sector-by-sector copy for offline analysis with a commercial
"forensic software" package).
Albert P. BELLE ISLE
Cerberus Systems, Inc.
================================================
ENCRYPTION SOFTWARE with
Forensic Software Countermeasures
http://www.CerberusSystems.com
================================================
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Extended Euclidean Algorithm
Date: 19 Jun 2000 19:41:11 -0400
> Simon Johnson wrote:
>> It would seem very logical that the Extended Euclidean Algorithm
>> is an *extension* of the euclidean algorithm. What is this
>> nature of this extention? - No source code please, all in
>> prose. :)
The Euclidean algorithm determines the GCD(a,b) (the greatest common divisor
of a and b).
It is true that for a,b and d=GCD(a,b) there exist integers (not necessarily
positive) m and n with ma+nb=d.
If you keep track of the calculations in the Euclidean Algorithm, you can
actually determine those m and n. The extended Euclidean Algorithm finds the
greatest common divisor of a and b and keeps track of the calculations and
determines m and n.
This is important for the case of a and b relatively prime. d=1. If ma+nb=1
then ma=1 mod b and m is the multiplicative inverse of a modulo b (as used in
the RSA algorithm).
------------------------------
From: [EMAIL PROTECTED] (Dave Ahn)
Subject: Re: obfuscating the RSA private key
Date: 19 Jun 2000 23:39:04 GMT
[EMAIL PROTECTED] (Mack) writes:
>The best way to 'publish' a private key which may be recovered is to
>divide it into parts using some form of threshold scheme. Each of the
>parts is then encrypted using public keys of trusted parties. M of these
>N parties can then reconstruct the private key.
I read up on threshold schemes and other secret sharing algorithms, and
they do present interesting ways for me to split up the RSA private key
into X different parts which could be scattered across the program
executable.
However, I am having a difficult time seeing whether this is any better
than the technique I described in my original post, because the assumptions
are different.
For one, all secret sharing algorithms make a private key unrecoverable
unless the minimum shares can be brought together to unlock the key.
But I'm forced to publish all the keys to the sharing algorithm in the
program code, so it isn't any safer unless I obfuscate the share keys,
too, which seems to be just a reiteration of the problem.
Second, the RSA private key is recovered in plain-text once the share
algorithms have been applied correctly. This means that breaking this
system is as easy as a hex dump on the memory segment containing the
password after the share algorithms are done. I want to force a
complete decompile for such a recovery, which means that the private
key should not be recovered within the program at all.
I am looking for a way to obfuscate the *process* of encrypting with
the private key as opposed to obfuscating the private key itself.
Any other suggestions? Or ways to use thresholding schemes towards
this end?
Thanks in advance,
Dave
--
Dave Ahn | [EMAIL PROTECTED] | Wake Forest University Baptist Medical Center
"When you were born, you cried and the world rejoiced. Try to live your life
so that when you die, you will rejoice and the world will cry." -1/2 jj^2
------------------------------
From: Dave Howe <DHowe@hawkswing>
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.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Tue, 20 Jun 2000 01:15:52 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Sun, 18 Jun 2000 17:21:47
GMT]), [EMAIL PROTECTED] (JimD) said :
>On Fri, 16 Jun 2000 12:03:48 +0100, "Darren Rhodes" <[EMAIL PROTECTED]>
>wrote:
>
>>I tried to access the Shayler web site listed below but could not. This was
>>said to be due to an HTTP error 403 - Forbidden.
>>Has anyone had a similar experience?
>>Is this due to my ISP Globalnet?
>
>Ask Globalnet. If you don't get a satisfactory answer,
>ditch them. (And post your results here, of course).
Hmm. well, apparently the website URL was given out on Channel 4 a few
days back - so it may just have been Slashdotted to the point of the
ISP locking it out.....
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Tue, 20 Jun 2000 00:55:03 GMT
On 19 Jun 2000 22:19:07 -0000, in
<[EMAIL PROTECTED]>, in sci.crypt
Secret Squirrel <[EMAIL PROTECTED]> wrote:
>[Apologies if a duplicate of this message appears.]
>
>[The discussion below references
> http://x61.deja.com/[ST_rn=ps]/getdoc.xp?AN=572282072 ]
>
>Terry Ritter writes:
>
>> I saw that when it came out, and a short summary is:
>>
>> "it follows from the RSA assumption that finding short cycles is
>> impossible, for moduli large enough that factorization is
>> intractable."
>>
>> and
>>
>> "The advice to choose moduli with guaranteed long cycles, and to
>> choose seeds that way, is completely useless."
>>
>> Oddly for useless advice, the last 2/3 of the BB&S published article
>> concerns just this issue. The response involves forming a special
>> construction for N which is guaranteed to have long cycles of a
>> computable length, and then finding an algorithm to traverse those
>> cycles of known length, to show that a long cycle has been selected.
>> Now, did Blum, Blum and Shub simply get carried away with their own
>> math abilities? Shall we assume that they were they so unaware of
>> their first results that they simply did not understand that 2/3 of
>> their work was "useless"?
>
>This is not an argument. This is innuendo. This is speculation. Not one
>word of what you have written here contradicts the proof referenced
>above that being able to find short cycles allows you to factor.
I've got your "innuendo," and it was the implication that 2/3 of the
BB&S article was "completely useless." See above.
>There is no reason to speculate on what anyone's motives are. That's
>not math, it's soap opera. Let us stick to mathematics here. This
>is a mathematical question and we have a mathematical answer.
Oddly, the mathematical answer is straightforward and obvious: Nobody
disputes that short cycles occur in all X^2 mod N constructions.
Nobody disputes that the conventional approach to X^2 mod N generators
does not eliminate the possibility of choosing an initial x0 on a
short cycle. Nobody disputes that if one uses a short cycle, the
generator is weak. So exactly what kind of answer are you looking
for? As I said in a previous posting, the issue here is nothing less
than the meaning of "proof" itself: If you are willing to call
something "proven secure," when the math itself says there is a small,
but preventable probability of weakness, you are willing to bend more
then I am.
>> >It shows a way to factor RSA moduli if you can find short BBS cycles
>> >(or any cycles for that matter).
>>
>> The cycles in an arbitrary primes construction will have various
>> lengths, but as far as I know, there are always some cycles of length
>> 1 (which I call "degenerate"). I doubt they will be much help in
>> factoring N. But they undoubtedly *are* the weakest possible
>> "sequence" (which would be, in practice, a "constant").
>
>If x^2 = x mod n, with n an RSA modulus, then x^2 = x mod p where p is one
>of the factors. Therefore x^2 - x is a multiple of p, and equivalently
>x(x-1) is a multiple of p. But by the unique factorization theorem then
>either x or x-1 must be a multiple of p. The same thing is true with
>respect to q, the other factor.
>
>Therefore, such x values are extremely rare. There are only 4 of them
>less than n, two of which are 0 and 1. Hence the chance of hitting one
>at random is the same as the chance of factoring n by just guessing a
>factor at random and seeing if you are right.
I thought we were talking discrete math here, not calculus. Simply
because we have just a few values does not mean we have zero values.
Nor is that chance "the same" as guessing a factor of N. That chance
is *in* *addition* to guessing a factor of N. Simply using the short
cycle is a weakness; it is *not* necessary to factor N to exploit
weakness.
The short cycle weakness is a weakness which does not have to exist,
but which is normally allowed to exist. The fact that this additional
weakness possibility is not eliminated is sufficient to show that any
resulting system cannot be "proven secure." End of story.
>Furthermore, even if you did manage to hit one of the two non-trivial
>values, it is a multiple of either p or q, and so if you do gcd(x,n)
>you recover a factor of n. (But it doesn't matter because you would
>never hit one, not in the lifetime of the universe.)
>
>> It may be that some of those on the other side have not really
>> understood the weakness of a short cycle. BB&S type systems probably
>> would be used as the generator of the confusion sequence for stream
>> ciphers. The stream cipher requires its sequence to be random-like,
>> and *ALSO* to not repeat. But if the BB&S happens to be on a short
>> cycle, it *will* repeat, and *that* is a weakness. Sufficiently short
>> cycles *are* weak, and there simply is nothing to debate about it.
>
>It seems that it is you who do not understand. Short cycles produce
>factors! That should be the beginning and ending of the discussion.
>No more is needed.
That is a non-sequitur. What do *you* think the implications are of
"short cycles produce factors"? Do you imagine that because "short
cycles produce factors" (except, I suppose, for 0 and 1 which you
mentioned above but apparently forgot), they thus cannot exist? Well,
they *do* exist, so they are an obvious weakness, aren't they?
>For more than five years you have been spreading misinformation on
>this topic by insisting that you do not have provable security in a BBS
>generator unless you use special primes and do tests so that your initial
>seed does not put you on a short cycle.
The information I present is fact, and it does not depend upon me,
because it does not take a rocket scientist to reason out:
Any person with some contact to stream cipher cryptography knows that
it is important to have a generator with a sequence which is known to
be long. Any person can construct a simple BB&S type system out of
small primes and prove by demonstration that such systems *can* have
short cycles. In fact, BB&S do and must have short cycles. Any
person can put these two facts together and know that unless steps are
taken to avoid short cycles, there is some possibility of using a weak
short cycle. Asserting that the possibility is almost zero in
practice does not make it zero.
>Again and again over the years
>you have been presented with mathematical proof that you are wrong.
The mathematical demonstration presented here actually *proved* *my*
*point*; it described one way a short cycle is weak (by allowing
factoring, though there is another weakness, the effect on systems
which need sequences of substantial length). Clearly, using such a
cycle is a weakness in the system. Finding such a cycle is a
*practical* problem, since, in theory, the weakness is present unless
construction and testing avoid it. Since the weakness is present, a
proper mathematical treatment must reveal it. A mathematical showing
of weakness in the system, however, will require that one not first
*assume* that the system is secure.
>All you ever respond with is "but why then did the BBS paper analyze
>cycle lengths?"
Oh, I think I've responded with more than that. Just what is *your*
position? Do you imagine that short cycles do not exist? Are you
prepared for a surprise?
>This is the weakest form of argument by authority, because you can't
>even find a quote from the authority which justifies your position.
>Instead you have to speculate: they must have analyzed cycle lengths
>because they believed that unless you check for short cycles, the BBS
>cipher is weak! Of course, they never say that. They do not have one
>word in any of their papers which says this. It is purely an invention
>which you have conjured up, an inference which you have reached on the
>basis of your guess at their psychological motivations.
Nonsense. My argument does require someone to actually *read* past
the first third of the article, however. Normally, one who actually
reads an article can summarize what it means. And in a mathematical
construction article, one should be able to summarize the purpose for
the construction, or what the construction accomplishes. Just exactly
what would be *your* summary of the purpose for the last 2/3 of the
BB&S article? Surely you must know what it is if you agree it is
useless (you included the quote).
>Such arguments have no place in a technical forum.
It is a telling argument for which you have presented no alternative.
You do not address the content of the BB&S article, yet are somehow
satisfied there is no reason to use that content. Odd.
>If you cannot
>respond with a mathematical argument, you should go away until you can.
>You certainly should not be making unsupported technical claims purely
>on the basis of what your imagination suggests is the motivation of
>other researchers.
And you have not been able to describe *your* position at all. Do you
imagine that short cycles do or do not exist in BB&S constructions?
Do you imagine that using such a cycle would be weak or not? Do you
imagine that it is actually impossible for a short cycle to be
selected? Or perhaps you simply missed the many times I have stated
that -- as far as I know -- this is not a problem in practice. But it
is a *theoretical* problem, and as such stands directly in the way of
any serious claim of "proven security."
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Subject: Re: quantum cryptography at nytimes.com
From: zzapzing <[EMAIL PROTECTED]>
Date: Mon, 19 Jun 2000 18:05:19 -0700
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>zzapzing wrote:
>> <sarcasm>
>> Oh, yeah, and it would be Sooo much less expensive
>> to build a quantum cryptography line than it would
>> be to generate and store enough OTP bits for the
>> next 3 million years !
>
>The trouble with sarcasm is that it makes your point unclear.
>If you mean to imply that an OTP is more practical,
>we have established before that there are severe problems
>in the practical use of OTPs.
My point was that it seems to me that generating and
distributing OTP bits securely seemed much easier
than a quantum cryptography application.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
** 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
******************************
