ciphers with keys modifying control flow?

[Jerry Leichter]

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 majordomo at metzdowd.com