Editing Burrows–Abadi–Needham logic (section)

== Basic rules ==
The definitions and their implications are below (''P'' and ''Q'' are network agents, ''X'' is a message,
and ''K'' is an [[encryption key]]):
* ''P'' believes ''X'': ''P'' acts as if ''X'' is true, and may assert ''X'' in other messages.
* ''P'' has jurisdiction over ''X'': ''P''{{'}}s beliefs about ''X'' should be trusted.
* ''P'' said ''X'': At one time, ''P'' transmitted (and believed) message ''X'', although ''P'' might no longer believe ''X''.
* ''P'' sees ''X'': ''P'' receives message ''X'', and can read and repeat ''X''.
* {{mset|''X''}}<sub>''K''</sub>: ''X'' is encrypted with key ''K''.
* fresh(''X''): ''X'' has not previously been sent in any message.
* key(''K'', ''P''↔''Q''): ''P'' and ''Q'' may communicate with shared key ''K''

The meaning of these definitions is captured in a series of postulates:
* If ''P'' believes {{nowrap|key(''K'', ''P''↔''Q'')}}, and ''P'' sees {{mset|''X''}}<sub>''K''</sub>, then ''P'' believes (''Q'' said ''X'')
* If ''P'' believes (''Q'' said ''X'') and ''P'' believes fresh(''X''), then ''P'' believes (''Q'' believes ''X'').

''P'' must believe that ''X'' is fresh here.  If ''X'' is not known to be fresh, then it might be an obsolete message, replayed by an attacker.
* If ''P'' believes (''Q'' has jurisdiction over ''X'') and ''P'' believes (''Q'' believes ''X''), then ''P'' believes ''X''
* There are several other technical postulates having to do with composition of messages.  For example, if ''P'' believes that ''Q'' said {{nowrap|⟨''X'', ''Y''⟩}}, the concatenation of ''X'' and ''Y'', then ''P'' also believes that ''Q'' said ''X'', and ''P'' also believes that ''Q'' said ''Y''.

Using this notation, the assumptions behind an authentication protocol
can be formalized.  Using the postulates, one can prove that certain
agents believe that they can communicate using certain keys.  If the
proof fails, the point of failure usually suggests an attack which
compromises the protocol.