Are there any systems out there that use a one-time pad?

Question

I'm still new to information security, but I have read a bit about the one-time pad. The point that sticks out to me the most is that it is supposedly unbreakable. Has this method of encryption ever been incorporated in any internet web applications on a larger scale? How would they pass they key?

The benefit of a OTP is to *move secrecy through time*. If you have a secure channel **now** (e.g. an in-person meeting) you can exchange an OTP. You have banked a little bit of secrecy for later. Later when you do not have a secure channel, you can use up a part of your pad to make your message secret. — Ben, Mar 28 '14 at 07:59
For example, you give your secret agent a BluRay with a few GB of OTP hidden on it, then everything he sends back while undercover can be perfectly encrypted. — OrangeDog, Mar 29 '14 at 11:03
Or you exchange OTPs with other heads of state at a UN meeting, and then your phone conversations can be secured. — OrangeDog, Mar 29 '14 at 11:04

score 30 · Accepted Answer · edited Mar 28 '14 at 08:20

30

The problem with a one time pad, is that is must be equal in length (or longer) than the data being encrypted , and must never, ever, be reused.

Just as you indicate, how would they send the key?, the OTP must then be sent in a secure way... however that is the problem that is usually left to the user and is generally why OTP is useless.

If you have the ability to send a large OTP securely, then you might think you could simply send the stuff you want to encrypt directly to the recipient over that secure channel.

However the benefit of a OTP is to move secrecy through time. If you have a secure channel now (e.g. an in-person meeting) you can exchange an OTP. You have banked some secrecy for later. Later when you do not have a secure channel, you can use up a part of your pad to make your message secret.

The improvement over OTP is where they make a small seed (a key) and use an expander called a PRNG to expand that key into what is essentially a stream cipher. This way you're only sending a small amount of data securely, and can encrypt lots of data with that expanded key. This is called "key stretching".

edited Mar 28 '14 at 08:20

Ben

3,697
1
18
24

answered Mar 27 '14 at 16:37

makerofthings7

50,090
54
250
536

24

"If you have the ability to send a large OTP in a securely, then you might as well send the stuff you want to encrypt directly to the recipient over that secure channel." -- That's a common, but incorrect assumption. The OTP key can be exchanged temporally independent of the actual message and even be long enough to be used for multiple messages, which can be transferred over an insecure channel at a later time. – jarnbjo Mar 27 '14 at 17:23
@jarnbjo You're right but I didn't get into that use case. Is there a word to describe that early transfer of an OTP secret for pending, future use by one or more messages? – makerofthings7 Mar 27 '14 at 17:30
1

In advance, beforehand, ahead? I don't know exactly what kind of word you're looking for. Exchanging the key in advance is one of the more common usage scenarios for OTP encryption. If A and B meet e.g. in person and exchange a long OTP key, they can later transmit the key offset and an encrypted message over an insecure channel as long as they keep track of which parts of the key have been used. – jarnbjo Mar 27 '14 at 18:09
5

Also, you don't have to use a channel that can't be intercepted to send the key, but only a channel that can't be intercepted without you knowing about it. If the key is intercepted, you just discard it and send another key. If your unencrypted message is intercepted, you're sunk. – cjm Mar 27 '14 at 21:22
Kind of related to @cjm's comment, sometimes it's possible to mutually agree on a secure key without being able to control the content of that key. Quantum cryptography works this way, for instance. In that case you couldn't send the message over the quantum channel, but you can still use it for a one time pad. – David Z Mar 28 '14 at 01:12
2

Key stretching is not an improvement, it's a tradeoff. You gain in terms of usability, but you sacrifice the security guarantees only OTP can give. – Drunix Mar 28 '14 at 17:12
1

All I can think is "I sent the key to my unbreakable encryption scheme in plaintext. Shit." – KnightOfNi Mar 28 '14 at 23:29

tylerl · Answer 2 · 2014-03-27T18:15:48.513

19

How would they pass they key?

