which is a slightly easier problem, about 100,000x faster

Where did you get this number from? I was under impression that this is completely infeasible (just like we can generate a collision good md5 in seconds, but we still can't do a preimage attack).