3 ms·

One thing I've never understood about the one-time pad: How do you guarantee the third condition? Wouldn't you eventually run into the birthday problem if you

by cbhl 9y ago

One thing I've never understood about the one-time pad: How do you guarantee the third condition? Wouldn't you eventually run into the birthday problem if you sent enough messages?

ikeboy 9y ago
Use a new one time pad for every message.
- hinkley 9y ago
  Are you suggesting we use the one time pad only one time? Well if it's that important maybe they should put that right in the name...
jaibot 9y ago
Yes, so the rule is slightly misstated. Assuming that your messages are all under n bits and you always use an n-length pad, you will reuse the same pad approximately once every 2^n messages. Not coincidentally, 2^n is also the number of possible one-time pads there are, so your adversary gains no information from this fact.
- dsacco 9y ago
  > Not coincidentally, 2^n is also the number of possible one-time pads there are, so your adversary gains no information from this fact. Yes! And this is what's critical to the success of the one-time pad: you've not just encrypted data, you've encrypted data in such a fashion that (from the attacker's perspective), all plaintexts they recover are equally likely. Cryptanalysis is fundamentally impossible. The information theory is absolutely groovy, but the application of it is unfortunately impractical.
jessriedel 9y ago
Formally, the condition isn't "never use a one-time pad with the same key numbers" it's "make sure the key numbers of each pad are statistically independent of each other". Not that it matters. The sqrt(n) birthday effect isn't sufficient to overcome the exponentially low chance of a one-time pad collision for pads of any substantial size.
- dsacco 9y ago
  > Formally, the condition isn't "never use a one-time pad with the same key numbers" it's "make sure the key numbers of each pad are statistically independent of each other". And to expand on this - this is why it is imperative that a source of true randomness is used as a seed. Pseudorandomness cannot (by definition) satisfy statistical independence. If you don't have a source of true randomness, you've just implemented a stream cipher, not a one-time pad.
PeterisP 9y ago
One-time pad means that you have a limit to how much data you can exchange before the pad is spent - if you send enough messages, then you can't send any more securely until you exchange another one-time pad. You're not likely to get a collision ever because of the typical sizes of one-time pads - birthday paradox matters if the key length is measured in bytes, but not if it's measured in gigabytes, there isn't enough space/time in our universe to expect a collision.

by cbhl 9y ago

One thing I've never understood about the one-time pad: How do you guarantee the third condition? Wouldn't you eventually run into the birthday problem if you sent enough messages?

ikeboy 9y ago

Use a new one time pad for every message.

hinkley 9y ago
Are you suggesting we use the one time pad only one time? Well if it's that important maybe they should put that right in the name...

jaibot 9y ago

Yes, so the rule is slightly misstated. Assuming that your messages are all under n bits and you always use an n-length pad, you will reuse the same pad approximately once every 2^n messages. Not coincidentally, 2^n is also the number of possible one-time pads there are, so your adversary gains no information from this fact.

dsacco 9y ago
> Not coincidentally, 2^n is also the number of possible one-time pads there are, so your adversary gains no information from this fact. Yes! And this is what's critical to the success of the one-time pad: you've not just encrypted data, you've encrypted data in such a fashion that (from the attacker's perspective), all plaintexts they recover are equally likely. Cryptanalysis is fundamentally impossible. The information theory is absolutely groovy, but the application of it is unfortunately impractical.

jessriedel 9y ago

Formally, the condition isn't "never use a one-time pad with the same key numbers" it's "make sure the key numbers of each pad are statistically independent of each other". Not that it matters. The sqrt(n) birthday effect isn't sufficient to overcome the exponentially low chance of a one-time pad collision for pads of any substantial size.

dsacco 9y ago
> Formally, the condition isn't "never use a one-time pad with the same key numbers" it's "make sure the key numbers of each pad are statistically independent of each other". And to expand on this - this is why it is imperative that a source of true randomness is used as a seed. Pseudorandomness cannot (by definition) satisfy statistical independence. If you don't have a source of true randomness, you've just implemented a stream cipher, not a one-time pad.

PeterisP 9y ago

One-time pad means that you have a limit to how much data you can exchange before the pad is spent - if you send enough messages, then you can't send any more securely until you exchange another one-time pad. You're not likely to get a collision ever because of the typical sizes of one-time pads - birthday paradox matters if the key length is measured in bytes, but not if it's measured in gigabytes, there isn't enough space/time in our universe to expect a collision.