From fd9ca85878543771a7f09afd821a5a5511e71aea Mon Sep 17 00:00:00 2001 From: Jonathan McDowell Date: Thu, 1 Aug 2019 19:19:30 +0100 Subject: [PATCH] Improve handling of colliding 64-bit key IDs Originally key retrieval was all performed on the 64 bit key ID but back in 2013 support was added for fetching by fingerprint. However not all the pieces to deal with colliding 64 bit IDs were added at this time. This commit improves things by: * Using the fingerprint to retrieve the key to update in update_keys() * Returning all keys that share a 64 bit key ID from the DB4 backend, rather than just the first found. * Adding a test to ensure multiple keys are returned for a colliding key lookup. It also removes the old compatibility code for the DB4 backend with key lookups by 64 bit key ID. Note this isn't yet common in the wild; unlike Evil32 it is not possible to create collisions for arbitrary key IDs. --- keydb.c | 9 +- keydb_db4.c | 272 ++++++++++------------------------- keys/DDA252EBB8EBE1AF-1.key | Bin 0 -> 1140 bytes keys/DDA252EBB8EBE1AF-2.key | Bin 0 -> 1140 bytes keys/README | 4 + t/all-046-index-64bit-dupe.t | 26 ++++ 6 files changed, 109 insertions(+), 202 deletions(-) create mode 100644 keys/DDA252EBB8EBE1AF-1.key create mode 100644 keys/DDA252EBB8EBE1AF-2.key create mode 100755 t/all-046-index-64bit-dupe.t diff --git a/keydb.c b/keydb.c index f8d5a0b..deedc49 100644 --- a/keydb.c +++ b/keydb.c @@ -200,17 +200,16 @@ int generic_update_keys(struct onak_dbctx *dbctx, struct openpgp_publickey *curkey = NULL; struct openpgp_publickey *oldkey = NULL; struct openpgp_publickey *prev = NULL; + struct openpgp_fingerprint fp; int newkeys = 0; bool intrans; - uint64_t keyid; for (curkey = *keys; curkey != NULL; curkey = curkey->next) { intrans = dbctx->starttrans(dbctx); - get_keyid(curkey, &keyid); + get_fingerprint(curkey->publickey, &fp); logthing(LOGTHING_INFO, - "Fetching key 0x%" PRIX64 ", result: %d", - keyid, - dbctx->fetch_key_id(dbctx, keyid, &oldkey, + "Fetching key, result: %d", + dbctx->fetch_key_fp(dbctx, &fp, &oldkey, intrans)); /* diff --git a/keydb_db4.c b/keydb_db4.c index f3d20db..aa2f229 100644 --- a/keydb_db4.c +++ b/keydb_db4.c @@ -294,7 +294,11 @@ static int db4_upgradedb(struct onak_dbctx *dbctx) * @keyid: The 32bit keyid. * * This function maps a 32bit key id to the full 64bit one. It returns the - * full keyid. If the key isn't found a keyid of 0 is returned. + * first full keyid that has this short keyid. If the key isn't found a + * keyid of 0 is returned. + * + * FIXME: This should either return the fingerprint or ideally go away + * entirely. */ static uint64_t db4_getfullkeyid(struct onak_dbctx *dbctx, uint64_t keyid) { @@ -329,14 +333,11 @@ static uint64_t db4_getfullkeyid(struct onak_dbctx *dbctx, uint64_t keyid) DB_SET); if (ret == 0) { - if (data.size == 8) { - keyid = * (uint64_t *) data.data; - } else { - keyid = 0; - for (i = 12; i < 20; i++) { - keyid <<= 8; - keyid |= ((uint8_t *) data.data)[i]; - } + keyid = 0; + /* Only works for v4, not v3 or v5 */ + for (i = 12; i < 20; i++) { + keyid <<= 8; + keyid |= ((uint8_t *) data.data)[i]; } if (data.data != NULL) { @@ -465,87 +466,68 @@ static int db4_fetch_key_id(struct onak_dbctx *dbctx, uint64_t keyid, struct onak_db4_dbctx *privctx = (struct onak_db4_dbctx *) dbctx->priv; struct openpgp_packet_list *packets = NULL; DBT key, data; + DBC *cursor = NULL; int ret = 0; int numkeys = 0; - struct buffer_ctx fetchbuf; + uint32_t shortkeyid = 0; struct openpgp_fingerprint fingerprint; + bool first; - if (keyid < 0x100000000LL) { - keyid = db4_getfullkeyid(dbctx, keyid); + if (!intrans) { + db4_starttrans(dbctx); } - memset(&key, 0, sizeof(key)); - memset(&data, 0, sizeof(data)); + /* If the key ID fits in 32 bits assume it's a short key id */ + if (keyid < 0x100000000LL) { + ret = privctx->id32db->cursor(privctx->id32db, + privctx->txn, + &cursor, + 0); /* flags */ - data.size = 0; - data.data = NULL; + shortkeyid = keyid & 0xFFFFFFFF; + memset(&key, 0, sizeof(key)); + memset(&data, 0, sizeof(data)); + key.data = &shortkeyid; + key.size = sizeof(shortkeyid); + } else { + ret = privctx->id64db->cursor(privctx->id64db, + privctx->txn, + &cursor, + 0); /* flags*/ - key.size = sizeof(keyid); - key.data = &keyid; + memset(&key, 0, sizeof(key)); + memset(&data, 0, sizeof(data)); + key.data = &keyid; + key.size = sizeof(keyid); + } - if (!intrans) { - db4_starttrans(dbctx); + if (ret != 0) { + return 0; } - /* - * First we try a legacy stored key where we used the 64 bit key ID - * as the DB key. - */ - ret = keydb_id(privctx, keyid)->get(keydb_id(privctx, keyid), - privctx->txn, - &key, - &data, - 0); /* flags*/ + memset(&data, 0, sizeof(data)); + data.ulen = MAX_FINGERPRINT_LEN; + data.data = fingerprint.fp; + data.flags = DB_DBT_USERMEM; + + first = true; + while (cursor->c_get(cursor, &key, &data, + first ? DB_SET : DB_NEXT_DUP) == 0) { + /* We got a match; retrieve the actual key */ + fingerprint.length = data.size; + + if (db4_fetch_key_fp(dbctx, &fingerprint, + publickey, true)) + numkeys++; - if (ret == DB_NOTFOUND) { - /* If we didn't find the key ID try the 64 bit map DB */ - memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); data.ulen = MAX_FINGERPRINT_LEN; data.data = fingerprint.fp; data.flags = DB_DBT_USERMEM; - key.size = sizeof(keyid); - key.data = &keyid; - - ret = privctx->id64db->get(privctx->id64db, - privctx->txn, - &key, - &data, - 0); /* flags*/ - - if (ret == 0) { - /* We got a match; retrieve the actual key */ - fingerprint.length = data.size; - - memset(&key, 0, sizeof(key)); - memset(&data, 0, sizeof(data)); - key.size = fingerprint.length; - key.data = fingerprint.fp; - - ret = keydb_fp(privctx, &fingerprint)->get( - keydb_fp(privctx, &fingerprint), - privctx->txn, - &key, - &data, - 0); /* flags*/ - } - } - - if (ret == 0) { - fetchbuf.buffer = data.data; - fetchbuf.offset = 0; - fetchbuf.size = data.size; - read_openpgp_stream(buffer_fetchchar, &fetchbuf, - &packets, 0); - parse_keys(packets, publickey); - free_packet_list(packets); - packets = NULL; - numkeys++; - } else if (ret != DB_NOTFOUND) { - logthing(LOGTHING_ERROR, - "Problem retrieving key: %s", - db_strerror(ret)); + first = false; } + cursor->c_close(cursor); + cursor = NULL; if (!intrans) { db4_endtrans(dbctx); @@ -615,18 +597,9 @@ static int db4_fetch_key_text(struct onak_dbctx *dbctx, const char *search, while (ret == 0 && strncmp(key.data, curword->object, key.size) == 0 && ((char *) curword->object)[key.size] == 0) { - if (data.size == 12) { - /* Old style creation + key id */ - fingerprint.length = 8; - for (i = 4; i < 12; i++) { - fingerprint.fp[i - 4] = - ((unsigned char *) - data.data)[i]; - } - } else { - fingerprint.length = data.size; - memcpy(fingerprint.fp, data.data, data.size); - } + + fingerprint.length = data.size; + memcpy(fingerprint.fp, data.data, data.size); /* * Only add the keys containing this word if this is @@ -669,20 +642,9 @@ static int db4_fetch_key_text(struct onak_dbctx *dbctx, const char *search, db4_starttrans(dbctx); for (i = 0; i < keylist.count; i++) { - if (keylist.keys[i].length == 8) { - keyid = 0; - for (int j = 0; j < 8; j++) { - keyid <<= 8; - keyid |= keylist.keys[i].fp[j]; - } - numkeys += db4_fetch_key_id(dbctx, keyid, - publickey, - true); - } else { - numkeys += db4_fetch_key_fp(dbctx, &keylist.keys[i], - publickey, - true); - } + numkeys += db4_fetch_key_fp(dbctx, &keylist.keys[i], + publickey, + true); } array_free(&keylist); free(searchtext); @@ -718,7 +680,9 @@ static int db4_fetch_key_skshash(struct onak_dbctx *dbctx, memset(&data, 0, sizeof(data)); key.data = (void *) hash->hash; key.size = sizeof(hash->hash); - data.flags = DB_DBT_MALLOC; + data.ulen = MAX_FINGERPRINT_LEN; + data.data = fingerprint.fp; + data.flags = DB_DBT_USERMEM; ret = cursor->c_get(cursor, &key, @@ -726,22 +690,9 @@ static int db4_fetch_key_skshash(struct onak_dbctx *dbctx, DB_SET); if (ret == 0) { - if (data.size == 8) { - /* Legacy key ID record */ - keyid = *(uint64_t *) data.data; - count = db4_fetch_key_id(dbctx, keyid, publickey, - false); - } else { - fingerprint.length = data.size; - memcpy(fingerprint.fp, data.data, data.size); - count = db4_fetch_key_fp(dbctx, &fingerprint, - publickey, false); - } - - if (data.data != NULL) { - free(data.data); - data.data = NULL; - } + fingerprint.length = data.size; + count = db4_fetch_key_fp(dbctx, &fingerprint, + publickey, false); } cursor->c_close(cursor); @@ -819,32 +770,9 @@ static int db4_delete_key(struct onak_dbctx *dbctx, data.size = sizeof(worddb_data); /* - * Old format word db data was the key creation time - * followed by the 64 bit key id. + * New style uses the fingerprint as the data + * Old (unsupported) style was the 64 bit keyid */ - worddb_data[ 0] = publickey->publickey->data[1]; - worddb_data[ 1] = publickey->publickey->data[2]; - worddb_data[ 2] = publickey->publickey->data[3]; - worddb_data[ 3] = publickey->publickey->data[4]; - worddb_data[ 4] = (keyid >> 56) & 0xFF; - worddb_data[ 5] = (keyid >> 48) & 0xFF; - worddb_data[ 6] = (keyid >> 40) & 0xFF; - worddb_data[ 7] = (keyid >> 32) & 0xFF; - worddb_data[ 8] = (keyid >> 24) & 0xFF; - worddb_data[ 9] = (keyid >> 16) & 0xFF; - worddb_data[10] = (keyid >> 8) & 0xFF; - worddb_data[11] = keyid & 0xFF; - - ret = cursor->c_get(cursor, - &key, - &data, - DB_GET_BOTH); - - if (ret == 0) { - cursor->c_del(cursor, 0); - } - - /* New style just uses the fingerprint as the data */ memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); key.data = curword->object; @@ -897,26 +825,9 @@ static int db4_delete_key(struct onak_dbctx *dbctx, &cursor64, 0); /* flags */ + /* 32 bit short key mapping to fingerprint */ shortkeyid = keyid & 0xFFFFFFFF; - /* Old style mapping to 64 bit key id */ - memset(&key, 0, sizeof(key)); - memset(&data, 0, sizeof(data)); - key.data = &shortkeyid; - key.size = sizeof(shortkeyid); - data.data = &keyid; - data.size = sizeof(keyid); - - ret = cursor->c_get(cursor, - &key, - &data, - DB_GET_BOTH); - - if (ret == 0) { - cursor->c_del(cursor, 0); - } - - /* New style mapping to fingerprint */ memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); key.data = &shortkeyid; @@ -994,23 +905,6 @@ static int db4_delete_key(struct onak_dbctx *dbctx, shortkeyid = subkeyid & 0xFFFFFFFF; - /* Remove 32 bit keyid -> 64 bit keyid mapping */ - memset(&key, 0, sizeof(key)); - memset(&data, 0, sizeof(data)); - key.data = &shortkeyid; - key.size = sizeof(shortkeyid); - data.data = &keyid; - data.size = sizeof(keyid); - - ret = cursor->c_get(cursor, - &key, - &data, - DB_GET_BOTH); - - if (ret == 0) { - cursor->c_del(cursor, 0); - } - /* Remove 32 bit keyid -> fingerprint mapping */ memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); @@ -1086,24 +980,7 @@ static int db4_delete_key(struct onak_dbctx *dbctx, if (ret == 0) { get_skshash(publickey, &hash); - /* First delete old style keyid mapping */ - memset(&key, 0, sizeof(key)); - memset(&data, 0, sizeof(data)); - key.data = hash.hash; - key.size = sizeof(hash.hash); - data.data = &keyid; - data.size = sizeof(keyid); - - ret = cursor->c_get(cursor, - &key, - &data, - DB_GET_BOTH); - - if (ret == 0) { - cursor->c_del(cursor, 0); - } - - /* Then delete new style fingerprint mapping */ + /* Remove SKS hash -> fingerprint mapping */ memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); key.data = hash.hash; @@ -1243,8 +1120,8 @@ static int db4_store_key(struct onak_dbctx *dbctx, write_openpgp_stream(buffer_putchar, &storebuf, packets); /* - * Now we have the key data store it in the DB; the keyid is - * the key. + * Now we have the key data store it in the DB; the fingerprint + * is the key. */ memset(&key, 0, sizeof(key)); memset(&data, 0, sizeof(data)); @@ -1278,7 +1155,8 @@ static int db4_store_key(struct onak_dbctx *dbctx, } /* - * Walk through our uids storing the words into the db with the keyid. + * Walk through our uids storing the words into the db with the + * fingerprint. */ if (!deadlock) { uids = keyuids(publickey, &primary); diff --git a/keys/DDA252EBB8EBE1AF-1.key b/keys/DDA252EBB8EBE1AF-1.key new file mode 100644 index 0000000000000000000000000000000000000000..a192c3cd6d4f46ba53786c2971cbd251fac3d133 GIT binary patch literal 1140 zcmV-)1dIEb0u2OGZFltn5CEye`fOf-jWfhYb35V>v1b|B%s}x8L+S2W4S*14D7xuj z<`HkuC~ipwONyi+w`n;mX=2H3OnG_<^4k5KDgS0KXSUZgT8@hDo9hfdG_PUJgMB%u zu(KlC`Lf;d@yfPvh3_|l&YNoLq!QWw%8Z!Umf4Q~Xap)(Tx~~wW1xDPnPJ0F^QO!b zEYr3UQZ?WUQ4Gh)7C|L?a^Mk<-Q>k+{70v#U~%8AV1yYR_1_9F=>(I^ht*TDYC@x? zbhWoFqsPU{$o)9%o<$A!+MSk|$shI>_ijrJ@<#$mVyN@^0{B!H(wk#pe3`--1R&k< zG5*DTr?}n0Y=tEaY@=T~@&V&QI(HS7vE1_zt8AgT9)XJ3v zRc{3|_}MfAlIZ{u0YR;_C^*25Yoe%p2A&|T#`C*(A#J%vhqV(?Jir?ho57m&h6hU6WIUVQnNNyi} zDa~u1aFE?4(#zK2@rbq<<_$dh9g%0Xfd2Fiw84-nr1C8K{D$+H_aZZ{nOj=%cz~~Miyc_JtwuVrrH=+n#qM`29#Cg~b(p56)~m9yImz^lgJ>4z zoli~8EfB@YEle$^EYOaTX>GpUKI%42N_6zN87Y3ZSSHdny-`h}pONM+bmZvTxOgS_ zK25*LMw7a7S~RZ^D)Mv3*=dIR)WPwV+wFvN8EcjO?oxSEQTsMLwRTFLWe6Wp$fmbG z2Gsfn>Rr9v0#9BHgVQFkThv~M@Eo?dfv9Wq_=fi_?j0aHMjZb8BdN&gjlAtk4;vUY zq(UKd32vwjz+PB2iA+Ah9%Jx^>{FWo`}?eTn6(s8e?5=j;eFFU$vd)j&%i70ynMF+x%iHj8Z|+CdD)@Hs@VNB#4t7zAhYyJ9IP+xnV| GHIy6m-!88J literal 0 HcmV?d00001 diff --git a/keys/DDA252EBB8EBE1AF-2.key b/keys/DDA252EBB8EBE1AF-2.key new file mode 100644 index 0000000000000000000000000000000000000000..96aff0981f59d71a52f6dca25d20b930c0fe69bd GIT binary patch literal 1140 zcmV-)1dIEb0u2OGgZqC05CGD@nRvwPeS{=QRm_{KtcvCo=@}tk-x@V;NN6(rg6n6Y zZ-~P%GVs9Ea?Bt^SprLLugfkh&lKINTvBOVmn^!g2Q`Fk4xqsjJ8Ov)FiN54sWt6$ zLb&Kw2bIu?LyzqRd`~0gu(f#HH5Hmyx%LM1eZ8rqzN{xhH7q)#^5)3N}ML+_L{2JJvD8ZG7r}Khsh=XvqPJUH1(TDZu{Xr|KA5dPrngd5JJnmCmCG;* zIfO%6M17j&L{ggen*lj*oMf|cPuO&fVN8dw!QT!%NvJ+>R}TbLk7}^Ka0S63L_@_t zM(MoGE{GuQf~aWwGKqQ141JX)K$o*_!`lPNFK!S^x#_;hI^4t0vc;eqmm0Xd=a|%Z z%bHM&st5cnbiYjNP@K9H@^eBK5rt!~hTQs(&k-2P#Wc{J2W3DC+4}d;{)-#8of%gg zf`U)%OG)@Fl~y8tVonIzV+65>ISpPEoKU#cX_{-1O!P9#7DybyqSgHX=23}fV6-5Kx7ak!+8lWvbN z3$Mr}z|O;+dM5x80U&p@C_yzfF)}bTGB-0fG)6N*25Ty$}C;MY}@IXZJupH4S{CLT0B3xmm;K6rnLY6m497LWRuBy6xg5OAopq z8ZXGbFd2FrWZua?N?duJx3IJA%_7{e>Sr21(dC;0jjyRY1TCZ_cLKzI12;HkBOOQG zKf;0wM_-MJ1%jm+{kF^FJd6hKu=A9CJm<&WreNC6W2-fEoTt)6WqP7~`q88RpR~)} zB4%-dYe8*k#3U(0>yZPc!7AfgF~))zzf5ixxwJ#Yb@f(@;{``!zLz6c@R`#XH{ zBDu}(h3iyt!H8isxh@oF-GI@8q zIyS^K+vF{JpWAM(cZRD#4~WILbiBM4(_YkM>J6%&iX#_zy0w!Eh7!?-eiC@X! G6|=Yu!45tE literal 0 HcmV?d00001 diff --git a/keys/README b/keys/README index ac64056..2244d3e 100644 --- a/keys/README +++ b/keys/README @@ -24,3 +24,7 @@ elgv3.key A v3 key using Elgamal (generated by older version of GnuPG) test-v5.key A v5 sample key as provided by Werner Koch on the OpenPGP mailing list +DDA252EBB8EBE1AF-1.key +DDA252EBB8EBE1AF-2.key + A pair of keys sharing a 64 bit keyid, generated by David Leon Gil and + taken from https://github.com/coruus/cooperpair/tree/master/pgpv4 diff --git a/t/all-046-index-64bit-dupe.t b/t/all-046-index-64bit-dupe.t new file mode 100755 index 0000000..23b326f --- /dev/null +++ b/t/all-046-index-64bit-dupe.t @@ -0,0 +1,26 @@ +#!/bin/sh +# Check we can index a key by some uid text + +set -e + +# Backends should really support storing keys with full fingerprints, +# but the file + fs backends only do 64 bit keys IDs for simplicity. +# Skip the test for them. +if [ "$2" = "file" -o "$2" = "fs" ]; then + exit 0 +fi + +cd ${WORKDIR} +# Import 2 keys with the same 64 bit key ID +${BUILDDIR}/onak -b -c $1 add < ${TESTSDIR}/../keys/DDA252EBB8EBE1AF-1.key +${BUILDDIR}/onak -b -c $1 add < ${TESTSDIR}/../keys/DDA252EBB8EBE1AF-2.key +# Add an extra key so we know we're not just returning all of them +${BUILDDIR}/onak -b -c $1 add < ${TESTSDIR}/../keys/noodles.key +c=$(${BUILDDIR}/onak -c $1 index 0xDDA252EBB8EBE1AF 2> /dev/null | \ + grep -c -- '^pub ') +if [ $c != 2 ]; then + echo "* Did not correctly retrieve keys with duplicate 64-bit keyids" + exit 1 +fi + +exit 0 -- 2.39.2