Brute Force attack Question
Hello, I've been thinking about brute force attacks, and there is something that I do not understand. Maybe someone could explain me where I am wrong. Suppose Alice sends letters to BoB, and they always exchange plain text ASCII data. Suppose also that they use DES for encryption. They are afraid that Perry intercepts their messages and tries to brute force their DES key. Perry has 100,000 computers (and 20,000 couriers alone:) and his brute force attacks are as follows: he tries all keys in succession, looks at the decrypted texts, and *if* the decrypted text looks like a potential message (has only ASCII characters for example) he looks at that key closer as it is likely that he has found the right key. What is Alice and Bob decide to obscure their letters and add random NON-ASCII characters at random places? They may agree to just ignore all non-ASCII characters, so these characters would never change the meaning of their letters. If they do that, Perry does not have any easy way to tell whether he really recovered the right plaintext or not, because even correct key would still produce a lot of non-ASCII characters. If percentage of ASCII characters in all 256 byte space is 40%, Alice and Bob may agree to put in junk characters to make up exactly 60% of the message. This way messages will look like random character data. Is there any good method for attackers to circumvent this obscurity? What is the general method to make a judgment whether the recovered text really is a plain text if Alice and Bob noisify their letters? I can think of this: we sift through all recovered plaintexts and remove all non-ASCII bytes, and then do some simple testing to see whether the remaining ASCII data resembles normal English texts. This kind of testing seems to be quite expensive though, compared to just testing for ASCII vs. non-ascii bytes. Anything else I am missig? Thanks. - Igor.
-----BEGIN PGP SIGNED MESSAGE----- On Wed, 24 Jul 1996, Igor Chudov wrote:
Suppose Alice sends letters to BoB, and they always exchange plain text ASCII data. Suppose also that they use DES for encryption. They are afraid that Perry intercepts their messages and tries to brute force their DES key.
Perry has 100,000 computers (and 20,000 couriers alone:) and his brute force attacks are as follows: he tries all keys in succession, looks at the decrypted texts, and *if* the decrypted text looks like a potential message (has only ASCII characters for example) he looks at that key closer as it is likely that he has found the right key.
What is Alice and Bob decide to obscure their letters and add random NON-ASCII characters at random places? They may agree to just ignore all non-ASCII characters, so these characters would never change the meaning of their letters. If they do that, Perry does not have any easy way to tell whether he really recovered the right plaintext or not, because even correct key would still produce a lot of non-ASCII characters.
If percentage of ASCII characters in all 256 byte space is 40%, Alice and Bob may agree to put in junk characters to make up exactly 60% of the message. This way messages will look like random character data.
Is there any good method for attackers to circumvent this obscurity? What is the general method to make a judgment whether the recovered text really is a plain text if Alice and Bob noisify their letters?
I can think of this: we sift through all recovered plaintexts and remove all non-ASCII bytes, and then do some simple testing to see whether the remaining ASCII data resembles normal English texts. This kind of testing seems to be quite expensive though, compared to just testing for ASCII vs. non-ascii bytes. Anything else I am missig?
If the attacker uses a known-plaintext attack, then all this is a non-issue. However, if the attacker is using a ciphertext-only attack, looking for the MSB to be 0 is a good way to find a correct decryption. Also, randomness tests could be run on recovered plaintexts. This is why compression before encryption is a good idea. If the plaintext is completely random, then there is no way to crack the ciphertext. - -- Mark PGP encrypted mail prefered Key fingerprint = d61734f2800486ae6f79bfeb70f95348 http://www.voicenet.com/~markm/ -----BEGIN PGP SIGNATURE----- Version: 2.6.3 Charset: noconv iQCVAwUBMfZzibZc+sv5siulAQEjOAQAsbTWucrq0yI8W1j0C1mQHiciFsRNyabH PatrW7m67qEy4Xgw+D7dDMURjjdkQFOAm1L4t0QCIuUNIa31H74x6e/qnNQn8WAs VBx95B1yQ8RF86rPEMkHO78FVDeQM+/oP2Dqe2/I6dO+pj5YLJ8E1IsBJz+JrUZl eXSDvmYNLp0= =QfTu -----END PGP SIGNATURE-----
Igor Chudov writes:
What is Alice and Bob decide to obscure their letters and add random NON-ASCII characters at random places?
Assuming I'm using a statistics based technique, that won't help. Superencipherment might, but then again, thats sort of what 3DES is, right?
If percentage of ASCII characters in all 256 byte space is 40%, Alice and Bob may agree to put in junk characters to make up exactly 60% of the message. This way messages will look like random character data.
Nope, it wouldn't. The statistics would be off. Perry
Perry E. Metzger writes:
Igor Chudov writes:
What is Alice and Bob decide to obscure their letters and add random NON-ASCII characters at random places?
Assuming I'm using a statistics based technique, that won't help.
Some fairly basic questions: 1) Is a statistical test like this done on the net composition of the whole message or locally, point by point throughout the text (for example, using a window)? 2) If what's tested is the net composition of the message, could you choose padding to normalize a message back to an apparently random distribution? 3) What kind of computation overhead does this statistical testing impose (compared to what would be needed for a known-plaintext search)? Thanks, Joel/ -- ===================================================================== Joel.Morgan@Helsinki.FI http://blues.helsinki.fi/~morgan "Over the mountains there are mountains." -- Chang-rae Lee =====================================================================
participants (4)
-
ichudov＠galaxy.galstar.com -
Mark M. -
morgan＠keilin.helsinki.fi -
Perry E. Metzger