gnunet-developers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [GNUnet-developers] Keyword queries shouldn't reveal the namespace


From: Christian Grothoff
Subject: Re: [GNUnet-developers] Keyword queries shouldn't reveal the namespace
Date: Mon, 25 Jun 2012 10:24:38 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.4) Gecko/20120510 Icedove/10.0.4

Pardon my short reply, but after reading your proposal carefully I have
very few comments:

1) I really, really like it, this would be a great improvement
   (and I fully agree with all of your motivations).
2) I don't think your 'proof' of the DSA0/DSA1 equivalence is sufficient
   as-is, but nevertheless I agree with your conclusion and that
   allowing 0 would seem to be harmless in this case; I might need to
   double-check the math one more time, but for now I found nothing that
   would contradict this.
3) This obviously would break backwards-compatibility on various levels,
   starting with pseudonyms (which currently use RSA).  The implications
   of switching from RSA to DSA here really imply a larger break.
4) Implementing this will be non-trivial, so while I'm happy to support
   this as a goal, I'm doubtful that this can be done overnight. ;-)

Naturally, it is great to have a design first (and I'm particularly
curious to see what Heikki might think about this).  Are you planning on
helping with the implementation of this?


Happy hacking!

Christian


On 06/25/2012 04:35 AM, Kenneth Almquist wrote:
> 
> 1.  The Issue
> 
> In GNUNET, keywords are passed through a one-way function before being
> published or queried.  However, the namespace is published and included
> in all queries.  There are several reasons why this is undesirable.
> 
> First, namespaces, like keywords, may be targets for censorship.  In
> fact, the contents of a namespace are likely to represent a particular
> viewpoint.  This should make them a particularly attractive target for
> censorship by Western governements, which generally want to censor
> particular types of materials in a way that doesn't restrict the
> distribuation of other types of materials that are not targets for
> censorship.  GNUNET uses a one-way function to hide the keywords in
> queries.  It should hide the namespace as well, for the same reasons.
> 
> Second, the content of a GNUNET query can be determined by guessing.
> The current design makes this type of attack unnecessarily easy by
> revealing the namespace, meaning that the attacker only has to guess
> the keyword, rather than being forced to guess a pair of values consisting
> of a namespace and a keyword.
> 
> Third, specifying the namespace in a query (rather than making all queries
> look alike to any attaker which fails to guess the query) might make
> attacks based on traffic analysis easier.
> 
> Fourth, the current design treats queries of the global namespace
> differently that queries of other namespaces.  This means that GNUNET
> has to support two types of keyword searches, which makes the system
> more complex at a conceptual level, and may make the code more complex
> as well.  Consider, for example, that GNUNET currently guarantees that
> if a response to a query in the global namespace contains a valid
> signature, then the response was generated by someone who knew the
> keyword.  However, if the query was for a namespace other than the
> global namespace, then there is no such guarantee.  Having a single
> keyword search mechanism that applied to all namespaces would eliminate
> this sort of discrepancy, making the security properties of GNUNET
> simpler and easier to understand and reason about.
> 
> 
> 2.  Our Proposal
> 
> In the current design of GNUNET, searches in the global namespace use
> K-blocks.  Our proposal, in a nutshell, is to make a K-blocks use a
> <namespace, keyword> pair, rather than just a keyword, as the search
> key.  KS-blocks, currently use for searches of a keyword in namespaces
> other than the global namespace, go away.
> 
> The remainder of this section explains the technical details of how this
> works.
> 
> 2.1.  DSA
> 
> Our design uses DSA to generate digital signatures.  To use DSA, it is
> necessary to select three parameters:  p, q, and g.  A single set of
> parameters should be chosen for use by all GNUNET participants.
> 
> Private keys in DSA are integers in the range 1 thought q - 1.  To simplify
> the exposition, we will assume for now that DSA also allows 0 to be used
> as a private key.  We will revisit this assumption in section 2.6.
> 
> If x is a private key, the corresponding public key is g^x mod p.
> 
> 2.2.  Namespaces
> 
> As with the current GNUNET design, a public/private key pair define a
> namespace.
> 
> One namespace is designated as the global namespace, and its private
> key is made public so that anyone can publish to the global namspace.
> Any namespace could be used as the global namespace, but for aesthetic
> reasons I would chose 0 as the private key for the global namespace.
> 
> 2.3.  Generating the Signature Key for K-blocks
> 
> Each K-block is signed by a key which is derived from the namespace and
> the keyword.  Let x be the private key of the namespace.  Let h be a
> value, in the range 0 through q-1, generated by hashing a combination of
> the public key of the namespace and the keyword.  The private key used
> to sign the K-block is x+h mod q.
> 
> This prevents a K-block from being forged by anyone who doesn't know
> both the namespace private key and the keyword, because without knowing
> these it is impossible to generate a valid signature.
> 
> We will discuss the details of signing in sections 2.6 thorough 2.8, but
> first we consider query generation.
> 
> 2.4.  Generating Queries
> 
> To perform a query, it is necessary to know the public key which
> corresponds to the private key used to sign the K-blocks being
> searched for.  The private key is x+h mod q, so the public key is:
> 
>         g^(x+h mod q) mod p
> 
> To compute the this without knowing the value of x (which is the
> private key of the namespace), we proceed as follows.  DSA requires
> the parameters be chosen such that
> 
>         g^q mod p = 1
> 
> so
> 
>         g^(x+h mod q) mod p = g^(x+h) mod p
> 
> Standard algebra tells us that
> 
>         g^(x+h) mod p = (g^x * g^h) mod p
>                       = ((g^x mod p) * g^h) mod p
> 
> g^x mod p is the namespace public key, and h is a hash of the namespace
> public key and the keyword.  Therefore, a query can be generated by
> anyone who knows both the namespace public key and the keyword.
> 
> 2.5.  Contents of a K-block
> 
> A K-block contains the following values, which are essentially the
> same as in the existing design:
> 
> 1)  The payload (typically a URI followed by metadata).  This is the
> data returned by search that matches the K-block.  The payload is
> encrypted using a symmetric encryption key generated from a hash of
> the namespace public key and the search keyword.  This means that only
> someone who knows the search criteria (namespace and keyword) can decode
> the payload.
> 
> 2)  The public key used to sign the payload.  Since this key is derived
> from the namespace and the keyword, it (or a hash of it) can be used
> as the search key.
> 
> 3)  A digital signature of the encrypted payload using the public key
> listed above.  A valid signature can only be generated by someone who
> knows both the private key of the namespace being searched and the
> keyword being searched for, so the signature can be checked to filter
> out bogus K-blocks.
> 
> 2.6.  Zero as a Private Key
> 
> As noted in section 2.1, the DSA specification does not permit a private
> key of zero.  There are two ways we can deal with this.  One is to modify
> the procedures described in sections 2.3 and 2.4 to avoid a private key
> of zero.  If the sum x+h mod q turns out to be zero, rather than using zero
> as the private key, we hash a combination of the namespace public key and
> the keyword to produce a value in the range 1 through q-1, and use that
> value as the private key.  In section 2.4, we don't compute the private
> key, so rather than comparing the private key to 0, we compare the public
> key to the public key which corresponds to a private key of zero.
> 
> Although the approach described in the preceding paragraph would work,
> it appears unnecessary.  The requirement that the private key be
> non-zero doesn't appear to be necessary for correctness, because a
> look through the proof of correctness for DSA reveals no steps that
> depend upon the assumption that the private key is nonzero.  Nor is
> the requirement that the private key be non-zero necessary for security,
> because the difference in security between DSA variants with or without
> the requirement that the private key is nonzero can be proved to be
> trivial.
> 
> We now present the proof referred to in the preceding sentence.  In
> what follows, we will use the name DSA1 to refer to the standard DSA
> algorithm, where the minimum value for the private key is 1, and DSA0
> to refer to a variant where then minimum value of the private key is
> zero rather than one.
> 
> Suppose that we have an algorithm that will break DSA0 in an expected
> time T, assuming that the private key is randomly selected with a uniform
> distribution.  This algorithm will also break DSA1.  To determine maximum
> run time for this algorithm when used to break DSA1, we assume that the
> run time of the algorithm is zero when used to break an instance of DSA0
> where the private key happens to be zero.  It then follows that the
> expected run time if the private key is non-zero will be T * (q/(q-1)).
> Since the actual run time for a zero key must be greater than zero, the
> actual time to break DSA1 must be less than T * (q/(q-1)).  For a
> realistic value of q, the difference between 1 and (q/(q-1)) is trivial.
> 
> Conversely, suppose that we have an algorithm that will break DSA1 in
> an expected time T.  We can break DSA0 by first checking whether the
> public key is 1 (which corresponds to a private key of 0), and then
> running the algorithm to break DSA1 if the check fails.  The expected
> run time will be C + T * ((q-1)/q), where C is the time required to
> compare the public key with 1.  Assuming that DSA has any meaningful
> resistance to attack, the value of C will be trivial compared to the
> value of T.
> 
> In short, the security of DSA0 and DSA1 are essentially identical, so
> there is no reason not to use DSA0.
> 
> 2.7.  Generating a value of k for signing K-blocks
> 
> Constructing a digital signature using DSA requires chosing a value of k
> in the range 1 through q-1.  We want to chose k using a deterministic
> fashion so that if the same K-block is published more than once, the
> signature won't change.  In addtion, we want to be sure that we don't
> chose k in a way that will help an attacker.  To generate k, we compute
> a cryptographic hash of the private key combined with the data being
> signed.  This ensures that:
> 
> 1)  At attacker who does not know the private key cannot determine the
>     value of k.
> 
> 2)  The probability of using the same value of k for two different
>     signatures, if either the signing key or the data being signed is
>     different, is the same as if k were chosen using a true random
>     number generator.
> 
> 3)  Repeatedly signing a given value with a given key will always use
>     the same value of k, thereby producing the same signature.
> 
> The data being signed (the payload) is encrypted.  We could use the
> unencrypted payload rather than the encrypted payload as input to
> the hash function.  It doesn't matter which we use if the hash function
> is secure.  If the hash function is not secure, using the unencrypted
> payload won't really help because anyone who received the K-block as
> a query result will be able to decrypt the payload.  So we specify that
> the encrypted payload is to be used as input to the hash function, but
> that choice is arbitrary.
> 
> 2.8.  Avoiding Collisions
> 
> In section 2.3, we specify that h is based on a hash of the namespace
> public key and the keyword.  In this section, we explain why it is
> necessary to include the namespace public key in the input to the hash.
> 
> Suppose that the only input to the hash was the keyword.  Then if we
> had two keywords K1 and K2, we would have corresponding hash values
> h1 and h2 which would be independent of the namespace involved in
> the query.
> 
> Suppose further that we have a namespace N1 for which we know the
> private key x1.  The private key associated with a search for K1 in
> namespace N1 is then (x1 + h1) mod q.  We can then define a new namespace
> N2 with a private key x2 = (x1 + h1 - h2) mod q.  The private key associated
> with a search for K2 in namespace N2 will then be
>     (x2 + h2) mod q = (x1 + h1 - h2 + h2) mod q = (x1 + h1) mod q
> In other words, we have produced a collision where the searches <N1, K1>
> and <N2, K2> both produce the same search key.  Including the namespace
> public key as an input to the hash prevents this attack.
> 
> 
> 3.  Conclusion
> 
> The design in section 2 shows that it is technically feasible to hide
> the namespace as well as the keyword in GNUNET queries.  That design
> used DSA, because it has a long track record, but it should be possible
> to substitute a different ElGamel variant if desired.
> 
> One of the stated goals of GNUNET is to provide deniability.  Hiding
> the namespace in queries would improve the ability of GNUNET to meet
> that goal.
> 
>                                         
> _______________________________________________
> GNUnet-developers mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/gnunet-developers

Attachment: 0x48426C7E.asc
Description: application/pgp-keys


reply via email to

[Prev in Thread] Current Thread [Next in Thread]