Re: why compression doesn't perfectly even out entropy
Perry Metzger writes:
1. If "cooking" a byte sequence in a manner that reduces its maximum entropy by less than 1% allows an attacker to break your cryptosystem, then it is crap to begin with. With only a little more effort, he could break it anyway.
I would suggest that you look at differential and linear cryptanalysis to learn what a tiny little statistical toehold will give you.
My "ad hominem PSA" stands. I suggest people not trust Mr. Wienke's pronouncements. He appears to be suffering from significant hubris.
No, he's correct; cryptanalytic schemes like those you mention rely on statistical toeholds *in the context of a deterministic cipher algorithm*. For one-time pads that are "cooked" or "screened" (and I agree that it's a silly thing to do), the toehold is much weaker, infinitesimal in fact. For example, suppose we take 1024-bit blocks from a physical RNG (which we'll agree is "good", has entropy close to 1024 bits, whatever that means). There are 2^1024 such blocks. Obtain one and apply the magical test---if the block fails, toss it in the bit bucket. Suppose, conservatively, that half the sequences fail. The cryptanalyst now knows that the plaintext cannot be ( failed_pad xor ciphertext ) for any of the 2^1023 failed_pads. Thus, it must be one of the other 2^1023. This is the *only* toehold he gets. Cheers, Peter Monta pmonta@qualcomm.com Qualcomm, Inc./Globalstar
Peter Monta writes:
No, he's correct; cryptanalytic schemes like those you mention rely on statistical toeholds *in the context of a deterministic cipher algorithm*. For one-time pads that are "cooked" or "screened" (and I agree that it's a silly thing to do), the toehold is much weaker, infinitesimal in fact.
Please learn what the context of the discussion was before commenting. It was not about using cooked streams for one time pads. Furthermore, I suggest you look up the Venona intercept work and tell me again about how far an advesary will go with a tiny toehold. .pm
Perry writes:
Furthermore, I suggest you look up the Venona intercept work and tell me again about how far an advesary will go with a tiny toehold.
The Venona breaks came because the NSA had a lot of encrypted traffic and some pads were used more than once, which is hardly a tiny toehold. After years of dragging intercepted messages through each other, something finally popped out. Messages encrypted with pads that were only used once are still unbroken, AFAIK, even though the pads were simply generated by clerks banging on keyboards. Still, a tiny toehold is all a good analyist needs to break a non-OTP cryptosystem, which attempts to protect a lot of information with only a little bit entropy. andrew
Andrew Loewenstern writes:
Perry writes:
Furthermore, I suggest you look up the Venona intercept work and tell me again about how far an advesary will go with a tiny toehold.
The Venona breaks came because the NSA had a lot of encrypted traffic and some pads were used more than once, which is hardly a tiny toehold.
In general, they were used twice. Thats a pretty tiny toehold. .pm
Peter Monta wrote:
Perry Metzger writes:
1. If "cooking" a byte sequence in a manner that reduces its maximum entropy by less than 1% allows an attacker to break your cryptosystem, then it is crap to begin with. With only a little more effort, he could break it anyway.
I would suggest that you look at differential and linear cryptanalysis to learn what a tiny little statistical toehold will give you.
My "ad hominem PSA" stands. I suggest people not trust Mr. Wienke's pronouncements. He appears to be suffering from significant hubris.
No, he's correct; cryptanalytic schemes like those you mention rely on statistical toeholds *in the context of a deterministic cipher algorithm*. For one-time pads that are "cooked" or "screened" (and I agree that it's a silly thing to do), the toehold is much weaker, infinitesimal in fact.
Perry's right: giving up any statistical information is too much. A slightly contrived example of why tossing out duplicated bytes is bad: Suppose that a military organization is using this almost one-time-pad system, and my spies tell my they've fallen into the habit of sending "attack" and "defend" as their only 6-byte messages. This isn't a problem with a real one-time pad (except for traffic analysis...), but this lets me determine the message 3.8% of the time! For example, if I see: 0xfce8e8c7f4f7 (cyphertext I see) which was generated by: d e f e n d (message) 0x646566656e64 (message in hex) 0x988d8ea29a93 (pad) Then I know that I'm not going to be attacked. Attack couldn't have had the e8e8, because they threw out those pads.
For example, suppose we take 1024-bit blocks from a physical RNG (which we'll agree is "good", has entropy close to 1024 bits, whatever that means). There are 2^1024 such blocks. Obtain one and apply the magical test---if the block fails, toss it in the bit bucket. Suppose, conservatively, that half the sequences fail. The cryptanalyst now knows that the plaintext cannot be ( failed_pad xor ciphertext ) for any of the 2^1023 failed_pads. Thus, it must be one of the other 2^1023. This is the *only* toehold he gets.
That's plenty big to be a problem. Jon Leonard
"Jon Leonard" writes:
Perry's right: giving up any statistical information is too much.
A slightly contrived example of why tossing out duplicated bytes is bad:
Suppose that a military organization is using this almost one-time-pad system, and my spies tell my they've fallen into the habit of sending "attack" and "defend" as their only 6-byte messages. This isn't a problem with a real one-time pad (except for traffic analysis...), but this lets me determine the message 3.8% of the time!
This could actually be used for traffic analysis in many instances; you could succeed in extracting small amounts of information from the passing data. Any amount of leakage can in some instances be too much... .pm
participants (4)
-
Andrew Loewenstern -
Jon Leonard -
Perry E. Metzger -
Peter Monta