Re: Newbie question(s)...

From: Kevin Buhr (buhr_at_telus.net)
Date: 09/19/03 

Date: Fri, 19 Sep 2003 21:14:45 GMT

jonathanrbaker@yahoo.com (Jonathan Baker) writes:
>
> If the "bit-selector" is a 1, then add the current bit of the "source"
> to our key. If the "bit-selector" is a 0, then skip the current bit of
> the "source"...
>
> This is a REALLY simple idea (could go anywhere with this idea... But
> how would an attacker go about analyzing this?

Note that the resulting keystream also represents the binary expansion
of a real number. If it turns out to be rational, then it's probably
worthless to us. If it turns out to be irrational, why didn't we take
our key to be that irrational number in the first place and forget
about a bit selection scheme?

The problem is that, unless you specify some practical keyspace (i.e.,
a subset of irrational numbers that can be easily communicated),
there's no way to evaluate the original selector-less scheme, much
less one with a selector.

> Say Alice and Bob secretly exchange their key "source" and
> "bit-selector" as square roots of 2 and 3 respectively... (obviously,
> we would really use a hard to guess irrational number)... Charlie,
> that scheming ***... does he stand a chance of figuring this out?

Yes, if Charlie knows that Alice and Bob have a thing for the
square-roots of small integers and like to combine them in various
simple ways.

> Suppose there are two more key sources... another irrational number,
> say the square root of 5... if a bit is a zero, skip the current key
> bit... if it is a one, then exchange the current bit with the bit in
> front of it... (unencode in reverse)...
>
> And the fourth irrational number, say Pi, or something... You could
> have zero mean XOR the plaintext and key, and one mean IFF the
> plaintext and key...

Note that this last operation is equivalent to XORing the key with pi
before XORing it with the plaintext.

So, you have four irrational numbers and 3 operations, let's call them
aSb = a's 1s select b's bits; aXb = a's 1s exchange b's bits (though I
don't exactly understand your description---if the first bit of a is a
1, which bits get exchanged?); and a+b = a XOR b.

You're planning to combine these operations in various ways. For
example, writing \2 for root 2 and p and c for the plaintext and
ciphertext, your example up above is:

        c = \5 X (\3 S \2) + Pi + p

This sequence of operations is the "key", if you'd like.

Great.

Now, if Alice sends two messages using this scheme, Charlie can use
the usual attack against an overused "one-time" pad. So, after Alice
sends her first message, she needs to come up with a new formula. She
thinks she's awfully clever when she tries:

        cbad = \5 X (\2 S \2) + pbad

for her next message. Charlie will never think of using the same key
for selection and source! Of course, \2 S \2 is all 1s, and "\5 X" of
that is all ones, so c is just the negation of p. Okay, Alice isn't
that stupid (or your cryptosystem doesn't allow her to do something so
stupid). Instead, she decides to do:

        c2 = \5 X (\3 S \2) + \2 + p2

Okay, not too bad. Charlie can't seem to do anything with that
(because he doesn't notice that c1+c2 share an amazing number of 8-bit
substrings the binary expansion of Pi+\2). But on the third message,
Alice decides that

        c3 = \5 X (\3 S \2) + (\2+Pi) + p3

has to be at least as good as the other things she tried. Charlie's
not totally dense. He knows Alice has a thing for Pi, so when c2+c3
shares so many 8-bit substrings with Pi, he knows he's on to
something. In particular, when he tries c+c2+Pi, he gets something
that shares 8-bit substrings with \2. And a little more fooling tells
him that there's some weird number W = \5 X (\3 S \2) that all three
share. c+Pi = W+p, c2+\2 = W+p2, and c3+Pi+\2 = W+p3. He can't see W
in the clear (unless p, p2, or p3 contain lots of nulls), but if p,
p2, and p3 have similar frequency profiles, he'll see lots and lots of
independent collisions in W+p, W+p2, and W+p3, and he can start
these against each other---he really has three plaintexts encrypted
with the same "one-time" pad W!

If Charlie knows the basic building blocks of your algorithm
beforehand (and you have to assume he will if you ever plan to use
your algorithm in the real world), then he would be even further ahead
than he was in the little thought experiment above. 

-- 
Kevin <buhr@telus.net>