• Alice and Bob use (cryptographically secure, hardware-rng generated) 4096 bit keys.
  • Each message is encrypted using a new key; meaning: once a key is used, it's destroyed.
  • Alice and Bob only need to encrypt/decrypt messages up to a length of 256 bytes.
  • To keep it simple, key-exchange is not part of the picture and can be assumed 100% secure.

Since the 4096 bit keys practically represent 512 bytes, the key obviously holds enough random material so that it "could" be considered suitable for One-Time-Pad use (like in classical OTP cipher examples).

Looking at the above assumptions, would the use of a simple OTP-XOR cipher indeed be secure enough from a cryptographic point of view, or is it more advisable to use another crypto-algorithm (for example a block-cipher) for some specific reason? And if, why would it be more advisable to use another cipher?

  • 1
    $\begingroup$ 1) You still need a MAC, luckily for you polynomial MACs are provably secure (with a certain probability of not detecting the error which is independent of attackers computation resources) 2) The problem with OTP is exchanging those keys and that you need state to ensure that you never reuse a key. $\endgroup$ Oct 23 '13 at 14:56
  • $\begingroup$ The obvious question is: how does Alice and Bob do key agreement? Does their 'cryptographically secure, hardware-rng' produce the same keys? If not, how does Bob get the key that Alice generates (and how is he certain that it's Alice's key, and not Eve's)? $\endgroup$
    – poncho
    Oct 23 '13 at 15:01
  • $\begingroup$ @poncho I already saw that question coming, which is why I added a 4th bullet to the list while you posted your comment. ;) I practically tried to boil it down to an encrypt/decrypt algorithm question, actively ignoring key-exchange and message authentication to keep it simple and because those points could be handled separately. In fact, I just want to be sure that "what looks like a perfect example of OTP material" is really what I think it is… or if there's reason (besides the usual "bling" that comes with crypto-protocols, which I could wrap around OTP-XOR too) to use another algorithm . $\endgroup$
    – e-sushi
    Oct 23 '13 at 15:15
  • $\begingroup$ @e-sushi I asked recently a related question: Is OTP useful in modern electronic communication?. The answer from Simon Johnson answer is very good, it points out three problems which all have been used to break some "OTP" implementations: Key generation, key distribution and key destruction. Maybe you want to look at that one for related information. $\endgroup$
    – user4982
    Oct 23 '13 at 17:04
  • $\begingroup$ @e-sushi You said: "Alice and Bob use (cryptographically secure, hardware-rng generated) 4096 bit keys." -- This statement often does not mean the keys have information theoretic security used by real OTP, but merely 128 bit - 256 bit security, i.e. "cryptographic level". If the key material is not perfect (it does not have information theoretic security), it is likely that the commonly used algorithms AES, Camellia, etc. would be more robust against attacks from slight bias in key stream. $\endgroup$
    – user4982
    Oct 23 '13 at 17:12

If your key material is properly random and at least as long as that which is to be encrypted, and indeed each key is used only once, then one-time pad is indeed applicable.

As was noted:

  • Distribution of keys will be a hard problem. OTP makes practical sense only in scenarios where keys can be distributed at some time T, then used for encrypting and decrypting messages at a later time T', when key distribution would no longer be an option. The red phone used this system (key tapes were exchanged by plane regularly).

  • OTP does just encryption, not integrity. You probably also need some sort of integrity check, which will need a bit more key material.

    You should compute the MAC over the encrypted message, because this obviously prevent any weakness in the MAC algorithm from leaking information about the message. Also, in order to prevent an attacker from swapping messages around, the MAC should probably include a sequence number, or any other unambiguous designation for the key to use (obviously, not a hash of the key).

    Alternatively, you can use a MAC over the decrypted message as long as you either encrypt it along with the message, or you use one of these nifty polynomial-based MAC which can be proven not to leak information about what they MAC. If you use OTP, you don't want to lose the psychological benefits of "proven security"...


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.