Cryptography-Digest Digest #574, Volume #12 Wed, 30 Aug 00 16:13:01 EDT
Contents:
Re: RSA public exponent (Thomas Pornin)
Re: I need ADK tampered key that PGP will not detect ADK, on it ... (Rich Wales)
Re: RSA public exponent (David A Molnar)
when netscape saves your password for my yahoo site in a cookie, how (Lee Herfel)
Re: "Warn when encrypting to keys with an ADK" (Rich Wales)
Re: RSA public exponent (Mack)
Serpent S-boxes (Mack)
Re: Secure Deletion of Data ("Keith Monahan")
Re: Where is everyone? ("Keith Monahan")
Re: Idea for creating primes (Mok-Kong Shen)
Re: Idea for creating primes (Mok-Kong Shen)
Re: Patent, Patent is a nightmare, all software patent shuld not be (Mok-Kong Shen)
Re: Serpent S-boxes ([EMAIL PROTECTED])
R: RSA public exponent ("Cristiano")
QKD and The Space Shuttle ("Richard Bembridge")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: RSA public exponent
Date: 30 Aug 2000 17:24:59 GMT
According to David A Molnar <[EMAIL PROTECTED]>:
> There isn't a disparity, really. Consider that q-1 and p-1 are both even,
> thus their product is even. So gcd( (p-1)*(q-1), 3) = 1 always.
Hum. 6 is even, and yet, gcd(6, 3) = 3.
For a more complete example, consider p = 19 and q = 31. Both are prime,
but gcd((p-1)*(q-1), 3) = gcd(540, 3) = 3.
To fulfill the condition with e = 3, you must choose p = 2 mod 3,
and q = 2 mod 3 either.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: I need ADK tampered key that PGP will not detect ADK, on it ...
Date: 30 Aug 2000 10:29:24 -0700
=====BEGIN PGP SIGNED MESSAGE=====
Earlier, in response to a query from "jungle", I wrote:
> > Have you tried Ralf Senderek's "A4" key with NAI's
> > latest PGP (6.5.8)? (That is, the same key you've
> > already tried, but with a different PGP?)
"jungle" replied:
> pgp v658 ? I don't have reason to upgrade from v262 ...
> the adk problem [ realistically doesn't exist ], when
> you [ I ] know what I'm doing ...
I'm a bit confused now. My understanding was that "jungle" was asking
for details about the ADK bug (and how various keys and/or software
versions would respond to it).
I was =not= recommending to "jungle" (or anyone else) that they should
adopt 6.5.8 for production use. I was simply describing a scenario (a
particular key, together with a particular version of the PGP software)
which I felt would come close to answering his/her question.
> the first simple rule in encryption software business
> is : - don't use when you don't know what is inside ...
Absolutely. I really don't believe in using encryption software unless
the algorithms are well understood and the source code is available.
Even if I, personally, don't have the time or expertise to study and
evaluate the source myself, having it readily available means other
people with those skills =will= have an opportunity to study it and
publicize any flaws they might find.
> when you know, you are the lucky one who works for nai
> company ... I don't know because source code is not
> available ...
It was a bit difficult for me to figure out what "jungle" meant by the
above (English can be a very tricky language for a non-native speaker
to express himself properly in). I =think= "jungle" was saying that
the only way someone could have access to the PGP 6.5.8 source right
now would be if they were employed by NAI -- and that since "jungle"
doesn't work for NAI, he doesn't have access to the 6.5.8 source.
Just so no one will misunderstand, I (Rich Wales) do =not= work for
NAI, I have no connections with NAI, and I have not seen the source
code for PGP 6.5.8 (or any other version for which the source hasn't
been publicly released). I do know one person who used to work on
PGP (he and I were co-workers at another company before he left to
join PGP), but we've never talked about PGP internals, and, in any
case, he recently transferred to another division of NAI.
As for using 6.5.8, I realize that people working in companies which
mandate corporate ADK's probably have little choice but to use it,
with or without the source. FWIW, my current employer doesn't use
any sort of encryption right now, so this issue doesn't affect me
directly.
I would feel more comfortable about 6.5.8 if the source were available
right now. At least I can note that the source code for some earlier
freeware versions (such as 6.5.1i) are available, and the algorithms
used in the 6.x line are well known, and my gut feeling is that Phil
Zimmermann and the PGP developers have =not= "sold out" by intention-
ally creating a flawed product. But, having said all that, I will
still feel better about NAI's current commercial PGP product when the
source has been released (at least for review by numerous independent
experts, under a limited NDA which will allow them to fully publicize
any flaws they find).
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3a
Charset: noconv
Comment: Rich Wales's public keys at http://www.webcom.com/richw/pgp/
iQEVAwUBOa1EZEm4X0z9+PxlAQELtggApwjFZA5R/tduh5X1yHYymHcI/9soATDN
V+zIoE34ggGYW/eVMdDQgNra63dKK/V/p5fcpeuhYme+KYeotuxvEbBP4169JJFD
wico/xatHxMpadnDYmLHm3O7zCH3OoxCX3vw0OyjD2oOjBnUXCp6q+X3aSuk3kSW
y3CjgpxAZMLzQhE9PieeWbZJoFjdgcVqKcWLjYQkIEq4tof0G26oHLmPH6A5RtJJ
v4cHwkC+khMVIXeP3wJm01blaXaldqv8QZHK82NMwITXhwXmpk8pqIN9RgeUU2Da
laJpF62ec+moD6OXQv7WdJLFNyOetFlQDAlrS74ixVoPywK9mSGlGA==
=b0AN
=====END PGP SIGNATURE=====
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: 30 Aug 2000 17:03:55 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
> There isn't a disparity, really. Consider that q-1 and p-1 are both even,
> thus their product is even. So gcd( (p-1)*(q-1), 3) = 1 always.
sorry, this is totally wrong. :-(
Yes, their product is even, but 3 could be a factor of p-1 * q-1 as well.
------------------------------
From: Lee Herfel <[EMAIL PROTECTED]>
Subject: when netscape saves your password for my yahoo site in a cookie, how
Date: Wed, 30 Aug 2000 17:35:48 GMT
I am considering switching my primary email address over to my yahoo
site which I have set up to automatically
load up without prompting me for a password.....two scenerios come to
mind
1)my password is saved in a cookie and sent to the site automatically
2)the password is just waived for the site...which the wording does not
seem to imply ie "remember my password" is checked.
so it seems to me that scenerio 1 is the case, it also seems they would
encrypt it somewhere.... how easy is this encryption to break?
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: "Warn when encrypting to keys with an ADK"
Date: 30 Aug 2000 11:09:40 -0700
Phil Harrison wrote:
> I would suggest that you enable the ADK column in PGP
> keys and see if any keys in your keyring have an ADK.
> If so, then make sure that it is supposed to be there.
> Better still is to get the hotfix.
Another reason to get the fix is that, even if you enable the ADK
column (which shows whether a key has an ADK), this doesn't help you
distinguish a key with a legitimate ADK from a key with two ADK's
(one of which is legitimate, but the other is not).
> Then they must also get the additional key onto the
> keyring of the sender.
I'm curious about this requirement. In order to get ADK's to work --
especially in situations where companies want to make them mandatory
(such as by configuring their mail servers to block incoming or out-
going encrypted messages that aren't accessible via the company's ADK)
-- it seems to me that one would want/need PGP to fetch the ADK auto-
matically from a key server (or, at least, prompt the sender that the
ADK is needed and ask for permission to go get it).
Do the commercial Windows versions of PGP 5/6 do this? Or do they
simply skip over an ADK reference in a recipient's key if the ADK is
not present in the sender's keyring? If the ADK is skipped for this
reason, is the sender notified?
> Finally they must hope that the sender does not notice
> that there was an ADK there and does not check with the
> recipient.
An ADK on what is supposed to be a personal, non-work key should
definitely be considered suspicious.
Less obvious, I fear, is the situation where an employee's key already
contains a legitimate ADK reference, but an attacker manages to add a
second, unauthorized ADK to it. The addition won't be flagged if the
sender is using a buggy PGP; he/she will see that an ADK is present,
but if he/she already knew this (or if the recipient confirms that an
ADK is in use), the sender might not bother to investigate further.
There is, BTW, one other thing a "Mallory" would have to do in order
to take advantage of the ADK bug. After the sender has unwittingly
encrypted a message which includes the ADK as a spurious recipient,
Mallory must somehow intercept a copy of the message (by tapping a
phone line, subverting an ISP, etc.).
> I don't know about you, but the only time I have ever
> seen a key with an ADK is on test keys created specif-
> ically to illustrate this bug.
I suspect legitimate ADK's are pretty much confined to commercial
settings -- e.g., sales reps in remote locations communicating with
the head office via (hopefully) secure, encrypted e-mail.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: RSA public exponent
Date: 30 Aug 2000 18:10:31 GMT
>According to John Matzen <jmatzen(at)origin(d0t)ea(d0t)com>:
>> I've read that good values for the RSA public exponent are 3 or 65537.
>> Then I read that you should use an exponent such that the GCD of
>> (q-1)(p-1) and the private exponent (e) is 1. So, my question is which
>> is better and what accounts for the disparity.
>
>
>e must be prime to (p-1)(q-1), so, when you choose your key, by
>randomly selecting p and q, you are more likely to have this property
>if e is prime. Your odds are about 44% with e = 3, and almost 100%
>with e = 65537, that the two first primes you choose are good in
>that respect.
>
>When enciphering with the public exponent, you perform a modular
>exponentiation, using usually the famous "square and multiply"
>algorithm. The complexity of this algorithm can be expressed in modular
>multiplications, and depends upon the binary representation of the
>exponent: each bit (except the first one) in the exponent means one
>squaring, and one extra multiplication if that bit is set to 1. 65537
>has the binary representation 10000000000000001, which means that there
>will be only one multiplication, and 16 modular squarings.
>
>
>e = 3 is the original exponent proposed in the paper from Rivest, Shamir
>and Adleman. However, there is a (real slight) security concern: if
>you encipher the same message three times with three different public
>keys and public exponent 3, an attacker will be able to retrieve the
>plaintext from the three ciphertext: if you have m^3 modulo N1, N2 and
>N3, you can easily get m^3 modulo N1*N2*N3 by Chinese Reminder Theorem.
>However, N1*N2*N3 is larger than m^3 (without the modulo) so you have
>m^3 with no modular reduction, and a simple integer cubic root will
>give you m.
>
>With e = 65537, this problem does not appear unless you encrypt the
>very same message 65537 times with 65537 different public keys. Quite
>unlikely.
>
>Note that the vulnerability does not affect PGP, since PGP encrypts en
>random session key with RSA, and this random key is never twice the
>same, even if the underlying message has not changed.
>
>
>To sum up, e = 3 is faster for encryption, and e = 65537 is faster
>for key generation.
>
>
> --Thomas Pornin
>
>
There are now better attacks than the one you describe. Not
having the papers in front of me right now I won't go into specifics
except to say that the current recommendation is a public key length
that is greater than 1/4 the length of the modulus. I believe the actual
value is .27 or something like that.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Serpent S-boxes
Date: 30 Aug 2000 18:27:11 GMT
Let me see if I understand the S-box criteria properly
1) The S-boxes are invertible
2) The S-boxes have 3 boolean equations of order 3 and one of order 2
3) No equation can have a hamming weight closer to a single input
or the inverse of an input than 6
4) The XOR table has no entries greater than 4
5) The LAT table has all entries between 4 and 12 (inclusive)
6) Any one bit change changes at least two bits
Some other criteria that appear to be redundant
7) All of the boolean equations have a non-linearity of 4
8) The inverse of the s-box has the same properties.
Do I understand the criteria properly?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "Keith Monahan" <[EMAIL PROTECTED]>
Subject: Re: Secure Deletion of Data
Date: Wed, 30 Aug 2000 18:45:44 GMT
Yeah, this article has been floating around for a number of years. It's
actually a great (and scary) article.
I wonder if anyone has done a more recent article, though. The way
technology changes, things might be considerably different now, than even
4/5 years ago.
Keith
Jeffrey Walton wrote in message <39ac3b94$0$[EMAIL PROTECTED]>...
>I thought this page mught have something on CDs (re: Destruction of CDs
>message thread). Interesting reading, with references.
>
>http://nondot.org/sabre/os/H3Disks/SecureDeletion.html
>
>
>
>
------------------------------
From: "Keith Monahan" <[EMAIL PROTECTED]>
Subject: Re: Where is everyone?
Date: Wed, 30 Aug 2000 18:47:26 GMT
Must be your ISP, I've got plenty of messages.
Rich Griffin wrote in message <[EMAIL PROTECTED]>...
>Is is just my ISP, or have all the messages disappeared?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: Wed, 30 Aug 2000 21:24:29 +0200
Scott Fluhrer wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote
> > O.k. This shows that the order of g is p-1 and hence p is
> > prime. But in a book of mine where this is proved it is
> > said that finding primes this way for large p is too slow
> > compared to modern methods.
>
> Actually, it's about as fast as a few passes with the Miller-Rabin test. In
> both cases, you pick a g, determine g^k mod p, where k is about as large as
> p, and then run quick tests on the results. With Tom's test, you run it
> once for every prime dividing p-1 (plus a few times to find an appropriate
> g). With Miller-Rabin's test, you run it until you get error probability
> "small enough". And, in both cases, when p is not prime, then almost all
> the time, you'll find it out the very first time you compute g^k mod p.
> And, of course, with both methods, you do some quick composite checks (eg.
> checking for small factors) first.
>
> What I suspect your book says that it's a slow way to prove a number p prime
> assuming you don't know a priori the factorization of p-1, because factoring
> p-1 is a bear. With Tom's approach, that isn't a problem.
Sorry for my poor knowledge. But if p is not prime, how
do I know the very first time that I compute g^k mod p?
I can't exclude the case that p is prime but I have picked
the wrong g, can I?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: Wed, 30 Aug 2000 21:24:35 +0200
[EMAIL PROTECTED] wrote:
>
> That's slightly right. My problem works the other way in that as soon
> as you find a primitive generator you know it's prime. However when
> you start with g=2 "g^k mod p" will not tell you right away that it's
> prime or not, unlike MR which will almost always immediately
> say "composite" if it is composite. With my method however you can
> discard values of g once you find a subgroup they belong to, so at most
> you will have to try a few times per base 'g'.
Right. But it depends on whether you have to discard only
a few trial values of g or a lot. That's why I asked
how much the tests g^s != 1 contributes to the purpose,
i.e. whether that implies large amount of computing effort
before success. Could you say something about the ease
or difficulty of finding a right g with reference to the
magnitude of p that you have investigated?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be
Date: Wed, 30 Aug 2000 21:25:05 +0200
Bill Unruh wrote:
>
> That patent is plain silly from the bit I have looked at it. By 1997 all
> of those functions were well known. However the patent office does not
> appear to be terribly up to date on the state of any field. See the
> recent patent awarded for faster than light communication.
It's probably unlikely but on the other hand also can't be
excluded that the firms selling PK products do nothing in
the issue and simply pass the fees they'll eventually pay to
that patent holder on to the consumers. That would be bad.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Serpent S-boxes
Date: Wed, 30 Aug 2000 19:06:23 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mack) wrote:
> Let me see if I understand the S-box criteria properly
>
> 1) The S-boxes are invertible
Yes.
> 2) The S-boxes have 3 boolean equations of order 3 and one of order 2
It means you cannot combine upto three of the output bits via xor for
all inputs to create a linear function. In other words the output bits
are linearly independent of each other. This is also known as the BIC
or Bit Independence Criterion.
> 3) No equation can have a hamming weight closer to a single input
> or the inverse of an input than 6
Or a WT of -4/4. Which is a distance of 12 from the closest linear
function.
> 4) The XOR table has no entries greater than 4
Yes.
> 5) The LAT table has all entries between 4 and 12 (inclusive)
LAT?
> 6) Any one bit change changes at least two bits
To clarify. No single bit difference causes a single bit difference.
> Some other criteria that appear to be redundant
> 7) All of the boolean equations have a non-linearity of 4
Well you want all boolean equations of the input/output bits to be
nonlinear to make the sbox secure.
> 8) The inverse of the s-box has the same properties.
The inverse sboxes must be used to decrypt, and we want decryption to
be just as secure.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: R: RSA public exponent
Date: Wed, 30 Aug 2000 21:29:17 +0200
John Matzen <jmatzen(at)origin(d0t)ea(d0t)com> wrote in message
[EMAIL PROTECTED]
> I've read that good values for the RSA public exponent are 3 or 65537.
Then
> I read that you should use an exponent such that the GCD of (q-1)(p-1) and
> the private exponent (e) is 1. So, my question is which is better and
what
> accounts for the disparity.
It is provable that a public exponent with only few bits is not secure (for
certain types of attacks).
With today's computers an attack with public exponent of 90-96 bits are
infasible.
By using Montgomery reduction for exponentiation, the advantage of an
exponent with 1 or 2 bit to 1 is trascurable.
In my programs the speed with a public exponent of 3 or 65537 or a 96 bits
number is the same.
Cristiano
------------------------------
From: "Richard Bembridge" <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: QKD and The Space Shuttle
Date: Wed, 30 Aug 2000 20:53:22 +0100
What kind of payloads can the Shuttle handle?
What is the typical altitude of the Shuttle when in Low Earth Orbit (LEO)?
What is the current record for QKD through free-space over a non-folded
(i.e. without the use of mirrors that may compensate for turbulence) path?
What does this record equate to in terms of 'straight up in the air'?
What are the mass and dimensions of the receiver (Bob) in the record-holding
apparatus?
Would it be possible to make these smaller (mass and dimension)?
Could they be fitted into the Shuttle?
Does anybody see where this is leading?
I wonder if...
--
[EMAIL PROTECTED]
------------------------------
** 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
******************************
