On Sep 22, 2010, at 9:34 AM, Steven Bellovin wrote:
Does anyone know of any ciphers where bits of keys modify the
control path, rather than just data operations? Yes, I know that
that's a slippery concept, since ultimately things like addition and
multiplication can be implemented with loops in the hardware or
firmware. I also suspect that it's potentially dangerous, since it
might create very hard-to-spot classes of weak keys. The closest I
can think of is SIGABA, where some of the keying controlled the
stepping of the other rotors.
This reminds me of an old, apparently-abandoned idea for producing one-
way hash functions: Choose two functions f_0 and f_1 that don't
commute. For input b_0 b_1 ... b_k, the hash is
f_b_k(f_b_k-1(...f_b_0(0)...)).
Obviously, saying the functions "don't commute" isn't enough. What
you really want is that if you consider the group generated by f_0 and
f_1, then there are no "short" non-trivial relations (or, same thing,
cycles). Also, of course, you can use more functions - e.g., use four
functions and pull off successive pairs of bits.
A variant uses the input itself as the initial value, rather than 0 -
though that limits the domain. Alternatively, you could start with
the length of the input, eliminating trivial extension attacks.
This idea goes back to the early 70's at least. There was really no
theory of how to produce or analyze one-way hash functions in those
days, but this one clearly comes from an approach to designing
encryption functions (alternating substitutions and permutations)
suggested by Shannon in his seminal work on cryptography. Shannon, in
turn, credits a theorem of Hopf's on mixing functions for the basic
idea - which is ultimately at the root of most encryption functions in
use today.
On its face, this approach has much to recommend it. It's a pure
stream computation. You can use any group for your functions.
There's a ton of theory on group presentations that might apply. (Of
course, many interesting questions about group presentations turn out
to be non-computable; not just any group will work. Given what we've
learned since the '70's, using two different representatives from a
universal class of hash functions might be an interesting starting
point.)
Anyone aware of why, back in the pre-history of one-way functions,
this design approach was abandoned? Perhaps there really are
fundamental problems with it; or perhaps it's just that the MD-style
approach was so successful that it just took over.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
