SymmetricCipher

Um - unless the key is at least as big as the data to be transferred (where size is in informational complexity - or, roughly, the size after maximum compression) then you can attack the encrypted data using statistical methods.  The ease of transferring the key before or afterhand, and the lower risk ("oh, the key was intercepted?  Don't use it then" versus "our top secret plans have been intercepted.  Ooops.") certainly stand though.  --Vitenka nitpicks.

Is that really always true? Assuming the encryption algorithm is such that there is no known attack better than searching through all possible keys, surely the only requirement on key size is that it takes one, on average, a suitably long time to search through all possible keys that the encrypted data becomes useless to the attacker by the time the right key has been found. This is the main idea behind all modern symmetrical ciphers, and cryptanalysis of them is precisely the attempt to find an "attack" - a statistical method of looking at available data that will decrypt the SecretData faster than a search of the key space. - MoonShadow nitpicks the nitpick

You might well know about the statistics, symmetries etc. of the original plaintext, but this is no help! Unless the cipher is badly broken, there should be no redundancy in the ciphertext - no point at which to start a statistical attack, no pattern or symmetry. Ciphertext is indistinguishable from random data; if this were not true, the SteganographicFileSystem would not work since you could just do a statistical analysis on each block to see if it contained encrypted plaintext. For that matter, well-compressed data should not be distinguishable from random numbers (i.e. contain redundancy, patterns etc.) - since if it were otherwise, this would imply you could compress it further and there it was not well-compressed to start with! - MoonShadow

Read section 8 of the sci.crypt FAQ, particularly the point of unicity distance. While you are not strictly wrong in that the output does have redundancy, it should not be redundancy you can usefully search for. Also note that combining redundant data with data that is indistinguishable from random data produces data that is indistinguishable from random data, not redundant data - othewise OTP would not work! ...and crypto algorithms are basically attempts to produce (a finite amount of) data that is statistically indistinguishable from random data, from a short key. Because the key is short, you can search all possible keys - that's due to precisely the redundancy you describe. Because the data produced is indistinguishable from random, you can't apply statistical attacks to the result, for the same reason you can't apply them to the result of a one time pad. I can't explain it any clearer - I don't have the background; perhaps someone else..? - MoonShadow

In general, no - but to discover which keys can't produce a given output would be an even worse brute-force problem barring advances in cryptoanalysis.

Problem being that no matter how good your algorithm, the result is always slightly more informational than truly random data - otherwise there'd be no way to get your data back - again, without a key as long as the data.

Information content is described as how compressible the data is - the less compressible it is, the less redundancy and therefore the more information it contains. Therefore, it is impossible to get an information content greater than that in truly random data. If, OTOH, you means that the output of your algorithm will always contain more redundancy than the original, this is simply not so. Redundancy in the output of a cipher is precisely the sort of thing cryptanalysts look for - a cipher with redundancy in its output is considered broken and should not be used. - MoonShadow

I suggest you try reading the [sci.crypt FAQ], then. The only known cipher not susceptible to brute force attack is the OneTimePad?. - MoonShadow

This is why cryptanalysts don't trust crypto algorithms until they have been aggressively peer-reviewed for a number of years without a better attack than brute force search being found, and usually not even then. - MoonShadow

You try and guess what key length to use based on how long you want it to stay secret for. There is an underlying assumption that no better way will be found in the meantime. For instance, a lot of data intended to last for 20+ years gets archived under 4096-bit RSA/1024-bit IDEA. The decision was made after observing how computing power and factoring algorithms improved over several years, and makes the assumption that no significant breakthrough in factoring (e.g. one that reduces the time to factor N to O(log N) or less) will be made in the future. If one is, they're basically stuffed. You also have to take into account how much computing power E can afford to buy.

That is all true.  I guess I kinda misinterpreted the way an attack improved.  I suppose that by having a key that is smaller, you take a risk - but as long as that risk is sufficiently well understood it doesn't matter.  --Vitenka  But surely all of those algorithms are more attackable than a one time pad - it's just known that they are safe _enough_?

That is perfectly true. The reason they exist is that OTPs are pretty much unusable for most everyday purposes, because (a) usually you don't know in advance you'll need to communicate, (b) the communication usually needs to reach the other end quickly, and hence (c) if you can usefully share an OTP secretly, you may as well just use that channel to share your SecretData. - MoonShadow