What is the smallest plaintext/ciphertext size for an algorithm like?

Question

When I read about a choosen plaintext attack, for example on AES the block size is always 128 bits, does it mean the attacker will only supply 128 bits data words as "plain text" ?

Answer 1

"Known plaintext" means that the attacker has knowledge of some data and its encrypted counterpart, but he did not choose either (it is "chosen plaintext" when the attacker chooses the plaintext and obtains the corresponding ciphertext, and "chosen ciphertext" when he chooses the ciphertext and obtains the corresponding plaintext). What is "plaintext" depends on what the attacker is trying to attack.

AES is a block cipher: it operates on fixed-size values (the "blocks", 128 bits for AES). When encrypting arbitrary messages, a mode of operation is used; the mode decides how the input data is to be split and mangled and reassembled; the block cipher being only the central part of the process. However, whatever the mode is, at some point some block-sized values will go through the block cipher, because the block cipher cannot use anything else.

So, when discussing attacks on a block cipher (as opposed to: attacks on a symmetric encryption scheme which uses a block cipher and a mode of operation and possibly many other things), we concentrate on the number of (distinct) block values for which the attacker needs to know the plaintext and the corresponding ciphertext. For instance, linear cryptanalysis, when applied on DES, requires $2^{43}$ known plaintexts, i.e. 64-bit plaintext blocks and corresponding ciphertext (DES uses 64-bit blocks). With common modes of operation such as CBC, a block cipher with $n$-bit blocks will be invoked once every $n$ bits of input data, so this requirement translates to $2^{46}$ bytes worth of data (somewhat over 70 terabytes).

Huge amounts of known plaintext are of course impractical. Cryptographers still consider an attack to be "genuine" as long as it requires less than $2^n$ known plaintext and $2^{k}$ effort: if, for $n$-bit blocks, you have $2^{n}$ plaintext/ciphertext pairs, then you have the complete codebook and you do not need the key anymore; and with a $k$-bit key, trying out all possible keys has cost $2^{k}$ invocations of the block cipher. An attack is "real" (in an academic sense) if it does better than that, even by a small margin.

Answer 2

No. A known plaintext attack uses some real-life plaintext-ciphertext pair which the attacker somehow got to know (or guess, in the case of plaintext), or multiple such pairs known (or assumed) to be enciphered by the same key.

As you normally don't use a block cipher as-is, but in a mode of operation, this means usually some sequence of blocks, together with an initialization vector. In some modes it can even be a non-integer number of blocks, or even less than one block (for CTR mode).

When the key size is larger than the block size, there are multiple keys which map one plaintext block to the same ciphertext block - here you would need multiple different blocks to find the right one. (Of course, for AES even finding one key by brute-force is quite hard.)