On Strengthening of Weak Algebraic Manipulation Detection Codes

On Strengthening of Weak Algebraic Manipulation Detection Codes

Maksim Alekseev (St. Petersburg State University of Aerospace Instrumentation, Saint Petersburg, Russia)
DOI: 10.4018/IJERTCS.2015040101
OnDemand PDF Download:
No Current Special Offers


Algebraic manipulation detection codes were introduced in 2008 to protect data against a special type of its modification – an algebraic manipulation. There are three classes of codes: weak, strong and stronger ones. Weak codes detect only weak algebraic manipulations, while strong and stronger are capable to detect both weak and strong manipulations. In this paper, a method to transform codes from weak to stronger is described resulting in a construction of generalized robust codes. The proposed construction forms the second known family of stronger AMD codes. Codes provide simple procedures of error detectiona and correction, and allow using multi-code codec design that makes it applicable in fault-tolerant computing, storage and cryptographic devices.
Article Preview

1. Introduction

An algebraic manipulation is a model of an undesirable data modification (Cramer, Fehr, & Padró, 2013; Jongsma, 2008). It assumes data distortion by some additive error whose value does not depend on the value of data being distorted. In the paper a concept of algebraic manipulations is described in accordance with a design of secure cryptographic devices (Akdemir, Wang, Karpovsky, & Sunar, 2012; Karpovsky & Wang, 2013; Wang, Karpovsky, Sunar, & Joshi, 2009).

It is well known that cryptographic algorithms' implementations are vulnerable to side-channel attacks (Zhou & Feng, 2005). A fault-injection attack is one of the most efficient attacks, based on an analysis of a cryptographic device's functioning in a presence of faults and computational errors. In many cases, this can lead to a cracking of a cipher-under-attack by revealing a secret key to an attacker. Almost all popular ciphers including RSA, DES and AES are recognized as vulnerable to the fault-injection attack (Abuelyaman & Devadoss, 2005; Anderson & Kuhn, 1998; Dusart, Letourneux, & Vivolo, 2003; Karri, Wu, Mishra, & Kim, 2002; Bar-El, Choukri, Naccache, Tunstall, & Whelan, 2006; Canivet et al., 2011; Kim & Quisquater). As a model of injected faults, an algebraic manipulation model is considered (Cramer et al., 2013; Jongsma, 2008; Wang & Karpovsky, 2011).

An algebraic manipulation is defined as an attacker being able to modify data being processed or stored (distort it by injecting a fault) by some device without being able to obtain any information on the value of the data (Jongsma, 2008). From here, it is possible to distinguish two algebraic manipulation models: a weak manipulation model and a strong manipulation model.

In the weak manipulation model, the attacker is not able to control an input to the device-under-attack. In other words, an informational message input into the device is considered to be uniformly distributed and there is no dependency between injected error and data to be distorted. The probability of error masking in case of weak manipulations is denoted IJERTCS.2015040101.m01.

The strong manipulation model is used in cases when the attacker is able to control the input to the device. This can lead to a more sophisticated choice of an error's value by the attacker. The probability of error masking in case of strong manipulations is denoted IJERTCS.2015040101.m02.

Some special data encoding is required in order to protect data against such manipulations. The most widely used method is to encode data using linear error detecting and correcting codes such as duplication codes, parity check codes and a Hamming code. This method is suitable for situations when arising error patterns correspond to the error detecting capability of the code. However, in cases when an attacker is able to inject specific error patterns, linear codes are not effective. Every IJERTCS.2015040101.m03-ary linear code of a dimension IJERTCS.2015040101.m04 has IJERTCS.2015040101.m05 error patterns (corresponding to nonzero codewords) that are undetectable by this code. Therefore, the attacker can successfully inject one of the codewords as an error into the device. For instance, injecting any double error in data protected with parity check code is undetectable.

Complete Article List

Search this Journal:
Open Access Articles
Volume 13: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing