Project topics and materials
Get Complete Project Material File(s) Now! »
From Herodotus to cryptographic processors
Cryptography, deriving from Greek \kryptos » hidden, and the verb \grafo » write, is the study of message secrecy. Encryption attempts to ensure secrecy in communications, such as those of spies, military leaders, and diplomats, but it has also had religious applications. For instance, early Christians used cryptography to obfuscate some aspects of their religious writings to avoid the near certain persecution. Before the modern era, cryptography was concerned solely with message con den-tiality (i.e. encryption). In recent decades, the eld has expanded beyond con den-tiality concerns to include techniques for message integrity checking, sender/receiver identity authentication, digital signatures, interactive proofs, and secure computation, amongst others. The earliest forms of secret writing required little more than local pen and paper analogs, as most people could not read. More literacy, or opponent literacy, required actual cryptography. The main classical cipher types were transposition ciphers and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters. An early substitution cipher was the Caesar cipher, in which each letter in the plaintext was replaced by a letter some xed number of positions further down the alphabet. It was named after Julius Caesar who is reported to have used it, with a shift of 3, to communicate with his generals during his military campaigns. Steganography (i.e. hiding even the existence of a message so as to keep it con – dential) was also rst developed in ancient times. An early example, from Herodotus, concealed a message { a tattoo on a slave’s shaved head { under the regrown hair. More modern examples of steganography include the use of invisible ink, microdots, and digital watermarks to conceal information.
Various physical devices and aids have been used to assist with ciphers. One of the earliest may have been the scytale of ancient Greece [11], the cipher grille in medieval times, the Alberti’s own cipher disk for the polyalphabetic ciphers (circa 1460), the Johannes Trithemius’ tabula recta scheme, and Thomas Je erson’s multi-cylinder (invented independently by Bazeries around 1900). Early in the 20th century, several mechanical encryption/decryption devices were invented, and many patented, including rotor machines { most famously the Enigma machine used by Germany in World War (WW) II [12]. The development of digital computers and electronics after WWII made possible much more complex ciphers. Today digital computers allows a large use of the cryp-tography not only for government necessity but also for secrecy in ordinary communi-cations, e-commerce secure transaction, trusted ID etc.
The Evaluation Assurance Level
A standard security measure for cryptographic algorithms or for their hardware and software implementations does not exist yet. Nevertheless, there are some criteria to evaluate their security level. One of these criteria is the evaluation of the di culty to break a given crypto-graphic algorithm, with respect to a well-known mathematical problem. Id est, the security level of many cryptographic algorithms can be associated to the di culty of certain computational problems, such as the integer factoring problem or the discrete logarithms in a nite eld problem [13, chapter 11]. There are proofs that crypto-graphic techniques are secure if a certain computational problem cannot be solved e ciently [14]. These proofs are contingent, and thus not de nitive, but are currently the best available for cryptographic algorithms and protocols. Example given, as the main operation in RSA based algorithms is the modular exponentiation in GF(2n), thus the security level of RSA based algorithms is associated to the discrete logarithms in a nite eld problem.
Since 1999 the international standards for security evaluation are de ned by the Common Criteria [15] as Evaluation Assurance Level (EAL1 through EAL7) of an Information Technology product or system [16]. The EAL is a numerical grade assigned following the completion of a Common Criteria security evaluation. The increasing assurance levels re ect added assurance requirements that must be met to achieve Common Criteria certi cation. The intent of the higher levels is to provide higher con dence that the system’s principal security features are reliably implemented. The EAL level does not measure the security of the system itself; it simply states at what level the system was tested to see if it meets all the requirements of its Security Target. The Security Target is a document that describes the assets to protect in the system, the threats that are identi ed on these assets, and the security objectives that are to be achieved by the system security. Then, it describes the system security by listing the security requirements, that are written using the Common Criteria restricted syntax.
A Security Target is generally written to be compliant to a Protection Pro le. The PP is a document, typically created by a user or user community, which identi es security requirements relevant to that user for a particular purpose. A PP e ectively de nes a class of security devices; for example, Smart Cards used to provide digital signatures, or network rewalls. A PP is associated to a product, and it is dedicated to a particular EAL. EAL5+ has become the standard in the SC business, with the PP called SC IC Platform Protection Pro le, under the reference BSI-PP-0002 [17]. The EAL5+ pro-vides more security con dence than the EAL5 does, but less than the EAL6 does. The BSI-PP-0002 speci es the security target for SC. The perimeter of the Target Of Evaluation (TOE) can be one or more assets to be protected, and one or more threats. For instance, perimeter of the BSI-PP-0002 can be the protection: of the user data (asset)
from the fault injection attack that would try to divulge or modify the asset (threat) To achieve a particular EAL, the computer system must meet speci c assurance requirements. Most of these requirements involve design documentation, design analy-sis, functional testing, or penetration testing. The higher EALs involve more detailed documentation, analysis, and testing than the lower ones. Achieving a higher EAL certi cation generally costs more money and takes more time than achieving a lower one. The EAL number assigned to a certi ed system indicates that the system com-pleted all requirements for that level. A higher EAL means nothing more, or less, than the evaluation completed a more stringent set of quality assurance requirements. It is often assumed that a system that achieves a higher EAL will provide its security features more reliably, but there is little or no published evidence to support that as-sumption. The required third-party analysis and testing performed by security experts is reasonably evidence in this direction. An evaluation example of an operating system is presented in [18].
In 2006, the US Government Accountability O ce published (Figure 1.1) a re-port on Common Criteria evaluations that summarized a range of costs and schedules reported for evaluations performed at levels EAL2 through EAL4.
Power dissipation analysis: SPA, DPA
A power monitoring attack can provide similar information by observing the power lines to the hardware, especially the CPU. As with a timing attack, considerable information is inferable for some algorithm implementations under some circumstances. Among these attacks, rst to be developed was the Simple Power Analysis (SPA). The current power samples are analysed in order to obtain information. The following operations are considered as leaks and can be attacked by SPA: writing \1″ or \0″ into the storage mediums (RAM, ROM, registers etc.): the transition current from the p-plan to the n-plan (and vice versa) of CMOS transistors are di erent, therefore writing an \1″ is di erent than writing a \0″; comparing data value stored in memory (e.g. in the conditional branching) can cause a variation of the power consumption; the execution of certain operations like the power elevation, in which there is an high correlation between the time during (and then the power consumption) of the operation itself and the power exponent.
In 1999 the SPA attacks could be performed easily and they cost 400$ only, as it is detailed in [24].
Another power analysis based attack more e cient than the SPA is the Di erential Power Analysis (DPA) attack, which works even on small signals [25]. In order to perform a DPA, rst an attacker must be able to precisely measure the power con-sumption. Second, the attacker needs to know what algorithm is computed, and third an attacker needs the plaintexts or ciphertexts. The strategy of the attacker is to make a lot of measurements, and then divide them with the aid of some oracle into two or more di erent sets. Then, statistical methods are used to verify the oracle. If and only if the oracle was right, one can see noticeable peaks in the statistics.
A direct countermeasure against SPA and DPA is to parallelize all computations. In this way the electrical noise produced can make the power analysis stronger to be performed. The coprocessor’s architecture we present here allows to parallelize the computations. Furthermore, Atmel technology we used, allows to secure write \1″ and \0″ into the memory. Therefore we will consider the writing operations as trusted ones.
Electromagnetic analysis
As a fundamental and inevitable fact of electrical life, current uctuations generate radio waves, which are the currents subject { at least in principle { to a TEMPEST or van Eck attack. If the currents concerned are patterned in distinguishable ways, which is typically the case, the radiation can be recorded and used to infer information about the operation of the associated hardware. If the relevant currents are those associated with a display device (i.e. highly patterned and intended to produce human readable images), the task is greatly eased. Cathode Ray Tube (CRT) displays use substantial currents to steer their electron beams and they have been ’snooped’ in real time with minimum cost hardware from considerable distances (hundreds of meters have been demonstrated). Liquid Crystal Displays (LCDs) require and use smaller currents and are less vulnerable than CRT displays { which is not to say they are invulnerable.
As we said in the previous section, a parallel architecture allows a good protec-tion even against TEMPEST attack, because the computing data are dispatched in several components working concurrently. Celator can exploit this protection against TEMPEST attack thanks to its parallel structure.
Acoustic analysis
As an inescapable fact of electrical life in actual circuits, owing currents heat the materials through which they ow. These materials also continually transmit heat to the environment due to other equally fundamental facts of thermodynamic existence, so there is a continually changing thermally induced mechanical stress as a result of these heating and cooling e ects. That stress appears to be the most signi cant contributor to low level acoustic (i.e. noise) emissions from operating CPUs. Recent research by Shamir et al. [26] has demonstrated that information about the operation of crypto-systems and algorithms can be obtained in this way by the so-called acoustic attack. This kind of attack is easy to perform hardware machines which include big CPU and hard disk.
Table of contents :
Glossary
Abstract
1 Introduction
1.1 Security and insecurity
1.1.1 From Herodotus to cryptographic processors
1.1.2 The Evaluation Assurance Level
1.2 From the Smart-Cards to the secure products
1.2.1 Smart Cards
1.2.2 A secure Environment
1.2.3 The Smart Cards market trend
1.2.4 Smart Card Readers
1.3 Side channel attacks
1.3.1 Timing analysis
1.3.2 Power dissipation analysis: SPA, DPA
1.3.3 Electromagnetic analysis
1.3.4 Acoustic analysis
1.4 Conclusions
2 Three cryptographic algorithms
2.1 The AES algorithm
2.2 The DES algorithm
2.3 The SHA
2.4 Conclusions
3 Hardware and software implementations of cryptographic algorithms: state of the art
3.1 General Purpose Processors
3.1.1 The NEC DRP
3.1.2 The Crow FPGA Implementation
3.1.3 The Zippy Project
3.2 Hardwired macros
3.2.1 The Sharma macro
3.2.2 The G-Plus AES implementation
3.2.3 The Trichina Coprocessor
3.2.4 The Eli Biham DES implementation
3.2.5 The Saqib implementation of DES
3.2.6 The Ahmad hardware implementation of SHA
3.2.7 The Chavez hardware implementations of SHA
3.2.8 The Cadence Hashing Algorithm Generator SHA-256
3.3 Conclusions
4 Proposing a recongurable cryptographic coprocessor: Celator
4.1 The system: CPU, Memory, peripherals, bus
4.2 Celator hardware architecture
4.2.1 The Processing Element Array
4.2.2 The Processing Element { Condential
4.2.3 The Controller { Condential
4.2.4 CRAM
4.2.5 The Interface unit
4.3 Considerations about Celator hardware architecture
5 Validating Celator on FPGA
5.1 AES
5.1.1 Implementation of the AES into a PE Array { Condential
5.1.2 FPGA results
5.1.3 ASIC results
5.2 DES
5.2.1 Implementation of the DES into a PE Array { Condential
5.2.2 FPGA results
5.2.3 ASIC results
5.3 SHA
5.3.1 Implementation of the SHA into a PE Array { Condential
5.3.2 FPGA results
5.3.3 ASIC results
6 Conclusions and Further Work
7 Resume en langue francaise de la these intitulee « Design and development of a recongurable cryptographic coprocessor » par Daniele Fronte
7.1 Resume
7.2 Introduction
7.3 Trois algorithmes cryptographiques
7.3.1 L’algorithme AES
7.3.2 L’algorithme DES
7.3.3 L’algorithme SHA
7.4 Implementations materielles et logicielles d’algorithmes cryptographiques : etat de l’art
7.4.1 Le NEC DRP
7.4.2 La macro SHARMA
7.5 L’architecture materielle de Celator
7.5.1 Le reseau de PE
7.5.2 Le Sequenceur
7.5.3 La CRAM
7.6 Comment Celator execute les algorithmes cryptographiques
7.6.1 Les transformations d’AES
7.6.2 Les transformations de DES
7.6.3 Les transformations de SHA-256
7.6.4 Modes ECB et CBC
7.7 Resultats et discussions
7.8 Conclusions
Acknowledgments
