[tor-dev] Even more notes on relay-crypto constructions

[Robert Ransom]

On 10/9/12, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 10/8/12, Nick Mathewson <nickm at torproject.org> wrote:

>> The second category (frob, encrypt, frob) is pretty elegant IMO. The
>> best-explained of these I've seen so far are in a
>> paper by Palash Sarkar [Efficient-Tweakable], though the earlier TET
>> construction [TET] might also be cool.  For these, you need an
>> invertible block-wise (Almost) (Xor-)Universal hash function,
>> typically implemented with GF(2^128).  I'm not sure if you could use a
>> different field.
>
> Please actually *read* http://cr.yp.to/papers.html#securitywcs this
> time (read the appendix first).  If you use polynomial evaluation over
> a different field, your ‘hash function’ will have small differential
> properties with respect to addition *in that field*.  The Poly1305
> paper then proves that the polynomial-evaluation part of Poly1305 also
> has small differential properties with respect to addition in
> Z/(2^128)Z .
>
> In short, you can use a different field for polynomial evaluation *if*
> you also use a different addition operation.

Sorry -- that paper does require polynomials over a field of the same
size as a block cipher's block size (for AES, that means GF(2^128)),
and does not work with general almost-(xor-)universal hash functions.

> (If you're going to pass the result of the polynomial-evaluation
> function through a one-way function so that you can tee off some bits
> for a chaining output, you can use whatever addition operation you
> want after the OWF.)

I don't see a way to obtain a chaining output from iHCH or HOH.

>>  The multiplication operations here appear to be
>> multiplication by a primitive element, and multiplication by a per-key
>> element.  The encryption step can be realized with a somewhat
>> unorthodox counter-mode stream cipher, or a ciphertext-stealing ECB
>> approach.  I don't know what you'd need to do to substitute in an
>> orthodox stream cipher for the one used in iHCH.  Sarkar seems to see
>> iHCH as a successor to HCH, which is a little worrisome given that HCH
>> is a spiritual descendant of the patented XCB, but to me the two
>> constructions (HCH, iHCH) look practically nothing alike except for
>> their use of a counter mode step.

iHCH and HOH use a block cipher, not just a stream cipher.


Robert Ransom