I recently read that generating large master keys for symmetric ciphers is very expensive. But what exactly do they cost? Any references would be much appreciated. I have checked NIST but actual costs seem hard to find.
The cost for generating master keys is not very expensive. It just requires secure random bit string of the same size as the key. Compare this with RSA, where a random prime needs to be generated. This may require repeated calls to the random number generator; you'd expect at least the same number of random bits for the RSA key size. Generally the largest symmetric keys are about 256 bits - far lower than the key size of even moderately secure RSA key pairs.
Now it completely depends on your requirements on the secure random number how much this will cost. If you require your master keys to be build directly upon (whitened) entropy then this may be a very expensive process if your entropy sources are slow. If you're OK with pseudo random numbers or if you have fast entropy sources, it will probably not be slow.
So it depends on the requirements and the implementation of the underlying RNG. I've seen several instances of Linux completely halt when large amount of data is retrieved from the (blocking)
/dev/random. Usually it is possible to configure use of
/dev/urandom instead. And usually this is as secure.