Abstract:
A cryptographic system comprising: 1) a first Montgomery-based cryptographic engine that receives a first operand and a second operand and generates a first result and 2) a second Montgomery-based cryptographic engine that receives a first reduced operand derived from the first operand and a second reduced operand derived from the second operand and generates a second result. The second Montgomery-based cryptographic engine operates in parallel with the first Montgomery-base cryptographic engine. The cryptographic system further comprises a comparator for comparing the second result to a first reduced result derived from the first result and generating an error flag if the second result and the first reduced result are different.

Description:
TECHNICAL FIELD OF THE INVENTION  
       [0001]     The present invention relates generally to cryptography systems and, more specifically, to a consistency checking apparatus for detecting disruptive attacks on a cryptographic engine.  
       BACKGROUND OF THE INVENTION  
       [0002]     The demand for improved security and privacy has led to the incorporation of cryptographic engines in a wide range of communication systems and data processing systems. Many of these cryptographic engines use public key cryptography algorithms (RSA, DSA, El-Gamal) that rely on modular arithmetic to crypt/decrypt messages. The basic operation used in these algorithms is a modular multiplication, which computes R=ABmodN, where A, B and N are large numbers, typically with hundreds of digits.  
         [0003]     Implementation of this basic operation has been made quite efficient thanks to Montgomery&#39;s theorem, which provides a multiplication technique for computing R without a long division by N to obtain the remainder. Practical implementations of Montgomery multiplication decompose A into k blocks of p bits to limit the size of the intermediate numbers (i.e., there is no need to store the product AB explicitly).  
         [0004]      FIG. 1  illustrates prior art cryptographic engine  110 , which is based on Montgomery multipliers. Cryptographic engine  110  receives the parallel input A i  and the serial inputs B[j] and N[j] and produces the serial output (or result) R[j]. The parallel input A i  is stored in register  115  in cryptographic engine  110 . It is assumed that N is an odd integer and that both A and B are integers smaller than N. The sizes of A, B and N are on the order of several hundred bits.  
         [0005]     Most common implementations that compute R=ABmodN are based on the Montgomery&#39;s interleaved multiplication. The input data A, B, S and N enter cryptographic engine in a serial fashion (one or more bit at each cycle). The output data, R, is obtained serially. The following equations summaries the basic operations carried by Montgomery-based cryptographic engine  110 : 
 
 T=S +( A   i   ·B )  [Eqn. 1]
 
 Y =( T·J ) mod 2 p   [Eqn. 2]
 
 R =( T+N·Y )/2 p   [Eqn. 3]
 
 where J is a p-bit constant, such that J·N 0 =−1mod2 p , and A i  is the ith block of p bits of A. The number p is usually a power of 2, such as 32 or 64. The numbers J and Y are stored internally in the registers of cryptographic engine  110 . The final result A.BmodN is obtained by iterating the Equation 1, 2 and 3 over each block of p bit of A with the number S of the current iteration being equal to the number R of the previous iteration. Initially, S is zero. 
 
         [0006]     However, cryptographic engines are often the prime targets of hacker attacks in which hostile parties attempts to discover the secret encryption keys. These attacks may take a number of forms, including invasive (e.g., physical probing), non-invasive (e.g., current probing), and disruptive (e.g., fault injection). Cryptographic researchers have extensively studied these types of attacks extensively and have added a number of hardware and software countermeasures to conventional cryptographic engines to minimize the impact of such attacks.  
         [0007]     Disruptive attacks are of particular concern. Disruptive attacks inject a fault (e.g., sudden voltage drop) during cryptographic computations and these faults may corrupt the computation results. Unfortunately, in the current state-of-the-art cryptographic devices, it is impossible to verify whether or not the computation engine returns correct result for S.  
         [0008]     Therefore, there is a need in the art for an improved cryptographic engine. In particular, there is a need for an apparatus and method for verifying the results from a cryptographic engine that may be subject to a disruptive attack.  
       SUMMARY OF THE INVENTION  
       [0009]     The present invention overcomes the shortcomings of the prior art cryptographic engines by the addition of a relatively small hardware engine that performs simple operations on a digest of the two operands A and B, returning a result R r , in parallel with the main computation. The reduced result R r  is compared to a digest of the main result, R. If the numbers are different, then the integrity of the computation has been compromised. The probability of error detection depends on the size of R r .  
         [0010]     To address the above-discussed deficiencies of the prior art, it is a primary object of the present invention to provide a redundant cryptographic system. According to an advantageous embodiment of the present invention, the cryptographic system comprises: 1) a first Montgomery-based cryptographic engine capable of receiving a first operand and a second operand and generating therefrom a first result; and 2) a second Montgomery-based cryptographic engine capable of receiving a first reduced operand derived from the first operand and a second reduced operand derived from the second operand and generating therefrom a second result. The second Montgomery-based cryptographic engine operates in parallel with the first Montgomery-base cryptographic engine.  
         [0011]     According to another embodiment of the present invention, the cryptographic system further comprises a comparator for comparing the second result to a first reduced result derived from the first result and generating an error flag if the second result and the first reduced result are different.  
         [0012]     According to still another embodiment of the present invention, the cryptographic system further comprises a first reduction engine for reducing the first operand from an N-bit value to a P-bit value, thereby producing the first reduced operand.  
         [0013]     According to yet another embodiment of the present invention, the cryptographic system further comprises a second reduction engine for reducing the second operand from an M-bit value to a P-bit value, thereby producing the second reduced operand.  
         [0014]     According to a further embodiment of the present invention, the cryptographic system further comprises a third reduction engine for reducing the first result from an R-bit value to a P-bit value, thereby producing the first reduced result.  
         [0015]     Before undertaking the DETAILED DESCRIPTION OF THE INVENTION below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term “controller” means any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]     For a more complete understanding of the present invention and its advantages, reference is now made to the following description taken in conjunction with the accompanying drawings, in which like reference numerals represent like parts:  
         [0017]      FIG. 1  illustrates a prior art cryptographic engine based on Montgomery&#39;s theorem;  
         [0018]      FIG. 2  illustrates a cryptographic system according to an exemplary embodiment of the present invention;  
         [0019]      FIG. 3  illustrates an exemplary reduction engine for reducing a serial value into a digest value according to the principles of the present invention;  
         [0020]      FIG. 4  illustrates an addition with reduction circuit according to an exemplary embodiment of the present invention;  
         [0021]      FIG. 5  illustrates a multiplication with reduction circuit according to an exemplary embodiment of the present invention;  
         [0022]      FIG. 6  is a timing diagram illustrating the operation of a prior art Montgomery-based cryptographic engine;  
         [0023]      FIG. 7  is a timing diagram illustrating the operation of a Montgomery-based cryptographic engine according to the principles of the present invention; and  
         [0024]      FIG. 8  illustrates the exemplary cryptographic system in  FIG. 2  in greater detail according to an exemplary embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0025]      FIGS. 2 through 8 , discussed below, and the various embodiments used to describe the principles of the present invention in this patent document are by way of illustration only and should not be construed in any way to limit the scope of the invention. Those skilled in the art will understand that the principles of the present invention may be implemented in any suitably arranged cryptographic system.  
         [0026]      FIG. 2  illustrates cryptographic system  200  according to the principles of the present invention. Cryptographic system  200  may be implemented in a data processor, a wireless transceiver, a wireline transceiver, and many other types of communication systems. Cryptographic system  200  comprises conventional Montgomery-based cryptographic engine  110 , reduction engines  211 - 216 , operation core  270  and comparator  280 . To detect faults in conventional cryptographic engine  110 , a small cryptographic engine (operation core  270 ) carries out similar operations in parallel with cryptographic engine  110  using reduced input arguments. At the end of the computations, comparator  280  compares the results of both engines.  
         [0027]     Conventional Montgomery-based cryptographic engine  110  receives the serial inputs B[j], S[j] and N[j], where the index j represents the jth bit of B, S or N. Conventional Montgomery-based cryptographic engine  110  also receives the parallel input A i , where the index i represents the ith block of p bits of the number A. Conventional Montgomery-based cryptographic engine  110  outputs the serial result R[j], where the index j represent the jth bit of R. Conventional Montgomery-based cryptographic engine  110  comprises registers  115  and  205 . Register  115  stores the value of A i . Register  205  stores the value of Y, which is a p-bit number derived from Ai, B and N that is found in all Montgomery-based multipliers.  
         [0028]     The serial input data, B[j], S[j] and N[j], enter reduction engines  211 ,  212  and  213 , each of which computes a digest of the given input data in a serial manner. In parallel with this operation, the serial output result, R[j], also enters reduction engine  216 , which produces a digest of the result. The values of A i  and Y from conventional Montgomery-based cryptographic engine  110  are input to reduction engines  214  and  214 , respectively.  
         [0029]     Each reduction engine stores a 4-bit or an 8-bit digest number. These digest numbers are then input to the digest operating core  270 . Operating core  270  returns a 4-bit or 8-bit number to be compared with the digest of the output result from reduction engine  216 . If these two numbers are not the same, then the computation is incorrect and Error Flag is set for any subsequent hardware or software actions.  
         [0030]     The choice of the number of bits for the reduction engines influences the size of the hardware as well as the probability of error detection. Because the present invention relies on digest numbers rather than the entire serial input numbers, there is a possibility that errors may be undetected through the well-known aliasing problem. The probability of undetected error is inversely proportional to the number of bits in the digest.  
         [0031]     The theory behind the present invention may be explained as follows. Let e be a divisor of p and let the numbers E and F be defined such that: 
 
