CHAP and rewrite components (Q766175)

The author proposes a new feature to an authentication system CHAP used in the point-to-point data link protocol PPP. It is based on ground term rewriting systems (GTRSs) and, from the mathematical point of view, the paper is mainly about GTRSs. A new kind of complement of GTRSs, the type-based complement, is defined and studied along with some previously introduced related notions. Among other things, the following is shown: if \(A\) is a subsystem of a reduced GTRS \(B\), then \(B- A\) is a type-based complement of \(A\) for \(B\); it is decidable whether a GTRS \(C\) is a type-based complement of a GTRS \(A\) for a given reduced GTRS \(B\); it is decidable whether a given GTRS has a type-based complement and if this is the case, such a complement can be constructed; the ternary relation of a GTRS being a type-based complement of a GTRS for a third GTRS is modular. Finally, the author explains how these results can be used for making CHAP resilient to off-line attacks.