Cryptography-Digest Digest #174, Volume #12 Fri, 7 Jul 00 11:13:00 EDT
Contents:
Re: Crypto jokes? (potentially OT) (Daniel James)
Re: SafeIT - Untrusted encryption program. (Runu Knips)
MD of large data-sets (Efthymios Ntasis)
Re: MD of large data-sets (Larry Kilgallen)
Re: Has RSADSI Lost their mind? (Runu Knips)
A variation of the Hill cipher (Mok-Kong Shen)
Re: Crypto jokes? (potentially OT) ("Trevor L. Jackson, III")
Re: Has RSADSI Lost their mind? (Mark Wooding)
Re: Crypto jokes? (potentially OT) (Mark Wooding)
Re: Prime Numbers? (John Myre)
Re: MD of large data-sets (Mark Wooding)
Re: Beginner Questions (Mark Wooding)
Re: Prime Numbers? (Mark Wooding)
Re: Prime Numbers? (Florian Weimer)
Re: Porting Keys Between PGP, other Apps ("Ed Suominen")
----------------------------------------------------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Date: Fri, 07 Jul 2000 12:11:18 +0100
Reply-To: [EMAIL PROTECTED]
In article <sR495.15$[EMAIL PROTECTED]>, Paul Pires wrote:
> > How may cryptographer does it take to change a light bulb?
>
> One, but you can't *PROVE* that it has been changed.
No, that can't be right. Well, not quite right. Probably.
If the bulb needs changing its output will be the same whatever the position
of the switch - you can't tell whether it's on or off because the output is
encrypted, but a dead bulb is always off so the output (ciphertext) will be
the same whatever the cleartext (switch position).
Note that this is a security problem because a known plaintext (switch=off)
attack can be mounted against the ciphertext resulting from the dead bulb
condition.
Once the bulb has been changed - assuming that the new bulb is not also dead
- the system is again secure.
It only takes one cryptographer to change the bulb, but this should be a
privileged operation as it is dangerous to change abulb while the circuit is
live and only someone with knowledge of the plaintext (switch position) can
be sure that the curcuit os off.
Now, how do we go about changing keys in this system?
Cheers,
Daniel.
------------------------------
Date: Fri, 07 Jul 2000 13:17:33 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: SafeIT - Untrusted encryption program.
[EMAIL PROTECTED] wrote:
> I have come across a company that sells an encryption program which
> primary function is to encrypt email. The company is Softnet Security
> and they spread knowledge of the products by a studied mouth-to-mouth.
> [...]
> But the thing that make me want to post this all over sci.crypt
> is that the symmetric key algorithm used in their program are a 'trade
> secret'. Sure it's legal to do so, but not acceptable. The users buy
> the program and thinks it's safe, but it might not. It it's safe, prove
> it!
Far more important: they want to encrypt MAILS so what is the most
important thing is that everybody else can read them. So its crap
by principle even if the algorithm used would be secure.
------------------------------
From: Efthymios Ntasis <[EMAIL PROTECTED]>
Subject: MD of large data-sets
Date: Fri, 07 Jul 2000 14:39:30 +0300
I want to the ensure the integrity of a data-set, which its zipped size
is between 25 and 50 Mbytes.
In practice, when a digital signature scheme is used, do I have to
insert the whole data-set to a message digest
algorithm as MD5 or SHA? Isn't this gonna take a long time?
If there are any papers on this subject could you please recommend them
to me?
Thank you in advance
Efthymios Ntasis
Biomedical Simulation and Medical Imaging Group - ICCS, NTU of Athens
------------------------------
From: [EMAIL PROTECTED] (Larry Kilgallen)
Subject: Re: MD of large data-sets
Date: 7 Jul 2000 09:08:01 -0500
In article <[EMAIL PROTECTED]>, Efthymios Ntasis
<[EMAIL PROTECTED]> writes:
> I want to the ensure the integrity of a data-set, which its zipped size
> is between 25 and 50 Mbytes.
> In practice, when a digital signature scheme is used, do I have to
> insert the whole data-set to a message digest
> algorithm as MD5 or SHA? Isn't this gonna take a long time?
It should not take a "long time" compared to the time required to
make use of the data. If the data is never actually going to be used,
perhaps the idea of keeping it at all should be revisited.
------------------------------
Date: Fri, 07 Jul 2000 14:15:32 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Has RSADSI Lost their mind?
Eric Lee Green wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > Below is a couple of messages posted to the OpenSSL users mailing list.
> > Seems someone down at RSADSI has lost it.
>
> No, this is typical behavior for RSADSI. They have a habit of sending out
> threatening BS letters at the slightest provocation, such as when they
> recently threatened to sue a Canadian citizen for violating the patent on the
> RSA public key encryption algorithm.
Hmm was that when they mailed to Tom ? I thought Tom was just
overcautious. But maybe I would have been that way, too.
Nevertheless, there is still ElGamal (which is somewhat
slower, of course).
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: A variation of the Hill cipher
Date: Fri, 07 Jul 2000 14:36:30 +0200
The Hill cipher (AMM 36 (1929)) is defined by the equation
C = H * P mod u
where H is an invertible matrix in Z_u and P and C are square
matrices representing a section of the numerically coded
plaintext and ciphertext message respectively.
Consider the matrix iteration
X_(i+1) = M * X_i mod u
with a matrix M whose main diagonal elements have inverses
but the other elements can be arbitrary. Let's us employ the
Gauss-Seidel iteration method (also known as the single step
method), i.e. each column of X_(i+1) is computed from top to
bottom, using the newest values obtained to replace the
corresponding elements of X_i in the expression M * X_i. on
the right side of the equation. It is evident that one can
also similarly obtain X_i from X_(i+1) through computing
each column of X_i from bottom to the top, noting that the
diagonal elements have inverses. In other words, the
iteration process is invertible.
Now we can define a variant of the Hill cipher as follows:
Randomly choose an M (with invertible diagonal elements) and
select a positive number n. Let X_0 = P. Then C is given by
the n_th iterate X_n.
Note that M is not necessarily invertible. Thus we are more
flexible in its choice than in the case of H in the original
scheme of Hill. In particular, if u is a power of 2, which is
convenient for implementation, one can generate M with a PRNG
(preferably one M for each P as part of a message), subject
to the restriction that the diagonal elements be odd. Further,
analogous to a previous article of mine on the Hill cipher
posted to sci.crypt, we can also use two M matrices as follows
to obtain enhanced diffusion effects of the encryption:
X_(i+1) = M1 * X_i * M2 mod u
In this case the iteration is done in two passes. In the
first pass each column of X_(i+1) is computed from top to
bottom with respect to M1 as described above. In the second
pass each row of X_(i+1) is computed from left to right with
respect to M2, keeping in mind that for the Gauss-Seidel
iteration (as against the Gauss-Jordan iteration) one always
uses the newest values of the elements of X in the iteration
equation.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
Date: Fri, 07 Jul 2000 09:21:03 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Mark Wooding wrote:
> Paul Pires <[EMAIL PROTECTED]> wrote:
> > <[EMAIL PROTECTED]> wrote in message news:8k1r9e$qhl$[EMAIL PROTECTED]...
> >
> > > How may cryptographer does it take to change a light bulb?
> >
> > One, but you can't *PROVE* that it has been changed.
>
> It's easier to detect changed incandescent lightbulbs if they have
> poorly designed filaments. You can distinguish a Tesco's 60W bulb with
> about 2^{37} chosen dimmer settings...
I'm having a _great_ deal of difficulty trying to conceptualize unchosen
dimmer settings. Does that make the switches autonomous? Talk about
decidability problems...
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Has RSADSI Lost their mind?
Date: 7 Jul 2000 13:15:54 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > Below is a couple of messages posted to the OpenSSL users mailing list.
> > Seems someone down at RSADSI has lost it.
>
> No, this is typical behavior for RSADSI. They have a habit of sending
> out threatening BS letters at the slightest provocation, such as when
> they recently threatened to sue a Canadian citizen for violating the
> patent on the RSA public key encryption algorithm.
Yes, that was a little silly. RSADSI have certainly gone the right way
about making themselves unpopular. The mess over PGP, which resulted in
the `legal kludge' and the nasty hacking to make PGP use the rather poor
RSAREF implementation, is another case in point.
> In September, the RSA public key encryption algorithm becomes public
> domain
Indeed. I still need to plan some celebrations for this event.
> and the whole thing becomes moot. RSADSI has not earned themselves
> friends by their behavior (especially by refusing to license the RSA
> PK algorithm to other toolkit makers),
Oooh. I didn't know they'd done that. I'm not susprised that this
hasn't won them friends.
> and is likely to be out of the toolkit business shortly thereafter
> unless they can persuade some hapless souls that RC5 and RC6 are worth
> licensing (in preference to Blowfish/Twofish). Luckily (for them, not
> for us), they have purchased Verisign and thus will continue to be a
> going concern... a pity, that.
The downside to the *fish algorithms is their memory usage profiles.
Blowfish also has very slow key scheduling, but that's not usually a
major concern.
> Oh well, at least they provide Rivest with a living beyond the meagre
> salary of a college professor... I guess they do SOMETHING good (well,
> firing the only first-class talent they have really WOULD be stupid!).
RSADSI have more talent than just Rivest: Silverman, Robshaw, Kaliski
and Yin are certainly not fools, to name just a few.
> > I found the part about them *owning* EAY quite amusing. I wounder if
> > anyone bothered telling him that he is considered owned property of
> > RSADSI.
>
> Yeah right :-). But there are some legal concerns about what happens
> to software when its current owner decides to revoke the open source
> license.
I didn't think that this was an issue for the SSLeay source. While
BSafe SSL-C is based on the SSLeay code, I don't think there's any hint
that Eric and co. have actually signed over rights to the existing
code.
> It is certainly legal to use OpenSSL for commercial purposes, as long
> as you remove the RSA PK encryption portion from the actual source
> code. Also remove RC5 support from it, that's another RSADSI-patented
> algorithm. Also remove IDEA support from it, that's patented by
> another group.
RSADSI might also get snotty about RC4, but they'd probably not get very
far with it. I think they're planning to produce an RFC for it, and Ron
has had a link to the leak on his own web pages for ages.
> Note that, after September, it's perfectly legal to put the RSA PK
> encryption portion back in, since it enters the public domain at that
> time.
76 days and counting!
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto jokes? (potentially OT)
Date: 7 Jul 2000 13:19:34 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> I'm having a _great_ deal of difficulty trying to conceptualize unchosen
> dimmer settings. Does that make the switches autonomous? Talk about
> decidability problems...
In a chosen dimmer attack, the adversary is actually allowed to control
the dimmer knob. In a known dimmer attack, the owner of the dimmer
paints a scale on the knob and twiddles it, letting the adversary see
which settings he's using. We also have adaptive chosen dimmer
attacks, and the academically interesting but impractical chosen light-
intensity attacks.
-- [mdw]
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Fri, 07 Jul 2000 07:58:02 -0600
Nicol So wrote:
<snip>
>
> I wouldn't call the the article misleading or wrong, but one does have
> to be careful when understanding what it says.
>
> In a proof by contradiction (reductio ad absurdum), *a* false conclusion
> is derived from a set of premises. In a valid argument, the conclusion
> is always true if all the premises are true.
<snip>
The point is, the argument attributed to Scientific American is
*not* valid, which means we cannot conclude anything from the
contradiction in the argument's final statement. That is, the
reductio ad absurdum doesn't work.
YUKE: Call it n. You take and form the product of all primes there
are right up to n. Ok? That's 2x3x5x...xn. Now add 1 to
the product and call the number you finally get p.
TYRO: Don't tell me that p is a prime!
YUKE: Sure is. Prime as all get-out.
Me: Wrong, sir!
Yes, we know that the there are an infinite number of primes, but
the argument as presented fails to prove this. And anyone who reads
the article without carefully checking the reasoning has been infected
with the false idea that the product of a bunch of primes, plus one,
is always prime. Therefore the article is indeed wrong and
misleading, even if it does make *some* true statements.
JM
P.S.
Another thing one has to be *very* careful about in proofs by
contradiction, is to know all of your assumptions. The proof
that there are an infinite number of primes requires proof (or
faith!) that the concept of primeness is in fact well defined,
for example. You can prove a lot of things about "numbers" in
a finite field, but somewhere you must discover some reason for
the proof of an infinite number of primes to fail in that case!
It is also in this spirit of extreme care with mathematical proof
that the article in Scientific American is so disappointing. One
would hope that, even in a popularization, the reasoning would be
more faithful to the nature of the subject. Or perhaps that is
just wishful thinking...
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: MD of large data-sets
Date: 7 Jul 2000 14:21:32 GMT
Efthymios Ntasis <[EMAIL PROTECTED]> wrote:
> I want to the ensure the integrity of a data-set, which its zipped
> size is between 25 and 50 Mbytes.
Oh, that's not going to take very long. Hashing the compressed image is
a reasonable thing to do.
> In practice, when a digital signature scheme is used, do I have to
> insert the whole data-set to a message digest
If you want to test the integrity of the whole data-set then yes, you
have to hash it all.
If you wanted to take short-cuts, you could use a (secure) pseudo-random
number generator, with a secret seed, and use this to decide which
subset of the data you actually hash. By deciding exactly what
proportion of the data you're going to skip over, you can tune the
probability that an adversary can make a change without being detected.
I don't recommend that you do this. I think hashing should be fast
enough anyway.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Beginner Questions
Date: 7 Jul 2000 14:26:33 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Now store each a_i in a word of an array. This is much more
> efficient than storing just 1 digit.
>
> Read chapter 4 of Knuth Vol. 2. [This is ESSENTIAL reading]
And when you've finished that, read chapter 13 of HAC (available online
from http://cacr.math.uwaterloo.ca/hac/).
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Prime Numbers?
Date: 7 Jul 2000 14:38:27 GMT
John Myre <[EMAIL PROTECTED]> wrote:
> Another thing one has to be *very* careful about in proofs by
> contradiction, is to know all of your assumptions. The proof that
> there are an infinite number of primes requires proof (or faith!) that
> the concept of primeness is in fact well defined, for example. You
> can prove a lot of things about "numbers" in a finite field, but
> somewhere you must discover some reason for the proof of an infinite
> number of primes to fail in that case!
This doesn't work in finite fields for fairly fundamental reasons:
* There isn't a sensible definition of primality. Given an element p
<- F_q, choose x_0, x_1, ..., x_{n-1}, let y be the multiplicative
inverse of the product of the x_i, and then x_0, x_1, ..., x_{n-1},
p y are factors of p. (Thus you don't get unique factorization
either.)
* Finite fields don't have orderings which interact properly with
addition and multiplication. Hence, the idea of assuming that
there's a `greatest' element of some kind and then finding a
`greater' one doesn't work.
> It is also in this spirit of extreme care with mathematical proof that
> the article in Scientific American is so disappointing. One would
> hope that, even in a popularization, the reasoning would be more
> faithful to the nature of the subject. Or perhaps that is just
> wishful thinking...
I fear so.
-- [mdw]
------------------------------
From: Florian Weimer <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: 07 Jul 2000 17:00:51 +0200
John Myre <[EMAIL PROTECTED]> writes:
> Yes, we know that the there are an infinite number of primes, but
> the argument as presented fails to prove this. And anyone who reads
> the article without carefully checking the reasoning has been infected
> with the false idea that the product of a bunch of primes, plus one,
> is always prime. Therefore the article is indeed wrong and
> misleading, even if it does make *some* true statements.
I think the proof is correct, for the following reason: First, show
that a number is prime if and only if it is not divisible by other
primes. Under the assumption that n is the largest prime, n! + 1 is
prime, because no prime numbers (which are in the range 1 .. n) divide
it. But n! + 1 is larger than n, contradiction.
But I'm sure it's not a good idea to present Euclid's proof this way
because as a result, a lot of people think that n! + 1 is prime even
if we don't assume that there finitely many primes.
------------------------------
From: "Ed Suominen" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Porting Keys Between PGP, other Apps
Date: Fri, 7 Jul 2000 08:01:28 -0700
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Originally, I wrote:
> > Can anyone shed light on this and why the PKCS #7 "thumbprint" is
> > different from the PGP "fingerprint" when its the same exact RSA
> > key?
>
To which Mark Woodring responded:
> I think that PKCS#7 hash is actually hashing some DER-encoding of
> the key, whereas PGP is doing something sensible and just hashing
> the key data. BER and DER encodings are part of the ASN.1
> braindamage which infests the PKCS standards.
And to which a person responded via email:
> SHA1 "Thumbprint"
> 91FE 6BC5 A1F8 6B0A 4B19 A035 B36B 136E 4C47 1944
> PGP "Fingerprint"
> 8EBF A10B A170 376D BCB6 649D 6143 D34A
>PKCS "thumbprint" is an SHA-1 hash of the key. PGP Fingerprint is
>an MD5 hash of the key. Different hash algorithms.
I don't think the difference is as simple as a SHA-1 vs. MD5, because
when I imported the PKCS certificate into Internet Explorer 5.0, I
got the correct 91FE... hash for SHA-1, but here's what IE5 told me
the MD5 hash is:
30A8 9E88 2DA1 6B43 8134 1125 7977 1827
I notice that PGP provides a 128 bit hash value while the SHA-1 hash
from PKCS has 160 bits. Does this mean that the email responder's
point is correct that PGP hashes the RSA key with MD5?
Ed Suominen
Registered Patent Agent
Web Site: http://eepatents.com
PGP Public Key: http://eepatents.com/key
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.5.3
iQA/AwUBOWXwX6mKuMvNCWDGEQL85ACeIt02Pc8dx97R8mxvFJdkh9mxF8IAnA4q
pP1hvN8d7qhvX+pwo9HbcyRh
=VSWM
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
