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 > [email protected] > https://lists.gnu.org/mailman/listinfo/gnunet-developers
0x48426C7E.asc
Description: application/pgp-keys
_______________________________________________ GNUnet-developers mailing list [email protected] https://lists.gnu.org/mailman/listinfo/gnunet-developers
