Information Security Stack Exchange is a question and answer site for information security professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
31  
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 at 23:57
4  
I think you may have answered your questions with your last question. – Zymus Feb 5 at 0:09
1  
I assume completely secure would mean the information theoretic definition as opposed to the computational definition. – puzzlepalace Feb 5 at 1:02
13  
"Fully secure" against what attack, exactly? – Michael Kjörling Feb 5 at 13:03
2  
Couldn't resist: xkcd.com/538 I.e. "security" is always relative to the attacker... – thkala Feb 7 at 13:30
up vote 96 down vote accepted

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

share|improve this answer
5  
Isn't it the case that technically nothing is fully secure? – Black Magic Feb 5 at 8:57
47  
@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 at 9:07
13  
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. – Michael Kjörling Feb 5 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 at 12:38
2  
@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 at 13:00

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.

share|improve this answer
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 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 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 at 15:39
5  
@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 at 16:42
6  
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 at 6:12

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.

share|improve this answer
2  
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 at 16:10
    
MIM & Dos are also humorous – Badr Bellaj Feb 5 at 21:24
4  
"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. – Michael Kjörling Feb 5 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 at 0:41

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.

share|improve this answer
    
... key-exchange is problematic at scale. – Trey Blalock Mar 3 at 18:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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