2
$\begingroup$

It seems to me (a non-expert obviously) that the brute-force breakability of symmetric encryption algorithms is usually (always?) expressed as "would take approximately N time on such-and-such hardware".

But in practice, how would one single attempt among trillions at finding the key be identified as "the right one" that succesfully decrypts the message? Doesn't that require the result of the attempt (i.e. the "plaintext" result) to be recognizable as such?

If yes, doesn't this mean that if the plaintext is not easily and quickly recognizable as such (as for example ASCII-encoded English prose might be), brute-force is in practice MUCH harder than the so-much-time-on-such-hardware description suggests?

And if yes, doesn't this mean that a trivial (but unknown) "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force attack hugely more difficult?

$\endgroup$
  • $\begingroup$ How do you define "brute force"? Note that in formal definitions of security, the attacker's goal is rarely to find the key. $\endgroup$ – fkraiem Nov 5 '16 at 9:05
  • $\begingroup$ I would define brute-force as trying all possible keys in order to find the right one. $\endgroup$ – Peter M. Nov 5 '16 at 9:26
  • $\begingroup$ When we design crypto, we try to guarantee a minimum strength. Making brute-force utterly infeasible is easy (a random key with a few hundred bits is clearly enough), so why people working on the defense care about minor practical complications an attacker would face? $\endgroup$ – CodesInChaos Nov 5 '16 at 9:29
1
$\begingroup$

If yes, doesn't this mean that if the plaintext is not easily and quickly recognizable as such (as for example ASCII-encoded English prose might be), brute-force is in practice MUCH harder than the so-much-time-on-such-hardware description suggests?

If the plaintext is not recognizable at all (random numbers (from a good generator)) and if the attacker has no other way to test if it is the real data, you are right, just brute-forcing solves nothing.

But, other than good random numbers, what kind of data is not recognizable for someone knowing a bit about computers? Text no, Images no, any file format from known programs no, any file format from unknown programs no (eg. low entropy and many more things), sometimes there are checksums as part of the data, and so on...

And if yes, doesn't this mean that a trivial (but unknown) "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force attack hugely more difficult?

No, ROT13, data compression and other preprocessing steps (other than good encryption with a different key) do not add security.

Because, even if the attacker doesn't know about the preprocessing step (which should not be assumed, listen to Kerckhoff), such things can be detected easily. Eg. ASCII text with ROT13 is still ASCII text (ie. A-Z), just not as readable. Getting an output with mostly english letters when trying AES keys is unusual => time look at it closer.

The practical scenario I have in mind is the encryption of one's own files on disk, using a standard algorithm, e.g. AES.

Lets take a disk with 1TB. The chance that, with 2^128 keys, multiple keys lead to a sane output (each one of size 2^(8*1024*1024*1024*1024)), is pretty small. And content of a HDD with OS and music and whatever on it is easily recognizable.

$\endgroup$
0
$\begingroup$

Indeed if you are encrypting a random string it is impossible to test for success after an attempted decryption. However you almost never encrypt only random strings without using them for anything afterwards so this is a rather unlikely scenario.

Usually known-plaintext-attacks are one of the weaker attacks and your attacker doesn't even get that. What we really want is our system to be secure even against more powerful attacks like chosen-plaintext attacks.

$\endgroup$
  • $\begingroup$ The practical scenario I have in mind is the encryption of one's own files on disk, using a standard algorithm, e.g. AES. I don't see how a chosen-plaintext attack pertains to that situation (but correct me if I'm wrong). It seems to me that even if someone has hardware that makes a brute-force attack feasible in terms of computation time, it is hopeless if I trivially "scrambled" my files prior to AES encryption. Right or wrong? $\endgroup$ – Peter M. Nov 5 '16 at 9:48

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.