Cryptography-Digest Digest #37, Volume #14 Thu, 29 Mar 01 12:13:01 EST
Contents:
Re: Breaking a DES encrypted code. (Mok-Kong Shen)
Re: Breaking a DES encrypted code. (Mok-Kong Shen)
Re: Clarification about the Czech attack to PGP (Mok-Kong Shen)
Re: Idea - (LONG) ("John A. Malley")
Re: WinZip and other Zip Archivers ([EMAIL PROTECTED])
Re: texts on factoring? ("Sam Simpson")
Re: Breaking a DES encrypted code. ("Scott Fluhrer")
Re: Question on the Quadratic Sieve (Stefan Katzenbeisser)
Re: texts on factoring? ("Tom St Denis")
Re: Strong primes ("Tom St Denis")
Re: Question on the Quadratic Sieve ("Tom St Denis")
Re: texts on factoring? ("Sam Simpson")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Breaking a DES encrypted code.
Date: Thu, 29 Mar 2001 18:16:49 +0200
William Hugh Murray wrote:
>
> Well, it is certainly being used for SETI. Has been used for brute force
> attacks against DES challenges. In order to paricipate, one need only click
> on an icon or two. It is almost that simple.
Yes. There are also universities where the computers of
the campus are connected to do distributed computing.
My impression is, though, that most commercial firms
(probably with the exception of very large ones, I don't
know) seem to opt to neglect that potential, which is
wasting of resources in my view. I am not sure whether
this is because of availability/popularity of good
software needed for distributed computing or of other
factors.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Breaking a DES encrypted code.
Date: Thu, 29 Mar 2001 18:21:29 +0200
William Hugh Murray wrote:
>
> Mok-Kong Shen wrote:
>
> > William Hugh Murray wrote:
> > >
> > > John Savard wrote:
> > >
> >
> > > > Either you know the original plaintext - a "known-plaintext" attack -
> > > > or you have partial knowledge of it. For example, the plaintext might
> > > > be uncompressed ASCII characters. In that case, have, say, seven
> > > > blocks of ciphertext, and for each key, decrypt as many of them in
> > > > turn as needed until you find the MSB of any byte equal to 1; if all
> > > > are zero, you may have found the right key.
> > >
> > > Which is why it is bad practice to encrypt a message with a strong and obvious
> > > patter like ascii characters. One should always hide any exploitable pattern in
> > > the plaintext before encrypting it.
> >
> > On the other hand, to eliminate the patterns before
> > encryption does involve cost. It seems to be the opinion
> > of many that, if one has a sufficiently strong cipher,
> > one needn't care that.
>
> Enigma was, and is still, a strong cipher. What was exploited in Ultra was poor use
> of the cipher. One specific use that was of aid in ultra was the encryption of
> standard headers. It is not at all clear that strengthening Enigma would have raised
> the cost of attack nearly so much as improving the way that it was used.
>
> Of course, cost was the issue for the Germans. However, today we use very cheap
> computer cycles to perform these tasks. Most implementations, for example, PGP and
> S-MIME perform these operations. Most encryption of interest is done at the desktop
> or the laptop using very low-cost cycles. It uses cycles that simply would have been
> thrown away if not used for code conversion. Code conversion is what computing is
>all
> about. If one is going to the trouble of converting from public codes to secret
> codes, one might as well do it right in the first place. We spend more money making
> the decision to encrypt than encryption costs us.
It is difficult to argue on the optimal constellation
of an encryption system, I suppose, because 'it depends'.
But sometime back someone wanted e.g. implementation
on a very minimum of hardware. In such cases, it could be
that one is confined with the use of one sufficiently
good algorithm without being able to afford the luxury of
additional crypto-beneficial processing, I guess.
(Otherwise, I personally would favour always to be
conservative in encryption.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Clarification about the Czech attack to PGP
Date: Thu, 29 Mar 2001 18:28:39 +0200
John Savard wrote:
>
> Ideally, if one is really serious about security, one ought to run PGP
> on a separate machine, and then use a floppy disk to carry the
> encrypted files to your machine that is connected to the Internet, on
> which you don't put any sensitive stuff that needs to be encrypted.
This is remniscent of the old days where processing
of sensitive data on a main frame was done without
concurrently running jobs. I think it was called
'times processing' or something like that.
M. K. Shen
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Idea - (LONG)
Date: Thu, 29 Mar 2001 08:30:17 -0800
"SCOTT19U.ZIP_GUY" wrote:
[snip]
> I still think its interesting
> that in the 40's Shannon felt long keys were needed. Yet today in the
> computer age. Most cyrpto systems limit there selves to very short keys.
> At least in the public domain. I doubt the NSA for there own internal
> secret encryption would so blatently violate Shannon's insights about
> crypto.
IMO we all should read Shannon's paper. His general information theory
analysis of ciphers from over 50 years ago still proves helpful today.
We tend to forget that perfect secrecy without an OTP is possible for a
finite number of messages as illustrated by the example provided in the
post. There is an ideal system protecting four messages with perfect
secrecy (per Shannon's definition) without using an OTP.
Shannon showed us that perfect secrecy with short keys requires a cipher
with very particular characteristics.
AFAIK there is no published demonstration of any block cipher algorithm
having the characteristics of an ideal system per Shannon's definition.
Anyone aware of such work? Pointers to papers welcome :-)
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: WinZip and other Zip Archivers
Date: Thu, 29 Mar 2001 16:27:05 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Mok-Kong Shen wrote:
> > Zip encryption is week (although it's better than just xoring)
> > there is known plaintext attack that requires only known 13 bytes
> > and then it can be broken in few hours
> >
> > but there are some other archivers that use better crypto
>
> Could you name one/some?
ARJ, uses GOST
WINACE, uses modified Blowfish
RAR, uses it's own algorithm, not sure how strong it is..
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp <----PGP plugins for Netscape and MDaemon
^--GPG for Win32 (supports loadable modules and IDEA)
^---PGP 2.6.3ia-multi03 (supports IDEA, CAST5, BLOWFISH, TWOFISH,
AES, 3DES ciphers and MD5, SHA1, RIPEMD160 hashes)
=====BEGIN PGP SIGNATURE=====
Version: Netscape PGP half-Plugin 0.14 by Disastry / PGPsdk v1.7.1
iQA/AwUBOsNGKTBaTVEuJQxkEQKc4gCgyPcowmaJanfCIOn9cVPg3lF+AecAnicN
c7H9y7cd8f5iRUwRDwlxLN3L
=zopM
=====END PGP SIGNATURE=====
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: texts on factoring?
Date: Thu, 29 Mar 2001 17:31:19 +0100
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > I have the complete Knuth set and he only discusses Pollard-Rho, Fermat
and
> > a sieve method. Nothing terribly advanced...
> >
> > I will look up the Koblitz book.
>
> Koblitz has a very readable treatment of ECM and the quadratic sieve,
> but says nothing about the number field sieve, at least in the edition
> I have (there's a newer one now). I think NFS might not have been
> invented when the 1st edition came out.
True. I've got the 2nd ed and NFS is covered on about 2 to 3 sides of text.
It just gives a basic introduction to how it works and the implication -
there are no annotated examples or anything :(
I think Koblitz is a good book, but is quite expensive.
--
Regards,
Sam
http://www.scramdisk.clara.net/
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Breaking a DES encrypted code.
Date: Thu, 29 Mar 2001 08:25:53 -0800
William Hugh Murray <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Douglas A. Gwyn" wrote:
>
> > William Hugh Murray wrote:
> > > Which is why it is bad practice to reuse keys ...
> >
> > yada, yada -- it's not like the Germans had much choice.
>
> Agreed. However, because we use automatic, rather than manual, key
> management, we do have a choice.
>
> > DES key *is* generally reused -- for subsequent blocks
> > in the same session. Therefore even though it might
> > appear that nothing was gained by cracking the first
> > block using known plaintext, it is *only* for the first
> > block that the plaintext needed to be known, and all the
> > unknown plaintext later in the same session is the payoff
> > for the attack.
>
> Agreed. This is the reason why one uses an initialization vector when
> using DES at the session layer.
>
> The assumption has always been that getting known plaintext is a trivial
> exercise. One need only dupe the adversary into sending a message that
> one already knows under the key in question. However, in session layer
> encryption this is usually difficult to do. In fact, it is so difficult
> that if one enjoys the necessary privileges do it, one probably is
> privileged to read the cleartext in the first place.
Not usually. If what is being encrypted is a computer generated plaintext,
it is often quite guessable. To take an extreme example, if you download
the 'pay' web page from Amazon, well, that is encrypted (SSL), but the
attacker knows exactly what HTML is being downloaded, and so he has several
kilobytes of known plaintext. In less extreme cases, there are often known
or guessable headers that an attacker can use.
--
poncho
------------------------------
Date: Thu, 29 Mar 2001 18:37:18 +0200
From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Subject: Re: Question on the Quadratic Sieve
Tom St Denis wrote:
>
> Please forgive my misunderstandings if any...
>
> If I get the QS right you are trying to find a pair X, Y in Zn (n = # to
> factor) such that X != +/- Y, and X^2 = Y^2 mod n. This is because if this
> is true then (x - y)(x + y) = kn and then (x-y) might be a divisor of n.
Actually x-y and n must share some prime factors; just compute gcd(x-y,n)
and you'll get them for free (well, almost ;-)
> Then the idea progresses by trying to find numbers Xi and their roots Yi
> such that Xi^2 = Yi (mod p).
OK; here is a "quick and dirty" introduction to the QS:
Common to all factor-base methods is the following observation: although
it is very difficult to compute a (nontrivial) congruence X^2=Y^2 (mod n),
one can try to generate a huge number of "simpler" congruences X_i^2=Y_i (mod n)
and combine some of them to a congruence X^2=Y^2 (mod n) that allows you to
factor n. So basically you need:
- a mechanism that generates congruences X_i^2=Y_i (mod n) and
- an algorithm to generate the congruence X^2=Y^2 (mod n) out of the mass
of "simpler" congruences.
To solve the second problem, one chooses a "factor base", which is simply
a set of primes. One tries to factor all of the Y_i's over the factor base
(that is, you try to write Y_i as a product of p_j^e_(i,j) with all primes p_j
of the factor base and appropriate exponents e_(i,j); of course, this is
quite expensive even if the Y_i's are moderately large and not always possible).
The main idea is now to pick a subset of "simpler" congruences and multiply them
together,
so that the right side of the resulting congruence is a perfect square. Unfortunately
at this point you don't know which congruences to use. Now you do so as if you would
multiply _all_ simpler congruences, but raise the i-th congruence to the (yet
unknown) power f_i; f_i will be computed later but can either be zero or one.
If the f_i turns out to be one, the i-th congruence will be in the subset we
choose, otherwise not. Take a closer look now at the product of all Y_i^f_i,
which we will call z.
Then, you can compute the prime decompisition of z; it is simply the product of
all p_j, taken to the power \sum_{i=1}^k f_ie_(i,j). Now you want z to be a perfect
power; this can only be the case if all exponents in the factorization of z are
multiples of two:
\sum_{i=1}^k f_ie_(i,j) = 0 (mod 2) for all j.
This is simply a system of linear equations, viewed over Z_2 (the field with
two elements). So you compute the e_(i,j) by factoring all Y_i, store them as
a matrix and use Gauss elimination to compute the f_i (but you must do Gauss
elimination over Z_2!!). Once this is done, you multiply all congruences with
an index i where f_i=1 together. By construction, you get a congruence
X^2=Y^2 (mod n). If this congruence is not trivial, you have the factorization
of n.
Now the QS gives you a method to compute a number of congruences X_i^2=Y_i mod n,
along with the factorization of the Y_i's. Choose the polynomial
z(x)=(x+\floor(\sqrt(n)))^2 - n
Substituting some values for x and taking the equation modulo n yields to
the congruence z(x)=(x+\floor(\sqrt(n)))^2) (mod n), which has the required form
(right side=perfect power).
The main thing now is that there is a quite efficient way to factor the left
side of the congruence, if this is possible. Recall that we have to check for each
prime
whether p_i divides z(x) to compute the prime decomposition of z(x).
Now, this problem is equivalent to checking whether the polynomial congruence
z(x)=0 (mod p_i) has a solution; this problem can be solved quite efficiently
(if you look into the literature: Shank's algorithm will do just that). The main
observation is that all solutions (if there are any) to this congruence have the
form
y + k p_i and
z + k p_i
where both y and z are fixed and k runs through all integers. Thus, solutions of
this congruence are somewhat evenly spaced with distance p_i.
So, you choose a sieving interval [0,M] for a large integer M and evaluate z(x)
for all values x in this interval. Then, you start solving all congruences
z(x)=0 (mod p_i); if any z(x) can be written as either y + k p_i or
z + k p_i for any integer k, divide z(x) by p_i. You do this for all primes
in the factor base and all values z(x).
Compare this with the sieve of Erathosthenes. It's quite similar...
When the algorithm ends, you perhaps have some values of z(x) that are equal
to 1. If this is the case, you know that the original value of z(x) can be factored
completely over the factor base. Every such entry gives you a congruence of
type X_i^2=Y_i (mod n) that we wanted to find. Now that you know which
z(x) can be factored, you just perform trial divisions to actually recover a
factorization.
All values that have z(x)>1 are useless for us, as they cannot be factored
over the factor base. [This is not really true, but it will do it for the
moment ;-)].
Hope this helps!
--Stefan.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: texts on factoring?
Date: Thu, 29 Mar 2001 16:52:14 GMT
"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
news:UoJw6.879$[EMAIL PROTECTED]...
> Paul Rubin <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > I have the complete Knuth set and he only discusses Pollard-Rho,
Fermat
> and
> > > a sieve method. Nothing terribly advanced...
> > >
> > > I will look up the Koblitz book.
> >
> > Koblitz has a very readable treatment of ECM and the quadratic sieve,
> > but says nothing about the number field sieve, at least in the edition
> > I have (there's a newer one now). I think NFS might not have been
> > invented when the 1st edition came out.
>
> True. I've got the 2nd ed and NFS is covered on about 2 to 3 sides of
text.
> It just gives a basic introduction to how it works and the implication -
> there are no annotated examples or anything :(
>
> I think Koblitz is a good book, but is quite expensive.
It's only 45$ at Amazon
http://www.amazon.com/exec/obidos/ASIN/0387942939/qid=985830984/sr=1-1/ref=s
c_b_2/102-5941110-7696927
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Strong primes
Date: Thu, 29 Mar 2001 16:53:19 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:99vfl3$heo$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:39vw6.156761$[EMAIL PROTECTED]...
> >
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > news:P_tw6.156323$[EMAIL PROTECTED]...
> > > And more exact it's the kind of primes where q is prime and so is p =
2q
> +
> > > 1. That way q is a large sub-group of Z*p.
> >
> > Err.. that's Z*q is a large sub-group of Z*p.
>
>
> No. If p = 2q+1, then there is a subgroup of Z*(p) of order q, but it is
> usually not Z*(q). For instance, it is possible to select p so that 2 is a
> generator of Z*(p), and 2 is a member of Z*(q).
>
> Example: The subgroup of Z*(5) of order 2 consists of {1,4}.
You're entirely correct... that will teach me to type late at night. Sorry
for the mistake guys!
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Question on the Quadratic Sieve
Date: Thu, 29 Mar 2001 16:57:48 GMT
"Stefan Katzenbeisser" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > Please forgive my misunderstandings if any...
> >
> > If I get the QS right you are trying to find a pair X, Y in Zn (n = # to
> > factor) such that X != +/- Y, and X^2 = Y^2 mod n. This is because if
this
> > is true then (x - y)(x + y) = kn and then (x-y) might be a divisor of n.
>
> Actually x-y and n must share some prime factors; just compute gcd(x-y,n)
> and you'll get them for free (well, almost ;-)
>
> > Then the idea progresses by trying to find numbers Xi and their roots Yi
> > such that Xi^2 = Yi (mod p).
>
> OK; here is a "quick and dirty" introduction to the QS:
<snip>
Thanks for the info. I saved this post to my desktop ...
It's really nice to get all this info, this group is fun again :-)
Thanks,
Tom
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: texts on factoring?
Date: Thu, 29 Mar 2001 18:03:01 +0100
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:2LJw6.159996$[EMAIL PROTECTED]...
<SNIP>
> > I think Koblitz is a good book, but is quite expensive.
>
> It's only 45$ at Amazon
>
http://www.amazon.com/exec/obidos/ASIN/0387942939/qid=985830984/sr=1-1/ref=s
> c_b_2/102-5941110-7696927
It's only 230 odd pages though!
I wouldn't say it was bad value for money _if you need some of the content_,
which you obviously do.
--
Regards,
Sam
http://www.scramdisk.clara.net/
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
