[Cryptography] [Crypto-practicum] Faster hashing with twisted computation graphs

[Ray Dillinger]

Coming back to Bill Cox's "twisted hashes."

I got the basic algorithm for generating N-cycle graphs of degree 4.
(graphs in which every node is connected to four edges, and there are
no cycles of length greater than N).  An Euler path in such a graph
creates a twist sequence of the nodes.

So the "twisted hash" construction means taking a twist sequence and
visiting blocks of a plaintext in that order - meaning you visit each
block twice, but the sequence in which you visit blocks makes
block-based attacks on the hash effectively impossible because no blocks
that are adjacent, or near neighbors, in the first visit, are also
adjacent, or near neighbors, in the second visit.

I think I've figured out how to make a block cipher with an arbitrary
block size, using the Feistel cipher construction on a twist sequence in
the same way the twisted hash uses it on text blocks.

However, twist sequences have a very definite set of sizes. The 4-cycle
graph has 8 nodes, the 6-cycle graph has 26 nodes, the 8-cycle graph has
80 nodes, the 10-cycle graph has 136 nodes, etc.  If I start with
a fixed block size and my twist sequence is on a number of nodes that
doesn't match the number of blocks I'm working with, then mapping each
element of the twist sequence to a block isn't exactly how to do it.

I can get to an arbitrary block size by taking the N-cycle graph,
finding a set of nodes that are maximally separated (N-1 edges apart)
and not mapping those nodes to text blocks.  Thus I can produce, say, a
twist sequence on 20 nodes by figuring out which 6 nodes of the 6-cycle
graph to not map to blocks, and still guarantee no cycles shorter than 5.

Perhaps I shall monkey together an implementation, with test vectors and
so on.  First, does anyone see a problem with this?  Second, is anybody
who understands it well enough to say anything fairly confident of the
absence of problems?

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160330/048ad02d/attachment.sig>