home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / crypt / 2935 < prev    next >
Encoding:
Text File  |  1992-08-18  |  5.6 KB  |  122 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!daisy.learning.cs.cmu.edu!Marc.Ringuette
  3. From: Marc.Ringuette@daisy.learning.cs.cmu.edu
  4. Subject: Secure netnews
  5. Message-ID: <9208182108.AA09132@news.cis.ohio-state.edu>
  6. Sender: daemon@cis.ohio-state.edu
  7. Organization: The Ohio State University Department of Computer and Information Science
  8. Date: Tue, 18 Aug 1992 20:54:00 GMT
  9. Lines: 111
  10.  
  11. It seems like a useful thing:  a newsgroup which can guarantee that
  12. every reader receives the identical articles in the identical order.
  13. Such a newsgroup can be used as the "worldwide consensus reality" for
  14. the purposes of arbitrating disputes.  For instance, a secure newsgroup
  15. would be an excellent way to distribute public keys.  You just post to
  16. the newsgroup, and when you see it appear, you're guaranteed that
  17. everybody sees it the same way you do.
  18.  
  19. Later in the article, I sketch out how to implement a secure newsgroup
  20. on top of a few insecure usenet newsgroups.  I'm serious -- this could
  21. be a useful and interesting hack!
  22.  
  23. -----
  24.  
  25. The basic technique I propose in order to achieve this is a two-stage news
  26. distribution process, where first the news is distributed to the entire set
  27. of receiving machines, then signatures are collected from all receivers and
  28. distributed in the same way as a regular news article.  Only when signatures
  29. from at least half the newsreading machines have been received, will a
  30. receiver be assured that the article is authentic, and the article is
  31. given the next number in the sequence of accepted articles.
  32.  
  33. One of the main challenges to deal with is a "network partition" where
  34. some fraction of the distribution network is cut off from the rest.
  35. In order to guarantee consistency, the procedure must determine
  36. which partition contains a majority of machines, or it must "stall" 
  37. until contact can be regained with the rest of the network.
  38.  
  39. It is necessary to know exactly what machines are receiving news, in order to
  40. poll them about what news they have received and are willing to sign.  New
  41. machines must register themselves by posting to the newsgroup, and must agree
  42. to respond to signature requests within a reasonable window, or they will be
  43. removed from the set of participating hosts.  Any non-participating machine
  44. can still read the group; it just can't participate in the security process.
  45.  
  46. It is important that confidence be maintained that no half of the machines on
  47. the network are going to get into a cheating coalition together.
  48.  
  49. I should point out that there is no centralized server in this scheme.
  50. Individuals post articles, post signatures, and post "proofs" that a given
  51. article has been accepted or rejected by more than half the participating
  52. hosts.
  53.  
  54. -----
  55.  
  56. It might be fun to set up such a system on the Internet, using
  57. conventional newsgroups and digital signatures.  I've sketched it
  58. out like this:
  59.  
  60.    alt.secure.submitted        -- articles are posted here by anyone
  61.  
  62.    alt.secure.packages        -- lists of "alt.secure.submitted articles
  63.                    posted today" are posted here by
  64.                    participating hosts; articles seen by
  65.                    most of the hosts are included
  66.                    in a "package" to be signed.
  67.  
  68.    alt.secure.signatures    -- signatures of message packages go here.
  69.  
  70.    alt.secure.proofs        -- proofs (in the form of lists of signatures)
  71.                    that package X has been accepted or that
  72.                    no agreement will be reached in this round.
  73.                    One proof is enough, but anyone can post
  74.                    one.
  75.  
  76.    alt.secure.accepted        -- (optional) an archive of the entire
  77.                    sequence of accepted packages with proofs.
  78.  
  79. -----
  80.  
  81. Requiring the agreement of half the machines is a minimum threshold (any less
  82. and two different articles could get accepted at once), but higher thresholds
  83. are reasonable.  It may be desirable to require 90% of machines to agree on
  84. an article; if more than 10% are shown to disagree, then the article is
  85. thrown out.  You'll note that as the threshold approaches 1, denial of
  86. service is possible by a smaller and smaller clique of machines.
  87.  
  88. Similarly, as the threshold approaches .5, the "swing vote" becomes
  89. smaller and a small number of cheating machines could (in the presence
  90. of a network partition) cause two inconsistent world views to exist.
  91. A threshold of 75% seems like a good choice.
  92.  
  93. -----
  94.  
  95. Since the verification process involves a large amount of signature traffic,
  96. the method can be modified to get signatures only from a random sample of
  97. receiving machines; only when it is shown with high probability that more
  98. than X% of the network has received the correct article will it be accepted
  99. by each individual machine as correct.  Until this happens, no further
  100. articles will be processed; instead, if there is some question as to whether
  101. at least X% the network has seen the article, more and more machines will be
  102. polled until the article is accepted or it can be proved that it will never
  103. be accepted.  The philosophy is that it's better to stall than it is to allow
  104. two inconsistent versions of the world to exist.  
  105.  
  106. It's slightly tricky to determine which machines must participate in the
  107. random sample while preventing cheating coalitions.  If the sampling
  108. algorithm were predictable, small cliques of machines could arrange to be
  109. part of a sample and spoil the results.  One solution is to choose the sample
  110. based on a "joint random-number stream" agreed upon in the previous round
  111. which consists of the XOR of all contributions to it; contributions are
  112. encrypted until after the contribution deadline in order to prevent
  113. last-minute fudging of the random number stream.
  114.  
  115. -----
  116.  
  117. What do you think?  See any gaping holes?  Want to flesh it out and 
  118. give it a try?
  119.  
  120.  
  121.     --Marc Ringuette, mnr@cs.cmu.edu
  122.