Recent Pwn2Own competitions have demonstrated the continued effectiveness of control hijacking attacks despite deployed countermeasures including stack canaries and ASLR. A powerful defense called Control flow Integrity (CFI) offers a principled approach to preventing such attacks. However, prior CFI implementations use static analysis and must limit protection to remain practical. These limitations have enabled attacks against all known CFI systems, as demonstrated in recent work. This paper presents a cryptographic approach to control flow integrity (CCFI) that is both fine-grain and practical: using message authentication codes (MAC) to protect control flow elements such as return addresses, function pointers, and vtable pointers. MACs on these elements prevent even powerful attackers with random read/write access to memory from tampering with program control flow. We implemented CCFI in Clang/LLVM, taking advantage of recently available cryptographic CPU instructions. We evaluate our system on several large software packages (including nginx, Apache and memcache) as well as all their dependencies. The cost of protection ranges from a 3-18% decrease in request rate.