System for execution of security related functions

An apparatus having a first memory circuit, a plurality of arithmetic modules, and a plurality of second memory circuits. The first memory circuit may be configured to read or write data to or from a host. The plurality of arithmetic modules each may be configured to be enabled or disabled in response to control signals received from the first memory circuit. The plurality of second memory circuits may be configured to read or write data to or from the first memory circuit through a data exchange layer. The arithmetic modules provide cryptographic protection of the data.

SYSTEM FOR EXECUTION OF SECURITY RELATED FUNCTIONS

This application relates to U.S. Provisional Application No. 61/934,940, filed Feb. 3, 2014, which is hereby incorporated by reference in its entirety.

FIELD OF THE INVENTION

The invention relates to security related functions generally and, more particularly, to a method and/or apparatus for implementing a system for execution of security related functions.

BACKGROUND

Public Key Authentication (PKA) algorithms such as RSA and elliptic curve cryptography (ECC) are used extensively for symmetric key establishment in systems that exchange encrypted data over the internet or mobile networks. The strength of the security algorithm is directly proportional to the length of the key used for encryption and decryption. The need for larger keys for enhanced security and fast processing requirements to meet the ever growing data bandwidth at base stations make the authentication mechanisms highly performance sensitive. The need for reducing cost and static power makes gate count minimization one of the primary goals in the design process. Due to its computationally intensive nature, novel approaches are needed to meet the performance goals of these systems.

SUMMARY

The invention concerns an apparatus having a first memory circuit, a plurality of arithmetic modules, and a plurality of second memory circuits. The first memory circuit may be configured to read or write data to or from a host. The plurality of arithmetic modules may each be configured to be enabled or disabled in response to control signals received from the first memory circuit. The plurality of second memory circuits may be configured to read or write data to or from the first memory circuit through a data exchange layer. The arithmetic modules provide cryptographic protection of the data.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiments of the invention include providing a system for execution of security related procedures that may (i) provide the ability to use a common hardware architecture to perform several cryptographic functions, (ii) provide functional and/or performance debugging both during simulation time as well as in hardware, (iii) provide a scalable solution with performance and gate count trade-off, (iv) provide software architecture that can transparently accelerate targeted cryptographic functions, (v) provide a single code base to seamlessly instantiate a high performance or low gate-count design, (vi) provide a firmware that uses a high level software programming language, such as a C program, to drive the hardware, (vii) provide a hardware architecture designed to achieve full parallelism, (viii) operate on large numbers, such as 8192 bit numbers, (ix) provide an efficient pipeline architecture, (x) provide a faster execution, and/or (xi) be implemented as one or more integrated circuits.

One embodiment provides an architecture to perform public key authentication. The architecture partitions the system into a hardware and a firmware component. The hardware may be implemented as a scalable design. The scalable design may achieve performance versus gate-count trade-off for different design goals. The firmware component drives the hardware. The firmware may be easily adapted to implement a variety of public key encryption systems. In one example, the hardware may be implemented in Verilog RTL. In one example, a firmware optimized for RSA may be developed in the C programming language. In one example, the C program may be integrated within a LibTomCrypt library. Encryption and/or decryption calls may use hardware accelerators. For example, given a dimension N, a prime number M (2N−1<M<2N), and a key K (2N−1<K<2N), the design objective may be to create an architecture to compute XNMOD M for any input X, such that the computation is immune to power attacks, maximizes performance, and/or minimizes gate count.

Referring toFIG. 1, a diagram illustrating the system50is shown. The system50describes the role of a public key accelerator in a base station. Generally, the system50comprises a block (or circuit)60, a series of blocks (or circuits)70a-70n, and a block (or circuit)80. The block60is shown representing a communications device, such as a mobile device. The series of blocks70a-70nmay represent base stations. The block80may represent an end point, such as a server.

A mobile data packet may be sent from the communication device60. The mobile data packet may pass through the multiple base stations70a-70n. Each of the multiple base stations70a-70nmay be part of the Internet Protocol Security (IPSEC) domain. The mobile data packet may then reach the end point80.

Depending on the shared keys that are agreed upon, each hop in the IPSEC domain is configured to implement a mechanism to exchange the shared key via a PKA protocol. The link between the mobile device60to the first base station70amay implement a PKA process, such as a Diffie Hellman Key Exchange. The link between70aand70bmay implement another PKA process, such as RSA. The link between70nand80may implement yet another PKA process, such as ECC.

