Beating the 678-Byte APK on Modern Android

There’s an old repo called fractalwrench/ApkGolf with a 678-byte APK in it. For a while that was the smallest known valid Android package. The problem is that it skips targetSdkVersion, which defaults to 0, and Android 14+ rejects that with INSTALL_FAILED_DEPRECATED_SDK_VERSION. So the record holder doesn’t really install anymore unless you pass a bypass flag.

I wanted to see if I could beat it anyway. I ended up writing the whole thing from scratch in Python (manifest builder, ZIP assembler, certificate generator, v2 signer) and eventually got a plain-adb install build down to 656 bytes on my test device.

The tooling doesn’t help you here #

apksigner sign works fine for normal APKs, but it pads and aligns things in ways that add hundreds of bytes. Won’t work for us.

A signed APK with a single AndroidManifest.xml entry breaks down into three parts: the ZIP structure, the compressed manifest, and the APK signing block.

An APK is just a ZIP file, and even for a single entry ZIP has way more structural overhead than you’d think. Every file gets two headers: a Local File Header (LFH) right before the compressed data, and a Central Directory File Header (CDFH) in a directory section at the end of the archive. Then there’s an End of Central Directory (EOCD) record that points to where the central directory starts. For normal archives with hundreds of files this overhead is negligible, but when the entire APK is one tiny manifest, it matters a lot.

For a single AndroidManifest.xml entry with all optional fields zeroed out, the math works out to:

• LFH: 30 bytes fixed + 19 bytes filename = 49
• CDFH: 46 bytes fixed + 19 bytes filename = 65
• EOCD: 22 bytes

Total: 136 bytes of ZIP structure before you even count the actual manifest data. The filename has to be exactly AndroidManifest.xml because Android’s PackageParser does a string match. You can zero out timestamps, extra fields, and internal attributes, but the signatures, offsets, CRC, and filename are all mandatory.

The manifest #

Android doesn’t store AndroidManifest.xml as text. It gets compiled into a binary format called AXML, a chunk-based structure with a string pool, element records, and attribute records. Normally aapt or aapt2 does this compilation, but those tools add extra chunks (resource maps, namespace declarations) that we don’t need. So I wrote the binary directly.

For the golf build, the manifest is just <manifest package="c.c"> encoded as AXML. No <application>, version fields, resource map. In binary that’s:

• XML wrapper header: 8 bytes
• String pool ("c.c", "manifest", "package"): 64 bytes
• StartElement for <manifest> with the package attribute: 60 bytes
• EndElement: 24 bytes

def build_minimal_manifest(package_name: str = "c.c") -> bytes:
    if "." in package_name:
        strings = [package_name, "manifest", "package"]
    else:
        strings = ["manifest", package_name, "package"]
    string_index = {value: index for index, value in enumerate(strings)}
    pool = _build_string_pool(strings)
    manifest = _build_start_element(
        name=string_index["manifest"],
        attrs=[
            _build_attr(
                ns=0xFFFFFFFF,
                name=string_index["package"],
                raw_value=string_index[package_name],
                data_type=TYPE_STRING,
                data=string_index[package_name],
            )
        ],
        ns=0,
        comment=0,
    )
    end = _build_end_element(name=string_index["manifest"], ns=0, comment=0)
    return _wrap_xml(pool + manifest + end)

156 bytes uncompressed, 82 after zopfli. I tried a bunch of different short package names to see if DEFLATE would compress any of them better. It didn’t, c.c was already at the sweet spot.

ZIP tricks #

I spent some time on the obvious question: can you overlap ZIP headers or entries to save space. Classic ZIP tricks exploit the fact that LFH and CDFH both store the filename and metadata redundantly. In theory you could make the CDFH point back into the LFH area and reclaim those duplicate bytes.

Not really, at least not here. Android’s ZIP parser (specifically LocalFileRecord in AOSP’s apksig) checks that LFH data doesn’t extend past the start of the central directory, that LFH and CDFH metadata agree, and that no entry data overlaps with the CD section. And once v2 signing is in the picture, the content digest covers the actual ZIP byte layout in three separate sections (everything before the CD, the CD itself, and the EOCD), so you can’t have structures that are ambiguous between the two views. I read through the apksig source to confirm. Dead end.

The signing block #

This is where most of the bytes are. Final breakdown:

• ZIP structure: 136
• compressed manifest: 82
• signing block: 458

Before signing, the APK is just this:

[manifest data] [central directory] [EOCD]

APK v2 signing inserts one big block before the central directory:

[manifest data] [APK Signing Block] [central directory] [EOCD]

The annoying part is the EOCD. ZIP readers use it to find the central directory, so after inserting the signing block I have to patch one offset in the EOCD. Otherwise the APK is just a broken ZIP.

The even more annoying part is that Android does not hash the final file exactly as-is. The signing block contains the signature, so it can’t be part of the bytes being signed. Instead, Android verifies the APK as if the signing block was removed again: hash the data before it, hash the central directory, and hash a patched EOCD where the central-directory offset points to the old place.

So my builder does the same thing:

