I spent a weekend building a secret scanner that reads a git repository's object database directly. No GitPython, no pygit2, no shelling out to git. Standard library only, because that was the rule of the hackathon I built it for.
The tool itself is straightforward: find API keys and credentials anywhere in a repo's history, including in files that were deleted years ago. The interesting part was everything git's on-disk format did to stop me.
Two things in particular. A variable-length integer encoding that looks identical to another one and isn't. And a repository big enough to prove that my working, tested, passing scanner was actually useless.
The part that looked easy, and was
Reading a loose git object is genuinely three lines:
raw = zlib.decompress(open(obj_path, "rb").read())
otype, size = raw[:raw.index(b"\0")].decode().split(" ")
content = raw[raw.index(b"\0") + 1:]
A git object is stored as zlib_compress(b" \0"). Inflate it, split on the null byte, done. The object's id is the SHA-1 of that entire decompressed buffer, header included, which means you can verify every read for free:
assert hashlib.sha1(raw).hexdigest() == expected_sha
I validated this against a real repo before writing anything else. It matched git cat-file exactly, first try. Very encouraging.
Then I ran git gc, every loose object vanished into a single .pack file, and the easy part was over.
This matters more than it sounds. Every repository you clone from GitHub arrives packed. A tool that only reads loose objects works beautifully on repos you created locally and fails on every repo anyone would actually hand it.
What's actually inside a packfile
A .pack file is a sequence of objects, each with a variable-length header encoding its type and size, followed by zlib-compressed content.
Except two of the seven object types aren't content at all. They're instructions.
OFS_DELTA and REF_DELTA objects say, in effect: copy these bytes from that other object, then insert these literal bytes. It's how git stores a file that changed by ten lines in a few dozen bytes instead of duplicating the whole thing. It's also why a naive reader gets garbage.
The size field in the object header is a varint: 7 bits of value per byte, continuation flag in the high bit, least-significant chunk first.
def _read_varint_size(buf, pos):
byte = buf[pos]
value = byte & 0x7F
shift = 7
pos += 1
while byte & 0x80:
byte = buf[pos]
value |= (byte & 0x7F) << shift
shift += 7
pos += 1
return value, pos
Fine. Now here is the one that cost me an afternoon.
The varint that lies to you
OFS_DELTA stores a negative offset pointing back to its base object. That offset is also a varint. It looks identical to the one above.
It is not the same encoding.
def _read_ofs_delta_offset(buf, pos):
byte = buf[pos]
value = byte & 0x7F
pos += 1
while byte & 0x80:
byte = buf[pos]
pos += 1
value = ((value + 1) << 7) | (byte & 0x7F) # <- the +1
return value, pos
Every continuation byte adds one before shifting. Git does this deliberately, so that no two distinct byte sequences can encode the same offset, but nothing about the format announces it. You have two varints in the same file, doing structurally similar jobs, with different carry rules.
I wrote the first version without the +1, because why would the carry rule change between one integer and another integer?
Here is what makes this genuinely nasty: it doesn't crash. A wrong offset doesn't point into empty space. It points at a different real object that happens to live at that byte position. You resolve it successfully. You apply a delta against the wrong base and get plausible-looking bytes out the other end.
I only caught it because I'd been SHA-verifying every resolved object against its own id since the very first commit. A wrong base fails its checksum instantly. Without that, I'd have shipped a scanner that silently read the wrong data on a subset of objects and had no idea.
The lesson generalises: when you implement someone else's binary format, build the format's own integrity check in first, before anything else works. It converts silent corruption into a loud failure at the exact moment you introduce it.
Applying a delta
Once you have the base, applying the delta is an interpreter for a two-opcode language. The high bit of each opcode byte picks which:
Copy (high bit set): the low 7 bits are a bitmask over up to 7 following bytes, 4 for a 24-bit offset into the base, 3 for a 24-bit length. Bytes the mask omits are implicitly zero. And a length of 0 means 0x10000, not zero, because nobody encodes a zero-length copy.
Insert (high bit clear): the byte itself is a length from 1 to 127, followed by that many literal bytes.
if op & 0x80:
offset = size = 0
for i in range(4):
if op & (1 << i):
offset |= delta[pos] << (8 * i); pos += 1
for i in range(3):
if op & (0x10 << i):
size |= delta[pos] << (8 * i); pos += 1
if size == 0:
size = 0x10000
out += base[offset:offset + size]
That if size == 0: size = 0x10000 is the kind of detail you only get from reading the spec properly. It's a special case that exists purely to reclaim an otherwise-wasted encoding.
The bug that only a real repository had
My first fully working version passed every test against a small hand-built fixture.
Then it hung on a cloned repo of about 1,200 objects.
Delta bases can themselves be deltas. Chains nest, sometimes deeply. My resolver was recursive and perfectly correct, but it re-resolved the same base from scratch every time a different delta pointed at it. With enough deltas sharing bases, the work explodes.
The fix was memoisation, keyed by byte offset in the pack:
def _resolve_at(self, offset, store):
cached = self._offset_cache.get(offset)
if cached is not None:
return cached
# ... resolve ...
self._offset_cache.put(offset, result)
return result
After that, the same repository resolved and SHA-verified all 1,200 objects in 90 milliseconds.
A four-object test fixture cannot expose this, because a fixture that small has no shared-base structure. The bug requires real data to exist at all.
And then a bigger repository had worse ones
At this point I had a scanner that worked. Tests passed. Real repo, correct output, fast.
So I pointed it at the full history of requests. 26,859 objects.
It reported 1,968 findings. Not one of them was real.
1,960 came from a single rule matching http://user:pass@host in documentation. I dumped the actual matched values and the entire distribution was five strings: pass, password, pass%20pass, pass%23pass, {ENCODED_PASSWORD}.
Then, with the entropy detector enabled, it produced 20,166 findings, of which 19,328 came from one file: requests/cacert.pem.
Every base64 line of a certificate is high-entropy. That is what a certificate is. It is also completely public.
Both problems are the same problem, and it took me embarrassingly long to see it:
Entropy measures randomness, and randomness is not secrecy.
A CA bundle is maximally random and perfectly public. The word "password" in a docs example is minimally random and equally harmless. No threshold on Shannon entropy separates either of them from a real credential, because the formula does not encode the distinction I actually care about.
What worked was structural, not statistical:
Is this token inside PEM armor? Then it's a certificate body, skip it. (Private keys still fire, because that rule matches the BEGIN line itself.)
Is this "password" one of the two dozen words people write when they mean your password here? Decode the URL-encoding first, then check.
Does entropy dominate this blob rather than appear once in it? Then it's an encoded data file, not source code with a key in it.
There was a memory bug hiding under all this too. My object cache was unbounded. Invisible at 1,200 objects; 172MB at 27,000; multiple gigabytes on anything CPython-sized. The tool would have died on exactly the repositories most worth scanning. Bounding it to an LRU window cost nothing measurable, because delta chains have strong locality: the base you need next is almost always one you touched recently.
Final numbers on that same repository: 4 findings, all true positives (real private keys in tests/certs/), 17 seconds, 87MB peak.
What I'd take away from it
Reimplementing a package is mostly not about the algorithm. zlib did the compression. hashlib did the hashing. What GitPython was actually selling me was knowledge of the format: a thousand small decisions like the +1 carry and the 0x10000 special case, each individually trivial and collectively the entire product.
And the thing I keep relearning, in a form I won't forget this time:
A tool that is correct on your fixture isn't finished. It's untested. Your fixture cannot contain the case you failed to anticipate, because you built it out of what you already anticipated. Every real bug in this project, the varint, the memoisation, the false positives, the memory, was found by pointing the thing at reality and being willing to read what it actually said back.
Top comments (0)