Score:5

Crypto

Is it possible to create a pseudo-One Time Pad by using a key smaller than the plaintext?

phantomcraft

11/27/23, 10:44 PM

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?

1671

2 + 0

one-time-pad

Score:11

Crypto

bk2204

11/27/23, 11:04 PM

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.

+ 5

forest

11/27/23, 11:08 PM

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).

bk2204

11/27/23, 11:55 PM

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.

forest

11/27/23, 11:57 PM

Oh, interesting. Even for the initial seeding? I guess I need to check the source again.

leftaroundabout

11/28/23, 10:13 AM

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.

bk2204

11/28/23, 10:38 PM

The [current ChaCha state generator](https://github.com/torvalds/linux/blob/b7b275e60bcd5f89771e865a8239325f86d9927d/drivers/char/random.c#L245-L261) 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.

Score:7

Crypto

forest

11/27/23, 11:01 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is it possible to create a pseudo-One Time Pad by using a key smaller than the plaintext?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.