[tor-dev] GSoC: Tor Messenger CONIKS integration
ml at tnull.de
Sat Mar 12 09:54:27 UTC 2016
On 11 Mar 2016, at 2:55, Marcela Melara wrote:
> Hi Elias,
>> On Mar 9, 2016, at 5:31 AM, Elias Rohrer <ml at tnull.de> wrote:
>> Hello Marcela!
>> Nice to meet you, too, and thank you for that interesting Paper!
>> It seems I made a lot of wrong assumptions in my last mail, ugh,
>> thats kind of embarrassing..
> I really appreciate your interest in our paper and CONIKS, thanks :)
> No worries, there are a lot of subtle aspects about CONIKS, so it can
> take some time to fully see and understand them.
>>> Yes, we propose that the identity providers can act as auditors and
>>> cross-verify each other in this way, and clients may query any
>>> auditor when they are checking for equivocation. However, I should
>>> note that we intended this to be the *ideal deployment* (and I
>>> apologize if this doesn’t come through clearly enough in the
>>> paper). CONIKS also allows third-party auditors whose sole job it is
>>> to check that the chain of signed tree roots is linear. In practice,
>>> we expect that auditors and identity providers will be separate in
>>> most cases (at least until there is a standard for CONIKS protocols
>>> and data formats, but we’re not there yet).
>>> It’s not accurate to conflate auditing with being a key server, or
>>> say that auditing is a subset of the key server’s functionality.
>>> Auditors only need to keep records of identity providers’ signed
>>> tree roots, and they never download or record any key directory
>>> contents, so it doesn’t really make sense to equip auditors with
>>> key server functionality and “turn it off” when you’re not
>>> acting as a key server. Key servers have the more complex and rich
>>> functionality needing to maintain significantly larger data
>>> structures and perform more cryptographic computations. This means
>>> that key servers have very different space and availability
>>> requirements than auditors do.
>> Ah, yes, that is true. Just turning of features of the server to get
>> an auditor might indeed be a bad idea. But wouldn't there be a lot of
>> overlapping functionality in the server, auditor and even the
>> clients? E.g. the crypto primitives for building and checking the
>> tree? Maybe it would be viable to create a libCONIKS which could be
>> used by all three components?
> So it might seem at first glance that there’s a lot of overlapping
> functionality between the server, auditor and clients, but once you
> start implementing each one, it’s not really the case. Think about
> the different tasks of each component: the server is generating a
> bunch of digital signatures (e.g. signed tree roots, lookup indices)
> and hashes (Merkle tree, lookup indices, signed tree roots) to build
> the Merkle trees and hash chain of signed tree roots. Clients, on the
> other hand, do a bunch of signature and hash verifications (which, yes
> to be fair requires hashing data as well, but for different reasons)
> to verify individual authentication paths and signed tree roots. So
> there’s really no overlap in functionality with the server.
> Similarly, the auditors need to verify the signed tree roots so
> there’s some signature and hash verification as well, but in a
> different way than clients need to do this.
> While generation and verification of these various crypto primitives
> go hand in hand, I would caution against putting them all in a single
> library if different components of the system will need different
> portions. If you look at the reference implementation, the only common
> code is the definition of the data formats. When I first started
> writing the reference implementation, I actually thought that it would
> be useful (and possible) to build a single libCONIKS, but sharing
> underlying crypto primitives isn’t reason enough to put all of the
> functionality in one place since the application of those primitives
> is what really matters. So I really think it makes more sense to make
> separate modules for server, client and auditor.
>>>> On Page 4 the authors state:
>>>> "We can implement a VUF using any deterministic, existentially
>>>> unforgeable signature scheme . The signature scheme must be
>>>> deterministic or else (in our application) the identity provider
>>>> could insert multiple bindings for a user at different locations
>>>> each with a valid authentication path. In practice, this could be a
>>>> classic RSA signature  (using a deterministic padding scheme
>>>> such as PKCS v. 1.5 ) or BLS “short signatures” , which
>>>> provide the best space efficiency. Many common discrete-log based
>>>> signature schemes such as DSA  are not immediately applicable
>>>> as they require a random nonce.
>>>> In CONIKS, we generate the index for a user u as: i = h (sign_K
>>>> where h() is a one-way hash function and sign() is a deterministic,
>>>> existentially unforgeable signature scheme. The extra hash function
>>>> is added because some bits of sign_K (u) might otherwise leak
>>>> through binding validity proofs, and signature schemes are
>>>> generally not unforgeable given some bits of the valid signature.
>>>> The hash function prevents this by ensuring the final lookup index
>>>> leaks no information about the value of sign_K (u).”
>>>> I understand that using the signature of the user identity ensures
>>>> that no information indicating its existence on the server is
>>>> leaked. But why are they hashing the signature again?
>>>> RSA-signatures normally already consist of a signed hash-value. Why
>>>> would it bad to leak bits of the signature?
>>> The answer to this question is in the portion of the paper you
>>> quote: "signature schemes are generally not unforgeable given some
>>> bits of the valid signature.” There’s some crypto-jargon here,
>>> which you may not be familiar with if you haven't taken a crypto
>>> course. What this sentence is trying to say is that, given some bits
>>> of a valid signature, an adversary could be able to find some
>>> message or data and a corresponding digital signature which is valid
>>> and which has not been generated by the legitimate signer (in this
>>> case the identity provider). This is called an existential forgery,
>>> and it means that an adversary can create forged lookup indices if
>>> the signature isn’t hashed. The hash on top of the signature also
>>> ensures that the lookup index can’t be easily computed from the
>> I actually had a crypto course some time ago, so crypto jargon should
>> be fine.. However it seems that part of my brain needs some more
>> training to get reactivated ;)
>> I want to get this into my brain so here are some more (probably
>> pretty naive) questions and thoughts on the topic:
>> - When bits of a valid signature leak, an external attacker could
>> forge a colliding index for a different user? This would allow an
>> attacker to register the same public key to a different username they
>> control? So therefore a hash is used?
> So the problem with leaked bits isn’t about an attacker forging an
> index. The problem is actually about privacy. Let’s go back and
> think about why the server transforms usernames into these lookup
> indices. The main purpose is so that the proofs of inclusion (i.e. the
> Merkle authentication paths) for one user don’t leak information
> about *any other* users in the tree. So if I receive the proof of
> inclusion for Alice, I should not be able to figure out who else might
> be in the tree. Remember that the proof of inclusion gives us the
> prefix of Alice’s lookup index, so in other words, we want to make
> sure that an attacker can’t find a name that results in an index
> with a shared prefix with Alice since this would be a privacy
> violation. If you use just a hash function, an attacker can reasonably
> hash a large set of usernames until it finds one that shares its
> prefix with Alice's index and determine whether this user exists by
> querying the server for the corresponding key.
> Using only the digital signature doesn’t solve this problem since
> there are attacks that allow you to recover the rest of the signature
> bits given some of the first bits (I don’t know which specific
> attacks do this, this is the explanation I received from my
> collaborator). So given Alice’s index prefix, an attacker could try
> to guess if the index for a specific user (e.g. Bob) shares the same
> prefix, recover the remaining bits of the signature, and verify —
> using the provider's index public verification key -- whether this is
> a valid signature for Bob’s name. This is also a privacy violation.
> So by hashing the signature, anyone who receives the authentication
> path for Alice cannot determine based on this path, which other
> usernames exist in the tree since this would require finding the
> signatures whose hash shares a prefix with Alice’s index, a much
> more difficult problem.
Ok, thanks for your elaborations! I think I understand the problem and
how you solved it now. I'm still a bit curious though, which specific
forgery attacks would be able to recover the signature. ;)
>> - What still confuses me: When I recall correctly, 'existential
>> forgery' is the lowest level of forgery since the attacker may not
>> have control over the contents of the signed message, but may forge a
>> valid signature for that message.
>> You propose to use a existentially unforgeable signature scheme for
>> your VUF. But:
>> - As you explicitly use an existentially unforgeable signature
>> scheme, why can the index then be forged if bits of this
>> (existentially unforgeable) signature are leaked to an attacker? Is
>> the hash needed when an external attacker has no knowledge of the
>> private key used to sign the index?
>> - You later propose RSA for the VUF, but isn't RSA *the* example for
>> which existential forgery can be done?
> We realized the potential dangers of using RSA, so we designed a
> different VUF scheme. I think it’s best if you read the new paper to
> see the description.
>> - So am I right to assume that the attacker model shifts from an
>> external one to a malicious identity provider? As he knows his
>> private key, the signed data and the signature, what is the hash
>> function hiding here?
> See my explanation of the VUF above. CONIKS tries to protect against
> external *and* internal attackers. As I explained above, the hash
> function in the private lookup index is used to protect users’
> privacy from external attackers. Like you said, the key server knows
> can know who all has name-to-key mappings in its own key directory.
> CONIKS deals with the internal attackers (i.e. malicious or
> compromised key server) using the tamper-evident data structure and
> signed tree roots to leave evidence of fake keys and equivocation.
>>>> Also, if I see this correctly, they don't do it in their reference
>>>> instead they just use SHA256withRSA...
>>>> So, am I misreading the paper? Or do they actually mean
>>>> sign_K(h(u)), which would be the normal 'hash and sign' operation
>>>> of RSA? Or does it make sense to rehash the signature and their own
>>>> implementation is not consistent with it?
>>>> This is probably no important point, however I want to make sure
>>>> I'm not missing a piece concerning the security of the user
>>> Unfortunately, the reference implementation is still a work in
>>> progress (although I’ve had to take some time off from working on
>>> it due to other research projects), and is missing several features
>>> described in the paper. The SignatureOps class in the reference
>>> implementation simply implements wrappers around Java signature
>>> functions, so that’s not where the user lookup index calculation
>>> happens. The lookup index calculation happens in the unameToIndex()
>>> function in conks_server.ServerUtils. Now, I will note that the
>>> reference implementation currently *isn’t* doing the proper index
>>> calculation as it only currently hashes the username, so thank you
>>> for making me go back and double-check my code! But it would be
>>> relative straight-forward to change this and to add the digital
>>> signature computation that needs to be done before the hashing.
>> Ok, good to know that, I'll keep it in mind when reading the
>> reference code! However, this is embarrassing, I only had a glance an
>> the reference implementation, sorry for linking to an unrelated spot
>> in the code and making assumptions...
>> I think my next steps will be to read the peer-reviewed version of
>> your Paper and to refresh my crypto-knowledge a bit. I'd appreciate
>> if you had some pointers to resources relevant to this project for me
>> (other than classic textbooks). I may even try to have a look at the
>> Micali/Rabin paper on VRFs.
> As for good pointers for this project, I’m not sure that the
> Micali/Rabin paper on VRFs specifically is really going to be all that
> helpful for implementing CONIKS because the paper describes VRFs at a
> level of detail that isn’t needed to understand why it may be better
> to use an EC-based VUF construction than RSA. I apologize about the
> confusion arising from the older version of our paper
> If you’re interested in the very formal crypto details of VRFs, you
> should read the paper, but for this project it’s more important to
> understand the security and privacy problems that CONIKS tries to
> solve and how it achieves those goals, and to understand how CONIKS
> fits into the workflow of the existing Tor Messenger service.
> Hopefully, our Usenix paper will explain most of the security and
> privacy design decisions, but definitely feel free to ask more
> questions! Another good resource might be to read about equivocation
> and fork consistency (David Mazieres’ paper on SUNDR first
> introduced this concept), and certificate transparency (there’s a
> good ACM Queue article) for more background on the problems CONIKS
> tries to solve and the design decisions we made. Goldberg et al’s
> paper on preventing DNS zone enumeration is a fairly recent paper that
> also shows how to use VUFs to prevent enumeration of sensitive
> information, so that might be another good resource. For figuring out
> how CONIKS can be integrated into Tor Messenger, I would look at the
> portions of the Tor Messenger code that currently handle encryption
> keys (e.g. key generation, registration, key lookups), and come up
> with a plan of how CONIKS will affect the existing workflow.
> I hope this helps!
Yes, thank you, your elaborations helped me very much! I'll send in my
proposal for this project on Monday and will have a look at the
promising resources you gave me over the next few weeks.
> tor-dev mailing list
> tor-dev at lists.torproject.org
More information about the tor-dev