5 ms·

There's only one "unbreakable" encryption, and that's a pair of one time pads with truly random data as long as the message itself. http://www.pro-technix.com/

There's only one "unbreakable" encryption, and that's a pair of one time pads with truly random data as long as the message itself. http://www.pro-technix.com/information/crypto/pages/vernam_base.html http://www.pro-technix.com/information/crypto/pages/vernam_b...

andrewla 13y ago
While this may seem like a tempting statement, it is not really an answer, since "unbreakable" is not really well-defined. Clearly, "truly random" is a bit of a tough one to define. And sending the message length is a bit of an information leak itself. But even putting those aside, there's a bigger flaw. The biggest problem in this mechanism is how does the other party get their one-time pad? An upper bound on the unbreakableness of the entire scheme is the unbreakability of transmitting a one-time pad; and if you can do that, then why not just send the actual message via that mechanism?
- nawitus 13y ago
  "unbreakable" may be not well-defined, but perfect secrecy is[1]. 1. http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
  - JackGibbs 13y ago
    Perfect secrecy refers to the ability to determine any information about the plaintext without decoding it. Not having it can be very useful to an attacker, but that isn't always the case. RSA, for instance, doesn't have perfect secrecy, because it leaks the Jacobi symbol (https://en.wikipedia.org/wiki/Jacobi_symbol https://en.wikipedia.org/wiki/Jacobi_symbol) of the plaintext. However, that information is of limited utility, and it can be shown that determining more useful facets, for instance the parity of the plaintext, requires solving more unfeasible problems.
    - darkmighty 13y ago
      Actually, perfect secrecy refers to the ability to determine any information about the plaintext at all, given arbitrary decoding power. It's quite simple -- it means that given a standard distribution of keys and an a priori distribution over the plain texts the best estimate of the plaintext given the ciphertext is simply the a priori distribution (no additional information). For the binary case, Y(any distribution)+X(uniform)=Z(uniform) (mod 2), so that this is satisfied for any prior.
- cuu508 13y ago
  > why not just send the actual message via that mechanism? suppose you can transmit information securely only for some time. Exchange one time pads ahead of time, and use them later to communicate over insecure channel
  - andrewla 13y ago
    By assumption, the only way to "transmit information securely" is by one-time pads. So...
    - dllthomas 13y ago
      That was not the assumption. The assumption (or assertion) was that one-time pads were the only unbreakable encryption. There are ways of securing things other than encryption (most obviously physical isolation).
      - andrewla 13y ago
        Ach! I let myself get drawn into a semantic argument, and it earned me my first downvotes! My only point was that talking about one-time-pads as "unbreakable" encryption is not a useful discussion, since "unbreakable" and "encryption" need to be better defined. If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system. Only by explicitly defining attack vectors can we really get a good framework for reasoning about cryptography, and even then we know that we can prove an encryption technique is bad. For "goodness", all we can do is increase our confidence, until the day the confidence drops to 0. Anyway, with this last salvo, I'll retreat from this conversation; it's pretty clear to me that my inane ramblings about semantics are as annoying to the community here as they are to me when other people make them.
        hueving 13y ago
        >My only point was that talking about one-time-pads as "unbreakable" encryption is not a useful discussion, since "unbreakable" and "encryption" need to be better defined. No they don't. You are receiving negative feedback because you are trying to adjust definitions that have been well-defined by the crypto community. When talking about the security of an encryption algorithm, the key distribution has absolutely nothing to do with it. Stop conflating the two. >If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system. Would you care to share with us some of these other unbreakable systems? Remember, the keys are the only thing that can be transmitted outside of the channel and they cannot be based on the information being encrypted.
- voidlogic 13y ago
  You give each party a briefcase full of 4 TB hard drives full of random numbers generated from a USB attached atomic decay device. Now for 1,2,10 years depending on your rate of communication you can communicate using the one time pad. >why not just send the actual message via that mechanism? The point is you only have to exchange pads periodically, not every time you communicate.
  - a1a 13y ago
    How do you encrypt the hard drives? I wouldn't trust some keys that had been lying around on an unencrypted hard drive for 1,2,10 years!
    - omh 13y ago
      If I was using one-time-pads I'd probably be using them because I didn't trust encryption, so "unencrypted" wouldn't matter here. In real-world implementations I think the security is probably based around a large number of men with guns.
      - voidlogic 13y ago
        Exactly, men with guns secure the one time pad. The data sent using that pad is secure. Nit: I would consider one time pad to be a method of encryption.
        omh 13y ago
        Nit: I would consider one time pad to be a method of encryption. Ah, true. But the encryption algorithm is much simpler to implement than most :-)
    - admax88q 13y ago
      You don't get it at all.
  - andrewla 13y ago
    I mean, what you're saying here is that in addition to one-time-pad based cryptography, there is a "give a briefcase to the person"-based cryptographic system. In reality, I think lot more briefcase-based transfers are "cracked", as it were, than SSL sessions. My problem is just that the proposed mechanism relies on already having an even more perfect mechanism, and thus cannot be the "only one", but is in fact strictly weaker than this other mechanism. So we have a contradiction, and we can get rid of the notion that there exists such a thing as an "unbreakable" system (or, alternatively, that it is a useful concept)
