  Symmetry protected topological (SPT) phases are well understood in the
context of free fermions and in the context of interacting but essentially
bosonic models. Recently it has been realized that intrinsically fermionic SPTs
exist which only appear in interacting models. Here we show that the 3+1
dimensional realizations of these phases have surface states characterized by a
new 't Hooft anomaly, captured by a $H^3(G, Z_2)$ class. This is encoded in the
anomalous action of symmetry on the surface states with topological order,
which must necessarily permute the anyons. We discuss in detail an example with
symmetry group $G = Z_2 \times Z_4$. Using a network model of the surface we
derive a candidate surface topological order given by a $Z_4$ gauge theory. We
relate our findings to anomalies valued in $H^3$ with various coefficients
introduced previously in both bosonic and fermionic settings, and describe a
general framework that unifies these various anomalies.
