View Issue Details
ID  Project  Category  View Status  Date Submitted  Last Update 

0002564  GNUnet  filesharing service  public  20120927 20:16  20131224 20:54 
Reporter  Christian Grothoff  Assigned To  Christian Grothoff  
Priority  urgent  Severity  feature  Reproducibility  N/A 
Status  closed  Resolution  fixed  
Product Version  SVN HEAD  
Target Version  0.10.0  Fixed in Version  0.10.0  
Summary  0002564: Implement new NS search based on suggestion from Kenneth Almquist  
Description  Kenneth wrote: 1. The Issue In GNUNET, keywords are passed through a oneway 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 oneway 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 Kblocks. Our proposal, in a nutshell, is to make a Kblocks use a <namespace, keyword> pair, rather than just a keyword, as the search key. KSblocks, 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 Kblocks Each Kblock 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 q1, generated by hashing a combination of the public key of the namespace and the keyword. The private key used to sign the Kblock is x+h mod q. This prevents a Kblock 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 Kblocks 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 Kblock A Kblock 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 Kblock. 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 Kblocks. 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 q1, 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 nonzero 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 nonzero 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 nonzero will be T * (q/(q1)). 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/(q1)). For a realistic value of q, the difference between 1 and (q/(q1)) 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 * ((q1)/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 Kblocks Constructing a digital signature using DSA requires chosing a value of k in the range 1 through q1. We want to chose k using a deterministic fashion so that if the same Kblock 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 Kblock 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.  
Tags  No tags attached.  
has duplicate  0002854  closed  Christian Grothoff  ECC signing error at publishing 
related to  0002566  closed  Christian Grothoff  need abstractions for DH crypto in util 

I think this part is going to be problematic to implement: >> 2.7. Generating a value of k for signing Kblocks Constructing a digital signature using DSA requires chosing a value of k in the range 1 through q1. We want to chose k using a deterministic fashion so that if the same Kblock 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: << The current libgcrypt API doesn't allow us to specify a value k for DSA signatures, so we need to either hope WK expands the API for us or reimplement DSA ourselves. 

I think this might be problematic: >>> 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 Kblock 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. <<< This means that 'k' can be predicted (by hashing) from the encrypted payload; however, DSA is not secure if the nonce is even just partially known (see "The Insecurity of the Digital Signature Algorithm with Partially Known Nonces" by Nguyen and Shparlinski. Journal of Cryptology, New York. Vol 15, nr 3 (2003)). Now, this is for Kblocks where the private key x=0, so it might not matter much; I still think it would be safer to generate the nonce from the hash of the plaintext, as an attacker would then not be able to get the nonce. So the choice is not quite "arbitrary". 

SVN 26326 includes a first patch, changing all of the APIs as needed (and keeping things mostly working). 2 FS tests fail and the crypto is not yet implemented (just a stub). 

SVN 26349 implements most of the new crypto, except the parts that need changes to libgcrypt. FS tests now pass (with 'fake' crypto). 

Only thing missing now is 2.7, as libgcrypt doesn't support deterministic ECDSA yet. 

WK says det. ECDSA will be ready end of July. 

This is working. 

Note that the crypto changed a tiny bit (multiplication instead of addition for key derivation), based on discussions with DJB. Will be documented. 
Date Modified  Username  Field  Change 

20120927 20:16  Christian Grothoff  New Issue  
20120927 20:17  Christian Grothoff  Status  new => confirmed 
20120927 20:22  Christian Grothoff  Relationship added  related to 0002566 
20120927 20:32  Christian Grothoff  Target Version  => 0.10.0 
20120929 21:24  Christian Grothoff  Priority  normal => high 
20121007 14:20  Christian Grothoff  Assigned To  => Christian Grothoff 
20121007 14:20  Christian Grothoff  Status  confirmed => assigned 
20121110 14:09  Christian Grothoff  Priority  high => normal 
20121221 20:31  Christian Grothoff  Priority  normal => urgent 
20130304 04:46  Christian Grothoff  Note Added: 0006915  
20130304 05:07  Christian Grothoff  Note Added: 0006916  
20130305 17:15  Christian Grothoff  Note Added: 0006941  
20130307 13:46  Christian Grothoff  Note Added: 0006948  
20130404 09:48  Christian Grothoff  Relationship added  has duplicate 0002854 
20130416 13:39  Christian Grothoff  Note Added: 0007053  
20130627 16:13  Christian Grothoff  Note Added: 0007194  
20130812 21:17  Christian Grothoff  Note Added: 0007358  
20130812 21:18  Christian Grothoff  Note Added: 0007359  
20130812 21:18  Christian Grothoff  Status  assigned => resolved 
20130812 21:18  Christian Grothoff  Fixed in Version  => 0.10.0 
20130812 21:18  Christian Grothoff  Resolution  open => fixed 
20131224 20:54  Christian Grothoff  Status  resolved => closed 