CHAP and rewrite components
type: Item
instance of: scholarly article
title: CHAP and rewrite components
zbMATH Open document ID: 1244.68011
author: Sándor Vágvölgyi
published in: Acta Informatica
publication date: 2012-03-23T00:00:00Z
review text: 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.
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68M12
Mathematics Subject Classification ID: 94A62
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 6018095
zbMATH Keywords: network protocols
zbMATH Keywords: authentication schemes
zbMATH Keywords: CHAP
zbMATH Keywords: PPP
zbMATH Keywords: ground term rewriting systems
zbMATH Keywords: rewrite complements
zbMATH Keywords: type-based complements
zbMATH Keywords: modular properties
zbMATH Keywords: tree automata
MaRDI profile type: Publication
full work available at URL: s00236-011-0141-z
OpenAlex ID: W1976431594
cites work: Term Rewriting and All That
cites work: Tree generating regular systems
cites work: Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
cites work: Derivation trees of ground term rewriting systems.
cites work: Reductions in tree replacement systems
cites work: Q3485880
cites work: A fast algorithm for generating reduced ground rewriting systems from a set of ground equations
cites work: Q4799892
cites work: A fast algorithm for constructing a tree automaton recognizing a congruential tree language
cites work: Congruential complements of ground term rewrite systems
cites work: How to Break MD5 and Other Hash Functions
DOI: 10.1007/S00236-011-0141-Z
description: scientific article; zbMATH DE number 6018095