Cryptography-Digest Digest #470, Volume #13 Mon, 15 Jan 01 03:13:01 EST
Contents:
Re: NSA and Linux Security (Rich W.)
Re: NSA and Linux Security (Rich W.)
Re: storing private keys ("Arnold Shore")
Failure discovered! (was Re: Security proof) (Benjamin Goldberg)
Re: The Word Problem and Group Isomorphism ("Ben Hopson")
Re: Security proof (Benjamin Goldberg)
Re: Security proof (David Wagner)
Re: Failure discovered! (was Re: Security proof) (David Wagner)
fun with solitaire ("r.e.s.")
Re: fun with solitaire (Mutt)
Re: fun with solitaire ("r.e.s.")
Re: Cavell Challenge #1 (Richard John Cavell)
Re: Cavell Challenge #1 ("John A. Malley")
Re: NSA and Linux Security (Shawn Willden)
Re: NSA and Linux Security ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Rich W. <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Sun, 14 Jan 2001 17:27:05 -0500
The voices in my head tell me that
In article <93t4ch$7d5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Rich W. wrote:
> > Yes, be naive and say it can never happen here.
>
> Actually, it already has happened here, to a limited extent.
> SHAMROCK, MINARET, Watergate, and all that.
> Read "The Puzzle Palace."
I read it. I'm on your side here.
> Read <http://www.wired.com/news/politics/0,1283,33026-2,00.html>.
> Read <http://www.time.com/time/digital/daily/0,2822,12609,00.html>.
> (Some of these are about the NSA, some about the FBI. The point is
> the same. If you think this couldn't possibly ever happen, think again.)
>
> Legal procedures may be different now, but the general
> reason for concern remains much the same, as far as I can see.
Agreed.
Rich...
------------------------------
From: Rich W. <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Sun, 14 Jan 2001 17:29:06 -0500
The voices in my head tell me that
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> > Yes, but you're being naive in thinking that a person can have sole
> > control over these systems regardless of the structures built into the
> > agencies. Do you believe the presidents/PMs have total control of
> > governmental actions? Rubbish.
>
> I suppose that the truth of your sentence, when applied
> to any country, is conditioned on its status of democracy,
> which, BTW, might vary with time, as history shows.
Exactly.
Who said we aren't going to get someone who's a little more ruthless
and grabs some power?
Have you learned nothing from history? I'm afraid I find you to be
more than frightening, and more than naive.
Rich...
------------------------------
From: "Arnold Shore" <[EMAIL PROTECTED]>
Subject: Re: storing private keys
Date: Sun, 14 Jan 2001 17:52:27 -0500
Do you really mean exactly what you say, "secure storage of private keys "?
FYI, I'm storing public keys on my server - the private key being a hash of
the userID and password, with the public key derived from that.
Arnold Shore
Annapolis, MD USA
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Failure discovered! (was Re: Security proof)
Date: Sun, 14 Jan 2001 23:06:17 GMT
Sorry for the misleading subject line, David, but *you* didn't quite
discover a failure, but your post DID make me think of something which
led me to see a way in which the structure fails to be an SPRP.
David Wagner wrote:
>
> Benjamin Goldberg wrote:
> > (t0, t1) = M(K0)(p0, p1)
> > (t2, t3) = M(K1)(p2, p3)
> > (t4, t5) = M(K2)(p4, p5)
> > (t6, t7) = M(K3)(p6, p7)
> >
> > (u0, u2) = M(K4)(t0, t2)
> > (u1, u3) = M(K5)(t1, t3)
> > (u4, u6) = M(K6)(t4, t6)
> > (u5, u7) = M(K7)(t5, t7)
> >
> > (c0, c4) = M(K8)(u0, u4)
> > (c1, c5) = M(K9)(u1, u5)
> > (c2, c6) = M(KA)(u2, u6)
> > (c3, c7) = M(KB)(u3, u7)
> [Note: I changed your notation slightly.]
>
> That's not a SPRP, either.
> Let c0,..,c7 be the encryption of an arbitrary plaintext p0,..,p7.
> Let c0',..,c7' be the encryption of a plaintext p0,..,p6,p7' differing
> from the first plaintext only in the last word.
Right. Changing p7 changes t6..7, and u4..u7, and c0..c7. The complete
ciphertext changes if any one input word is changed.
> Now, consider the decryption of the ciphertext
> c0,c1',c2,c3',c4,c5',c6,c7'.
This deciphers to
(u0 , u4 ) = M(K8)^-1(c0 , c4 )
(u1', u5') = M(K9)^-1(c1', c5')
(u2 , u6 ) = M(KA)^-1(c2 , c6 )
(u3', u7') = M(KB)^-1(c3', c7')
(t0 , t2 ) = M(K4)^-1(u0 , u2 )
(t1', t3') = M(K5)^-1(u1', u3')
(t4 , t6 ) = M(K6)^-1(u4 , u6 )
(t5', t7') = M(K7)^-1(u5', u7')
(p0'', p1'') = M(K0)^-1(t0, t1')
(p2'', p3'') = M(K1)^-1(t2, t3')
(p4'', p5'') = M(K2)^-1(t4, t5')
(p6'', p7'') = M(K3)^-1(t6, t7')
> This third plaintext will have the form p0,..,p5,?,?.
How do you figure that? You can't get p0 from deciphering t0 and t1',
only from deciphering t0 and t1.
> Since for a real SPRP we would not be able to predict anything about
> the third plaintext, your construction must not be a SPRP.
Actually... I see a weakness for a reason entirely different from the
one you suggest.
Assume the words are 8 bits each. If the cipher complies with SAC, an
input difference in plaintext p7 SHOULD cause c0..c7 to each have a
nonzero output difference with probability 255/256.
Actually, though, if you change one input word, the chance any
particular output word not changing is (1/256) + (1/256)(255/256) +
(1/256)(255/256)(255/256), when SAC requires that it be (1/256). Since
the cipher fails SAC, it's not a SPRP.
Note that the failure is worse with smaller words -- if each word is 2
bits, the chance of any particular output word not changing is 37/64,
when SAC requires 1/4. If each word is 1 bit, the chance of a
particular word not changing is 7/8, when SAC requires 1/2.
The problem also becomes worse if a larger FFT structure is used.
Considering how Luby-Rackoff constructs fail if too few rounds are used,
I shouldn't be dissapointed that only one round of my construct fails,
too.
The question of course now becomes, how do I fix it? I think that if
two rounds are used, and 24 independent keys, the difference from SAC
will be smaller than the number of possible texts.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: "Ben Hopson" <[EMAIL PROTECTED]>
Subject: Re: The Word Problem and Group Isomorphism
Date: Sun, 14 Jan 2001 23:09:17 -0000
> It has not been obvious that
> using a semigroup gives us any advantage over using a group,
> Do we know anything about the class of semigroups whose elements are not
> representable by nonsingular matrices? (does that question make proper
sense?)
> (and where would I go to learn more about such things?)
I am still just at the reading stage but Boolean Semigroups are a huge
class...
(semigroups defined by matrices with binary entries) and are especially
quick to work with, I think.
I think that Simms' book has a huge amount in it.
> As David Wagner pointed out, the fact that decryption must terminate (in
> polynomial time), combined with the finite length of the ciphertext and
finite
> length of the key, means that the "brute forcing problem" is guaranteed to
be
> decidable.
Yes. I see. I think that the kinds of monoids that could be constructed
using relations as a key are decidable anyway. The idea of using semigroups
was more to frustrate a brute force attack by the large number of available
semigroups.
> After that, you have the fun task of justifying that the
> instances you can generate are actually hard - as you've noted, heuristic
means
> seem to work "often." That can be embarassing for a cryptosystem.
Sure! It would be really hard to ensure that a partial decode isn't possible
using a factor or extension of the correct group.
Thanks,
Ben
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Security proof
Date: Sun, 14 Jan 2001 23:20:41 GMT
David Wagner wrote:
>
> Benjamin Goldberg wrote:
> >Notation:
> >Let M be a SPRP, and M(K) is a particular 2N bit permutation.
> >Let a, b, c, d each be 1/4 of the 4N bit plaintext.
> >Let w, x, y, z each be an N bit temp variable
> >Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
> >
> >The reduced size cipher is as follows:
> >(w, x) = M(K0)(a, b)
> >(y, z) = M(K1)(c, d)
> >(e, f) = M(K2)(w, y)
> >(g, h) = M(K3)(x, z)
> >
> >How do I go about proving that this construct is also an SPRP?
>
> You don't -- it's not a SPRP. :-)
>
> Choose a,b,c,d,c',d' arbitrarily, where (c,d) != (c',d').
> Let (e,f,g,h) be the encryption of the plaintext (a,b,c,d).
> Let (e',f',g',h') be the encryption of the plaintext (a,b,c',d').
> Finally, obtain the decryption of (e,f,g',h').
Let's see...
(x', z') = M(K3)^-1(g', h')
(w , y ) = M(K2)^-1(e , f )
(c'',d'') = M(K1)^-1(y, z')
(a'',b'') = M(K0)^-1(w, x')
> Note that for your cipher, this third plaintext will be of the form
> (a,b,?,?), where ? represents an unknown word.
Sorry, you can't obtain (a, b) from (w, x'). You can only obtain (a, b)
from (w, x).
> For a true SPRP, you wouldn't be able to predict anything about
> the third plaintext. Hence, your construction is not a SPRP.
The construction isn't an SPRP, but for other reasons than what you
said. With only two layers, a MITM attack is possible on it. Since an
SPRP should not be vulnerable to chosen plaintext and ciphertext
attacks, it's not an SPRP. Also, as I said in another message, there's
a bias in the output against changing. If word a changes, the chance of
(for example) word e changing, is ((2^N-1)/2^N)^2, when it should be
exactly ((2^N-1)/2^N). Input differences change outputs less often than
they should. Thus, the construct fails SAC, and fails to be an SPRP.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Security proof
Date: 15 Jan 2001 00:04:32 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>Notation:
>Let M be a SPRP, and M(K) is a particular 2N bit permutation.
>Let a, b, c, d each be 1/4 of the 4N bit plaintext.
>Let w, x, y, z each be an N bit temp variable
>Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
>
>The reduced size cipher is as follows:
>(w, x) = M(K0)(a, b)
>(y, z) = M(K1)(c, d)
>(e, f) = M(K2)(w, y)
>(g, h) = M(K3)(x, z)
>
>How do I go about proving that this construct is also an SPRP?
You're right. My previous post was in error.
Here's a correction. Let's see if I get it right this time.
Choose a,b,c,d,d' arbitrarily, where d != d'.
Let (e,f,g,h) be the encryption of the plaintext (a,b,c,d).
Let (e',f',g',h') be the encryption of the plaintext (a,b,c,d').
Finally, obtain the decryption (a'',b'',c'',d'') of (e,f,g',h').
I claim that we will have a''=a, b''=b, hence this is not a SPRP.
Proof: Using the natural notation [variables have 0, 1, or 2
primes appended according to whether they represent the 1st, 2nd,
or 3rd encryption], calculate:
(w',x') = M(a,b) = (w,x).
(w'',y'') = M^{-1}(e,f) = (w,y).
(x'',z'') = M^{-1}(g',h') = (x',z') = (x,z').
(a'',b'') = M^{-1}(w'',x'') = M^{-1}(w,x) = (a,b).
This is the desired result.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Failure discovered! (was Re: Security proof)
Date: 15 Jan 2001 00:12:24 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
In contrast to the previous one,
I believe _this_ attack is correct. (I think.)
Because I was too lazy to type everything up, I left out
some of explanations of why the attack works, but
I'll explain the one you asked about.
You noted that (p0'', p1'') = M(K0)^-1(t0, t1'),
but couldn't see why this should have any relation to (p0,p1).
You were almost there: The only missing step is to observe that
t1' = t1 (because changing p7 doesn't affect t1), hence we have
(p0'', p1'') = M(K0)^-1(t0, t1') = M(K0)^{-1}(t0, t1) = (p0, p1).
I've included the relevant parts of your post below, to help
establish context. I hope this answers all of your questions.
Benjamin Goldberg wrote:
>David Wagner wrote:
>> Benjamin Goldberg wrote:
>> > (t0, t1) = M(K0)(p0, p1)
>> > (t2, t3) = M(K1)(p2, p3)
>> > (t4, t5) = M(K2)(p4, p5)
>> > (t6, t7) = M(K3)(p6, p7)
>> >
>> > (u0, u2) = M(K4)(t0, t2)
>> > (u1, u3) = M(K5)(t1, t3)
>> > (u4, u6) = M(K6)(t4, t6)
>> > (u5, u7) = M(K7)(t5, t7)
>> >
>> > (c0, c4) = M(K8)(u0, u4)
>> > (c1, c5) = M(K9)(u1, u5)
>> > (c2, c6) = M(KA)(u2, u6)
>> > (c3, c7) = M(KB)(u3, u7)
>> [Note: I changed your notation slightly.]
>>
>> That's not a SPRP, either.
>> Let c0,..,c7 be the encryption of an arbitrary plaintext p0,..,p7.
>> Let c0',..,c7' be the encryption of a plaintext p0,..,p6,p7' differing
>> from the first plaintext only in the last word.
>
>Right. Changing p7 changes t6..7, and u4..u7, and c0..c7. The complete
>ciphertext changes if any one input word is changed.
>
>> Now, consider the decryption of the ciphertext
>> c0,c1',c2,c3',c4,c5',c6,c7'.
>
>This deciphers to
> (u0 , u4 ) = M(K8)^-1(c0 , c4 )
> (u1', u5') = M(K9)^-1(c1', c5')
> (u2 , u6 ) = M(KA)^-1(c2 , c6 )
> (u3', u7') = M(KB)^-1(c3', c7')
>
> (t0 , t2 ) = M(K4)^-1(u0 , u2 )
> (t1', t3') = M(K5)^-1(u1', u3')
> (t4 , t6 ) = M(K6)^-1(u4 , u6 )
> (t5', t7') = M(K7)^-1(u5', u7')
>
> (p0'', p1'') = M(K0)^-1(t0, t1')
> (p2'', p3'') = M(K1)^-1(t2, t3')
> (p4'', p5'') = M(K2)^-1(t4, t5')
> (p6'', p7'') = M(K3)^-1(t6, t7')
>
>> This third plaintext will have the form p0,..,p5,?,?.
>
>How do you figure that? You can't get p0 from deciphering t0 and t1',
>only from deciphering t0 and t1.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: fun with solitaire
Date: Sun, 14 Jan 2001 17:20:19 -0800
The stream generator of the Solitaire encryption
algorithm generates a stream of letters that are
completely determined by the starting sequence
of a deck of 54 cards.
Is it possible to find a starting sequence that
will cause the Solitaire letter stream to begin
with "HELLOEARTHLINGS...", or perhaps
"THISISTHENSA..."? ;o)
--r.e.s.
------------------------------
From: Mutt <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 03:40:06 GMT
On Sun, 14 Jan 2001 17:20:19 -0800, "r.e.s." <[EMAIL PROTECTED]>
wrote:
>Is it possible to find a starting sequence that
>will cause the Solitaire letter stream to begin
>with "HELLOEARTHLINGS...", or perhaps
>"THISISTHENSA..."? ;o)
It would be a scary thing to discover. What key would you need to have
for it, I wonder... FORTYTWO? THEGENERAL? MORRIS? Maybe Schneier and
Stephenson know something we don't? ;)
Seriously, though - I don't see why you couldn't potentially end up
with a keystream beginning with English words, but I'd say the
probability of it turning up would be extremely low. Probably like
1000 monkeys typing to eventually get a Shakespearean sonnet. Or a
picture in a cloud - order within apparent chaos, given a long enough
keystream?
I've only just started playing with the Solitaire cipher myself, using
both the shuffled cards and key (bridge ordered) methods. It's very
neat, I must say.
Now I'm off to play with the Perl and Palm versions from Counterpane's
website...
Regards,
--
Mutt - [EMAIL PROTECTED]
Remove 15 from my address to reply.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Sun, 14 Jan 2001 20:31:39 -0800
"Mutt" <[EMAIL PROTECTED]> wrote ...
| "r.e.s." <[EMAIL PROTECTED]> wrote:
|
| >Is it possible to find a starting sequence that
| >will cause the Solitaire letter stream to begin
| >with "HELLOEARTHLINGS...", or perhaps
| >"THISISTHENSA..."? ;o)
[...]
| I don't see why you couldn't potentially end up
| with a keystream beginning with English words,
| but I'd say the
| probability of it turning up would be extremely low.
[...]
My question is how (if it's possible) to *tailor* the
sequence so that the Solitaire procedure will produce
some desired sequence of letters in the output stream.
Suppose we have the deck in some reference sequence.
Call this D(0). I think it's clear that we can, with
some effort, study the algorithm enough to see how to
rearrange very few cards so that any desired letter is
first in the stream. Call the rearranged deck D(1).
It seems likely to me that we can now find another few
cards to rearrange to produce a desired second letter,
and still preserve the desired first letter. Call the
deck after this second rearrangement D(2). I expect
that the effort needed to find a sequence of "initial-
segment preserving" rearrangements to increase as we
proceed D(0)->D(1)->D(2)->etc, and at some point would
become impossible in principle (regardless of effort).
So there seem to be two questions: One is how long
this chain of rearrangements can be in principle, and
the is how long it can be in actual practice.
--r.e.s.
------------------------------
From: Richard John Cavell <[EMAIL PROTECTED]>
Subject: Re: Cavell Challenge #1
Date: Mon, 15 Jan 2001 16:54:39 +1100
Excellent. I shall post Challenge #2 in rec.puzzles. I might just note
that you didn't rotate the ciphertext 'r' in your plaintext. I actually
used the letter Z to represent spaces, and two Zs to represent a full
stop.
> This cipher is made by rotating the alphabet eight letters Julius Caesar
> invented it I have used the letter R to represent spaces see if you can
> decode this message
=============================================================
Richard Cavell - [EMAIL PROTECTED]
Newsgroups - Please keep any discussion on the group, and copy your
replies to me via email. (Server problems). Sending me bulk email
guarantees a nasty response.
Judge Thomas Penfield Jackson on Bill Gates: "He has a Napoleonic concept
of himself and his company, an arrogance that derives from power"
=============================================================
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cavell Challenge #1
Date: Sun, 14 Jan 2001 22:17:16 -0800
Richard John Cavell wrote:
>
> Excellent. I shall post Challenge #2 in rec.puzzles. I might just note
> that you didn't rotate the ciphertext 'r' in your plaintext. I actually
> used the letter Z to represent spaces, and two Zs to represent a full
> stop.
>
> > This cipher is made by rotating the alphabet eight letters Julius Caesar
> > invented it I have used the letter R to represent spaces see if you can
> > decode this message
>
Damn, what a typo! Yes, R = Z in your cipher's key. In my excitement I
wrote down the feature I kept thinking about - the Rs.
Sheepish grins aren't visible 'cross the network, are they?
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Sun, 14 Jan 2001 23:27:04 -0700
David Wagner wrote:
> Establish a clear policy that giving intelligence to US companies
> is forbidden, even indirectly (e.g., through a White House agency),
So, would this policy mean that the NSA wasn't allowed to give intelligence
that might be commercially valuable to the White House? Or would it mean
that the White House is constrained in what they can say to companies?
> Communicate this policy clearly to all NSA employees.
It seems to me that you'd have to communicate it to all government
employees who might be the recipients of intel.
I'm actually not so certain that we should stop the NSA from assisting U.S.
corporations in this manner, as long as the information is fairly
distributed to all the relevant U.S. corps (how to do that might be a
problem). Yes, it gives the U.S. corps an "unfair" advantage, but heck,
they pay for it, and it's not as though the U.S. is the only country that
does it. In fact, unless there is some sort of international treaty
forbidding the practice of using intelligence services to assist
corporations, it might be foolish to abstain from the practice, even if it
feels unethical. Other countries may get very upset about it, which is
perfectly understandable, and so they should take the issue to the UN and
the WTO and set about trying to stop all countries from doing it. Absent
that sort of international agreement, however, commercial spying to
strengthen the U.S. position in international commerce seems like a
reasonable function of the NSA to me.
Gathering intelligence data on U.S. citizens via exchange agreements with
other countries (UKUSA), however, is a violation of their legal charter as
far as I understand it. So, if they're doing that then we need to overhaul
our oversight structure and we need to roll some heads.
Shawn.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Mon, 15 Jan 2001 07:13:21 GMT
David Wagner wrote:
> [1] Let me give, by way of example, some "responses" to Echelon
> allegations, ...
The basic problem is that there is *no* good way
to respond to baseless allegations, other than to
simply deny them and move on. Where there is no
credible evidence, there are no grounds for making
allegations in the first place. Thus, the burden
of proof must be placed on the *alleger*, not on
the target of the allegation. To pretend
otherwise would merely invite an avalanche of
additional harmful, time-wasting groundless
allegations, since there would be no cost to those
who make false accusations.
Strong claims require strong evidence to support
them. In the case of this so-called "Echelon"
claim, the evidence offered up is puny in the
extreme.
------------------------------
** 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
******************************
