Re: [cryptography] One Time Pad Cryptanalysis
Ben Laurie b...@links.org wrote: | Encryption is time-consuming; compressing a file before encryption | speeds up the process. I haven't benchmarked it, but I find it unlikely that compression is faster than encryption. It can be if weak compression is acceptable. That may not be worth the trouble, but it is certainly possible. If the input is English text, then space is much the commonest character, about one in seven. If the encoding is ASCII, then the top bit of every byte is zero. You can get 10% compression with a fast dumb algorithm that just deletes spaces and sets the top bit of the following character to indicate where to re-insert them. Any newline not followed immediately by another can be removed the same way if format is not an issue. A somewhat smarter method that replaces common sequences like 'the' or 'ing' with single non-ASCII bytes can also be fast and would probably give quite a bit better compression. Where problems appear is if you try to be clever and adaptive; that is clearly necessary for optimal compression, but perhaps not for useful compression. It has higher overheads and it requires some sort of header to tell the receiver about the compression, which introduces a known plaintext risk. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Applied Cryptography (2nd edition) contains this: | 10.6 Compression, Encoding, And Encryption | | Using a data compression algorithm together with an encryption | algorithm makes sense for two reasons: | | Cryptanalysis relies on exploiting redundancies in the plaintext; | compressing a file brfore encryption reduces these redundancies. | | Encryption is time-consuming; compressing a file before encryption | speeds up the process. | | The important thing to remember is to compress before encryption. […] Schneier doesn't cite any references for these claims, unfortunately. Bergen and Hogan, A Chosen Plaintext Attack on an Adapative Arithmetic Coding Compression Algorithm (2002) cite Witten and Cleary, On the privacy afforded by Adaptive Text Compression (1988) and Jones, An efficient coding system for long source sequences (1981). Neither paper appears to be available on the public Internet. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 3 October 2013 14:13, Florian Weimer f...@deneb.enyo.de wrote: On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Applied Cryptography (2nd edition) contains this: Oh boy. | 10.6 Compression, Encoding, And Encryption | | Using a data compression algorithm together with an encryption | algorithm makes sense for two reasons: | | Cryptanalysis relies on exploiting redundancies in the plaintext; | compressing a file brfore encryption reduces these redundancies. Yeah. So CRIME shows us how accurate this wild claim is. | | Encryption is time-consuming; compressing a file before encryption | speeds up the process. I haven't benchmarked it, but I find it unlikely that compression is faster than encryption. | The important thing to remember is to compress before encryption. […] Obvious. Schneier doesn't cite any references for these claims, unfortunately. Bergen and Hogan, A Chosen Plaintext Attack on an Adapative Arithmetic Coding Compression Algorithm (2002) cite Witten and Cleary, On the privacy afforded by Adaptive Text Compression (1988) and Jones, An efficient coding system for long source sequences (1981). Neither paper appears to be available on the public Internet. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
* Ben Laurie: | 10.6 Compression, Encoding, And Encryption | | Using a data compression algorithm together with an encryption | algorithm makes sense for two reasons: | | Cryptanalysis relies on exploiting redundancies in the plaintext; | compressing a file brfore encryption reduces these redundancies. Yeah. So CRIME shows us how accurate this wild claim is. And it's not even the first attack of this type. I find the application voice codecs particularly cute. The recommendation is really puzzling. With a modern cipher, compression (even if it hasn't fingerprints of its own) should never make cryptanalysis harder. With a very weak cipher, it could make a difference, but even in the mid-90s, you hopefully wouldn't use one, even after consulting Applied Cryptography (which describes quite a few of them, admittedly). ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
* Lodewijk andré de la porte: 2013/9/30 Florian Weimer f...@deneb.enyo.de 3. Message integrity does not matter. 4. The security proof assumes there is only one message, ever. 3 and your paper about VOIP regard traffic analysis. I'm not sure what else 3 refers to. Certainly a known plaintext attack would negate that part of the message, but then it wasn't very encrypted in the first place, was it? Then you can of course replace part of the message, and if you have a partial plaintext you might even make it not-garbled, but then still I think you should apply mixing/scrambling before OTP'ing your plaintext. Surely that invalidates the security proof. :-) 4 regards the notion that a One-Time-Pad is only used One-Time. Sorry, not what I meant. Even if you avoid reuse of key material, it is not (provable) secure to send more than one message. I might've misunderstood the meaning of these points. I'd like to have misunderstood, then there is something to learn. I'm trying to argue out that OTP is broken according to the standards we require from generic encryption protocols such as TLS. Or that there is a large gap between the security proof and reality, making the proof rather pointless. P.S.: Why is that paper 15 pages long? I mean, really. It's just correlating input letter (in voice), where possible, with the output bandwidth and it's changes. There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Without these, IMHO your sentence is false. Example: http://breachattack.com/ ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
That would be known plaintext attack (or statistical analysis like how simple ciphers typically are broken) vs chosen plaintext attack (BREACH is the latter, while compression would increase entropy density to make the former harder since each individual bit becomes harder to predict). Sorry, no sources from me either. I could try looking for some. - Sent from my phone Den 2 okt 2013 19:38 skrev danimoth danim...@cryptolab.net: On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Without these, IMHO your sentence is false. Example: http://breachattack.com/ ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 10/2/13 10:38 AM, danimoth wrote: On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Without these, IMHO your sentence is false. Since when are academic references needed to assert that something is widely believed? ;-) Peter - -- Peter Saint-Andre https://stpeter.im/ -BEGIN PGP SIGNATURE- Version: GnuPG/MacGPG2 v2.0.19 (Darwin) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSTFswAAoJEOoGpJErxa2pPEoQAKTK8mIbdWoCpTOTKzlnV1Gh rekmu7C9WwKJSTxhfKBzeMKKMgKjq8PL/O2/Yxl9v82uV4wM5SPOV8VtzoDSwoXH wDu8uZVqWWcVVxUQdnD1sGve8+XlsbNtBcRKKIabKVOTWA3QgdVQWOvtErwTlWIB SCpMO+JjRqSDKwnmyxpnfB9Y83bMvDQisqvYsxRZuwfVICn/HJWyFAIedfYT7vM2 I0MiplVIdZf137ZbWlaOlEzabV28FbAPxUAeYnrLuJhmSzW4fzgla6bM66OfBz8m vlk1pa2i1Yj3ZzJN0zcOYdnLkEoRy6H8PC8Tl7YvlJM8wiOjpfoDJy7fd9yUKlUq sxPs0CbYHs+gh/jRV0EHR2eBSfhEBh9zAYPtKdmMpdS/0+iyO+6fnOPqR0Kvo5su 1qNY690wfsu8HEDVHJr+tqc1EDy3Ay618yNyJnCRvLz1BJtGMXgKbhSFPYnt2fJJ VQmVw0RcBBIuHVXhq4LAjIJQ5j1ABn1v700IoP2wkNBtdIWF0XUXNBgYgCLvo5gB rOw4xbKIDmHCuoClCZ4oeUOBNWzJvFxe/aCrPBGdwyPt1KnQ85ufBk7LOg3y+D5Q dtf1sNJdfFExXB55z9Kwn4g9rY/lyRdy5CvGtXZqQOx7SFRSAlAfrw5BmbqPVkgV U0dAkJIvZPB7bv2BPUYf =m6cZ -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
Communications Theory of Secrecy Systems, Claude Shannon, 1949 http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf On Wed, Oct 2, 2013 at 1:38 PM, danimoth danim...@cryptolab.net wrote: On 02/10/13 at 08:51am, Florian Weimer wrote: There is widespread belief that compressing before encrypting makes cryptanalysis harder, so compression is assumed to be beneficial. Any academic references? Without these, IMHO your sentence is false. Example: http://breachattack.com/ ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 2013-10-03 09:17, Charles Jackson wrote: Any academic references? Official reality is surreal and generally should be ignored. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
2013/9/30 Florian Weimer f...@deneb.enyo.de 3. Message integrity does not matter. 4. The security proof assumes there is only one message, ever. 3 and your paper about VOIP regard traffic analysis. I'm not sure what else 3 refers to. Certainly a known plaintext attack would negate that part of the message, but then it wasn't very encrypted in the first place, was it? Then you can of course replace part of the message, and if you have a partial plaintext you might even make it not-garbled, but then still I think you should apply mixing/scrambling before OTP'ing your plaintext. There's quite a selection of ways to do that. I agree this is relevant in some applications. In others it can be fixed. For example by mixing by doing AES (or something better) with the first x bits of the OTP. Just to mix, not to encrypt. But then a (mayor) flaw in AES could provide the opponent with a partial plaintext attack against AES an attack on whatever touched that data in the OTP'ed output. Hmm. Even a simple mixer exclusively using the beginning of the pad for secret information must be able to simply mix the input. AES should be able to do that much, I doubt it would so broken it wouldn't do that. And of course I don't think we can consider traffic analysis a breach of encryption. Not that I think it's not breach. But it's not related to OTP. You could apply traffic analysis even on plaintext. Point is that it's a breach of security from another piece of the system (the whole) than the one we are discussing. 4 regards the notion that a One-Time-Pad is only used One-Time. I agree, but reuse of any form will either make P leak or it will not be a problem. There's no real reason to use P multiple times and it is very hard to be sure you are not leaking information about P when you reuse. I judge this 4th requirement to be redundant to requirement 2. Although it is still correct, of course. I might've misunderstood the meaning of these points. I'd like to have misunderstood, then there is something to learn. P.S.: Why is that paper 15 pages long? I mean, really. It's just correlating input letter (in voice), where possible, with the output bandwidth and it's changes. Of course there's hundreds of little annoying things from several disciplines. I guess they did it thoroughly, then the paper should be thorough. Fine. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
* Lodewijk andré de la porte: [OTP assumptions] 1. Good source. P[i] must be independent to anything in P nor to the method to generate P. Random, you'd typically say. Fully unpredictable might be more clear (given people's unclarity about what's random). 2. No leak of P 3. Message integrity does not matter. 4. The security proof assumes there is only one message, ever. The proof is simply not correct for multiple messages, and OTP does not provide unconditional security for the multi-message case anyway. I'm really frustrated with people claiming OTP is insecure. I don't understand how it is and I cannot seem to construe any angles of attack. This attack would work against an OTP, too: Wright et al., Spot me if you can: Uncovering spoken phrases in encrypted VoIP conversations. http://cs.unc.edu/~fabian/papers/oakland08.pdf The basic issue has recently been rediscovered in the context of HTTP(S). ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 26/09/13 23:09 PM, Jeffrey Goldberg wrote: I’m suggesting that when offering advice to application developers on what sorts of systems to use, we should explicitly consider how easy it is for them to screw it up and how bad things get when they do. They should be given something that won't screw up. Which means it needs to be simple enough such that all the decisions are already made. In my work, I've evolved into an OO pattern which I call a Cryptor. It has everything built in: creation, storage, encrypt, decrypt as required. Plus heavy ouroboris testing. The idea is modular, eg PK Cryptor is built out of an AES/CBC Cryptor and a HMAC Cryptor, etc. Another example is the API provided to do curve25519xsalsa20poly1305 (which is in C so not OO). iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] One Time Pad Cryptanalysis
Cryptanalystis make their living out of sloppy thinking and enthusiastic over-ingenuity of designers of cipher systems. Brig. Gen. J.H. Tiltman, Some Principles of Cryptographic Security, NSA Technical Journal, Summer 1974. http://www.nsa.gov/public_info/_files/tech_journals/Some_Principles.pdf Tiltman vaunts the One Time Pad but cautions there have been effective decrypts exploiting enthusiastic sloppy thinking that OTP is unbreakable. Most appears to involve non-decipher means and methods. The paper redacts others presumably still effective. For amateur ingenuity Tiltman footnotes: I remember an early example of the solution of the problem of producing strictly one-time perforated tape. A Canadian engineer working for a British intelligence organization in New York who knew nothing at all about cryptography produced in 1942 an on-line machine called TELEKRYPTON. He generated his tapes by pouring a mixture of metal and glass balls through a hopper, the metal halls alone passing current and perforating 5-level tape. He analyzed the result and saw that it was biased, owing to the heavier weight of the metal balls, and then changed the respective sizes of the balls to compensate for the extra weight of the metal. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] One Time Pad Cryptanalysis
John Young j...@pipeline.com wrote: Tiltman vaunts the One Time Pad but cautions there have been effective decrypts exploiting enthusiastic sloppy thinking that OTP is unbreakable. Most appears to involve non-decipher means and methods. The paper redacts others presumably still effective. Here's one, not always applicable but devastating when it is: http://en.citizendium.org/wiki/Stream_cipher#Rewrite_attacks ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 26/09/13 17:36, Sandy Harris wrote: John Young j...@pipeline.com wrote: Tiltman vaunts the One Time Pad but cautions there have been effective decrypts exploiting enthusiastic sloppy thinking that OTP is unbreakable. Most appears to involve non-decipher means and methods. The paper redacts others presumably still effective. Here's one, not always applicable but devastating when it is: http://en.citizendium.org/wiki/Stream_cipher#Rewrite_attacks Reuse of pads is also disastrous - VENONA made a breakthrough due to pad reuse, which wasn't public knowledge at the time the paper was written (though was by the time it was declassified). Cheers, Michael -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJSRIG3AAoJEBEET9GfxSfMPAsH/RiJ3eshLdf9wHCVzeZ+ WNSLuJ4Pb3J+B3kjYmei6M3RpfhsA0TWhHZxjUlBnBLqf3/+CoRsXSXMlfTS9EZV BXbNIjiDH5JiYJHGFGp3RZ3Cu1tDO59+1J+albBgMsY9V7Nk67HgBp66n9BuvgxK CqpY1gZQ5dXU/iQVgpUdAgPt9urZeShy9IF8l9pj38tAZtNF6XKjZ/HvezbGwh4s yhoYsYjIT56Nc04/yGKJKTwGztPJ4V3oIcKeXgCYCQx5AbGNqkimk+fnkiYVFzoW Wq3ycmgMJqFYSr3GSGniGjPeh/4kOsvSQSENHUzGW6qk//bNkgrsRm3TekCSsQQ= =lPIx -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] One Time Pad Cryptanalysis
On 2013-09-26, at 1:49 PM, Michael Rogers mich...@briarproject.org wrote: Reuse of pads is also disastrous - VENONA made […] Forgive me for taking this opportunity to repeat an earlier rant, but your example provides the perfect example. When a one time pad is operated perfectly, it provides perfect secrecy; but once it is operationed with small deviations from perfection it provides terrible security. Things that approximate the OTP in operation do not approximate it in security. This is a very good reason to steer people away form it. This is an example of why we need to pay attention to how easy it is to screw things up and how badly things fail. For example, CBC mode will degrade proportionally with how poorly IVs are selected. CTR, on the other hand, can degrade catastrophically with poor nonces. Another example is that we prefer ciphers which are not vulnerable to related key attacks even though we expect good system design to not use related keys in the first place. I’m suggesting that when offering advice to application developers on what sorts of systems to use, we should explicitly consider how easy it is for them to screw it up and how bad things get when they do. Cheers, -j smime.p7s Description: S/MIME cryptographic signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
