View Issue Details

Jump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0002564GNUnetfile-sharing servicepublic2012-09-27 20:162013-12-24 20:54
ReporterChristian Grothoff Assigned ToChristian Grothoff  
PriorityurgentSeverityfeatureReproducibilityN/A
Status closedResolutionfixed 
Product VersionGit master 
Target Version0.10.0Fixed in Version0.10.0 
Summary0002564: Implement new NS search based on suggestion from Kenneth Almquist
DescriptionKenneth 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.

TagsNo tags attached.

Relationships

has duplicate 0002854 closedChristian Grothoff ECC signing error at publishing 
related to 0002566 closedChristian Grothoff need abstractions for DH crypto in util 

Activities

Christian Grothoff

2013-03-04 04:46

manager   ~0006915

I think this part is going to be problematic to implement:
>>
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:
<<
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 re-implement DSA ourselves.

Christian Grothoff

2013-03-04 05:07

manager   ~0006916

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 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.
<<<
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 K-blocks 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".

Christian Grothoff

2013-03-05 17:15

manager   ~0006941

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).

Christian Grothoff

2013-03-07 13:46

manager   ~0006948

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

Christian Grothoff

2013-04-16 13:39

manager   ~0007053

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

Christian Grothoff

2013-06-27 16:13

manager   ~0007194

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

Christian Grothoff

2013-08-12 21:17

manager   ~0007358

This is working.

Christian Grothoff

2013-08-12 21:18

manager   ~0007359

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

Issue History

Date Modified Username Field Change
2012-09-27 20:16 Christian Grothoff New Issue
2012-09-27 20:17 Christian Grothoff Status new => confirmed
2012-09-27 20:22 Christian Grothoff Relationship added related to 0002566
2012-09-27 20:32 Christian Grothoff Target Version => 0.10.0
2012-09-29 21:24 Christian Grothoff Priority normal => high
2012-10-07 14:20 Christian Grothoff Assigned To => Christian Grothoff
2012-10-07 14:20 Christian Grothoff Status confirmed => assigned
2012-11-10 14:09 Christian Grothoff Priority high => normal
2012-12-21 20:31 Christian Grothoff Priority normal => urgent
2013-03-04 04:46 Christian Grothoff Note Added: 0006915
2013-03-04 05:07 Christian Grothoff Note Added: 0006916
2013-03-05 17:15 Christian Grothoff Note Added: 0006941
2013-03-07 13:46 Christian Grothoff Note Added: 0006948
2013-04-04 09:48 Christian Grothoff Relationship added has duplicate 0002854
2013-04-16 13:39 Christian Grothoff Note Added: 0007053
2013-06-27 16:13 Christian Grothoff Note Added: 0007194
2013-08-12 21:17 Christian Grothoff Note Added: 0007358
2013-08-12 21:18 Christian Grothoff Note Added: 0007359
2013-08-12 21:18 Christian Grothoff Status assigned => resolved
2013-08-12 21:18 Christian Grothoff Fixed in Version => 0.10.0
2013-08-12 21:18 Christian Grothoff Resolution open => fixed
2013-12-24 20:54 Christian Grothoff Status resolved => closed