The crudeness in this is really the timeline.  While we have a pretty good idea of roughly (in billions of years or so) when the big bang was, the sun accumulated enough mass, when it'll burn out and eventually the heat death of the universe, these are relatively fixed points in time and they aren't going to move around on that timeline very much.

For finding a key collision,

it could just as easily be:                 , you finding k
big bang       sun was born      now. /         sun dies       existing stars burn out                       all matter evaporated
     |-------------|---------------||-------------|---------------|-----------------------------------------|
     0                 9.2e9            13.8e9             19e9                 1e15                                               1e34

( not to scale )
It's just that the odds of that being the case are very, very, very (rinse and repeat a lot) low.  Of course the odds are exactly the same for your point along the timeline, or for any other point along the timeline within the bounds as proposed, to the point where statistically speaking it doesn't make sense to even try.