Re: Compression side channel
Greg Rose wrote: At 12:44 AM 9/9/2001 -0400, Sandy Harris wrote: Does using non-adaptive compression save the day? Huffman coding using a fixed code table is not a bad way to go. You can even peek at the characteristics of the input and choose a table based on that... having standardised tables for English text, intel machine code, MS-word documents, C code, other languages, etc. Fax machines do something like this, with a huffman code table conditioned on a set of standard documents, but I'm not sure whether it is just a single table or a set of choose one of these. Choosing one of a set of tables would be a bad idea - I can then use the chosen plaintext to force the choice of particular tables, which would then leak information copiously. Cheers, Ben. -- http://www.apache-ssl.org/ben.html There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Compression side channel
On Sat, Sep 08, 2001 at 10:45:14PM -0400, John Kelsey wrote: where the encryption preserves length (e.g., RC4 encryption). Suppose someone is sending a secret S in these messages, and the attacker gets to choose some prefix or suffix to send, e.g. X[0] = S+suffix[0] X[1] = S+suffix[1] ... Good point. The mistake seems to be mixing a (non-compressible) secret and a (compressible, possibly attacker-chosen) message in one compression run. It seems to be a good idea to compress every logical part of the plaintext separately (and to compress only things which are compressible). Hadmut - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Compression side channel
Peter Wayner wrote: b. I'm hoping to find out if anyone else has seen similar work anywhere. I've not been able to find any references to this kind of attack, though once you've had the idea to try it, it's really pretty straightforward. (And I know there are a couple of occasional posters on this list who know a heck of a lot more about compression algorithms than I do. Peter, are you listening?) These are all good ideas, but I don't know how often you'll get to try them, much less use them enough to extract enough information. I wrote a paper a long time ago that tweaked compression algorithms. It wasn't meant to be secure, only ensure that the compression algorithms constantly changed the set of bits assigned to each character. This meant that a Huffman algorithm encoding 'e' as '0010' at one point would use '1011' later. It was a simple remapping of the compression tree so it wouldn't cost much. But I don't think it had any security on its own. It also wouldn't help at all in this context, since all that is used is the length, not the bits (which, inherently, you don't know anyway). Cheers, Ben. -- http://www.apache-ssl.org/ben.html There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]