0
$\begingroup$

Let's say that Alice wants to communicate some secret value $S$ to Bob through a public channel in a way that other people don't know what the value was.

To do this, Alice publishes that secret value to the public channel, along with $N-1$ other values, making a list $L$ which has $N$ items in it.

Before this communication, Alice and Bob agreed that the value Alice wanted to communicate to Bob would be $L_M$ where $M \in [0,N)$.

How secure is this scheme? What attack vectors could be used on it? Also, does this technique have a name?

Some thoughts of my own:

  • The security of the scheme seems to relate to the size of $N$. Larger $N$ values seem more secure.
  • It seems like if you didn't choose the other values of the list carefully, that it could be seen statistically that "one data point doesn't fit with the others" which could make the actual value cared about stick out more obviously.
  • One idea to make the value fit in completely could be that if the secret value $S$ could be represented in $B$ bits, that maybe the list $L$ could be a random shuffle of all values $[0,2^B)$, but if someone knew that, they could know that the number was probably on the higher side of the values so this may be too naive.
  • Agreeing on $M$ in advance has the usual key generation / key sharing / key storing problems and attack vectors. I'm not interested in that part of the problem.

Thanks for any information or insights!

$\endgroup$
1
$\begingroup$

Short answer: Sorry, no, unfortunately your concept is neither a secure, practical nor efficient crypto scheme.

Slightly longer answer: To illustrate the impractically of your scheme, let's assume you are sending a completely random bit string $S$ of length $B$. In such case, in order to preserve perfect secrecy, you will at least have to send a list $L$ containing all possible values $[0..2^B)$ in random order, except for $S$ which is fixed at position $M$, where $M$ is the secret key you share with the recipient.

Now, if $M$ is selected completely at random from all possible values, it will also be a random element from $[0..2^B)$ and consequently be exactly as long, and contain as much entropy as, the message $S$ you want to sent.

The cipher text $L$ on the other hand, will be exponentially longer than the plain text message $S$. This is bad, because it means that your effort of sending the message securely, will be exactly as great as the effort you want your adversary to suffer trying to brute force guessing the key or the plain text.

Furthermore, if the plain text $S$ is not completely random, securely executing your scheme gets more complicated, but the conclusion doesn't change. If you maximize security, your effort of encoding and sending the plain text will be no less than the effort you want your adversary to suffer trying to break your scheme.

$\endgroup$
  • $\begingroup$ I'm not so sure. Can you speak to this (counter?) example? Let's say that I tell you I'm going to publish a list of 100 numbers and that the number you should care about is at index 58 (first index in list is 0). The actual number that I want to communicate turns out to be 68.5. One possibly list I could publish is a list where the first number is 39.5, and it increases by .5 for each index. 39.5, 40.0, 41.5, ... 68.5, ...89. An attacker could know that the value was between 39.5 and 68.5 and a multiple of .5, but otherwise is a 1 in 100 guess. Larger lists would be less info even. $\endgroup$ – Alan Wolfe Apr 14 '16 at 13:13
  • $\begingroup$ typo. Between 39.5 and 89 is what I meant. $\endgroup$ – Alan Wolfe Apr 14 '16 at 13:24
  • $\begingroup$ If you reveal something by sending a cipher text list $L$ that the attacker didn't already know, your scheme isn't secure. OTOH, if you manage to only reveal as much as the attacker already knows and secrecy is preserved, it would be a lot more efficient, and exactly as secure, to use some form of OTP. And an OTP is already considered impractical. $\endgroup$ – Henrick Hellström Apr 14 '16 at 15:44
-2
$\begingroup$

Reviewing crypto-protocols is in general off-topic here, and there has actually been a lot of discussion about it recently. If the voting keeps its trend, it's likely to become an official closing reason around May.

In general, I believe this answer in Sec.SE is amazingly accurate at explaining why building crypto constructions out of thin air is a bad idea. Recently there was another discussion in the same direction that could be also interesting to check.

The point is: don't reinvent the wheel. There is a lot of concepts that can fit your objective and have been widely tested. My first thought was Diffie-Hellman key exchange, but then I realized that a lot of scenarios can fit, including normal symmetric and asymmetric encryption.

There are things that are immediately apparent in your description, starting by the fact that you need to transfer $N$ items to get one value, and the idea that if they can agree on $M$ securely they could agree on $N$ also using the same channel, but then again: don't try to build with sticks when concrete is an option.

$\endgroup$
  • $\begingroup$ Regarding agreeing on the value instead of the key in advance, it's a good point, but you could imagine something such as either the index was reused for several messages (not the best idea I know), or there was some other scheme to derive the next index from the current (also not the best) or that there was a shared one time pad that specified each index to use in sequence. Just trying to understand the hardness and complexity of "here are N public numbers and only one truly matters.". I'm trying to understand it's weaknesses, not really trying to make something that I'd go out and use. $\endgroup$ – Alan Wolfe Apr 12 '16 at 16:00
  • $\begingroup$ Oh hey BTW, if crypto isn't the place for this, would math or comp sci be better choices do you think? $\endgroup$ – Alan Wolfe Apr 12 '16 at 16:05
  • $\begingroup$ Then you need an objective, security model, a definition that needs to be fulfilled. And then maybe follow the advise of crypto.stackexchange.com/questions/33274/… $\endgroup$ – Sergio Andrés Figueroa Santos Apr 12 '16 at 16:05
  • $\begingroup$ I am in neither of them, but usually the FAQ of each site defines what is on topic there. In general, the idea in StackExchange sites is that the answer can be useful not only to the person who asks, but to people who search for it in the future. Questions about sharing a secret value are welcome in Crypto.SE, but should fit the FAQ. Good luck, and feel free to ask other questions in Crypto.SE! $\endgroup$ – Sergio Andrés Figueroa Santos Apr 12 '16 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.