Benefit of combining classical substitution ciphers with modern cryptography I know that a simple monoalphabetic substitution cipher is considered extremely weak, on account of linguistic frequency-analysis attacks.  However, assume the following:


cleartext is encrypted (with 256-bit AES, for example), and the resulting cipher is in base64 format
the client has a key of 64 chars (a-z, A-Z, "+/"), where each character is randomly mapped to another character (i.e., 'a' -> 'Y', 'b' -> 'f', 'c' -> '/' etc)
a simple monoalphabetic substitution cipher is applied to the base64 ciphertext 


Aside from the practicalities of implementing this approach, would this add much security?  I argue that it would, taking into consideration the following points:


neither base64 encoded text nor the raw encrypted data it represents are subject to frequency-analysis attacks
the 'key space' (to use the word loosely) of the base64 character set, represented as a factorial (64!) = 1.2688693e+89, or roughly 2^296 (if I calculate correctly).


So, in the case of a brute force attack, an attacker would need to try 2^296 key combinations, and for each one of those, they would need to go through the normal process of brute-forcing a 256-bit AES cipher (already unfeasible). 

In the case of a break in the underlying algorithm (AES, in this case a break would be highly unlikely) the attacker would still need to search the 2^296 keyspace to find the original ciphertext.

There has been plenty of discussion about double-encryption, and how it adds little more security (in terms of orders of magnitude), but I would like to know people's thoughts about the approach described above.  I DO understand that it's complete overkill, and that 256-bit AES encryption is more than sufficient by itself, but I'm interested to hear opinions at least from a theoretical point of view.  Does this potentially add much security?
The fact that a given cipher has a key length of 296 bits doesn't mean at all that it provides 296 bits of security or even that a brute force attack would take $2^{296}$ steps. The problem of mono-alphabetic substitution cipher is the ridiculously small block size (in this case, barely $\log 64 = 6$ bits). 

If absolutely nothing about the plaintext is known, every cipher is unbreakable, as there's no way of knowing if you got the right result.

In practice, you always know something about the plaintext. If that's not enough to launch a known-plaintext attack, your method might add some security form a theoretical point of view, but it's rather pointless in practice, since brute-forcing a 256-bit key is just as feasible as brute-forcing a 552-bit key.

However, if you do know enough plaintext, the mono-alphabetic substitution cipher doesn't add any security at all. After encrypting the known plaintext with an AES key, all you have to do is check if matching characters get mapped into matching characters. If they don't, discard the key; no further tests are required.