TPTP Problem File: SWW953+1.p
View Solutions
- Solve Problem
%--------------------------------------------------------------------------
% File : SWW953+1 : TPTP v8.2.0. Released v7.4.0.
% Domain : Software Verification
% Problem : Attack on KCLL06 protocol
% Version : [LT19] axioms : Especial.
% English : Attack demonstrates violation of aliveness property of reader
% guaranteed to tag.
% Refs : [BO97] Bull & Otway (1997), The Authentication Protocol
% : [RS98] Ryan & Schneider (1998), An Attack on a Recursive Auth
% : [LT19] Li & Tiu (2019), Combining ProVerif and Automated Theo
% : [Li20] Li (2020), Email to Geoff Sutcliffe
% Source : [Li20]
% Names : KCLL06-reader-auth.p [LT20]
% Status : CounterSatisfiable
% Rating : 0.67 v8.1.0, 0.75 v7.5.0, 0.80 v7.4.0
% Syntax : Number of formulae : 168 ( 135 unt; 0 def)
% Number of atoms : 209 ( 117 equ)
% Maximal formula atoms : 3 ( 1 avg)
% Number of connectives : 146 ( 105 ~; 0 |; 8 &)
% ( 0 <=>; 33 =>; 0 <=; 0 <~>)
% Maximal formula depth : 5 ( 2 avg)
% Maximal term depth : 10 ( 1 avg)
% Number of predicates : 4 ( 3 usr; 0 prp; 1-2 aty)
% Number of functors : 36 ( 36 usr; 18 con; 0-2 aty)
% Number of variables : 63 ( 63 !; 0 ?)
% SPC : FOF_CSA_RFO_SEQ
% Comments : Generated by a modified version of ProVerif used in the
% ProVerif-ATP project [LT19].
%--------------------------------------------------------------------------
fof(ax0,axiom,
constr_CONST_0x30 != constr_CONST_1 ).
fof(ax1,axiom,
constr_CONST_0x30 != constr_CONST_2 ).
fof(ax2,axiom,
constr_CONST_0x30 != constr_CONST_3 ).
fof(ax3,axiom,
constr_CONST_0x30 != constr_CONST_4 ).
fof(ax4,axiom,
constr_CONST_0x30 != constr_QUERY_REQ ).
fof(ax5,axiom,
constr_CONST_0x30 != constr_ZERO ).
fof(ax6,axiom,
constr_CONST_0x30 != name_EPC ).
fof(ax7,axiom,
constr_CONST_0x30 != name_PIN1 ).
fof(ax8,axiom,
constr_CONST_0x30 != name_PIN2 ).
fof(ax9,axiom,
constr_CONST_0x30 != name_S ).
fof(ax10,axiom,
constr_CONST_0x30 != name_c ).
fof(ax11,axiom,
constr_CONST_0x30 != name_r1 ).
fof(ax12,axiom,
constr_CONST_0x30 != name_r1_from_1st_round ).
fof(ax13,axiom,
constr_CONST_0x30 != name_r2_from_1st_round ).
fof(ax14,axiom,
constr_CONST_1 != constr_CONST_2 ).
fof(ax15,axiom,
constr_CONST_1 != constr_CONST_3 ).
fof(ax16,axiom,
constr_CONST_1 != constr_CONST_4 ).
fof(ax17,axiom,
constr_CONST_1 != constr_QUERY_REQ ).
fof(ax18,axiom,
constr_CONST_1 != constr_ZERO ).
fof(ax19,axiom,
constr_CONST_1 != name_EPC ).
fof(ax20,axiom,
constr_CONST_1 != name_PIN1 ).
fof(ax21,axiom,
constr_CONST_1 != name_PIN2 ).
fof(ax22,axiom,
constr_CONST_1 != name_S ).
fof(ax23,axiom,
constr_CONST_1 != name_c ).
fof(ax24,axiom,
constr_CONST_1 != name_r1 ).
fof(ax25,axiom,
constr_CONST_1 != name_r1_from_1st_round ).
fof(ax26,axiom,
constr_CONST_1 != name_r2_from_1st_round ).
fof(ax27,axiom,
constr_CONST_2 != constr_CONST_3 ).
fof(ax28,axiom,
constr_CONST_2 != constr_CONST_4 ).
fof(ax29,axiom,
constr_CONST_2 != constr_QUERY_REQ ).
fof(ax30,axiom,
constr_CONST_2 != constr_ZERO ).
fof(ax31,axiom,
constr_CONST_2 != name_EPC ).
fof(ax32,axiom,
constr_CONST_2 != name_PIN1 ).
fof(ax33,axiom,
constr_CONST_2 != name_PIN2 ).
fof(ax34,axiom,
constr_CONST_2 != name_S ).
fof(ax35,axiom,
constr_CONST_2 != name_c ).
fof(ax36,axiom,
constr_CONST_2 != name_r1 ).
fof(ax37,axiom,
constr_CONST_2 != name_r1_from_1st_round ).
fof(ax38,axiom,
constr_CONST_2 != name_r2_from_1st_round ).
fof(ax39,axiom,
constr_CONST_3 != constr_CONST_4 ).
fof(ax40,axiom,
constr_CONST_3 != constr_QUERY_REQ ).
fof(ax41,axiom,
constr_CONST_3 != constr_ZERO ).
fof(ax42,axiom,
constr_CONST_3 != name_EPC ).
fof(ax43,axiom,
constr_CONST_3 != name_PIN1 ).
fof(ax44,axiom,
constr_CONST_3 != name_PIN2 ).
fof(ax45,axiom,
constr_CONST_3 != name_S ).
fof(ax46,axiom,
constr_CONST_3 != name_c ).
fof(ax47,axiom,
constr_CONST_3 != name_r1 ).
fof(ax48,axiom,
constr_CONST_3 != name_r1_from_1st_round ).
fof(ax49,axiom,
constr_CONST_3 != name_r2_from_1st_round ).
fof(ax50,axiom,
constr_CONST_4 != constr_QUERY_REQ ).
fof(ax51,axiom,
constr_CONST_4 != constr_ZERO ).
fof(ax52,axiom,
constr_CONST_4 != name_EPC ).
fof(ax53,axiom,
constr_CONST_4 != name_PIN1 ).
fof(ax54,axiom,
constr_CONST_4 != name_PIN2 ).
fof(ax55,axiom,
constr_CONST_4 != name_S ).
fof(ax56,axiom,
constr_CONST_4 != name_c ).
fof(ax57,axiom,
constr_CONST_4 != name_r1 ).
fof(ax58,axiom,
constr_CONST_4 != name_r1_from_1st_round ).
fof(ax59,axiom,
constr_CONST_4 != name_r2_from_1st_round ).
fof(ax60,axiom,
constr_QUERY_REQ != constr_ZERO ).
fof(ax61,axiom,
constr_QUERY_REQ != name_EPC ).
fof(ax62,axiom,
constr_QUERY_REQ != name_PIN1 ).
fof(ax63,axiom,
constr_QUERY_REQ != name_PIN2 ).
fof(ax64,axiom,
constr_QUERY_REQ != name_S ).
fof(ax65,axiom,
constr_QUERY_REQ != name_c ).
fof(ax66,axiom,
constr_QUERY_REQ != name_r1 ).
fof(ax67,axiom,
constr_QUERY_REQ != name_r1_from_1st_round ).
fof(ax68,axiom,
constr_QUERY_REQ != name_r2_from_1st_round ).
fof(ax69,axiom,
constr_ZERO != name_EPC ).
fof(ax70,axiom,
constr_ZERO != name_PIN1 ).
fof(ax71,axiom,
constr_ZERO != name_PIN2 ).
fof(ax72,axiom,
constr_ZERO != name_S ).
fof(ax73,axiom,
constr_ZERO != name_c ).
fof(ax74,axiom,
constr_ZERO != name_r1 ).
fof(ax75,axiom,
constr_ZERO != name_r1_from_1st_round ).
fof(ax76,axiom,
constr_ZERO != name_r2_from_1st_round ).
fof(ax77,axiom,
name_EPC != name_PIN1 ).
fof(ax78,axiom,
name_EPC != name_PIN2 ).
fof(ax79,axiom,
name_EPC != name_S ).
fof(ax80,axiom,
name_EPC != name_c ).
fof(ax81,axiom,
name_EPC != name_r1 ).
fof(ax82,axiom,
name_EPC != name_r1_from_1st_round ).
fof(ax83,axiom,
name_EPC != name_r2_from_1st_round ).
fof(ax84,axiom,
name_PIN1 != name_PIN2 ).
fof(ax85,axiom,
name_PIN1 != name_S ).
fof(ax86,axiom,
name_PIN1 != name_c ).
fof(ax87,axiom,
name_PIN1 != name_r1 ).
fof(ax88,axiom,
name_PIN1 != name_r1_from_1st_round ).
fof(ax89,axiom,
name_PIN1 != name_r2_from_1st_round ).
fof(ax90,axiom,
name_PIN2 != name_S ).
fof(ax91,axiom,
name_PIN2 != name_c ).
fof(ax92,axiom,
name_PIN2 != name_r1 ).
fof(ax93,axiom,
name_PIN2 != name_r1_from_1st_round ).
fof(ax94,axiom,
name_PIN2 != name_r2_from_1st_round ).
fof(ax95,axiom,
name_S != name_c ).
fof(ax96,axiom,
name_S != name_r1 ).
fof(ax97,axiom,
name_S != name_r1_from_1st_round ).
fof(ax98,axiom,
name_S != name_r2_from_1st_round ).
fof(ax99,axiom,
name_c != name_r1 ).
fof(ax100,axiom,
name_c != name_r1_from_1st_round ).
fof(ax101,axiom,
name_c != name_r2_from_1st_round ).
fof(ax102,axiom,
name_r1 != name_r1_from_1st_round ).
fof(ax103,axiom,
name_r1 != name_r2_from_1st_round ).
fof(ax104,axiom,
name_r1_from_1st_round != name_r2_from_1st_round ).
fof(ax105,axiom,
constr_add(constr_ZERO,constr_ZERO) = constr_ZERO ).
fof(ax106,axiom,
! [VAR_X_23] : constr_sub(VAR_X_23,constr_ZERO) = VAR_X_23 ).
fof(ax107,axiom,
! [VAR_X_22] : constr_add(VAR_X_22,constr_ZERO) = VAR_X_22 ).
fof(ax108,axiom,
! [VAR_X_21] : constr_sub(VAR_X_21,VAR_X_21) = constr_ZERO ).
fof(ax109,axiom,
! [VAR_X_19,VAR_Y_20X30] : constr_sub(constr_add(VAR_X_19,VAR_Y_20X30),VAR_Y_20X30) = VAR_X_19 ).
fof(ax110,axiom,
! [VAR_X_16,VAR_Y_17,VAR_Z_18] : constr_add(VAR_X_16,constr_add(VAR_Y_17,VAR_Z_18)) = constr_add(constr_add(VAR_X_16,VAR_Y_17),VAR_Z_18) ).
fof(ax111,axiom,
! [VAR_X_14,VAR_Y_15] : constr_add(VAR_X_14,VAR_Y_15) = constr_add(VAR_Y_15,VAR_X_14) ).
fof(ax112,axiom,
! [VAR_X_11,VAR_Y_12,VAR_Z_13] : constr_concat(constr_concat(VAR_X_11,VAR_Y_12),VAR_Z_13) = constr_concat(VAR_X_11,constr_concat(VAR_Y_12,VAR_Z_13)) ).
fof(ax113,axiom,
! [VAR_X_10X30] : constr_xor(VAR_X_10X30,VAR_X_10X30) = constr_ZERO ).
fof(ax114,axiom,
! [VAR_X_9] : constr_xor(VAR_X_9,constr_ZERO) = VAR_X_9 ).
fof(ax115,axiom,
! [VAR_X_7,VAR_Y_8] : constr_xor(VAR_X_7,VAR_Y_8) = constr_xor(VAR_Y_8,VAR_X_7) ).
fof(ax116,axiom,
! [VAR_X_0X30,VAR_Y_0X30,VAR_Z_0X30] : constr_xor(VAR_X_0X30,constr_xor(VAR_Y_0X30,VAR_Z_0X30)) = constr_xor(constr_xor(VAR_X_0X30,VAR_Y_0X30),VAR_Z_0X30) ).
fof(ax117,axiom,
! [VAR_V_49,VAR_V_50X30] :
( ( pred_attacker(VAR_V_49)
& pred_attacker(VAR_V_50X30) )
=> pred_attacker(constr_xor(VAR_V_49,VAR_V_50X30)) ) ).
fof(ax118,axiom,
pred_attacker(tuple_true) ).
fof(ax119,axiom,
! [VAR_V_53,VAR_V_54] :
( ( pred_attacker(VAR_V_53)
& pred_attacker(VAR_V_54) )
=> pred_attacker(constr_sub(VAR_V_53,VAR_V_54)) ) ).
fof(ax120,axiom,
! [VAR_V_57] :
( pred_attacker(VAR_V_57)
=> pred_attacker(tuple_knowledge_from_1st_round_out_5(VAR_V_57)) ) ).
fof(ax121,axiom,
! [VAR_V_60X30] :
( pred_attacker(tuple_knowledge_from_1st_round_out_5(VAR_V_60X30))
=> pred_attacker(VAR_V_60X30) ) ).
fof(ax122,axiom,
! [VAR_V_63] :
( pred_attacker(VAR_V_63)
=> pred_attacker(tuple_knowledge_from_1st_round_out_4(VAR_V_63)) ) ).
fof(ax123,axiom,
! [VAR_V_66] :
( pred_attacker(tuple_knowledge_from_1st_round_out_4(VAR_V_66))
=> pred_attacker(VAR_V_66) ) ).
fof(ax124,axiom,
! [VAR_V_69] :
( pred_attacker(VAR_V_69)
=> pred_attacker(tuple_knowledge_from_1st_round_out_3(VAR_V_69)) ) ).
fof(ax125,axiom,
! [VAR_V_72] :
( pred_attacker(tuple_knowledge_from_1st_round_out_3(VAR_V_72))
=> pred_attacker(VAR_V_72) ) ).
fof(ax126,axiom,
! [VAR_V_75] :
( pred_attacker(VAR_V_75)
=> pred_attacker(tuple_knowledge_from_1st_round_out_2(VAR_V_75)) ) ).
fof(ax127,axiom,
! [VAR_V_78] :
( pred_attacker(tuple_knowledge_from_1st_round_out_2(VAR_V_78))
=> pred_attacker(VAR_V_78) ) ).
fof(ax128,axiom,
! [VAR_V_81] :
( pred_attacker(VAR_V_81)
=> pred_attacker(tuple_knowledge_from_1st_round_out_1(VAR_V_81)) ) ).
fof(ax129,axiom,
! [VAR_V_84] :
( pred_attacker(tuple_knowledge_from_1st_round_out_1(VAR_V_84))
=> pred_attacker(VAR_V_84) ) ).
fof(ax130,axiom,
pred_attacker(tuple_false) ).
fof(ax131,axiom,
! [VAR_V_87] :
( pred_attacker(VAR_V_87)
=> pred_attacker(constr_f(VAR_V_87)) ) ).
fof(ax132,axiom,
! [VAR_V_90X30,VAR_V_91] :
( ( pred_attacker(VAR_V_90X30)
& pred_attacker(VAR_V_91) )
=> pred_attacker(constr_concat(VAR_V_90X30,VAR_V_91)) ) ).
fof(ax133,axiom,
! [VAR_V_94,VAR_V_95] :
( ( pred_attacker(VAR_V_94)
& pred_attacker(VAR_V_95) )
=> pred_attacker(constr_add(VAR_V_94,VAR_V_95)) ) ).
fof(ax134,axiom,
pred_attacker(constr_ZERO) ).
fof(ax135,axiom,
! [VAR_V_97] :
( pred_attacker(VAR_V_97)
=> pred_attacker(tuple_T_out_6(VAR_V_97)) ) ).
fof(ax136,axiom,
! [VAR_V_10X300X30] :
( pred_attacker(tuple_T_out_6(VAR_V_10X300X30))
=> pred_attacker(VAR_V_10X300X30) ) ).
fof(ax137,axiom,
! [VAR_V_10X303] :
( pred_attacker(VAR_V_10X303)
=> pred_attacker(tuple_T_out_4(VAR_V_10X303)) ) ).
fof(ax138,axiom,
! [VAR_V_10X306] :
( pred_attacker(tuple_T_out_4(VAR_V_10X306))
=> pred_attacker(VAR_V_10X306) ) ).
fof(ax139,axiom,
! [VAR_V_10X309] :
( pred_attacker(VAR_V_10X309)
=> pred_attacker(tuple_T_out_2(VAR_V_10X309)) ) ).
fof(ax140,axiom,
! [VAR_V_112] :
( pred_attacker(tuple_T_out_2(VAR_V_112))
=> pred_attacker(VAR_V_112) ) ).
fof(ax141,axiom,
! [VAR_V_115] :
( pred_attacker(VAR_V_115)
=> pred_attacker(tuple_T_in_5(VAR_V_115)) ) ).
fof(ax142,axiom,
! [VAR_V_118] :
( pred_attacker(tuple_T_in_5(VAR_V_118))
=> pred_attacker(VAR_V_118) ) ).
fof(ax143,axiom,
! [VAR_V_122,VAR_V_123] :
( ( pred_attacker(VAR_V_122)
& pred_attacker(VAR_V_123) )
=> pred_attacker(tuple_T_in_3(VAR_V_122,VAR_V_123)) ) ).
fof(ax144,axiom,
! [VAR_V_130X30,VAR_V_131] :
( pred_attacker(tuple_T_in_3(VAR_V_130X30,VAR_V_131))
=> pred_attacker(VAR_V_130X30) ) ).
fof(ax145,axiom,
! [VAR_V_133,VAR_V_134] :
( pred_attacker(tuple_T_in_3(VAR_V_133,VAR_V_134))
=> pred_attacker(VAR_V_134) ) ).
fof(ax146,axiom,
! [VAR_V_137] :
( pred_attacker(VAR_V_137)
=> pred_attacker(tuple_T_in_1(VAR_V_137)) ) ).
fof(ax147,axiom,
! [VAR_V_140X30] :
( pred_attacker(tuple_T_in_1(VAR_V_140X30))
=> pred_attacker(VAR_V_140X30) ) ).
fof(ax148,axiom,
pred_attacker(constr_QUERY_REQ) ).
fof(ax149,axiom,
pred_attacker(constr_CONST_4) ).
fof(ax150,axiom,
pred_attacker(constr_CONST_3) ).
fof(ax151,axiom,
pred_attacker(constr_CONST_2) ).
fof(ax152,axiom,
pred_attacker(constr_CONST_1) ).
fof(ax153,axiom,
pred_attacker(constr_CONST_0x30) ).
fof(ax154,axiom,
! [VAR_V_143] :
( pred_attacker(VAR_V_143)
=> pred_attacker(constr_ACK(VAR_V_143)) ) ).
fof(ax155,axiom,
! [VAR_V_148,VAR_V_149] :
( ( pred_mess(VAR_V_149,VAR_V_148)
& pred_attacker(VAR_V_149) )
=> pred_attacker(VAR_V_148) ) ).
fof(ax156,axiom,
! [VAR_V_150X30,VAR_V_151] :
( ( pred_attacker(VAR_V_151)
& pred_attacker(VAR_V_150X30) )
=> pred_mess(VAR_V_151,VAR_V_150X30) ) ).
fof(ax157,axiom,
pred_attacker(name_c) ).
fof(ax158,axiom,
! [VAR_V_153] : pred_equal(VAR_V_153,VAR_V_153) ).
fof(ax159,axiom,
! [VAR_V_154] : pred_attacker(name_new0x2Dname(VAR_V_154)) ).
fof(ax160,axiom,
pred_attacker(tuple_knowledge_from_1st_round_out_1(constr_QUERY_REQ)) ).
fof(ax161,axiom,
pred_attacker(tuple_knowledge_from_1st_round_out_2(constr_xor(name_r1_from_1st_round,name_PIN1))) ).
fof(ax162,axiom,
pred_attacker(tuple_knowledge_from_1st_round_out_3(constr_ACK(constr_xor(name_r1_from_1st_round,name_PIN1)))) ).
fof(ax163,axiom,
pred_attacker(tuple_knowledge_from_1st_round_out_4(constr_xor(constr_add(constr_concat(constr_ZERO,constr_concat(name_r1_from_1st_round,constr_concat(constr_xor(constr_xor(name_r2_from_1st_round,name_PIN2),name_r1_from_1st_round),constr_f(constr_xor(constr_xor(name_r2_from_1st_round,name_PIN2),name_r1_from_1st_round))))),name_S),name_EPC))) ).
fof(ax164,axiom,
pred_attacker(tuple_knowledge_from_1st_round_out_5(constr_xor(name_PIN1,constr_f(constr_xor(name_r2_from_1st_round,constr_xor(name_PIN2,name_r1_from_1st_round)))))) ).
fof(ax165,axiom,
( pred_attacker(tuple_T_in_1(constr_QUERY_REQ))
=> pred_attacker(tuple_T_out_2(constr_xor(name_r1,name_PIN1))) ) ).
fof(ax166,axiom,
! [VAR_R2_421] :
( ( pred_attacker(tuple_T_in_3(constr_ACK(constr_xor(name_r1,name_PIN1)),VAR_R2_421))
& pred_attacker(tuple_T_in_1(constr_QUERY_REQ)) )
=> pred_attacker(tuple_T_out_4(constr_xor(constr_add(constr_concat(constr_ZERO,constr_concat(name_r1,constr_concat(constr_xor(constr_xor(VAR_R2_421,name_PIN2),name_r1),constr_f(constr_xor(constr_xor(VAR_R2_421,name_PIN2),name_r1))))),name_S),name_EPC))) ) ).
fof(co0,conjecture,
pred_attacker(name_objective) ).
%--------------------------------------------------------------------------