78

I had a job interview yesterday where they asked what the only scenario where a one-time pad can be broken would be, my answer to which was "when the key distribution process is not secure enough".

They praised my answer, but they asked me another question: Why would you even use a one-time pad if the key distribution is 100% secure? Why not simply send the plain-text message since you are sure that distribution is 100% secure?

What is the correct answer to that question?

  • 1
    I'm not sure what the definition of "secure channel" entails, but the key distribution is in one direction (A -> B) and the message is in the other (B -> A). – Bergi Jun 11 '16 at 19:17
  • 5
    bad key generation can be problematic as well, see VENONA et al – dandavis Jun 12 '16 at 3:12
  • 2
    It could be that you want someone to waste resources trying to break your code (not knowing it is an OTP) on the insecure channel. – mathreadler Jun 12 '16 at 13:47
  • 6
    "100% secure" isn't something that actually exists, which is worth keeping in mind. – HopelessN00b Jun 13 '16 at 14:32
  • 3
    Reusing an OTP is superbad even if the length isn't known especially if the stream is uncompressed or has structure, eg headers. If you XOR at each shift in turn then you'll get a dip in 1's when the pad is reused. Bits set at A will correlate with bits set at B, so A+B will have more zeros, so (A+K)+(B+K) = A+B will have more zeros too. – Dan Sheppard Jun 14 '16 at 18:08

10 Answers 10

161

You can distribute the key now and send the message later.

Suppose you are a spy sent on a mission behind enemy lines. You take the key with you (secure distribution) and when you discover a secret you can securely send it using the One-Time pad.

  • is the difference between the size of a key and an actual message also a valid point? – user13267 Jun 13 '16 at 0:08
  • 28
    @user13267 Not for a one-time pad. An OTP key must be at least as long as the message; that's the whole point of the system. – cpast Jun 13 '16 at 1:35
  • 4
    @cpast Which is why spies frequently deploy with large OTPs to allow them to send secure messages later. The key distribution in this analogy would be whatever process you have for getting the OTP in the hands of your spy (and a handler or whomever he'd be communicating with). – HopelessN00b Jun 13 '16 at 14:40
  • 13
    The Moscow-Washington hotline (called the "red phone", but never actually a telephone) is another good example. (It is reported that this actually used OTPs, at least when first set up.) They exchanged OTPs via diplomatic bag from time to time - very secure, but slow and having to be scheduled in advance. But having done that, the hotline could be used the moment it became necessary, which was the whole point. – zwol Jun 13 '16 at 20:24
  • 1
    Another great example is SIGSALY from World War II as described in 99% Invisible's episode [Vox Ex Machina])99percentinvisible.org/episode/vox-ex-machina). It used records with random noise as one time pads to encrypt phone calls between the white house and allied leaders around the world. The records would be securely sent ahead of time. They would be destroyed after the communication ended to ensure forward secrecy. – David Jun 14 '16 at 13:10
50

That you can distribute something securely today, doesn't guarantee you can do it tomorrow - or next week or next year.

Also, your secure channel used to distribute the key may have limitations. Perhaps it depends on some person actually travelling between point A and B... Perhaps it's only available at certain times - e.g. weekends or during winter... Perhaps its capacity is very limited - maximum size per message and/or total messages that can be sent (e.g. it'll look suspicious if used too often with too much)... You may also want to "save" that channel for sending physical items (like OneTime-Pads or virus-samples), that actually can't be transmitted using radio or Internet - unlike text and images...

But the biggest obstacle is probably the time-aspect. Intelligence - the type spies gathers, and which are used in war and politics - has a very limited shelf-life. If you can't get the information out immediately, it looses its value - either because the slight head-start is gone, because whatever it warned about has happened, or because the same information trickles in from other sources.

So using the safe channels of communications - bringing it personally, couriers, letters past by officers on ship or planes, relaying the information through a chain of people - are probably all too slow. That leaves the fast - but unsafe and easily monitored - methods like radio, telegraph, telephone and the Internet. Through these insecure channels the information can be sent very quickly, but they're not safe... So you encrypt the information first, with the one-time pad you've gotten through the guaranteed secure channel.

