0
$\begingroup$

Some mode of operation of block ciphers rely on the fact that E(k,0) is an unpredictable value when k is random and secret (with 0 denoting the all-zero binary string). Why is this a reasonable assumption?

$\endgroup$
  • 1
    $\begingroup$ I would say that specifying just a single zero as ciphertext is really bad practice. Either you should specify $0^{n}$ or indeed $0^{\{n\}}$ to specify a block of zeros of width $n$, just $0$ really doesn't cut it. $\endgroup$ – Maarten Bodewes Mar 30 '19 at 22:40
2
$\begingroup$

A block cipher, according to its design purpose, is assumed to be a pseudorandom permutation. This means when the key $k$ is chosen at random, $E(k,\cdot)$ can be viewed as a random permutation. Then, $E(k,0)$ is indistinguishable from a random value of the block length, hence unpredictable.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But what exactly does E(k,0) mean here? Does the all-zero binary string matter at all? $\endgroup$ – Kivi Mar 30 '19 at 21:01
  • $\begingroup$ @kivi Good point :) Actually E(k,x) is unpredictable for any x if x is the first query to E(k,.). $\endgroup$ – Shan Chen Mar 30 '19 at 21:52
0
$\begingroup$

If $\pi$ is a uniform random permutation of $\ell$-bit strings, then $\pi(0)$ is a uniform random $\ell$-bit string. (Similarly, the string $(\pi(0), \pi(1))$ is not uniformly distributed—it excludes the $2^\ell$ pairs of the form $(x, x)$—but it is very close.)

If you have a secure cryptosystem defined in terms of $\pi(0)$, and you instantiate it with $\pi = \operatorname{AES}_k$ where $k$ is a uniform random key, the fact that you're using a uniform random AES permutation instead of a uniform random permutation in general gives the adversary very little advantage in breaking the instantiation of the cryptosystem. So even though $\operatorname{AES}_k(0)$ may not have exactly uniform distribution when $k$ is uniformly distributed, it is close enough as far as any algorithms we know can discern.

| improve this answer | |
$\endgroup$

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.