5 ms·
> Isn't "unbreakable" a bit of a dirty word in the security community "Dirty" is one way to put it, yes. I'd personally use something like "false god" or "blas
by dsacco 9y ago
> Isn't "unbreakable" a bit of a dirty word in the security community
"Dirty" is one way to put it, yes. I'd personally use something like "false god" or "blasphemy" :). "Unbreakable" is a naive way of describing cryptographic algorithms, because it preempts conversations about intractability assertions or complexity analysis...modern cryptography accepts as a premise that "unbreakable" is not a reasonable goal, which is why we work by quantifying computational cost.
When I see someone use the phrase, "unbreakable cryptography", I mentally discount their authority to speak about cryptography and become more skeptical (this also applies to people who write things like "bank-grade security" or who tell me "AES-256" when I ask them how they're encrypting data, as if the key size is more important than the block cipher mode or confidentiality/authentication construction).
> Is there really such a thing as "unbreakable cryptography"?
A one-time pad, with the following provisos:
1. It has a truly random seed, not a pseudorandom one;
2. It is at least as long as the plaintext;
3. It is never reused (for the same plaintext, in whole or part).
It's straightforward to see why this guarantees information-theoretic security - you have no way of knowing when you've recovered the correct plaintext. There's nothing to brute-force.
In the security community we don't use one-time pads because we dare not touch the sun: they are extremely difficult to implement correctly, and even if you do implement them correctly you have traded off an inordinate amount of practical usability for a relatively small improvement in information theoretic security.
Asking people to 1) use true randomness to seed keys, 2) generate a new secret key for every message, 3) never reuse the same secret key and 4) keep each secret key securely confidential is extremely prone to error. It's often a fetishized ideal among people who first read about it, but in practice it's just not worth it.
- cbhl 9y agoOne 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 agoUse a new one time pad for every message.
- hinkley 9y agoAre 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 agoYes, 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 agoFormally, 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 agoOne-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.
- Animats 9y agoThose are not sufficient conditions for a one-time pad. The entire pad, not just some "seed" has to be random. The pad cannot ever be reused even with a different plaintext. Breaking a one-time pad that's been used twice is not very hard. It's equivalent to recovering two texts which have been XORed together, which is not hard for English. One time pad systems are used regularly for high-security embassy-to-State Department communications. Since there are also secure couriers between those locations, there's a way to distribute key material. With today's storage densities, carrying key material around is easy.
- kierenj 9y agoI don't understand how this is practical. If you have a highly secure mechanism for distributing the ultimate secret - one-time-pads - why not just distribute the messages in this way? Is it just the fact that it would take two trips for the courier? Or that someone would need to intercept both communications (pad, ciphertext)?
- j08ny 9y agoIt's not practical for most cases, but the few very very high-security ones. The pads are distributed beforehand, stored securely and used when a message encrypted to them comes in. So it's just that the message can have OTP security while not taking the time of a courier trip and can be just sent on other somewhat insecure channel.
- PeterisP 9y agoA big benefit is that you can time-shift the distribution of the secret - you can distribute the one-time pad when it's convenient (e.g. when your submarine is at a home port) and be able to send secure messages over insecure channels at any future time.
- dsacco 9y agoYes, this is essentially half the basis for cryptography, of which the one-time pad is one particularly rigid form. If Alice and Bob wish to communicate, they can do so by first verifying each other in person, or with a trusted courier, and from then on can communicate remotely. Alternatively, they can use public-key cryptography to communicate remotely and securely over an insecure channel without requiring face to face contact or a trusted courier.