PKA encryption processes (such as RSA and ECC) are used extensively for symmetric key establishment in systems that exchange data over the internet and/or to mobile networks. In the base stations70a-70n, a typical network bandwidth of 20 Giga bits per sec (Gbps) may be implemented. In the next few years, network bandwidth is expected to increase (e.g., to 100 Gbps). The hardware accelerators in the base stations70a-70nperform public key authentication such as RSA. In general, authentication is done fast enough to not become a bottleneck in the processing pipeline. The operations are performed as much in parallel as possible, and each set of operations are as pipelined as possible.

With increasing security breaches, the specifications for RSA key length tend to increase with each generation. While 2048 bits are often considered mainstream, RSA key length in the near future is predicted to reach 8192 bits. Public key authentication operations involve exponentiation and are computationally expensive. For example, an 8192 bit RSA will use 8192 modular multiplications of two 8192 bit numbers which, in turn, corresponds to 8192*3=24486 total multiplications (assuming Montgomery reduction). Furthermore, if the architecture needs to safeguard against power attacks, each multiplication step is further composed of a squaring operation and/or a multiplication operation.

Referring toFIG. 2, a diagram of a system100is shown. The system100is shown implementing a scalable public key establishment system architecture. In various embodiments, the system100comprises a block (or circuit)110, and a block (or circuit)112. The block110implements a host processor. The block112implements a PKA architecture.

The PKA architecture112generally comprises a block (or circuit)120, a series of blocks (or circuits)130a-130n, a series of blocks (or circuits)140a-140n, a series of blocks (or circuits)150a-150n, and a series of blocks (or circuits)160a-160n. The block120implements a command FIFO. In various embodiments, the blocks130a-130nmay be implemented as one or more data exchange layers. In various embodiments, the blocks140a-140nmay be implemented as one or more SRAM clusters. In various embodiments, the blocks150a-150nmay be implemented as one or more interconnects. In various embodiments, the blocks160a-160nmay be implemented as one or more arithmetic modules. The entry point to the PKA architecture112may be the command FIFO120. The host processor110may communicate with the PKA architecture112through the command FIFO120.

The system100may be implemented as part of a larger System-on-Chip (SoC) that performs all the other networking functionality needed at the base station. The host processor110may be an application processor (e.g., an ARM Cortex-15 core, or similar architecture), or a dedicated smaller processor (e.g., a Cortex-M3 core, or similar architecture) that drives the PKA or other processor suitable for implementing a PKA. A PKA driver provides the necessary APIs for the host processor110to invoke the PKA operations. In one example, communication with the PKA architecture112by the host processor110may be through an ARM Advanced Extensible Interface (AXI) bus. The PKA architecture112may act as an AXI slave to the host processor110. The PKA architecture112may include an AXI bus to the system memory. In one example embodiment, the system memory is treated as an AXI slave by the PKA.

In general, the host processor110writes instructions to the command FIFO120through the AXI interface. In general, the instructions need several cycles to execute. For example, an 8192 bit multiplier may take in the order of 160 cycles. Therefore, the command FIFO120may be shallow and still not be a performance bottleneck. In one example embodiment, an 8 deep command FIFO may be implemented. The instructions are then fed to the Data Exchange Layer (DEL)130a-130nfor further processing.

Each of the DELs130a-130nmay decode instructions read from the command FIFO120. Each of the DELs130a-130nmay decode the address. Each of the DELs130a-13On may then issue read (RD) or write (WR) commands to the SRAM clusters140a-140n. Each of the DELs130a-130nmay issue execute requests to the arithmetic modules160a-160n. Wire congestion at the DEL level may be minimized by configuring the DEL to operate as a “tree” of DELs. A tree of DELs may be similar to a network-on-chip structure. In an embodiment implemented using a tree of DELs, each DEL may decode the target of a particular one of the immediate children of a particular one of the DELs130a-130n.

Each arithmetic module160a-160nmay be connected to a set of dedicated SRAMs140a-140n, or other memory elements, via an interconnect150a-150b. In one example, the connection may be via a Parallel Data Transfer (PDT) interconnect. The PDT may perform the functions of a crossbar (XBAR) interconnect (except arbitration). In one example, instead of utilizing arbitration, each master may have a unique port dedicated at each slave with which the master may communicate. To avoid arbitration overhead and achieve parallelism, the number of ports may be increased. Removing the arbitration units within the interconnects150a-150nmay also eliminate head-of-line blocking based deadlock situations.

