Is a PRG more costly than AES or any other encryption standard?

Question

I know that there are many encryption standards that take a key and sometimes an IV, and produces a cipher-text (the most prominent one is AES). These standards usually involve many rounds of addition and multiplication. However, using a OTP is much easier than this. You XOR the plaintext with your pad, this is the only requirement computation-wise. However, OTP comes with the problem of a key-stream as long as the plaintext. This key-stream is supposed to be random. My question is, is this randomness more costly than the encryption standards that are in use? Why don't we use OTP in every case, what is the downside?

Let's say I cannot afford to use encryption algorithms, but I have a stream of data that is nearly-random. If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return? What can be done to obtain the best pseudo-random characteristics from this arbitrary stream of data, to make it as qualified as it can get to be an OTP?

Answer 1

A one-time pad requires a true random sequence that is as long as the material you want to encrypt. If you have a pseudo-random sequence, then you don't have a one-time pad: you have a stream cipher. If you have a stream of data that is only “nearly random”, then you don't have a one-time pad, you have a broken stream cipher.

Concretely, if the nearly-random sequence isn't uniform, it means that there are biases: certain arrangements of bits are more likely than certain others. Whenever these arrangements are aligned with a pattern in the plaintext — for example English text contains more E than J, text in most languages contains more spaces than any other character, HTML tends to have a > shortly after each <, … — the pattern in the plaintext becomes apparent in the ciphertext. So certain patterns appear in the ciphertext more often than chance, they will reveal patterns in the plaintext.

To generate a cryptographically secure random sequence from a source of randomness that isn't perfectly uniform, you need to pass this random source through a cryptographically secure pseudorandom generator. One of the cheapest techniques to build a pseudorandom generator is to use an encryption algorithm such as AES in a construction known as CTR_DRBG. If all you want to do is to encrypt one message, then it's simpler and cheaper to encrypt the message with AES-CTR than do use AES-CTR_DRBG to build a key stream and to use that key stream to encrypt a message.

In addition, a one-time pad doesn't help with the authenticity of the message. If the message is modified in transit, there's no way to detect it. Encryption algorithms can be combined with authentication algorithm, and the cost of doing the two together is less than the cost of doing the two completely independently. The computational cost is only slightly less, but the cost in code size or in gate count is significantly less. For example, once you have the AES block cipher, it only takes a little additional work to build an authenticated encryption mode such as GCM or CCM.

Answer 2

Distilling your question down to these two salient points:-

Why don't we use OTP in every case, what is the downside?

leads directly to Why wouldn't everyone encrypt with a One Time Pad? and I won't add to the confusion, but that question might provide some insight. It also deals with the authentication /malleability issues.

I have a stream of data that is nearly-random

Then use it to seed a CSPRNG. Why in one time pad must the key distribution to be truly random and Why does the key for a one-time pad have to be uniformly distributed? show why you shouldn't use it raw. If your system has the capacity to store a large one time pad, it probably has enough computing power to run some form of CSPRNG. There are ChaCha derived implementations that will run as low as Arduino level. Just make sure that your original entropy is sufficient, typically 128 bits or more. That might require some compression /folding of the raw data to suit the seed size of the CSPRNG you should be using.

In many respects, this is the hardest part facing you as accurate entropy measurement of data is tricky. You clearly want to avoid the situation where a 1kbit stream of data only has a few bits of entropy as it's generated purely arithmetically.

Answer 3

I know that there are many encryption standards that take a key and sometimes an IV, and produces a cipher-text (the most prominent one is AES).

AES by itself is not a cipher, it is a block cipher. As such it can only encrypt messages that are exactly one block (16 bytes). You need a mode of operation such as counter mode encryption to create a real cipher. The mode of operation requires the IV. The IV just depends on the block size, not on any other property of the cipher.

These standards usually involve many rounds of addition and multiplication.

Not really. Some symmetric ciphers use addition, but more complex computations such as multiplication are generally avoided. Bit operations such as XOR, shifting and transposition are much more common.

However, using a OTP is much easier than this. You XOR the plaintext with your pad, this is the only requirement computation-wise. However, OTP comes with the problem of a key-stream as long as the plaintext. This key-stream is supposed to be random.

