38

Is there an encryption algorithm that is completely secure and isn't based on difficult computational algorithms?

If such an algorithm exists, why we don't we use it in SSL/SSH?

Peter Mortensen
  • 895
  • 5
  • 10
SDasd
  • 433
  • 4
  • 7
  • 36
    Why do you think that the algorithms are "difficult"? What do you define as "completely secure"? Once those things are defined, I think you will find that we do use those things in SSL. – schroeder Feb 04 '16 at 23:57
  • 5
    I think you may have answered your questions with your last question. –  Feb 05 '16 at 00:09
  • 1
    I assume completely secure would mean the information theoretic definition as opposed to the computational definition. – puzzlepalace Feb 05 '16 at 01:02
  • 14
    "Fully secure" against what attack, exactly? – user Feb 05 '16 at 13:03
  • You may be interested in quantum cryptography too. Not only is this fully secure; it even allow to detect if someone is eavesdropping! – Bakuriu Feb 06 '16 at 12:40
  • 2
    Couldn't resist: https://xkcd.com/538/ I.e. "security" is always relative to the attacker... – thkala Feb 07 '16 at 13:30
  • 1
    "completely secure" is a meaningless term. And stop to contemplate a security algorithm based on simple computational algorithms - if they are simple for the adversary what value do they have? – MCW Feb 08 '16 at 13:08
  • You can mathematical prove that one time pad ciphers and quantum ciphers cannot be broken. The key exchange for one time pad ciphers is a bit expensive and might be only useful for things like presidential telephones. Quantum cryptography is possible but now widely availalabe yet – BlueWizard Feb 13 '16 at 19:35

4 Answers4

98

Yes, it's called One Time Pad, and we don't use it in SSL/TLS because key-exchange is problematic at scale.

I will point out that with the rapid decline in the price of various types of storage, One Time Pad's use for smaller communications such as e-mails is more practical now than it ever has been simply because the cost of giving someone something like a large USB Flash Drive with a large "pad" on it didn't exist in a practical sense a few years ago. Still, as the price approaches zero, this becomes trivial to do. As storage costs continue to approach zero, this could become more useful for a wide variety of uses in the future, but the key-exchange problem will still exist.

Trey Blalock
  • 14,209
  • 6
  • 45
  • 49
  • 5
    Isn't it the case that technically nothing is fully secure? – Black Magic Feb 05 '16 at 08:57
  • 49
    @BlackMagic Assuming the key is truly random and never reused, a message encrypted with OTP can never be cracked. "Perfect secrecy" means the cipher text gives no information about the plain text (except its maximum length). OTP cannot be brute forced as that will simply reveal all possible texts. Even if you know part of the text that does not help as each piece of the key is independent of the rest. – Schwern Feb 05 '16 at 09:07
  • 16
    OTPs, or at least naiive implementations of OTPs, are however malleable, which means that a part of the message can be changed undetectably. An OTP must be coupled with a MAC (message authentication code) to provide protection against ciphertext modification, but once you have a MAC, chances are pretty good that the combined system no longer possesses the OTP's information-theory confidentiality guarantees because you can then guess keys and try to validate the MAC. – user Feb 05 '16 at 13:01
  • 1
    Comments are not for extended discussion; this conversation has been moved to chat. – Rory Alsop Feb 06 '16 at 12:29
  • 2
    @MichaelKjörling The MAC can be sent as the prefix of the message and encrypted with it. In this way perfect secrecy guarantees that the attacker cannot obtain any knowledge from the message. Sure: he can still randomly change it but now he'd have to do so in a way that make the MAC match, which is pretty much impossible. – Bakuriu Feb 06 '16 at 12:38
  • 4
    @MichaelKjörling The unconditional security of the OTP will be preserved when a MAC is applied as long as you use an unconditionally secure MAC. The first such MAC was published in 1981 by Wegman and Carter. – kasperd Feb 06 '16 at 13:00
  • @Schwern Eve doesnt even have to know the maximum lenght. You can add nulls to ut to stretch it. – BlueWizard Feb 13 '16 at 19:39
  • 1
    @JonasDralle Nulls are necessary to hide the true length of the message. The maximum length is still known because there's a one-to-one mapping between the encrypted data and the original. If you have an OTP key N bytes long you can encrypt, at most, N bytes. – Schwern Feb 13 '16 at 19:55
  • @Schwern alice and bob could use codes to make their message shorter – BlueWizard Feb 13 '16 at 19:57
  • @JonasDralle Yes, the message can always be shorter than the maximum length... though I'm not sure what you mean by "codes". Do you want to discuss this in chat? – Schwern Feb 13 '16 at 20:01
  • 1
    @MichaelKjörling Wegman-Carter MACs provably leak nothing about the plaintext and are unconditionally secure. – forest Jul 12 '18 at 02:54
  • @BlueWizard Then the codes themselves are part of the key, given that you need to share them in advance. I believe "maximum length" should instead be meant to mean "maximum information", since compression is a thing. – forest Jul 12 '18 at 02:56
37

The only theoretical algorithm that can fulfill that is OTP, one-time pad.

See the question How is the One Time Pad (OTP) perfectly secure?.

