How to evaluate data capability to train a model?
1.2M is about 2^16.
You have 512 features plus the concept so the number of possibilities is much larger.
Therefore, you can claim that the number of samples you have is too small.

Though that, machine learning is done almost always in a situation that you have less samples the all permutations.

The VC dimension allow estimate how well a data set fits the underlying distribution. It applies to an hypothesis class (e.g., linear functions) whose size is typically much smaller than the number of permutations.

Note that both the number of permutations and the VC dimension refer to worse case scenarios. It is possible that on of the 512 is identical to the concept. In this case you will be able to learn though the other 511 features.