464 \begin{isamarkuptext}% |
464 \begin{isamarkuptext}% |
465 The system's behaviour is formalized as a set of traces of |
465 The system's behaviour is formalized as a set of traces of |
466 \emph{events}. The most important event, \isa{Says\ A\ B\ X}, expresses |
466 \emph{events}. The most important event, \isa{Says\ A\ B\ X}, expresses |
467 $A\to B : X$, which is the attempt by~$A$ to send~$B$ the message~$X$. |
467 $A\to B : X$, which is the attempt by~$A$ to send~$B$ the message~$X$. |
468 A trace is simply a list, constructed in reverse |
468 A trace is simply a list, constructed in reverse |
469 using~\isa{{\isacharhash}}. Other event types include reception of messages (when |
469 using~\isa{{\isaliteral{23}{\isacharhash}}}. Other event types include reception of messages (when |
470 we want to make it explicit) and an agent's storing a fact. |
470 we want to make it explicit) and an agent's storing a fact. |
471 |
471 |
472 Sometimes the protocol requires an agent to generate a new nonce. The |
472 Sometimes the protocol requires an agent to generate a new nonce. The |
473 probability that a 20-byte random number has appeared before is effectively |
473 probability that a 20-byte random number has appeared before is effectively |
474 zero. To formalize this important property, the set \isa{used\ evs} |
474 zero. To formalize this important property, the set \isa{used\ evs} |
475 denotes the set of all items mentioned in the trace~\isa{evs}. |
475 denotes the set of all items mentioned in the trace~\isa{evs}. |
476 The function \isa{used} has a straightforward |
476 The function \isa{used} has a straightforward |
477 recursive definition. Here is the case for \isa{Says} event: |
477 recursive definition. Here is the case for \isa{Says} event: |
478 \begin{isabelle}% |
478 \begin{isabelle}% |
479 \ \ \ \ \ used\ {\isacharparenleft}Says\ A\ B\ X\ {\isacharhash}\ evs{\isacharparenright}\ {\isacharequal}\ parts\ {\isacharbraceleft}X{\isacharbraceright}\ {\isasymunion}\ used\ evs% |
479 \ \ \ \ \ used\ {\isaliteral{28}{\isacharparenleft}}Says\ A\ B\ X\ {\isaliteral{23}{\isacharhash}}\ evs{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ parts\ {\isaliteral{7B}{\isacharbraceleft}}X{\isaliteral{7D}{\isacharbraceright}}\ {\isaliteral{5C3C756E696F6E3E}{\isasymunion}}\ used\ evs% |
480 \end{isabelle} |
480 \end{isabelle} |
481 |
481 |
482 The function \isa{knows} formalizes an agent's knowledge. Mostly we only |
482 The function \isa{knows} formalizes an agent's knowledge. Mostly we only |
483 care about the spy's knowledge, and \isa{knows\ Spy\ evs} is the set of items |
483 care about the spy's knowledge, and \isa{knows\ Spy\ evs} is the set of items |
484 available to the spy in the trace~\isa{evs}. Already in the empty trace, |
484 available to the spy in the trace~\isa{evs}. Already in the empty trace, |
485 the spy starts with some secrets at his disposal, such as the private keys |
485 the spy starts with some secrets at his disposal, such as the private keys |
486 of compromised users. After each \isa{Says} event, the spy learns the |
486 of compromised users. After each \isa{Says} event, the spy learns the |
487 message that was sent: |
487 message that was sent: |
488 \begin{isabelle}% |
488 \begin{isabelle}% |
489 \ \ \ \ \ knows\ Spy\ {\isacharparenleft}Says\ A\ B\ X\ {\isacharhash}\ evs{\isacharparenright}\ {\isacharequal}\ insert\ X\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}% |
489 \ \ \ \ \ knows\ Spy\ {\isaliteral{28}{\isacharparenleft}}Says\ A\ B\ X\ {\isaliteral{23}{\isacharhash}}\ evs{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ insert\ X\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}% |
490 \end{isabelle} |
490 \end{isabelle} |
491 Combinations of functions express other important |
491 Combinations of functions express other important |
492 sets of messages derived from~\isa{evs}: |
492 sets of messages derived from~\isa{evs}: |
493 \begin{itemize} |
493 \begin{itemize} |
494 \item \isa{analz\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}} is everything that the spy could |
494 \item \isa{analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}} is everything that the spy could |
495 learn by decryption |
495 learn by decryption |
496 \item \isa{synth\ {\isacharparenleft}analz\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}{\isacharparenright}} is everything that the spy |
496 \item \isa{synth\ {\isaliteral{28}{\isacharparenleft}}analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}} is everything that the spy |
497 could generate |
497 could generate |
498 \end{itemize}% |
498 \end{itemize}% |
499 \end{isamarkuptext}% |
499 \end{isamarkuptext}% |
500 \isamarkuptrue% |
500 \isamarkuptrue% |
501 % |
501 % |