Re: Recognising one's own messages on an anonymous broadcast channel?

<bergstrom.henrik@xxxxxxxxx> wrote:
On 29 Jan, 13:21, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
We did consider a similar approach - including a random "correlation
id" in the input message which is echoed back in the output message -
but we need to guarantee that no collisions occur between id:s nonces,
etc., not just offering "high probability" of no collisions.

You talked about 10^5 messages per second, or approximately 10^12 ~ 2^40
messages per year. The collision probability for 2^40 128 bit strings is
(very) approximately 2^80/2^128 ~ 2^(-48). If you are unconfortable with
that level, increase the length to 256 bits.

The fact is that we're uncomfortable with all levels of probability
(except probability 1). We would like a *guarantee* that no collisions
can occur. Ever. Even after billions of years.

Does that sound silly or does it just mean that standard "crypto-
algorithms" can't offer a solution to our problem?

It is extraordinary silly. Sorry to say so. (Academics might be allowed
to worry about such things, practical people shouldn't. Unless they have
_very_ good reasons to do so.)

What we are hoping for is that some scheme exists which makes use of
crypto-algorithms and pure cleverness rather than just very advanced
crypto-algorithms. We're also hoping that the fact that the client and
server can cooperate - for example by adding information like "user
id" to the message - will make the problem easier to solve.

Fix an RSA public key, throw away the private key, the client then
encrypts its user id and a counter under that key and use the ciphertext
as a nonce. (This is what David Eather just suggested, contrary to what
I said it does work.)

And I'm sure there are more efficient schemes out there.

But it is all very silly, when you have a _perfect_ solution lying around.

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: [RFC/PATCH] Documentation of kernel messages
    ... Maybe a stupid idea but why do we want to assign these numbers by hand? ... I can imagine it could introduce collisions when merging tons of patches ... But maybe also 4 bytes would be enough, since the hash only has to be ... For 1000 messages the probability is ...
    (Linux-Kernel)
  • Re: Recognising ones own messages on an anonymous broadcast channel?
    ... not just offering "high probability" of no collisions. ... crypto-algorithms and pure cleverness rather than just very advanced ... id" to the message - will make the problem easier to solve. ...
    (sci.crypt)
  • Re: GUID on Linux
    ... > Besides anything deterministic is at least as likely to collide as truly ... collisions due to hardware errors or software bugs will be at least as ... large as the probability of collisions of random numbers. ...
    (comp.os.linux.development.apps)
  • Re: Recognising ones own messages on an anonymous broadcast channel?
    ... not just offering "high probability" of no collisions. ... system would likely still be subject to many types of attack - attacks on ... If each client has a unique ID then there are several clever cryptographic ...
    (sci.crypt)
  • Re: Recognising ones own messages on an anonymous broadcast channel?
    ... not just offering "high probability" of no collisions. ... crypto-algorithms and pure cleverness rather than just very advanced ... id" to the message - will make the problem easier to solve. ...
    (sci.crypt)