Secure netnews

#801

Author: Marc.Ringuette
Date: Tue, 18 Aug 1992 20:54

111 lines
5816 bytes

It seems like a useful thing:  a newsgroup which can guarantee that
every reader receives the identical articles in the identical order.
Such a newsgroup can be used as the "worldwide consensus reality" for
the purposes of arbitrating disputes.  For instance, a secure newsgroup
would be an excellent way to distribute public keys.  You just post to
the newsgroup, and when you see it appear, you're guaranteed that
everybody sees it the same way you do.

Later in the article, I sketch out how to implement a secure newsgroup
on top of a few insecure usenet newsgroups.  I'm serious -- this could
be a useful and interesting hack!

-----

The basic technique I propose in order to achieve this is a two-stage news
distribution process, where first the news is distributed to the entire set
of receiving machines, then signatures are collected from all receivers and
distributed in the same way as a regular news article.  Only when signatures
from at least half the newsreading machines have been received, will a
receiver be assured that the article is authentic, and the article is
given the next number in the sequence of accepted articles.

One of the main challenges to deal with is a "network partition" where
some fraction of the distribution network is cut off from the rest.
In order to guarantee consistency, the procedure must determine
which partition contains a majority of machines, or it must "stall" 
until contact can be regained with the rest of the network.

It is necessary to know exactly what machines are receiving news, in order to
poll them about what news they have received and are willing to sign.  New
machines must register themselves by posting to the newsgroup, and must agree
to respond to signature requests within a reasonable window, or they will be
removed from the set of participating hosts.  Any non-participating machine
can still read the group; it just can't participate in the security process.

It is important that confidence be maintained that no half of the machines on
the network are going to get into a cheating coalition together.

I should point out that there is no centralized server in this scheme.
Individuals post articles, post signatures, and post "proofs" that a given
article has been accepted or rejected by more than half the participating
hosts.

-----

It might be fun to set up such a system on the Internet, using
conventional newsgroups and digital signatures.  I've sketched it
out like this:

   alt.secure.submitted		-- articles are posted here by anyone

   alt.secure.packages		-- lists of "alt.secure.submitted articles
				   posted today" are posted here by
				   participating hosts; articles seen by
				   most of the hosts are included
				   in a "package" to be signed.

   alt.secure.signatures	-- signatures of message packages go here.

   alt.secure.proofs		-- proofs (in the form of lists of signatures)
				   that package X has been accepted or that
				   no agreement will be reached in this round.
				   One proof is enough, but anyone can post
				   one.

   alt.secure.accepted		-- (optional) an archive of the entire
				   sequence of accepted packages with proofs.

-----

Requiring the agreement of half the machines is a minimum threshold (any less
and two different articles could get accepted at once), but higher thresholds
are reasonable.  It may be desirable to require 90% of machines to agree on
an article; if more than 10% are shown to disagree, then the article is
thrown out.  You'll note that as the threshold approaches 1, denial of
service is possible by a smaller and smaller clique of machines.

Similarly, as the threshold approaches .5, the "swing vote" becomes
smaller and a small number of cheating machines could (in the presence
of a network partition) cause two inconsistent world views to exist.
A threshold of 75% seems like a good choice.

-----

Since the verification process involves a large amount of signature traffic,
the method can be modified to get signatures only from a random sample of
receiving machines; only when it is shown with high probability that more
than X% of the network has received the correct article will it be accepted
by each individual machine as correct.  Until this happens, no further
articles will be processed; instead, if there is some question as to whether
at least X% the network has seen the article, more and more machines will be
polled until the article is accepted or it can be proved that it will never
be accepted.  The philosophy is that it's better to stall than it is to allow
two inconsistent versions of the world to exist.  

It's slightly tricky to determine which machines must participate in the
random sample while preventing cheating coalitions.  If the sampling
algorithm were predictable, small cliques of machines could arrange to be
part of a sample and spoil the results.  One solution is to choose the sample
based on a "joint random-number stream" agreed upon in the previous round
which consists of the XOR of all contributions to it; contributions are
encrypted until after the contribution deadline in order to prevent
last-minute fudging of the random number stream.

-----

What do you think?  See any gaping holes?  Want to flesh it out and 
give it a try?


    --Marc Ringuette, mnr@cs.cmu.edu

