RFID is one of the most promising identification schemes in the field of pervasive systems. Due to wireless channel incorporation, security issues arise and to make the system reliable and secure, numerous UMAPs have been proposed which involve only simple bitwise logical operations in their designs. However, almost all of the previously proposed UMAPs are reported to be vulnerable against various security attacks. We propose a new pseudo-Kasami code based Mutual Authentication Protocol which avoids unbalanced logical operations and introduces a new Ultra lightweight primitive: pseudo-Kasami code. This enhances the diffusion properties of the protocol messages and makes hamming weight of the secrets unpredictable and irreversible. The performance evaluation shows that the KMAP requires fewer resources on the tag in terms of on-chip memory, communication cost and computational operations which makes it a more feasible protocol.