This gets to the root of where OTPs came from, and indeed how they got that name.

This is for correspondence during wartime with ships or other similar agents^[*]. When the ship leaves port, they head out with a pad of random data. When they receive an encrypted communication over the radio, they decode it using the indicated sheet from their random pad, and then destroy that sheet.

So what's the level of secrecy of the transmission? If the pad is used and implemented correctly, then the secrecy of the message is the same as the secrecy of the pad. It has nothing to do with the secrecy of the radio transmission. Instead, however careful they were in handling and storing the decryption pad determines how vulnerable the message is. They're effectively using the OTP technique to confer the level of secrecy of an object delivered at one point to a message delivered later on.

That is the technique's (only) use and purpose. If you see OTPs in use today for general cryptography, then the user almost certainly doesn't understand what he's doing. This technique cannot be correctly incorporated into common electronic communication, and is totally inappropriate for things like web applications.

^{[*] Not sure if this was ever actually used for shore-to-ship communication, but the concept of an agent leaving base for a period of time fits the "ship" metaphor most closely. Often OTPs were used by spies.}

edited Mar 27 '14 at 18:15

answered Mar 27 '14 at 18:06

tylerl

82,225
25
148
226

But doesn't any kind of encryption provide no more secrecy than the secrecy of the key? – Shnatsel Mar 27 '14 at 19:16
5

OTP is *as* secure as the 'key'. Other kinds of encryption are *less* secure as the key, as they can (with a difficulty depending on the method) theoretically be broken also without knowing the key. – Peteris Mar 27 '14 at 19:45
3

@Shnatsel with OTP, unless you have the correct key *given to you*, you're sunk. There is no guessing. You can't guess at keys because *ALL* messages of a given length are equally probable. Every key "works" because for every message, you can trivially construct a corresponding key. With any other algorithm, you try a key and see if it generates an intelligible result. If you get a result that "looks right", then there's a high probability that it *is right*. – tylerl Mar 27 '14 at 20:35
@tylerl ain't encryption all about making all cleartexts equally probable? – Shnatsel Mar 27 '14 at 20:41
2

@Shnatsel no ... – tylerl Mar 27 '14 at 21:21
@Shnatsel That's true of the underlying block cipher (such as AES), but applying a [block cipher in a proper mode of operation](http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation) (such as AES-CTR) to an entire message does not have that property. – Jeremy Mar 28 '14 at 01:11

score 13 · Answer 3 · answered Mar 27 '14 at 20:22

