Skip to main content
Cryptography

Return to Answer

Minimal typo corrections.
Source Link
e-sushi
e-sushi
  • 18.1k
  • 12
  • 85
  • 235

If a cipher has independent round keys, then it is trivially susceptible to a meet-in-the-middle attack. Independence of the rounds means you can brute force the first half of the rounds and second half of the rounds separately. A cipher with independent round keys totaling $n$ bits can be brute forced in $2^{n/2}$ time. So, from the point of view considering keylengthkey length alone, this is not a very good cipher.

However, it is likely that $n/2$ is much greater than the keylengthkey length of the thing you started with. And it seems very plausible that the cipher could actually achieve security in the neighborhood of $2^{n/2}$ (as opposed to $2^{n/2}$ just being the obvious upper bound). Heuristically at least, the key schedule is supposed to derive many "independent-looking" keys from a single key. So the cipher may have been designed and analyzed based on the heuristic that is now the reality.

So I don't think it's a big stretch to consider such a cipher to be secure with $n/2$ bits of security, though it's not the most aesthetically pleasing way to get $n/2$ bits of security.

If a cipher has independent round keys, then it is trivially susceptible to a meet-in-the-middle attack. Independence of the rounds means you can brute force the first half of the rounds and second half of the rounds separately. A cipher with independent round keys totaling $n$ bits can be brute forced in $2^{n/2}$ time. So, from the point of view considering keylength alone, this is not a very good cipher.

However, it is likely that $n/2$ is much greater than the keylength of the thing you started with. And it seems very plausible that the cipher could actually achieve security in the neighborhood of $2^{n/2}$ (as opposed to $2^{n/2}$ just being the obvious upper bound). Heuristically at least, the key schedule is supposed to derive many "independent-looking" keys from a single key. So the cipher may have been designed and analyzed based on the heuristic that is now the reality.

So I don't think it's a big stretch to consider such a cipher to be secure with $n/2$ bits of security, though it's not the most aesthetically pleasing way to get $n/2$ bits of security.

If a cipher has independent round keys, then it is trivially susceptible to a meet-in-the-middle attack. Independence of the rounds means you can brute force the first half of the rounds and second half of the rounds separately. A cipher with independent round keys totaling $n$ bits can be brute forced in $2^{n/2}$ time. So, from the point of view considering key length alone, this is not a very good cipher.

However, it is likely that $n/2$ is much greater than the key length of the thing you started with. And it seems very plausible that the cipher could actually achieve security in the neighborhood of $2^{n/2}$ (as opposed to $2^{n/2}$ just being the obvious upper bound). Heuristically at least, the key schedule is supposed to derive many "independent-looking" keys from a single key. So the cipher may have been designed and analyzed based on the heuristic that is now the reality.

So I don't think it's a big stretch to consider such a cipher to be secure with $n/2$ bits of security, though it's not the most aesthetically pleasing way to get $n/2$ bits of security.

Source Link
Mikero
Mikero
  • 14.5k
  • 2
  • 35
  • 56

If a cipher has independent round keys, then it is trivially susceptible to a meet-in-the-middle attack. Independence of the rounds means you can brute force the first half of the rounds and second half of the rounds separately. A cipher with independent round keys totaling $n$ bits can be brute forced in $2^{n/2}$ time. So, from the point of view considering keylength alone, this is not a very good cipher.

However, it is likely that $n/2$ is much greater than the keylength of the thing you started with. And it seems very plausible that the cipher could actually achieve security in the neighborhood of $2^{n/2}$ (as opposed to $2^{n/2}$ just being the obvious upper bound). Heuristically at least, the key schedule is supposed to derive many "independent-looking" keys from a single key. So the cipher may have been designed and analyzed based on the heuristic that is now the reality.

So I don't think it's a big stretch to consider such a cipher to be secure with $n/2$ bits of security, though it's not the most aesthetically pleasing way to get $n/2$ bits of security.