E=2 e   [Eqn. 4]
 
 F=E− 1  [Eqn. 5]
 
         [0032]     A positive integer can be represented as the sum of k blocks of e bits or as the sum of k′ blocks of p bits. We have for number X:  
             X   =         ∑     i   =   0         k   ′     -   1       ⁢     X   ⁢     〈   i   〉     ⁢     2   pi         =         ∑     i   =   0       k   -   1       ⁢       X   ⁡     [   i   ]       ⁢     E   i         =       ∑     i   =   0       ek   -   1       ⁢       X   i     ⁢     2   i                     [     Eqn   .           ⁢   6     ]             
 
 with 0&lt;=X i &lt;2, 0&lt;=X[i]&lt;2 e , and 0&lt;=X         i         &lt;2 p . 
 
         [0033]     It can be easily proven that:  
               X   ⁢           ⁢   mod   ⁢           ⁢   F     =       (       ∑     i   =   0       k   -   1       ⁢     X   ⁡     [   i   ]         )     ⁢   mod   ⁢           ⁢   F             [     Eqn   .           ⁢   7     ]             
 
         [0034]     The right hand side of Equation 7 is defined as the reduction function of number X and uses the notation red(X) to simplify the writing. This is the function performed by reduction engines  211 - 216 . Stated verbally, the reduction of X with respect to a number k is obtained by summing all the digits of X when represented in base k and then taking the rest of the division modulo k−1. When X is represented as an n-bit binary number, it is advantageous to choose k as a power of 2 (k=2 p ), such that each digit of X in base k is a p-bit number.  
         [0035]     The following equations can be easily proven: 
 