def prepare_apk_v2(unsigned_apk: bytes) -> tuple[bytes, bytes, bytes, bytes]:
    before_central_directory, central_directory, eocd = _split_zip_sections(unsigned_apk)
    eocd_for_digest = bytearray(eocd)
    struct.pack_into("<I", eocd_for_digest, 16, len(before_central_directory))
    content_digest = _compute_chunked_sha256_digest(
        [before_central_directory, central_directory, bytes(eocd_for_digest)]
    )
    return before_central_directory, central_directory, eocd, content_digest


def assemble_apk_v2(*, before_central_directory, central_directory, eocd, signing_block):
    final_eocd = bytearray(eocd)
    struct.pack_into("<I", final_eocd, 16, len(before_central_directory) + len(signing_block))
    return before_central_directory + signing_block + central_directory + bytes(final_eocd)

That’s basically the whole trick. Build unsigned ZIP, hash the version Android expects, put the signature block in the middle, then fix the EOCD so normal ZIP parsing still works.

Comparing against the original #

The thing that actually moved the needle was when I stopped guessing and just pulled apart the original signed-release.apk and key.x509.pem from the ApkGolf repo.

The build.sh in that repo is not interesting. The artifact is.

• upstream: 678 = 136 ZIP + 82 manifest + 460 signing block
• mine at that point: 680 = 136 ZIP + 82 manifest + 462 signing block

Same ZIP, same manifest. The difference was entirely in the signing block. That narrowed things down fast.

My certificate builder was already pretty minimal, but the upstream cert was still smaller. Diffing the hex got me part of the way there. One useful detail was that they used OID 0.1 in the distinguished name instead of the more obvious junk OIDs I started with.

But the bigger finding came later, when I stopped looking at apksigner verify as the source of truth and started testing every weird cert combo on a real device.

The package installer on my phone accepts a certificate whose SubjectPublicKeyInfo uses a compressed P-256 point, while the signer record in the v2 block still carries the normal uncompressed SPKI. If you compress both, it dies. If you compress only the cert, apksigner verify says the APK is malformed, but adb install still succeeds and PackageManager reports it as a v2-signed app.

That was the real breakthrough, because it cuts 32 bytes out of the certificate without touching the signer record:

def build_minimal_certificate_der(private_key, *, compressed_subject_public_key=False):
    algorithm = _seq(_oid("1.2"))
    issuer = _minimal_name()
    subject = _minimal_name()
    public_key = private_key.public_key()
    point_format = (
        serialization.PublicFormat.CompressedPoint
        if compressed_subject_public_key
        else serialization.PublicFormat.UncompressedPoint
    )
    point = public_key.public_bytes(serialization.Encoding.X962, point_format)
    public_key_info = build_subject_public_key_info_from_point(point)
    tbs = _seq(_integer(1), algorithm, issuer, validity, subject, public_key_info)
    signature = b""
    return _seq(tbs, algorithm, _bit_string(signature))

Signature brute-forcing #

The part I didn’t expect: ECDSA signatures on the same key and same message don’t always have the same DER length.

An ECDSA signature is two big integers, r and s, encoded in DER as a SEQUENCE of two INTEGERs. DER integers are variable-length and need a leading 0x00 byte when the high bit is set (to distinguish them from negative numbers). So a P-256 signature can be anywhere from ~68 to ~72 bytes depending on whether r and s happen to need that padding. OpenSSL picks a random nonce k each time you sign, which gives you different r and s values even for identical inputs.

At this stage I was still letting OpenSSL choose random signing nonces. I was generating a key, signing once, and moving on. That’s wasteful. Better to sign the same payload dozens of times per key and keep the shortest one:

def _find_shortest_signature(private_key, signed_data, *, signs_per_key):
    best = None
    for _ in range(signs_per_key):
        sig = private_key.sign(signed_data, ec.ECDSA(hashes.SHA256()))
        if best is None or len(sig) < len(best):
            best = sig
    return best

Most signatures came out at 69-72 bytes. 68 showed up once in a while. Never saw 67 in 20k attempts. This still matters, because once the compressed-cert trick was in place, signature length was back to being one of the few moving parts left. A lucky 69-byte signature was enough to get one build down to 656.

Dead ends #

For the record, things that didn’t work:

• Compressed EC points in both the certificate and signer record
• Empty issuer/subject DN
• Empty AlgorithmIdentifier
• Stripping any of the required v2 signing structures
• ZIP entry/header overlap tricks

The funny non-dead-end is compressed EC points only in the certificate. apksigner hates it, but the actual device installs it.

Result #

output/bypass.apk: 656 bytes, 22 less than the old record.

The weird part is that it no longer verifies clean in apksigner. apksigner verify rejects the compressed certificate, but plain install on my test device succeeds:

$ adb install output/bypass.apk
Performing Streamed Install
Success

So this first result was not “smallest APK that keeps apksigner happy”. It was “smallest APK I could get to install on a modern Android device without any bypass flag”. It still belonged to the old probabilistic build path: generate keys, ask OpenSSL generate a bunch of random ECDSA signatures and keep the shortest one.

The command I used for that phase was:

APKGOLF_ZOPFLI_ITERATIONS=200 python -m tools.build --rounds 1000 --signs-per-key 64

