TPTP Problem File: SWV791_5.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : SWV791_5 : TPTP v8.2.0. Released v6.0.0.
% Domain : Software Verification
% Problem : Needham-Schroeder shared-key protocol line 438
% Version : Especial.
% English :
% Refs : [BN10] Boehme & Nipkow (2010), Sledgehammer: Judgement Day
% : [Bla13] Blanchette (2011), Email to Geoff Sutcliffe
% Source : [Bla13]
% Names : ns_438 [Bla13]
% Status : Unknown
% Rating : 1.00 v6.4.0
% Syntax : Number of formulae : 165 ( 37 unt; 48 typ; 0 def)
% Number of atoms : 259 ( 122 equ)
% Maximal formula atoms : 7 ( 1 avg)
% Number of connectives : 184 ( 42 ~; 12 |; 20 &)
% ( 34 <=>; 76 =>; 0 <=; 0 <~>)
% Maximal formula depth : 17 ( 5 avg)
% Maximal term depth : 9 ( 2 avg)
% Number of types : 6 ( 5 usr)
% Number of type conns : 36 ( 23 >; 13 *; 0 +; 0 <<)
% Number of predicates : 4 ( 3 usr; 0 prp; 1-3 aty)
% Number of functors : 40 ( 40 usr; 18 con; 0-5 aty)
% Number of variables : 372 ( 351 !; 5 ?; 372 :)
% ( 16 !>; 0 ?*; 0 @-; 0 @+)
% SPC : TF1_UNK_EQU_NAR
% Comments : This file was generated by Isabelle (most likely Sledgehammer)
% 2011-12-13 16:26:48
%------------------------------------------------------------------------------
%----Should-be-implicit typings (7)
tff(ty_tc_Event_Oevent,type,
event: $tType ).
tff(ty_tc_HOL_Obool,type,
bool: $tType ).
tff(ty_tc_List_Olist,type,
list: $tType > $tType ).
tff(ty_tc_Message_Oagent,type,
agent1: $tType ).
tff(ty_tc_Message_Omsg,type,
msg: $tType ).
tff(ty_tc_Nat_Onat,type,
nat: $tType ).
tff(ty_tc_fun,type,
fun: ( $tType * $tType ) > $tType ).
%----Explicit typings (41)
tff(sy_c_COMBB,type,
combb:
!>[B: $tType,C: $tType,A: $tType] : ( ( fun(B,C) * fun(A,B) ) > fun(A,C) ) ).
tff(sy_c_COMBC,type,
combc:
!>[A: $tType,B: $tType,C: $tType] : ( ( fun(A,fun(B,C)) * B ) > fun(A,C) ) ).
tff(sy_c_Event_Obad,type,
bad: fun(agent1,bool) ).
tff(sy_c_Event_Oevent_OSays,type,
says: ( agent1 * agent1 * msg ) > event ).
tff(sy_c_Event_Oknows,type,
knows: ( agent1 * list(event) ) > fun(msg,bool) ).
tff(sy_c_List_Oappend,type,
append:
!>[A: $tType] : ( ( list(A) * list(A) ) > list(A) ) ).
tff(sy_c_List_Olist_OCons,type,
cons:
!>[A: $tType] : ( ( A * list(A) ) > list(A) ) ).
tff(sy_c_List_Olist_ONil,type,
nil:
!>[A: $tType] : list(A) ).
tff(sy_c_List_Orev,type,
rev:
!>[A: $tType] : ( list(A) > list(A) ) ).
tff(sy_c_List_Oset,type,
set:
!>[A: $tType] : ( list(A) > fun(A,bool) ) ).
tff(sy_c_List_OtakeWhile,type,
takeWhile:
!>[A: $tType] : ( ( fun(A,bool) * list(A) ) > list(A) ) ).
tff(sy_c_Message_Oagent_OServer,type,
server: agent1 ).
tff(sy_c_Message_Oagent_OSpy,type,
spy: agent1 ).
tff(sy_c_Message_Oanalz,type,
analz: fun(msg,bool) > fun(msg,bool) ).
tff(sy_c_Message_Omsg_OAgent,type,
agent: agent1 > msg ).
tff(sy_c_Message_Omsg_OCrypt,type,
crypt: ( nat * msg ) > msg ).
tff(sy_c_Message_Omsg_OKey,type,
key: nat > msg ).
tff(sy_c_Message_Omsg_OMPair,type,
mPair: ( msg * msg ) > msg ).
tff(sy_c_Message_Omsg_ONonce,type,
nonce: nat > msg ).
tff(sy_c_Message_Oparts,type,
parts: fun(msg,bool) > fun(msg,bool) ).
tff(sy_c_NS__Shared__Mirabelle__iywubrjwsc_Ons__shared,type,
nS_Sha254967238shared: fun(list(event),bool) ).
tff(sy_c_NS__Shared__Mirabelle__iywubrjwsc_Ons__sharedp,type,
nS_Sha993195050haredp: list(event) > $o ).
tff(sy_c_Public_OshrK,type,
shrK: agent1 > nat ).
tff(sy_c_aa,type,
aa1:
!>[A: $tType,B: $tType] : ( ( fun(A,B) * A ) > B ) ).
tff(sy_c_fFalse,type,
fFalse: bool ).
tff(sy_c_fNot,type,
fNot: fun(bool,bool) ).
tff(sy_c_fTrue,type,
fTrue: bool ).
tff(sy_c_fequal,type,
fequal:
!>[A: $tType] : fun(A,fun(A,bool)) ).
tff(sy_c_member,type,
member:
!>[A: $tType] : ( ( A * fun(A,bool) ) > $o ) ).
tff(sy_c_pp,type,
pp: bool > $o ).
tff(sy_v_A,type,
a: agent1 ).
tff(sy_v_Aa,type,
aa: agent1 ).
tff(sy_v_B,type,
b: agent1 ).
tff(sy_v_Ba,type,
ba: agent1 ).
tff(sy_v_K,type,
k: nat ).
tff(sy_v_Ka,type,
ka: nat ).
tff(sy_v_NA,type,
na: nat ).
tff(sy_v_Nb,type,
nb: nat ).
tff(sy_v_S,type,
s: agent1 ).
tff(sy_v_X,type,
x: msg ).
tff(sy_v_evs3,type,
evs3: list(event) ).
%----Relevant facts (100)
tff(fact_0_ns__shared_ONil,axiom,
member(list(event),nil(event),nS_Sha254967238shared) ).
tff(fact_1_spies__evs__rev,axiom,
! [Evsa: list(event)] : knows(spy,Evsa) = knows(spy,rev(event,Evsa)) ).
tff(fact_2_B__trusts__NS5__lemma,axiom,
! [NB: nat,NA: msg,Aa: agent1,Ka: nat,Evsa: list(event),Ba: agent1] :
( ~ member(agent1,Ba,bad)
=> ( member(list(event),Evsa,nS_Sha254967238shared)
=> ( ~ member(msg,key(Ka),analz(knows(spy,Evsa)))
=> ( member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),crypt(shrK(Ba),mPair(key(Ka),agent(Aa)))))))),set(event,Evsa))
=> ( member(msg,crypt(Ka,mPair(nonce(NB),nonce(NB))),parts(knows(spy,Evsa)))
=> member(event,says(Aa,Ba,crypt(Ka,mPair(nonce(NB),nonce(NB)))),set(event,Evsa)) ) ) ) ) ) ).
tff(fact_3_Spy__analz__shrK,axiom,
! [Aa: agent1,Evsa: list(event)] :
( member(list(event),Evsa,nS_Sha254967238shared)
=> ( member(msg,key(shrK(Aa)),analz(knows(spy,Evsa)))
<=> member(agent1,Aa,bad) ) ) ).
tff(fact_4_Spy__see__shrK,axiom,
! [Aa: agent1,Evsa: list(event)] :
( member(list(event),Evsa,nS_Sha254967238shared)
=> ( member(msg,key(shrK(Aa)),parts(knows(spy,Evsa)))
<=> member(agent1,Aa,bad) ) ) ).
tff(fact_5_ns__shared_ONS3,axiom,
! [X1: msg,Ka: nat,Ba: agent1,NA: nat,S: agent1,Aa: agent1,Evs3: list(event)] :
( member(list(event),Evs3,nS_Sha254967238shared)
=> ( ( Aa != server )
=> ( member(event,says(S,Aa,crypt(shrK(Aa),mPair(nonce(NA),mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evs3))
=> ( member(event,says(Aa,server,mPair(agent(Aa),mPair(agent(Ba),nonce(NA)))),set(event,Evs3))
=> member(list(event),cons(event,says(Aa,Ba,X1),Evs3),nS_Sha254967238shared) ) ) ) ) ).
tff(fact_6_A__trusts__NS4__lemma,axiom,
! [NB: nat,X1: msg,Ba: agent1,NA: msg,Aa: agent1,Ka: nat,Evsa: list(event)] :
( member(list(event),Evsa,nS_Sha254967238shared)
=> ( ~ member(msg,key(Ka),analz(knows(spy,Evsa)))
=> ( member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evsa))
=> ( member(msg,crypt(Ka,nonce(NB)),parts(knows(spy,Evsa)))
=> member(event,says(Ba,Aa,crypt(Ka,nonce(NB))),set(event,Evsa)) ) ) ) ) ).
tff(fact_7_A__trusts__NS2,axiom,
! [Evsa: list(event),X1: msg,Ka: nat,Ba: agent1,NA: msg,Aa: agent1] :
( member(msg,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),X1)))),parts(knows(spy,Evsa)))
=> ( ~ member(agent1,Aa,bad)
=> ( member(list(event),Evsa,nS_Sha254967238shared)
=> member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evsa)) ) ) ) ).
tff(fact_8_Oops__parts__spies,axiom,
! [Evsa: list(event),X1: msg,Ka: msg,Ba: msg,NA: msg,Aa: agent1] :
( member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(Ba,mPair(Ka,X1))))),set(event,Evsa))
=> member(msg,Ka,parts(knows(spy,Evsa))) ) ).
tff(fact_9_unique__session__keys,axiom,
! [X6: msg,B1: agent1,NA2: msg,A5: agent1,Evsa: list(event),X1: msg,Ka: nat,Ba: agent1,NA: msg,Aa: agent1] :
( member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evsa))
=> ( member(event,says(server,A5,crypt(shrK(A5),mPair(NA2,mPair(agent(B1),mPair(key(Ka),X6))))),set(event,Evsa))
=> ( member(list(event),Evsa,nS_Sha254967238shared)
=> ( ( Aa = A5 )
& ( NA = NA2 )
& ( Ba = B1 )
& ( X1 = X6 ) ) ) ) ) ).
tff(fact_10_NS3__msg__in__parts__spies,axiom,
! [Evsa: list(event),X1: msg,Ka: msg,Ba: msg,N: msg,KA: nat,Aa: agent1,S: agent1] :
( member(event,says(S,Aa,crypt(KA,mPair(N,mPair(Ba,mPair(Ka,X1))))),set(event,Evsa))
=> member(msg,X1,parts(knows(spy,Evsa))) ) ).
tff(fact_11_NS4__implies__NS3,axiom,
! [NB: nat,X1: msg,Ba: agent1,NA: msg,Aa: agent1,Ka: nat,Evsa: list(event)] :
( member(list(event),Evsa,nS_Sha254967238shared)
=> ( ~ member(msg,key(Ka),analz(knows(spy,Evsa)))
=> ( member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA,mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evsa))
=> ( member(msg,crypt(Ka,nonce(NB)),parts(knows(spy,Evsa)))
=> ? [A4: agent1] : member(event,says(A4,Ba,X1),set(event,Evsa)) ) ) ) ) ).
tff(fact_12_B__trusts__NS3,axiom,
! [Evsa: list(event),Aa: agent1,Ka: nat,Ba: agent1] :
( member(msg,crypt(shrK(Ba),mPair(key(Ka),agent(Aa))),parts(knows(spy,Evsa)))
=> ( ~ member(agent1,Ba,bad)
=> ( member(list(event),Evsa,nS_Sha254967238shared)
=> ? [NA1: msg] : member(event,says(server,Aa,crypt(shrK(Aa),mPair(NA1,mPair(agent(Ba),mPair(key(Ka),crypt(shrK(Ba),mPair(key(Ka),agent(Aa)))))))),set(event,Evsa)) ) ) ) ).
tff(fact_13_Spy__spies__bad__shrK,axiom,
! [Evsa: list(event),Aa: agent1] :
( member(agent1,Aa,bad)
=> member(msg,key(shrK(Aa)),knows(spy,Evsa)) ) ).
tff(fact_14_rev_Osimps_I2_J,axiom,
! [A: $tType,Xs1: list(A),X: A] : rev(A,cons(A,X,Xs1)) = append(A,rev(A,Xs1),cons(A,X,nil(A))) ).
tff(fact_15_rev__eq__Cons__iff,axiom,
! [A: $tType,Ys: list(A),Y2: A,Xs: list(A)] :
( ( rev(A,Xs) = cons(A,Y2,Ys) )
<=> ( Xs = append(A,rev(A,Ys),cons(A,Y2,nil(A))) ) ) ).
tff(fact_16_shrK__in__knows,axiom,
! [Evsa: list(event),Aa: agent1] : member(msg,key(shrK(Aa)),knows(Aa,Evsa)) ).
tff(fact_17_takeWhile_Osimps_I2_J,axiom,
! [A: $tType,Xs: list(A),X3: A,P1: fun(A,bool)] :
( ( pp(aa1(A,bool,P1,X3))
=> ( takeWhile(A,P1,cons(A,X3,Xs)) = cons(A,X3,takeWhile(A,P1,Xs)) ) )
& ( ~ pp(aa1(A,bool,P1,X3))
=> ( takeWhile(A,P1,cons(A,X3,Xs)) = nil(A) ) ) ) ).
tff(fact_18_rev__singleton__conv,axiom,
! [A: $tType,X3: A,Xs: list(A)] :
( ( rev(A,Xs) = cons(A,X3,nil(A)) )
<=> ( Xs = cons(A,X3,nil(A)) ) ) ).
tff(fact_19_singleton__rev__conv,axiom,
! [A: $tType,Xs: list(A),X3: A] :
( ( cons(A,X3,nil(A)) = rev(A,Xs) )
<=> ( Xs = cons(A,X3,nil(A)) ) ) ).
tff(fact_20_append1__eq__conv,axiom,
! [A: $tType,Y2: A,Ys: list(A),X3: A,Xs: list(A)] :
( ( append(A,Xs,cons(A,X3,nil(A))) = append(A,Ys,cons(A,Y2,nil(A))) )
<=> ( ( Xs = Ys )
& ( X3 = Y2 ) ) ) ).
tff(fact_21_Crypt__Spy__analz__bad,axiom,
! [Evsa: list(event),X1: msg,Aa: agent1] :
( member(msg,crypt(shrK(Aa),X1),analz(knows(spy,Evsa)))
=> ( member(agent1,Aa,bad)
=> member(msg,X1,analz(knows(spy,Evsa))) ) ) ).
tff(fact_22_Spy__in__bad,axiom,
member(agent1,spy,bad) ).
tff(fact_23_list_Oinject,axiom,
! [A: $tType,List2: list(A),A3: A,List1: list(A),A2: A] :
( ( cons(A,A2,List1) = cons(A,A3,List2) )
<=> ( ( A2 = A3 )
& ( List1 = List2 ) ) ) ).
tff(fact_24_append__same__eq,axiom,
! [A: $tType,Zs: list(A),Xs: list(A),Ys: list(A)] :
( ( append(A,Ys,Xs) = append(A,Zs,Xs) )
<=> ( Ys = Zs ) ) ).
tff(fact_25_same__append__eq,axiom,
! [A: $tType,Zs: list(A),Ys: list(A),Xs: list(A)] :
( ( append(A,Xs,Ys) = append(A,Xs,Zs) )
<=> ( Ys = Zs ) ) ).
tff(fact_26_append__assoc,axiom,
! [A: $tType,Zs1: list(A),Ys2: list(A),Xs1: list(A)] : append(A,append(A,Xs1,Ys2),Zs1) = append(A,Xs1,append(A,Ys2,Zs1)) ).
tff(fact_27_event_Osimps_I1_J,axiom,
! [Msg3: msg,Agent21: agent1,Agent12: agent1,Msg: msg,Agent2: agent1,Agent11: agent1] :
( ( says(Agent11,Agent2,Msg) = says(Agent12,Agent21,Msg3) )
<=> ( ( Agent11 = Agent12 )
& ( Agent2 = Agent21 )
& ( Msg = Msg3 ) ) ) ).
tff(fact_28_shrK__injective,axiom,
! [Y2: agent1,X3: agent1] :
( ( shrK(X3) = shrK(Y2) )
<=> ( X3 = Y2 ) ) ).
tff(fact_29_rev__is__rev__conv,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( rev(A,Xs) = rev(A,Ys) )
<=> ( Xs = Ys ) ) ).
tff(fact_30_append__Cons,axiom,
! [A: $tType,Ys2: list(A),Xs1: list(A),X: A] : append(A,cons(A,X,Xs1),Ys2) = cons(A,X,append(A,Xs1,Ys2)) ).
tff(fact_31_append__self__conv2,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( append(A,Xs,Ys) = Ys )
<=> ( Xs = nil(A) ) ) ).
tff(fact_32_append__self__conv,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( append(A,Xs,Ys) = Xs )
<=> ( Ys = nil(A) ) ) ).
tff(fact_33_append__is__Nil__conv,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( append(A,Xs,Ys) = nil(A) )
<=> ( ( Xs = nil(A) )
& ( Ys = nil(A) ) ) ) ).
tff(fact_34_self__append__conv2,axiom,
! [A: $tType,Xs: list(A),Ys: list(A)] :
( ( Ys = append(A,Xs,Ys) )
<=> ( Xs = nil(A) ) ) ).
tff(fact_35_self__append__conv,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( Xs = append(A,Xs,Ys) )
<=> ( Ys = nil(A) ) ) ).
tff(fact_36_Nil__is__append__conv,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( nil(A) = append(A,Xs,Ys) )
<=> ( ( Xs = nil(A) )
& ( Ys = nil(A) ) ) ) ).
tff(fact_37_set__rev,axiom,
! [A: $tType,Xs: list(A)] : set(A,rev(A,Xs)) = set(A,Xs) ).
tff(fact_38_rev__is__Nil__conv,axiom,
! [A: $tType,Xs: list(A)] :
( ( rev(A,Xs) = nil(A) )
<=> ( Xs = nil(A) ) ) ).
tff(fact_39_Nil__is__rev__conv,axiom,
! [A: $tType,Xs: list(A)] :
( ( nil(A) = rev(A,Xs) )
<=> ( Xs = nil(A) ) ) ).
tff(fact_40_rev_Osimps_I1_J,axiom,
! [A: $tType] : rev(A,nil(A)) = nil(A) ).
tff(fact_41_rev__append,axiom,
! [A: $tType,Ys2: list(A),Xs1: list(A)] : rev(A,append(A,Xs1,Ys2)) = append(A,rev(A,Ys2),rev(A,Xs1)) ).
tff(fact_42_takeWhile__eq__all__conv,axiom,
! [A: $tType,Xs: list(A),P1: fun(A,bool)] :
( ( takeWhile(A,P1,Xs) = Xs )
<=> ! [X5: A] :
( member(A,X5,set(A,Xs))
=> pp(aa1(A,bool,P1,X5)) ) ) ).
tff(fact_43_takeWhile_Osimps_I1_J,axiom,
! [A: $tType,P1: fun(A,bool)] : takeWhile(A,P1,nil(A)) = nil(A) ).
tff(fact_44_not__Cons__self2,axiom,
! [A: $tType,Xs1: list(A),X: A] : cons(A,X,Xs1) != Xs1 ).
tff(fact_45_not__Cons__self,axiom,
! [A: $tType,X: A,Xs1: list(A)] : Xs1 != cons(A,X,Xs1) ).
tff(fact_46_append__eq__appendI,axiom,
! [A: $tType,Us1: list(A),Ys2: list(A),Zs1: list(A),Xs11: list(A),Xs1: list(A)] :
( ( append(A,Xs1,Xs11) = Zs1 )
=> ( ( Ys2 = append(A,Xs11,Us1) )
=> ( append(A,Xs1,Ys2) = append(A,Zs1,Us1) ) ) ) ).
tff(fact_47_append__eq__append__conv2,axiom,
! [A: $tType,Ts: list(A),Zs: list(A),Ys: list(A),Xs: list(A)] :
( ( append(A,Xs,Ys) = append(A,Zs,Ts) )
<=> ? [Us: list(A)] :
( ( ( Xs = append(A,Zs,Us) )
& ( append(A,Us,Ys) = Ts ) )
| ( ( append(A,Xs,Us) = Zs )
& ( Ys = append(A,Us,Ts) ) ) ) ) ).
tff(fact_48_rev__swap,axiom,
! [A: $tType,Ys: list(A),Xs: list(A)] :
( ( rev(A,Xs) = Ys )
<=> ( Xs = rev(A,Ys) ) ) ).
tff(fact_49_rev__rev__ident,axiom,
! [A: $tType,Xs1: list(A)] : rev(A,rev(A,Xs1)) = Xs1 ).
tff(fact_50_set__ConsD,axiom,
! [A: $tType,Xs: list(A),X3: A,Y2: A] :
( member(A,Y2,set(A,cons(A,X3,Xs)))
=> ( ( Y2 = X3 )
| member(A,Y2,set(A,Xs)) ) ) ).
tff(fact_51_list_Osimps_I3_J,axiom,
! [A: $tType,List: list(A),A1: A] : cons(A,A1,List) != nil(A) ).
tff(fact_52_list_Osimps_I2_J,axiom,
! [A: $tType,List: list(A),A1: A] : nil(A) != cons(A,A1,List) ).
tff(fact_53_Cons__eq__appendI,axiom,
! [A: $tType,Zs1: list(A),Xs1: list(A),Ys2: list(A),Xs11: list(A),X: A] :
( ( cons(A,X,Xs11) = Ys2 )
=> ( ( Xs1 = append(A,Xs11,Zs1) )
=> ( cons(A,X,Xs1) = append(A,Ys2,Zs1) ) ) ) ).
tff(fact_54_eq__Nil__appendI,axiom,
! [A: $tType,Ys2: list(A),Xs1: list(A)] :
( ( Xs1 = Ys2 )
=> ( Xs1 = append(A,nil(A),Ys2) ) ) ).
tff(fact_55_append__Nil2,axiom,
! [A: $tType,Xs1: list(A)] : append(A,Xs1,nil(A)) = Xs1 ).
tff(fact_56_append__Nil,axiom,
! [A: $tType,Ys2: list(A)] : append(A,nil(A),Ys2) = Ys2 ).
tff(fact_57_spies__partsEs_I2_J,axiom,
! [H: fun(msg,bool),X1: msg,Ka: nat] :
( member(msg,crypt(Ka,X1),parts(H))
=> member(msg,X1,parts(H)) ) ).
tff(fact_58_set__takeWhileD,axiom,
! [A: $tType,Xs: list(A),P1: fun(A,bool),X3: A] :
( member(A,X3,set(A,takeWhile(A,P1,Xs)))
=> ( member(A,X3,set(A,Xs))
& pp(aa1(A,bool,P1,X3)) ) ) ).
tff(fact_59_Server__not__bad,axiom,
~ member(agent1,server,bad) ).
tff(fact_60_Cons__eq__append__conv,axiom,
! [A: $tType,Zs: list(A),Ys: list(A),Xs: list(A),X3: A] :
( ( cons(A,X3,Xs) = append(A,Ys,Zs) )
<=> ( ( ( Ys = nil(A) )
& ( cons(A,X3,Xs) = Zs ) )
| ? [Ys1: list(A)] :
( ( cons(A,X3,Ys1) = Ys )
& ( Xs = append(A,Ys1,Zs) ) ) ) ) ).
tff(fact_61_append__eq__Cons__conv,axiom,
! [A: $tType,Xs: list(A),X3: A,Zs: list(A),Ys: list(A)] :
( ( append(A,Ys,Zs) = cons(A,X3,Xs) )
<=> ( ( ( Ys = nil(A) )
& ( Zs = cons(A,X3,Xs) ) )
| ? [Ys1: list(A)] :
( ( Ys = cons(A,X3,Ys1) )
& ( append(A,Ys1,Zs) = Xs ) ) ) ) ).
tff(fact_62_analz__impI,axiom,
! [Q1: bool,Evsa: list(event),Y1: msg] :
( ( ~ member(msg,Y1,analz(knows(spy,Evsa)))
=> pp(Q1) )
=> ( ~ member(msg,Y1,analz(knows(spy,Evsa)))
=> pp(Q1) ) ) ).
tff(fact_63_takeWhile__tail,axiom,
! [A: $tType,L: list(A),Xs: list(A),X3: A,P1: fun(A,bool)] :
( ~ pp(aa1(A,bool,P1,X3))
=> ( takeWhile(A,P1,append(A,Xs,cons(A,X3,L))) = takeWhile(A,P1,Xs) ) ) ).
tff(fact_64_takeWhile__append1,axiom,
! [A: $tType,Ys: list(A),P1: fun(A,bool),Xs: list(A),X3: A] :
( member(A,X3,set(A,Xs))
=> ( ~ pp(aa1(A,bool,P1,X3))
=> ( takeWhile(A,P1,append(A,Xs,Ys)) = takeWhile(A,P1,Xs) ) ) ) ).
tff(fact_65_Says__imp__knows,axiom,
! [Evsa: list(event),X1: msg,Ba: agent1,Aa: agent1] :
( member(event,says(Aa,Ba,X1),set(event,Evsa))
=> member(msg,X1,knows(Aa,Evsa)) ) ).
tff(fact_66_analz__shrK__Decrypt,axiom,
! [H: fun(msg,bool),X1: msg,Aa: agent1] :
( member(msg,crypt(shrK(Aa),X1),analz(H))
=> ( member(msg,key(shrK(Aa)),analz(H))
=> member(msg,X1,analz(H)) ) ) ).
tff(fact_67_Says__imp__spies,axiom,
! [Evsa: list(event),X1: msg,Ba: agent1,Aa: agent1] :
( member(event,says(Aa,Ba,X1),set(event,Evsa))
=> member(msg,X1,knows(spy,Evsa)) ) ).
tff(fact_68_Says__imp__analz__Spy,axiom,
! [Evsa: list(event),X1: msg,Ba: agent1,Aa: agent1] :
( member(event,says(Aa,Ba,X1),set(event,Evsa))
=> member(msg,X1,analz(knows(spy,Evsa))) ) ).
tff(fact_69_Says__imp__parts__knows__Spy,axiom,
! [Evsa: list(event),X1: msg,Ba: agent1,Aa: agent1] :
( member(event,says(Aa,Ba,X1),set(event,Evsa))
=> member(msg,X1,parts(knows(spy,Evsa))) ) ).
tff(fact_70_analz__mono__contra_I1_J,axiom,
! [Evsa: list(event),X1: msg,Ba: agent1,Aa: agent1,C1: msg] :
( ~ member(msg,C1,analz(knows(spy,cons(event,says(Aa,Ba,X1),Evsa))))
=> ~ member(msg,C1,analz(knows(spy,Evsa))) ) ).
tff(fact_71_MPair__parts,axiom,
! [H: fun(msg,bool),Y1: msg,X1: msg] :
( member(msg,mPair(X1,Y1),parts(H))
=> ~ ( member(msg,X1,parts(H))
=> ~ member(msg,Y1,parts(H)) ) ) ).
tff(fact_72_analz__disj__parts,axiom,
! [H: fun(msg,bool),X1: msg] :
( ( member(msg,X1,analz(H))
| member(msg,X1,parts(H)) )
<=> member(msg,X1,parts(H)) ) ).
tff(fact_73_analz__conj__parts,axiom,
! [H: fun(msg,bool),X1: msg] :
( ( member(msg,X1,analz(H))
& member(msg,X1,parts(H)) )
<=> member(msg,X1,analz(H)) ) ).
tff(fact_74_parts__analz,axiom,
! [H: fun(msg,bool)] : parts(analz(H)) = parts(H) ).
tff(fact_75_ext,axiom,
! [B: $tType,A: $tType,G: fun(A,B),F: fun(A,B)] :
( ! [X4: A] : aa1(A,B,F,X4) = aa1(A,B,G,X4)
=> ( F = G ) ) ).
tff(fact_76_mem__def,axiom,
! [A: $tType,Aa: fun(A,bool),X3: A] :
( member(A,X3,Aa)
<=> pp(aa1(A,bool,Aa,X3)) ) ).
tff(fact_77_analz__parts,axiom,
! [H: fun(msg,bool)] : analz(parts(H)) = parts(H) ).
tff(fact_78_MPair__analz,axiom,
! [H: fun(msg,bool),Y1: msg,X1: msg] :
( member(msg,mPair(X1,Y1),analz(H))
=> ~ ( member(msg,X1,analz(H))
=> ~ member(msg,Y1,analz(H)) ) ) ).
tff(fact_79_ns__sharedp_ONS3,axiom,
! [X1: msg,Ka: nat,Ba: agent1,NA: nat,S: agent1,Aa: agent1,Evs3: list(event)] :
( nS_Sha993195050haredp(Evs3)
=> ( ( Aa != server )
=> ( member(event,says(S,Aa,crypt(shrK(Aa),mPair(nonce(NA),mPair(agent(Ba),mPair(key(Ka),X1))))),set(event,Evs3))
=> ( member(event,says(Aa,server,mPair(agent(Aa),mPair(agent(Ba),nonce(NA)))),set(event,Evs3))
=> nS_Sha993195050haredp(cons(event,says(Aa,Ba,X1),Evs3)) ) ) ) ) ).
tff(fact_80_analz__idem,axiom,
! [H: fun(msg,bool)] : analz(analz(H)) = analz(H) ).
tff(fact_81_analz_OInj,axiom,
! [H: fun(msg,bool),X1: msg] :
( member(msg,X1,H)
=> member(msg,X1,analz(H)) ) ).
tff(fact_82_msg_Osimps_I6_J,axiom,
! [Msg22: msg,Msg12: msg,Msg21: msg,Msg11: msg] :
( ( mPair(Msg11,Msg21) = mPair(Msg12,Msg22) )
<=> ( ( Msg11 = Msg12 )
& ( Msg21 = Msg22 ) ) ) ).
tff(fact_83_msg_Osimps_I4_J,axiom,
! [Nat2: nat,Nat1: nat] :
( ( key(Nat1) = key(Nat2) )
<=> ( Nat1 = Nat2 ) ) ).
tff(fact_84_parts__idem,axiom,
! [H: fun(msg,bool)] : parts(parts(H)) = parts(H) ).
tff(fact_85_parts_OInj,axiom,
! [H: fun(msg,bool),X1: msg] :
( member(msg,X1,H)
=> member(msg,X1,parts(H)) ) ).
tff(fact_86_msg_Osimps_I7_J,axiom,
! [Msg3: msg,Nat2: nat,Msg: msg,Nat1: nat] :
( ( crypt(Nat1,Msg) = crypt(Nat2,Msg3) )
<=> ( ( Nat1 = Nat2 )
& ( Msg = Msg3 ) ) ) ).
tff(fact_87_msg_Osimps_I3_J,axiom,
! [Nat2: nat,Nat1: nat] :
( ( nonce(Nat1) = nonce(Nat2) )
<=> ( Nat1 = Nat2 ) ) ).
tff(fact_88_msg_Osimps_I1_J,axiom,
! [Agent1: agent1,Agent: agent1] :
( ( agent(Agent) = agent(Agent1) )
<=> ( Agent = Agent1 ) ) ).
tff(fact_89_ns__sharedp__ns__shared__eq,axiom,
! [X2: list(event)] :
( nS_Sha993195050haredp(X2)
<=> member(list(event),X2,nS_Sha254967238shared) ) ).
tff(fact_90_ns__sharedp_ONil,axiom,
nS_Sha993195050haredp(nil(event)) ).
tff(fact_91_analz__analzD,axiom,
! [H: fun(msg,bool),X1: msg] :
( member(msg,X1,analz(analz(H)))
=> member(msg,X1,analz(H)) ) ).
tff(fact_92_parts__partsD,axiom,
! [H: fun(msg,bool),X1: msg] :
( member(msg,X1,parts(parts(H)))
=> member(msg,X1,parts(H)) ) ).
tff(fact_93_analz_OFst,axiom,
! [H: fun(msg,bool),Y1: msg,X1: msg] :
( member(msg,mPair(X1,Y1),analz(H))
=> member(msg,X1,analz(H)) ) ).
tff(fact_94_analz_OSnd,axiom,
! [H: fun(msg,bool),Y1: msg,X1: msg] :
( member(msg,mPair(X1,Y1),analz(H))
=> member(msg,Y1,analz(H)) ) ).
tff(fact_95_not__parts__not__analz,axiom,
! [H: fun(msg,bool),C1: msg] :
( ~ member(msg,C1,parts(H))
=> ~ member(msg,C1,analz(H)) ) ).
tff(fact_96_analz__into__parts,axiom,
! [H: fun(msg,bool),C1: msg] :
( member(msg,C1,analz(H))
=> member(msg,C1,parts(H)) ) ).
tff(fact_97_msg_Osimps_I40_J,axiom,
! [Msg2: msg,Msg1: msg,Nat: nat] : key(Nat) != mPair(Msg1,Msg2) ).
tff(fact_98_msg_Osimps_I41_J,axiom,
! [Nat: nat,Msg2: msg,Msg1: msg] : mPair(Msg1,Msg2) != key(Nat) ).
tff(fact_99_parts_OFst,axiom,
! [H: fun(msg,bool),Y1: msg,X1: msg] :
( member(msg,mPair(X1,Y1),parts(H))
=> member(msg,X1,parts(H)) ) ).
%----Helper facts (8)
tff(help_pp_1_1_U,axiom,
~ pp(fFalse) ).
tff(help_pp_2_1_U,axiom,
pp(fTrue) ).
tff(help_fNot_1_1_U,axiom,
! [P: bool] :
( ~ pp(aa1(bool,bool,fNot,P))
| ~ pp(P) ) ).
tff(help_fNot_2_1_U,axiom,
! [P: bool] :
( pp(P)
| pp(aa1(bool,bool,fNot,P)) ) ).
tff(help_COMBB_1_1_U,axiom,
! [C: $tType,B: $tType,A: $tType,R: A,Q: fun(A,B),P: fun(B,C)] : aa1(A,C,combb(B,C,A,P,Q),R) = aa1(B,C,P,aa1(A,B,Q,R)) ).
tff(help_COMBC_1_1_U,axiom,
! [A: $tType,C: $tType,B: $tType,R: A,Q: B,P: fun(A,fun(B,C))] : aa1(A,C,combc(A,B,C,P,Q),R) = aa1(B,C,aa1(A,fun(B,C),P,R),Q) ).
tff(help_fequal_1_1_T,axiom,
! [A: $tType,Y: A,X: A] :
( ~ pp(aa1(A,bool,aa1(A,fun(A,bool),fequal(A),X),Y))
| ( X = Y ) ) ).
tff(help_fequal_2_1_T,axiom,
! [A: $tType,Y: A,X: A] :
( ( X != Y )
| pp(aa1(A,bool,aa1(A,fun(A,bool),fequal(A),X),Y)) ) ).
%----Conjectures (9)
tff(conj_0,hypothesis,
~ member(agent1,a,bad) ).
tff(conj_1,hypothesis,
~ member(agent1,b,bad) ).
tff(conj_2,hypothesis,
member(list(event),evs3,nS_Sha254967238shared) ).
tff(conj_3,hypothesis,
aa != server ).
tff(conj_4,hypothesis,
member(event,says(s,aa,crypt(shrK(aa),mPair(nonce(na),mPair(agent(ba),mPair(key(ka),x))))),set(event,evs3)) ).
tff(conj_5,hypothesis,
member(event,says(aa,server,mPair(agent(aa),mPair(agent(ba),nonce(na)))),set(event,evs3)) ).
tff(conj_6,hypothesis,
~ member(msg,key(k),analz(knows(spy,evs3))) ).
tff(conj_7,hypothesis,
( member(event,says(b,a,crypt(k,nonce(nb))),set(event,evs3))
=> ~ member(msg,crypt(k,nonce(nb)),parts(knows(spy,takeWhile(event,combb(bool,bool,event,fNot,combc(event,event,bool,fequal(event),says(b,a,crypt(k,nonce(nb))))),rev(event,evs3))))) ) ).
tff(conj_8,conjecture,
( ( b != aa )
| ( a != ba )
| ( crypt(k,nonce(nb)) != x )
| ~ member(msg,x,parts(knows(spy,takeWhile(event,combb(bool,bool,event,fNot,combc(event,event,bool,fequal(event),says(aa,ba,x))),append(event,rev(event,evs3),cons(event,says(aa,ba,x),nil(event))))))) ) ).
%------------------------------------------------------------------------------