They managed to get a BitLicense (one of very few orgs to do so) which at least somewhat lends to legitimacy. Also pretty easy to find the people involved, and a founding team of infosec people is a pretty decent means to start an exchange.
https://bittrex.com/home/abouthttps://en.wikipedia.org/wiki/BitLicense