2.4. At first glance it seems as though an exhaustive key search is possible aga
ID: 3745188 • Letter: 2
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
Brute-force attack do not work on OTP system as if we implement a dictionary attack(infinite computing resources) against an OTP, it gives the dictinoary itself.
lets assume we produce each bit of output as
Y0 = M0 XOR K0
where,
Y is output
M is the message
K is the key
Then each indivisual relation is a liner equation XOR with two unkown if the attacker knows the value for Y0 (be it 0 or 1). This is impossible to solve, the value for M0 cannot be determined. here the solutions M0 = 0 and M0 = 1 are equally likely to occour if K0 is from a random source. this situation will persist for the second equation and all the other subsequent equations.
Therefore by a burte force attack the message cannot be determined.
For a more practical approach let say we have message "CAGE" encrypted by OTP. If we know the key and following a procedure the encrypted message can be any 4 letter word.
For a 4-character message a 4-character key is required to produce the output "CAGE". As we lack a way to decide which message is more or less likely than any else. So given any encrypted message, we have no way of choosing of all the possible messages of that length.
Even for an exhaustive search the result will be "The text can be any message of lenght n". A OTP is different, unlike the keystream it's completely random and unpredictable, there's no basis to try and brute force anything because there's no key, just a completely random pre-shared key-stream. We can construct any 4 letter word simply by constructing the right keystream, so if you try to brute force the keystream we'll get literally every 4-letter word out and no idea which is the messege.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.