-4
$\begingroup$

It is known that One-Time Pad(OTP)s are theoretically unbreakable but impractical for use because of the size of the key length. But what if multiple encryption is used? Not to encrypt the first cipher text, but the key.

First, the message is encrypted using OTP. Then the key used for OTP encryption is encrypted using an Elliptic Curve Cryptosystem(ECC). The private key of ECC is again encrypted using OTP. Effectively reducing the key length considerably while providing the security of one-time pads.

Can this be a practical implementation of OTP?

$\endgroup$
3
$\begingroup$

No. Here is a breakdown of definitions:

  • One Time Pad encryption refers to one bit of key material is used to encrypt at most one bit of output.
  • The "One Time" part is critical. Using any bit twice means you cannot call the new encryption algorithm a "One Time Pad".
  • The "Pad" in OTP is the key.
  • ECC cannot encrypt long messages. It can encrypt many small messages, but that's slow. You can encrypt many small messages, but it's slow and under normal circumstances you need to use a nonce.
  • Instead of using asymmetric algorithms to encrypt arbitrarily long plaintexts, the type of encryption scheme used is called "hybrid encryption". To over simplify, the idea is to encrypt a symmetric key (which is short) using asymmetric encryption. Then the actual message you want to send is encrypt using a stream cipher (or other algorithm) using the ECC/RSA encrypted key. That effectively allows an arbitrarily large message to be encrypted without performing ECC/RSA encryption/decryption more than once.

From this you can draw the conclusion: No. It is not a practical algorithm, for one, because it is slow.


And some additional clarification about what is and isn't an OTP for the confused global audience:

  • Using random bits to seed a PRNG and using the output to encrypt is not an OTP algorithm. This is usually called a stream cipher.
  • XORing a message with a pad and repeating bits from the same pad once you run out is not an OTP algorithm.
  • Deriving new pseudo-random bits from a one time pad using a block cipher, stream cipher, sponge construct, or hash function and using that output for encryption is not an OTP algorithm.
  • Any form of reuse of pad bits once you generate one bit of ciphertext is not only cheating, it also means what you are using is not a one time pad algorithm.
  • Think of a one time pad as a strip of paper. Read one symbol off the beginning of the strip, use that symbol to encrypt an equivalently sized unit of plain text, rip the paper between the first and second symbol, then burn the piece of paper with the symbol you just used. (If someone recovers the pad of paper that contains your key material then you're message can be recovered. So destroy it immediately.) The digital equivalent of this process you can call a one time pad algorithm but any other process you cannot call an OTP algorithm.

From this you can draw the same conclusion a second time that, no, it is not more practical than a normal OTP algorithm because a two-time-pad is not a one-time-pad. You don't have the security properties of an OTP unless you only encrypt one message. And even if you do limit yourself to one message you are just adding complexity without gaining any security.


Now for the third impracticality:

There exists no encryption algorithm which will have ciphertext that requires less storage space than is required to store the plaintext. In fact, there exists no invertible function than can map a set of $n$ inputs to a set of fewer than $n$ outputs.

You cannot encrypt an in-compressible plaintext string into a shorter ciphertext string. This includes ECC and OTP encryption. If a one time pad is long, then encrypting the one time pad will result in a long ciphertext. Having a short key does not mean you have a short ciphertext.


The good news is that it doesn't matter that asymmetric systems, symmetric systems, and hybrid systems are less "perfect" than OTP encryption. There are symmetric algorithms you can choose that will not produce crackable ciphertext. (They're not "classical encryption" algorithms of course. Except OTP.)

The only reason I can think of where I would choose to use a one time pad algorithm is if it were a situation in which I have a reason to distrust all computers (or practical alternative machines), I intend for both sender and recipient to perform encryption by hand, I am able to share one time pads on paper with someone I meet in person, I can validate the identity of that person, and if we both agree only to decrypt messages if we can use another algorithm to validate ciphertext integrity.

$\endgroup$
2
$\begingroup$

Even though you’re encrypting it in some way, you are reusing the key (aka "pad") and thereby violating the OTP definition.

Per definition, OTP requires the “key“ to be…

  1. a truly random one-time pad value,
  2. generated and exchanged in a secure way.
  3. at least as long as the message, and
  4. only to be used once.

Besides, when you think that re-encrypting a key several times to use it for successive encryption efforts is a novel idea, I have to somewhat disappoint you by saying: You might as well simply use a well vetted stream cipher (or KDF – depending on the exact scenario) because that’s what you’re (im)practically reinventing here.

Btw.: For a very related OTP Q&A, check Mathematical formula for switching the key for OTP?

$\endgroup$
1
$\begingroup$

You still would only have the security of the ECC - someone could just break the ECC (with brute force, if needed) and then use the OTP to decrypt the ciphertext to get the original message.

You can encrypt the key of the ECC with an OTP, but that doesn't stop an attacker from trying to break the asymmetrical encryption. Try to think of it the following way: What whould happen if you didn't send the ECC key at all, for example when your friend already knows it? An opponent would then need to attack the asymmetrical encryption directly because he has no idea about the key at all. The message OTP key may be random, but he can still try to decrypt the ciphertext with his guesses to check if it's correct.

Also, you still have other disadvantages of the OTP with your scheme:

  • The ciphertext is over two times as large as the message because you still need to send the whole OTP of the message with the ciphertext itself.
  • You need to generate a huge amount of true random key material.
$\endgroup$
0
$\begingroup$

No. Your first and penultimate sentences contradict each other. Consider why OTPs are theoretically unbreakable, and how therefore it's mathematically impossible to maintain perfect secrecy with a considerably reduced key length.

$\endgroup$
-1
$\begingroup$

My research and experience with "Multiple Use Pads (MUP)" suggests strongly that this would not be an effective approach.

One of the advantages to MUPs, or their limited ancestor, OTPs, is as you pointed out, they are the ideal in encryption (I believe Claude Shannon used the term 'perfect secrecy').

I see two problems with using any other type of encryption (such as ECC) with an OTP or MUP:

  1. time - one loses the advantage of providing very fast encryption
  2. if the result is a smaller key (from ECC), then one loses the advantage associated with 'perfect secrecy'. In particular, shorter keys have been compromised, and, as quantum computers emerge, they will cut through these smaller (factorization based) keys like a hot knife through butter.

This is why I have focused on MUPs - they offer the advantages of OTPs without their limitations, and without the need to use "multiple forms" of encryption.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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