Score:2

Is OTP still perfectly secure if we limit message and key space

cn flag

If we have a message space M {0,1,2,3,4,5,6} and likewise keyspace is K = {0,1,2,3,4,5,6} (generator choosen uniform keys k)

We define our encryption to be the XOR of their bitwise rep on K and M using 4 bits {0000, 0001, 0010, 0011, 0100, 0101, 0110}

This is one time pad right? Because we are XORing and using the a key of same length.

However here the message and keyspace is represented using 4 bits; it is also limited to values within the inclusive range 0000 to 0110.

Does that violate the perfect secrecy in any way? Perfect secrecy says regardless of prior info known to the attacker the ciphertext wont leak any additional info.

Score:21
my flag

Does that violate the perfect secrecy in any way?

Yes, obviously. Restricting the message space doesn't hurt in any way (the attacker can't get any additional information about the message, even if he knows quite a lot about it already); restricting the key does.

OTP uses a group operation to combine the message and the key; one thing that it needs to assume is that the group members that make up the key are chosen uniformly randomly from all possible group elements - with your example, this is not the case.

Specifically, if we see in the ciphertext the value 0111, we can deduce from that is that the corresponding plaintext value is not 0000; after all, for that to be the case, the key value would have been 0111, and we know that's not the case. That are values that the attacker can deduce are not the message, and this is a violation of perfect secrecy.

Now, if you did have the message and key consisting of values from 0 to 6, the obvious thing to do is change the group operation to 'addition modulo 7'; that is, to encrypt, you add the message to the key, and then if that value is 7 or more, subtract 7 - that gives you the ciphertext. And, to decrypt, you do 'subtraction modulo 7'; you subtract the key from the ciphertext, and if that value is negative, add 7. This is a perfectly valid group operation, and since all values of the key are possible (and presumably equiprobable), it can satisfy the requirements of perfect secrecy.

Jack avatar
cn flag
Hi, why is it that if the ciphertext value 0111 we know that the plaintext will not be 0000? Is it because the key and message cannot be the same? However if we do not restrict the key space tot he same set of values as the message space as mentioned above, would this be allowed? I am confused.
Chris Peikert avatar
in flag
The ciphertext 0111 cannot have underlying plaintext 0000 because 0111 is not an allowed key under the system you presented; plaintext 0000 could only yield ciphertext 0111 if the key was 0111.
SAI Peregrinus avatar
si flag
I'd also note that a naive modulo operation using a conditional subtraction as described may lead to a side-channel leakage of data. The mathematical "perfect secrecy" isn't violated but the real-world secrecy can be!
poncho avatar
my flag
@SAIPeregrinus: yes; I wrote out the "obvious" method because I expected the OP to have relatively minimal mathematical background (and my apologies if I got that wrong) - a real implementation would want to use better (but harder to explain) methods
Nobody avatar
in flag
@SAIPeregrinus What side channel? Power/time? Yeah, sure, but that's so far away from the question here that I was at first pretty confused by your comment.
jp flag
So, just to make it clear: what makes this scheme insecure is actually *not* the *reduction* in key space, as asked in the question, but the *distribution* of keys. Correct?
poncho avatar
my flag
@JörgWMittag: that is correct; changing the distribution so that all key values possible but some have different probabilities would leak some probabilistic information about the plaintext.
fgrieu avatar
ng flag
For perfect secrecy with these message and keyspace, something close to the original OTP is $C\gets(K-M)\bmod7$ [C = (K+7-M)%7` in C] with decryption by $M\gets(K-C)\bmod7$ [M = (K+7-M)%7` in C]. That has the advantage encryption and decryption are the same, like in the traditional OTP.
Jack avatar
cn flag
I am a little confused with what uniformly random k means when it is said that k = {0000, 0001, 0010, 0011, 0100, 0101, 0110} if it is uniformly random shouldnt this be ok? @poncho
Jack avatar
cn flag
@ChrisPeikert but how would the attacker how that the key is not allowed in the key space specified? i am confused
Chris Peikert avatar
in flag
@Jack We follow Kerckhoff’s principle, and assume that the adversary knows all the algorithms and distributions (of the key and message), but not the chosen key itself. This is actually reflected in the formal definition of perfect secrecy.
Jack avatar
cn flag
@ChrisPeikert How is the example of having 0111 valid? When we say that both k and m is {0000, 0001, 0010, 0011, 0100, 0101, 0110}. you can never have a message 0111
Chris Peikert avatar
in flag
@Jack The real key and message could be 0110 and 0001 (respectively), making the ciphertext 0111. When the eavesdropper sees this ciphertext, it can infer that the message was not 0000. However, before the ciphertext was sent, 0000 was a possible message. Together, this is a violation of perfect secrecy.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.