Is it possible for a ML model to perform worse than random classification?
Yes, it's possible.

Just means the model is adjusting to noise, so it's valuing the "wrong" features. 

As an analogy, if you were randomly guessing basketball game outcomes, you'd probably perform better than someone who thinks less points is better and is guessing based on previous games' scores