Protocol for verifying a key from a previous epoch

[vqhuy]

Continue the discussion at #64 (comment)

[vqhuy]

I think it makes sense to try to make a distinction between lookup requests and monitoring requests, but I'm not sure epoch vs no epoch and TB vs no TB is the only distinction. As we defined monitoring (the operation), it's a self-check that you should be doing every single epoch (or catch up if you go offline). What if Bob goes offline for a couple epochs and needs to verify a message I sent him while he was offline? I don't think "monitor" should be the right request in this case since he's only interested in ensuring that my key was in the tree at that time, and that the old STR is consistent with the latest STR he saw.

Totally makes sense to me. A key lookup is probably the right request in this case. Just to clarify, in this case, Bob would request a lookup with the start epoch that is the latest epoch he saved, right?

So I still think that a lookup with an epoch would make sense for such cases, and the server returns a nil TB and a range of STRs if its not the latest epoch. A monitoring request could include a range of epochs (i.e. start and end epoch) and could return all auth paths and STRs for the given range (this will also save the client so many individual requests for each missed epoch). What do you guys think?

Agree, but I think the monitoring request could omit the end epoch, the server would return all auth paths and STRs from the given start epoch to the latest epoch. The request should include a range of epochs to prevent message overhead.

Maybe a better name would have been KeyLookup and KeyLookupInEpoch, which do have the Epoch / TB distinctions

Is this KeyLookupInEpoch different with monitoring request? I think they are the same, right?

Because, what if the current epoch is 5? We're looking for proof that at epoch 0, a key was absent (which they all should be). I don't think that's a misuse of any operation, though it may not be a popular request.

Yup, I wasn't thinking about this. Thanks!

Update: I just gave it a try in 3bbc298b71ffea0ed518c471b56dc517bc0cee66.

[masomel]

Sorry for joining in late.

Just to clarify, in this case, Bob would request a lookup with the start epoch that is the latest epoch he saved, right?

Yes, that's right.

Is this KeyLookupInEpoch different with monitoring request? I think they are the same, right?

I'm not sure. I think that KeyLookupInEpoch should only take the target epoch as a parameter, and the server should include all STRs from the epoch to the latest.

Because, what if the current epoch is 5? We're looking for proof that at epoch 0, a key was absent (which they all should be). I don't think that's a misuse of any operation, though it may not be a popular request.

This is a good point. On a related note, I've been wondering if would be more secure to verify that a newly registered name is absent in all epochs before the registration epoch? If we had auditors, I don't think this would be as big of an issue.

[vqhuy]

and the server should include all STRs from the epoch to the latest.

What do you think about:

The request should include a range of epochs to prevent message overhead.

I've been wondering if would be more secure to verify that a newly registered name is absent in all epochs before the registration epoch? If we had auditors, I don't think this would be as big of an issue.

I think the user can just verify the latest epoch before registering and she can trust the auditors which are what we will have in the future.

[masomel]

I think the user can just verify the latest epoch before registering and she can trust the auditors which are what we will have in the future.

Sounds good to me.

What do you think about:

The request should include a range of epochs to prevent message overhead.

Do you mean the response? I totally agree that we want to prevent message overhead (and I think I even mention this in my previous comment). I was trying to make a distinction between KeyLookupInEpoch and a monitoring request, since you had asked about that. I'm sorry if that wasn't clear. I think that in terms of arguments, both requests have the same two arguments (username, startEpoch), but what they return is different. The lookup should only return the AP for the startEpoch and all STRs in the range [startEpoch, latestEpoch], while the monitoring request should return all APs and STRs in that range.

[vqhuy]

Do you mean the response?

Yes.

The lookup should only return the AP for the startEpoch and all STRs in the range [startEpoch, latestEpoch], while the monitoring request should return all APs and STRs in that range.

Yeah, I get it. It makes a lot of sense to me now. Thanks!

[vqhuy]

The lookup should only return the AP for the startEpoch and all STRs in the range [startEpoch, latestEpoch], while the monitoring request should return all APs and STRs in that range.

