Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Temporary Bindings implementation #13

Closed
vqhuy opened this issue Jun 29, 2016 · 10 comments
Closed

Temporary Bindings implementation #13

vqhuy opened this issue Jun 29, 2016 · 10 comments
Assignees
Labels

Comments

@vqhuy
Copy link
Member

vqhuy commented Jun 29, 2016

@masomel said:

I'm thinking it might be better to have a separate TB struct, because the server needs to keep track of all temporary bindings issued during a given epoch, and return a TB whenever a client makes a lookup for a name which may not be in the tree yet but which has been registered/changed.
I think the functionality of keeping track can probably be implemented in the server itself, but I think it would facilitate handling TBs if they had their own struct.

This issues would be a part of #3

@vqhuy vqhuy self-assigned this Jun 29, 2016
@masomel masomel added the tbs label Jun 29, 2016
@arlolra arlolra mentioned this issue Jun 30, 2016
@masomel
Copy link
Member

masomel commented Jul 8, 2016

I asked Joe about the change counter in the TB had mentioned to me before as an approach to support multiple changes in a single epoch, but it seems they discarded this idea because of its complexity (the idea was to have a Merkle tree per user leaf node to store all the changes ever made to that node).

A long time ago, we considered including a hash chain recording all changes made to a name-to-key mapping. We could imagine using a hash chain to record all changes made between two epochs and combine this with a change counter that needs to be included in the TB's as well. Thoughts? @c633 @arlolra @liamsi

@liamsi
Copy link
Member

liamsi commented Jul 8, 2016

We could imagine using a hash chain to record all changes made between two epochs and combine this with a change counter that needs to be included in the TB's as well.

I'm not sure I understood the approach correctly: Would this be another hash chain (one specifically and only for the temporary bindings)?
And do we in fact we already know/estimate how much we need to worry about too many temporary bindings in between epochs? If yes, wouldn't it be much simpler to adjust the epoch period according to this knowledge (I remember this had some drawbacks although I can't remember which exactly; also it might not scale if the number of TBs gets larger than our estimate)?

@masomel
Copy link
Member

masomel commented Jul 13, 2016

We could imagine using a hash chain to record all changes made between two epochs and combine this with a change counter that needs to be included in the TB's as well.

I'm not sure I understood the approach correctly: Would this be another hash chain (one specifically and only for the temporary bindings)?

Sorry, let me expand on this. The issue we're worried about is that a user may change their keys more than once (e.g. by re-installing the app), or install the app on multiple devices, in a single epoch, generating multiple temporary bindings. The hash chain would be per user allowing us to order all registrations/changes (i.e. TBs) for each user linearly.

And do we in fact we already know/estimate how much we need to worry about too many temporary bindings in between epochs?

At the time of writing our paper, one of our contacts in industry mentioned that they had seen about 1% of users changing their keys each day (mostly via app re-installs). They said this actually would probably pose a non-negligible overhead on their system if they had CONIKS (unfortunately, we don't have numbers for the size of their user base) .

For us, maybe it's fine to impose a "single change per epoch" restriction for now, making epoch's a shorter in exchange.

wouldn't it be much simpler to adjust the epoch period according to this knowledge (I remember this had some drawbacks although I can't remember which exactly; also it might not scale if the number of TBs gets larger than our estimate)?

Yeah, the main issue with making the epoch period shorter is that you're going to be reconstructing (and rehashing) your tree more frequently, which probably won't scale for a very large tree. OTOH, making the epoch period longer saves time on tree reconstruction, but leaves a larger window open in which the server doesn't include new updates in the signed tree roots, which leaves a window for attack.

@vqhuy
Copy link
Member Author

vqhuy commented Jul 14, 2016

Maybe this question is out of scope, but as I understand, there is no auditor module for TBs, right?

@masomel
Copy link
Member

masomel commented Jul 14, 2016

Maybe this question is out of scope, but as I understand, there is no auditor module for TBs, right?

I don't think it's out of scope. Yes, you're right. We don't have have auditors for TBs. Joe's original proposal with TB counters did require TB auditors, but since we're not going that route, we still shouldn't need one.

@vqhuy
Copy link
Member Author

vqhuy commented Jul 15, 2016

Even if the server allows only one registration/change per epoch, how does Bob know that Alice's key returned by the TB is not spurious, without an auditor?

@masomel
Copy link
Member

masomel commented Jul 15, 2016

This is a good question. You're right that Bob can't know if the TB is spurious when he first receives it. If we wanted to avoid this situation we could have auditors for TBs and STRs. The only issue with having auditors also handle TBs is that CONIKS now loses a big part of its privacy guarantees since auditors would then have a way of knowing which users have keys in which servers.

But without auditors Bob will still know by the next epoch if the TB was spurious since the server will either not include the spurious TB in the tree, which he will detect when he does the first lookup for Alice's key and checks if the TB is included. Or the server will include the bad TB in the tree for Bob but not others (including Alice) and equivocate, which Bob will detect using regular CONIKS auditors. Alice will also detect the attack in the next epoch since she will have received a legitimate TB when she first registered her key, so she also has strong evidence of the attack. I hope this makes sense.

@vqhuy
Copy link
Member Author

vqhuy commented Jul 15, 2016

But without auditors Bob will still know by the next epoch if the TB was spurious since the server will either not include the spurious TB in the tree, which he will detect when he does the first lookup for Alice's key and checks if the TB is included. Or the server will include the bad TB in the tree for Bob but not others (including Alice) and equivocate, which Bob will detect using regular CONIKS auditors. Alice will also detect the attack in the next epoch since she will have received a legitimate TB when she first registered her key, so she also has strong evidence of the attack. I hope this makes sense.

Yes. I got that part. It makes sense, of course :-)
My most concern is in the first time when Bob receives Alice's TB. But if it is what proposed, I think it's fine to me to leave it as it is.

@masomel
Copy link
Member

masomel commented Jul 15, 2016

The fact that TBs are TOFU is definitely a concern. At the very least, we can enforce shorter epoch intervals to decrease the attack window. I do agree, though, that we should have a mechanism for auditing TBs. This is something we can work on in the future.

@vqhuy
Copy link
Member Author

vqhuy commented Jul 15, 2016

I do agree, though, that we should have a mechanism for auditing TBs. This is something we can work on in the future.

Great! I'm glad to know that :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants