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

[Sam Mason]

On Tue, Mar 31, 2009 at 01:59:54PM -0700, Bill Frantz wrote:
> sam at samason.me.uk (Sam Mason) on Tuesday, March 31, 2009 wrote:
> 
> >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 this case, a hash table will use the hash of the Swiss number to select
> a chain head (simple indexing). There may be more than one object with the
> same hash, and these are linked together in a list. Traversing that list is
> O(n) where n is the number of entries on the list. One can reduce n by
> increasing the number of hash chain heads.

Yes, but surely that's why it's the "asymptotic complexity" and not
worst case analysis.

> If we are using indexes, we want to keep the array referenced by the
> indexes reasonably compact. When we delete an object, we want to ensure
> that capabilities to that object do not reference any new objects we assign
> the same index. To do this, we associate an "allocation count" with the
> index. Every time we assign an index to a new object, we increment the
> associated index. By checking that the allocation count in a capability
> matches the allocation count associated with the index, we can prevent old
> capabilities from accessing newer objects.

OK, so how do you decide a new object's index?  It sounds as though
you've just traded an O(1) insert, lookup and delete algorithm (the hash
table) for one with O(1) lookup (and maybe delete) and worse performance
for insert (and probably delete).  Also I can't see how you'd stop your
array from growing indefinitely.

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