Detection of Wrongly Directed Messages by Efficient Fault-Tolerance Signatures

摘要

When a message is wrongly directed due to a technical fault, it causes the receiver to assume that its sender was some node y instead of the true sender x, if the error remains undetected. To prevent from this kind of confusion the sender adds a digital signature to the message, which is checked by the receiver. The signature is called fault-tolerance signature since it needs to withstand technical faults, not intelligent human attacks. This paper presents a signature technique that requires just a minor computational overhead. Moreover, the signature is combined with the CRC of the message in a way that it needs only 2, only 1, or even no extra bit, depending on the variant of the technique. The socalled odd multiplication is introduced as a double-sided bijective mapping that allows signature generation by just one multiplication and a few one-cycle instructions. A signature generated with any wrong key, or generated by misusing a signature test key is guaranteed to be detected (100% coverage). The coverage of bit flips or bursts by the combination of CRC and signature is quantified by extensive simulation for various message parameters. Compared to a pure CRC the coverage of a fault-tolerance signature is somewhat worse (as expected), but does not differ much.