It's almost always probabilistic - someone guessing the right key the first time could break it very quickly.

It may be possible to reduce variance in cracking times by requiring multiple cracks (use a secret sharing scheme to break up the "real" key in chunks; encrypt each chunk in a crackable way.)