A vehicle communication system, comprising a plurality of control devices configured to carry out communication with one another, the plurality of control devices comprising a transmitting device at a transmitting side and a receiving device at a receiving side, wherein: the transmitting device and the receiving device each include a memory configured to store an encryption key and predetermined authentication information, and a processor that is coupled to the memory, the processor at the transmitting device is configured to: generate first authentication information based on a message and the encryption key that is stored in the memory of the transmitting device, and in a case in which the encryption key that is stored does not differ from the encryption key that was originally used in order to generate the first authentication information, transmit the generated first authentication information and the message to the receiving device, and in a case in which the encryption key that is stored differs from the encryption key that was originally used in order to generate the first authentication information, transmit the predetermined authentication information and the message to the receiving device, and the processor at the receiving device is configured to: generate second authentication information based on the encryption key stored in the memory of the receiving device and the message received from the transmitting device, collate the first authentication information received from the transmitting device and the generated second authentication information, and authenticate the message, and in a case in which, after starting-up of the receiving device, authentication has not succeeded even once, and the received first authentication information and the predetermined authentication information match, accept the received message regardless of a result of the authentication. the transmitting device and the receiving device each include a memory configured to store an encryption key and predetermined authentication information, and a processor that is coupled to the memory, the processor at the transmitting device is configured to: generate first authentication information based on a message and the encryption key that is stored in the memory of the transmitting device, and in a case in which the encryption key that is stored does not differ from the encryption key that was originally used in order to generate the first authentication information, transmit the generated first authentication information and the message to the receiving device, and in a case in which the encryption key that is stored differs from the encryption key that was originally used in order to generate the first authentication information, transmit the predetermined authentication information and the message to the receiving device, and generate first authentication information based on a message and the encryption key that is stored in the memory of the transmitting device, and in a case in which the encryption key that is stored does not differ from the encryption key that was originally used in order to generate the first authentication information, transmit the generated first authentication information and the message to the receiving device, and in a case in which the encryption key that is stored differs from the encryption key that was originally used in order to generate the first authentication information, transmit the predetermined authentication information and the message to the receiving device, and the processor at the receiving device is configured to: generate second authentication information based on the encryption key stored in the memory of the receiving device and the message received from the transmitting device, collate the first authentication information received from the transmitting device and the generated second authentication information, and authenticate the message, and in a case in which, after starting-up of the receiving device, authentication has not succeeded even once, and the received first authentication information and the predetermined authentication information match, accept the received message regardless of a result of the authentication. generate second authentication information based on the encryption key stored in the memory of the receiving device and the message received from the transmitting device, collate the first authentication information received from the transmitting device and the generated second authentication information, and authenticate the message, and in a case in which, after starting-up of the receiving device, authentication has not succeeded even once, and the received first authentication information and the predetermined authentication information match, accept the received message regardless of a result of the authentication.