8 ms·

Chaffing and Winnowing: Confidentiality without Encryption (1998)

69 points by ronancremin 13y ago

zepolud 13y ago
It's cool but basically solves a problem that no longer exists. Once you've caused enough suspicion, they can simply dig up the records of all the data you've sent, both chaff and wheat, and serve you with an order to disclose your authentication key/lawfully hack you computer and obtain it without asking/apply some lead pipe cryptanalysis and get it anyway. In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient. 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."
- Lexarius 13y ago
  Near the bottom they mention using more than one wheat stream to achieve something like deniable encryption. If they ask you for the key, give them the one that produces innocent-looking messages.
  - ionforce 13y ago
    I'm sure if law enforcement doesn't like your innocent looking messages they can just keep demanding that you give them the real key. How easy is it to produce a stream of messages that is fake but looks real?
    - Lexarius 13y ago
      Depends, how good are you at creative writing? I can think of a lot of messages you might send to someone that you'd want to be private that aren't nefarious plots. Weird fan fiction. Deviant porn. Messages exchanged with a secret mistress. Depending on the situation, you might even want to give them a fake copy of your nefarious plot. Include more than one extra set of messages if you like and give them whatever keys you like in whatever order is appropriate.
- AnthonyMouse 13y ago
  >In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient. 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.
knowaveragejoe 13y ago
Isn't this still, in essence at least, Steganography?
- zepolud 13y ago
  Nope. You would be painting a huge red target on yourself if you tried something like this. The purpose of steganography is not to get noticed in the first place. It's orthogonal to regular cryptography.
  - ozi 13y ago
    Unfortunately, common steganography algos used on images are easy to detect with statistical analysis.
    - akkartik 13y ago
      Can you elaborate?
      - knowaveragejoe 13y ago
        http://en.wikipedia.org/wiki/Steganalysis http://en.wikipedia.org/wiki/Steganalysis
      - DanBC 13y ago
        People read a book, they see a simple description of steganography, they whip up an implementation as a proof of concept, they share that code, other people think it's secure when it's not meant to be. (http://www.ifp.illinois.edu/~ywang11/paper/CISS04_204.pdf http://www.ifp.illinois.edu/~ywang11/paper/CISS04_204.pdf) (http://eprint.iacr.org/2005/305 http://eprint.iacr.org/2005/305) (http://vision.ece.ucsb.edu/publications/sullivan_ICIP06.pdf http://vision.ece.ucsb.edu/publications/sullivan_ICIP06.pdf)
    - pkinsky 13y ago
      Does this include f5? https://code.google.com/p/f5-steganography/ https://code.google.com/p/f5-steganography/
DanBC 13y ago
See also "Chaffinch: Confidentiality in the Face of Legal Threats" by Richard Clayton and George Danezis from University of Cambridge, which has some more plausible deniability. (http://www.cl.cam.ac.uk/~rnc1/Chaffinch.html http://www.cl.cam.ac.uk/~rnc1/Chaffinch.html)
crb002 13y ago
I've thought about writing a Chrome plugin to do something similar. While on it would randomly chaff the low order bits of any image you upload, and would automatically add a chaff postscript to every Gmail. An adversary would have no clue which images/messages contain ciphertext, and which contain nothing but random chaff.
Cyranix 13y ago
Was unreachable for me, here's the cached version: http://webcache.googleusercontent.com/search?q=cache:zgl1Lf25QRIJ:people.csail.mit.edu/rivest/Chaffing.txt http://webcache.googleusercontent.com/search?q=cache:zgl1Lf2...
theboss 13y ago
Kind of interesting scheme that doesn't really work in 2013. Wouldn't this be vulnerable to replay attacks, or am I missing something?
- hellcow 13y ago
  If Alice's messages could all be intercepted and manipulated prior to Bob's receiving them, then yes, they could be changed without either party knowing. Combined with asymmetric encryption of the messages, you should be able to prevent that from happening.
  - theboss 13y ago
    Without any manipulation why wouldn't this be vulnerable to a replay attack?
- jamesrom 13y ago
  No. This is just a method of "securing" messages without encryption. It still requires a shared key. Replaying messages sent this way would be no different to replaying an encrypted message. This is not an authentication scheme.
sirmarksalot 13y ago
I'm probably misunderstanding this. The way I'm envisioning this is basically a half-dozen parallel conversations, with only one of them being the actual conversation. 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.
- ronaldx 13y ago
  Keep reading: the first example is a bit misleading (for the reason you state) and the article gets more interesting. They deal with this problem by coding the message with single-bit packets, always contrasting 0s with 1s.
  - sirmarksalot 13y ago
    Yup, that was the critical piece I was missing. Thanks!
- kyboren 13y ago
  In that document, he proposed two different systems. 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())) ); } Without knowing the HMAC key, the only information exposed is the length of the message. Without the HMAC key, you can't tell whether '0' or '1' (both of which are sent, for every bit in the message) is the correct bit. 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. [1]: http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps
lucb1e 13y ago
Might be just me, but I'm thinking encryption is way easier than this.
- bigiain 13y ago
  Two points: First, this was from 1998 - back when "exporting encryption" from the US was punishable as exporting weapons. Secondly, this is proposing a communication scheme where there is no "encryption/decryption key" for the NSA to coerce people into handing over.
- Cyranix 13y ago
  But that's rather missing the point, isn't it? The premise is "Under circumstances where encryption is not a viable option, what secure communication methods might be possible?" so responses that ignore the premise, like "just use encryption" or "just don't get into such circumstances", aren't the most salient critiques.

