You're correct that collision resistance is not sufficient for the above construction to be secure, but you don't need to assume H() is a random oracle. You could instead model H(k||s) as a pseudorandom function with k as the key. And of course, if you don't trust existing functions to be directly pseudorandom, then a PRF can be built from one-way functions: so pre-image resistance is sufficient. (The remaining question is how to get there from CR alone.)