1

I was reading Serious Cryptography book. I am a newbie in cryptography field who try to learn as possible as he can. In this book, there is the following section of phrases:

For example, if a ciphertext is 128 bits long (meaning the plaintext is 128 bits as well), there are 2^128 possible ciphertexts; therefore, there should be 2^128 possible plaintexts from the attacker’s point of view. But if there are fewer than 2^128 possible keys, the attacker can rule out some plaintexts. If the key is only 64 bits, for example, the attacker can determine the 264 possible plaintexts and rule out the overwhelming majority of 128-bit strings. The attacker wouldn’t learn what the plaintext is, but they would learn what the plaintext is not, which makes the encryption’s secrecy imperfect.

I understand in OTP, plaintext and key should have a same size to generate a ciphertext with same size too. Also I understand the concept of randomness behind the key which that generate random output all the time.

But in this section I couldn't understand what he said when he mentioned if our key was less than 128 bit, the attacker can rule out some plaintext. What he mean? What is the meaning of rule out in this context? Sorry if this question is so basic.

0

I think Amussen mixed it while trying to make it clear.

Consider that you have 264 possible 128-bit keys instead of 2128 then the possible keyspace is reduced to half of its security.

This time you will ask how the attacker will know which ones are missing. Since we assume that everything is known but the key, we also know the key-space. So if we have time and money we can list them and see the possible messages and the reverse is the impossible messages.

Therefore read this

If the key is only 64 bits

as the effective key length of the key-space is 64-bit, i.e. the key generation can generate up to 264 different keys.

0

Bruce Schneier describes the process in his 1996 book, Applied Cryptography:

There’s no real security here. This kind of encryption is trivial to break, even without computers [587,1475]. It will only take a few seconds with a computer. Assume the plaintext is English. Furthermore, assume the key length is any small number of bytes. Here’s how to break it:

Discover the length of the key by a procedure known as counting coincidences [577]. XOR the ciphertext against itself shifted various numbers of bytes, and count those bytes that are equal. If the displacement is a multiple of the key length, then something over 6 percent of the bytes will be equal. If it is not, then less than 0.4 percent will be equal (assuming a random key encrypting normal ASCII text; other plaintext will have different numbers). This is called the index of coincidence. The smallest displacement that indicates a multiple of the key length is the length of the key.

Shift the ciphertext by that length and XOR it with itself. This removes the key and leaves you with plaintext XORed with the plaintext shifted the length of the key. Since English has 1.3 bits of real information per byte (see Section 11.1), there is plenty of redundancy for determining a unique decryption.

1
  • That is the X-Or cipher that repeats the key. Amussen talks about the reduced keyspace. At first, I've thought the same, the 64-bit repeats, however, But if there are fewer than 2^128 possible keys is indicating that they want to talk about effective key length. Amussen talk this in the context of the OTP, Schneier talk this before OTP. – kelalaka Jan 7 at 20:41

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.