5
$\begingroup$

I have recently gotten interested in cryptography, so I looked some things up.

I thought, why even use AES or DES or any other complex way for encrypting data when there are far simpler ways, like just generating a random (pseudorandom) bitstream, and XOR'ing it with the data or secret message? The point is, if you have a random enough bitstream, you can just XOR the data.

Of course, you're the only one who will know the stream.

So why use all sorts of encryption if you have these simpler, easier ways of doing things? I'm new to cryptography, so this question may sound a bit naive.

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Can you tell me a way to generate that stream in a practical way without symmetric cryptography like AES? We use these ciphers because OTP key distribution is HARD, and these ciphers is the most cost effective method we have for encryption. $\endgroup$ – Natanael Oct 12 '19 at 11:36
  • 2
    $\begingroup$ You should definitely start to read a book like Serious Cryptography by Jean-Philippe Aumasson or Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell $\endgroup$ – kelalaka Oct 12 '19 at 11:52
  • 3
    $\begingroup$ While there is a lot of overlap between this question and the one linked as duplicate, they are far from the same, and the present one is the most generic. Problem with the other is that it specifically advocates using encryption by XOR with a key stream generated using Blum-Blum-Shub, which calls for specific counterargument (utter slowness). Also, the top-voted answer there properly answers neither the BBS aspect of that other question, nor the present question, for it's mostly focused against OTP. $\endgroup$ – fgrieu♦ Oct 13 '19 at 10:31
11
$\begingroup$

We use more complex encryption algorithms than XOR with a random or pseudo-random keystream for a number of reasons:

  • In order to get a short secret key in symmetric encryption. XOR with a true random stream (One Time Pad) requires storing or/and transfering a secret keystream the size of the data to encipher, which is utterly impractical. Replacing the keystram with a pseudo-random stream (as outlined in the question) solves that key size problem, but see below.
  • In order to construct Cryptographically Secure Pseudo-Random Number Generators then used as suggested in the question. A weakness in a PRNG could become a weakness in the encryption scheme using its keystream, especially if that's by XOR. We know several demonstrably secure ways to turn a secure block cipher into a CSPRNG, that are reasonably efficient, and (thus) popular.
  • In order to get direct access to encrypted data. Imagine a large movie stored encrypted as proposed in the question. In order to start viewing it in the middle, we have to run the pseudo-random generator from the start of the file. That's solved by encryption using a block cipher (such as AES) in most common modes, including CTR/CBC/OFB/CFB. For example, AES-CTR does as in the question, with the pseudo-random stream obtained by enciphering a counter (starting from an Initial Value usually stored at start of file), so that we can produce the keystream for any position by adding the IV and the (appropriately scaled) file index, and enciphering the counter values startign from there with AES, yielding the keystream, which allows decryption starting at the desired point.
  • In order to also get assurance of data integrity and origin, which often turns out to be at least as needed as data confidentiality. Even if we assume a large secret keystream, we need something slightly more complex than XOR with the keystream (e.g. universal hashing) in order to ensure that an adversary did not mess-up with the data (e.g. change "pay \$100" to "pay \$900").
  • In order to get asymmetric encryption, that is the capability to encipher without needing anything secret (beyond the data to encipher) on the side that enciphers.
| improve this answer | |
$\endgroup$
  • $\begingroup$ This suggests that one could use asymmetric encryption to transfer the OTP. But that's not done because you'd have to transfer twice as much (the key stream and the encrypted stream), and asymmetric encryption is relatively expensive. In practice, asymmetric encryption is used to transfer a short randomly-generated secret key before switching to symmetric encryption using that key. $\endgroup$ – ikegami Oct 12 '19 at 21:17
  • $\begingroup$ @ikegami I would say it is not done because that would reduce the security of the OTP down to the level of the asymmetric/hybrid encryption level. $\endgroup$ – Patriot Oct 12 '19 at 22:37
  • 1
    $\begingroup$ @Patriot, It can't be true that we don't use asymmetric encryption for key exchange because it lowers the level of security, because we do use asymmetric encryption for key exchange. $\endgroup$ – ikegami Oct 12 '19 at 23:05
  • $\begingroup$ @ikegami it's lower than the bar for OTP, but we consider this security margin to still be acceptable $\endgroup$ – Natanael Oct 21 '19 at 4:41
7
$\begingroup$

The other answers are great, but I wanted to call out an interesting feature of modern cryptography. Your question asked:

I thought, why even use AES or DES or any other complex way for encrypting data when there are far simpler ways, like just generating a random (pseudorandom) bitstream, and XOR'ing it with the data or secret message?

In point of fact, many modern encryption schemes do exactly that. Both ChaCha20 and AES in any counter mode (CTR and GCM both come to mind) actually generate a pseudorandom bitstream (usually called a keystream) and XOR it with the input data to encipher it.

As you can see, and as Paul's answer correctly points out, this observation hasn't actually made anything particularly simpler. We've just changed the problem: the problem isn't "how to encipher data", it's now "how to generate good pseudorandom bits". It turns out that doing that well from a relatively small amount of key material is fundamentally difficult.

| improve this answer | |
$\endgroup$
4
$\begingroup$

