Re: More efficient chaffing technique

James Nicolson (nicolson@netscape.com)
Fri, 27 Mar 1998 02:10:14 -0800

• Next message: Matt Blaze: "Re: Yet another angle on Rivest's chaffing and export control"
• Previous message: Chuck McManis: "Re: More efficient chaffing technique"
• In reply to: proff@iq.org: "Re: More efficient chaffing technique"
• Next in thread: Marshall Clow: "Re: More efficient chaffing technique"

Chuck McManis wrote:

> Hi Julian, perhaps I wasn't clear, let me try again.
>
> You've got a chaffed stream, in this stream you have chaff packets with
> serial numbers and messages. Lets say for the example it is
>
> 1, A, mac
> 1, B, mac
> 1, C, mac
> 2, B, mac
> 2, A, mac
> 2, C, mac
> 3, A, mac
> 3, C, mac
> 3, B, mac
> 4, B, mac
> 4, C, mac
> 4, A, mac
>
> The number of possible messages from this sequence is:
> Seq 1 2 3 4
> A B A B
> B B A B
> C B A B
> A A A B
> B A A B
> ...
> C C B A
>
> The total being something like 3! * 4! or 144 combinations. Now if we've

I think it's 3^4 = 81.

> futher 'packaged' the message (per Ron's suggestion) then the correct
> message should be extractable (it is a package) automatically.
> Relatively easily. (further the problem is seems easily vectored)
>
> Further since the message is actually in the clear, one might be able to
> use correlation techniques to winnow the solutions and avoid the larger
> factorial combinations.
>
> To use your example, one constructs all possible necklaces and then
> notes that one is all red and one is all green. Unlike encryptions which
> are compute bound, this problem is merely memory bound.
>

If the message is split into N pieces, and M pieces of chaff are sent out
for each piece of wheat, then the total number of possible combinations is
(M+1)^N, as has been pointed out by others. If you split your message into
100 pieces (not hard to do), we are talking at least an order of 2^100.
Not likely you can construct that many necklaces, bargain RAM prices
notwithstanding.

In your example, M =2 and N =4, we get 81 which is easy. Obviously the N
is the exponential variable, split your message up into a fair number of
pieces and the size of the problem gets Real Big.

-james

> That's why I was wondering about its effectiveness, especially in
> networks where there are natural choke points where one can capture all
> of the information in the transaction.
>
> --Chuck

• Next message: Matt Blaze: "Re: Yet another angle on Rivest's chaffing and export control"
• Previous message: Chuck McManis: "Re: More efficient chaffing technique"
• In reply to: proff@iq.org: "Re: More efficient chaffing technique"
• Next in thread: Marshall Clow: "Re: More efficient chaffing technique"