Not really "Internet", but the one-time pad is documented to have been used for the Red Phone (a westernly-biased name; I don't know how they called it in Moscow). The pads were exchanged on magnetic tapes, sent by planes on a weekly basis. It is possible that the current system still uses a similar encryption method.

This makes sense: though the one-time pad requires as big a key as the data which is to be transmitted, it still yields a time-based advantage: you can swap keys in advance, at a time when bulk secure transfer is feasible, and then use them when time is of the essence (e.g. ten minutes before launching the ICBM, not ten minutes after).

The one-time pad also had the advantage that it wasn't telling the other side about any of your more complex cryptosystems (while a good cryptosystem should be secure assuming the enemy knows it, older systems were *not* necessarily secure under those conditions, and if you had a system you can't break you don't want your enemy able to use that system to talk to their own people). — cpast, Feb 13 '15 at 22:17

Shnatsel · Answer 4 · 2014-03-27T20:42:21.957

Pidgin instant messenger has a plugin that implements OTP encryption of messages sent over the wire, called pidgin-paranoia. So there is at least one OTP cryptosystem out there.

However, according to USE OTR's presentation at FOSDEM 2014, Pidgin is by no means secure software because it has 300,000+ lines of poorly audited C code, a lot of which is dealing with parsing binary data. It should be fairly trivially exploitable, and once exploited the attacker could simply siphon out the cleartext.

Security seems to be improving with the upcoming Pidgin 3.0 but if you're paranoid enough to use OTP, you should never use Pidgin (or even general-purpose operating systems for that matter).

Also OTP in Pidgin has not seen wide use because there is to be a good IM cryptosystem called OTR which is more than sufficient for the vast majority of use cases.

Graham Hill · Answer 5 · 2014-03-31T12:50:53.333

4

Not supposedly; Claude Shannon famously proved that one-time-pad has "perfect secrecy", and cannot be broken with a brute force attack.

But no-one uses it on the Internet because it turns out that in practice, you don't actually need perfect secrecy. I'm fine if you can brute force the encryption I'm using if it is going to take you twenty million years to do.

And alternative encryptions schemes have a big advantage over one-time pads - the keys can be much smaller, and so they are much easier to protect and exchange.

edited Mar 31 '14 at 12:50

answered Mar 27 '14 at 16:43

Graham Hill

15,394
37
62

6

And while the proof is mathematical, it's requirement involves **true** randomness for the key material, in the strictest sense. True randomness is hard and expensive to produce. If you don't absolutely satisfy that requirement, you lose the absolute proof, and so your OTP falls down to the slight imperfectness of every other practical scheme out there, while being a tonne slower and still impractical. – Ivo Mar 27 '14 at 16:53

score 1 · Answer 6 · answered Jul 16 '14 at 10:50

E.g. finnish Pohjola bank uses one-time pads. I got first one through normal snailmail and I have gotten new ones when I visit the bank. One list has 350 entries and I need one to sign up and another for accepting the payment of bills. If the amount is larger (thousands of euros) the bank sends as a textmessage the information which one-time number I choose. Feels very secure and handy, at least as long as I don't know how the numbers are created. The list folded down is exactly the same size as a credit card in my wallet.

Whoa! Pohjala gives you 350 for each list? Aktia gives you only 148, and Nordea even less. — Adi, Jul 16 '14 at 11:29

LB2 · Answer 7 · 2014-03-27T20:13:38.893

0

WikiPedia article has pretty good description on the practical weaknesses of OTP, and why not used in modern computing.

To it I can only add that even on modern networks transmission is not perfect and bits can flip, and thus messages are checked (I believe by including a hash of original message) to verify that message was delivered intact. Without it, there would be no way to validate that the message received actually made it through the wire intact and is thus a valid message. This, inturn, would take away from perfect secrecy since now it can be brute forced (with success of brute force evaluated by matching the hash to original).

For example, let's look at the example in the article in section "Attempt at cryptanalysis" which illustrates that attacker cannot know whether 'LATER' is the original message for a brute-forced potential key 'TQURI'.

Let a transmission validation (a.k.a. decryption validation) hash function be defined as H = Sum(characters) Mod Count(characters), that is summing up all characters of the message and then modulo-division by number of characters.

With such hashing function, original message HELLO would be tagged with hash code (7 + 4 + 11 + 11 + 14) % 5 = 2. The recipient of the message would then take decrypted message, recalculate the hash over received data, and validate that the result is 2.

Now, evaluating potential brute-forced key TQURI, the decrypted text is LATER. Without the hashcode to validate the message, the interceptor has no way of knowing if the key TQURI actually worked or not (perfect security). With hash key, interceptor can now validate by calculating hash key for LATER which is (11 + 0 + 19 + 4 + 17) % 5 = 1. Since calculated hash code 1 does not match original message's hashcode 2, interceptor now knows that the original message is not LATER and the key TQURI is not a valid key, and thus continue to enumerate and brute-force keys until a key produces a matching hashcode (not perfect security due to brute-forcing ability).

edited Mar 27 '14 at 20:13

answered Mar 27 '14 at 17:00

LB2

420
2
8

7

You could verify the message by including a hash of the ciphertext, couldn't you? Then it wouldn't expose any additional information. – Michelle Mar 27 '14 at 19:29
@Michelle I think it will. If you read the article, it stresses that brute forcing is not possible because you can come up with any key to produce any desired text, making it perfectly secure. If you include verification hash, then you can brute force the key until verification hash matches, thus revealing and confirming the key and the original message. – LB2 Mar 27 '14 at 19:37
All I'm seeing in the article is that hashing methods don't provide 100% security against forgeries. A hash of the ciphertext wouldn't give an attacker an additional vector to retrieve the original plaintext. – Michelle Mar 27 '14 at 19:54
@Michelle I just added an example to the post... – LB2 Mar 27 '14 at 20:15
@Michelle Oh, after I finished typing I think I now see what you mean: apply hashing over encrypted text to validate transmission, not over the original message. Yeah, I think that would solve the imperfect transmission problem without compromising perfect security. – LB2 Mar 27 '14 at 20:18
The network doesn't hash or checksum the original plaintext message - under normal circumstances, the network never sees or knows about the plaintext (all it sees is data, it has no idea if it's encrypted data). If hashing of the plaintext is desirable to ensure integrity of the decrypted message, that can be done by the encryption software (and included as a part of the encrypted payload so no attacker can see it). – Johnny Mar 27 '14 at 23:12
@Johnny We are talking about hashing by encryption algorithm/software and not network. The only network reference is in context that network is not perfect and can cause a bit flip... – LB2 Mar 27 '14 at 23:19
1

