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

On 29 Jan 2007 05:07:12 -0800, 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.
1000 billion years is 10^12 years. At 10^12 messages per year that is
10^24 messages in total, about 2^80 messages. Collision probability
for 2^80 256 bit strings is about 2^160/2^256 ~ 2^(-96) after 100
billion years. That is probably secure enough. With 512 bit strings
you get 2^(-352) collisions. You cannot get to zero probability, but
the numbers you can reach are less than one collision for the probable
remaining life of planet earth (about another 5 billion years before
the Sun turns into a red giant).

rossum


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

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.

.

Relevant Pages

  • 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: [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: 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 ... Fix an RSA public key, throw away the private key, the client then ...
    (sci.crypt)