Score:1

Separate Messages Encryption

re flag

In a public key system, Alice sends Bob separate messages telling him information about the time T and place P they would meet, encrypted with Bob's public key. What is the most secured protocol:

A --> B : {T},{P}

or

A --> B : {T,P}

?

In other words, which one is most secure: sending separate messages with different encryptions, or combinig two messages in one and sending it with one encryption? In which scenario could Eve, the eavesdropper, more likely intercept or tamper with the sent messages?

My answer so far: Combining into one message and encrypting it. I think this way I increase unlinkability between the items/events/messages in question. But I do not have clear idea about what Eve would do in such situations.

Any other idea would be appreciated.

Maarten Bodewes avatar
in flag
Yes, unlinkability comes into play. In the first instance you can combine previously eavesdropped encrypted messages using recombination. Remember though that anybody can encrypt, so if an adversary can guess the message contents, then what happens? Remember: asymmetric encryption is performed using a **public** key. What would you need for message integrity and authenticatoin?
Ali_Habeeb avatar
re flag
@MaartenBodewes For integrity I need a message digest (calculated by a hash function), and for authentication I need a digital signature. But even without those, still Eve cannot decrypt (he does not have Bob's private key). So he has a very little room to play around. Also, he is very unlikely to guess the message content.
Maarten Bodewes avatar
in flag
Confidentiality can be assumed yes, unless things like plaintext or padding oracles or timing attacks can be found. But "have very little room to play around", and "unlikely to guess the message content", well - that's a "citation needed", it really depends on the context and content. Without any additional measures and implementation details, I'd assume confidentiality only, as stated in the given answer. Note that an attacker only has to guess an *acceptable* T and/or P.
Score:1
ng flag

Per the standard definitions of CPA-secure public key encryption, there are exactly the same security assurances for the protocol A --> B : {T},{P} and A --> B : {T,P}. Confidentiality, and nothing else.


Proof: from any CPA-secure public key encryption we build another one as follows:

  • We define the new encryption of a single-bit¹ message $m$ to be the original encryption of a random bit $b$, concatenated with $c:=m\oplus b$. Decryption deciphers $b$, then finds $m=c\oplus b$.
  • We define that the new encryption of a multi-bit message is the concatenation of the new encryption of each message bit. Decryption deciphers individuals bits, and rebuilds the original message.

It's easy to prove that the new encryption scheme decrypts correctly, and is CPA-secure. For this encryption scheme and any messages T and P it holds {T,P} = {T},{P} thus the two methods in the question are indistinguishable, thus equally secure.

In both cases, the data is not authenticated. Adversaries can encrypt any message and substitute the outcome for the original. And it should be assumed that they can manipulate a cryptogram in order to change any portion of the plaintext after decryption, including inserting, reordering, duplicating, flipping a bit, adding a constant.


Note: there are encryption schemes making A --> B : {T},{P} susceptible to attacks that fail for A --> B : {T,P} (like changing what B gets to {T'},{P} with T' a close time, which allows to find {P} in advance of the planned meeting by following B trying to go to the meeting place too early). My point is that the problem statement does not allow to conclude that the encryption system used is one of these non-malleable cryptosystems.


¹ change bit to byte if the cryptosystem only allows messages with size multiple of 8 bits.

Ali_Habeeb avatar
re flag
Thanks for the details, though I did not understand it all. Last paragraph answers my question.
fgrieu avatar
ng flag
@Ali_Habeeb : another way to say it is that `A --> B : {T},{P}` _is_ vulnerable to the attack I describe which allows Eve to find the meeting place `P`, when `A --> B : {T,P}` _may be_.
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.