5
$\begingroup$

Background

I am an undergraduate novice learning about cryptography. Recently my professor introduced us to the concept of a "One time pad".

According to my professor:

A one time pad is a cipher that exists when one unique key is used once to encipher/decipher one message. It is also the only genuinely unbreakable cipher.

However, this simple definition seems a bit anti-climatic for describing the world's "best possible cipher" - and has left me with some lingering questions.

Questions

1) Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

2) What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123 - is this no longer a one-time-pad?

3) What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

4) Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

So in terminology that a novice or layman like me can understand. What exactly does it mean for a cipher to be a "One time pad"?

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Dec 10 '19 at 3:41
6
$\begingroup$

I'll answer your questions (1, ..., 4) first:

1) Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

No. The one time pad (OTP) requires the key to be truly random - otherwise it's guessable. And encrypt is vague - this could be any cipher.

2) What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123` - is this no longer a one-time-pad?

No - this is called a multi time pad and is crackable. And the OTP needs the key to be the same length as the message.

3) What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

The OTP doesn't take a salt, though I suppose what you suggest is plausible. If the salt is different for each message, than that avoids multi-time pads, but sending it with the message isn't particularly secure. Like sending half a password. Plus you still have the plaintext-key length problem.

Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

The OTP is a cipher$^1$ in itself. You don't use AES or ROT. And that voids the rest of the question.

The original OTP was based of the Vignère cipher. In Vignère, the key fred with message plaintext means that the key isn't long enough. Therefore, it repeats and becomes:fredfredf. Then, it's encrypted with a vigénere square, and you have the ciphertext.

The old OTP is almost identical; the key must be random though. Truly random. And the same length as the ciphertext.

The modern OTP is much simpler:

$C_i = (P_i \oplus K_i)$

Now you might wonder: that's so simple! Why don't we use it all the time? It is, after all, unbreakable.

The answer is because of its keysize. For a 5GB message (or file) you need a 5GB key. See the problem?

As an afternote, read Crypto101 (https://crypto101.io). It's a work in progress, (some sections simply contain TODO) but it'll be beneficial for anyone interested in cryptography.


$1$: The one time pad's status as a "cipher" is argued about all the time. I use that term here because it gets the meaning across.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Nice answer. One nitpick: a one time pad is usually implemented using XOR (the $\oplus$ symbol) as that's the most simple function - but that's not a requirement. Proof: take the inverse after performing XOR and you still have an OTP. $\endgroup$ – Maarten Bodewes Dec 9 '19 at 11:45
  • $\begingroup$ @Maarten-reinstateMonica I show that don't I? Originally the OTP was based of the Vigénere cipher... The idea is older that XOR ($\oplus$). It's only "recently" that it's used as the operator, and only because it keeps with the properties that the original vigénere based idea used. $\endgroup$ – Legorooj Dec 9 '19 at 22:42
  • $\begingroup$ Let's try to remember that comments should be used for clarification/suggestions rather than discussion. If you would like to talk about any aspect of this answer or question, feel free to step into the side channel $\endgroup$ – Ella Rose Dec 10 '19 at 3:38
4
$\begingroup$
  1. Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

No, because the one time pad requires a fully random key, and a password string is not a key.

  1. What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123 - is this no longer a one-time-pad?

Correct, as the name implies the one time pad needs to be used a single time. It would be (jokingly) called a many time pad, and is insecure.

  1. What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

A one time pad doesn't take a salt, and it doesn't even work on keys generated from a password and salt, as the generation of the key is not completely random.

  1. Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

There is no cipher involved in the one-time pad. The one-time pad doesn't take a cipher either; it is a cipher.

|improve this answer|||||
$\endgroup$
4
$\begingroup$

Funny how easy it is even for a professor to explain something that's apparently so easy in a confusing (arguably even wrong) way.

A one time pad is a cipher that exists when one unique key is used once to encipher/decipher one message.
It is also the only genuinely unbreakable cipher.

The first line means that most applied encryptions are one time pads (which is obviously not true!). For example, one very common algorithm for encryption (and authentication) is AES-GCM. This algorithm has the requirement that the combination key/nonce must be unique for one single message. So, you could argue that this is a kind of OTP. It is, of course not. When you go on the internet and use TLS, a session key is established, which is random and thus (with overwhelming likelihood) unique. So every communication using TLS uses a one time pad? Obviously not.

What's the deal with an one time pad?
Originally, once upon a time, you would just add the key going forward in the alphabet, and do the equivalent of "overflow" (or, a modulo operation, if you want to call it that) on paper. To decrypt, you would count backwards the same. Something like the Caesar chiffre, or ROT13, only just you use a different offset for every new character, not the same all over.

Nowadays, for computers, the easiest invertible operation is XOR, and it has the nice property that forward and backwards it's all the same: a XOR b XOR b = a.
You can in fact use AES for a one time pad (any key-dependent, invertible function can be used), but this doesn't make sense. you do not gain anything. If, instead of processing one char at a time, you were using blocks of 16 bytes of key and message at a time and ran the whole through AES encode (or decode) it would be exactly the same (with a more complicated function, and a different cipher text, but otherwise exactly the same thing). However, it would only be some ten thousand times more difficult to do, and none more secure. So that doesn't really make sense, nobody does that.

The second line is true (if the preconditions are met, and only then!), but worded badly. The OTP is not the only genuinely unbreakable cipher, it is the only cipher that is provably (and in fact trivially provably) secure. If the preconditions are met, that is. Those are:

  1. The key is only ever used once, on one single message.
  2. The key is as long as the message (so it is not repeated or expanded).
  3. The sub-parts of the key (bits/bytes/characters/whatever) are independent, ideally random (somewhat the implication of (2)).

How is it trivially provable that the cipher is secure? Well, because without knowing the key, the encrypted message can be decrypted to everything and anything. Every solution is equally likely and "equally correct". It is not possible to tell whether what you decrypted is the actual message.

That isn't the case for other ciphers (most of the time, at least). This is because the message is almost always longer than the key, so there must be some correlation. A good cipher makes it hard, infeasible, or technically impossible to find that correlation. So, a good cipher that isn't an OTP may very well be genuinely unbreakable (since, for example, even with an ideal computer there's not enough energy in the entire solar system to run the computations), but it is not provably unbreakable. In principle, you can break it, just like you can in principle win the lottery twice within two weeks. It may be difficult and impractical, but it isn't provably impossible.

A cipher is considered "secure" when there is no known way of breaking the encryption that is faster (or, at least, significantly faster, if an attack on a 128-bit cipher takes 2^126.5 iterations, usually people aren't really concerned) than simply trying all possible keys. This is called "brute force". That's much, much harder to achieve than you would think. With a (correctly used) one time pad, you get that property automatically. The only possible attack is brute force in the first place, and even then you are none smarter than before because every result that you get is equally valid. I cannot even apply torture to get the correct key from you because you can trivially create two keys, of which one will give me a by all means correct, and plausible, but entirely false message.

Any kind of "counter/stream" mode (GCM, CCM, OFB...) that effectively turns a block cipher into a stream cipher produces a sequence of bits (bytes, characters, whatever) as long as the message (or any other desired length) that can be XOR-combined with the message. Same for stream ciphers. So as long as I am not reusing keys, are these one time pads? Well no, the bits within the stream are not independent. They're calculated, or derived, from some known small constant (the key). So they are correlated in some way, and every solution is not just as likely as every other solution. Plus, there most likely exists a way to find that solution which is faster than brute force (even if it's not known, or impractical).

Then why don't we use OTP all the time? Well, because it's disturbingly difficult to work with, or distribute, keys that are a couple of megabytes (gigabytes...) in size.

Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

Technically yes, but it will be a rather poor one. The key has rather low entropy and since the key is an English word, the bits in that key are (obviously) somewhat correlated. That should actually be not so much of a problem because as an attacker, I have no way of telling, unless I already forced you to hand over the key, right? Except... that's not quite true.
The ss and the 123 will result in visible patterns that make someone looking at it immediately conclude: "Oh wait, this isn't random, there's a clear pattern.". Once that is known, it's mere milliseconds to find the pattern. On a more professional, less naked-eye level, an attacker could run some statistical tests (or simply try to compress the ciphertext, which is a surprisingly good approach) to come to the same conclusion.

What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123 - is this no longer a one-time-pad?

This is then basically no-encryption. Remember that a XOR b XOR b = a. If you encrypt two messages with the same key, and I get the two messages, then I have the key!

The same goes for partially reusing the key, such as for example encrypting This is a longer message encrypted with a shorter key with the key lkgeqeivod (lkgeqeivodlkgeqeivodlkgeqeivod...). I only have to shift some substrings around a bit, and try XORing them, and within less than a second, I have the key!

What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

If the salt (which is probably better called nonce) is as long as the key, sure. But then you can just use a different key. If the salt is shorter than the key, and you use it in some more or less non-trivial way to transform the key, you basically have a stream cipher of sorts (but no longer a OTP) -- where the "key" is really an implementation detail, and the nonce is the "key".

Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message.
Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

In general, the strength of a cipher certainly matters. Using a weak cipher (in general) is not secure regardless of key strenght or key reuse. In the scope of OTP, the difference is zero. Any key-invertible function does the job, the system's security does not come from using a particularly strong function. Since security is already "perfect" (if done properly), it cannot get any better.

|improve this answer|||||
$\endgroup$

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.