Makes sense. But what about the case in which I'm brute forcing a private key. And my machine is the only one working on the problem. At some point in time a million bajillion years from now I would expect to have been able to try all possible combinations. Now assuming there is only one matching private key, it would be possible to find that key on the very last sequence tried. What is the CDF? Would 50% CDF be half that time, in this case?
Hmm, yeah ok, I was a bit quick there. You're hashing an 80 byte bitcoin header. Of that you'll just want to change the 4 byte nonce and the 32 byte merkle root (determined by the transactions you include). So that's 36 bytes, or 288 bits, you change while hashing. That's 2 to the power of 288 possible permutations, which is 4.9732323640978664E86. If we round it up a bit the number of possible headers you can hash is 5 followed by 86 zeroes. As a second passes you can update the time field and you get that many new headers to try.
If you had a lot of hashing power I guess you could compute all those before everyone else, basically buying all the lottery tickets.
It's also possible that at some point, with a certain previous block hash, difficulty, and time value, that there is no valid solution until the time field has advanced months or years. It's just not very likely. It's actually more likely that Slender Man lives under your bed. So check on that first.
50% CDF means 50% of blocks are found with this amount of work or less at the difficulty in question. At 99% CDF only 1% of blocks take more work, so that's pretty unlucky. On average it happens with 1 out of 100 blocks though, so it's not like some people think; "bad luck like this is impossible, something must be wrong". Mining is like a lottery and on average 1 out of 100 blocks will take that much work. If you expect that to never happen, it's your thinking that is wrong.