Re: 3-instruction one-way function. Invitation

From: Francois Grieu (fgrieu_at_micronet.fr)
Date: 08/22/03 

Date: Fri, 22 Aug 2003 21:53:42 +0200

In article <c8016437.0308220613.3ed9485d@posting.google.com>,
 tomstdenis@yahoo.com (Tom St Denis) wrote:

> He used the VMPC in a modified RC4 to make a stream cipher.

Very right. Similarities with RC4 abound:
 - an hidden state P[] that is a 256 bytes permutation,
   plus one extra byte
 - swapping of entries of the permutation, one of which is
   at an incremental index, the other at a computed index.

Actually it is easier to state the main difference with RC4:
output goes thru permutation VMPC(P) instead of just
thru P. The stated design rationale for this is to guard
against partial attacks [1] against RC4 (see also [2])
that aim at recovering the state by observing the output.
With VMPC hard to invert, this seems better than no
countermeasure at all.
Note: the stated attacks are near practical; which depending
on point of view means impractical or dangerous.
Note: the first step in the VMPC composition also serves
as a step in the state schedule; on one hand this can be
used to speed up the computation, but on the other hand it
sorts of "opens the VMPC black box", which goes against
the rationale.

There is (reportedly) another small change to the scheduling
algorithm, aimed at guarding against another attack path [3].
Note: I do not understand why it should be necessary to guard
against this attack, which "can't happen", and fear
that any schedule change could actually worsen a time-proven
schedule.

> Second the VMPC function is a static function of a 256
> element permutation.

More precisely: a static function ON THE SET OF ALL THE
256 element permutationS. See
<http://www.VMPCfunction.com/function.htm>

> One byte in, one byte out.

This does NOT apply to "the VMPC function". It does
apply to permutations that are input and output of the
VMPC function.

> I don't see why an unkeyed repeated substitution is
> fundamentally harder to attack than a single
> unkeyed substitution.

Inverting VMPC is recovering permutation x -> P[x] (256 bytes)
from permutation x -> P[P[P[x]]+1] (256 bytes)
One most appreciate the VMPC function after discovering
how to recover permutation x -> P[x] matching a given
permutation x -> P[P[P[x]]], and failing to extend the attack.
Hint: rknzvar gur plpyrf jura vgrengvat k -> C[k], naq
vgrengvat k -> C[C[C[k]]].

   François Grieu

[1] S. Mister and S.E. Tavares:
"Cryptanalysis of RC4-like Ciphers"
<http://www1.cs.columbia.edu/~dcook/candexam/Y_23_rc4_cryptana.pdf>

[2] Knudsen, Meier, Preneel, Rijmen and Verdoolaege:
"Analysis Methods for (Alleged) RC4"
<http://citeseer.nj.nec.com/524295.html>

[3] Hal Finney: "An RC4 cycle that can't happen"
<http://groups.google.com/groups?selm=35hq1u%24c72%40news1.shell>

Relevant Pages

  • VMPC function. Question on definition of inverting
    ... computable with 3 one-cycle processor instructions and requiring ... VMPC is an abbreviation of Variably Modified Permutation Composition. ... The VMPC function, also presented at this year's CRYPTO rump session and at ... I have defined the problem of inverting VMPC as finding all Ps ...
    (sci.crypt)
  • Re: VMPC function. Question on definition of inverting
    ... > simple substitution defined by a static pseudorandom permutation. ... produced by applying the VMPC function to P. ... We want to invert VMPC. ...
    (sci.crypt)
  • Re: Solitaire hand encryption algorithm
    ... > strength of such a reduced VMPC. ... Recovering the permutation from the ... I don't have a dedicated simulation for RC4 but based on VMPC ... operations performed by the VMPC cipher can be translated into ...
    (sci.crypt)
  • Imperfect random permutation of 2^k elements
    ... given that one has available the Algorithm P of ... from the given random bit sequence real-valued random numbers ... to any other permutation by applying to it a certain permutation ... It may be noted that the dynamically varying S-box of RC4 is ...
    (sci.crypt)
  • Re: Why RC4 state table is fixed for 256 bytes
    ... Kamalesh wrote: ... The state function in RC4 is a "random" permutation in ...
    (sci.crypt)
Quantcast