#!/usr/bin/python # Will contain all terms that are deducible by the adversary known_terms = set() # Contains all terms that have been added to known_terms but not yet combined # with other terms fresh_terms = set() # The term about which we want to know whether it is deducible target_term = ("enc","B",("rand",2)) # Maximum size. Terms above this size will not be considered max_size = 4 # Results of my experiments (I also analyzed the NSL protocol): # nsl | max_size | #known_terms | derivable # -------------------------------------- # no | 2 | 60 | no # yes | 2 | 60 | no # no | 3 | 1768 | yes # yes | 3 | 1267 | no # no | 4 | 41280 | yes # yes | 4 | 26404 | no # -------------------------------------- # Encoding of messages: # enc(pk_A,t) --> ("enc",A,t) (where A is just a string) # (t,u) --> ("pair",t,u) # A --> ("name",i) (i is an integer) # R_i --> ("rand",i) (i is an integer) # \Hat R_i --> ("rand_adv",i) (i is an integer) # Computes the size of t # (Lots of asserts to catch encoding bugs early on) def size(t): assert isinstance(t,tuple) if t[0]=="enc": assert len(t)==3 assert isinstance(t[1],str) return size(t[2])+1 if t[0]=="pair": assert len(t)==3 return size(t[1])+size(t[2]) if t[0]=="rand": assert len(t)==2 assert isinstance(t[1],int) return 1 if t[0]=="name": assert len(t)==2 assert isinstance(t[1],str) return 1 if t[0]=="rand_adv": assert len(t)==2 assert isinstance(t[1],int) return 1 raise RuntimeError("unexpected term",t) # Useful for debugging def term_to_string(t): if t[0]=="enc": return "enc({},{})".format(t[1],term_to_string(t[2])) if t[0]=="pair": return "({},{})".format(term_to_string(t[1]),term_to_string(t[2])) if t[0]=="rand": return "R{}".format(t[1]) if t[0]=="name": return t[1] if t[0]=="rand_adv": return "R^{}".format(t[1]) raise RuntimeError("unexpected term",t) [...lots more...] print "Number of derivable terms:",len(known_terms) # Uncomment to see all terms (useful for debugging) #for t in known_terms: # print ">",term_to_string(t) derivable = target_term in known_terms print "Checking if {} can be derived: {}".format(term_to_string(target_term),derivable)