[cap-talk] use of hashcodes?

[David Wagner]

David Barbour  wrote:
>I'm not fond of signatures / hash based security, for a few reasons:
>
>Read http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/
> 
>[that] document was enough to make me question the viability of
>hashes as a security mechanism.

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?

Of course SHA256-HMAC could get broken too -- but I say that the chances
of that are far less than the chances that your software has some bug or
other security vulnerability.

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.

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

$ openssl speed sha256     
Doing sha256 for 3s on 16 size blocks: 7481981 sha256's in 2.99s
Doing sha256 for 3s on 64 size blocks: 4083543 sha256's in 3.00s
Doing sha256 for 3s on 256 size blocks: 1737188 sha256's in 3.00s
Doing sha256 for 3s on 1024 size blocks: 530990 sha256's in 3.00s
Doing sha256 for 3s on 8192 size blocks: 70692 sha256's in 3.00s
OpenSSL 1.0.0-fips-beta4 10 Nov 2009
[...]
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
sha256           40037.36k    87115.58k   148240.04k   181244.59k 193036.29k

We're talking about speeds in the range of 80-200 MB/s.  That's fast,
probably far faster than the network connection that Waterken will be
hooked up to.  I doubt that SHA256-HMAC is the performance bottleneck
in Waterken (though if you think it is, the best way to tell for sure
is to conduct careful performance measurements and share the results).

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.

>The relevant semantics for asymmetric hashes are captured by
>Stamp/Verify pairs, with the semantics that for arbitrary message M,
>Verify(M,Stamp(M)) is True.
>* 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.
>* Note that one does NOT promise that M1 != M2 implies
>Verify(M1,Stamp(M2)) is False. However, a secure Stamp makes it
>cryptographically expensive to produce such collisions.
>* Use of hashes allows Stamp(M) to be much smaller than M.

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).
There's nothing undefined about it.  SHA256-HMAC is a deterministic
function.  While your comments may be valid for generic integrity
algorithms (e.g., INT-PTXT or INT-CTXT), they're not relevant to
SHA256-HMAC.

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

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.