System and method for protecting a cryptographic device against fault attacks while performing cryptographic non-linear operations using linear error correcting codes
A system, method and computer-readable storage medium with instructions for protecting an electronic device against fault attack. Given a data represented as an input codeword of a systematic linear error correcting code, the technology provides the secure computation of the output codeword corresponding to the result of the non-linear function applied to this data. Other systems and methods are disclosed.
1. A cryptography device protected from fault attacks while performing a cryptographic operation f, comprising:
a memory, a hardware processor and instruction storage storing instruction executable by the hardware processor to perform cryptography operations, the instructions including—instructions to generate a codeword cw in a code C from an input quantity x wherein the codeword comprises a systematic portion equal to the quantity x and a redundancy portion R x derived from the quantity x using a first redundancy-portion mapping function;
instructions to determine f(x) from x using a cryptography-operation mapping function;
instructions to determine a unique index value using a linear index-value mapping that uniquely maps the combination of the systematic portion x and the redundancy portion R x to said unique index value;
instructions to compute a second redundancy portion R f(x) as a function of the unique index value wherein the combination off(x) and the second redundancy portion is a codeword in C corresponding tof(x) using a second redundancy-portion mapping function;
instructions to verify, the absence of a fault in the computation off by verifying the second redundancy portion (R f(x)) against an expected value for the second redundancy portion;
and in response to detecting a fault by determining a mismatch between the second redundancy portion and the expected value for the second redundancy portion, taking a corrective action to thwart a threat from a potential fault attack.
2. The cryptography device of claim 1 , wherein at least one of the codeword cw, the value f(x), the index value uniquely corresponding to the combination of the systematic portion x and the redundancy portion R_x, or the second redundancy portion is determined using lookup table.
3. The cryptography device of claim 2 , wherein the lookup table for determining at least one of the codeword cw, the value f(x), the index value uniquely corresponding to the combination of the systematic portion x and the redundancy portion R_x, or the second redundancy portion is determined using lookup table is stored in permanent storage of the cryptography device.
4. The cryptography device of claim 1 , wherein the unique index value is a function (l) that is a mapping of inputs x and R_x such that l(x,R_x) determines uniquely x and the instructions to compute a second redundancy portion comprises computing R_f(x) using a mapping of l(x,R_x) to R_f(x).
5. The cryptography device to claim 1 , wherein f is a nonlinear operation in a cryptographic operation.
6. The cryptography device to claim 5 , wherein the cryptography non-linear operation is an operation on a cryptography state word.
7. The cryptography device to claim 1 , wherein the second mapping function is defined such that given as input the output of the index-value mapping the second redundancy-portion mapping function produces the same output as the first redundancy-portion mapping function produces using the output from the cryptography-operation mapping; and
wherein instructions to verify the absence of a fault in the computation of f by verifying the second redundancy portion against an expected value for the second redundancy portion comprises computing a verification value for the redundancy portion based solely on f(x) (R_f(x)′) and comparing the verification value for the redundancy portion against the second redundancy portion computed as a function of the unique index value (R_f(x)).
8. The cryptography device to claim 1 , wherein instructions to verify the absence of a fault in the computation of f by verifying the second redundancy portion against an expected value for the second redundancy portion comprises computing by determining that a codeword composed of a systematic portion f(x) and the second redundancy portion is a valid codeword in C.
9. A method for operating a cryptography device having a processor and instruction storage, the method protecting the cryptography device against fault attacks, the device operable to perform a cryptographic operation f on an input quantity x of a cryptographic process, the input quantity not represented in plaintext and protected against fault attacks, the method comprising:
generating a codeword cw in a code C from an input quantity x wherein the codeword comprises a systematic portion equal to the quantity x and a redundancy portion R_x derived from the quantity x using a first redundancy-portion mapping function;
determining f(x) from x using a cryptography-operation mapping function;
determining a unique index value using a linear index-value mapping that uniquely maps the combination of the systematic portion x and the redundancy portion R_x to said unique index value;
computing a second redundancy portion R_f(x) as a function of the unique index value wherein the combination of f(x) and the second redundancy portion is a codeword in C corresponding to f(x) using a second redundancy-portion mapping function; and
verifying the absence of a fault in the computation of f by verifying the second redundancy portion (R_f(x)) against an expected value for the second redundancy portion; and
in response to detecting a fault by determining a mismatch between the second redundancy portion and the expected value for the second redundancy portion, taking a corrective action to thwart a threat from a potential fault attack.
10. The method for operating a cryptography device having a processor and instruction storage of claim 9 , wherein at least one of the generating a codeword cw, determining the value f(x) from x, the determining the index value uniquely corresponding to the combination of the systematic portion x and the redundancy portion R_x, or the determining the second redundancy portion is determined using lookup table.
11. The method for operating a cryptography device having a processor and instruction storage of claim 10 , wherein the lookup table for determining at least one of the codeword cw, the value f(x), the index value uniquely corresponding to the combination of the systematic portion x and the redundancy portion R_x, or the second redundancy portion is determined using lookup table is stored in permanent storage of the cryptography device.
12. The method for operating a cryptography device having a processor and instruction storage of claim 9 , wherein the unique index value is a function (l) that is a mapping of inputs x and R_x such that l(x,R_x) determines uniquely x and the instructions to compute a second redundancy portion comprises computing R_f(x) using a mapping of l(x,R_x) to R_f(x).
13. The method for operating a cryptography device having a processor and instruction storage of claim 9 , wherein f is a non-linear operation in a cryptographic operation.
14. The method for operating a cryptography device having a processor and instruction storage of claim 9 , wherein the second mapping function is defined such that given as input the output of the index-value mapping the second redundancy-portion mapping function produces the same output as the first redundancy-portion mapping function produces using the output from the cryptography-operation mapping; and wherein verifying the absence of a fault in the computation of f by verifying the second redundancy portion against an expected value for the second redundancy portion comprises computing a verification value for the redundancy portion based solely on f(x) (R_f(x)′) and comparing the verification value for the redundancy portion against the second redundancy portion computed as a function of the unique index value (R_f(x)).
15. The method for operating a cryptography device having a processor and instruction storage of claim 9 , wherein verifying the absence of a fault in the computation of f by verifying the second redundancy portion against an expected value for the second redundancy portion comprises computing by determining that a codeword composed of a systematic portion f(x) and the second redundancy portion is a valid codeword in C.
16. The cryptography device of claim 2 , wherein the unique index value is a function (l) that is a mapping of inputs x and R_x such that l(x,R_x) determines uniquely x and the instructions to compute a second redundancy portion comprises computing R_f(x) using a mapping of l(x,R_x) to R_f(x).
17. The cryptography device of claim 3 , wherein the unique index value is a function (l) that is a mapping of inputs x and R_x such that l(x,R_x) determines uniquely x and the instructions to compute a second redundancy portion comprises computing R_f(x) using a mapping of l(x,R_x) to R_f(x).
18. The cryptography device to of claim 2 , wherein f is a nonlinear operation in a cryptographic operation.
19. The cryptography device to of claim 3 , wherein f is a nonlinear operation in a cryptographic operation.
20. The cryptography device to of claim 4 , wherein f is a nonlinear operation in a cryptographic operation.