  Fully Encrypted Protocols (FEPs) have arisen in practice as a technique to
avoid network censorship. Such protocols are designed to produce messages that
appear completely random. This design hides communications metadata, such as
version and length fields, and makes it difficult to even determine what
protocol is being used. Moreover, these protocols frequently support padding to
hide the length of protocol fields and the contained message. These techniques
have relevance well beyond censorship circumvention, as protecting protocol
metadata has security and privacy benefits for all Internet communications. The
security of FEP designs depends on cryptographic assumptions, but neither
security definitions nor proofs exist for them. We provide novel security
definitions that capture the metadata-protection goals of FEPs. Our definitions
are given in both the datastream and datagram settings, which model the
ubiquitous TCP and UDP interfaces available to protocol designers. We prove
relations among these new notions and existing security definitions. We further
present new FEP constructions and prove their security. Finally, we survey
existing FEP candidates and characterize the extent to which they satisfy FEP
security. We identify novel ways in which these protocols are identifiable,
including their responses to the introduction of data errors and the sizes of
their smallest protocol messages.
