On every startup of an application, a random message of 128bits should be created such that the message has not been chosen before with maximum probability and this should also be secure (i.e. cannot be broken by some hacks). For example using a standard random generator with a seed taken from the system time is not secure because it can be broken by freezing the system time somehow (is this possible anyhow?).
The Windows function CryptGenRandom seems to be appropriate for this. But is there a portable alternative? If not, are there corresponding functions for Linux and Mac?
The Windows function CryptGenRandom seems to be appropriate for this. But is there a portable alternative?
That depends on how you look at it; I'm not sure if there is a standalone wrapper that can wrap directly around platform RNG's. But most crypto libraries will have a random generator that directly references or - more likely - seeds itself from the OS random number generator.
For instance, read about the AutoSeeded generators of Crypto++ here. These libraries abstract from the functionality offered by the OS, giving you a portable option that keeps the calls to the underlying platform to a minimum (i.e. they are both secure and fast).
If not, are there corresponding functions for Linux and Mac?
To use a cryptographic random directly then use /dev/urandom. Generally there is no reason to use /dev/random which may block. I would recommend using a well vetted library though.
Especially if you are using an embedded or virtualized device & OS it pays to make sure that the OS random number generator is random enough. For virtualized systems it is often a good idea to make sure the VM extensions are installed for the OS, for instance.
Additional seed may be added to the random number generator as well, so if you have anything that looks random to you it might be wise to add it as seed if you're not sure about the strength of the random numbers.
Having a CPU with RNG extensions (that are used by the OS or library) such as Intel RD_RAND may make sense as well of course.