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?

8
  • 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 4, 2016 at 23:57
  • 5
    I think you may have answered your questions with your last question.
    – user64273
    Feb 5, 2016 at 0:09
  • 1
    I assume completely secure would mean the information theoretic definition as opposed to the computational definition. Feb 5, 2016 at 1:02
  • 14
    "Fully secure" against what attack, exactly?
    – user
    Feb 5, 2016 at 13:03
  • 2
    Couldn't resist: xkcd.com/538 I.e. "security" is always relative to the attacker...
    – thkala
    Feb 7, 2016 at 13:30

4 Answers 4

99

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.

12
  • 5
    Isn't it the case that technically nothing is fully secure? Feb 5, 2016 at 8: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 5, 2016 at 9: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 5, 2016 at 13:01
  • 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 6, 2016 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 6, 2016 at 13:00
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.

9
  • 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. Feb 5, 2016 at 9: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. Feb 5, 2016 at 9:42
  • 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 5, 2016 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 5, 2016 at 16:42
  • 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 6, 2016 at 6:12
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.

4
  • 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 5, 2016 at 16:10
  • MIM & Dos are also humorous Feb 5, 2016 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 5, 2016 at 21:35
  • 1
    i mean it lead you to this case, it is a result of the pre-shared data use Feb 6, 2016 at 0: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.

2
  • ... key-exchange is problematic at scale. Mar 3, 2016 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 3, 2019 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.