red( X+Y )=red(red( X )+red( Y ))  [Eqn. 8]
 
red( X−Y )=red(red( X )·red( Y ))  [Eqn. 9]
 
         [0036]     It is easy to compute the reduction of R·2 p  by successive application of Equations 8 and 9 above. This gives the result:  
               red   ⁡     (     R   ·     2   p       )       =     red   ⁡     (       red   ⁡     (   S   )       +     red   ⁡     (       red   ⁡     (       red   ⁡     (     A   i     )       ·     red   ⁡     (   B   )         )       +     red   ⁡     (       red   ⁡     (   N   )       ·     red   ⁡     (   Y   )         )         )         )               [     Eqn   .           ⁢   10     ]             
 
         [0037]     The left hand side can be further simplified by observing that the reduction of 2 p  is 1. This gives the result:  
               red   ⁡     (   R   )       =     red   ⁡     (       red   ⁡     (   S   )       +     red   ⁡     (       red   ⁡     (       red   ⁡     (     A   i     )       ·     red   ⁡     (   B   )         )       +     red   ⁡     (       red   ⁡     (   N   )       ·     red   ⁡     (   Y   )         )         )         )               [     Eqn   .           ⁢   11     ]             
 
         [0038]     This result represents the main theoretical result and is the foundation of the error detection engine according to the principles of the present invention.  
         [0039]      FIGS. 3-5  illustrate examples based on an architecture where the serial data width is 1 bit and the digest is 4 bits. This should not be construed as a limitation of the present invention, since the theoretical results above show that larger data widths and digest values are also possible.  
         [0040]      FIG. 3  illustrates exemplary reduction engine  300 , which reduces a serial value into a digest value according to the principles of the present invention. Reduction engine  300  represents any one of reduction engines  211 - 216 . Reduction engine  300  comprises a block of AND gates  310 , a block of adders  320 , a block of subtractors  330 , multiplexer (MUX)  340 , and reduction register  350 .  
         [0041]     The reduction operation (i.e., the computation of red(X)) is based on the following interactive formula: 
 
 X ( t+ 1)=( X[t]+X ( t )) modF   [Eqn. 12]
 
 with X(0)=0, so that at the end, we have: 
 
 X ( k+ 1)=red( X )  [Eqn. 13]
 
         [0042]     The reduction operation is carried in a serial fashion on each incoming or outgoing bit stream. This operation uses an e-bit counter (e.g., 4 bits), which starts at 1 and increments by a factor of 2 at each cycle up to 2 e−1 . The next value after 2 e−1  is 1. Such counter can be implemented very easily with a rotating register. Let 2 Ci  be the value of the counter after the ith cycle. A bitwise AND operation by AND gate  310  between the value of the bit steam at the ith cycle X i  and 2 Ci  is performed. The result is either 0 or 2 Ci , which is added by adders  320  to the current reducted value in reduction register  350 .  
         [0043]     Subtractors  330  subtract the value F from the result of the addition. If the value from subtractors  330  is greater than or equal to 0, the new reducted value is the output of subtractors  330 , otherwise it is the output of adders  320 . It is therefore guarantee that the reducted value is strictly lower than F at all time.  
         [0044]      FIG. 4  illustrates addition with reduction circuit  400  according to an exemplary embodiment of the present invention. Addition with reduction circuit  400  comprises a block of adders  410 , a block of subtractors  420 , and multiplexer (MUX)  430 . Addition with reduction circuit  400  performs the operation red(X+Y), where X and Y are two positive integers strictly less than F. Adders  410  add X and Y and substractors  420  subtract F from the result. If the value from subtractors  420  is greater than or equal to 0, the new reducted value is the output of subtractors  420 . Otherwise, it is the output of adder  410 .  
         [0045]      FIG. 5  illustrates multiplication with reduction circuit  500  according to an exemplary embodiment of the present invention. Multiplication with reduction circuit  500  comprises a block of subtractors  510 , multiplexer (MUX)  520 , X p  register  530 , a block of AND gates  540 , a block of adders  550 , a block of subtractors  560 , multiplexer (MUX)  570  and M register  580 . Multiplication with reduction circuit  500  performs the operation red(X·Y), where X and Y are two positive integers strictly less than F.  
         [0046]     The timing budget allows this operation to be done sequentially using two bit e registers. The first register, X p  register  530 , is initialized with value X. At each cycle, the new value is given by X p &gt;=red(X p +X p ), thus computing the reduced values of 2×, 4×, . . . up to 2 e−1 ×. The second register, M register  580 , is the result register. It is initialized at zero and its new value is given by: 
 
 M &lt;−red( M+X   pi ) if Y i =1  [Eqn. 14]
 
 M &lt;−red( M ) if Y i =0.  [Eqn. 15]
 
         [0047]     The final result is available once all the bits Y are processed.  
         [0048]      FIG. 6  depicts timing diagram  600 , which illustrates the operation of a prior art Montgomery-based cryptographic engine. In  FIG. 6 , the numbers B, S and N are decomposed into 3 blocks of 32 bits. In  FIG. 6 , the term A&lt;i&gt; is equivalent to A i . It is assumed that the number A i  is already loaded in the Montgomery-based engine. In conventional implementations, this is done during the cycle of the round i−1.  
         [0049]     At cycle j of round I, the bits B j , S j  and N j  are the inputs. After a latency of l y  cycles, the bits from Y become available. After a further latency of l R  cycles, the result bit R lR  is available on the output. The latency cycles are usually between 1 and 5, depending on the implementation.  
         [0050]      FIG. 7  depicts timing diagram  700 , which illustrates the operation of a Montgomery-based cryptographic engine according to the principles of the present invention. The present invention implements a schedule for the reduction operations, thereby minimizing the amount of hardware resources. In  FIG. 7 , the term A&lt;i&gt; is equivalent to A i . It is noted from  FIG. 6  that the processing of A i  and the processing of B are separate in time. Also, it is noted that the processing of Y and the processing of R overlap, but during that time, the bits of R are guarantee to be zero. As a consequence, only 4 reduction engines are needed. Thus, Ai is shared with B, and N, S and Y are shared with R.  
         [0051]     The operations 
        red(red(B)·red(A i )) and     red(red(N)·red(J)) 
 
 can only take place once all the bits of B and N have been loaded (i.e., cycle  96  in  FIG. 7 ). These two operations can be done in series, so only one serial reducting multiplier is needed. The reduced sum 
 
