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:15 ADT
Brian Hurt (brianh@bit3.com)
Wed, 25 Mar 1998 10:01:46 -0600
On Wednesday, March 25, 1998 7:50 AM, Adam Shostack
[SMTP:adam@homeport.org] wrote:
>
> Is your scheme to replace the use of the MAC with a PRNG
> sequencing, or combine the two? It seems to me that the first might
> be equivallent in security, and the second might be a win.
I was thinking of combining the two, using the MAC key as the seed for
the PRNG. The problem is that this adds another link in the chain.
One thing I would be very worried about is if the PRNG seed had
fewer bits than the MAC key. An attacker could then concentrate
on cracking the PRNG, which would then greatly reduce the cost
of cracking the MAC key.
Another thing I'd be worried about would be the PRNG sequence
leaking information about the MAC key.
>
> PRNG sequencing is actually not equivallent to Rivest's scheme
> by itself, because it loses the property of seperability; Rivest's
> scheme is exciting because it allows us to seperate encryption into
> authentication and chaffing, both of which may be legitamate
> operations. I don't see a legitimacy to resequencing someone elses
> packets.
>
> Regarding the combination, I think that this is a win, but
> your scheme reduces the security of Rivest's to either that of the MAC
> or that of the PRNG. (If I can break the PRNG, I can use that to
> seperate the wheat from the chaff.) If instead you send multiple
> versions of each message, but with sequence numbers that are not of
> use to the attacker, then he still needs to break the MAC to choose
> the appropriate wheat.
You are correct, if an attacker breaks the PRNG they break the whole
message. For this reason, I recommend using a cryptographically
secure PRNG with at least as many bits of entropy as the original
MAC (remember, if they break the MAC key, they can also 'decrypt'
the original message, even with PRNG sequence numbers).
I've been thinking of variations of this scheme to increase the
difficulty of attack the PRNG (unfortunately, they are all just
constant factor increases in difficulty- the above statement
still holds true).
One standard thing you should do is use the same PRNG in
generating the chaff sequence numbers as the wheat sequence
numbers, just use a different seed. This gaurentees multiple
solutions to solving which PRNG sequence is being used.
Also add chaff with the same sequence numbers as a subset of
the wheat messages (you'd also want to add all-chaff duplicate
sequence numbers, so the attacker couldn't pick out the wheat &
chaff messages from the chaff-only messages).
>
> However, by forcing him to re-sequence, we may have a gain in
> that the attacker can not use statistical techniques to select
> probable bits. (Eg, every 8th bit should be a zero if you're sending
> printable ascii text.) Its not clear that this selection of the 8th
> bit gets you anything, but denying it to the attacker is probably not
> a bad thing.
I've contemplated compressing the messages before chaffing
them. In the end, I decided it was not worth the CPU cycles. The
attacker
could simply "trial decompress" every possible next packet and
check the results for statistical correctness. This may not be fool
proof, but it does give the attacker an advantage by seperating
the packets into "probably wheat" and "probably chaff". You simply
end up giving the attacker more bits per packet to make the
determination on.
In your case, attempting to hide the zero 8th bit, it'd be easier to
simply generate chaff packets that have the same quality (but first
check to make sure the message has that quality).
One of the things I am trying to do is to allow the sucessful use
of chaffing with block sizes of larger than a few bits. With one
bit blocks, and the chaff being the complement of the wheat,
all valid messages of N-bits long are equally likely, and the attacker
is forced to break the MAC key to determine which one is the
correct one. So the security of the Rivest's original scheme
is as secure as the MAC. The obvious problem is the increase
in the message size. Equally obviously, while increasing the
block size decreases the size increase of the chaffed message,
it also decreases the security of the chaffing, by giving an attacker
more information per block to seperate wheat from chaff.
Increasing the number of chaff blocks per wheat block returns
some of the security lost by going to larger blocks (once again,
at the cost of increasing the message size). One way to look
at the PRNG sequence numbers is that you are using later
message blocks as pseudo-chaff for the current message block.
How many windows are required such that it is easier to break
the PRNG or MAC than to brute-force trial requeuncing of the
message? It's before lunch- I'm not awake enough to do the
Math :-).
I don't speak for Bit 3.
Brian
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:15 ADT