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

[Bill Frantz]

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.


>> 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"?

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.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | There are also no libertar-  | Periwinkle
(408)356-8506      | ians in financial crises.    | 16345 Englewood Ave
www.pwpconsult.com |               - Jeff Frankel | Los Gatos, CA 95032