2.4. At first glance it seems as though an exhaustive key search is possible aga

Question

2.4. At first glance it seems as though an exhaustive key search is possible against an OTP system. Given is a short message, let’s say 5 ASCII characters represented by 40 bit, which was encrypted using a 40-bit OTP. Explain exactly why an exhaus- tive key search will not succeed even though sufficient computational resources are available. This is a paradox since we know that the OTP is unconditionally secure. That is, explain why a brute-force attack does not work.

Note: You have to resolve the paradox! That means answers such as “The OTP is unconditionally secure and therefore a brute-force attack does not work” are not valid.

Explanation / Answer

we want to prove that even if attacker has infinte computing resource. He can not decipher the message crpyted using a one time pad.

okay let say we produce each bit of output as Y0=M0 xor K0 (y is output, M is message and K is the key)

Each individual relation is a linear equation XOR with two unknowns. They

are impossible to solve. If the attacker knows the value for Y0 (0 or 1), he cannot

determine the value of M0. In fact, the solutions M0 =0 and M0 =1 are exactly equally

likely if K0 stems from a truly random source and there is 50% chance that it has the

value 0 and 1. The situation is identical for the second equation and all subsequent

ones.

Hence even though the attacker has infinite computing resource he cannot determine

the message signal.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.