Re: Secure netnews

#820

Author: Don Alvarez
Date: Tue, 18 Aug 1992 22:15

54 lines
3091 bytes

In article <9208182108.AA09132@news.cis.ohio-state.edu> Marc.Ringuette@daisy.learning.cs.cmu.edu writes:
>
>The basic technique I propose in order to achieve this is a two-stage news
>distribution process, where first the news is distributed to the entire set
>of receiving machines, then signatures are collected from all receivers and
>distributed in the same way as a regular news article.  
>
>Machines must register themselves by posting to the newsgroup, and must agree
>to respond to signature requests within a reasonable window, or they will be
>removed from the set of participating hosts.  
>
>What do you think?  See any gaping holes?  Want to flesh it out and 
>give it a try?
>
>    --Marc Ringuette, mnr@cs.cmu.edu

Gaping holes?  *YES*

There is no central authentication server, so every subscriber must be
able to determine authentication themselves.  That means every
subscriber needs a list of the names of all of the other subscribers.

Any subscriber can fraudulently "authenticate" any posting simply by
greping through the list of subscribers and announcing "subscriber foo
received article 754", "subscriber bar received article 754", etc.

There is no way to defend against this because there is no way to prove
who sent the message stating that machine foo has received an article.

Worse, there is no way for any machine even to know that it has a complete
or accurate list of subscribers because there is no way to distribute
such a list in a trusted manner.

Providing a centralized server for doing the authentication wouldn't
help, because there is no way for it to know who is sending the
subscription messages or who is sending the receipt messages.  There
would also be no way for the individual subscribers to know who sent
the "article 754 authenticated" message.

If you had a mechanism that allowed you to prove who sent a message,
then you could solve not only the secure newsfeed problem but a whole
host of more serious problems.  Unfortunately, such a mechanism doesn't
exist.

Note that any proposed solution to the above problem which claims to
find an answer using any of the words DES, RSA, public-key encryption,
or private-key encryption is a non-solution.  Those are all encryption
techniques.  The problem here has nothing to do with encryption
techniques.  The problem here has to do with cryptographic protocols,
or more importantly with the lack thereof.  It is a fundamentally unsolved
and (I believe) unsolveable problem.  There is no way to propagate trust
across the entire network.

-don

Re: Secure netnews

#841

Author: Arthur Rubin
Date: Wed, 19 Aug 1992 16:37

56 lines
2963 bytes

In <1992Aug18.221506.13535@Princeton.EDU> dla@raven (Don Alvarez) writes:

>In article <9208182108.AA09132@news.cis.ohio-state.edu> Marc.Ringuette@daisy.learning.cs.cmu.edu writes:
>>
>>The basic technique I propose in order to achieve this is a two-stage news
>>distribution process, where first the news is distributed to the entire set
>>of receiving machines, then signatures are collected from all receivers and
>>distributed in the same way as a regular news article.  
>>
>>Machines must register themselves by posting to the newsgroup, and must agree
>>to respond to signature requests within a reasonable window, or they will be
>>removed from the set of participating hosts.  
>>
>>What do you think?  See any gaping holes?  Want to flesh it out and 
>>give it a try?
>>
>>    --Marc Ringuette, mnr@cs.cmu.edu

>Gaping holes?  *YES*

>There is no central authentication server, so every subscriber must be
>able to determine authentication themselves.  That means every
>subscriber needs a list of the names of all of the other subscribers.

>Any subscriber can fraudulently "authenticate" any posting simply by
>greping through the list of subscribers and announcing "subscriber foo
>received article 754", "subscriber bar received article 754", etc.

Actually, if the "signatures" are cryptographic, there may be a solution to that.
You have to define "subscribers" as key-holders rather than as machines,
but it seems somewhat reasonable.

...

>Worse, there is no way for any machine even to know that it has a complete
>or accurate list of subscribers because there is no way to distribute
>such a list in a trusted manner.

That's true.

>Providing a centralized server for doing the authentication wouldn't
>help, because there is no way for it to know who is sending the
>subscription messages or who is sending the receipt messages.  There
>would also be no way for the individual subscribers to know who sent
>the "article 754 authenticated" message.