red(red(S)+red(red(red(A i )·red(B))+red(red(N)·red(Y)))) 
 
 is carried in 2 consecutive cycles, as follows: 
 
t 1 =red(red(S)+red(red(red(A i )·red(B))) and 
 
t 2 =red(t 1 +red(red(N)·red(Y))). 
 
 This allows further minimization of the hardware with only one reducting adder. 
       
 
         [0054]     The final operation to be scheduled is the compare operation between t 2  and red(R), which can only take place once all the bits of R are available (i.e., cycle  128 +l R ).  
         [0055]      FIG. 8  illustrates exemplary cryptographic system  200  in greater detail according to an exemplary embodiment of the present invention. The circuit in  FIG. 8  is derived from timing diagram  700 . In  FIG. 8 , the term A&lt;i&gt; is equivalent to A i . Cryptographic system  200  comprises multiplexers  801 - 806 , a block of reduction engines  810 , a block of internal registers  820 , multiplication with reduction circuit  830 , internal registers  840 , addition with reduction circuit  850 , internal register  855 , internal register  860 , and comparator  870 .  
         [0056]     Reduction engines  810  are similar to reduction engine  300  in  FIG. 3 . Addition with reduction circuit  850  is similar to addition with reduction circuit  400  in  FIG. 4 . Multiplication with reduction circuit  830  is similar to multiplication with reduction circuit  500  in  FIG. 5 . Multiplexers  803  and  804  control the flow of data toward multiplication with reduction circuit  830 , allowing either red(A i ·B) or red(Y·N) to be computed.  
         [0057]     Multiplexers  805  and  806  control the flow of data toward addition with reduction circuit  850 , allowing either allowing either red(A i ·B+S) or red(A i ·B+S+Y·N) to be computed. A simple e-bit comparator  870  is the last stage operator, returning a Logic 1 value if the quantities red(A i ·B+S+Y·N) and red(R) are equal.  
         [0058]     The operation of the present invention may be explained by the following example. The value of e is set equal to 8, so that each reduced number is represented by 2 hexadecimal digits. Let A, B, S, N and Y be the numbers given below: 
        A=D59139E1     B=37A391D_C9193A0E — 335C5FA3     S=674E35B9 — 183FB6EA — 7FB9861A     N=8BE15734 — 23DCEF49 — 61262B9B     Y=49E3C399        
 
         [0064]     The result R=A·B+S+Y·N is given by: 
        R=2B466018 — 3F3291E3_FC34C8DD — 00000000        
 
         [0066]     The reductions of A, B, S, N and Y are given by: 
        red(A)=82     red(B)=91     red(S)=77     red(Y)=8A     red(N)=80        
 
         [0072]     The results of the reduced multiplication/addition are: 
 
red(red( A )·red( B ))= EB  
 
red(red( N )·red( Y ))=45 
 
red(red( A )·red( B )+red(S))=63 
 
red(red( A )·red( B )+red( S )+red( N )·red( Y ))=A8 
 
         [0073]     The direct reduction of R is: 
        red(R)=A8        
 
         [0075]     The last two numbers are the same, therefore the result, R, is consistent with the input data.  
         [0076]     Although the present invention has been described with an exemplary embodiment, various changes and modifications may be suggested to one skilled in the art. It is intended that the present invention encompass such changes and modifications as fall within the scope of the appended claims.