Logistic regression program does not give statistically correct result
If you initialized the weights randomly and predicted immediately, you should probably expect 1/num_classes accuracy. 

But you are training first. The data may be random, but it is still possible to overfit it. With a sample that small and wide, you could imagine some degree of separability of the classes by chance. In that scenario, your network can learn weights that are better than random (far from perfect in only one iteration).

The effect would likely be lessened by using much more data or holding out/using new random data to test accuracy.