That's not correct.  If you believe public key signature systems can be
secure, then a message can be posted which has the effect that "someone
with key K1 posted message M1".


--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; if you want to be sure I see a post, mail it.

Re: Secure netnews

#894

Author: Joseph F. Hull
Date: Wed, 19 Aug 1992 21:48

132 lines
6906 bytes

In <9208182108.AA09132@news.cis.ohio-state.edu>
Marc.Ringuette@daisy.learning.cs.cmu.edu writes:

> The basic technique ... is a two-stage news distribution process, where first
> the news is distributed to the entire set of receiving machines, 
> then signatures are collected from all receivers and distributed in the same
> way as a regular news article. ... when signatures from at least half the
> newsreading machines have been received, will a receiver be assured that the
> article is authentic, and the article is given the next number in the 
> sequence of accepted articles.

Please note that Marc seems to be making an assumption that I can trust my own
machine.  I think this is a reasonable assumption, but I recognize that it may
not be true in every case.

In <1992Aug18.221506.13535@Princeton.EDU>
dla@raven (Don Alvarez) writes:

+ Gaping holes?  *YES*

+ Any subscriber can fraudulently "authenticate" any posting simply by
+ greping through the list of subscribers and announcing "subscriber foo
+ received article 754", "subscriber bar received article 754", etc.

+ There is no way to defend against this because there is no way to prove
+ who sent the message stating that machine foo has received an article.

Why not use a public key encryption system to provide digital signatures?
Whether or not you agree with RSA's policies on use of their techniques, the
techniques are reasonably secure (certainly secure enough for this use,
although possibly not secure enough for financial systems).

+ Worse, there is no way for any machine even to know that it has a complete
+ or accurate list of subscribers because there is no way to distribute
+ such a list in a trusted manner.

Horsefeathers.  The same public key encryption system used for digital 
signatures, be it RSA or something else, can be used to authenticate the
contents of any message sent by a trusted machine.  Read RSA's public
documents on features of their system.

+ Providing a centralized server for doing the authentication wouldn't
+ help, because there is no way for it to know who is sending the
+ subscription messages or who is sending the receipt messages.  There
+ would also be no way for the individual subscribers to know who sent
+ the "article 754 authenticated" message.

Providing a centralized authentication server is not adequate and is not 
necessary.  The individual subscribers can authenticate the "article
received" messages using public key encryption.

+ If you had a mechanism that allowed you to prove who sent a message,
+ then you could solve not only the secure newsfeed problem but a whole
+ host of more serious problems.  Unfortunately, such a mechanism doesn't
+ exist.

Prove, as used here, is a very tricky term.  There are very involved 
discussions of just what it means going on within a large number of
interested groups, including NSA, the Federal Reserve System and the legal
community.  However, to the extent that a public key encryption system can
successfully protect the value of each and every user's private key, a
digital signature using that system may reasonably be said to "prove" that
a message came from the purported user and a digital authentication using
that system may reasonably be said to "prove" that the message received is
the message that was sent.  The threat model against which the public key
encryption system must protect includes:  compromise within the user's own
system; compromise via cryptanalytic attacks against the public key data
base; compromise via cryptanalytic attacks against authenticated messages
and digital signatures.

+ Note that any proposed solution to the above problem which claims to
+ find an answer using any of the words DES, RSA, public-key encryption,
+ or private-key encryption is a non-solution.  Those are all encryption
+ techniques.

Yes, Don, these are all encryption techniques.  But why do you assume that
encryption techniques CAN NOT be a part of a solution to the system Marc is
proposing.

+ The problem here has nothing to do with encryption
+ techniques.  The problem here has to do with cryptographic protocols,
+ or more importantly with the lack thereof.

Let's define some terms.  I suggest "cryptographic protocol" refers to those
rules by which various participants in an encryption method exchange the
information needed to encrypt and decrypt "messages."  I suggest "security 
protocol" refers to those rules by which various participants in some security
process, such as ensuring all nodes see the same news articles, exchange the 
information needed to complete the process.  Security protocols may or may not 
involve cryptographic methods.  I agree that one part of the solution to the 
system Marc is proposing is development of an appropriate security protocol.

+ It [referring back to what Don called cryptographic protocols] is a 
+ fundamentally unsolved and (I believe) unsolveable problem. 
+ There is no way to propagate trust across the entire network.

