Cryptography-Digest Digest #583, Volume #12 Thu, 31 Aug 00 22:13:01 EDT
Contents:
Post-ADK bug blues ("A. Melon")
Re: QKD and The Space Shuttle (wtshaw)
Re: Remark on practical predictability of sequences (Mok-Kong Shen)
Re: QKD and The Space Shuttle (Brian Thorn)
Re: more on that neat prime generator ([EMAIL PROTECTED])
Re: one-time pad question (Mr. Ian E. Yolk)
Re: an attack for stream ciphers ([EMAIL PROTECTED])
Re: an attack for stream ciphers ([EMAIL PROTECTED])
Re: QKD and The Space Shuttle (Markus Mehring)
Re: blowfish problem ("Kelsey Bjarnason")
Re: blowfish problem ("Bruce G. Stewart")
Re: blowfish problem (Kaz Kylheku)
test (Jim Walsh)
Re: QKD and The Space Shuttle (John Savard)
Re: QKD and The Space Shuttle (John Savard)
----------------------------------------------------------------------------
Date: Thu, 31 Aug 2000 14:12:19 -0700
From: "A. Melon" <[EMAIL PROTECTED]>
Subject: Post-ADK bug blues
The discovery that Mallory can tamper with PGP v4 self-signatures
to insert ADK's and thus trick certain newer versions of PGP into
giving the session key to Mallory is pretty upsetting, especially
in view of the fact that (1) GnuPG uses the v4 format (even though
it isn't vulnerable to ADK's itself, Mallory can still tamper with
keys generated by GnuPG to trick PGP users of the key), and (2) the
other family of freeware public key systems, namely Pegwit and its
derivatives (Pegwit-W and CryptoKong), has also bit the dust.
It appears that if you want a general PC cryptosystem that can
generate a public key that is secure, we are stuck with the ADK-free
PGP v3 signature format, which means using software from the PGP v2.6
stable and its derivatives. However, PGP 2.6.3i (the most popular
in this category, especially after the RSA patent expires and
Americans can start using it legally) is not without its problems.
Ideally, I would like a system where the public key is at least as
secure as the 128-bit symmetric session key, which is not the case
when you are limited to 2048-bit RSA. Likewise, the hash function
ought to achieve that level of security too, especially if you plan to
use the cryptosystem for clearsigs - but MD5 comes up short in this
regard.
My question is: what is the best software option for minimizing these
shortcomings? I know the Cyber-Knights Templar have come up with a
derivative of PGP 2.6 that allows bigger RSA key sizes. Likewise, the
pgpi.org page has links to a variant called Even-Better Privacy v2.7,
that allows one to subsitute HAVAL for MD5 as the hash function.
Unfortunately, there doesn't seem to be a PGP 2.6 variant that does
both, and I have no idea how trustworthy either the CKT or EBP
software is. Has anyone taken a careful look at these PGP v2.6
variants? And assuming that they are both trustworthy, which is the
lesser of two evils - MD5+big RSA keys, or HAVAL+2048-bit RSA? Or is
there some other software I'm overlooking?
Maybe these "evils" aren't really that much of a problem in practical
terms, but a lot of people said the same thing about using the v4
signature format too. In this business, one can't be too paranoid.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Thu, 31 Aug 2000 14:59:47 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> David A Molnar wrote:
> >
> [snip]
> > The problem with all of these protocols is that if an adversary can
> > replace the random beacon with his own source, all bets are off.
> > So some people would *like* to see a satellite in the sky broadcasting
> > random bits to the world. There will still be issues with ground-side
> > jamming and with authentication of the satellite, though, which are
> > not yet fully ironed out (at least not that I've seen).
>
> Isn't the trouble in principle the same with certification
> where one needs some trust/belief on a third party, in
> other words there is some non-objectivity that can NEVER
> be entirely disposed of?
>
> M. K. Shen
Yes, just when are you ready to trust imperfect strangers who interests
are likely to viewed by them as superior to your own. All the propaganda
to the contrary is the real snake oil.
--
A Pangram:
Fast girls show jugs to vex quizical boys, plus mankind.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Remark on practical predictability of sequences
Date: Fri, 01 Sep 2000 00:01:31 +0200
"John A. Malley" wrote:
>
> Does enciphering the output of a fast and predictable PRNG always
> generate an unpredictable output sequence if the applied cipher is
> secure? A draft paper considering a specific example is now available
> for the group's review and comment at
>
> http://www.homeworlds.com/papers/SECLCG.doc
>
> The attacks presented in this paper show enciphering the output of a
> fast and predictable PRNG with a secure cipher does not always generate
> an unpredictable PRNG output sequence. Mathematical operations common
> to the PRNG and the secure cipher can permit the prediction of the
> enciphered sequence without knowledge of the cipher’s secret key or of
> the PRNG’s parameters and without "brute-forcing" the secure cipher. The
> predictability of the enciphered PRNG output sequence depends on the
> internals of the cipher applied to the predictable PRNG. These attacks
> are not guaranteed to succeed for any known subset of the output of the
> encrypted PRNG but the probability of success increases with the volume
> of known encrypted PRNG output.
Your work is certainly very interesting. However, I guess
that your result could also be interpreted this way:
ElGamal does not provide perfect secrecy (which no
practical algorithm in fact does). In some sense I suppose
it is also remniscent of the opinion that in multiple
encryption it is preferable to have adjacent ciphers of
(widely) different nature.
M. K. Shen
------------------------------
From: Brian Thorn <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Thu, 31 Aug 2000 17:07:31 -0500
On Thu, 31 Aug 2000 12:16:36 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>On Wed, 30 Aug 2000 20:53:22 +0100, "Richard Bembridge"
><[EMAIL PROTECTED]> wrote, in part:
>
>>What kind of payloads can the Shuttle handle?
>
>The Space Telescope represented the upper limit.
Hubble is mostly an empty tube. It weighs 24,000 lbs, about the same
as the (now retired) Spacelab module. Galileo, Ulysses, Magellan, all
of the TDRS satellites, ACTS, and Chandra all weighed roughly twice as
much as Hubble, since they all were paired with big, heavy boosters.
>>What is the typical altitude of the Shuttle when in Low Earth Orbit (LEO)?
>
>About 250 miles.
140 miles would be about average for flights prior to the start of
Space Station assembly. The Space Station orbits at 200 miles.
Brian
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: more on that neat prime generator
Date: Thu, 31 Aug 2000 22:04:55 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > I was thinking, you could start lower, making 128-bit primes with my
> > method by picking 16 random 16-bit primes (*) then making 6 128-bit
> > primes. Then you can use 3 each as factors of a 768-bit number ...
>
> Isn't 16 x 16 = 256, not 128? I'll assume you mean 8 16-bit primes.
Yea.
>
> Isn't it true that about half (or less) of the 16-bit primes have
> their high bit set? That would mean you have about 2^-8 chance of
> the product being a full 128 bits. Although actually, since you
> want 2p'+1 to be 128 bits, you want p' to be 127 bits. In fact, you
> would expect to be about 7(#) bits short or so, but you might be
> anywhere from one bit longer than you would like to way short.
>
> (#) Back-of-the-envelope calculation. Assume half of the 16-bit
> primes (i.e., 4 of them) are actually 16 bits; assume half of the
> rest (2 of them) are 15 bits; half left (one) is 14 bits, and the
> last is 13 bits. Then we are missing 2x1 + 1x2 + 1x3 = 7 bits.
> Crude, perhaps.
Even if you consider a smaller prime such as 251^8 you still get a 64
bit number. see below...
> > (*) The neat thing is that 16-bit primes can be stored in a table
since
> > there are only 6521 of them. Now the problem is how many primes
cannot
> > be represented by this, the answer "None of them.".
>
> Well, you'd certainly miss 2^19+1 and 2^31+1, or any other prime
> 2q+1 where q has more than 8 factors. Of course you would also
> miss any where q was itself prime, or had any factors larger than
> 2^16.
>
> > If we include '1'
> > in the table then all primes from 2..2^128-1 can be represented. At
> > least it sounds right. We note that 6521^16 ~ 2^202 which means the
> > numerical range is covered at least.
>
> Counting 6521^N different products means you are counting as
> different those cases where the factors are reordered. I don't
> think I'll go to the trouble of looking up how to solve this
> combinatorial problem, but you can already see that some primes
> aren't represented, and those that are are not equiprobable.
>
> This might still be a neat method if the distribution is not
> too skewed to give any advantage to the attacker - I'll leave
> that problem for people smarter than I.
A better idea is to take 'x' primes until you hit a certain numerical
range. This will allow for numbers like 2^19 + 1 = 2(2^18) + 1. As
for making prime factors above 2^16 it's a matter of choosing a
suitably large factor base. We could use 2^32 as the upper limit to
include more primes. obviously not a complete solution
Tom
>
> JM
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mr. Ian E. Yolk)
Subject: Re: one-time pad question
Date: Thu, 31 Aug 2000 22:36:38 GMT
Emery Conrad <[EMAIL PROTECTED]> wrote:
>can someone explain to me (or point me to some resource) that explains
>how one can crack a one-time pad whose key is not perfectly random. i'm
>not sure i believe it can be done (in any but the most obvious of
>patterned data).
It's quite possible that at least in some cases, you're right and it can't
be done. The main reason that pure randomness is stressed in the
description of a one time pad is that the mathematical proof that the
method is secure depends on that provision, among other things. A
technically non-random pad might still be secure, but you won't be able to
prove it.
--
"Mr. Ian E. Yolk" is actually 0295 436871 <[EMAIL PROTECTED]>.
01 234 5 6789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: an attack for stream ciphers
Date: Thu, 31 Aug 2000 22:57:05 GMT
In article <8nmrjb$fum$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> Anyway, if you try this experimentally on RC4, what you find
> is that you need to start out with knowledge of somewhere
> between 1/2 to 2/3 of m[] for this tactic to work. Otherwise,
> you lose knowledge fairly quickly, and the technique is pretty
> much useless.
I implemented this anyhow. It didn't work. Details:
I scaled it down to 6-bit rc4 (array of size 64) to make things a
little faster.
For each result r[i],
* Generate lots of internal states that produced r[i-9]..r[i-1]
and r[i+1]..r[i+9]. That's a match of 18 terms, or
ln(2^^(8*18))/ln(8*64!) = 48% of the internal state determined.
* Count how often internal states produce each possible value of r[i].
* Find how likely the actual value of r[i] is.
Repeating this for many r[i]s gives a slight bias for each result,
and those can be multiplied together to eventually detect if the
sequence is an RC4 sequence or not. It wouldn't tell you the
internal state, but it would distinguish RC4 from non-RC4.
This approach should detect at least as much bias as can be found
by looking at just pairs of results. There are known biases for
certain pairs of results, like (0,0).
I never found any detectable bias. I only looked at 5 randomly
chosen r[i]s because my internal state matcher is very slow
(about 30 seconds per matching interal state found). I never
generated more than 25000 internal states for any r[i]. A
sample of 25000 should detect any bias for any value beyond
about (1 +- .3)/64. I guess I didn't hit any interesting pairs.
It appears that xxxxxxxxx_xxxxxxxxx sequences have not much more
bias than their subsequence pairs x_ and _x.
I'll put my code at http://burtleburtle.net/bob/crypto/partrc4.c when
I get home tonight.
My take on this is that pairs of results have detectable biases
because the number of ways to produce a pair of results is small.
Small samples have relatively large biases. Larger sequences
can be produced in a large number of ways, and large samples have
relatively small biases. The bias should go up again for even
larger sequences that can be matched only a few thousand ways, but
if you could match those then a few thousand trials would hit the
true internal state anyhow.
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: an attack for stream ciphers
Date: Thu, 31 Aug 2000 23:22:38 GMT
In article <8omnrn$ne2$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I implemented this anyhow. It didn't work.
Here's another attack that I don't intend to implement and that I
haven't seen anyone else try so far: apply a belief propagation network
to rc4.
Belief propagation networks are known to work well on Gallager codes,
which are big np-complete matrix problems
(http://wol.ra.phy.cam.ac.uk/mackay/p0.html). You could view an RC4
sequence as a very redundant encoding of its internal state. A network
for a 1000-term sequence would have hm, 256 array positions of 256
possible values apiece, 256*256*1000 times other factors I'm forgetting,
it would be humongous. You'd try it out on a 4-bit rc4 first of course,
that's only 16*16*100, much more feasible.
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Markus Mehring <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Fri, 01 Sep 2000 01:54:59 +0200
On Thu, 31 Aug 2000 19:58:58 +0000, Alan Mackenzie<[EMAIL PROTECTED]>
wrote:
>WTF do all these TLAs mean? Please, pretty please? This post is appearing
>on talk.politics.crypto and sci.crypt as well as sci.space.shuttle.
>
>For starters:
>QKD: (Is this "Quantum" something?)
Quantum Key Distribution. I figure this is some cryptology stuff, so you
folks over in .crypt* should explain this to us in .space* rather than vice
versa ... :)
>GRO:
Gamma-Ray Observatory. That's the "Compton GRO" that has been deorbited a
while back, and stirred the media a bit because scientists still wanted to
use it, while NASA found it was about time to get rid of it before they
totally lost control and couldn't deorbit it safely (i.e. in a remote area)
in case yet more of its gyroscopes failed.
>HST: ("High Speed Train"?)
Hubble Space Telescope. I guess you know what that is. If not, it's a
telescope that is in orbit since April of 1990.
>STS-93:
Space Transportation System, i.e. the Shuttle (program). The missions are
numbered (not quite chronologically), STS-93 is the mission that flew in
July '99 and deployed the Chandra/CXO observatory in orbit, where it is
still doing some seriously cool science as of writing (i.e. the telescope -
the Shuttle, Columbia in this case, has of course landed after some days).
>AXAF/IUS
AXAF is 'Advanced X-ray Astrophysics Facility', basically a different name
for the Chandra-observatory.
IUS is 'Inertial Upper Stage', that's a booster stage that pushes its
payload from a parking orbit into the desired final orbit (a highly
eccentric orbit in this case). The AXAF/IUS is the combo of both objects
-payload and stage- as it was launched inside the payload bay of the Space
Shuttle and deployed from there in orbit.
>ISS:
International Space Station. That's the space station that is currently
being built in orbit and to which the majority of the upcoming Shuttle
flights will go.
>PV-6:
That's one of the solar arrays that are yet to be added to the ISS in order
to take care of the power supply. It will be brought up on some upcoming
Shuttle flight.
>LEO: "Low Earth Orbit", perhaps? :-) Or "Lyons' Electronic Office"?
Low Earth Orbit, correct.
>>> About 250 miles.
>> About 250 statute miles, yes.
>Are satellite altitudes really quoted in statute miles?
Sometimes, apart from that it's mostly nautical miles, the sensible rest of
the world uses kilometers instead. :)
CU! Markus
--
http://www.geocities.com/Area51/Vault/8611/
------------------------------
From: "Kelsey Bjarnason" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Fri, 01 Sep 2000 00:11:02 GMT
[snips]
"Kaz Kylheku" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> >might be promoted to "int" when used in an expression but that
> >isn't quite the same. No?
>
> In what context would a character constant not be used in an expression?
I think he might be getting at the implicit silliness of the following:
char c;
c = (char) 'a';
Since it's a char value, and since it's being assigned a char, why is the
cast necessary? It shouldn't be... but if 'a' is an int rather than a char,
one might presume that unless char and int are the same size on your
implementation, you're risking compilation warnings ("Possible loss of
precision assigning int to char" or some such).
In such a case, the notion of character constants actually being ints seems
bizarre in the extreme.
------------------------------
From: "Bruce G. Stewart" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Fri, 01 Sep 2000 00:43:31 GMT
Kelsey Bjarnason wrote:
>
> [snips]
>
> "Kaz Kylheku" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> > >might be promoted to "int" when used in an expression but that
> > >isn't quite the same. No?
> >
> > In what context would a character constant not be used in an expression?
>
> I think he might be getting at the implicit silliness of the following:
>
> char c;
>
> c = (char) 'a';
>
> Since it's a char value, and since it's being assigned a char, why is the
> cast necessary? It shouldn't be... but if 'a' is an int rather than a char,
> one might presume that unless char and int are the same size on your
> implementation, you're risking compilation warnings ("Possible loss of
> precision assigning int to char" or some such).
>
> In such a case, the notion of character constants actually being ints seems
> bizarre in the extreme.
And yet 'tis so, and was ever thus.
------------------------------
From: [EMAIL PROTECTED] (Kaz Kylheku)
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Reply-To: [EMAIL PROTECTED]
Date: Fri, 01 Sep 2000 01:21:08 GMT
On Fri, 01 Sep 2000 00:11:02 GMT, Kelsey Bjarnason <[EMAIL PROTECTED]>
wrote:
>[snips]
>
>"Kaz Kylheku" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>
>> >might be promoted to "int" when used in an expression but that
>> >isn't quite the same. No?
>>
>> In what context would a character constant not be used in an expression?
>
>I think he might be getting at the implicit silliness of the following:
>
>char c;
>
>c = (char) 'a';
>
>Since it's a char value, and since it's being assigned a char, why is the
>cast necessary? It shouldn't be...
Not only is it not necessary, it does nothing useful. The expression
(char) 'a' promotes back to type int.
>one might presume that unless char and int are the same size on your
>implementation, you're risking compilation warnings ("Possible loss of
>precision assigning int to char" or some such).
That is not a diagnostic required by ANSI C and only a braindead compiler
(MSVC?) would produce it an assignment from a character constant,
not realizing that the constant has a suitable range to convert to a char
without loss.
>In such a case, the notion of character constants actually being ints seems
>bizarre in the extreme.
It must have seemed that way to the C++ folk, because character constants
have type char in that language. (The actual reason is to allow for finer
grained overload resolution; the function call foo('x') will choose a
void foo(char) candidate over, say, a void foo(int) candidate).
------------------------------
From: Jim Walsh <[EMAIL PROTECTED]>
Subject: test
Date: 1 Sep 2000 01:36:23 GMT
Reply-To: [EMAIL PROTECTED]
test
Love, Jim
"If a state is governed by the principles of reason,
poverty and misery are the subjects of shame.
If a state is not governed by the principles of reason,
riches and honors are the subject of shame."
Confucius, as quoted by Thoreau in Civil Disobedience.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Fri, 01 Sep 2000 02:07:51 GMT
On Thu, 31 Aug 2000 19:58:58 +0000, Alan
Mackenzie<[EMAIL PROTECTED]> wrote, in part:
>For starters:
>QKD: (Is this "Quantum" something?)
Yes. I didn't pay enough attention at first: he is talking about
Quantum Cryptography, here referred to as Quantum Key Distribution. So
he is asking about Shuttle parameters because he is wondering about
setting up some kind of orbital satellite that uses Quantum
Cryptography for a secure one-time-pad type link.
Oh, yes:
>AXAF/IUS
Advanced X-Ray Array Facility/International Ultraviolet Spectrometer
probably, or something like that.
No, I wasn't quite right.
From:
http://hea-www.harvard.edu/~jcm/space/axaf/sts93.html
I find that AXAF stands for
Advanced X-Ray _Astrophysics_ Facility
and I was completely wrong about the IUS; is is the
Inertial Upper Stage
as described at
http://www.boeing.com/defense-space/space/ius/
which will be used to boost Chandra into its proper orbit.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Fri, 01 Sep 2000 01:59:46 GMT
I know some of them...
On Thu, 31 Aug 2000 19:58:58 +0000, Alan
Mackenzie<[EMAIL PROTECTED]> wrote, in part:
>GRO:
Gamma Ray Observatory.
>HST: ("High Speed Train"?)
Hubble Space Telescope.
>STS-93:
The designation of a Shuttle mission.
>ISS:
International Space Station.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
