[cap-talk] use of hashcodes?

[David Wagner]

David Barbour  wrote:
>On Mon, Feb 22, 2010 at 12:15 PM, David Wagner <daw at cs.berkeley.edu> wrote:
>> If you want to talk about concrete attacks, that's probably easier to
>> do in the context of a specific counterproposal for what you would use
>> in place of SHA256-HMAC.
>
>Sure. Consider a webserver that implements this in the most
>straightforward way possible:
>
>* ETag numbers are simple increments on an integer. Andy the Attacker
>can totally guess and influence them.
>
>* The server keeps a fixed-size hashtable of ETags, without any other
>information.
>
>* If a user requests Get with an ETag, and the ETag is in the table,
>then the 304 is returned. For all other requests, a new ETag is
>created and the full Get is applied.
>
>* When the server receives a Post, the hashtable of ETags is cleared
>before taking action.
>
>Now, this will likely perform worse and less reliably than the
>SHA256-HMAC approach, especially under concurrency and mirroring
>conditions or a high 'POST' load. But this isn't a serious attempt at
>an alternative.
>
>This relevant question: how does it compare security-wise?

I can't see any security problems with it.

(Trivia: there's a potential for algorithmic complexity
denial-of-service attacks if you use a hashtable that degrades
poorly in the presence of collisions, together with a hash
table that is not cryptographically collision-resistant.
But that's a minor issue and separate from the kind of thing
we've been discussing.)

You've convinced me that there are non-cryptographic solutions
that could be used.  However the cryptographic solutions probably
have advantages that are hard to achieve without cryptography
(or at least a 2-universal hash function).

>I suspect it would be more secure than the SHA256-HMAC design, if only
>because there's no risk of collisions.

I would expect that the security increase is probably negligible
(because I expect that the risk of collisions is negligible, in the
grand scheme of things) -- but I can't prove it.