EDIT: I realized after the fact there is a nice infographic in the git repo I reference in this post which should help if you follow along: https://github.com/lclevy/firepwd/blob/master/mozilla_pbe.pdf
I am going to rewrite this answer as I understand this process a bit better now. This is my attempt at an English synthesis of the information contained in https://connect.ed-diamond.com/MISC/MISC-069/Protection-des-mots-de-passe-par-Firefox-et-Thunderbird-analyse-par-la-pratique (English translation). Even though my answer here is pretty long, that document explains much more than my summary here.
Basically, this database contains two tables (I am going to explain this from the perspective of the key4.db sqlite DB, the key3.db contains the same data, but of course is stored in the bsddb185 format. Refer to the readBsddb() method in https://github.com/lclevy/firepwd/blob/master/firepwd.py for the intricacies of actually reading this DB. I think since this method exists, what's important is understanding the data that's actually in it rather than the mechanics of reading this old database).
One of the many pieces of this puzzle that had me confused was that, while I knew 3DES+CBC was the encryption algorithm used to store this data, I did not realize there were three separate 3DES+CBC strings to understand.
Once the data from the database has been extracted from either the key3.db BDB or the key4.db sqlite3 DB, the data we need is spread across two tables, the metadata table and the nssPrivate table.
The value we need from the metadata table is the encryption key for the actual private key used to decrypt the data in logins.json, known as the global-salt. This can be extracted with "SELECT item1 FROM metadata WHERE id = 'password';". The item2 column is actually just the string "password-check" that is encrypted with this global salt along with an IV packed along with it. For our purposes this should be unnecessary unless we want to test our master-password.
The next value is contained in the nssPrivate table. There's quite a bit of other data stored here, but the important column for our purpose is the a11 column (note those are ones and not Ls), extracted with "SELECT a11 FROM nssPrivate".
This column contains an ASN.1DER object that contains a few different values, but important to us are the encrypted private key, and the IV used to generate that private key (needed for the CBC part of 3DES). There is a lot going on in the ASN.1DER object, but using the pyasn1 library we can extract the values that we need. Once we've extracted all of those values, we simply need to pass them to the 3DES decryption method. All those steps together should look like this:
from pyasn1.codec.der import decoder
conn = sqlite3.connect(key4.db)
c = conn.cursor()
c.execute("select item1 from metadata where id = password;")
row = c.next()
globalSalt = row
c.execute("select a11 from nssPrivate")
row = c.next()
item2 = row
decodedItem2 = decoder.decode(item2)
entrySalt = decodedItem2.asOctets()
cipherT = decodedItem2.asOctets()
BUT WAIT, THERE'S MORE
Before we can decrypt the value stored in cipherT, we have another set of arcane hashing functions we need to perform before we get our private key. This will contain SHA-1 hashing the global salt together with the master password, then padding the entry salt with null bytes until it is 20 bytes long, SHA-1 hashing that with the value we just generated, then three more arcane hmac hashes. Once we've completed that set of arcane hashes on the global salt and the entry salt, we can split the value we receive - the first 8 bytes are the IV and the last 24 are the key needed to decrypted the value stored in cipherT. Put that all together, and you get this:
from hashlib import sha1
from Crypto.Cipher import DES3
hp = sha1( globalSalt+masterPassword ).digest()
pes = entrySalt + '\x00'*(20-len(entrySalt))
chp = sha1( hp+entrySalt ).digest()
k1 = hmac.new(chp, pes+entrySalt, sha1).digest()
tk = hmac.new(chp, pes, sha1).digest()
k2 = hmac.new(chp, tk+entrySalt, sha1).digest()
k = k1+k2
iv = k[-8:]
key = k[:24]
privateKey = DES3.new( key, DES3.MODE_CBC, iv).decrypt(cipherT)
Now that we have our private key, we need to do this whole process over again with the value stored in logins.json. The encryptedPassword and encryptedLogin fields are actually another ASN.1DER object encoded in base64 containing the actual encrypted password, the IV, as well as some other data not important to our particular use case. We can use the same pyasn1.codec.der.decoder.decode() function we used previously on the base64 decoded data. Once we get the encrypted password and the IV from that function, we can plug those values into the 3DES decrypt we used before to get our password:
encryptedPassword = "MDIEEPgAAAAAAAAAAAAAAAAAAAEwFAYIKoZIhvcNAwcECIb8AxZg6uueBAi0G6tJ10aBhQ=="
asn1data = decoder.decode(b64decode(encryptedPassword))
iv = asn1data.asOctets()
cipherText = asn1data.asOctets()
#use privateKey from the codeblock immediately preceding this one
cleartext = DES3.new(privateKey, DES3.MODE_CBC, iv).decrypt(cipherText)
Wow! That's the same combination I have on my luggage!
This is definitely a much more long and involved process than I originally expected, and finding this information was pretty darn difficult, so I hope that even though I may not have explained it all that well, that this may help anyone trying to answer this question in the future (the reason I wasn't really able to use https://github.com/lclevy/firepwd/blob/master/firepwd.py as is was because I'm actually working on doing the reverse - I have a TON (in the thousands) of PCs with thunderbird whose passwords I would like to change automatically which required that I do the reverse, which took about 3 workdays to figure out). Though my use-case will admittedly be pretty rare, so possibly this may only be of academic interest in the future.
Oh, and someone please change the combination on my luggage