You make it sound a bit too easy “just add some random colours”. But there are theoretical hardness results from the 90s on learning NN. It is so-called inherently unpredictable. These hardness results became a bit obsolete by big data. I believe that what we see happening with adversarial inputs is a shadow of such hardness results.