29

I'm currently reading about one time pad encryption, and I have a question. They say OTP encryption is unbreakable, and this can be proved mathematically. This is provided that the key used is truly random and is used only one time, right? What if I come with a whole system (can be software or hardware or a combination of both) to force these two conditions? Will I have the best & ideal encryption solution?

Say for example the two sides willing to exchange information are getting the keys by connecting to a server that is online all the time. The server will ensure the keys generated are random, and will ensure that a key is never used again. The users at each side will only have to have an internet connection and a mechanism to exchange information. The information will travel via the internet encrypted using the one time pad key generated randomly by the server.

Am I making any sense here? I just started reading about one time pad, and started wondering about this. There are many websites that will tell you that one time pad isn't practical at all, because you can't really come up with a truly random number or something like this.

Addition:

Do these guys offer anything special in key distribution? They say they have perfected implementing OTP over time.

http://www.mils.com/en/technology/unbreakable-encryption/#1

Improve this question
9
  • 24
    If used properly, the best security system is telling the other party whatever you have to say to them, in person, with no one else around in a room you've personally swept for recording devices. The reason we don't do that is that we have to worry about practicality - a OTP only works in very specific circumstances, which alone makes it suboptimal.
    – cpast
    Feb 11, 2015 at 20:56
  • 53
    "Say for example the two sides willing to exchange information are getting the keys by connecting to a server that is online all the time." Woah, hold on a second there. How exactly are you securing that connection? With a different one time pad? How did the clients obtain that pad? See the problem?
    – Ajedi32
    Feb 11, 2015 at 21:02
  • 4
    'Best' is subjective. It all depends on one's requirements. Speed of encryption, tools available, resistance to cracking, ease of key exchange... the list goes on.
    – BAR
    Feb 11, 2015 at 21:38
  • 8
    Remember what the fundamental principle of cryptography is: you can leverage the secrecy of a key into the security of a message against certain attacks. Newcomers to crypto often fall in love with the mathematics and gloss over the significant difficulties in that "the secrecy of the key" part.
    – Eric Lippert
    Feb 11, 2015 at 23:57
  • 5
    You can't currently exchange a OTP over the internet and still have the security of a OTP. The security would be limited to whatever method you used to exchange the key. This isn't to say a OTP is useless: in certain applications it is the best choice. I believe so-called 'numbers stations' still broadcast messages using a OTP to encrypt the message. If an OTP is used then it is usually exchanged by hand, and it the responsibility of each party to keep it secure.
    – Ananke
    Feb 12, 2015 at 17:50

7 Answers 7

Reset to default
84

Key distribution is the problem.

In your scenario, you use a server to communicate the one-time pads to the users. But how is that communication protected? Not by a one-time pad, or it wouldn't be necessary. Let's say it's SSL with AES 128. Then, wham, your cryptosystem is as secure as SSL with AES 128 - pretty secure, but not as secure as a one-time pad.

The mils guys you reference appear to be offering physical devices which you load a one-time keystream onto (and can use it from). Again, key distribution is a problem. You could buy two hard drives, load terabytes of keystream on them, and send one to your buddy... how? Do you trust USPS? Fedex? Courier? Diplomatic pouch? All of these can be compromised. The only perfectly encrypted way to send them would be to encrypt them with a one-time pa... crap, it happened again.

Improve this answer
14
  • 6
    @SpencerDoak But then you are only as secure as the Key used for the exchange - and then you wouldn't need the server at all and can exchange keys directly... And then you start worrying about authentication and MITM...
    – Falco
    Feb 12, 2015 at 10:14
  • 4
    There is a (still fairly theoretical) answer to this problem: entangled photons. Quantum Crypto doesn't allow us to directly encrypt a message, but it does allow us to (slowly) distribute a key. OTP is the obvious encryption method to be used with such keys.
    – MSalters
    Feb 12, 2015 at 11:01
  • 1
    @MSalters And there are already effective attacks (plural, two that I know of off the top of my head) against quantum entanglement (or at the very least, existing crypto systems using quantum entanglement). So that's not a solution either.
    – HopelessN00b
    Feb 12, 2015 at 14:01
  • 1
    @SeanPedersen The problem with using that for a OTP is that you need to use one bit of OTP key material for each bit you encrypt. So if you want to encrypt 1024 bits of your next OTP, you have to use 1024 bits of your current one, so there's really no point in doing so.
    – cpast
    Feb 14, 2015 at 3:25
  • 2
    @gowenfawr I think you're overstating the key distribution problem. There absolutely are situations where you have a better ability to keep physical media secure than an electronic communication; if you give your spy a pack of OTPs in person, or if you fly a tape accompanied at all times by trusted courier (that's not an unusual way to carry small diplomatic pouches, and the courier can report if the pouch was opened so you can throw out that pad), you can find yourself in a situation where you trust your key distribution as much as you trust the other side to not share the message.
    – cpast
    Feb 14, 2015 at 3:29
