Why I can't permutate an email and get away with it?

Question

I can understand why a simple substitution cipher can be broken easily using English letter frequencies, and even English digrams like th can be used. Also a complete random substitution will have a key length of $26!$ which can be done (around $2^{88}$, maybe NSA).

But what about emails? According to Google, emails have an average word count of 400 words. So I guess letter count will be at the very very least 800 letters. Brute forcing $800!$ (assuming a completely random permutation function) is not possible.

I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption.

So why is that? How to get around brute-forcing $800!$ permutations?

Answer 1

I can understand why a simple substitution cipher can be broken easily due to English letter frequencies can be used and even English diagrams like th can be used, also a complete random substitution will have a key length of 26! which can be done(around 2^88 maybe NSA)

The first part is correct. A thousand years old Frequency analyses can break this very easily. Many times this is given as homework on the Introduction to Cryptography courses. Note that this may require longer text in some languages or in some contexts (Gabel's Novel without e). In real-life both are assumed to be known since the attackers know you.

Trying all permutations is not the correct way since it can lead to many false positives and a long process to go.

but what about emails according to google emails have an average word count of 400 words so I guess letters count will be at very very least 800 letters. Brute forcing 800! (assuming complete random permutation function) is not possible. I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption so why is that, How to get around brute-forcing 800!.

I think you mixed about how the permutation cipher works. Or you are referring you generate a larger permutation like the permutation of two characters instead of one where you will have $26^2$ elements to permute in the standard English letter. That will contain $26^2! = 676!$. And it has 1622 decimal digits, try here, or around 5386 bits. This is still applicable to diagram-based frequency attacks therefore insecure.

Now, what about the key size? How do you exchange this key? It is not practical since you need to send an array of size $676*2^{10}$.

A cryptosystem besides being secure needs to be practicable, and this is not practicable. The common wisdom is using the substitution/permutation (confusion/diffusion) to achieve a computationally secure cipher like AES and be practical.

The kind of permutation I mean is we have 800 letters so 800 positions are possible. The first letter will go into one of 800 positions the second letter goes into 799 positions and so total =800!. From your answer, I guess this approach is completely safe (if letters length is large), but not practical right?

That is a positional permutation that only scrambles the letters. It is not as secure as one may think of since all characters are there. It may take time to place them correctly. The e-mails have some known beginning and ending and that will help to find the permutation. And keep in mind that that is not even secure under the Known-Plaintext Attack. The key size still is the issue.

Answer 2

It's worth mentioning that permuting things can still leak a lot of information. For example, imagine you see an email with some (small) number of numerals (say 3 or 4), and a symbol such as $. From that, it wouldn't be too difficult to get a narrow list of possible quantities of money that were discussed. Similarly, the presence of certain accented characters can potentially leak information (imagine you intercept communications by American english speakers about which job applicant they want to propose an offer to --- an accented character could potentially uniquely identify a certain candidate out of a list). Depending on your base alphabet (say UTF-8), you might have to worry about things like emojis as well (although if you are permuting bytes this likely isn't the case), which can convey a great deal of information in a single "character".

With a weak "cipher" such as what you suggest, you have to start worrying about all of these "potential leaks". If this is the only option you had then maybe it would be worth the (many) negatives, but when ciphers without these flaws exist there is no reason to consider permutation ciphers.