Re: Simple balanced pair-wise function

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 07/25/04


Date: Sun, 25 Jul 2004 16:21:16 +0200


Tom St Denis wrote:

> Mok-Kong Shen wrote:
>
>>Tom St Denis wrote:
>>
>>>Something I've been toying with for a while is a balanced pair-wise
>>>mixer.
>>>The use is in stream ciphers. The idea is instead of simply xor'ing the
>>>stream cipher's keystream we use a mixer. Since it's pair-wise we don't
>>>directly leak the actual key stream to the attacker.
>>>
>>>My choice for now is
>>>
>>>p => c, encrypt p to c
>>>
>>>c = ((((p + A) mod 256) + 1) * (B + 1)) mod 257) - 1
>>>
>>>Where A and B are PRNG bytes. The function achieves balanced
>>>decorrelation
>>>as there are an equal number of states in A and B. That is an attacker
>>>has a 1/256 chance of knowing B if they guess A [and vice versa].
>>
>>Maybe I don't understand properly your goal, but how about
>>the following, which is based on combining A and B via Latin
>>square (I had a thread on that sometime ago):
>>
>> c = p + 2*A*B + A + B mod 256
>
>
> On the surface this seems ok too. I just don't like the 2ab mod 256 bit.
> It does have some biases. Most notably if the lsb of A+B is 1 then the 2nd
> bit is the not of second bit of A+B.
>
> I can't directly turn that into an attack. What I like better about my
> approach is when it boils down to the c = ab mod 257 there is zero leakage.
> If the lsb of c = 1 that doesn't mean anything about the individidual
> values of a or b.
>
> Since my approach uses tables anyways [which would be harder to use mod 256]
> I'd think mine is the same speed or faster.

The lsb issue refers to the PRNG that generates it. A good
PRNG should by itself (or after proper postprocessing) be
void of bias or immune to any bias issue in my huble view.

M. K. Shen



Relevant Pages