A block cipher is (or tries to be) a pseudorandom permutation on a given space. Let $\mathcal{M}$ be the set of $n$-bit blocks for a given $n$. There are $2^n$ possible block values, and a permutation on $\mathcal{M}$ sends each block value to another value. There are $2^n!$ such permutations. A block cipher is a mapping from key values (in a given key space $\mathcal{K}$) to permutations on $\mathcal{M}$.
For instance, AES-256 is a block cipher which operates on 128-bit blocks and uses a 256-bit key. Each possible key value ($2^{256}$ possibilities) selects a permutation among the $2^{128}!$ of the space of 128-bit blocks (which has size $2^{128}$).
For the block cipher $\phi$ to have any practical value, it shall be easily computed: given a key $k$ and an input block $x$, applying the permutation $\phi_k$ selected by $k$ on $x$ takes a small amount of computing power. Usually, the inverse permutation is also easily computed: given $k$ and $y$, find $x$ such that $\phi_k(x) = y$.
The main security assumption on block ciphers is indistinguishability: for whoever does not know $k$, the permutation $\phi_k$ should behave as if it had been selected at random and uniformly among the $2^n!$ possible permutations of $\mathcal{M}$. This can be illustrated with the following experiment: suppose that I give two black boxes which compute, respectively, $\phi_k$ and on inputs $x$ of your choosing, and yields the corresponding output. I do not tell you the value of $k$. At any time, when you have sent $q$ requests ($q$ block values $x$ to encrypt), your goal is to predict the output of the box on yet another input $x$ that is distinct from your previous $q$ inputs. Since $\phi_k$ is a permutation, you know that the output will be different from the $q$ previous outputs, so there are $2^n-q$ possibilities. The block cipher is "secure" if you cannot predict the output correctly with probability substantially better than $1/(2^n-q)$.
(This "black box" model is a bit simplified; in fact, I should give you two black boxes computing $\phi_k$ and $\phi_k^{-1}$ respectively, and each of your $q$ request is for one of the boxes, at your choice.)
The "black box" model explains why a simple XOR is a very poor block cipher. If you define $\phi$ such that keys are also sequences of $n$-bits, and $\phi_k(x) = k \oplus x$, then a single request to the encryption black box allows recomputing $k$ (with $k = x \oplus \phi_k(x)$) and thus predict output for all other requests with 100% accuracy.
Terminology is the following:
Known Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ but does not get to choose $x$ or $\phi_k(x)$.
Chosen Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ where he can choose the $x$ values at will.
Adaptive Chosen Plaintext Attack: a CPA attack where the attacker is allowed to think a lot between each two requests; meaning that when he selects the next request $x$ to send to the black box, then he can do so after due inspection of the previously obtained outputs.
Chosen Ciphertext Attack: attacker obtains $q$ pairs $(\phi_k^{-1}(y),y)$ where he can choose the $y$ values at will.
Adaptive Chosen Ciphertext Attack: a CCA attack where the attacker can think between any two successive requests.
The "gold standard" is called IND-CCA2 which means "indistinguishable from a random permutation against adaptive chosen ciphertext attacks".
(The description above is slightly simplified; true formal exposition would use Turing machines and a game between a challenger and a prover; but it should give you the intuition.)
There are limits to the indistinguishability. Indeed, if you allow $q$ to raise up to $2^n-1$ then the notion ceases to be interesting; if the attacker can send requests for all possible block values except one, then he can predict the missing one with probability 1: it is the one output that he did not get yet. Also, indistinguishability cannot hold beyond exhaustive search on the key space: if the attacker can try all possible key values, then he can look for a match with the outputs he got. Once he gets the key, he can predict with probability 1.
It is customary to study algorithms where keys are sequences of $r$ bits (e.g. $r = 256$ for AES-256). The "exhaustive search" attack has average cost $2^{r-1}$ (the attacker needs, on average, to try half the keys before hitting the right one). So, the security of any block cipher tends to break down when the attacker is "allowed" too many requests and/or too much computing power.
In practice, for a block cipher with $n$-bit blocks and $r$-bit keys, we consider an attack to be "academically successful" if it can predict the black box output with the following conditions:
- Attacker can send $q$ requests to the encryption or decryption box with $q \leq 2^{n-1}$ (attacker can obtain "half of the code book").
- Attacker can spend enough CPU to compute $2^{r-1}$ evaluations of the function.
- Attacker also has access to $2^{r-1}$ bits of very fast RAM.
- Attacker's probability to predict the next output is at least $3/4$.
With $2^{r-1}$ evaluations of the function, attacker's success with the simple exhaustive search and $2^{n-1}$ requests will be $1/2+2^{-(n-1)}$ (50% chance of having found the key through the search, and, if not, the knowledge that the next output will be in the code book half that the attacker did not get with his $q$ initial requests). Hence the $3/4$ criterion: attacker must be able to do better than this generic attack.
For instance, if you consider 3DES: block size is $n = 64$, and key size is $r = 168$ (the standard says "192 bits" but the algorithm simply ignores 24 of these bits, so for the cryptographer the key size is 168 bits). There is a known "meet-in-the-middle" attack which requires $2^{62}$ bits of storage (for $2^{56}$ words of 64 bits), computational effort equivalent to about $(2/3)·2^{112}$ evaluations of 3DES, and only 2 known plaintexts. This attack cannot be implemented with existing technology (the storage requirement would be quite expensive, since we are talking about half a millions of terabytes of fast RAM; and the CPU requirements is simply completely out of reach because it would requires way more energy than what Mankind produces as a whole). Yet it counts as a break. In that sense, 3DES is "academically broken".
Modes of operation turn a block cipher into something which can encrypt and decrypt messages of almost arbitrary length, not just single block values. Each mode of operation has its own requirements, in particular with any Initialization Vector. For instance, with CBC, in a "black box" model similar to what is described above, the encryption system must generate IV values randomly, uniformly, with values which are not predictable by the attacker (the BEAST attack on SSL/TLS builds on IV predictability, in the sense that the attacker can know the IV before choosing his plaintext for the next request).
As a generic rule, most modes of operation run into trouble when the amount of encrypted data exceeds about $2^{n/2}$ blocks. This is the threshold at which a pseudorandom permutation begins to behave differently from a pseudorandom function (a permutation is injective: it won't give you the same output with two distinct inputs; whereas a random function, on average, is not injective). This is why AES was defined with 128-bit blocks, as opposed to 3DES 64-bit blocks: to give us enough room in practical situations.
