I'm kind of surprised that this took "two weeks, a stable of computers, and billions of combinations tested"? If we make the (generous) assumption that this was using a 128-bit key (more than was common in 1993—the age of DES and 56-bit keys, unless you were using public key crypto – which would be a very strange choice for a military satellite), we have:
256 (2 * 128) keys with 1 bit different
32,512 (2^2 * 128 choose 2) keys with 2 bits different
2,731,008 (2^3 * 128 choose 3) keys with 3 bits different
170,688,000 (2^4 * 128 choose 4) keys with 4 bits different
8,466,124,800 (2^5 * 128 choose 5) keys with 5 bits different
So to reach billions of combinations you need 5 bitflips, which seems quite high! But I guess space is a pretty rough environment :)
Article says "which was only a handful of bits away from the original". As non-native speaker i don't know the exact nuance of handful when considering bits, but it seems a lot
No a handful in this abstract context (strengthened by the word “only”) means not so many (which given even the power of the computers at the disposal of the NSA at the time was enough to ruin your 2 weeks).
That's assuming NSA told the world (/ people who go around posting stories about their day-job to the internet) immediately after succeeding with the crack. Much better opsec to wait a for a period at least as big as the time it took to crack, leaks less information about the magnitude of compute you can harness.
Oh, you might be right – I originally had that but second-guessed myself (thinking that once you have the k bit positions, you need to exhaustively search the 2^k possible settings for those bits). I guess for each possible set of positions you only need to check the case where they're all flipped.
Without the extra factor you need 6 flipped bits to reach a billion combinations (128 choose 6 is 5,423,611,200).
256 (2 * 128) keys with 1 bit different
32,512 (2^2 * 128 choose 2) keys with 2 bits different
2,731,008 (2^3 * 128 choose 3) keys with 3 bits different
170,688,000 (2^4 * 128 choose 4) keys with 4 bits different
8,466,124,800 (2^5 * 128 choose 5) keys with 5 bits different
So to reach billions of combinations you need 5 bitflips, which seems quite high! But I guess space is a pretty rough environment :)