- TeMPOraL 13y ago
  > why not just send the actual message via that mechanism? If you can, then there's no real need for using a one-time pad. But there's a benefit that comes from a fact that exchanging the random data is a completely separate process in time and space from sending the messages. You can do it once, spending all your resources to secure it. Imagine e.g. two governments establishing a secret emergency line by generating a few terabytes of random data in one physical place and then escorting each copy in armoured trucks to proper communication factilities. BTW. exchanging physical "XOR's" for one-time pad communication is a plot point of Vernor Vinge's "A Fire Upon the Deep".
- mannykannot 13y ago
  You do not actually have to define "truly random". You do have to trust that the mechanism you are using to generate keys (radioactive decay or rolling dice, for example) is unpredictable. There is a more general point here, that sometimes seems to be lost in philosophical arguments: reality doesn't pay any attention to the meaning of words. If "unbreakable" is not well-defined (I am not sure that is so), then it is a problem within the domain of language, not cryptography.
  - aidenn0 13y ago
    Unpredictable and unbiased
- AnthonyMouse 13y ago
  > And sending the message length is a bit of an information leak itself. The known solution to this is to pad messages to some fixed length. The obvious drawback is that you have to choose the fixed length message to be as long as the longest message you may wish to transmit, which could result in having to transmit rather a lot of padding. The equivalent of this for real-time communications is to transmit continually at a fixed bit rate regardless of whether you have any data to send at any given time.
  - Loughla 13y ago
    Congratulations, you just reinvinted numbers stations. Send random data that is probably meaningless, until which point you send real data. Let everyone listen in to the gibberish for 50 years, in the end, only the person with the key knows the message.
- kenjackson 13y ago
  When you transmit the pads may not correspond with when you want the message sent. For example I may be able to send you a one-time pad securely today, but the message I need to tell you ("buy GM stock at 37.82") I won't know until next week -- at which point I may not be able to expediently send you the one-time pad securely.
Xylakant 13y ago
And even this is in practice a problem: How do you distribute and secure the pads? A lot of problems in cryptosystems stem from implementation details - think side-channel attacks, exploits, ...
- kevincrane 13y ago
  Well that's exactly the reason the one-time pad isn't used anywhere. It's perfectly secure but basically impossible to actually implement securely because of key distribution.
- IvyMike 13y ago
  "I know! I'll use a PRNG to create the one-time pad on the fly!"
samatman 13y ago
This singular, provable fact is the basis of the modern Internet. ...we're not on the modern Internet. I'm looking forward to it; it'll be a better place.
mpyne 13y ago
This was actually broken in practice once, by (you guessed it) NSA. They managed to break into part of Soviet VENONA since the demand of OTP keymat during WWII was such that someone took a shortcut and reprinted pages of random numbers. Don't ask me how Cold War-era NSA discovered that without Cray supercomputers everywhere, but even this scheme is difficult to pull off in practice.
- IvyMike 13y ago
  Technically a TTP is not a OTP.
  - mpyne 13y ago
    Yes, that's why I referenced in practice vs. in theory.
klodolph 13y ago
There are two known unbreakable encryption schemes, the other one is Shamir's Secret Sharing.
- rhth54656 13y ago
  I believe you misrepresented that algorithm. While it is true that Shamir's Secret Sharing is unbreakable if you split the actual clear text among participants, it is not used that way. The actual use is to use SSS to encrypt and distribute the key used to encrypt the clear text.
  - klodolph 13y ago
    I think you are describing a larger encryption scheme that uses SSS as a component. I am talking about SSS itself, which is unbreakable, from an information theoretic standpoint. You can use SSS to split the clear text among all participants, even if most people don't use it that way to construct larger systems.

