The growth of distributed Internet-of-Things (IoT) systems has increased the requirement of secure and efficient mutual authentication mechanisms to safeguard resource-constrained devices from a wide array of cyber threats. We present in this paper, a mutual authentication protocol that is both highly secure and practical to deploy. It is secure against replay attacks, impersonation and man-in-the-middle (MIM) attacks and uses elliptic curve cryptography (ECC), implicit certificates, keyed-hash tokens for mutual authentication, anonymity and session key confidentiality. Security verification of the protocol is formally performed using the AVISPA security tool which results that the implemented multicasting proxy discovery is secure against Dolev–Yao model attacks. Experimental results on TelosB motes show significant benefits in terms of computation time, energy consumption and communication overhead with respect to other state-of-the-art (software and hardware) approaches. The results demonstrate that the technique is a useful and scalable solution to protect large-scale distributed IoT installations.