[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / BAN
[Index] [Contents] [Source Text] [About] [Notation] [Copyright] [Comment/Contact] [Search ]
Tue Sep 18 15:25:04 PDT 2007

Contents


    The BAN Logic of Authentication

      Introduction

      The BAN logic [BurrowsAbadiNeedham89] [BurrowsAbadiNeedham90] is a formal Logic used to reason about beliefs, encryption, and protocols. It is simple and has been used in several successful projects, It is a logic of who believes what about whom.

      For more see Timo Kyntaja's page: [ ban.html ] , or Annette Bleeker and Lambert Meertens's [ http://dimacs.rutgers.edu/Workshops/Security/program2/bleeker/ ] paper on supplying a semantic model to the BAN logic. More web pages and Usenet discussions can be found easily on Google.

      Formal System

      1. BAN::=following,
        Net
          Note BAN is not built on top of the normal propositional calculus. In the MATHS system formulae can be defined and reasoned with anyway by introducing the syntax and inference rules.

          The syntax shows both the long hand (readable) syntax and the shorthand (writable) mathematical symbols.

          I (dick) have taken a few liberties in formalizing the logic such as separating messages from beliefs after some experiences with a partial implementation [ BAN.plg ] in Prolog.

          Elements

        1. Participant::Sets, people and systems sending messages and entertaining beliefs.
        2. Message::Sets, things that are sent and perhaps believed by participants.
        3. Belief::Sets, things that can be believed but are not always transmitable.
        4. |- (mb): Message==>Belief.

        5. Key::@(Message), a special message that is used to encrypt and decrypt messages..
        6. (mb)|- (kb): Key ==> Belief.
        7. encrypt::Message><Key->Message.
          encrypt(X,K)=message X was encrypted by key K and sent by some one else. {X}[K]::=encrypt(X,K).
        8. Public_Key::@(Key).
        9. Private_Key::@(Key).
        10. For K:Public_Key, /K ::Private_Key.
        11. (dick)|- (Public_private_keys): For K:Public_key, {{X}[/K]}[K] = X.

        12. nonce::Message=Number used ONCE.
        13. A nonce is a one time number used to identify a message. They can be sequence numbers or random numbers.


          Messages can be concatenated with + to give a new message, The order in which this is done does not matter.

        14. |- (concatenation): Abelian_semigroup(Message, (+)).

          In the original papers concatenation is shown by a comma: {X,Y,Z,...}[K] ::Message= {X + Y + Z ... }[K]

        15. For A,B,C:Participant.
        16. For X,Y,Z:Message.
        17. For K,K1,K2:Key.

          Syntax

        18. believes::infix(Participant, Belief, Belief).
          A believes X=A is entitled to believe X.
        19. A|≡ X::= A believes X.

        20. said::infix(Participant, Message, Belief).
        21. A said K::=once upon a time, A used key K.
        22. A said X::=once upon a time, A said X.
        23. A|~X::=A said X.

        24. controls::infix(Participant, Message, Belief).
          A controls X=A is an authority on X and can be trusted on X.
        25. A |=> X::= A controls X.

        26. sees::infix(Participant, Message, Belief).
          A sees X=Someone has sent a message to A containing X so that he can read X and repeat it. Implicitly in this: the message X is not sent to A by A itself!
        27. A \triangleleft X::= A sees X.

        28. fresh::Message -> Belief.
          fresh(X)=X has not been sent in a previous run of the protocol, Typically X contains time-stamp-like info identifying it as current from a relevant source. Many attacks use previously recorded messages to full the recipient into believing them. Freshness means that the information transmitted identifies itself as being current.
        29. \sharp::=fresh.

        30. share(K)::infix(Participant, Message, Belief).
          A share(K) B =A and B can use Key K to communicate. The key is known and used by A and B but nobody else will discover it and use it.
        31. Shorthand form is a two-way double arrow with K on top.

        32. has_public_key::infix(Participant, Key, Belief).
          B has_public_key K=B has a published public key K and has a private key /K. So B sends messages encrypted by /K but others use K to decrypt them.
        33. Shorthand: An arrow with a vertical tail with K over it.

        34. secret(K)::infix(Participant, Message, Belief).
          A secret(K) B=X is a secret known only to A, B and possibly some trusted associates.
        35. Shorthand: looks like a chemical two way reaction -- two opposed harpoons with K over the top.

        36. combine::Message><Message->Message. <X>[Y]::Message=message X combined with Y so that Y is a secret and identifies whoever sends the combined message.

          Inference Rules


        37. |- (message_meaning): If A believes(A share(K) B) and A sees {X}[K] then A believes(B said X).
        38. |- (public_key_message_meaning): If A believes(B has_public_key K) and A sees {X}[/K] then A believes(B said X).
        39. |- (secret_message_meaning): If A believes(A secret(K) B) and A sees <X>[K] then A believes(B said X).


        40. |- (nonce_verification): If A believes(fresh X) and A believes(B said X) then B believes X.
        41. |- (jurisdiction): If A believes(B controls X) and A believes (B believes X) then A believes X.


        42. |- (components_1): If A sees (X + Y ) then ((A sees X) and (A sees Y)).
        43. |- (components_2): If A believes (A share(K) B) and A sees {X}[K] then (A sees X).
        44. |- (components_3): If A sees <X>[Y] then (A sees X).
        45. |- (components_4): If A believes (B has_public_key K) and A sees {X}[/K] then (A sees X).


        46. |- (freshness_is_contagious): If A believes fresh(X) then A believes fresh(X + Y).


        47. |- (+out1): If A believes(X + Y) then (A believes X).
        48. |- (+out2): If A believes(X + Y) then (A believes Y).


        49. (dick)|- (+in): If A believes X and A believes Y then A believes (X + Y).


        50. (Anderson99)|- (key_meaning): If A believes(A share(K) B) and A sees {X}[K] then A believes(B said K).


        (End of Net BAN)

      . . . . . . . . . ( end of section Formal System) <<Contents | End>>

      Protocols

      Syntax
    1. protocol::=#message.
    2. message::=participant "->" participant ":" data eoln.

      References, Sources, and Links

      1. Abelian_semigroup::= See http://csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html#abelian_semigroup.
      2. Anderson99::=following,
        • Ross J Anderson
        • The Formal Verification of a Payment System
        • In HincheyBowen99 pp43-52

      3. BurrowsAbadiNeedham89::=following,
        • M Burrows & M Abadi & R M Needham
        • A Logic of Authentication
        • Proc Royal Society of London A V426(1989)pp233-271
        • Ref In [Anderson99]

      4. BurrowsAbadiNeedham90::=following,
        • Michael Burrows & Martin Abadi & Roger M Needham
        • A Logic of Authentication
        • ACM Transactions on Computer Systems V8n1(Feb 1990)pp18-36 [ 77648.77649 ]
      5. dick::=Assertions I've added to the original presentation.
      6. infix::=A symbol or operator placed between two formulae to make another one. For Sets A,B,C, infix(A,B,C)= A><B->C.
      7. MATHS::= See http://csci.csusb.edu/dick/maths.

      . . . . . . . . . ( end of section References, Sources, and Links) <<Contents | End>>

    . . . . . . . . . ( end of section The BAN Logic of Authentication) <<Contents | End>>

End