Abstract
We present a scheme for robust multi-precision arithmetic over the positive integers, protected by a novel family of non-linear arithmetic residue codes. These codes have a very high probability of detecting arbitrary errors of any weight. Our scheme lends itself well for straightforward implementation of standard modular multiplication techniques, i.e. Montgomery or Barrett Multiplication, secure against active fault injection attacks. Due to the non-linearity of the code the probability of detecting an error does not only depend on the error pattern, but also on the data. Since the latter is not usually known to the adversary a priori, a successful injection of an undetected error is highly unlikely. We give a proof of the robustness of these codes by providing an upper bound on the number of undetectable errors.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shamir, A.: Method and apparatus for protecting public key schemes from timing and fault attacks. US Patent No. 5, 991, 415 (1999)
Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.P.: Fault attacks on RSA with CRT: Concrete results and practical countermeasures (2002)
Blömer, J., Otto, M., Seifert, J.: A new crt-rsa algorithm secure against bellcore attacks. In: CCS 2003: Proceedings of the 10th ACM conference on Computer and communications security, pp. 311–320. ACM Press, New York (2003)
Yen, S.M., Joye, M.: Checking before output may not be enough against fault-based cryptanalysis. IEEE Trans. Comp. 49, 967–970 (2000)
Wagner, D.: Cryptanalysis of a provably secure CRT-RSA algorithm. In: CCS 2004: Proceedings of the 11th ACM Conference on Computer and Communications Security, pp. 92–97. ACM Press, New York (2004)
Karpovsky, M., Taubin, A.: New class of nonlinear systematic error detecting codes. IEEE Transactions on Information Theory 50, 1818–1820 (2004)
Karpovsky, M.G., Kulikowski, K.J., Taubin, A.: Robust protection against fault-injection attacks of smart cards implementing the advanced encryption standard. In: Simoncini, L. (ed.) Proc. Int. Conf. Dependable Systems and Networks (DSN 2004), pp. 93–101. IEEE Computer Society Press, Los Alamitos (2004)
Kulikowski, K., Karpovsky, M.G., Taubin, A.: Robust codes for fault attack resistant cryptographic hardware. In: Breveglieri, L., Koren, I. (eds.) 2nd Int. Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2005) (2005)
Rao, T.R.N., Garcia, O.N.: Cyclic and multiresidue codes for arithmetic operations. IEEE Trans. Inf. Theory 17, 85–91 (1971)
Mandelbaum, D.: Arithmetic codes with large distance. IEEE Transactions on Information Theory 13, 237–242 (1967)
Anderson, R., Kuhn, M.: Tamper resistance - a cautionary note. In: Proceedings of the Second Usenix Workshop on Electronic Commerce, USENIX Association, pp. 1–11. USENIX Press (1996)
Pradhan, D.K.: Fault Tolerant Computing – Theory and Techniques, 1st edn., vol. 1. Prentice-Hall, New Jersey (1986)
Koç, Ç.K., Acar, T., Kaliski, B.J.: Analyzing and comparing montgomery multiplication algorithms. IEEE Micro 16, 26–33 (1996)
Gaubatz, G.: Versatile montgomery multiplier architectures. Master’s thesis, Worcester Polytechnic Institute, Worcester, Massachusetts (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gaubatz, G., Sunar, B., Karpovsky, M.G. (2006). Non-linear Residue Codes for Robust Public-Key Arithmetic. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, JP. (eds) Fault Diagnosis and Tolerance in Cryptography. FDTC 2006. Lecture Notes in Computer Science, vol 4236. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11889700_16
Download citation
DOI: https://doi.org/10.1007/11889700_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46250-7
Online ISBN: 978-3-540-46251-4
eBook Packages: Computer ScienceComputer Science (R0)