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

[Sam Mason]

On Wed, Apr 01, 2009 at 04:08:09PM -0700, Bill Frantz wrote:
> sam at samason.me.uk (Sam Mason) on Wednesday, April 1, 2009 wrote:
> >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.)

Garg; not sure what I was thinking.  As David said I should have said
"average case" and not "asymptotic" complexity.  I have a feeling I've
always had the two being synonymous, not sure where I've picked that up
from!

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

Yes, some sort of linked list is very obvious.  I think my head was
broken last night.

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

Wouldn't it be as large as the highest currently allocated client's
index, or is my head still broken?

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

Yes, all nice as well.

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