An Improved Binary Authentication Tree Algorithm for Vehicular Networks

Vehicular networks are gaining popularity because vehicular communications are able to help minimize accidents, improve traffic conditions, etc. To avoid malicious attacks and potential abuse, employing digital signatures is widely recognized as the most efficient approach for vehicular networks. However, when the number of signatures received by a roadside unit (RSU) becomes large, a scalability problem emerges immediately: it can be difficult for the RSU to sequentially verify every received signature within 100-300ms as required by the current Dedicated Short Range Communications (DSRC) broadcast protocol. Jiang et al. proposed a robust and efficient signature scheme for vehicular-to-infrastructure communications, called binary authentication tree. In this paper, we show that their binary authentication algorithm is insecure to at least two attacks. The first attack shows that the original binary authentication algorithm is universally forgeable under chosen-message attacks, i.e., the attacker can forge other vehicles´ authentication on any message under chosen-message attack. The second attack shows that the original binary authentication algorithm is universally forgeable, i.e., the attacker can forge other vehicles´ authentication on any message at will. Although Jiang et al.´s scheme is insecure, it can be repaired. Using the binary authentication tree model, we repair their scheme in order to make it provably secure and efficient.