Joe Marshall <eval.apply@gmail.com> wrote:
+---------------
| Ray Dillinger wrote:
| > that gives the reversal, not the difficulty of *doing* the reversal.
...
| I think you are right, then.  If a function computes a permutation,
| then the repeated application of the function should generate a group
| (right?).
+---------------

Wrong, actually if I understand what all the guys over on "sci.crypt"
were talking about a few years ago when it was proved that DES is *not*
a group! [Google for "DES is not a group" and you'll get lots of hits.]

    http://en.wikipedia.org/wiki/Data_Encryption_Standard
    ...
    DES has also been proved not to be a group, or more precisely, the
    set {EK} (for all possible keys K) under functional composition is
    not a group, nor "close" to being a group (Campbell and Wiener, 1992).
    This was an open question for some time, and if it had been the case,
    it would have been possible to break DES, and multiple encryption modes
    such as Triple DES would not increase the security.

The Campbell & Wiener paper is here:

    http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/desgroup.pdf
    "DES is not a Group"
    Keith W. Campbell and Michael J. Wiener
    Bell-Northern Research
    P.O. Box 3511 Station C, Ottawa, Ontario, Canada, K1Y 4H7

    Abstract. We prove that the set of DES permutations (encryption
    and decryption for each DES key) is not closed under functional
    composition. This implies that, in general, multiple DES-encryption
    is not equivalent to single DES-encryption, and that DES is not
    susceptible to a particular known-plaintext attack which requires,
    on average, 228 steps. We also show that the size of the subgroup
    generated by the set of DES permutations is greater than 102499,
    which is too large for potential attacks on DES which would exploit
    a small subgroup.

+---------------
| Therefore, every permutation should have both a predecessor
| and successor, and if the predecessor is known it should be
| computationally no more difficult to invert the permutation
| than to compute it in the first place.
+---------------

Since the presumed premise is false, doesn't that also cast doubt
on the "Therefore"...?


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607