Ned, back in the early days of DES I presented a paper to the IACR
concerning the expected cycle length of DES in Output Feedback Mode.
Donald Davies did a rather similar analysis, beginning with a different
set of assumptions. Although the conclusions differed slightly, the
average length of a DES cycle was absolutely huge.
Indeed it is. However, the results I was referring to were for various
different tests, including weak keys and pseudorandom next key tests. (I didn't
want to get into a discussion of weak keys and the different sorts of cycling
tests and whatnot on the PEM-DEV list; I only wanted to forestall discussion
about whether or not multi-pass DES is demonstrably better than single-pass
DES.)
If ANYONE has succeeded in finding a cycle in DES OFB (other than
that resulting from a weak or semiweak key), I would like to know
the reference.
The shortest normal cycle ever found that I know about was ~2^33, but it was
produced with a weak key. A cycle of 2^30 was produced by a pseudorandom next
key test in one case, I believe. I don't think any normal cycles for a nonweak
key have been found to be shorter than 2^36 (which is more a hardware speed
limitation than an actual determination of true cycle length, of course).
The sources I have handy are Eurocrypt 85 proceedings and Vol. 1 No. 1 of the
Journal of Cryptology. I believe I've read some more recent articles about this
but I can't put my hands on them at the moment. (A trip to the Citation Index
would be in order here, but I just don't have the time to do it.)
For my part I'd be interested if subsequent theoretical/experimental results
have managed to push up the likely lower bound on the size of the group
generated by DES. The number for this I'm aware of is 2^68. I think better
theory would be needed to push this up appreciably, but I'd be delighted to be
shown that this is incorrect or that better theory is now available in the open
literature...
Ned