g10/keydb.c: Cache consistency problem
Closed, ResolvedPublic

Description

g10/keydb.c uses a keyblock cache. This is currently a global cache. The
functions, however, assume that the cache is owned by a database handle. Thus,
if we do the following:

       keydb_search_fpr (hd1, fpr1);
       keydb_search_fpr (hd2, fpr2);
       keydb_get_keyblock (hd2, ...);
       keydb_get_keyblock (hd1, ...);

the second call to keydb_get_keyblock will (should) return the keyblock
associated with fpr2, not fpr1!

Consider the start of keydb_get_keyblock:

  gpg_error_t
  keydb_get_keyblock (KEYDB_HANDLE hd, KBNODE *ret_kb)
  {
    ...

    if (hd->keyblock_cache.state == KEYBLOCK_CACHE_FILLED)
      {
        iobuf_seek (hd->keyblock_cache.iobuf, 0);
        err = parse_keyblock_image (hd->keyblock_cache.iobuf,
                                    hd->keyblock_cache.pk_no,
                                    hd->keyblock_cache.uid_no,
                                    hd->keyblock_cache.sigstatus,
                                    ret_kb);
        if (err)
          keyblock_cache_clear (hd);
        if (DBG_CLOCK)
          log_clock (err? "keydb_get_keyblock leave (cached, failed)"
                        : "keydb_get_keyblock leave (cached)");
        return err;
      }

We don't check that the cache entry corresponds with the selected result.

Similarly, when we fill the cache further down in the same function, we don't
check that the prepared area is actually for this keyblock; the area could have
been prepared by another search on a different handle:

        err = keybox_get_keyblock (hd->active[hd->found].u.kb,
                                   &iobuf, &pk_no, &uid_no, &sigstatus);
        if (!err)
          {
            err = parse_keyblock_image (iobuf, pk_no, uid_no, sigstatus,
                                        ret_kb);
            if (!err && hd->keyblock_cache.state == KEYBLOCK_CACHE_PREPARED)
              {

Unfortunately, it is not enough to add a check that the cached data is what we
are looking for. It is possible that the same key is in multiple keyrings, but
with different contents (e.g., one has a revocation certificate and the other
doesn't).

Another interesting effect is that if keydb_search fails and the caller proceeds
to call keydb_getblock anyways data will be returned instead of an error message
if the cache is filled!

The attached patch makes the cache a per-handle cache. There is currently one
gotcha: in keydb_rebuild_caches, we invalidate the keyblock cache (but,
interestingly no the not found cache). Since we don't have a list of all
handles, it's not clear how to invalidate the cache. But, is it really
necessary? Reindexing shouldn't change the contents only the layout on disk,
right? (I'm sorry for my ignorance, but I haven't taken the time to figure out
exactly what this function does.) Further, the cache is only used for keyboxes
and keydb_rebuild_caches only works on keyrings (it's a noop for keyboxes). So,
I think it is safe to not invalidate the cache in this case.

neal added a subscriber: werner.
werner added a comment.Sep 1 2015, 9:45 AM

Fixing this is really problematic. For this very reason I proposed to drop the
feature of using several keyrings but too many users insisting on keeping it.
IIRC, this discussion is more the 15 years old.

werner lowered the priority of this task from High to Normal.Sep 1 2015, 9:45 AM
neal added a comment.Sep 1 2015, 2:44 PM

Why do you think fixing this is problematic? My simple patch ensures cache
consistency. What's the problem with it?

neal added a comment.Sep 1 2015, 6:26 PM

Just to be clear: this bug has nothing to do with multiple keyrings; it will
continue to occur even if we decide to use just a single keyring. The problem
has to do with multiple handles.

neal added a comment.Sep 2 2015, 11:07 AM

I've attached a patched that demonstrates the problem. This uses a single
keyring. Here is the output using the cache consistency fix:

  $ gpg2
  : keydb_search: preparing cache
  : keydb_search: preparing cache
  : keydb_get_keyblock: enter (cache state: 1).
  : keydb_get_keyblock: filling cache.
  : keydb_get_keyblock: enter (cache state: 1).
  : keydb_get_keyblock: filling cache.
  : desc1: Werner Koch (ha ha test) <wk@gnupg.org>
  : desc2: Werner Koch <wk@g10code.com>
  : Looks good.

And here is the output when the patch is not applied:

  $ gpg2
  : keydb_search: preparing cache
  : keydb_search: preparing cache
  : keydb_get_keyblock: enter (cache state: 1).
  : keydb_get_keyblock: filling cache.
  : keydb_get_keyblock: enter (cache state: 2).
  : keydb_get_keyblock: returning data from cache.
  : desc1: Werner Koch <wk@g10code.com>
  : desc2: Werner Koch <wk@g10code.com>
  : Same name (fail)!

As you can see, the second time keydb_get_block is called, it sees a filled
cache and simply returns the contents. However, the contents are for a
different search. I hope you now agree that fixing this bug is not really
problematic, that the problem has nothing to do with multiple keyrings and this
bug doesn't relate to the 15 year old discussion.

werner reassigned this task from werner to neal.Sep 2 2015, 12:05 PM

Okay

neal closed this task as Resolved.Sep 2 2015, 8:40 PM