We present a connection establishment protocol with integrated authentication, suited for Massive Machine-Type Communications (mMTC). The protocol is contention-based and its main feature is that a device contends with a unique signature that also enables the authentication of the device towards the network. The signatures are inspired by Bloom filters and are created based on the output of the MILENAGE authentication and encryption algorithm set, which is used in the authentication and security procedures in the LTE protocol family. We show that our method utilizes the system resources more efficiently, achieves lower latency of connection establishment for Poisson arrivals and allows a $87\%$ signalling overhead reduction. An important conclusion is that the mMTC traffic benefits profoundly from integration of security features into the connection establishment/access protocols, instead of addressing them post-hoc, which has been a common practice.