The number of SRAMs in an SRAM cluster140a-140nthat each master may communicate with may be limited by setting the corresponding configuration parameters. Limiting the number of SRAMs each master communicates with may keep the number of ports within predetermined design limits. When a master communicates with an SRAM not within the connectivity of the master, the data may be explicitly moved from the DEL130a-130nby a software instruction. Since the architecture of the system100may be massively pipelined, and because these movements are relatively few in an optimized firmware, the performance penalty due to the explicit data movement through software may be insignificant.

The arithmetic modules160a-160nprovide an arithmetic logic unit of the system100. One or more arithmetic modules may be implemented in a system. The need for more arithmetic modules may be based on the performance objectives of the system100. An arithmetic module may include two arithmetic module operations (AMOs). The AMOs may be a “multiplicative AMO or MAMO” and/or an “additive AMO of AAMO”. The additive AMO may include adders, subtractors, and/or comparators and/or shifters that may operate on 8192 bit numbers. The multiplicative AMO will be described in more detail inFIG. 5.

Referring toFIG. 3, a block diagram of the system200is shown illustrating an embodiment of the invention. The system200comprises a block (or circuit)210, a block (or circuit)220, a block (or circuit)230, a block (or circuit)240, a block (or circuit)244, a block (or circuit)250a, a block (or circuit)250b,a block (or circuit)260a, a block (or circuit)260b, a block (or circuit)270, a block (or circuit)280, a block (or circuit)282, and/or a block (or circuit)284. The block210may be implemented as a host processor. The block220may be implemented as a command FIFO. The block230may be implemented as a data exchange layer. The blocks240and244may be implemented as a SRAM cluster. The blocks250aand250bmay be implemented as an interconnect. The blocks260aand260bmay be implemented as arithmetic modules. The block270may be implemented as a debug manager. The block280may be implemented as a system interface. The block282may be implemented as an interrupt manager. The block284may be implemented as a status manager.

The debug manager270may send signals to and/or receive signals from (i) the command FIFO220, (ii) the SRAM clusters240and244, (iii) the interconnects250aand250b, and/or (iv) the arithmetic modules260aand260b. The debug manager may provide a framework for fast functional and/or performance debugging. Debugging may be done at simulation time and/or in the hardware.

The system200may support post silicon debug through the debug manager270. Post silicon debug may be performed utilizing the debug interface. The debug interface implements a GDB-like debugger. The debug interface may operate the PKA system200in step mode. The debug interface may insert breakpoints at different points in the firmware.

The interrupt manager282may include an interrupt register to communicate to the host processor210that an error has occurred. In an example embodiment, the PKA system200monitors timeout errors by reporting an error if an operation has been idle for more than a programmed timeout value. The status manager284may be used to execute conditional operations based on the status reported by the different units in the system200.

The PKA system200may incorporate a dedicated power manager to perform coarse level power gating and a clock manager to perform coarse level clock gating. In various embodiments, fine grained clock and/or power gating may be performed by using power management tools such as Synopsys Power Compiler.

Referring toFIG. 4, a diagram illustrating the architecture of a data exchange layer block300is shown. The data exchange layer block300illustrates an example of the data exchange layer blocks130a-130ndescribed inFIG. 2. The data exchange layer block300generally comprises a block (or circuit)302, a block (or circuit)304, a block (or circuit)306, a block (or circuit)308, a block (or circuit)310, a block (or circuit)314, a block (or circuit)316, and a block (or circuit)318. In one example, the block302may be implemented as an input register. In one example, the block304may be implemented as an address decoder. In one example, the block306may be implemented as a command decoder. In one example, the block308may be implemented as a FIFO insertion logic. In one example, the block310may be implemented as a read FIFO control. In one example, the block314may be implemented as a write FIFO control. In one example, the block316may be implemented as a read bus network. In one example, the block318may implement a write bus network.

The input register302may provide data and/or operations to the address decoder304. The address decoder304may determine the actual targets to which the operations should be sent. Data from the address decoder304may be presented to the FIFO insertion logic block308.

The input register302may provide data and/or operations to the command decoder306. The command decoder306may determine the instruction and the type of operations that would be needed to execute an instruction. Data from the command decoder306may be presented to the FIFO insertion logic block308. For example, if the instruction is a “COPY”, the command decoder306may decode the operation as a “READ” from one memory location, and a “WRITE” to another memory location.