69 points by ronancremin 13y ago

It's cool but basically solves a problem that no longer exists. Once you've caused enough suspicion, they can simply dig up the records of all the data you've sent, both chaff and wheat, and serve you with an order to disclose your authentication key/lawfully hack you computer and obtain it without asking/apply some lead pipe cryptanalysis and get it anyway. In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient. 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."

Lexarius 13y ago
Near the bottom they mention using more than one wheat stream to achieve something like deniable encryption. If they ask you for the key, give them the one that produces innocent-looking messages.
- ionforce 13y ago
  I'm sure if law enforcement doesn't like your innocent looking messages they can just keep demanding that you give them the real key. How easy is it to produce a stream of messages that is fake but looks real?
  - Lexarius 13y ago
    Depends, how good are you at creative writing? I can think of a lot of messages you might send to someone that you'd want to be private that aren't nefarious plots. Weird fan fiction. Deviant porn. Messages exchanged with a secret mistress. Depending on the situation, you might even want to give them a fake copy of your nefarious plot. Include more than one extra set of messages if you like and give them whatever keys you like in whatever order is appropriate.
AnthonyMouse 13y ago
>In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient. 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.

knowaveragejoe 13y ago

Isn't this still, in essence at least, Steganography?

zepolud 13y ago
Nope. You would be painting a huge red target on yourself if you tried something like this. The purpose of steganography is not to get noticed in the first place. It's orthogonal to regular cryptography.
- ozi 13y ago
  Unfortunately, common steganography algos used on images are easy to detect with statistical analysis.
  - akkartik 13y ago
    Can you elaborate?
    - knowaveragejoe 13y ago
      http://en.wikipedia.org/wiki/Steganalysis http://en.wikipedia.org/wiki/Steganalysis
    - DanBC 13y ago
      People read a book, they see a simple description of steganography, they whip up an implementation as a proof of concept, they share that code, other people think it's secure when it's not meant to be. (http://www.ifp.illinois.edu/~ywang11/paper/CISS04_204.pdf http://www.ifp.illinois.edu/~ywang11/paper/CISS04_204.pdf) (http://eprint.iacr.org/2005/305 http://eprint.iacr.org/2005/305) (http://vision.ece.ucsb.edu/publications/sullivan_ICIP06.pdf http://vision.ece.ucsb.edu/publications/sullivan_ICIP06.pdf)
  - pkinsky 13y ago
    Does this include f5? https://code.google.com/p/f5-steganography/ https://code.google.com/p/f5-steganography/

DanBC 13y ago

See also "Chaffinch: Confidentiality in the Face of Legal Threats" by Richard Clayton and George Danezis from University of Cambridge, which has some more plausible deniability. (http://www.cl.cam.ac.uk/~rnc1/Chaffinch.html http://www.cl.cam.ac.uk/~rnc1/Chaffinch.html)

crb002 13y ago

I've thought about writing a Chrome plugin to do something similar. While on it would randomly chaff the low order bits of any image you upload, and would automatically add a chaff postscript to every Gmail. An adversary would have no clue which images/messages contain ciphertext, and which contain nothing but random chaff.

Cyranix 13y ago

Was unreachable for me, here's the cached version: http://webcache.googleusercontent.com/search?q=cache:zgl1Lf25QRIJ:people.csail.mit.edu/rivest/Chaffing.txt http://webcache.googleusercontent.com/search?q=cache:zgl1Lf2...

theboss 13y ago

Kind of interesting scheme that doesn't really work in 2013. Wouldn't this be vulnerable to replay attacks, or am I missing something?

hellcow 13y ago
If Alice's messages could all be intercepted and manipulated prior to Bob's receiving them, then yes, they could be changed without either party knowing. Combined with asymmetric encryption of the messages, you should be able to prevent that from happening.
- theboss 13y ago
  Without any manipulation why wouldn't this be vulnerable to a replay attack?
jamesrom 13y ago
No. This is just a method of "securing" messages without encryption. It still requires a shared key. Replaying messages sent this way would be no different to replaying an encrypted message. This is not an authentication scheme.

sirmarksalot 13y ago

I'm probably misunderstanding this. The way I'm envisioning this is basically a half-dozen parallel conversations, with only one of them being the actual conversation. 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.

ronaldx 13y ago
Keep reading: the first example is a bit misleading (for the reason you state) and the article gets more interesting. They deal with this problem by coding the message with single-bit packets, always contrasting 0s with 1s.
- sirmarksalot 13y ago
  Yup, that was the critical piece I was missing. Thanks!
kyboren 13y ago
In that document, he proposed two different systems. 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())) ); } Without knowing the HMAC key, the only information exposed is the length of the message. Without the HMAC key, you can't tell whether '0' or '1' (both of which are sent, for every bit in the message) is the correct bit. 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. [1]: http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps

lucb1e 13y ago

Might be just me, but I'm thinking encryption is way easier than this.

bigiain 13y ago
Two points: First, this was from 1998 - back when "exporting encryption" from the US was punishable as exporting weapons. Secondly, this is proposing a communication scheme where there is no "encryption/decryption key" for the NSA to coerce people into handing over.
Cyranix 13y ago
But that's rather missing the point, isn't it? The premise is "Under circumstances where encryption is not a viable option, what secure communication methods might be possible?" so responses that ignore the premise, like "just use encryption" or "just don't get into such circumstances", aren't the most salient critiques.