Byzantine Failures and Security: Arbitrary is not (always) Random

Abstract

The Byzantine failure model allows arbitrary behavior of a certain fraction of network nodes in a distributed system. It was introduced to model and analyze the effects of very severe hardware faults in aircraft control systems. Lately, the Byzantine failure model has been used in the area of network security where Byzantine-tolerance is equated with resilience against malicious attackers. We discuss two reasons why one should be careful in doing so. Firstly, Byzantine-tolerance is not concerned with secrecy and so special means have to be employed if secrecy is a desired system property. Secondly, in contrast to the domain of hardware faults, in a security setting it is difficult to compute the assumption coverage of the Byzantine failure model, i.e., the probability that the failure assumption holds in practice. To address this latter point we develop a methodology which allows to estimate the reliability of a Byzantine-tolerant solution exposed to attackers of different strengths.