Instruction Set Extensions for Public-Key Cryptography

Public-key cryptography is the basis for security and privacy in distributed systems like the Internet, for e- commerce, and for virtually all modern cryptographic protocols. Most public-key cryptosystems involve computation-intensive arithmetic operations (e.g. 1024-bit modular exponentiation), resulting in unacceptably long delays an constrained devices like smart cards. Therefore, current-generation smart cards are equipped with a cryptographic co-processor. However, using special-purpose hardware for public-key cryptography imposes limitations in terms of scalability and algorithm agility. Public-key cryptosystems nonnally spend most of their execution time in a few performancecritical code Segments with well-defined characteristies (e.g. inner loops), making them amenable to processor specialization. The project described in this proposal is directed towards research an instruction-level enhancements to raise the performance of embedded RISC processors when executing cryptographic workloads. We will focus an low-level arithmetic operations used in public-key cryptography, e.g. addition, multiplication, squaring, modular reduction, inversion, and division in multiplicative groups or finite fields of very high order (160-2048 bits). The first goal of this research project is the design, prototype implementation, and test of a SPARC V8-compatible processor with an extended instruction set optimized for public-key cryptography. The second project goal is to develop and analyze sophisticated micro-architectural enhancements for high-Speed cryptography and improved security (i.e. resistance against sidechannel attacks).

Today, the immersion of digital electronic devices into our everyday life is already very high. However, the number of such devices which will be present in our future environments will be even much higher. It is likely that we will not directly perceive the actual density of these processing devices as many of them will be integrated in everyday appliances in the form of so-called "embedded systems". The enhanced functionality of such systems also gives rise to new potential problems. Only if these problems can be addressed properly, the benefits can outweigh the hazards. Security is one of the most pressing problems in the context of embedded systems. The Internet, which has not been conceived with security measures in mind, gave rise to wide variety of new security threats. As more and more embedded systems become networked, the security problems of the Internet are likely to extend to the embedded domain. Only embedded systems which are built from ground up with security measures in mind can prevent these vulnerabilities. The basis for sound security measures is formed by cryptographic algorithms. When properly implemented, they can serve as adequate tools to defend against security threats. But most cryptographic algorithms (and especially the important class of asymmetric cryptographic algorithms) are very computation intensive. Embedded computing systems are often severely constrained in resources (e.g. processing power, memory, energy), and the need to execute cryptographic algorithms can pose a considerable burden. The goals of this project have been the investigation of a new approach to relieve embedded processors of this burden, and to reduce the overhead of cryptography on these devices. Using a typical embedded processor (SPARC V8 compatible) as target platform, we have designed and added new instructions for cryptography to the original set of instructions. Originally, the project has aimed to demonstrate the benefits for public-key algorithms (RSA, ECC). After we have achieved very good results, we have extended our scope to secret-key primitives (AES) as well, where we were also able to demonstrate impressive processing speedups. In the end we have shown that instruction set extensions allow the efficient implementation of cryptographic algorithms requiring little computing power, memory and energy. In the context of the emerging design paradigm of configurable processors, we see our concept as a key enabling technique for securing future embedded systems.