andrewla 13y ago

While this may seem like a tempting statement, it is not really an answer, since "unbreakable" is not really well-defined. Clearly, "truly random" is a bit of a tough one to define. And sending the message length is a bit of an information leak itself. But even putting those aside, there's a bigger flaw. The biggest problem in this mechanism is how does the other party get their one-time pad? An upper bound on the unbreakableness of the entire scheme is the unbreakability of transmitting a one-time pad; and if you can do that, then why not just send the actual message via that mechanism?

nawitus 13y ago
"unbreakable" may be not well-defined, but perfect secrecy is[1]. 1. http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
- JackGibbs 13y ago
  Perfect secrecy refers to the ability to determine any information about the plaintext without decoding it. Not having it can be very useful to an attacker, but that isn't always the case. RSA, for instance, doesn't have perfect secrecy, because it leaks the Jacobi symbol (https://en.wikipedia.org/wiki/Jacobi_symbol https://en.wikipedia.org/wiki/Jacobi_symbol) of the plaintext. However, that information is of limited utility, and it can be shown that determining more useful facets, for instance the parity of the plaintext, requires solving more unfeasible problems.
  - darkmighty 13y ago
    Actually, perfect secrecy refers to the ability to determine any information about the plaintext at all, given arbitrary decoding power. It's quite simple -- it means that given a standard distribution of keys and an a priori distribution over the plain texts the best estimate of the plaintext given the ciphertext is simply the a priori distribution (no additional information). For the binary case, Y(any distribution)+X(uniform)=Z(uniform) (mod 2), so that this is satisfied for any prior.
cuu508 13y ago
> why not just send the actual message via that mechanism? suppose you can transmit information securely only for some time. Exchange one time pads ahead of time, and use them later to communicate over insecure channel
- andrewla 13y ago
  By assumption, the only way to "transmit information securely" is by one-time pads. So...
  - dllthomas 13y ago
    That was not the assumption. The assumption (or assertion) was that one-time pads were the only unbreakable encryption. There are ways of securing things other than encryption (most obviously physical isolation).
    - andrewla 13y ago
      Ach! I let myself get drawn into a semantic argument, and it earned me my first downvotes! My only point was that talking about one-time-pads as "unbreakable" encryption is not a useful discussion, since "unbreakable" and "encryption" need to be better defined. If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system. Only by explicitly defining attack vectors can we really get a good framework for reasoning about cryptography, and even then we know that we can prove an encryption technique is bad. For "goodness", all we can do is increase our confidence, until the day the confidence drops to 0. Anyway, with this last salvo, I'll retreat from this conversation; it's pretty clear to me that my inane ramblings about semantics are as annoying to the community here as they are to me when other people make them.
      - hueving 13y ago
        >My only point was that talking about one-time-pads as "unbreakable" encryption is not a useful discussion, since "unbreakable" and "encryption" need to be better defined. No they don't. You are receiving negative feedback because you are trying to adjust definitions that have been well-defined by the crypto community. When talking about the security of an encryption algorithm, the key distribution has absolutely nothing to do with it. Stop conflating the two. >If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system. Would you care to share with us some of these other unbreakable systems? Remember, the keys are the only thing that can be transmitted outside of the channel and they cannot be based on the information being encrypted.
voidlogic 13y ago
You give each party a briefcase full of 4 TB hard drives full of random numbers generated from a USB attached atomic decay device. Now for 1,2,10 years depending on your rate of communication you can communicate using the one time pad. >why not just send the actual message via that mechanism? The point is you only have to exchange pads periodically, not every time you communicate.
- a1a 13y ago
  How do you encrypt the hard drives? I wouldn't trust some keys that had been lying around on an unencrypted hard drive for 1,2,10 years!
  - omh 13y ago
    If I was using one-time-pads I'd probably be using them because I didn't trust encryption, so "unencrypted" wouldn't matter here. In real-world implementations I think the security is probably based around a large number of men with guns.
    - voidlogic 13y ago
      Exactly, men with guns secure the one time pad. The data sent using that pad is secure. Nit: I would consider one time pad to be a method of encryption.
      - omh 13y ago
        Nit: I would consider one time pad to be a method of encryption. Ah, true. But the encryption algorithm is much simpler to implement than most :-)
  - admax88q 13y ago
    You don't get it at all.
