INVESTIGATION OF INFLUENCE OF ENCODING FUNCTION COMPLEXITY ON DISTRIBUTION OF ERROR MASKING PROBABILITY

Error detection codes are mechanisms that enable robust delivery of data in unreliable communication channels and devices. Unreliable channels and devices are error-prone objects. Respectively, error detection codes allow detecting such errors. There are two classes of error detecting codes - classical codes and security-oriented codes. The classical codes have high percentage of detected errors; however, they have a high probability to miss an error in algebraic manipulation. In order, security-oriented codes are codes with a small Hamming distance and high protection to algebraic manipulation. The probability of error masking is a fundamental parameter of security-oriented codes. A detailed study of this parameter allows analyzing the behavior of the error-correcting code in the case of error injection in the encoding device. In order, the complexity of the encoding function plays an important role in the security-oriented codes. Encoding functions with less computational complexity and a low probability of masking are the best protection of encoding device against malicious acts. This paper investigates the influence of encoding function complexity on the error masking probability distribution. It will be shownthat the more complex encoding function reduces the maximum of error masking probability. It is also shown in the paper that increasing of the function complexity changes the error masking probability distribution. In particular, increasing of computational complexity decreases the difference between the maximum and average value of the error masking probability. Our resultshave shown that functions with greater complexity have smoothed maximums of error masking probability, which significantly complicates the analysis of error-correcting code by attacker. As a result, in case of complex encoding function the probability of the algebraic manipulation is reduced. The paper discusses an approach how to measure the error masking probability in the case of nonuniform distribution of the input code words. This approach can also be used to study the characteristics of security-oriented codes in case of strong and weak models of algebraic manipulation. 

1. Karpovsky M.G., Taubin A. New class of nonlinear systematic error detecting codes. IEEE Transactions on Information Theory, 2004, vol. 50, no. 8, pp. 1818–1820. doi: 10.1109/TIT.2004.831844
2. Kulikowski K.J., Karpovsky M.G., Taubin A. Fault attack resistant cryptographic hardware with uniform error detection. Lecture Notes in Computer Science, 2006, vol. 4236, pp. 185–195.
3. Kulikowski K.J., Karpovsky M.G., Taubin A. Robust codes and robust, fault tolerant architectures of the advanced encryption standard. Journal of System Architecture, 2007, vol. 53, pp. 138–149. doi: 10.1016/j.sysarc.2006.09.007
4. Ge S., Wang Z., Luo P., Karpovsky M. Reliable and secure memories based on algebraic manipulation detection codes and robust error correction. Proc. 6th Int. Conf. on Dependability. Barcelona, Spain, 2013.
5. Luo P., Lin A.Y.-L., Wang Z., Karpovsky M.G. Hardware implementation of secure shamir's secret sharing scheme. Proc. IEEE 15th Int. Symposium on High-Assurance Systems Engineering. Miami, USA, 2014, pp. 193–200. doi: 10.1109/HASE.2014.34
6. Wang Z., Karpovsky M.G., Kulikowski K.J. Design of memories with concurrent error detection and correction by non-linear SEC-DED codes. Journal of Electronic Testing: Theory and Applications, 2010, vol. 26, no. 5, pp. 559–580. doi: 10.1007/s10836-010-5168-5
7. Cramer R., Fehr S., Padro C. Algebraic manipulation detection codes. Science China Mathematics, 2013, vol. 56, no. 7, pp. 1349–1358. doi: 10.1007/s11425-013-4654-5
8. Cramer R., Dodis Y., Fehr S., Padró C., Wichs D. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. Lecture Notes in Computer Science, 2008, vol. 4965, pp.
471–488. doi: 10.1007/978-3-540-78967-3_27
9. Wang Z., Karpovsky M.G. Reliable and secure memories based on algebraic manipulation correction codes. Proc. 2012 IEEE 18th Int. On-line Testing Symposium. Sitges, Spain, 2012, art. 6313861, pp. 146–149. doi: 10.1109/IOLTS.2012.6313861
10. Wang Z., Karpovsky M.G., Joshi A. Nonlinear multi-error correcting codes for reliable MLC nand flash memories. IEEE Transactions on VLSI Systems, 2012, vol. 20, no. 7, pp. 1221–1234. doi: 10.1109/TVLSI.2011.2157183
11. Jongsma E. Algebraic Manipulation Detection Codes. Bachelorscriptie, Universiteit Leiden, 2008.
12. Ge S., Wang Z., Luo P., Karpovsky M. Secure memories resistant to both random errors and fault injection attacks using nonlinear error correction codes. Proc. 2nd Int. Workshop on Hardware and Architectural Support for Security and Privacy, HASP 2013. Tel-Aviv, Israel, 2013, art. 5.
13. Shumsky I., Keren O., Karpovsky M. Robustness of security-oriented binary codes under non-uniform distribution of codewords. Proc. 6th Int. Conf. on Dependability. Barcelona, Spain, 2013.
14. Wang Z., Karpovsky M. New error detecting codes for design of hardware resistant to strong fault injection attacks. Proc. Int. Conference on Security and Management, SAM. Las-Vegas, USA, 2012.
15. Akdemir K.D., Wang Z., Karpovsky M.G., Sunar B. Design of cryptographic devices resilient to fault injection attacks using nonlinear robust codes. In: Fault Analysis in Cryptography. Eds. M. Joye, M. Tunstall. Springer, 2011, pp. 1036–1048. doi: 10.1007/978-3-642-29656-7
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License