Is C# Random Number Generator thread safe?

No, using the same instance from multiple threads can cause it to break and return all 0's. However, creating a thread-safe version (without needing nasty locks on every call to Next()) is simple. Adapted from the idea in this article:

public class ThreadSafeRandom
{
    private static readonly Random _global = new Random();
    [ThreadStatic] private static Random _local;

    public int Next()
    {
        if (_local == null)
        {
            lock (_global)
            {
                if (_local == null)
                {
                    int seed = _global.Next();
                    _local = new Random(seed);
                }
            }
        }

        return _local.Next();
    }
}

The idea is to keep a separate static Random variable for each thread. Doing that in the obvious way fails, however, because of another issue with Random - if multiple instances are created at nearly the same time (within about 15ms), they will all return the same values! To fix this, we create a globally-static Random instance to generate the seeds used by each thread.

The above article, by the way, has code demonstrating both of these issues with Random.

There's nothing special done in the Next method to achieve thread safety. However, it's an instance method. If you don't share instances of Random across different threads, you don't have to worry about state corruption within an instance. Do not use a single instance of Random across different threads without holding an exclusive lock of some sort.

Jon Skeet has a couple nice posts on this subject:

StaticRandom
Revisiting randomness

As noted by some commentators, there is another potential problem in using different instances of Random that are thread-exclusive, but are seeded identically, and therefore induce the identical sequences of pseudorandom numbers, because they may be created at the same time or within close temporal proximity of each other. One way to alleviate that issue is to use a master Random instance (which is locked by a single thread) to generate some random seeds and initialize new Random instances for every other thread to use.

The offical answer from Microsoft is a very strong no. From http://msdn.microsoft.com/en-us/library/system.random.aspx#8:

Random objects are not thread safe. If your app calls Random methods from multiple threads, you must use a synchronization object to ensure that only one thread can access the random number generator at a time. If you don't ensure that the Random object is accessed in a thread-safe way, calls to methods that return random numbers return 0.

As described in the docs, there is a very nasty side effect that can happen when the same Random object is used by multiple threads: it just stops working.

(i.e. there is a race condition which when triggered, the return value from the 'random.Next....' methods will be 0 for all subsequent calls.)