I can understand that ROT13 is not secure for obvious reasons, but I'm looking for the theoretical answer. Wikipedia says "The algorithm provides no cryptographic security.." What does it mean to provide cryptographic security? Why does it provide no security as opposed to, say, very little security?
What would make ROT13 easy to crack from an automated program (e.g. one that had no knowledge at all of what the encryption cipher was)? How is a cipher measurably "weak?"
I think I understand what you're asking for. You're trying to learn how we know which algorithm was used, so we know how to attack it. That's a part of what is known as cryptanalysis, the task of breaking ciphers.
If you are using a standard computer protocol, the encryption algorithm is defined as a part of the protocol. The computers can't talk unless both know what algorithm is in use. No attempt is made to keep it secret.
Generally there are plenty of clues will tell you what's going on. If things are flowing through port 443, the attacker is going to assume it's SSL protocol, look for the header which indicates what algorithms are in use, and begin there.
(If you're reading a joke or a movie plot on-line, ROT-13 has traditionally been used to keep you from accidentally seeing the punchline or spoiler until you're ready. Thus, ROT-13 is actually a de facto standard. Note that "standard" does not necessarily mean "secure".)
Even without knowledge of the protocol, though, there are usually other ways to figure out which algorithm was used. The old school tool is frequency analysis. The cryptanalyst (the guy whose job is to break the cryptography) might plot out the frequency of characters. Normal English text follows a distribution such that the letter E appears 12% of the time, T appears 9%, A, O, I, and N appear about 8% each, and so on. (The nonsense words ETAOIN SHRDLU represent the 12 most common letters in English in descending order.) If the distribution of letters in the ciphertext approximately follows this same distribution, the cryptanalyst can assume a transposition cipher was used to shuffle the plaintext letters. If a different set of letters follows the same distribution, it's likely that a simple substitution cipher was used. (ROT-13 follows this pattern, by the way, and can be spotted because the distribution will be RGNBVA FUEQYH.)
If the distribution is flatter, the cryptanalyst might try measuring the distribution for every other letter, or every third letter, or every fourth letter, etc. If the distribution suddenly follows that same 12,9,8,8,8,8 curve, then the cryptanalyst has discovered that a Vigenere cipher or polyalphabetic cipher might have been used.
Once the algorithm is known, the next task is finding the key. Frequency analysis can help with the simpler codes, but with the advent of computers a different attack becomes possible. A computer can quickly try every possible key, which is called a brute-force attack. The number of keys you would have to try is called the keyspace. The classical Caesar cipher is a rotation cipher with a key of 3 (shift every letter to the left by 3 places.) The keyspace of a Caesar cipher is $26^1 - 1$ (there are 26 possible shifts, but cleartext is not considered encrypted), or just 25. Because these increase exponentially with the number of possible keys, and because brute-forcing is generally done with computers, it's common to refer to these with power of 2 exponent notation. The keysize is generally referred to by the number of bits. The next power of 2 greater than or equal to 25 is 32, ($32 = 2^5$), so we can say the keysize of a Caesar cipher is 5.
Because the algorithm and key of ROT-13 is known (the algorithm is ROTate, and the key is 13) the keyspace is 1, and the only possible result is to decrypt. The keysize of ROT13 is $1^{1} = 1$. The next power of 2 greater than or equal to 1 is $2^0 = 1$. Therefore the keysize (the exponent) is zero.
Keysize is an upper boundary of cryptographic security for an algorithm, as it represents the number of tries using brute force. A 40 bit keysize (2^40) is easily brute forced on a home PC. DES, with a 56 bit key length, was brute forced in the 1990s on a special purpose-built computer (Deep Crack.) Keysize is an upper boundary only, because if an attacker can figure out a cryptographic weakness in the algorithm, they can use it to reduce the number of brute force attempts. 80 bits is right at the margin of what is considered safe - advances in computer power make brute forcing larger keys more and more possible.
(Please note that this explanation doesn't work the same for RSA keys, where factoring a public key is the method of brute force. Today, a 1024 bit key is right on the margin of safety, and is not expected to remain safe much longer.)
Cryptanalysis is a fascinating study, and is highly recommended for anyone interested in cryptography. Being able to break protocols or ciphers is the first step in understanding what is needed to make protocols and ciphers more secure.
Kerckhoffs's principle states, that a cryptographic system shall be secure even if everything about the system, except the key, is known to the attacker.
Typically an encryption algorithm has two inputs:
In the case of Rot13, there is no key. So if you know the algorithm, there is nothing left to guess.
Let's assume the algorithm was not Rot13, but RotX. This is called a Caesar cipher.
Now the knowledge of the algorithm alone, is not sufficient anymore. The attacker needs to "guess" the X.
A Caesar cipher is still a very weak algorithm: the number of possible values for X is very small. X is used many times to encrypt a message, so characteristics of the plain text such as common letters show up in the cipher text.
I'm not exactly certain why "the obvious reasons" ROT13 isn't secure wouldn't be considered the appropriate answer; it's not secure (that is, doesn't provide privacy) because anyone can decrypt it trivially (whether they're the intended recipient or not).
If you want to get into the details about why it is not secure, well, we need to talk about "security through obscurity" and why it is a bad idea. This term refers to any system where knowledge of how the system works is sufficient to allow anyone to decrypt the traffic (or otherwise break the system). This is considered a bad idea, because we generally need to assume that the attacker might be able to learn more than we care for him to, and he might just learn the system. If he does, well, the entire security of the system goes away, and the only remedy is to replace the system with something else entirely, and replacing the system with something that's we should have confidence in is hard.
What we generally do, rather than using "security through obscurity", is break the system into two halves; the cipher and the key. The cipher is the recipe for taking the key and the plaintext and producing the ciphertext; it is hard to design (but that work has already been done; there are a number of well-regarded public designs available). The key is easy to create and easy to replace; we can update the key whenever we think the system may be compromised. In fact, the key is so easy to replace, we generally periodically replace the keys (after all, the attacker generally doesn't tell us that he got his hands on a copy of the key and he can now read the traffic).
Because the cipher is hard to replace, well, we arrange things so we don't mind if the attacker learns it. In fact, sometimes we tell him what cipher we're using (not specifically to make his life easier; instead, we generally do this to communicate with the recipient before we've established a secure connection); since we're not relying on the secrecy of the cipher for security, we can do this. Instead, the security of the system relies on the key, which is easy to replace.
The bottom line: because ROT13 does not have any keys that can be replaced, and anyone who knows/guesses that ROT13 is being used to read the traffic, we generally assume it doesn't provide any real security (which, when you come down to it, is the same idea as the "obvious reason", only using more words).
In fact, ROT13 doesn't even do "security through obscurity" very well because it isn't very obscure; it's built into many Web browsers, and it's not hard to recognize ROT13'ed English after you've seen it a number of times (which many people have).
CodesInChaos nailed it -- the key size is zero. The strength of an algorithm is roughly determined by how many tries someone who didn't know the key would need in order to successfully decrypt the message. In the case of ROT13, the key size is zero, and anyone attempting to decrypt the message would succeed on the first try.
Let's say the person who intercepts the message doesn't know what cipher was used. As long as the message is large enough (sar 30 to 40 characters), it can still be broken (I do it all the time playing Cryptograms.org, which uses a simple substitution cipher, a general class of ciphers to which ROT13 belongs).
The process is easy, the most common letter in English texts is e. So, the attacker figures out which ciphertext letter occurs most often (say it is R). You then replace e with R (switch case so you know what you have changed). Then you move to the next most frequent letter (look at a frequency chart). After you have a few of these done, you can start looking at potential words. For example if I have T_E, chances are whatever letter is in the blank is was substituted for H to make THE. Continue the process and you will eventually break the ciphertext.
In short, even without knowing that the person used ROT13, one could use statistical analysis to figure out the plaintext. Go try it out on Cryptograms.org and also pick up a copy of The Code Book to learn about real life examples of when these types of ciphers were broken (leading to the death of a person in at least one case).
Quite simply, ROT-13 provides zero security because it has no key. There is no "secret" inherent in the system which makes it difficult to crack. The algorithm is a simple shift cipher, but unlike other "Caesar ciphers" the system uses a fixed, predetermined number of places to shift. Even worse, the shift is 13 places, basically creating complementary pairs of letters; all As become Ns and all Ns become As. As a result, all you need to know is that ROT13 is being used, flip the letters to their complement and you have the plaintext. As an encryption scheme (which requires both sides to know the scheme being used), it's completely broken.
The theoretical answer is thus that there is no secret data needed to solve the problem. Shift ciphers, properly implemented, are very secure (the "one-time pad" is still a standard among spooks), but they require a high amount of random "secrets". ROT13 has none.
