review of Projects/replay_cache_collision_avoidance, ending Jan. 12

[Jeffrey Hutzelman]

--On Tuesday, December 30, 2008 05:32:08 PM -0500 ghudson at mit.edu wrote:

> 1. Supporting multiple algorithm identifiers is not simple.  With a
> fixed hash algorithm, you can hash a received authenticator once, use
> it to check each record, and (if the authenticator is accepted) use
> the same hash value to write out a new record.  With multiple
> algorithms, the checking loop has to be prepared to re-hash the
> received authenticator for each record.  (Note that I am addressing
> the complexity cost here, not the performance cost.  The performance
> cost is negligible since in almost every practical scenario, the
> expected number of re-hashes is zero.)

If a transition were ever to actually occur, you'd have to either be ready 
to do this, or hash with multiple algorithms up front, or require that all 
entries in the replay cache use the same hash.  In the last case, a 
per-record hash algorithm ID would turn out to be superfluous.  I 
previously avoided considering that model because it would make transparent 
transition impossible; however, I can think of ways to make it feasible.

In any case, such complexity would be needed only in the future, not now, 
and is brought on by the desire to perform the transition, not by planning 
for it.  So this, alone, is not really an argument for not identifying the 
hash used for each record.


> 2. Since the hash algorithm is not security-critical in this
> application, it is vanishingly unlikely that we will ever need to
> change it.

Agree, particularly in light of Sam's additional detail.

> 3. Extensibility mechanisms, where they exist, should be general.  An
> algorithm identifier does not help us if we need to add another piece
> of information to records, or if we want to change the data string
> being hashed, both of which are much more likely than us needing to
> change the algorithm.

Agree.  In fact, now that I think about it, I can imagine ways in which a 
general extension mechanism could be used to enable transition without 
requiring storing a hash algorithm ID on every record today.

> In fact, we already have a more general
> extensibility hook: the four-byte extension magic number extension
> magic number 0x48415348 ("HASH").

I'll take your word for that.


> 4. The proposal does not define the meaning of the algorithm
> identifier, and it is easier to simply remove it than it is to define
> its meaning.

Eh.  Not that much easier, but OK.


Overall, I find the argument compelling.

-- Jeff