net-update verifcation checking insecure

Looking at this problem I think we should actually change the way we provide the keyring on the server and provide it
there as a signed keyring file.

I did not manage to get reliable key signature verification checks with gpg if there are multiple identical keyids in the keyring, so I think the best approach is to simplify and just provide the complete archive keyring file signed with the master-key.

I will outline a debdiff with the new approach.

This is what I have in mind, changing it to simply download the signed keyring, verify and if its good, import. I would like to clean the code up a bit more and extend the test, but it should be ok for a outline.

My understanding of the rationale for the addition of the signature file on the servers is as follows.

 - Provided that you don't have to match the key *size* but only the 8-byte key *ID*, it's very easy to create a collision.
 - The --list-sigs / --check-sigs output from gpg, even using --with-colons, does not include the key size in the output for the signatures, only in the output for the signed key
 - Therefore, it's impossible to tell with this interface whether the signing key is the correct one, with a collision-proof key size, or a fraudulent one with a much smaller key size.

However, if we allow for the requirement that we should *never* be importing the master signing key via the server, then I believe a secure method of validating the keys is possible without changing the server-side API.

 - grab the list of keys in the master keyring.
 - grab the list of new keys from the provided file.
 - for each new key:
   - verify that the key ID does not collide with that of any keys in the master keyring.
     - if it does, skip the key (alternatively: abort the entire operation)
   - export this key into a new temporary keyring
   - using only the master keyring and the new temporary keyring, verify that the new key is signed by a master key
   - if it is, import it
   - clean up the temp keyring

By rejecting any keys whose IDs collide with the master keys, and considering each new key in isolation for signature checking, I believe we eliminate any risk of impersonating the master key (barring cracking of the signing algorithm itself).

Does that seem reasonable, or have I overlooked something?

Thanks Steve for your analysis, this is exactly what the problem is.

I can not see a hole in this argument and attach a patch that implements this. I will also add a regression
test later for this. I will also think some more about it to see if I can find a flaw in the new approach.

I've made this bug public, so more eyes can look at it.

The attachment "Here is a outline of a patch for this, including a test" of this bug report has been identified as being a patch. The ubuntu-reviewers team has been subscribed to the bug report so that they can review the patch. In the event that this is in fact not a patch you can resolve this situation by removing the tag 'patch' from the bug report and editing the attachment so that it is not flagged as a patch. Additionally, if you are member of the ubuntu-sponsors please also unsubscribe the team from this bug report.

[This is an automated message performed by a Launchpad user owned by Brian Murray. Please contact him regarding any issues with the action taken in this bug report.]

I'm a little worried by the assumption here that adding the key size check is sufficient. It's certainly an improvement, but key ID collisions are clearly possible even without this - they're just more work. The key ID isn't *that* long, and it is still many orders of magnitude easier to construct an attack that involves a key ID collision than to brute-force the key itself. Can somebody explain to me how this approach defends against such an attack?

Hello Colin, thanks for your comment on this.

I'm not sure I quite follow the comment, the code is meant to check the following:
  for every key we got from the network, check if the same keyid is also in the master-keyring
    if that is the case -> abort as this clearly indicates that something fishy is going on

AFAICS this closes the attack vector described in the full-disclosure list as the attacker will not be
able to "shadow" our master-key-id anymore with the key id duplication.

For am I missing something and/or made a mistake in the code so that I actually check for the wrong thing?

After discussion with mvo on IRC I think my objection was incorrect, so I withdraw it.

There is also another scenario we should test for. If we decide to add a key to the downloaded keyring, an attacker could then add a duplicate key id for the new key in the spoofed keyring. I'm not sure what gpg would do in that scenario, which key would get parsed first, etc.

Thats a very good point Marc. I get the feeling the other approach (providing a signed version of the keyrigng or a signature file for it) is actually more robust and we should go with that.

Well, we could do what Steve originally suggested: export each key from the downloaded keyring one by one, validate it, and import it into a new keyring.

After discussing some improvements with Michael, I can't think of any issues with r1935 right now.
sbeattie is looking at it also.

This bug was fixed in the package apt - 0.8.16~exp5ubuntu13

---------------
apt (0.8.16~exp5ubuntu13) oneiric; urgency=low

  [ Adam Conrad ]
  * On armel, call update-apt-xapian-index with '-u' to keep the CPU
    and I/O usage low. We would do this on all arches, but there's a
    regression risk here, but that's better than killing slow systems.

  [ Michael Vogt ]
  * cmdline/apt-key:
    - fix apt-key net-update, thanks to Marc Deslauriers and
      Adam Conrad for the code review (LP: #857472)
 -- Michael Vogt <email address hidden> Thu, 06 Oct 2011 16:14:41 +0200