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?

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

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 actually 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 really exist in a practical sense a few years ago but 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.

  • 5
    Isn't it the case that technically nothing is fully secure? – Black Magic Feb 5 '16 at 8:57
  • 48
    @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 '16 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. – a CVn Feb 5 '16 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 '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 6 '16 at 13:00
36

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.

  • 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 5 '16 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. – CodesInChaos Feb 5 '16 at 9:42
  • 2
    "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 '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 5 '16 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 '16 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.

  • 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 '16 at 16:10
  • MIM & Dos are also humorous – Badr Bellaj Feb 5 '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. – a CVn Feb 5 '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 6 '16 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.

  • ... key-exchange is problematic at scale. – Trey Blalock Mar 3 '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 3 '19 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.