If there’s another byte to find, it’s probably still in the ECDSA signature. Or in some even dumber disagreement between the desktop verifier and PackageManager on a real phone. That’s the next rabbit hole.

Update: 624 bytes #

So, yeah. There was another byte to find.

Actually, 32 of them.

The previous result was 656 bytes. After more poking at the cert parser and after giving up on OpenSSL’s random ECDSA nonces, the same idea is now down to 624 bytes.

The final layout is:

• ZIP structure: 136
• compressed manifest: 82
• signing block: 406

Total: 624 bytes.

The ZIP and manifest did not move. The entire win came from the signing block again, because of course it did.

The dead end that wasn’t #

In the first pass I had “empty issuer/subject DN” in the dead-end list. That was true for the exact malformed shapes I tested back then, but it wasn’t true in the useful way.

A normal-ish tiny name looked like this:

SEQUENCE {
  SET {
    SEQUENCE {
      OID 0.1
      PrintableString ""
    }
  }
}

Tiny, but still not free.

The device also accepts the issuer and subject as just empty DER SEQUENCEs:

30 00

That’s 2 bytes per name. No OID, SET or anything else. apksigner is already unhappy because of the compressed public key in the certificate, but we don’t care. PackageManager on the phone accepted it.

That changed the certificate from 134 bytes to 115 bytes.

With the old random-signature setup, the empty-name trick got the APK from the mid-640s to 628 bytes. That was still the lottery-based path, just with a smaller certificate. At that point the breakdown was basically:

• manifest: still 82
• cert: 115
• signer public key: still 91
• ECDSA signature: usually 68-70

So there was nothing left to do except stare at the ECDSA signature again.

Stop asking OpenSSL nicely #

Brute-forcing signatures by calling private_key.sign() works, but it’s a dumb lottery. OpenSSL chooses a random nonce k, returns a DER signature, and you hope both integers happen to be short.

For golfing, the nonce is the interesting part. ECDSA is:

r = x(kG) mod n
s = k^-1 * (H(m) + r*d) mod n

Where:

• d is the private key
• k is the signing nonce
• n is the P-256 group order
• m is the v2 signed-data blob

Nothing says I have to ask OpenSSL to invent k for me during the final build. I can search for good k and d values offline, compute r and s, DER-encode the pair, verify the result locally, and then bake those values into the builder.

The important bit is that DER INTEGERs are minimal. If the first byte would have the high bit set, DER adds a leading zero. If the integer starts with zero bytes, DER drops them. So the golf target is not “valid ECDSA signature”. That’s easy. The target is “valid ECDSA signature where both r and s serialize short”.

For the new method, I started by searching for a nonce whose r was small enough to encode in 29 bytes instead of the usual 32 or 33:

k = 1476301
r = 0x681931a6ef9f2d17ae79af40a6edcb081751089fdf5f7a9c07b141d4c

That gave me a 29-byte r.

Then I fixed that nonce and searched private keys until s was also short. Since ECDSA has the usual s vs n-s symmetry, I tried both and kept the shorter DER encoding. This search is the expensive part, but it happens once; the published build no longer brute-forces signatures at runtime.

The final values for the c.c build are:

d = 19249613
k = 1476301

That produces this 64-byte DER signature:

303e021d0681931a6ef9f2d17ae79af40a6edcb081751089fdf5f7a9c07b141d4c021d30d276509eea634f0209fd9370ebdbf76fdbac73064d9e27ab748e765c

The signature starts with 30 3e, which means the SEQUENCE payload is 62 bytes. Each INTEGER is 29 bytes of payload plus the 02 len wrapper.

Why not 623? #

There was a very tempting fake win: use a one-letter package name.

package="a" compressed the manifest to 80 bytes, which would immediately beat the 82-byte c.c manifest. It also produced a smaller APK locally. Android did not care for it:

INSTALL_PARSE_FAILED_BAD_PACKAGE_NAME: Invalid manifest package: must have at least one '.' separator

I also tried weird edge names like a., .a, and .. Some of them install, which is funny, but none of them compressed below 82 bytes in the useful case. I brute-forced short names over [a-z.] and didn’t find a valid package name with a compressed manifest under 82.

So the manifest is still stuck at 82 bytes.

To get to 623 without a new structural trick, I need a 63-byte DER signature. With the current 29-byte r, that means making s encode in 28 bytes. That’s not impossible, just rarer. The search that found the 64-byte signature took a few minutes on my machine; the next byte is much less friendly.

Current result #

The current artifact is:

output/golf.apk: 624 bytes

Build:

nix develop -c python -m tools.build

apksigner verify still fails, for the same reason as before: the certificate uses a compressed P-256 point. The actual install-tested shape is still the one Android accepts:

• compressed SPKI inside the certificate
• normal uncompressed SPKI in the v2 signer record
• empty issuer/subject names
• 13-byte UTCTime values, because shorter ones really do break parsing
• fixed ECDSA nonce and private key for a 64-byte DER signature

So the new number is 624 bytes. Cool, I guess.

At this point the next rabbit hole is either a 63-byte signature, or finding another place where Android’s actual parser is more permissive than the tools around it.