Then you should take out the whole section about the network, since there are a lot more ways to corrupt a message than sending it across a network (which already computes a checksum of the data, usually at multiple levels in the stack). There's no reason to add a hash of the plaintext outside of the encrypted payload, since as you say, it leaks data about the plaintext. The plaintext hash can be included within the encrypted payload, or a hash of the encrypted data can be added to allow validation of the encrypted data. – Johnny Mar 27 '14 at 23:28

score 0 · Answer 8 · answered Mar 28 '14 at 20:56

0

The one-time pad is hardly ever used for reasons already covered. As has been pointed out it has perfect security (assuming it was generated from a truly random source) -- since the "password" is of equal length to the message, there is no possible statistical deviation from "perfectly random" with which to break the password.

Modern encryption algorithms try to approximate a one-time pad by using what is called a key schedule. The key schedule is used to generate the "pad" as needed. However, they are not perfect, which is why it is not recommended to encrypt messages over a certain size -- for instance, AES-128 is not recommended for use with "messages" over 1TB in size.

answered Mar 28 '14 at 20:56

Shawn C

181
2

That's not really the definition of a key schedule. Ciphers are not theoretically perfect, but flaws found beyond the inherent limits of the design (of course a 128-bit key will be brute-forced with 2^128 tries) are not okay. – Matt Nordhoff Mar 29 '14 at 07:29
'AES-128 is not recommended for use with "messages" over 1TB in size' is misleading. Indeed, the usual recommended limits are much _lower_, but this is not due to any cryptographic flaws in AES. For a 128-bit block cipher in, say, CBC mode, collisions simply become likely after 2^64 blocks (256 EiB). It's common to limit yourself to 2^32 blocks, or 64 GiB, and minimize the risk. – Matt Nordhoff Mar 29 '14 at 10:32
... on the other hand, a different source recommends 2^48 blocks (4 PiB) for a somewhat higher (2^-32) but still minimal risk. At that point, for most practical purposes, rekeying obviously never becomes necessary. – Matt Nordhoff Mar 29 '14 at 10:39

score -1 · Answer 9 · answered Mar 28 '14 at 11:58

-1

Before moving to an mobile app my bank used something like that for signing and logging in. They sent a card (via registered mail) with one time codes that in combination with my PIN was used to verify login.

answered Mar 28 '14 at 11:58

liftarn

99
2

3

One-time passwords aren't the same as one-time pads. – Adi Mar 28 '14 at 12:46
2

Those "one time codes" are probably not even OTPs. The banking industry is fond of using cryptographic algorithms to derive unique codes from a base secret. See DUKPT for an example. The CVV2 number on your card is another. – John Deters Mar 28 '14 at 12:59

Are there any systems out there that use a one-time pad?

9 Answers9