31

No, because you misunderstand the meaning of "best" in a security context. Contrary to popular opinion, "most secure" and "best" are not synonyms, rather, security is entirely about balancing usability and security. It is about risk management.

The most secure drive on the planet is writing to DevNull (the bit bucket) on the bottom of the ocean in a locked box in a pile of concrete, in a faraday cage, sunk in lava with no cables or wires to it. Absolutely nobody will ever get any data from it, but legit users will never get any data from it either.

One time pads do have the luxury of being provably impossible to break if used correctly, however they are cumbersome to use. If they were the "best" option, then none of the other systems we know of today would exist as they almost all came about after the idea of the one time pad (which is a truly ancient concept.)

Rather, the best option is the one which mitigates your risks to acceptable levels while also maintaining an acceptable level of usability. In many cases, the best security may well be no security. For example, I don't care if you know my cookie recipes, so putting any effort to protect them would reduce usability unnecessarily. I do care if my cooking recipes get lost, so I may want to store multiple copies and back them up somewhere, but I wouldn't access control them as it would be a waste of my time.

The same thought process is no less true for high security situations than for my cooking recipes. It comes down to analyzing the risk as they apply to me (Oreo may care more about protecting their recipe) and then deciding what is my best option. It is different for everyone and every situation and there is no universal answer.

Improve this answer
5
  • 2
    +1 for "legit users will never get any data from it either" And the lava, of course.
    – Kzqai
    Feb 13, 2015 at 0:47
  • 1
    @Hopelessn00b - Ok, re-reading your comment from earlier, I think I get what you are saying about OTP not maintaining perfect information security (sorry, it is 2am here). It does leak that you may have sent a message (but you may not have). But that in no way aids in breaking the cryptography itself. My statement is very clearly about being "impossible to break", not "impossible to make any observation about your action". There is no information leaked which is useful in breaking the cryptographic protection of the message.
    – AJ Henderson
    Feb 14, 2015 at 7:16
  • 1
    Oh, yes, there you go... that's what I was trying to get at. Not having perfect information security means that even the protection of perfect crypto won't perfectly protect your information, so even without breaking the crypto, some information can be gleaned. For some reason, I inferred an implication in your post that wasn't there about a properly implemented OTP equating to perfect information security.
    – HopelessN00b
    Feb 14, 2015 at 7:24
  • 1
    That leakage that you may have sent a message, is part of the reason some people advocate using crypto all the time. If you only use it for stuff that you really want to hide, then Eve can safely assume that she's just found something more interesting than your cookie recipe.
    – cHao
    Feb 14, 2015 at 13:32
  • 1
    @chao it is worth pointing out that using crypto all the time doesn't hide that you sent a message, it just hides if it is interesting. Also, otp isn't limited to the Internet so it could be used through covert channels that are harder to track to you.
    – AJ Henderson
    Feb 14, 2015 at 15:38
29

No. Not only does a one time pad suffer from secure key distribution problems Mike and gowenfawr mentioned in their answers but:

Even if if you did have a mechanism to securely distribute keys, the one time pad (by itself) has no mechanism for ensuring integrity. The ciphertext is what we call "malleable" meaning that it can be manipulated by an attacker to modify the plaintext message in predictable, undetectable ways.

So, even though the one-time-pad offers information theoretic perfect secrecy, it is not, by itself a secure cipher, and in the real world, easy to use authenticated ciphers with reasonably sized keys such as AES-CTR-HMAC or AES-GCM are clearly better.

Improve this answer
31
  • 4
    True, OTP is meant to provide guaranteed secrecy, not guaranteed integrity. I don't think the attacker can modify the plaintext in a predictable way though unless the attacker knows (the corresponding part of) the plaintext message.
    – Ajedi32
    Feb 11, 2015 at 22:00
  • 5
    @Ajedi32 Yes, and in the real world in which we live, and in which our ciphers must work, attackers frequently do.
    – Xander
    Feb 11, 2015 at 22:02
  • 3
    @Xander how is it vulnerable to known-plaintext attacks?
    – user253751
    Feb 12, 2015 at 0:02
  • 4
    @Xander why would you send the hash unencrypted ??? You compress the original message, hash it and then encrypt compressed original+hash with OTP. I want to see the attack which changes the random bitfield in a way that the subsequent decompression and hash-check works...
    – Falco
    Feb 12, 2015 at 10:16
  • 3
    I think what Xander is trying to say, that if you know both the plaintext and the crypttext, then you can calculate the OTP from them, and easily do a MITM attack. The other end will have no way of knowing that the message was tampered with, as it will perfectly decrypt with the OTP code.
    – SztupY
    Feb 12, 2015 at 10:58
