[cap-talk] use of hashcodes?

[David Barbour]

On Sat, Feb 20, 2010 at 11:08 PM, David Wagner <daw at cs.berkeley.edu> wrote:
> Why?  Cryptographers understand everything on that page very well, and
> still have confidence in SHA256-HMAC.  Sure, some previous hashes have
> been broken (though even MD5-HMAC is still unbroken in practice despite
> the fact that there are devastating collision attacks on MD5), but what
> does that have to do with whether SHA256-HMAC in particular is secure?

Sure, HMAC is secure. I even agreed as much in my post: "HMAC can work
even with broken hash functions."

Of course, HMAC is a symmetric authentication: anyone who can
authenticate a signature also has capability to forge one, which
prevents a number of useful distribution and delegation patterns. If
the main goal is to distribute the Stamp capability, OTOH, HMAC may be
a relatively secure mechanism for doing so. (One might use this to
allow one to prove full knowledge of a capability without actually
revealing it in an open text stream.)

>
> On that page Stefan is warning about a particular error in reasoning
> that some people have fallen for.  Fine.  So don't make that particular
> reasoning error.  I don't see how this is a valid reason to give up on
> the entire concept of hashing, MACs, and digital signatures.

It is a contributing reason - one among others.

Known forms of asymmetric hash-based authentication require signing
the hash, and are thus vulnerable to the error described in the
aforementioned document.

>
>>Second, and more importantly, I don't believe hash semantics are very
>>good for performance - [...]
>
> I would say this is a matter of empirical fact, which can be verified
> through measurement, rather than of belief.  Fact: SHA256-HMAC is fast.

Apparently you didn't bother reading the remainder of my post. How
much good does a larger Bytes/Second do you if it simply means you end
up processing more Bytes?

Unseal(Seal(M1)) can logically lift the Seal without any loss in
semantics, without any serialization, without any encryption... it can
be 'compiled out' of the system, similar to static typing. Avoiding
serialization also means one can avoid naming and introducing proxies
for capabilities - naming is a relatively expensive operation. One
can't do this optimization with hash-based authentication without
sacrificing location transparency. The semantics of
Verify(M1,HashStamp(M2)), with a local M1 and M2. You either end up
serializing+hashing M2 and M1 both and comparing the hashes in order
to preserve semantics relative to remote M1 and M2, or you sacrifice
transparency in order to lift the hash from a local M2 and compare
directly.

Additionally, use of named values can allow one, at the cost of a new
capability, to reduce encryption costs from megabytes down to just a
few hundred bytes for a secure or authenticated distribution of a
message. This feature is desirable even outside of encryption, for
such purposes as lazy production of a large SQL query, or lazy
streaming of a file, at the network layer - in particular, with the
ability to delegate the stream to another reading process. One could,
of course, do something similar for hashes, but this sort of feature
effectively defeats the relative 'absolute' speed advantage of hashes
- and does so through architecture.

>
> Moreover, caching using ETags has important performance benefits, so I'd
> expect that the net performance impact of Waterken's use of SHA256-HMAC
> for ETags is a win for performance, not a loss.

Compared to what, exactly?

>
>>* Stamp(M) is not necessarily comparable. That is, Stamp(M) ==
>>Stamp(M) is undefined and (if compared bitwise) might return false due
>>to different stamping contexts.
>
> Trying to draw analogies to programming language concepts has
> led you a bit astray here, I think.  Contrary to what you say,
> it is indeed guaranteed that
>  SHA256-HMAC(K,M) = SHA256-HMAC(K,M).

Sigh. What I said is that it is not *necessarily* comparable, and
therefore comparison is undefined: not, in general, a meaningful or
legal operation.

The equality test for hash-based authentication can be encapsulated as follows:

New_SHA256_HMAC_Signet() {
 K= NewSecureRandomBits(256*8);
 Stamp = function(M){ return HMAC(SHA256,K,M); }
 Verify  = function(M,S){ return Stamp(M)==S; }
 return (Stamp,Verify);
}

Clearly, Stamp(M)==Stamp(M) is true for this signet. But it users
never need to actually try it; they can stick with using just Stamp
and Verify.

Being 'symmetric', anyone with the implementation for the 'Verify' cap
can peek into it and create a 'Stamp' cap (though you can always force
them to serialize M,S to a trusted host for each verification, if
you're okay with relatively poor performance and disruption
tolerance).

>
>>A relevant question is: in which environments is a sealer-based
>>authentication cheaper than equivalently-secure hash-based
>>authentication?
>
> That's a different question, and it's not relevant to Waterken's ETags.
> Waterken's use of SHA256-HMAC for ETags is a very specific use case,
> one where hashing (MACing) is entirely appropriate, and where public-key
> cryptography (what you are calling "sealers") would not be.

Sure, it's relevant. The environment is the ultimate arbiter of which
use-cases are relevant. Waterken is clearly an attempt to architect an
environment for 'general purpose' usage. If you architect the
environment such that HMAC is appropriate for a particular purpose,
then it will be appropriate. Of course, from what I've read on ETags
in http://www.eecs.berkeley.edu/~daw/papers/joe-e-ndss10.pdf (section
7.1.2), I don't really see why you think HMAC is especially
appropriate. It is, perhaps, slightly more convenient than generating
a unique distributed transaction capability.

>
> The best cryptographical algorithms to use in any particular situation
> may well depend upon the specifics of the situation.  I don't think
> you'll find any one algorithm that is optimal for all scenarios.

The goal isn't to find an algorithm optimal for all scenarios. The
goal is to architect an environment that is near-optimal for most
scenarios and is capable of supporting the rest. Waterken represents
one instance of this goal, and is quite admirable for it. But Waterken
is hindered by assuming a capability-hostile environment. Most of the
work must be performed at a common Server rather than cooperatively
distributed among servers and browsers.