And unlike your secure channel, it's almost 100% guaranteed that phones, radio and the Internet will be available also next year.

  • 7
    If capacity is limited then OTP doesn't work as OTP needs a key the size of the message and the same key can not be used for multiple messages, so we need enough key to cover all future messages before next key refresh (larger than the messages). – ewanm89 Jun 12 '16 at 16:19
  • 3
    @ewanm89 I was referring to capacity-problems with the "secure channel" - the one used to carry the OneTime-pad in the first place. By definition, it wouldn't be necessary to encrypt the message if it was sent through a guaranteed secure channel. However that channel may still pose capacity-limitation on the medium sent: Maybe it's a courier with a hollow shoe-heel that can only take ten sheets of paper. Maybe it's a way to smuggle one microfilm - or one memory-card. Maybe - to go old school - it's a carrier-pigeon which can only carry one small sheet of paper. OTP+radio no such limit! – Baard Kopperud Jun 12 '16 at 18:31
  • 8
    Yes, but the OTP itself must be sent by such a secure channel. When using an OTP you are sending equal or more data via that secure channel than sending the message directly, so capacity can not be the issue for why not to use that secure channel to send messages direct. The rest is fine, and time limits or not having reliable access to that secure channel are valid reasons to use OTP rather than the secure channel. – ewanm89 Jun 12 '16 at 18:38
  • Now you might want to add, if the secure channel is handing the information over when you get back to HQ and you are in enemy territory, well there is no guarantee you'll even make it back, better to encrypt and send to HQ by radio now rather than hand it over in person later when you might be shot before getting there. – ewanm89 Jun 12 '16 at 18:42
  • 4
    I'm not saying the message would be longer, the key has to be that long or longer and I'm directly pointing out capacity of secure channel is not a reason why OTP would be used instead as the question asks, every other reason in the answer is sound. Yes, the common method would be to take it out with you as the secure channel which is covered by all the time reasons given. – ewanm89 Jun 12 '16 at 21:16
30

There are some practical scenarios, where you exchange a key and only know, that it was not intercepted (i.e. the exchange was 100% secure) after you sent it. If you would have directly transmitted the secret message, it could have been compromised, but since you only exchanged the key, you can just discard it. This is by the way the idea of quantum cryptography.

Another characteristics of quantum cryptography is, that you are not able to choose the key. It is just random and contains no information by itself. In fact you aren't even able to send any non random-generated information through the 100% secure quantum channel, which means you couldn't send your secret message directly. If you want to learn more about the subject I can recommend the Wikipedia page about Quantum key distribution.

  • 2
    Good point about quantum key distribution. – Johannes Kuhn Jun 12 '16 at 14:13
  • While this is good information to have, I'm not sure this is a practical scenario for an interview since QKD isn't exactly prevalent in the industry. As I mention in a comment below - this is a job interview, not a dissertation on the academics of cryptography. – Jesse Williams Jun 15 '16 at 13:57
  • +1. You might add to this answer historical systems that used tamper-evident seals on packages used to send one-time pads, such as the Canadian OTFP / OTLP system; the DDR and USSR OTP system; etc. – David Cary Jun 15 '16 at 14:11
10

The answers to the effect that secure distribution today doesn't ensure secure distribution tomorrow are ok, I guess, but isn't there another reason: distributing the keys is usually done from some central site to the "spies", whereas the spies are sending their messages in the reverse direction? (Assuming the spies are the ones generating the messages; of course messages can be sent in either direction.) Security in one direction does not necessarily imply security in the other direction.