Very often, the way one states, or formulates, a problem has a lot to do with
how easy it is to solve the problem.  Some formulations lead us, more or less
directly, to a solution, while other formulations offer no assistance at all.
I agree that there is no way (I see no way) to propagate trust across the
entire network.  But why would you want to (mis)state the problem this way.
The problem, as stated by Marc (and he gets to state it anyway he wants to,
it's HIS problem), is how could we implement a news system that:
  1) lets each subscribing system determine that it is seeing "the same" 
     articles as other systems 
  2) does not let a (small) group of cooperating machines spoof the system
     into accepting un-authenticated articles.
The problem is trusted counting of messages from identifiable sources.  The
identification is provided by digital signatures.  The trusted counting is
provided by my own, I hope trusted, machine.  If my machine isn't trusted, I
have MUCH bigger problems than netnews.

-- 
	   _   _
    /_    / ) / ) Jeff Hull          hull@den.mmc.com
   //_) -/- -/-   1544 S. Vaughn Cir
/_/ \_/ /   /	  Aurora, CO 80012   303-977-1061

Re: Secure netnews

#859

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

18 lines
1311 bytes

In <9208182108.AA09132@news.cis.ohio-state.edu> Marc.Ringuette@daisy.learning.cs.cmu.edu (Marc_Ringuette) writes:

> Later in the article, I sketch out how to implement a secure newsgroup
> on top of a few insecure usenet newsgroups.  I'm serious -- this could
> be a useful and interesting hack!

I really hate when people post saying that netnews needs to be
re-written.

Tom
--
There is nothing wrong with talking to yourself...
I do it, and so do I!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+

Re: Secure netnews

#862

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

17 lines
1237 bytes

In <f1@Warren.MENTORG.COM> tal@Warren.MENTORG.COM (Tom Limoncelli) writes:

> I really hate when people post saying that netnews needs to be
> re-written.

Such posts are always followed by someone talking about how it
can't be done without breaking all old systems.

Tom
--
There is nothing wrong with talking to yourself...
I met an interesting person that way!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+

Re: Secure netnews

#865

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

17 lines
1294 bytes

In <f2@drew.drew.edu> tlimonce@drew.drew.edu (Tom Limoncelli) writes:

> Such posts are always followed by someone talking about how it
> can't be done without breaking all old systems.

This is always followed by someone who really believes that they've
figured out a way to do it.

Tom
--
There is nothing wrong with talking to yourself...
at least you know you're going to win any arguments!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+

Re: Secure netnews

#868

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

20 lines
1392 bytes

In <f3@pilot.njin.net> limonce@pilot.njin.net (Tom Limoncelli) writes:

> This is always followed by someone who really believes that they've
> figured out a way to do it.

Yeah, but then Henry or Geoff will beg them to explain their solution.
Tons of flamage will go back and forth because the explaination
won't be very well written.

Finally people will really understand the proposal.

Tom
--
There is nothing wrong with talking to yourself...
I do it, and so do I!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+

Re: Secure netnews

#870

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

16 lines
1260 bytes

In <f4@Warren.MENTORG.COM> tal@Warren.MENTORG.COM (Tom Limoncelli) writes:

> Finally people will really understand the proposal.

At which time Geoff will post a short message showing how simple it
is to subvert such a system.

Tom
--
There is nothing wrong with talking to yourself...
I met an interesting person that way!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+

Re: Secure netnews

#873

Author: Tom Limoncelli
Date: Wed, 19 Aug 1992 23:14

27 lines
1831 bytes

In <f5@drew.drew.edu> tlimonce@drew.drew.edu (Tom Limoncelli) writes:

> At which time Geoff will post a short message showing how simple it
> is to subvert such a system.

Of course, this whole process will take a week because someone will
misunderstand Geoff or how netnews works, and start posting about
how such a system actually *would* work.  This person will eventually
be proven wrong also.

All the while someone will write a script that checks various
parts of a post message to be a little more sure that the post
wasn't forged.

Of course, that just means that forgers will only need to be a bit
more careful when crafting their forgeries for them to work.  After
a few iteration of attempts, they'll have perfected their technique.

Tom
--
There is nothing wrong with talking to yourself...
at least you know you're going to win any arguments!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+