8

You are trying to compare a Cryptographic Primitive and compare it to Cryptographic system. This is really comparing apples and oranges.

Cryptographic Primitives are put together to create a Cryptographic system, and you can only evaluate the security of a system once you understand the Use Cases and environment that the system operates in, including attackers, users, protocols on the wire, storage mechanisms, avenues of compromise, availability requirements, number of users, nodes, networks between, dependent services etc.

So to your Question:

So outside the context of the One Time Pad primitive, the system should probably introduce other techniques/primitives to support the following requirements.

  • Integrity of Message (Checksums, Signing)
  • Ensure synchronisation to avoid DOS. (An Attacker might introduce a bogus message to de-synchronises the communication between the parties).
  • Stop Man in the Middle from Changing a single bit in transit (could change the meaning of a partially known plaintext by flipping one bit. i.e. "LaunchMissiles=0" versus "LaunchMissiles=1"
  • Stop replay attacks ("Attack at Dawn" replayed three days later)

And Other Optional Requirements

  • Sender Verification (Signing)
  • Receiver Verification (Certificates)

So you could only attempt to evaluate the security of a Crypto-System once it is reasonably articulated.

Improve this answer
4
  • Wouldn't "stop replay attacks" follow naturally from "never reuse key material" which is an absolute requirement for the OTP to be secure in the first place? Any message that uses overlapping key material should be thrown out as bogus without even being looked at any further than that.
    – user
    Feb 14, 2015 at 17:04
  • Replay attacks can reuse previously valid messages, like the "Attack at Dawn" message that the evil villain resends to the recipient three days later. The message has metadata to ensure that the correct part of the OTP is used for decryption.
    – Andrew Russell
    Feb 15, 2015 at 20:13
  • 1
    Exactly. The message metadata includes some sort of pointer into the key material (a starting location in the pad, if you will) and the message length. If that combination indicates an overlap with key material known to the recipient to have been used previously, the message should be discarded; it's either a replay, or someone doesn't know how to use an OTP securely.
    – user
    Feb 15, 2015 at 21:47
  • Hi @MichaelKjörling all of the techniques you mention are outside the scope of the One Time Pad primitive. Note that you introduce another vulnerability above when you consider an attacker conducting a denial of service attack on the communication by forcing the one time pad to be marked as "used".
    – Andrew Russell
    Apr 1, 2015 at 4:20
5

The problem with a one-time pad is distributing it to both parties. You can't just put it on a server for them both to download, because if you had a secure channel to do that then the two parties could just use that secure channel to communicate anyway. You pretty much have to get both parties physically together, which is obviously very limiting.

Improve this answer
3
  • 4
    Key distribution is a problem in some cases, but not all; it's not uncommon for two parties to have a secure communications channel before acquiring some information they'll want to transmit, but for the channel to be unavailable by the time they have the information to be transmitted. OTP could be useful in such cases if other ciphers weren't essentially as good, and if the channel that would be available would be susceptible only to passive listening attacks. I think a much more important aspect of OTP is the one mentioned by Xander.
    – supercat
    Feb 11, 2015 at 21:27
  • 4
    @supercat OTP has, in fact, historically been used in exactly that kind of situation -- you can send a new tape via diplomatic courier on weekly flights to Moscow, and then not worry about key distribution when you're almost ready to launch nukes. Tampering is really not practical in that kind of situation (you need to know the contents of the message to effectively tamper with it), so it worked well enough in the Cold War.
    – cpast
    Feb 12, 2015 at 0:03
  • @cpast: In some situations adversaries would have no knowledge of messages. In others, however, adversaries might be able to guess. For example, I read that in WWII there was a German desert base that allies were supposed to stay far away from because its predictable weather reports formed a useful crib. If they'd been using OTP, someone who could intercept the transmission could have substituted any other desired message instead.
    – supercat
    Feb 12, 2015 at 16:00
5

An enduring problem with all encryption is trust. You have to trust that the person you are sending a message to is on your side and won't deliver the message or key to someone who shouldn't have it. You have to trust that the people who invented the encryption scheme you are using didn't include a backdoor or a flaw on accident. With OTP, you have the problem of trust with the recipient, but if you cannot give the key to the recipient yourself physically, you now have to put trust in a 3rd party entity that can deliver the key to the recipient. This problem still exists today with modern encryption as well as authentication.

If I was a potential user, I would never put my trust in 3rd party that would generate a key and transmit it over a network connection. There is also no way for a user to ensure that you are generating truly random keys or if you have been compromised. It is definitely not proper use of OTP, as encryption is only as strong as its worst weakness. If you are sending the key over the internet, you've lost any benefit that real OTP can provide and you might as well go with AES-256.

I think it is safe to say that OTP is technically the best transport encryption, the word "best" referring to security. This does not mean that it's "best" for most use cases, and OTP has some serious negatives. The key must be stored somewhere, and this means the key can fall in to the wrong hands. Modern block ciphers usually have shorter keys that a human being can memorize, thus making it much harder for a 3rd party to extract them. It's also really hard to poorly implement something like AES given the right software.

What you can count on more than the security of OTP is the laziness of human beings; we are naturally driven towards doing what is easiest, and this has historically led to people making some really bone-headed decisions that cost them the security of their communication channel. Sometimes lazy humans decide to re-use keys once their key or code book has run out and they don't have the means to generate & transport a new one. The result of this can be much worse than ceasing communication entirely.

Define best, and the answer may be yes or no.

Improve this answer
0
0

The main problem is the secure key exchange! If you can somehow connect to an always online server and can communicate with this server 100% secure - why don't you just relay your message over that server?

A perfectly valid scenario is the following: You meet someone in Person and exchange OTPs with him. After that you can communicate safely with him as long as the OTPs last. To ensure integrity of the messages and you will add N random bytes to your plaintext and then hash everything before encrypting with the OTP (I would usually also compress plaintext before encryption to ensure smaller size and higher information density). This will ensure authentication and encryption at once. Because authentication is in essence just verifying the other party knows some secret, which only he can know. But with symmetric secret keys the key is already a secret which only the two of you know, so if a message successfully decrypts with the shared secret key and is still intact (decompress + check hash) than integrity and authentication have been verified.

But if you want to use OTP against brute Force approaches, you can just as well use a big enough symmetrical encryption (like AES) which is also pretty infeasible to break. The interesting part of crypto is key-exchange. How can I do this whole encryption/authentication without meeting with everyone in person I want to communicate with securely? This is why asymmetrical encryption exists.

So OTP solves a problem pretty good which is already solved good enough (symmetrical encryption) but doesn't solve the real problems at all, which are the reason for asymmetrical encryption!

Improve this answer
9
  • 2
    I doubt that "compression + hash" is really a way to provide integrity comparable to the security of the OTP. I'm not sure what the use of the compression step is supposed to be, and the hash alone doesn't provide protection against a known-plaintext MiTM attack. You should at least use a MAC (with additional key input), and I think there are MAC algorithms which have a similar theoretical protection level as OTP ... I would have to look that up, though.
    – Paŭlo Ebermann
    Feb 12, 2015 at 11:24
  • Compression will save you bytes of your OTP and it will raise information-density making guessed-plaintext attacks harder. Furthermore a perfect encrypted hash is a really good way to protect against most attacks. But against known plaintext you would need an additional random component. Simply add N Random bytes to the plaintext before hashing where N is the hash-length. This will even make known plaintext attacks infeasible
    – Falco
    Feb 12, 2015 at 11:44
  • 2
    @Falco If the attacker knows the plaintext, then they know the hash of the plaintext and can replace both plaintext and hash with their own plaintext and hash. A MAC is not "a hash encrypted with an individual key;" not all MACs even use hashes, and HMAC (which does) is H(k||H(k||M)), not E_k(H(M)), and encrypting a hash with a malleable encryption system can't produce a MAC. MACs have to be existentially unforgeable under known plaintext attacks -- if an attacker can get you to MAC as much as he wants, he can't feasibly fake any message-MAC pair that you didn't MAC for him.
    – cpast
    Feb 12, 2015 at 16:34
  • 1
    @Falco Where'd we get a salted hash? Salts are used in password hashes, not elsewhere, and are not secret. If you mean "I have a secret thing that I add to the message before hashing it," then you're not doing "hash and encrypt the hash". Incidentally, the point of HMAC is to work around certain issues with Merkle-Damgard hashes that makes H(k||plaintext) utterly unsuited for a MAC; that's why it hashes twice (with SHA-3, you can do H(k||plaintext), but that's not "do a hash and encrypt it," that's "have a secret key and use it in the hash itself" -- again, hashes don't generically have salts)
    – cpast
    Feb 12, 2015 at 16:57
  • 1
    @Falco Using a secure hash function in that way is not sufficient for a perfectly secure MAC. For instance, the very common Merkle-Damgard family of hashes can't possibly provide perfect security with your construction: if I find a collision in the hash where the messages M and N are the same length (which I can do, because I have infinite computing power in perfect security analysis), and get M to be encrypted and MACed by you, I can swap out N for M and get a new valid message. Perfectly secure MACs exist. Your algorithm is not among them, with what you've said so far.
    – cpast
    Feb 13, 2015 at 0:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .