5
$\begingroup$

Let's suppose I want to encrypt a 10GiB file but I don't want to use a One Time Pad, just a 1MiB key taken from /dev/random (in Linux).

I know that the key should not be repeated, but is it possible to do a form of pseudo-OTP by using the same key across the entire plaintext?

I thought in a scheme: Hash each 64-byte piece of the key with a hash function (with output size of the same size of the 64-byte piece) concatenated with a seed, and when repeating the key in the next portion of ciphertext, use another seed. Basically, a pseudo-OTP by using different seeds ("keys") for each repetition of the key.

/\ Is this scheme valid?

Is there another scheme that would be secure as if it was done with a true OTP by using a key smaller than the ciphertext?

$\endgroup$
0

2 Answers 2

11
$\begingroup$

What you're proposing is called a stream cipher. Most stream ciphers take a key of one of a set of fixed sizes, usually with a non-secret value of fixed size called a nonce, and generate a very large key stream that can be used to encrypt large plaintexts securely.

In such a context, we usually don't use a key as large as 1 MiB because we presently believe that it will be computationally infeasible using all the resources of this planet to brute-force a 128-bit key. People who wish to hedge against additional cryptographic advances may choose to use a 256-bit key. Note that /dev/random and /dev/urandom are generated using a 256-bit stream cipher on Linux and thus cannot have more security than that.

A scheme where you use a fixed key and a nonce and/or counter (what you refer to as a seed), passing them through a PRF, such as a cryptographically secure hash function, and then XOR it with the plaintext is, in the general case, referred to as counter mode, and is secure provided the PRF is secure. However, no stream cipher is perfectly secure in the way that a one-time pad is secure. That's not practically a problem because we have many good stream ciphers that are extremely fast and provide excellent security.

As a practical matter, you will also want to provide integrity verification for your plaintext using a message authentication code, or MAC, or by using an integrated design containing encryption and a MAC, called an AEAD. Instead of rolling your own algorithm, I'd recommend using AES with OCB mode or XChaCha20-Poly1305, both of which are extremely fast AEADs (4-11 GB/s) and provide excellent security guarantees.

$\endgroup$
5
  • 1
    $\begingroup$ Interestingly, the Linux random driver actually uses an effectively 320-bit key with 256 of those bits being periodically reseeded. This is because it uses ChaCha20 with a random key and nonce (and counter). $\endgroup$
    – forest
    Nov 27, 2022 at 23:08
  • $\begingroup$ True, but recent versions of the kernel use BLAKE2s to generate the 256-bit seed for the PRF when extracting entropy and thus cannot provide more than 256 bits of security. $\endgroup$
    – bk2204
    Nov 27, 2022 at 23:55
  • $\begingroup$ Oh, interesting. Even for the initial seeding? I guess I need to check the source again. $\endgroup$
    – forest
    Nov 27, 2022 at 23:57
  • $\begingroup$ But surely you can still get more than 256 bits by waiting until the kernel has put in fresh hardware entropy into the pool? It may be pointless since ̶6̶4̶0̶k̶ 256 bits should be enough for everyone, and unreliable since /dev/random doesn't block anymore to indicate lack of entropy, but that doesn't mean that it's not possible. $\endgroup$ Nov 28, 2022 at 10:13
  • $\begingroup$ The current ChaCha state generator sets the nonce and counter to zero when created. The extract_entropy code uses keyed BLAKE2s as a PRF to extract and expand, just like HKDF, and therefore suffers from the same limitations as the extract step of HKDF in terms of entropy. $\endgroup$
    – bk2204
    Nov 28, 2022 at 22:38
7
$\begingroup$

An OTP is only an OTP if the key and plaintext are exactly the same size. Anything else is not an OTP. However, you can take a small key and expand it algorithmically into a large amount of random data which you can then combine with plaintext in the same way you would an OTP key. This is called a stream cipher. There's no reason to try to reinvent it. They already exist.

There is absolutely no need to use a 10 MiB key. Instead, use a 256-bit key with a good stream cipher such as ChaCha20 or AES-CTR. Alternatively, you could feed a seed of appropriate size into a hash function along with a counter to generate a portion of keystream the size of the hash. Incrementing the counter ensures that each input will be unique.

By the way, even /dev/random's output is generated with a CSPRNG (a stream cipher), so it can't be used as a true OTP either. But that doesn't matter. A good stream cipher and an OTP are equally secure in practice, even if an OTP is more secure in theory.

You should also be using authentication. I would recommend using ChaCha20-Poly1305.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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