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

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.

-

## migrated from stackoverflow.comOct 18 '11 at 12:12

This question came from our site for professional and enthusiast programmers.

Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Oct 18 '11 at 12:23
Actually, any encryption algorithm which has a corresponding decryption algorithm must guarantee absence of collisions, otherwise decryption would not be possible. –  Paŭlo Ebermann Oct 18 '11 at 12:39

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.

-

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

-
The number of all general monoalphabetic substitution cipher keys is $|\Sigma|!$, where $\Sigma$ is the alphabet. This is still quite a large number ($256! \approx 2^{1684}$ (one byte), $92! \approx 2^{472}$ (printable ASCII), $26! \approx 2^{88}$ (english alphabet)). –  Paŭlo Ebermann Oct 18 '11 at 17:29