ECC Drives Next Generation Hardware Security Applications
By Daniel O'Loughlin, Director of Hardware Technology Certicom
Public key cryptography has made possible many conveniences of modern day electronic commerce. Internet banking, online retail sales and electronic personal identity verification depend on the confidentiality, integrity and authentication of the data used to make the transactions needed for these applications. Electronic commerce simply could not exist without the ability to secure sensitive data as it is stored remotely on personal devices or traveling over local networks and the internet.
The two most common public key algorithms used in electronic commerce today are RSA and ECC. The main difference between the two is that the security of RSA depends on the apparent hardness of the integer factorization problem, while the security of ECC depends on the apparent hardness of elliptic curve discrete logarithm problem (ECDLP). Because ECDLP is a theoretically apparent harder problem to solve than integer factorization, the elliptic curve public key algorithms have more security strength per bit than RSA.
Quantifying the security strength of the public key algorithm is important. Typically, public key schemes are used with symmetric key algorithms to protect sensitive data. The security strength of a public key scheme must be matched with the security strength of the symmetric algorithm. Some guidelines do exist. The U.S. National Institute of Standards and Technology (NIST) notes in FIPS 140-2: Security Requirements for Cryptographic Modules that:
"Compromising the security of the key establishment method (e.g., compromising the security of the algorithm used for key establishment) shall require at least as many operations as determining the value of the cryptographic key being transported or agreed upon."
In other words, according to NIST, the modulus lengths of the public key must be enforced for use with a symmetric key of a given security strength.
Table 1, also published by NIST, defines the equivalent security strengths between RSA, ECC and symmetric key algorithms.
Table 1. NIST Crypto Modernization Guidelines
Security systems that use ECC public key schemes are well suited for applications that need long-term security requirements. It can be shown mathematically that the relative computational overhead of ECC versus RSA is determined by the cube of the difference in key sizes. Using Table 1 as reference, the increase from 80-bit symmetric key strength to 128-bit requires an equivalent increase from a 1024-bit RSA modulus to a 3072-bit modulus. That increase requires about 27 times (33) more computational cost for RSA, while the same increase using ECC only increases the computational cost by just over 4 times (1.63). The increase in RSA modulus size needed to match the security strength of 128 bit symmetric key AES makes efficient public key computation on constrained platforms near impossible. Providing efficient RSA implementations that match the security strength of greater than 128-bit AES security strength is computationally prohibitive on most platforms.
The argument for ECC as the better long term security scheme was made credible in 2004 when the NSA released the Suite B crypto-modernization statement, while at the same time licensing 26 patents from Certicom for technology related to ECC based digital signatures and key agreement. In Suite B, the NSA specifies only ECC as the public key scheme to secure both sensitive-not classified, and classified U.S. government documents and data starting in 2010.
This past August at the CHES conference in Washington D.C., Adi Shamir of The Weizmann Institute of Science, and co-inventor of RSA, gave a presentation entitled "The Future of RSA". During this presentation Dr. Shamir made the following comments concerning RSA and ECC:
Practical RSA key sizes today are unlikely to be secure 30 years from now.
RSA key sizes which are likely to be secure in 30 years are impractical today.
ECC is clearly better for applications requiring long term security.
These announcements, made by the world's leading code breakers, not only validate the strength of ECC, they also create the opportunity for ECC to be widely adopted. It seems very likely that other government agencies and the commercial sector will follow suit and adopt ECC for strong security across a wide variety of applications and devices.
Certicom and ECC
Since the 1980s, Certicom has been on the forefront of ECC security technology. Over the last 20 years, researchers at Certicom have studied ECC and determined it is a stronger, more efficient technology that is ideally suited for resource-constrained environments such as smart cards, cell phones, and personal digital assistants (PDAs).
Backed by over 125 issued patents covering methods, efficiencies, implementations and general concepts relating to ECC, a number of which are related to efficient hardware security implementations, Certicom is one of the few remaining commercial security firms that still perform original cryptographic research. Certicom's first hardware design was the "583" ElGamal accelerator chip in 1987, used in the CertiFax "bump-in-the-line" encryption product. Other highlights from the Certicom's hardware legacy include the "155" point multiply accelerator chip in 1992, and the hardware point multiply/exponentiation circuit implemented in the Motorola PowerQuicc SEC engine in 1997.
Today, Certicom offers both hardware IP cores and middleware solutions to fit almost any ECC-based public key implementation. Certicom public key solutions are designed for legacy RSA support while providing for the present and future ECC based standards. Certicom hardware IP is easily integrated into any platform through a consistent and configurable software API made available by Certicom Security Builder toolkits.
Certicom hardware IP cores are categorized by architecture into three basic hardware IP core families, P1, P2 and P3. Each IP core family is targeted to satisfy one of three cost/performance tradeoffs. Certicom IP cores offer further cost/performance refinement within an architecture family using compile time design parameterization techniques.
The Certicom P1 architecture family is designed for ultra low power public key performance and is targeted for smartcard, sensor/industrial network, and battery powered handheld devices. Typically, software-only public key operations take several seconds, or more, on computationally constrained 8 and 16 bit embedded platforms. The P1 architecture family was developed to reduce public key operations on these platforms down to a few hundred milliseconds, or faster, while maintaining ultra low dynamic power dissipation.
The Certicom P2 architecture family is designed to provide public key performance over and above what is possible in most embedded 32 bit platforms, using software-only public key implementations. Applications that may fall into this category include wireless networking, secure storage, LAN appliances and government/military class communication devices.
Finally, the Certicom P3 architecture family is designed to provide state-of-the-art public key performance with little regard to cost. Applications requiring this performance grade include enterprise grade servers/security appliances, edge routers/switches and high throughput hardware security modules (HSMs).
The following table summarizes the typical technology usage scenario for each architecture family:
Table 2. Typical Target Technologies
Within these architecture families, Certicom offers two levels of hardware acceleration. Depending on the public key application, hardware acceleration at the point multiply level, or the field arithmetic level is available. Cores that offer hardware accelerated point arithmetic are designated as PKA, while cores that offer hardware accelerated field arithmetic are designated as FAU. In both cases, the lower level hardware accelerated operations are called through the Certicom Security Builder middleware. The Security Builder middleware provides the same public key protocol level API to the application, whether the hardware acceleration is PKA or FAU based.
An example implementation of the Certicom SB-PKA-P2 core has the following cost/performance characteristics measured in operations/sec or throughput for either exponentiation (RSA), or point multiply (ECC):
Table 3. SB-PKA-P2 - Cost/Performance
An example implementation of the SB-FAU-P1 core would provide the following cost/performance design parameters measured in the time to perform a single operation, exponentiation for RSA and point multiply for ECC:
Table 4. SB-FAU-P1 - Cost/Performance
The SB-FAU-P1 implementation dissipates approximately 1 mW of total power (dynamic plus static) in TSMC 130 nM G silicon technology and had been certified at Common Criteria assurance level EAL 5+.
The future of electronic commerce will depend on the ability of security technology to adapt and continue to protect the assets of those who participate. Adoption of ECC as the next generation public key technology has begun today, and will become widespread in the years to come. ECC offers more security per bit than any other standardized public key scheme available today. ECC allows for efficient public key implementations in highly constrained embedded systems, where the advantages of public key schemes are needed more than ever, and where they could not be realized before. Certicom has been focused for over 20 years on developing ECC technology and remains your security partner of choice as you specify and develop your firm's vision for the next generation.
Dan has spent the last five years directing a group of cryptographers and chip designers working on architecting and designing secure device platforms, silicon IP cores and chips for security applications. Dan's major interest is in the design and architecture of efficient ECC-based public key hardware. Dan spent the previous 10 years designing and building audio DSP chips for Creative Technology at the Advanced Technical Center in Scotts Valley, CA. He was the co-architect of the last four generations of the Sound Blaster product line. In the early 90's he was a chip designer at Alesis Studio Electronics in Los Angeles, CA. In the late 80's Dan worked at 360 Systems where he wrote DSP and RTOS system software for studio and broadcast equipment.