They state that they can push an update that makes brute-forcing possible by disabling software-enforced delays between attempts.

Apple's security PDF says that the iteration count is calibrated so that one attempt takes 80ms in hardware, so that's the hard limit on the brute forcing speed, regardless of any updates Apple releases.

This means that a long alphanumeric passphrase is secure, but a 6-digit passcode could be broken in half a day, and a 4-digit passcode would take just a dozen minutes.

It's so weird how hard it is for the brain to handle exponential growth. I was amazed that a 4-digit password can be cracked so quickly at 80ms a pop, but you're right. Just for the hell of it, here's how long it would take for different length passcodes for digits, digits plus letters (case insensitive), and digits plus letters (case sensitive):

    # characters  [0-9]         [0-9a-z]            [0-9a-zA-Z]
    1             0.8 seconds   2.9 seconds         5   seconds
    2             8   seconds   1.7 minutes         5.1 minutes
    3             1.3 minutes   1   hour            5.3 hours
    4             13  minutes   1.6 days            2   weeks
    5             2.2 hours     8   weeks           2.3 years
    6             22  hours     5.5 years           140 years
    7             1.3 weeks     200 years           9   thousand years
    8             13  weeks     7   thousand years  550 thousand years
    9             2.5 years     260 thousand years  34  million years
    10            25  years     9   million years   2   billion years

Does this consider the "too many incorrect attempts" lockout that iOS imposes though?

Nope, it's just 80ms multiplied by the number of possibilities.

According to Snowden, the NSA can brute force at the speed of over a trillion guesses a second, of course, they would need to be able to disable other security features first.

Ok, I read the entire thing once again. Nowhere in there do they state that they can comply with the request, only the consequences that would result if it were possible. In fact they say they "even put that data out of our own reach".

If it is stated very clearly, can you quote me a sentence?

In the security guide linked here it seems possible for this iPhone model but not later ones.

Edit: According to the discussion below Apple can ship updates to the secure enclave. I don't know if that's possible to a locked phone.

The word "push" appears nowhere in their letter. There is no way (in evidence) of "pushing" anything to the locked phone OTA. Physical access as a requirement? Sure, there's likely some way to get something onto the phone. But any DFU or JTAG-enabled update (likely the only vectors available on a passcode-protected device) would not be able to gain access to any appreciable fraction of the data on the phone, since doing so would invalidate the keys.

I wouldn't be surprised (It isn't stated in their iOS security doc) if the key generation uses a hash of the system files as part of a seed for the entropy source used for keys, though that's pure speculation on my part.

Edited for clarity regarding "push" vs physical access.

No, they state clearly that this is what the court ordered them to do. That doesn't mean it is possible. The court doesn't care whether something is possible or not.

That doesn't sound all correct. Assuming the phone holds an encryption key that can read/write local data, a software update could simply command it to decrypt all data and save it as a copy.

A device containing an encryption key that's just protected by a software password check would be absolutely useless. Part or all of the encryption key (maybe even the IV) is derived from the phone passphrase, this is why you can't just pop the NVRAM off a phone and try to find the key.

yes this is very interesting!