Lower Bound on the Probability of Successful Substitution of Messages

We prove that the probability of successful substitution of messages for the optimal strategy is not less than $K^{-1/2}$ for an arbitrary probability distribution of messages provided the probability of each message is less than or equal to 1/2. Here $K$ is the number of keys.