Difficulty of fixing reconciliation

[Alessandro Vesely]

On Tue 13/Aug/2019 13:07:07 +0200 Peter Lebbing wrote:
> On 13/08/2019 09:54, Alessandro Vesely via Gnupg-users wrote:
>> More than a reasonable number of signatures makes no sense in
>> practice, so I agree lists should somehow be "fixed" so as not to
>> accept an unreasonable number of signatures (reasonable == 2??)
> 
> [...]
> 
> Furthermore, this is from memory, but when I read basic information
> about the SKS reconciliation algorithm, I see the terms "monotonicity
> requirement for progress" or something alike.


Absolute monotonicity is wrong.  It must be possible to delete errors.


> [...skip algorithm for their PhD thesis...]
>
> Let's do this with your max 2.
> 
> Somebody uses SKS keyserver network host A to add two signatures, call
> them A1 and A2 to the key in question, which did not have any signatures
> yet. Host A accepts them, they fall within the limits.
> 
> Either this same person or someone else adds two signatures on SKS
> server B on the same key, call them B1 and B2. Hosts A and B haven't
> reconciled yet, so B sees no signatures on the key and accepts.
> 
> Now they reconcile.
> 
> They compare their datasets. They are not the same: we still need to
> have progress to get to completion. Let's reconcile signature A1. Server
> A offers server B signature A1. Wait a minute, the key already has
> signatures B1 and B2. Server B cannot accept signature A1, it would
> break the contract that there are ever only 2 signatures on the key.
> 
> Now we have a deadlock. There is no following step that would fulfill
> the monotonicity requirement as well as make any progress. The only way
> to fulfill the monotonicity requirement is when server A keeps the
> signatures A1 and A2, and server B keeps B1 and B2. But the progression
> has halted and the process never finishes.


The illegal sig shall be deleted from both servers.  (2 is a bit
Procrustean, a reasonable number would be enforceable.)


> Besides, any limit on the number of signatures is a Denial-of-Service.
> In your case, if Alice, Bob and Carol all sign eachother's keys, there's
> no more room for other signatures. And if Mallory creates two bogus keys
> and signs all the keys of Alice, Bob and Carol, the three can't add any
> real signatures anymore.


I'm no expert, but it seems to me that 3rd party signatures should not
be allowed.  All signing party recipes provide for /exchanging/ sigs,
but then rely on the fact that Alice can sign Bob's sig before Bob has
signed Alice's and without Bob's authorization.  That is, the
semantics is good, but it's not algorithmically enforced.


> The algorithm is designed to withstand very well funded actors,
> oppressive regimes were what the designers were thinking of. Obviously,
> the algorithm does this regardless of who is trying to do something
> otherwise, no matter whether it is a repressive regime or the legitimate
> operators and designers of the system.


Hm... if your sig is signed by a suspect, you become suspect too?  In
fact, SKS servers with lots of countersigned sigs is manna from heaven
for police.  I recall someone in the sixties recommending "Comrades,
no phone-books!  Burn them, learn numbers by memory and burn them."

So, would that be a reason to allow 3rd party signatures?  I sign your
sig, but then I also sign a few dozens other random sigs so as to
conceal the link between you and me.  Sounds like a poor trick to me.


>> The bug, however, is in the program that chokes on poisoned keys!
> 
> [...skip very unfavourable runtime <-> data size ratio...]
> 
> So GnuPG gets a key with a lot of third-party signatures. It can keep
> wading through all the crap looking for the real signatures the user
> does want between all the crap added by attackers, and this takes a lot
> of runtime.
> 
> Or it can decide: this is taking to long, I bail out.


Exactly!  That signature is poisoned, delete it.  There might be
utilities that attempt to recover it —much like AV utilities to
recover infected files.


>> Was that fixed, yet?
> 
> How? You keep looking through the piles of crap, or you stop looking. In
> either case, you don't find what you are looking for in a desirable
> length of time.


The defense would try and avoid poisoning.  When a signature is
poisoned, the defense has failed.


> I think the solution needs to be sought in a direction where GnuPG
> doesn't have to look for valid data amidst a lot of invalid crap.
> Because evaluating the invalid crap can always be made expensive, so
> there should be other means to say "I'm not going to parse this, find
> another way to get me the proper data where it's not buried in crap".


Agreed.


Best
Ale
-- 









-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <https://lists.gnupg.org/pipermail/gnupg-users/attachments/20190814/6d62ecb9/attachment.sig>