System and method of interlocking to protect software—mediated program and device behaviors

An automated method for rendering a software program resistant to reverse engineering analysis, whereby existing methods are based on substituting, modifying, or encoding computational expressions or statements, in any one of the following application:

• the computational expressions or statements themselves to be protected, the computational expressions or statements being used to render control flow obscure or tamper-resistant, the computational expressions or statements being used to render data addressing obscure or tamper-resistant, the computational expressions or statements being used to render accesses to large bodies of data obscure or tamper-resistant, or the computational expressions or statements being used for some combination computation protection, control-flow protection, data-addressing-protection, or protection of accesses to large bodies of data, the method comprising:
• replacing at least one first constant or first expression in such a computational expression or statement, whether said computational expression or statement is in source code or binary code form, of said software program, with a second expression, said first expression being a mathematical expression, a Boolean expression, or a bitwise-Boolean expression, said second expression being a mixed mathematical and bitwise-Boolean expression, said first constant or said first expression being simpler than said second expression and said second expression being based on the value or the variables found in said first constant or said first expression,
• wherein evaluation of said second mixed mathematical and bitwise-Boolean expression produces a value which preserves the value of said first constant or said first expression, either:
• with the original value of said first constant or the original value of the result of said first expression, in which case said second mixed mathematical and bitwise-Boolean expression is obtained from said first constant or said first expression by converting said first constant or said first expression by mathematical identities, or,
• in an encoded form, that is, as a new value, which can be converted back to the original said value of said first constant or said first expression by applying an information-preserving decoding function, in which case said second expression is obtained from said first constant or said first expression by modifying said first constant or said first expression by a combination of conversion according to mathematical identities and transformation according to an information preserving encoding function corresponding to the information preserving decoding function,
• wherein conversion of said original constant or expression is performed according to a mathematical identity of the form
• ∑
• i
• =
• 1
• k
• ⁢
• a
• i
• ⁢
• e
• i
• =
• 0
• where ai are coefficients and ei are bitwise expressions, whether simple or complex.

An automated method for rendering a software program resistant to reverse engineering analysis, whereby existing methods are based on substituting, modifying, or encoding computational expressions or statements, in any one of the following application:

• the computational expressions or statements themselves to be protected, the computational expressions or statements being used to render control flow obscure or tamper-resistant, the computational expressions or statements being used to render data addressing obscure or tamper-resistant, the computational expressions or statements being used to render accesses to large bodies of data obscure or tamper-resistant, or the computational expressions or statements being used for some combination computation protection, control-flow protection, data-addressing-protection, or protection of accesses to large bodies of data, the method comprising:
• replacing at least one first constant or first expression in such a computational expression or statement, whether said computational expression or statement is in source code or binary code form, of said software program, with a second expression, said first expression being a mathematical expression, a Boolean expression, or a bitwise-Boolean expression, said second expression being a mixed mathematical and bitwise-Boolean expression, said first constant or said first expression being simpler than said second expression and said second expression being based on the value or the variables found in said first constant or said first expression,
• wherein evaluation of said second mixed mathematical and bitwise-Boolean expression produces a value which preserves the value of said first constant or said first expression, either:
• with the original value of said first constant or the original value of the result of said first expression, in which case said second mixed mathematical and bitwise-Boolean expression is obtained from said first constant or said first expression by converting said first constant or said first expression by mathematical identities, or,
• in an encoded form, that is, as a new value, which can be converted back to the original said value of said first constant or said first expression by applying an information-preserving decoding function, in which case said second expression is obtained from said first constant or said first expression by modifying said first constant or said first expression by a combination of conversion according to mathematical identities and transformation according to an information preserving encoding function corresponding to the information preserving decoding function,
• said at least one first constant, mathematical expression, Boolean expression in source code is an expression producing a vector-valued result, the constants or variables of which include a vector-valued variable or variables, and in which the value of said second mixed mathematical and bitwise-Boolean expression preserves the value of the said at least one first constant, mathematical expression, Boolean expression or bitwise-Boolean expression in source code in encoded form, where the encoding employed in said encoded form is obtained by computing a function of the result of said first constant, mathematical expression, Boolean expression, or bitwise-Boolean expression, said function being a deeply nonlinear function ƒ constructed by a method comprising:
• (a) selecting numbers n, u, and v, such that n=u+v;
• (b) selecting finite fields which are specific representations N, U, and V of finite fields GF(2n), GF(2u), and GF(2v), respectively;
• (c) selecting p and q with q not less than p and with each of p and q not less than 3;
• (d) randomly selecting 1-to-1 linear functions L:
• Up→Uq and G0, G1, . . . , Gk−1:
• Vp→Vq, where each of p, q , and k is at least 2 and k is a power of 2 and k is not greater than 2u;
• (e) randomly selecting a linear function z:
• Up→U and obtaining from z a function s:
• Up→{0, 1, . . . , k−1} by selecting, by a bitwise-Boolean operation, the low order m bits of z's output, where k=2m;
• or alternatively, directly choosing a random onto function s:
• Up→{0, 1, . . . , k−1};
• (f) building the function ƒ from the above-constructed components, where ƒ:
• Np→Nq is computed by computing the leftmost u bits of all of its output vector elements by applying L to the vector P obtained by taking only the leftmost u bits of its input vector elements, and computing the rightmost v bits of all of its output vector elements by applying Gs(P) to the vector Q obtained by taking only the rightmost v bits of its input vector elements, so that the output bits supplied by L(P) and those supplied by Gs(P) (Q) are interleaved throughout the output;
• and
• (g) testing ƒ by enumeration of the frequency of occurrence of its 1-by-1 projections to determine whether ƒ is deeply nonlinear, and if not, repeating the above construction until a deeply nonlinear function ƒ is obtained.