Still, for all the crypto export nonsense, 1998 appears to have been a more innocent time:
> "But access to authentication keys is one thing that government has long agreed that they don't want to have."
How easy is it to produce a stream of messages that is fake but looks real?
He goes on to explain how to make it more efficient: If you need every "wheat" packet to reconstruct any part of the message, you can send a finite number of chaff packets (e.g. 1000) in random locations, which would make reconstructing a message of arbitrary length infeasible for an adversary that can't separate the wheat from the chaff other than by exhaustive search.
Couldn't it be easily defeated with contextual analysis? I mean, if it were English sentences, the attacker could just choose a set of packets that make grammatical sense. Or in more real-world examples, you'd just choose the packets that form a valid HTTP session.
To work around this, you'd have to choose your chaff packets to flow seamlessly from one to the other, which would make chaffing a really hard problem.
The first transmits two tuples for every bit of the message. In pseudo-ish code:
for(i = 0; i < message_bits.length; ++i){
send( (sequence_number, 0, (message_bits[i] == 0? HMAC(shared_key, sequence_number . '0') : rand())) );
send( (sequence_number, 1, (message_bits[i] == 1? HMAC(shared_key, sequence_number . '1') : rand())) );
}
The second works in a slightly different way. You take a message, and transform it into a package in such a way that one must determine the entire package contents before being able to decode any part of the package. (Rivest's proposal for such an 'All-or-Nothing Transform' can be found in [1]).
Next, you packetize that transformed package. Rivest proposes blocks of 1024 bits, but it could be anything. The point is you can't send (2^1024 - 1) 'chaff' blocks, which would be required to not leak any information about a 1024-bit message block.
But, crucially, you must determine which is the correct block for every sequence number sent. So, if one includes just one 'chaff' block for each 'wheat' block (so there is one wheat and one chaff block for each sequence number), and sends n blocks, then an attacker who doesn't know the HMAC key would need to choose the right combination of blocks of all sequence numbers--a 1 in 2^n chance--before being able to decode your message.
If one splits an all-or-nothing transformed message into at least 256 blocks and sends one 'chaff' block with each 'wheat' block, you could be pretty sure the message remains confidential. Of course, this assumes all those pesky security assumptions about the random number generator, transform, and HMAC function hold up.
They deal with this problem by coding the message with single-bit packets, always contrasting 0s with 1s.
Wouldn't this be vulnerable to replay attacks, or am I missing something?
Combined with asymmetric encryption of the messages, you should be able to prevent that from happening.
This is not an authentication scheme.
The purpose of steganography is not to get noticed in the first place. It's orthogonal to regular cryptography.