How can one break a monoalphbetic substitution chipher at pseudorandom text?

Question

Does anybody know how to break monoalphbetic substitution cipher, if it is applied to some pseudorandom text (for example to some surrogate key filed in a database)?

Let us assume that we have only cipher text, and don't know anything about distribution of different characters appearance probabilities, so frequency analysis doesn't work. Is there some other approach?

Background: I just need to "encrypt" (not really encrypt, possibility to decrypt is not necessary) key fields in a db, keeping the length of it and avoiding collisions (don't ask why).

And I just cannot google out some encryption algorithm which will satisfy both clauses. Cryptographic hash functions are too long, common encryption algorithms can not guaranty absence of collisions, and actually also basically have a limit of length. So the only solution which I can imagine is a substitution cipher, and I want to know how weak it would be in my case.

Answer 1

One problem with a mono-alphabetic substitution cipher is that an attacker would gain a lot of information if (s)he gets just one plain-cipher pair. Given few plain-cipher pairs, the attacker can probably break your full cipher.

You wrote that (at least part of) the encrypted data is a surrogate key. These keys should have all the same format (like 32-bit or 64-bit number) and should be better encrypted with a block-cipher for the required block size (see also the 2nd link in Paŭlo 3rd comment to your question).

If you have also data of different size (which seems to be the case), you should consider taking a family of block ciphers such that you have a (different) block cipher for each byte-length and encrypt the data with the block cipher according to its bytelength.

Answer 2

First of all, such a cipher would never be considered secure. Given a single plaintext-ciphertext pair, one could easily extract the key, compromising all other ciphertexts. This means that to be even considering this you have to rule out the possibility that an attacker could get such a pair. (Which you probably cannot.)

But even if we assume, that nobody could ever get hold of a plaintext-ciphertext pair this would probably be easy to break. The problem is that the number of possible keys is very small for a monoalphabetic substitution cipher. This means that the attacker can severely reduce the number of possible plaintexts. Without the ciphertext, (considering ASCII symbols) an attacker, simply guessing the plaintext, would have a success probability of $\frac{1}{|m|^{255}}$. Given the ciphertext, the success probability is $\frac{1}{255}$, which would constitute a successful attack.

edit: yea, that last part is bullshit