Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:17 ADT
Aaron D. Gifford (agifford@infowest.com)
Thu, 26 Mar 1998 20:09:41 +0000
Mark A. Herschberg wrote:
> This sounds like a good idea. Suppose we want to have a half hour
> "conversation." Someitme before, we open a channel, and start sending
> packets, including, not just chaff, but also Shakespeare's _Hamlet_, data from
> my web page, etc., each one a different "message." These different messages
> jump in and out of the channel to inhibit timing analysis. At some point, I
> also include the actual information I want to secretly tell you. There's
> plenty of extra messages to hand over to the courts. (Note: you may need to
> include a channel with private, useless messages, and not just public
> information such as _Hamlet_ and your web page, but dummy private messages
> could easily be made.)
>
> The drawback to this system is the heavy load. Certainly, if we all use
> this protocol, especially where we sure the channel significantly ahead of
> time (as described above), the internet going to be extremely jammed.
> However, a more practical use for this might be over the phone. To send a
> secure fax, for example, we'll have a "private" (although not secure) line
> which we can stuff packets down to our heart's content.
>
> Art Housnger brough up the follwing point to me the other day:
> Why not just send
> (1,0,351216)
> (1,1,351216)
> (2,0,452412)
> (2,1,452412)
> (3,0,639723)
> (3,1,639723)
> (4,0,321329)
> (4,1,321329)
>
> were for each bit of wheat, the chaff uses the same MAC. This, in and of
> itself, doesn't seem to add any security, but what if we do the following:
>
> (1,0,1,351216)
> (2,0,1,452412)
> (3,0,1,639723)
> (4,0,1,321329)
Along the same lines, would this work:
(1,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,547234)
(2,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,325266)
(3,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,715246)
(4,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,175467)
Where the MAC is only valid for 1 of the 4-bit values and the rest are
chaff. Could you not then leave out the
"0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F" part entirely?:
(1,547234)
(2,325266)
(3,715246)
(4,175467)
Is this what you were trying to say later on in your message, Mark?
In doing this with a 4-bit value versis Rivest's original 1-bit wheat
and inverted bit chaff
It looks like the packet savings over the original 1-bit wheat/chaff
system doing things this way is 2N where N is the number of bits sent
this way. The receiver must then search a maximum of 2N possible values
to find the correct wheat value. I would expect the search to only
require searching (on average over many packets) about half the possible
values assuming a message with even distribution of values.
A quick table:
Bits Packet Max. Ave.
Sent Savings Search Search
---- ------- ------ ------
1 1 2 1
2 3 4 2
3 5 8 4
4 7 16 8
5 9 32 16
6 11 64 32
7 13 128 64
8 15 256 128
It loos to me like the break-even point is at around 3 to 4 bits before
cost of the search on the receiver's site begins to exceed the packet
savings. 4-bits with a message with even distribution of values,
perhaps 3-bits with a worst-case message.
I assume that the chances for collision are still insignificant for
sending 4 bits this way such that the MAC would still only be valid for
a single value. How much does this reduce the security of chaffing
things this way versus Rivest's original single-bit with inverted chaff
version?
Leaving out the wheat and chaff and just sending the sequence number and
MAC would require the other side of the channel to "search" through the
possible values for the real message, but the receiver would essentially
be doing the same thing if the data were present as wheat and chaff
anyway. In fact, leaving the chaff/wheat data out, it appears there
would be a slight win in that the search for valid data would probably
require searching only about half of the available wheat/chaff space on
average.
What are the imlications of leaving out the data (wheat AND chaff) and
just sending the MAC? It seems that this defeats (to some degree) the
argument that the data is IN THE CLEAR.
Mark continues:
>
> In the above case, each packet has two bits with it, one of which matches the MAC, and one of which doesn't. (And occasionally packets neither of which work as some extra chaff?) Clearly in the bit case, the "0,1" can be left out. If more than one bit is sent per packet, then one could imagine when sending, say, hex, a packet like
>
> (1,E,5,657439)
>
> where the MAC is valid for either E or 5.
> I haven't had time to look this up, but I seem to recall in literature some use of MACs for security that works in this way.
> Now in the example with 4 packets, it's still revealing that a message is 4 bits long (and there may be other flaws I'm not thinking of). If this isn't a problem (and I didn't miss a security hole), then we just made the algorithm 50% more efficient.
> I've only given brief thought to this, as I'm extremely busy with other projects, but I would be interesting in hearing feedback and/or point out what I've missed here.
>
> Some points to consider:
> Would this work even with a bad MAC? (Since # of 1's = # of 0's)
> Is this stronger when using 2 or 3 different MACs for one message?
>
> --Mark A. Herschberg
I belive Mordechai Ovits message pointed out the danger of sending a
4-bit packet where the value is only either of 2 possibilities. But if
the value is left out and could be ANY of the full range of 4-bit
values, it seems this would work.
Aaron out.
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:17 ADT