. At first glance it seems as though an exhaustive key search is possible agains
ID: 3885760 • Letter: #
Question
. 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 exhaustive 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
OTP is not vulnerable to brute-force because a dictionary attack against an OTP yields the dictionary itself.Let's say you have the following encrypted message:
XYJT
And you know it was encrypted with a one-time pad. The problem is, if you followed the appropriate procedures, that encrypted message could be any four letter word. For example:
WEST (if the key was BURA)
EAST (if the key was TYRA)
CORN (if the key was VKSG)
So, for any four-letter message, there exists a four-character key that, when combined with the message produces "XYJT" as an output. And you lack a way to decide which of those is more or less likely than any else. So given any encrypted message, you have no way of choosing, of all the possible messages of that length, which message it could be.So if we do our exhaustive search, all it will tell us is that "the plaintext could be any message of length n". Which we knew already. We can still rule out the garbage, but doing so leaves us with every single non-garbage message of the correct length and tells nothing. A one time pad 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 keystream. If you try and guess the keystream you'll get nowhere, you can construct any 4 letter word simply by constructing the right keystream, so if you try to brute force the keystream you'll get literally every 4-letter word out and no idea which is correct.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.