You could use a one-time pad, which does grant confidentiality when properly employed, but then you would have many non-trivial problems:

  1. Your message or messages would have to be quite short because generating letters in a truly random manner usually takes a bit of time and effort (rolling dice).

  2. One-time pads only have limited practical use. You cannot use your OTP for the purposes of making payments with your ATM card, using WeChat, establishing a secure link to this website, etc.

  3. You might need to make sure that the person you are talking to is who you think they are, and vice versa (authentication). It isn't easy to authenticate a one-time pad without using a modern method such as a Carter-Wegman MAC or an HMAC, etc.

  4. How is the receiver going to check the integrity of your message? How will they know that someone else did not add something, move something around, or take something away? How will they know that a technical glitch had not altered the message during transmission?

  5. How are you going to securely share your one-time pad?

  6. Physical security. How are you going to keep that one-time pad safe twenty-four hours a day? How about the person you are going to talk to? How will they keep their OTP safe?

  7. How are you going to explain to someone who was watching that you enjoy communicating like a Cold War spy?

Modern cryptography can solve all of these problems well--key exchange, authentication, integrity checks, confidentiality, encrypted storage, establishing a shared secret--and that is why we use it.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Short is a relative term. 1TB OTP key can be transferred easily. And you can communicate for a very long time if you don't send pictures or movies. $\endgroup$ – kelalaka Oct 12 '19 at 14:09
  • 1
    $\begingroup$ @kelalaka If you take details into account, it's not so clear that it's easy. It quickly becomes prohibitive if you need to securely share a 1 TB drive with every entity that you intend to communicate with. Especially if you run a server rather than just consider personal communication between individuals. Also, it needs to be 1 TB of secure, reliable storage per entity, which costs more than a single 1TB hard drive. This doesn't even take into account how you securely transfer the drive (plane tickets probably cost even more than the drives). $\endgroup$ – Ella Rose Oct 12 '19 at 14:26
  • 1
    $\begingroup$ @EllaRose I'm not an OTP fun, However, usually, the embassies in my mind when OTP is required and they talk with the capitol. In this case, they need only to give the ambassadors when they visit the capitol, etc. Run a server with OTP forget about it. And for ambassadors, the plane ticket is usually the least concern. $\endgroup$ – kelalaka Oct 12 '19 at 14:34
  • 2
    $\begingroup$ @kelalaka Sure, if you're shielded from all the inconvenience by a team of people who are paid to deal with it for you, then you personally won't notice the difficulty involved in using the system. But the difficulties are still there, it's just that the ambassador (in your example) does not have to witness them. $\endgroup$ – Ella Rose Oct 12 '19 at 14:57
  • 1
    $\begingroup$ @ikegami there is no problem, I can delete my comments. It was broken since re-use, crib dragging and the NSA guys always trying. There is no historical known for key OTP espionage. It is like German Enigma operator mistakes. That's it. It is informaticall secure and you can send the message on the phone. This debeate will never finish and this is why we prohibited OTP from HNQ, however we have no active mod around here now! $\endgroup$ – kelalaka Oct 12 '19 at 21:39
2
$\begingroup$

...random enough..

Let's just focus on that as it forms the nub of your question. Yes,$$\text{random (pseudorandom) bitstream} \oplus \text{secret message}$$ is very simple, works and is in common usage. But the first term in this encryption function masks great (and necessary) complexity. In order to be secure, the bitstream must comprise independent and uniformly distributed numbers, typically with bias not exceeding $2^{-64}$. How do you obtain them? Therein lies your complexity.

You can make them with a physical device. If we exclude zany methods like dice and aquarium fish, we're left with some type of electromagnetic apparatus. These days, that will take the form of either a laser or diode. Both create the original entropy for distillation into random numbers based on quantum indeterminacy. Quantum mechanics are pretty complex.

Or you can expand a little entropy like say a password, into a long stream of pseudo random numbers with a CSPRNG (and perhaps a key derivation function). The need for non invertability/non predictability of the output and to guarantee acceptable bias, requires complexity. And so cryptographic primitives are complex. If it wasn't complex, you could just roll it backwards.

Therefore, what you've really asked is:- $$\text{complex to make random (pseudorandom) bitstream} \oplus \text{secret message}$$

You've simply moved the complexity upstream of the XOR operator.

| improve this answer | |
$\endgroup$
1
$\begingroup$

What you're describing would be a One-Time-Pad. The OTP would actually be perfectly secure, but the first problem is in the issue that you have to generate a bit stream using a cryptographically secure pseudorandom number generator (CSPRNG) instead of a usual pseudorandom number generator. But even that doesn't pose a particularly large problem. Keep also in mind that a OTP is only secure if you use it once, using a OTP with the same bit stream would be insecure.

So let's assume generating a random bit stream isn't a problem:

The big problem lies in the process of sharing the key with others. That's the real issue, because a public cryptosystem like RSA-2048 can for example only encrypt a message of size 245 bytes, as described in this answer on securitySE.

You could therefore also only generate a random bit stream for the OTP of equal size. And each time you would have to transmit a new bit stream for a new OTP, all the time until you're finished. That's a very slow process. At that point you could even ask: "Why am I even using a OTP anymore, I could just send the actual message using RSA instead the key!".

So generally we transmit a key for a symmetric cryptosystem like AES using something like RSA. AES has (practically) no limit of data to encrypt for it to still be secure.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Another problem with OTP is when the key is finished either no communication at all, or have a crib-dragging attack. Maybe you should also mention the Historical bond case key carrying and trusting the carrier issue. Note: the first sentence not clear. $\endgroup$ – kelalaka Oct 12 '19 at 12:10
  • $\begingroup$ Well, some issues with all this... 1) OTP key generation doesn't require any CSPRNGs at all. That's not how they were made in days of olde, or are made these days. 2) Generation is as fast as you need. They range from 100's b/s to >> 10 Gb/s. Even /dev/random will give you 30 kb/hr. 3) Quantum key distribution networks exist in many countries to exchange keys. 4) You can fit 32GB of material on a £6 flash drive which you can swap with Ömer. $\endgroup$ – Paul Uszak Oct 12 '19 at 12:28

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