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

[Bill Frantz]

sam at samason.me.uk (Sam Mason) on Wednesday, April 1, 2009 wrote:

>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.

All of the hash tables I have used have been designed to have more than one
entry/chain head. These tables are designed to incur an O(n) cost. Is there
an example of a real-world O(1) hash table? It would have to have a
guarantee that no chain was more than one element long. (And with that
guarantee, the link field in the elements could be eliminated.)


>> 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.

The entries for deleted entries are linked together into a free list. When
I need a new entry, I check the free list. If there is an entry on the free
list, I remove if from the free list and reuse it, incrementing the
allocation count. If there is no entry on the free list, I grow the array.
My array is only as large as the maximum number of remotely accessible
objects that have ever existed. Keeping the array from growing indefinitely
is why the allocation count is included in the design.

If the free list is kept LIFO, adding and removing entries is O(1). LIFO is
also good for cache performance, including CPU caches, dynamic paging, and
disk block caching.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | When it comes to the world     | Periwinkle
(408)356-8506      | around us, is there any choice | 16345 Englewood Ave
www.pwpconsult.com | but to explore? - Lisa Randall | Los Gatos, CA 95032