- andrewla 13y ago
  I mean, what you're saying here is that in addition to one-time-pad based cryptography, there is a "give a briefcase to the person"-based cryptographic system. In reality, I think lot more briefcase-based transfers are "cracked", as it were, than SSL sessions. My problem is just that the proposed mechanism relies on already having an even more perfect mechanism, and thus cannot be the "only one", but is in fact strictly weaker than this other mechanism. So we have a contradiction, and we can get rid of the notion that there exists such a thing as an "unbreakable" system (or, alternatively, that it is a useful concept)
TeMPOraL 13y ago
> why not just send the actual message via that mechanism? If you can, then there's no real need for using a one-time pad. But there's a benefit that comes from a fact that exchanging the random data is a completely separate process in time and space from sending the messages. You can do it once, spending all your resources to secure it. Imagine e.g. two governments establishing a secret emergency line by generating a few terabytes of random data in one physical place and then escorting each copy in armoured trucks to proper communication factilities. BTW. exchanging physical "XOR's" for one-time pad communication is a plot point of Vernor Vinge's "A Fire Upon the Deep".
mannykannot 13y ago
You do not actually have to define "truly random". You do have to trust that the mechanism you are using to generate keys (radioactive decay or rolling dice, for example) is unpredictable. There is a more general point here, that sometimes seems to be lost in philosophical arguments: reality doesn't pay any attention to the meaning of words. If "unbreakable" is not well-defined (I am not sure that is so), then it is a problem within the domain of language, not cryptography.
- aidenn0 13y ago
  Unpredictable and unbiased
AnthonyMouse 13y ago
> And sending the message length is a bit of an information leak itself. The known solution to this is to pad messages to some fixed length. The obvious drawback is that you have to choose the fixed length message to be as long as the longest message you may wish to transmit, which could result in having to transmit rather a lot of padding. The equivalent of this for real-time communications is to transmit continually at a fixed bit rate regardless of whether you have any data to send at any given time.
- Loughla 13y ago
  Congratulations, you just reinvinted numbers stations. Send random data that is probably meaningless, until which point you send real data. Let everyone listen in to the gibberish for 50 years, in the end, only the person with the key knows the message.
kenjackson 13y ago
When you transmit the pads may not correspond with when you want the message sent. For example I may be able to send you a one-time pad securely today, but the message I need to tell you ("buy GM stock at 37.82") I won't know until next week -- at which point I may not be able to expediently send you the one-time pad securely.

Xylakant 13y ago

And even this is in practice a problem: How do you distribute and secure the pads? A lot of problems in cryptosystems stem from implementation details - think side-channel attacks, exploits, ...

kevincrane 13y ago
Well that's exactly the reason the one-time pad isn't used anywhere. It's perfectly secure but basically impossible to actually implement securely because of key distribution.
IvyMike 13y ago
"I know! I'll use a PRNG to create the one-time pad on the fly!"

samatman 13y ago

This singular, provable fact is the basis of the modern Internet. ...we're not on the modern Internet. I'm looking forward to it; it'll be a better place.

mpyne 13y ago

This was actually broken in practice once, by (you guessed it) NSA. They managed to break into part of Soviet VENONA since the demand of OTP keymat during WWII was such that someone took a shortcut and reprinted pages of random numbers. Don't ask me how Cold War-era NSA discovered that without Cray supercomputers everywhere, but even this scheme is difficult to pull off in practice.

IvyMike 13y ago
Technically a TTP is not a OTP.
- mpyne 13y ago
  Yes, that's why I referenced in practice vs. in theory.

klodolph 13y ago

There are two known unbreakable encryption schemes, the other one is Shamir's Secret Sharing.

rhth54656 13y ago
I believe you misrepresented that algorithm. While it is true that Shamir's Secret Sharing is unbreakable if you split the actual clear text among participants, it is not used that way. The actual use is to use SSS to encrypt and distribute the key used to encrypt the clear text.
- klodolph 13y ago
  I think you are describing a larger encryption scheme that uses SSS as a component. I am talking about SSS itself, which is unbreakable, from an information theoretic standpoint. You can use SSS to split the clear text among all participants, even if most people don't use it that way to construct larger systems.