The FIFO insertion logic block308may provide data to the read FIFO control310and the write FIFO control314. Data provided by the FIFO insertion logic block308may be optimized to achieve parallelism. In one example, the tuple represented by {operation, source, target} may determine the instructions to be loaded to the FIFO310and/or the FIFO314.

The read FIFO control310may receive read instructions from the FIFO insertion logic block308. The read FIFO control310may contain read FIFO control memory blocks312a-312m. The read FIFO control memory blocks312a-312mmay be arranged to optimize parallelism in the data exchange layer block300. The read FIFO control310may present signals to the read bus network316.

The write FIFO control314may receive write instructions from the FIFO insertion logic block308. The write FIFO control314may contain write FIFO control memory blocks316a-316m. The write FIFO control memory blocks316a-316mmay be arranged to optimize parallelism in the data exchange layer block300. The write FIFO control314may present a signal to the write bus network318. The read bus network316may send and/or receive data to a corresponding SRAM cluster140a-140n. The write bus network318may send data to a corresponding SRAM cluster140a-140n.

In one example implementation, the data exchange layer block300may maintain one read FIFO control310and/or one write instruction FIFO314per target. The interface from the data exchange layer block300to the rest of PKA architecture112may resemble an AXI interface with separate RD and WR channels. Implementing separate RD and/or WR channels may achieve full parallelism between RD and/or WR operations.

The data exchange layer block300ensures strong ordering of traffic for requests targeted to the same memory. In one example, the following two requests may be strictly ordered:

The MOV operation may not start before the COPY operation is completed. Without a strict ordering mechanism, software would be used to take care of every ordering issue. With a strict ordering mechanism, a software developer may instead focus on optimizing the software (e.g., for efficiency and/or performance).

The parallel architecture of the DEL300may allow multiple instructions to disparate targets to be executed in parallel. In one example, the following two instructions may be executed in parallel:

Referring toFIG. 5, a diagram illustrating a multiplier architecture circuit400is shown. The multiplier architecture circuit400generally comprises a block (or circuit)402, a block (or circuit)404, a block (or circuit)406, a block (or circuit)408, a block (or circuit)410, a block (or circuit)412, and a block (or circuit)414. In one example, the circuit402may be a read controller. In one example, the circuit404may be a pipeline stage for the read controller. In one example, the circuit406may be a multiplier. In one example, the circuit408may be a pipeline stage for the multiplier. In one example, the circuit410may be a carry save adder. In one example, the circuit412may be a pipeline stage for the write controller. In one example, the circuit414may be a write controller.

The read controller402may receive and respond to a first operand data and a second operand data. The read controller402may send data to the pipeline stage404. The pipeline stage404may eliminate bottlenecks in the read operations of the multiplier circuit400.

The multiplier406may perform multiplication operations on data. The multiplier may send data to the pipeline stage408. The pipeline stage408may eliminate bottlenecks in the multiplication operations of the multiplier circuit400. The pipeline stage408may send data to the carry and save adder410. The carry and save adder410may perform mathematical operations. The carry and save adder410may send data to the pipeline stage412. The pipeline stage412may reduce and/or eliminate bottlenecks in the operations of the multiplier circuit400. The pipeline stage412may send data to the write controller414. The write controller414may present data as an output signal (e.g., RESULT).

Generally, the MAMOs are the most complex part of the PKA system112. The efficiency of the PKA system112may be dependent on the efficiency of the implemented multiplier architecture400. Conversely, the implementation of the multiplier architecture400may impact the gate-count of the PKA system112.

In one example embodiment of the multiplier architecture400, an 8192 bit multiplier may be implemented from nine 128 bit multipliers. The 8192 bit multiplier may be implemented by applying a two level Karatsuba technique and/or a state machine. Traditional multiplication processes implement four multipliers. The Karatsuba technique generates a 2N×2N multiplier with three N×N multipliers. A 256 bit multiplier may be implemented with three 128 bit multipliers. A 512 bit multiplier may be implemented with three instances of the 256 bit multipliers.

In one example embodiment, the read controller402and the write controller414may implement the 512 bit multiplier from the individual 128 bit multipliers. The controllers402and414and the multiplier may be decoupled. Decoupling the controllers and the multiplier may allow the same hardware to implement a different bit multiplier by modifying one or more of the controllers. The same hardware may also implement a different algorithm to perform the 512 bit multiplication.

