[cap-talk] solve CSRF by making references unforgeable, not unshareable

[Sam Mason]

On Mon, Mar 30, 2009 at 06:52:43PM -0700, Bill Frantz wrote:
> David-Sarah Hopwood on Thursday, March 26, 2009 wrote:
> >Encrypted capabilities work by being sparse (if they were only encrypted
> >but not sparse, then it would be possible to forge a random but valid
> >capability).
> 
> If the representation of a capability includes a dense index to the
> referenced object, and a MAC for the index, then the server can use
> indexing rather than lookup to locate the object. (Lookup would probably
> use a data structure such as a hash table or RBtree.)
> 
> Of course, checking the MAC would be more expensive than the lookup for
> small number of objects. For large numbers of objects, the MAC would win.
> Calculating the number of objects where the two techniques are equally
> costly is left as an exercise for the reader. :-)

I thought that hash tables have asymptotic complexity of O(1) the same
as a lookup table.  Admittedly the constant is a bit higher, but I'm not
sure what you'd gain by having any sort of dense index here.

> In practice, the representation would also contain an "allocation count" to
> permit reuse of indexes.

Sorry if I'm being slow, but what's the purpose of this "allocation
count"?

-- 
  Sam  http://samason.me.uk/