Cryptography-Digest Digest #69, Volume #12 Tue, 20 Jun 00 08:13:01 EDT
Contents:
Re: small subgroups in Blum Blum Shub (Mark Wooding)
Re: Is this a HOAX or RSA is REALLY broken?!? (Mark Wooding)
Re: MD5 Expansion (Mark Wooding)
Re: MD5 Expansion ("ben handley")
Re: Extended Euclidean Algorithm (Mark Wooding)
Re: Encryption on missing hard-drives ("Trevor L. Jackson, III")
"What 'flagrant' bugging abuse?",asks Home Secretary Straw [Was Re: RIP Bill 3rd
Reading in Parliament TODAY 8th May] (U Sewell-Detritus)
Re: small subgroups in Blum Blum Shub ("Trevor L. Jackson, III")
Re: New Hash Function (tomstd)
Re: New Hash Function (tomstd)
Re: Is this a HOAX or RSA is REALLY broken?!? (tomstd)
Re: S/MIME + Netscape v47 serious problem in symmetric encryption ... (Jaime Cardoso)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: small subgroups in Blum Blum Shub
Date: 20 Jun 2000 10:04:09 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> It would be fine if someone could show the theoretical underpinning
> of this.
OK. Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
Choose an integer x, 0 < x < n. Then y = x^2 (mod n) is a quadratic
residue, mod n.
I claim (a) that y has four square roots, mod n, and (b) that exactly
one of these square roots is a quadratic residue.
Firstly, it's (fairly) clear that x is a square root of y, mod p.
Writing the assertion that y = x^2 (mod n) as y = x^2 + k p q makes this
obvious. By symmetry, we also have y = x^2 (mod q).
Let x_p = x (mod p), x_q = x (mod q), with 0 < x_p < p, 0 < x_q < q.
Clearly, -x_p is the other square root of y (mod p), and -x_q is the
other square root of y (mod q). By the Chinese Remainder Theorem, we
can show, using the result above, that y has precisely four square roots
mod n. To see this, let z be a square root of y (mod n). We know that
z_p is a square root of y (mod p), so z_p must be congruent to either
x_p or -x_p. By symmetry, a similar argument applies to z_q. Hence, y
has four square roots, as claimed in (a).
Now to prove that exactly one of the square roots is a quadratic
residue. Let g be a primitive element in GF(p), and choose \alpha such
that x_p = g^\alpha (mod p); then y = g^{2\alpha} (mod p). Now,
-x_p = g^{\alpha + (p - 1)/2} (mod p)
To see this, note that g^{(p - 1)/2} = -1 (mod p). Since p = 3 (mod 4),
(p - 1)/2 is odd. Hence, precisely one of x_p and -x_p has an odd index
and is therefore a quadratic residue. Similarly, one of x_q and -x_q is
a quadratic residue. Again using the Chinese Remainder Theorem, we see
that one of the square roots of y (mod n) is a quadratic residue mod
each of p and q. To prove (b), I must now show that this square root
(let's call it z) is a quadratic residue mod n.
Since z is a quadratic residue mod p it has a square root[1] mod p --
call this r_p. It also has a square root mod q -- call it r_q. By the
Chinese Remainder Theorem, we can find a unique integer r, 0 < r < n,
where r = r_p (mod p) and r = r_q (mod q). A final application of the
Chinese Remainder Theorem shows that r^2 = z (mod n). This proves claim
(b).
I earlier stated that, in the multiplicative group of quadratic residues
Q_n of the integers mod n, the map x |-> x^2 is bijective. This is a
simple corollary of the above claims -- x^2 has exactly one square root
mod n which is in Q_n. This map is therefore a permutation on Q_n.
Finally, let S be any finite set, and let f : S -> S be any permutation
on S. Define the relation C_f on S by
C_f(x, y) <==> there exists an integer i such that f^i(x) = y;
I claim that C_f(x, y) is an equivalence relation. To do this, I must
show:
(a) relexivity: that C_f(x, x) for all x;
(b) commutivity: that C_f(x, y) <==> C_f(y, x); and
(c) transitivity: that C_f(x, y) and C_f(y, z) imply C_f(x, z)
(c) is obvious from the definition of C_f.
Choose any element x of S. Consider the sequence x, f(x), f^2(x), ...
Since S is finite, this sequence must cycle. So, we must have i != j
where f^i(x) = f^j(x). If i > 0, I can apply f^{-i} to both sides to
show that x = f^{j-i}(x). Let c = j - i be the cycle length. Claim (a)
is now proven trivially; (b) is proven by noting that if x = f^i(y) then
y = f^{c-i}(x) (apply f^{c-i} to both sides: f^{c-i}(x) = f^{i+c-i}(y) =
f^c(y) = y).
Finally, I suspect Terry found an arc length of one because he started
with a non-residue.
[1] Of course, it actually has two, but I don't care about the other
one.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: 20 Jun 2000 10:18:13 GMT
S. T. L. <[EMAIL PROTECTED]> wrote:
> <<The optimists in the field believe that in 5 or 10 years
> it will be possible to build a quantum computer that can
> factor the number 4 as 2x2.>>
>
> I believe that 15's already been factored. Now for something big,
> like 77....
<fx: hand in the air> Ooh! Ooh! I can do that one!
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: MD5 Expansion
Date: 20 Jun 2000 10:21:51 GMT
Arthur Dardia <[EMAIL PROTECTED]> wrote:
> 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?
Not at all. Utterly hopeless.
Find M, M' such that MD5(M) = MD5(M'). This is at most 2^{64} effort;
maybe less if MD5 gets any more broken than it is already. From there,
you get identical C outputs.
-- [mdw]
------------------------------
From: "ben handley" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Tue, 20 Jun 2000 22:23:59 +1200
>>I little bit of miscommunication here. I meant a linear
> transform of
>>the message, not the hash, so it looks something like this:
>>
>>A = H(m) B = H(L(m))
>>
>>Final hash = AB
>>
>>Are you saying this is not secure as well? I'm interested, if
> it isn't
>>secure, how one might break it. Just from the outside (amateur)
> view,
>>it seems as though L(m) could be something as simple as
> flipping the
>>first bit of the message and this would still be effective
> because the
>>avalanche effect of the hash would amplify that difference
> tremendously.
>
> Well we can find collisions in A such that
>
> A = H(m) = H(m') for m != m'
>
> Then we just need to find collision in B such that
>
> B = H(L(A) || m) == H(L(A) || M')
>
> The first has a probability of 2^-64 of happening before the bday
> threshold, the second has an equal prob... together it is
> 2^-65... that's if I get this right, ... err.. I am tired...
Umm, you still haven't read what he said right. B=H(L(m)), notH(L(A)||m).
And in any case, two events with probability
2^-64 combine to give a probability of 2^-128, not 2^-65.
However, in Applied Cryptography, Bruce Schneier describes a method for
doing this (pages 430-431), which is more complicated (involving
concatenating the message with its hash), which he says various people
have
'serious reservations about'. If that system is thought untrustworty, this
system
is likely to be too.
ben
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Extended Euclidean Algorithm
Date: 20 Jun 2000 10:28:32 GMT
Simon Johnson <[EMAIL PROTECTED]> 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. :)
Any good introductory number theory text should cover this in the first
chapter. I quite like Davenport's `The Higher Arithmetic: An
Introduction to the Theory of Numbers', published by CUP.
> Also: i'm told it can solve the following problem:
>
> 6y + 7x + 14z mod n - where n is known........
>
> How do i go about this?
Err... what's the problem? You've missed something out here.
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
This advertising is getting extremely tiresome.
-- [mdw]
------------------------------
Date: Tue, 20 Jun 2000 07:11:22 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
Guy Macon wrote:
> Albert P. Belle Isle wrote:
> >
> >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).
>
> Hi! Guy Macon the former hard disk drive engineer here...
>
> There is a way, even if the slave drive method was used. I will put
> in a bit of scrolling now so you can try to think of it before reading
> my answer. It's clever, but a non technical person could think of it.
>
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
>
> Examine the pins of the hard drives with a microscope. You can probably
> tell if the last computer it was plugged into wasn't the one it came out
> of before it went into the vault. You may be able to tell which computer,
> if any, was was used to read it.
There may be a simpler method. Due to the volume of cooling air required,
most laptops and all PCs quickly become coated with a layer of dust. Merely
opening the case will disturb the dust sufficiently to be detectable.
Actually doing something to the innards will leave traces such that an astute
observer will be able to determine what was done.
Note that it would be extremely difficult for a thief to recreate the dust
conditions because dust is fiber, and fiber identification is a fairly mature
science. Attempting to fake the original dust might provide an evidentiary
link to the thief.
------------------------------
From: [EMAIL PROTECTED] (U Sewell-Detritus)
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,uk.telecom
Subject: "What 'flagrant' bugging abuse?",asks Home Secretary Straw [Was Re: RIP Bill
3rd Reading in Parliament TODAY 8th May]
Date: 20 Jun 2000 11:01:38 GMT
James Hammerton <[EMAIL PROTECTED]> wrote:
>You have to prove you're not lying when you say that, which is well impossible.
In Letters to the Editor, Jack Straw, the British Home Secretary
poses the following question to the readers of The Daily Telegraph
(Monday 19 June 2000):
========
Unjustified worries about e-mails
SIR - You peddle many erroneous assumptions about the
Regulation of Investigatory Powers Bill, including the
extraordinary assertion that there has been "flagrant"
abuse of telephone interception.
Where is the evidence for this?
[snip]
Jack Straw
Home Secretary
London SW1
========
It comes as some surprise that the Home Secretary need ask such a question.
Have his mandarins not visited the web site of Mr Duncan Campbell,
the investigative journalist?
Mr Campbell's expertise in the field of communications intelligence has
enjoyed him the audience of European Commissioners along with the
audience of numerous television broadcasts.
On the links below to Mr Cambell's web site, details of this
"flagrant abuse of telephone interception" can be found, fully documented.
http://anon.free.anonymizer.com/www.gn.apc.org/duncan/stoa.htm
http://anon.free.anonymizer.com/www.gn.apc.org/duncan/menwith.htm
http://anon.free.anonymizer.com/www.gn.apc.org/duncan/875112275-phone.html
------------------------------
Date: Tue, 20 Jun 2000 07:26:00 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Mok-Kong Shen wrote:
> Terry Ritter wrote:
>
> > Secret Squirrel <[EMAIL PROTECTED]> wrote:
> > >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."
>
> I am not sure but I have the impression that the presently very heated
> dispute is somewhat analogous to a dispute over OTP. Person A
> gets some hardware generated extremely high quality random bit
> sequences and claims that his encryption is provably secure because
> OTP is proved to be secure, while person B maintains that, because
> the sequences obtained in practice must necessarily have some minute
> deviations from what is assumed in the proof of OTP's security, A's
> system is not provably secure.
Not quite. One position is similar to that of an OTP user. The other
position is that of pseudo-OTP user, whose pad is generated by an inferior
process (PRNG). The OTP user is subject to a Karnak attack. The other is
subject to both a Karnak attack and cryptanalysis of the PRNG.
The distinction can be seen more clearly when one considers that betting on
long odds say 1:2^256 and betting on an impossibility are the same in practice
-- fruitless. But they are not the same in theory. In this particular case
one can easily accept the remote possibility of a short BBS cycle because for
all practical purposes the risk is negligible. However, the term "provably
secure" applies in theory, not in practice. It rules out the possibility, no
matter how remote, of any weakness. Thus it is an error to assert that
unfiltered BBS systems are "provably secure", just as it is (*) an error to
assert that filtering is required for practical security.
===================
(*) I'm not qualified to make the judgment. The reasoning presented by daw
and mdw appears to be convincing.
------------------------------
Subject: Re: New Hash Function
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 20 Jun 2000 04:20:52 -0700
>If your algorithm would have an obvious weakness it
>would have surprised me. ;-)
me too.
>The Feistel structure worked well against my attempts
>to attack it. That damned thing remembers me of RC5,
>but that didn't helped me much, the rotations are not
>dynamic and there is no key to discover in a one way
>hash function anyway.
Well you still want to force parts of it to collide via diff or
linear cryptanalysis I suppose.
>These fixed rotations in F() destroy all informations
>about the lower bits. There was already another
>rotation in the initialisation of W[] which is also
>evil for the attacker, just like the constant term
>in the XOR. So, AFAICS, there is also no weakness.
The rotations (in 3hash_rev.c) are designed so that single bit
errors will propagate and infect the entire block after about 2
or so cycles.
>
>I still think there might be a problem with parity.
>You use XOR everywhere but when you store the results
>of your Feistel loop. Damned, but I can't see a way
>to use that property.
The sbox at the end of the F function should help break the
parity up a bit. But probably not enough.
>In short: I can't see any way to attack it. :) Why
>can't you store the loop results with '=' instead of
>'+=' or remove those ugly rotations ? ;-) However,
>I would use addition instead of XOR in the
>initialization of W[] so that parity doesn't slip
>through.
I can't just store it because it's a feistel and it would be
degenerative if I did that. I can't use addition in the W[]
expansion since I would have to use a primitive trinomial and I
don't want todo that.
I think I could change the "mixing" part at the end of the
feistel function to addition instead of xor and make it a tad
less xor'ish...
Thanks for looking at it.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: New Hash Function
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 20 Jun 2000 04:25:45 -0700
One observation that I don't like is that in an attack the
attacker gets five rounds for free since W[0..14] are not
changed in anyway by the expansion.
I think that's a good place to look for weaknesses... anyways I
am off to write my last exam... yipeee.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 20 Jun 2000 04:33:04 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>S. T. L. <[EMAIL PROTECTED]> wrote:
>> <<The optimists in the field believe that in 5 or 10 years
>> it will be possible to build a quantum computer that can
>> factor the number 4 as 2x2.>>
>>
>> I believe that 15's already been factored. Now for something
big,
>> like 77....
>
><fx: hand in the air> Ooh! Ooh! I can do that one!
Simple 77 = 23 * 9. I am glad I am doing goodly in math.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Jaime Cardoso <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp.discuss
Subject: Re: S/MIME + Netscape v47 serious problem in symmetric encryption ...
Date: Tue, 20 Jun 2000 01:55:33 +0000
It's 2 am in here, has I am typing this message so, i belive that I may not be
gettin things right but, the way I see it his this:
If I want to send you an encripted e-mail, i will take your digital certificate
and encript the message the way I can, of course I know nothing about your browser
configuration, I will just encript it acording to MY browser configuration.
When you receive the message, the browser takes your certificate and, after
unlocking your private key, will decript the message. Because the browser has in
it's database, the code for decripting all the algoritms you mentioned, then he
CAN decript the message and, it's up to you to see with algoritm the mesage was
encripted and to know if your trust what's in there or not.
When you want to send an encripted e-mail, then your browser encripts the message
with the safest algoritm specified by you (in your case, RC5 128 bits, I believe
that was waht you said).
Once again, if I got your problem right, this his not a bug, it's a feature :)))))
(No, I don't work for Microsoft to be saying that)
Bye
PS. I syncronize my browser with this Newsgroup and then I red the messages when I
have time, at this point I am on vacations so, if you want to answer me, please
also reply to my e-mail. Sorry
//JaimeC
Boris Kazak wrote:
> jungle wrote:
> > > >***************
> > > > Anyway, it would be interesting to find out why it keeps reporting
> >
> > how to find that it is reporting ONLY and not practically using only 40 bits
> > encryption ?
> ===========================
> This is even more cause for concern. If the system is reporting
> not the facts, but high fantasy, we are ALL in very bad shape...
>
> Best wishes BNK
------------------------------
** 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
******************************