Since the CONIKS protocol also includes the auditors involvements, and per paper, CONIKS auditors store only the current STRs of key servers, I was thinking that is there any way to make use of these auditors for the key lookup in epoch operation? I think instead of storing only the current STR, the auditor could story entire hash chain (i.e., [{STR_0, Epoch_0 = 0}, {STR_1, Epoch_1 = 1}, ...]. This's still a small amount of data ((SignatureSize + sizeof(uint64)) * number of STRs). This way, the key lookup in epoch response needs to include the STR at looking up epoch only, then the client could verify by comparing the received STR with the STR in that epoch stored in auditors. I'm not sure that whether this proposal has any security problems. What do you think?

For our discussion in #72 (comment), assume that the server splits a large response into chunks, I imagined that the responses could be

// e: querying epoch
// response #1
{AP_e, STR[e, e +limit]}
// response #2
{AP_e, STR[e+limit+1, ...]}

There're 2 questions come to my mind:

1. Do we need to return the AP_e in following responses?
2. Do we need to have a sequence number included in these responses? If so, I think it would make our implementation become more complicated.

[masomel]

I think instead of storing only the current STR, the auditor could story entire hash chain ... This's still a small amount of data ((SignatureSize + sizeof(uint64)) * number of STRs). This way, the key lookup in epoch response needs to include the STR at looking up epoch only, then the client could verify by comparing the received STR with the STR in that epoch stored in auditors.

At first glance, I think that it definitely makes sense for the auditors to store the entire hash chain, and to be part of the lookup in epoch. At the same time, I'm not sure it's enough for the client to compare the single STR for the lookup epoch with the auditor's STR. I need to think more about this.

1. Do we need to return the AP_e in following responses?

The format you suggested for chunked responses looks good to me. I don't think we need to if the chunked responses assuming that the client can order them.

1. Do we need to have a sequence number included in these responses? If so, I think it would make our implementation become more complicated.

I don't think so either, since the epochs in the STRs (either the first or the last in the list) can be used as sequence numbers. E.g. if the client saved epoch t=3 and sees two chunked responses with STRs starting at t=4 and t=8, I think this should be enough to help the client order the responses. Either way, I think chunking would make our implementation more complicated. Maybe we can add support for chunked responses as an optimization later?

[vqhuy]

At the same time, I'm not sure it's enough for the client to compare the single STR for the lookup epoch with the auditor's STR.

I think the saved STRs in the auditors are actually valid STRs, since they all have been verified. Yup, I'm not sure if this's right, though.

I think chunking would make our implementation more complicated. Maybe we can add support for chunked responses as an optimization later?

Yup, I don't disagree.

[vqhuy]

@arlolra : I think this is the reason why we have separate requests type for key lookup in epoch and monitoring: #70 (comment) (my first quote of @masomel's comments )

[masomel]

I think the saved STRs in the auditors are actually valid STRs, since they all have been verified. Yup, I'm not sure if this's right, though.

This is true, the auditors shouldn't be saving any STRs they can't verify. But the client should still be checking the whole hash chain range for itself, otherwise it wouldn't detect if a fork happened somewhere in the middle of the range. E.g. The client wants to lookup at epoch t=2 and the current epoch is t=5, and the server equivocated by creating a fork in the hash chain for the client at t=3. If KeyLookupInEpoch only returns the latest STR, the malicious server can present the client the valid STR for epoch t=5, which is consistent with the STR for t=5 that the unforked auditor saw, and the client wouldn't detect the fork. But if the client checks the whole hash chain range from t=2 to t=5 and then also compares its STR with the auditor's, the client forces the server to either reveal the fork or to present the valid hash chain.

[vqhuy]

If KeyLookupInEpoch only returns the latest STR

I think the KeyLookupInEpoch should return the STR of looking up epoch. This request would probably be used by users to lookup the key of their contacts in the past epochs. E.g., assume that Alice want to lookup for Bob's key at epoch t=2 and the current epoch is t=5, the server would return the STR at epoch t=2 to Alice. Since this STR is verified and monitored by Bob and auditors for detecting equivocation, I believe that Alice just needs to compare the received STR with some random auditors'. This may not work if Bob did not monitor his own binding from epoch t=2 to t=5 yet.
And does Alice just need to make sure that she received a valid STR at epoch t=2, i.e., it is a valid STR in the hash chain in range [0,2]? Maybe she don't care about the STR after epoch t=2, since she is looking up for the key at epoch t=2 only?

[masomel]

This request would probably be used by users to lookup the key of their contacts in the past epochs. E.g., assume that Alice want to lookup for Bob's key at epoch t=2 and the current epoch is t=5, the server would return the STR at epoch t=2 to Alice.

I understand that this scenario is the use case for KeyLookupInEpoch, but I had misunderstood which epoch's STR you are returning.

Since this STR is verified and monitored by Bob and auditors for detecting equivocation, I believe that Alice just needs to compare the received STR with some random auditors'.

You're right about this.

And does Alice just need to make sure that she received a valid STR at epoch t=2, i.e., it is a valid STR in the hash chain in range [0,2]? Maybe she don't care about the STR after epoch t=2, since she is looking up for the key at epoch t=2 only?

This, I'm a little more worried about. Let me think this through: If Alice is going to use the looked up key to verify Bob's signature on an old message (I believe this is the only scenario in which she would have to look up an old key), she definitely wants to make sure that the STR is part of a valid hash chain for range [0,2]. Otherwise, she could be using a spurious key. The issue with checking the range [0,2] is that Alice has no way of knowing if the STRs she is seeing for [0,2] at t=5 are the same as the STRs she saw at t=2. The server could be forking her at t=5, and she would not detect it. Whereas, if we leverage that Alice has an STR for t=5 that she got when she monitored her own key, since Alice has verified the range [0,5] at that point, she can make sure that the STR she got for Bob's key at t=2 is part of her [2,5] if KeyLookupInEpoch returns [2,4]. Does this make sense?

[vqhuy]

The issue with checking the range [0,2] is that Alice has no way of knowing if the STRs she is seeing for [0,2] at t=5 are the same as the STRs she saw at t=2

I suppose Alice could make sure about that since she has compared the received STR (STR at epoch t=2 when server is at epoch t=5) with the auditor's, she has also verified the range [0,5] at that point as you said, thus the STR she got should be part of the valid hash chain for range [0,5].
Otherwise, your explanation definitely makes sense.

[masomel]

the STR she got should be part of the valid hash chain for range [0,5].

I think the relevant word here is "should". The STR should be part of the valid hash chain, but there's no guarantee just because she sees it and some other auditors see it, and she also checked the hash chain for a different STR. The point I'm trying to make is that the server could be presenting Alice a malicious STR for t=2, which other auditors also see (if she happens to query the right auditors). Since Alice doesn't store all STRs, only the latest, she can't be sure the server hasn't equivocated about the "new" STR for t=2 unless she explicitly checks that it is part of her [0,5] range.

[vqhuy]

The point I'm trying to make is that the server could be presenting Alice a malicious STR for t=2, which other auditors also see (if she happens to query the right auditors).

I think this sound like the KeyLookup case (section 4.1.4 & app. B per paper).

Update: Can we think this as follows?
For each STR in range [0,5], Alice verifies it to make sure she got the valid hash chain. She also compares these STRs with auditor's, and instead of storing all the STRs herself, she trusts the auditors to store these STRs for her.
Then when she wants to re-verify the STR at epoch t=2 that she received from the key server at epoch t=5, she just needs to compare it with the STR at epoch t=2 from auditor's. Does this check ensure that the STR at epoch t=2 she got is part of her [0,5] range?

In addition, to make sure that the hash chain of the auditor is the same as her hash chain, Alice can compare the STR at epoch t=5 she received from the server with the STR at epoch t=5 of the auditor. I'm saying that because per paper,

CONIKS auditors store the current STRs of CONIKS providers; since the STRs are chained, maintaining the current STR commits to the entire history.

But I think this additional check is unnecessary. What do you think?

[masomel]

The point I'm trying to make is that the server could be presenting Alice a malicious STR for t=2, which other auditors also see (if she happens to query the right auditors).

I think this sound like the KeyLookup case (section 4.1.4 & app. B per paper).

Sorry, I'm not really sure what you're referring to.

She also compares these STRs with auditor's, and instead of storing all the STRs herself, she trusts the auditors to store these STRs for her.

I see two issues with this approach. The auditors aren't really trusted entities in the system, and by design Alice shouldn't always query the same auditors, so having Alice rely on some auditors to store the STRs leaves her open for being equivocated later by the server.

Then when she wants to re-verify the STR at epoch t=2 that she received from the key server at epoch t=5, she just needs to compare it with the STR at epoch t=2 from auditor's. Does this check ensure that the STR at epoch t=2 she got is part of her [0,5] range?

If Alice trusts the auditor, then it does. But I don't think trusting auditors alone is a reliable way of ensuring that the server's hash chain is valid.

In addition, to make sure that the hash chain of the auditor is the same as her hash chain, Alice can compare the STR at epoch t=5 she received from the server with the STR at epoch t=5 of the auditor. I'm saying that because per paper,

CONIKS auditors store the current STRs of CONIKS providers; since the STRs are chained, maintaining the current STR commits to the entire history.

But I think this additional check is unnecessary. What do you think?

So here you're suggesting that Alice compare both the STR for t=2 and the STR for t=5 with auditors when she does a KeyLookupInEpoch, right? The comparison for t=5 will happen when Alice monitors, but there's no guarantee she'll choose the same auditors for the lookup as she chose for the monitoring, right? You definitely bring up a good point that I wasn't thinking about, which is that clients only compare the current STRs because they commit to the entire history. I do think that this additional check is necessary (especially if this auditor is different than the ones Alice queried when monitoring her own key) since it can help increase her confidence that her and the auditor see the same history, and she doesn't have to check the entire hash chain on her end again.

I'm not sure I understand, at this point, what we would achieve by avoiding some of the checks that seem necessary to prove non-equivocation.

[vqhuy]

The point I'm trying to make is that the server could be presenting Alice a malicious STR for t=2, which other auditors also see (if she happens to query the right auditors).

I think if the auditors also see a malicious STR for t=2 as Alice, then the hash chain has been equivocated since (at least) epoch t=2 or before. Then this problem is actually auditing for non-equivocation operation, not just specified for KeyLookupInEpoch, I think.

She also compares these STRs with auditor's, and instead of storing all the STRs herself, she trusts the auditors to store these STRs for her.
I see two issues with this approach. The auditors aren't really trusted entities in the system, and by design Alice shouldn't always query the same auditors, so having Alice rely on some auditors to store the STRs leaves her open for being equivocated later by the server.

Using "trust" here is probably wrong. "Trust" here meant Alice could believe in the auditors that they would store the STR at each epoch. What I meant here is all the auditors would store the STR, and Alice queries the auditors at random. I'm still using assumptions per paper.

I do think that this additional check is necessary (especially if this auditor is different than the ones Alice queried when monitoring her own key) since it can help increase her confidence that her and the auditor see the same history, and she doesn't have to check the entire hash chain on her end again.

Yes, you're right. This check is necessary if all the auditors Alice queried see the same invalid history.

I'm not sure I understand, at this point, what we would achieve by avoiding some of the checks that seem necessary to prove non-equivocation.

I'm trying to simplify the KeyLookupInEpoch's response. If my thought was right, the response would need to include the STR at querying epoch, and the latest STR, not a range of the hash chain.

[masomel]

I think if the auditors also see a malicious STR for t=2 as Alice, then the hash chain has been equivocated since (at least) epoch t=2 or before. Then this problem is actually auditing for non-equivocation operation, not just specified for KeyLookupInEpoch, I think.

This is true. And it's true that is a check for non-equivocation, but as we state in the paper in 4.1.4, a non-equivocation check is supposed to happen every time the client gets an STR from the server: "Identity providers perform the history verification whenever they observe a new STR from any other provider, while clients do so whenever they request the most recent STR from a specific identity provider directly." Since every lookup returns (at least) one STR, clients should also be checking for non-equivocation in the KeyLookupInEpoch case.

"Trust" here meant Alice could believe in the auditors that they would store the STR at each epoch. What I meant here is all the auditors would store the STR, and Alice queries the auditors at random. I'm still using assumptions per paper.

I agree that auditors should store the STR at each epoch, and I agree that Alice can assume this. Maybe I was misunderstanding something, but it sounded to me like you were making an assumption that Alice can believe that the auditors she queries will see the same thing (even with random queries), because you had said

instead of storing all the STRs herself, she trusts the auditors to store these STRs for her.

and this isn't an assumption we should make. This is why I was saying that the auditors' STRs alone aren't enough to ensure non-equivocation. But then you said

the response would need to include the STR at querying epoch, and the latest STR, not a range of the hash chain.

which makes more sense to me because this allows Alice to gain confidence that there hasn't been an equivocation.

I'm trying to simplify the KeyLookupInEpoch's response.

We didn't cover the case for a lookup earlier in the history in our original design for CONIKS, so you're right that we should try to optimize the non-equivocation check for KeyLookupInHistory. I just want to make sure that we think about all the possible scenarios before we try to simplify more.

[masomel]

To recap, the protocol for verifying a key from a previous epoch is the following?

• client calls KeyLookupInEpoch("bob", 2)
• server responds with AP_bob_2, STR_2, STR_curr
• client verifies AP_bob_2
• For non-equivocation, client checks that STR_curr == STR_curr_saved, STR_curr == STR_curr_aud and STR_2 == STR_2_aud (repeat these last two checks with multiple auditors)

[vqhuy]

Yes, I think it is.
What do you think? @liamsi @arlolra

[vqhuy]

@masomel said:

On a related note, I've been wondering if would be more secure to verify that a newly registered name is absent in all epochs before the registration epoch? If we had auditors, I don't think this would be as big of an issue.

How can the auditors help us solve the TOFU issue? Does the client still need to verify all the STRs and the proof of absences from beginning?

[masomel]

How can the auditors help us solve the TOFU issue? Does the client still need to verify all the STRs and the proof of absences from beginning?

I'm thinking that auditors could help with this by allowing clients to verify that the STR they receive as part of the RegistrationResponse is the same as what auditors are seeing. Since the client will have verified the proof of absence that comes with the RR, too, it can be pretty sure that the user's name indeed did not exist in the tree before it was registered.

But I still need to think more about whether this is enough, i.e. I don't know if we can treat registration like any other auditing case. Or maybe we say it's not the client's responsibility to detect whether the the name "alice" existed before, but rather alice's responsibility for detecting (and reporting) that there are now two versions of its name in the tree? My main issue with this problem is that it's retroactive, not proactive, meaning that a lot of damage could have been done by the time alice detects the problem.