This isn't a minor quibble, it's a major reason to go "Whaa?" at the idea that protein folding and protein design have intractable search spaces in practice. They have highly regular search spaces in practice or evolution couldn't traverse that space at all.

Yep, it's highly implausible that a natural non-designed process would happen to be a secure hash (as you know from arguing with cryonics skeptics). And that's before we look at how evolution works.

Good point. The search space is at least smooth once in a few thousand tries. (While doing the nearby fermi estimate, I saw a result that 12% (!!!) of point mutations in some bacteria were beneficial).

That said, the "worst possible case" is usually interesting.