[chord] authentication modifications?

[Michael Walfish]

Hello chord-dev at pdos and chord at pdos,

I am wondering whether it would be possible to implement some changes,
described below, in the dhash code base. I have implemented similar
changes in a couple of earlier versions of the code, and, since
Chord/dhash frequently change, I'm hoping you could apply a patch I will
send so that, in the future, these changes will simply be part of the
Chord/dhash code base.

I am aware that, in all software projects, additions beget complexity; my
arguments in favor of having these modifications be part of the code base
are: a) dhash might want to support, within reason, a variety of
applications that can take advantage of its properties b) these changes
would enhance the functionality offered by dhash in general c) there would
be fewer questions from me and d) I will submit the patch and, if
necessary, maintain it.

I have exchanged e-mails with Emil and James and have spoken with James
(they were both quite helpful, thanks!), and they suggested I write to the
mailing lists, which I am now doing. Perhaps other users of Chord would
find these proposed enhancements useful.

Our application uses the dhashclient interface, and it has the following
characteristics/requirements:

a) our application uses chordIDs as references and so when the block
associated with a particular chordID changes, our references shouldn't
change. this of course rules out DHASH_CONTENTHASH blocks

b) we desire self-certifying blocks, but creating a new public key for each
reference is probably too expensive for us (and it's unnatural in the
context of our application), so this rules out DHASH_KEYHASH blocks in
their current form

c) for several reasons (including convenience and generality of
architecture), we do not want to enforce authentication of blocks (for
example, when we test, it's sometimes useful to have static references and
to avoid using keys). 

Taken together, I believe these requirements would be satisfied by the
following set of changes:

I. To address a) and b), there are two options. I believe option A would be
easier to implement and maintain but option B would be more general:

   A. we create a block type called DHASH_KEYHASH_2 (or just piggyback on
   the current DHASH_KEYHASH). For these blocks, the chordID must equal
   SHA-1(Pubkey, Nonce), where Nonce is any 32 byte quantity, supplied by
   the user. When the user interacts with the dhashclient, he will supply a
   chordID, pubkey, sig, nonce, version, payload, payloadlen where:

      chordID = SHA-1(Pubkey, Nonce)
      sig = SIGN(payload, nonce)
      nonce = user-supplied 32 byte number
      and
      version, pubkey, payload, and payloadlen have the same semantics as
      they currently do

   Note that these blocks are still self-certifying: an adversary cannot
   "fake" a block since the payload is signed with the public key that
   generated the ChordID. James asked what happens if an adversarial dhash
   node switches two (payload,sig) pairs and keeps the (pubkey,nonce,tag)
   triplet fixed.  The protection against this attack is that the nonce and
   payload are signed together.

   Note that this block type is essentially another flavor of
   DHASH_KEYHASH: it permits one key to self-certifiably authenticate any
   number of blocks.  I believe the changes required are: i) passing the
   nonce around through the RPCs and the call stack ii) storing the nonce
   inside the backing store and iii) a small change to the verify() code.
   Note, also, that for convenience and to minimize duplicated code, it
   might make sense to put this other block type inside the same DB used
   for standard DHASH_KEYHASH blocks. 

   B.  An equally useful scheme for our application is to permit a block
   type in which: the dhashclient user chooses the ChordID, public key, and
   payload independently of each other and then signs the payload with the
   public key.  Then, dhash ensures that future modifications to the block
   are signed with the originally-supplied public key. Like KEYHASH blocks,
   fragmentation and erasure coding again do not happen for this block
   type.  
   
   This scheme is actually more general than the one in A.; (in fact, A. is
   a special case of B.) In order for it to be useful for us, we'd need the
   stored signature and public key (which dhashclient has anyway) passed
   back to our application on a lookup(). The reason is that we need to
   ensure that sig = SIGN(payload,nonce) and chordID = SHA1(pubkey,nonce).
   As James pointed out, this block type is not self-certifying, and so you
   might not want to support it. (My application would do the certification
   by checking signatures and nonces; other applications could do
   likewise.)

II. To address c), the ability to insert NOAUTH blocks could perhaps be
exposed via the dhashclient interface. Currently, users of the dhashclient
interface can only create DHASH_KEYHASH and DHASH_CONTENTHASH blocks, but
the server side of the dhash_program_1 RPC interface makes it perfectly
legal to insert DHASH_NOAUTH blocks.

My request would be to make this interface explicit and convenient. If the
developers are not amenable to this, I will maintain this change as a
separate patch. It's of course not a lot of code: a few lines in
dhashclient.C plus a bit of factoring out common code. And maybe changing
the names of the overloaded dhashclient::insert() functions to, for
example, insert_keyhash(), insert_contenthash(), insert_noauth(),
insert_keyhash_2(), etc. 

I'm curious what people think, particularly about A. vs. B., above. As I
wrote, I'm making these changes anyway since my application requires them;
my hope is to have them be part of the code base where they could be
useful to others or, at least, maintained.

Many thanks,
Mike