3
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ What would be a key in your case? $\endgroup$
    – mentallurg
    Nov 6 '20 at 22:54
  • 2
    $\begingroup$ If the key is as long as the message, and you can transmit the key securely, why bother sending the message at all? Send all the secret stuff in the key! $\endgroup$
    – tucuxi
    Nov 7 '20 at 18:10
  • 2
    $\begingroup$ @tucuxi: Because I can send the key a year ago. $\endgroup$
    – Joshua
    Nov 8 '20 at 5:56
  • $\begingroup$ If your key is as long as your message, and you can transmit the key securely before the message is known, you could just roll a one-time-pad. $\endgroup$ Nov 8 '20 at 20:00
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The kind of permutation i mean is we have 800 letters so 800 positions possible. First letter will go into one of 800 position second letter goes into 799 position and so total =800!. From your answer I guess this approach is completely safe (if letters length is large), but not practical right ? $\endgroup$
    – KMG
    Nov 6 '20 at 23:14
  • $\begingroup$ @KhaledGaber Added that part and clarified that diagram based frequency attacks can easily break the two character-based permutations. $\endgroup$
    – kelalaka
    Nov 6 '20 at 23:31
  • 1
    $\begingroup$ Letter-order-scrambling would be really obnoxious if a frequency-balanced slab of letters was added to the end before scrambling. $\endgroup$
    – Joshua
    Nov 8 '20 at 5:55
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thank's mark, Your answer is really helpful, didn't thought about that at all. $\endgroup$
    – KMG
    Nov 7 '20 at 11:43
  • $\begingroup$ There's a further security issue: if the key/permutation gets reused (and since it requires 821 bytes to express, that's a tentation), it becomes quite possible to find part of it. For example, if a known long word is hypothesized to be used at different locations in a few emails (and the rest is English) it's very possible to find it's location by elimination, and the matching entries in the permutation; and then to decipher a lot of the rest. $\endgroup$
    – fgrieu
    Nov 7 '20 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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