We don't use it in anything common for a few reasons:

  • Its security depends on having as much truly random data as we have data to transmit, and that random data has already been sent to both parties securely, and is never reused.

    • This is impossible because we don't actually have truly random data.

    • Even with nearly random data, which is difficult to obtain and requires sampling certain aspects of the real world in as unbiased a fashion as possible, this is very expensive - 4 GB of key to watch 4 GB of secure video.

    • Each transmitter/recipient pair should have independent random data.

  • It does not provide any data integrity features in and of itself, while many of our other algorithms and implementations do.

    • @CodesInChaos has mentioned that Polynomical MACs can be used in conjunction with OTP to provide this

We do use OTP in a few rare contexts, but generally only to send a key for one of the more common algorithms.

Anti-weakpasswords
  • 9,980
  • 2
  • 25
  • 53
  • 14
    You can drop the "which is known to day" part. You can prove that any perfectly secure encryption needs a key that's at least as long as the message. So while the details of the algorithm can vary (e.g. you could design it to be stateless or to be still computationally secure on pad reuse), it'll always share the keying requirements of the OTP. – CodesInChaos Feb 05 '16 at 09:40
  • 2
    Also Polynomial MACs are secure against computationally unbounded attackers (but there is an exponentially small chance that the attacker simply gets lucky when forging a tag). You can combine them with an OTP to provide integrity protection. – CodesInChaos Feb 05 '16 at 09:42
  • @CodesInChaos - "which is known today" dropped, thank you - an excellent point. I'll leave the Polynomial MAC discussion to you! – Anti-weakpasswords Feb 05 '16 at 14:32
  • 3
    "4 GB of key to watch 4GB of secure video" True, and if you're somehow securely sending a key that's the same size as the data, you might as well just send the data. – Travis Feb 05 '16 at 15:39
  • 6
    @Travis: The key can be sent days before the data is even generated. Example: a spy drone can contain a 1 TB SSD loaded with an OTP, and use that OTP to securely transmit live video. – MSalters Feb 05 '16 at 16:42
  • 2
    Can we say that OTP is isomorphic to just sending the plaintext over a secure connection, up to time travel? As in, it doesn't spare us from requiring a preexisting secure channel, the channel just doesn't have to last until we have data to transmit. – John Dvorak Feb 05 '16 at 17:35
  • 7
    This is impossible because we don't actually have truly random data. It is in fact possible to generate truly random data using a quantum random number generator. At least according to the Copenhagen interpretation. – Matt Feb 06 '16 at 06:12
  • Isn't the OTP "forwarding" or "pushing" the responsibility for security to the process of previously sharing the OTP? (as @Travis mentioned) – marstato Feb 08 '16 at 14:55
  • 1
    Sure we have truely random data. Or at least we have data that we cannot foresee with cirrent technology. For example radioactive decay – BlueWizard Feb 13 '16 at 19:38
6

In fact, the one-time pad (OTP) encryption technique is the only proven unbreakable encryption system. It is simple to use, it only uses the XOR operation, and is so secure that the ciphertext is literally uncrackable if done correctly.

The dark side is that it requires a lot of pre-shared data which gets used up as you encrypt data. When you run out, you have to share more of this data if you want to keep communicating with that person.

This pre-shared data is the key used for encryption and unencryption. If someone were to intercept a message between you and your target person, they may not be able to get your plaintext out, but if they can keep that message from getting to your target, and do so in a way that you aren’t aware of, they can completely break your communication channel.

Peter Mortensen
  • 895
  • 5
  • 10
Badr Bellaj
  • 349
  • 2
  • 9
  • 3
    I don't see what extra value this answer brings, but i do find this humorous if they can keep that message from getting to your target, and do so in a way that you aren’t aware of this, they can completely break your communication channel. – Pogrindis Feb 05 '16 at 16:10
  • MIM & Dos are also humorous – Badr Bellaj Feb 05 '16 at 21:24
  • 5
    "if they can keep that message from getting to your target, and do so in a way that you aren’t aware of this, they can completely break your communication channel" Cryptography cannot protect you against this type of attack. – user Feb 05 '16 at 21:35
  • 1
    i mean it lead you to this case, it is a result of the pre-shared data use – Badr Bellaj Feb 06 '16 at 00:41
0

As an extension to the one time pad, a currently rarely used but possibly prevalent future technology is quanatum key distribution

The basic idea, is that you can send a one time pad over a quantum channel, where any measurement affects the signal, so any eavesdropping can be detected. Thus if you detect no anomalous readings, no one is eavesdropping and the communication channel is secure. This still does not solve the identification issue, and is thus venerable to man-in-middle attacks when used by itself, but can be used to generate an arbitrarily large one-time-pad if the parties already share a secret.

Rick
  • 143
  • 6
  • ... key-exchange is problematic at scale. – Trey Blalock Mar 03 '16 at 18:25
  • It would be more practical but "less secure" to use QKD to seed a very good CSPRNG and then just use that as an OTP key. Unfortunately, this is about as bad/good as simply using QKD as a key and nonce with say AES-512 in CTR mode and rekeying periodically using all available QKD bandwidth to change the key and nonce. CTR is basically a practical OTP. We don't use OTP because you'd need confidential key material the size of the ciphertext. – dhchdhd Jan 03 '19 at 13:51