An obvious case would be submarines sent out on missions. They're given one-time pads before they leave, but use those pads to encrypt messages they're sending back to base. (The base may be sending messages back to them, which of course gets back to the other answer: you don't want the submarines to have to come back to port to securely pick up messages from the base.)

It's a very good thing that the German Navy used Enigma, rather than one-time pads, in WWII.

  • But do submarines actually use OTPs? Using an OTP would limit the amount of text they could encrypt (or decrypt) on any particular mission. – David Richerby Jun 14 '16 at 14:33
  • 2
    A one time pad in the form of a read-once-then-wipe CD/tape/hard disk would give a fairly large amount of totally secure comms. – Sobrique Jun 15 '16 at 8:27
  • 1
    @DavidRicherby dictionary-based compression is used anyway in submarine comms (e.g. VLF radio, for shore-to-ship). It has historically been used for naval communications both to disguise the message content and to encode it efficiently (the bit rate of even an efficient morse operator was rather low). By the early 70s you could get a tape drive storing 20MB (and you don't need 8 bits/symbol, 6 is easily enough) – Chris H Jun 15 '16 at 9:36
5

I had a job interview yesterday where they asked what the only scenario where a one-time pad can be broken would be, my answer to which was "when the key distribution process is not secure enough".

I don't mean to give you insecurities about your interview, but I'm quite sure this is not the correct answer -- or, otherwise, I haven't understood your answer. This because your answer applies to any encryption method -- if you cannot communicate securely a symmetric key, then it's game over.

The only scenario in which a OTP can be broken (leaving aside obvious blunders from the communicating parties, such as reusing parts of the OTP, or letting the enemy get his hands over it) is when it has been generated using a non-truly random source. This would allow the enemy to run a frequency analysis and try to deduce the text being exchanged.

In fact, a one-time pad guarantees perfect security and is theoretically unbreakable. The only reasons why it is not being used widely is because of its impracticality.

Why would you even use a one-time pad if the key distribution is 100% secure? Why not simply send the plain-text message since you are sure that distribution is 100% secure?

The answer to this question is: because the secure channel could be not always available, could have a limited bandwidth, or could be too costly to use. So it can be used to exchange (once) a small-sized key but not (often) lengthy private communications.

  • 1
    "a small-sized key but not (often) lengthy private communication" - but a OTP key must be at least as long as the message it encrypts. Limited availability is a valid reason, but not bandwidth. – Blorgbeard Jun 13 '16 at 20:32
  • 4
    By definition, the OTP key is generated by a truly-random source. It is impossible to be provably unbreakable without this assumption. Therefore, not being generated by a truly-random source is not a valid way to break OTP. The only way to break it is to know the key. Because of this, his answer is correct (as the key is only as secure as the exchange and protections while at rest. In this case, an assumption is that protections at rest are impractical to attack). – Qwerty01 Jun 13 '16 at 23:45
  • I agree with @Qwerty01 - taking advantage of a flawed implementation of an encryption scheme doesn't mean that you have broken the encryption scheme itself. – Jon Bentley Jun 14 '16 at 12:09
  • @Qwerty01 Could you cite the definition that excludes non-truly-random generation? I'm asking because Wikipedia article on OTP has a >10 year history of changes calling truly random keys "a challenge", or using conditional "if the key is truly random" then impossible to break. If it's a matter of definition, then interviewers could use a different one. – techraf Jun 16 '16 at 1:01
  • The reason why they're mentioning it is because generating truly random data is difficult. Because of this, people tend to use CSPRNGs in order to generate the data needed rather than truly random data. If the data is not truly random, you're attacking the algorithm that generated the key and not OTP. Another way to think of it is like this: if you use a RNG that returns the same number every time to generate an RSA key, the key will be easilly broken: not because of an issue in RSA, but because of an issue in your RNG. – Qwerty01 Jun 16 '16 at 1:30
4

Here's another reason that the other answers don't mention:

You can use your secure channel once to transmit OTPs and then send secure messages multiple times later until your OTPs run out.

This can be useful because achieving a 100% secure (or close to it) channel can be very difficult and/or costly, whereas insecure channels are cheap, fast, and readily available, so there is a benefit to minimising the frequency of your use of the secure channel.

Example: you transport 1 terabyte worth of OTP data by physically carrying a hard drive to the destination (a costly and inconvenient operation). You can then send 1 terabyte worth of encrypted messages via the internet as and when you need to. This is better than repeatedly using the secure channel to send your messages by hand.

-2

A one-time pad can be broke if the message to be encrypted is significantly longer (like multiple times) than the number of characters/bytes in the pad. This amounts to repeated use of the same "one-time pad" and is equally vulnerable to decryption.

  • 5
    If you repeat the pad, it is no longer a one-time-pad. – Anders Jun 14 '16 at 18:42
-2

Honestly, I think a plausible answer is that you cannot guarantee 100% security. Or at least that would be my answer, likely followed by "anyone assuming 100% security does not understand security. Furthermore, anyone assuming 100% security is as much at risk, and possibly more, than someone assuming less than 100% security."

  • That's irrelevant to the question. Whether you have 100% security, 99% security, or 50% security on your chosen channel, the question still remains - should I send a OTP over that channel and then send an encrypted message later, or should I simply send the message on that channel? How secure the channel is doesn't make any difference - if there is a way to break the channel and obtain the message, then the same way will enable you to obtain the OTP. – Jon Bentley Jun 15 '16 at 13:50
  • I would disagree - this isn't a dissertation on security, it's an interview question. Having been a hiring manager in Security R&D, I would expect a candidate to be giving me an answer that shows an injection of real world thought into such a question. If I was looking for an academic answer, I would happily assert that after such an answer was given. – Jesse Williams Jun 15 '16 at 13:54
  • 1
    If I were a hiring manager and got that answer, I'd be less concerned with the validity of the answer, and more concerned that they failed to understand the question correctly. That indicates problems with attention to detail and ability to follow instructions. I'd prefer a wrong answer that at least attempts the question (after all, no human can be expected to know everything), than a "correct" piece of information that is irrelevant. – Jon Bentley Jun 15 '16 at 14:01
  • Looking at the question - "Why would you even use a one-time pad if the key distribution is 100% secure? Why not simply send the plain-text message since you are sure that distribution is 100% secure?" - it's very clear that the security of the channel is assumed, and they want to know why you should bother with a OTP. They're not asking whether or not it is possible for a channel to be 100% secure. – Jon Bentley Jun 15 '16 at 14:03
  • I disagree, but... that just goes to show that when responding to a question in an interview, you are at the mercy of the interviewers position on a matter. It's not as if this question was "solve for x" or "what are the components of the TCP/IP protocol stack". I would rather see a skeptic in security than someone with a fresh degree and book smarts that thinks they can outwit the system - said system being that security even under ideal conditions is imperfect. – Jesse Williams Jun 15 '16 at 14:04
-2

The question:

Why would you even use a one-time pad if the key distribution is 100% secure? Why not simply send the plain-text message since you are sure that distribution is 100% secure?

This assumes that at the time of the key distribution there is information to be sent which may not be the case. Other answers given here have addressed this point. Another issue is that even in principle the key distribution may only be good enough for only key distribution while it may be insecure for the desired transfer of information.

An example is the problem of how Edward Snowden can send you information securely. We assume that all communications from Snowden are monitored, if you meet him face to face then you'll be monitored, anything you take back from him won't be secure. So, there is then no way Snowden can give you a plain text file without that being compromised. At most you can bring something to Snowden securely. To implement the OTP method that's all you need to do.

A secure protocol using the OTP could then work as follows. I make copies of pictures I have on my hard disk and put them on a thumb drive. I ask someone who I trust to give this thumb drive to Snowden. After this person has met with Snowden, he is spotted having done so, all his belongs are searched, the CIA monitors him, his house ends up burgled regularly, spyware in installed on his computer. So, obviously he cannot receive anything from Snowden securely.

But Snowden can send information to me securely by applying the OTP method to split up messages into two white noise parts and adding that noise as fake high ISO noise to two pictures that he obtained from me and uploading these two pictures to Flickr. All I have to do is download his latest two Flickr postings, subtract the picture files from the pictures on my hard drive and add up the two noise parts to obtain the message.

  • 1
    I think you've not understood the question. The OP is aware of what a OTP is and how it works. Going by your example, the question is - if you can securely hand the person the thumb drive containing the OTP, then why not simply hand them the message in the first place, since you already have a secure channel by which to give them the thumb drive. – Jon Bentley Jun 15 '16 at 13:47
  • @JonBentley I have correctly understood the question, I addressed it on the point already made in some other answers about the information transfer happening later when there are no secure channels available. – Count Iblis Jun 15 '16 at 16:01
  • @CountIblis How does the answer the question "Why would you use a OTP if you're 100% sure the key distribution is secure?" It's clear you didn't understand the question. This is answering a question along the lines of "How can you make the key distribution more secure?" – Qwerty01 Jun 15 '16 at 20:41
  • @Qwerty01 I did understand the question, it's just that in the context of the OTP in the way one would use it in practice, this is an extremely trivial thing. The key distribution is not the point where information is transfered, it may not be even possible to transfer information securely through this channel. The Guardian could send a journalist to Snowden and give him a thumb drives containing pictures. But on his way back all his belongs may be searched. There is then no secure channel for communications from Snowden to the Guardian available at all, yet the OTP can be used. – Count Iblis Jun 15 '16 at 21:09
  • So, the OTP key may only be send securely one way, because when I'm going to Snowden, the intelligence services do not know that I intend to meet him. But after I've met him I may have been spotted by secret agents monitoring his apartment, so anything I take back from him is not secure. – Count Iblis Jun 15 '16 at 21:12
-4

If you send really confident text that can't be intercepted by computers under any circumstances, then you should use OTP and deliver key face-to-face, but you can mail encrypted message via post office. If used properly, then anyone can't break messages. Even in 1'028'526'910 year.

  • The question isn't about OTPs or how they work. The question is - if you can deliver the OTP face-to-face, then why not deliver the message face-to-face and skip the extra complication of using a OTP. To answer the question, you need to address specifically the reasons for using a OTP instead of the message itself. – Jon Bentley Jun 15 '16 at 13:53
  • @JonBentley Surely, the problem is not how to securely communicate with your wife at home.... – Count Iblis Jun 15 '16 at 16:33
  • @CountIblis I don't really understand your comment. My point is, if you have a way to securely deliver the OTP, then you could have used that way to deliver the message instead, and the OP is asking why you would bother using a OTP in that case. – Jon Bentley Jun 16 '16 at 10:15
  • @JonBentley Who says that there is a message to be delivered by me to the receiver of the OTP key? It may well be the other way around and that reverse path may not be secure at all. Snowden wants to send me a secure message but he is in no position to deliver a OTP key to me. I can deliver a OTP key to him, but I cannot take any message back from him as I'll be spotted having visited him and I'll be searched. – Count Iblis Jun 17 '16 at 22:24
  • @CountIblis Yes... that's one possible answer to the question. What is your point? You seem to think I'm asking the question, but I'm not. I'm clarifying what the question is, as this answer doesn't understand the question. – Jon Bentley Jun 18 '16 at 17:18

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.