The multiplier406and the carry save adder410may operate in a pipelined fashion. For example, with N>512 (and assuming N is a multiple of 512), a N bit multiplier may be created by invoking the 512 bit multiplier 4^(N/512−1) times. At lower levels, the Karatsuba method may use 3^(N/512−1) multiplications. A lower efficiency multiplication method may be preferred because the memory fetches may align themselves better to a pipelined behavior. An overall pipelined operation of several 8192 bit multipliers may be implemented for the exponentiation process.

The PKA architecture112may implement the following instructions: i) Copy, ii) Move, iii) Remove, iv) Exec, and v) Zeroize, and/or Sync. The operating semantic “Copy DST SRC N” may read N bytes from the starting SRC address to the address SRC+N−1, and write the N bytes in the address starting at DST to DST+N−1. The operating semantic “MOVE DST SRC N” may read N bytes from the starting SRC address to the address SRC+N−1, and write the N bytes in the address starting at DST to DST+N−1. The address from SRC to SRC+N−1 may be marked as invalid. The operating semantic “REMOVE SRC N” may read N bytes by starting from the address SRC and reading towards the address SRC+N−1 and discarding the bytes read. The address from SRC to SRC+N−1 may be marked as invalid. The operating semantic “Exec ALU-ID Options” may send an execute command to the ALU with an ID given by ALU-ID. Other options may be specified in the Options parameter. The value presented in the option may indicate the starting addresses of operands for the ALU, the destination addresses, and/or the types of operations to execute (e.g., multiplication, addition, subtraction and/or compare). The operating semantic “ZEROIZE SRC N” may write zeros at the address SRC to the address SRC+N−1. Generally, the ZEROIZE instruction is used to initialize the local memories. The operating semantic “SYNC” may backpressure the PKA system112until all outstanding operations are completed. The SYNC command may be useful in implementing certain barrier conditions. The SYNC command may be used to implement strong ordering semantics at the host processor110. Both the SYNC and ZEROIZE commands may be useful tools when the hardware needs to be debugged during post silicon testing.

Referring toFIG. 6, a flow diagram of a method (or process)500is shown. The method500may perform a read operation from a memory location while ensuring a deadlock free operation. The method500generally comprises a step (or state)502, a step (or state)504, a decision step (or state)506, a step (or state)508, a step (or state)510, and a step (or state)512. The state502may start the method500. The state504may detect a read operation from memory. Next, the method500moves to the decision state506. In the decision state506, if the method500determines there is valid data in the memory location the method500moves to the state510. The state510may complete the read request. Next, the state512may end the method500. If the decision state506determines there is not valid data in the memory location, the method500moves to the state508. The state508may wait until the data in the memory location becomes valid.

Referring toFIG. 7, a flow diagram of a method (or process)550is shown. The method550may perform a write operation from a memory location while ensuring a deadlock free operation. The method550generally comprises a step (or state)552, a step (or state)554, a decision step (or state)556, a step (or state)558, a step (or state)560, and a step (or state)562. The state552may start the method550. The state554may detect a write operation. Next, the decision state556may determine whether there is valid data in the memory location. If yes, the method550moves to the state558. The state558may wait until the data in the memory location is invalidated by a different read operation in the same location. Next, the method550moves to the decision state556. In the decision state556, if the method550determines there is not valid data in the memory location the method550moves to the state560. The state560may complete the write request. Next, the state562may end the method550.

In an example embodiment, memory locations may not be overwritten. A memory location may not be invalidated while there is a pending read operation on the memory. The method500and the method550may prevent the system100from entering into a deadlock situation.

An example of a common deadlock situation in the computation of modular multiplication may be when ALU-0reads a memory location X0, performs an operation, and writes to location X1; ALU-1reads X1, performs an operation, and writes the result to location X2; and ALU-2reads X2, performs an operation and writes the result back to X0. If the result (location X0) has to be moved to the system memory, a typical set of instructions for this operation may be as follows:

Although the program may impose an order for the operations, the MOV instruction may be re-ordered within the PKA architecture112. The MOV instruction may not be re-ordered if a SYNC command was issued. In one example, an old value of X0may be moved to the system memory before ALU-2has completed the operation. The MOV operation may invalidate X0and ALU-0may never complete the operation. The chaining of dependent operations may cause each ALU to wait for data resulting in a deadlock situation.

The deadlock situation may be solved by ensuring that the memory being read is never invalidated. The instructions may be replaced with: