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

Eugen Leitl eugen at leitl.org
Wed Oct 10 02:24:26 EDT 2012

----- Forwarded message from Robert Ransom <rransom.8774 at gmail.com> -----

From: Robert Ransom <rransom.8774 at gmail.com>
Date: Tue, 9 Oct 2012 14:53:10 -0400
To: tor-dev at lists.torproject.org
Subject: Re: [tor-dev] Even more notes on relay-crypto constructions
Reply-To: tor-dev at lists.torproject.org

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
tor-dev mailing list
tor-dev at lists.torproject.org

----- End forwarded message -----
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE

More information about the cryptography mailing list