That's only true if you have true random number generator that supplies all the bits.

My question is, is this randomness more costly than the encryption standards that are in use?

There are speedy true random number generators, but you'd need a RNG that is inside the CPU to come anywhere close to ciphers based on AES. It is generally more costly to have a true random number generator than to use AES.

Often the random number generator at least requires whitening, which requires calculations. Sometimes the random numbers are even fed into AES to do this!

AES-NI on the Intel / AMD CPUs is currently at least 4 times as fast as the random number generator RDRAND on the same CPU's.

Why don't we use OTP in every case, what is the downside?

As you already mentioned, for a real OTP you need to distribute the key. To do this securely you would either need to use a physical, out of band solution (using sneakernet to distribute a CD).

Encrypting the key stream doesn't make sense, as you would need as many bits to encrypt the key as the size of the key.

Let's say I cannot afford to use encryption algorithms, but I have a stream of data that is nearly-random. If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return.

The algorithm needs to be secure. Otherwise an adversary could retrieve the state of the algorithm and use that to calculate the key stream.

The best thing to secure the algorithm is to use a stream cipher to create the key stream. AES can be turned into a stream cipher - for instance using counter (CTR) mode. There are also dedicated stream ciphers that are more lightweight, including the one in your GSM phone. Block ciphers such as AES are however more versatile.

What can be done to obtain the best pseudo-random characteristics from this arbitrary stream of data, to make it as qualified as it can get to be an OTP?

You'd use a stream cipher or a block cipher - such as AES - in a mode of operation that turns it into a stream cipher.

Fun fact: if you have a stream cipher then you can pre-calculate the key stream that it generates. Then you can have very speedy, low latency encryption by - indeed - just XOR'ing the cached key stream with the plaintext. And a relatively small key to establish.

Answer 4

Let's say I cannot afford to use encryption algorithms, but I have a stream of data that is nearly-random. [...]

I think one problem you're having is that you're treating this as a reasonable assumption: that cryptographic algorithms are somehow costlier than random bit generation. But it's the other way around—OTP is the costlier alternative.

One useful way to think about modern cryptography is this: the point of cryptography is to reduce our requirements for pre-cryptographic secure channels. All cryptography, from OTP to DH, needs to make some use of some such channel to work:

• OTP requires that the parties share at least as much random key material as the amount of data they plan to encrypt. This key material must be exchanged over a channel that's confidential and guarantees message authenticity.
• Modern symmetric encryption requires the parties to share a small random secret key. This key must also be exchanged over a channel that's confidential and guarantees message authenticity.
• Public-key encryption requires one of the parties to know the other's public key. This key must be obtained over a channel that guarantees message authenticity, but doesn't have to be confidential.

So looking at it from this angle, OTP is the costliest by far. Every bit that you encrypt with an OTP must be "paid for" by sending a pad bit over a costlier key establishment channel that you cannot protect cryptographically. If you think about it you can see that this volume limit also implies an average bandwidth limit—measured over long time periods, your encrypted message bandwidth cannot exceed the key establishment channel's bandwidth. If I can only establish 1 GiB of pad material per week, then that's how much data I can encrypt on average as well.

In comparison, with modern symmetric encryption a 128-bit AES key is sufficient to encrypt vast volumes of data. My key establishment channel can have a bandwidth vastly smaller than my encrypted communications.

Answer 5

If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return?

Why don't we use OTP in every case, what is the downside?

The problem with OTP is key distribution. If you have a secure channel to transmit the key, then instead of the key, transmit the message.

OTP is used between embassies and the governments. The embassies can return the Capitol and take a suitcase to carry the OTP with them. There the problem is when the OTP key is finished will you stop communicating or start to reuse?

It is used since it has perfect secrecy.

I have a stream of data that is nearly-random. If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return?

The answer depends on the definition of your nearly random. If it is an LFSR, I can try all possible LFSR outputs up to some length.

Is a PRG more costly than AES or any other encryption standard?

Compare the cost of carrying securely the OTP or using Public Key Encryption to Key exchange for Symmetric key encryption.