Assumptions Alice and Bob use cryptographically secure hard

Assumptions:

+ 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?

Solution

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\"...