By introducing collision information, the existing side-channel Correlation-Enhanced Collision Attacks (CECAs) performed collision-chain detection, quickly filtered out candidates unsatisfying collision conditions and extracted a part of optimal candidates for further process, thereby rapidly and significantly reducing the key candidate space and the difficulty of key recovery. However, they are still limited by disadvantages such as serial implementation, complex parameter settings and lack of intelligence, resulting in a low success rate of key recovery. To address these issues, we first present a Collision Detection framework with Genetic Algorithm (CDGA), which exploits Genetic Algorithm to detect the collision chains and has a strong capability of global searching. Secondly, we theoretically analyze the performance of CECA, and bound the searching depth of its output candidate vectors with a confidence level using a data-driven hypothesis test that provides confidence bounds for Gaussian leakages and an approximation based on Central Limit Theory (CLT)for non-Gaussian cases, which facilitates effective and stable population initialization. Thirdly, benefiting from our hypothesis-test-guided design, we propose a goal-directed mutation that prioritizes promising collision candidates, thus improving efficiency and adaptability of the CDGA. Finally, to optimize the evolution of CDGA, we introduce a roulette selection strategy to employ a probability assignment based on individual fitness values to guarantee the preferential selection of superior genes. Comprehensive experiments on DPA Contest v4.1 (AES-256 with Rotated S-boxes Masking) and an AT89S52 AES-128 platform demonstrate that CDGA achieves faster convergence and higher key-recovery success rates compared with TOC/FTC/FCC and Wiemers’ cumulative-correlation selection.

A cryptographic implementation produces very similar power leakages when fed with the same input. Side-channel collision attacks exploit these similarities to establish the relationship between sub-keys and improve the efficiency of key recovery. Benefiting from independence of leakage model, they play an important role in non-profiled setting. However, performance of existing approaches against single collision value is still sub-optimal and optimization is promising. Motivated by this, we first theoretically analyze the mathematical dependency between the number of collisions and the number of encryptions, and propose an efficient side-channel attack named Collision-Paired Correlation Attack (CPCA) to guarantee that the side with fewer samples in a collision is completely paired in low noise scenario. This allows overcoming the inefficient utilization of information in existing works. Moreover, to further employ underlying informativeness, we maximize collision pairs as many as possible. This optimization significantly improves performance of CPCA and thereby extends it to large noise scenarios. Finally, to achieve moderate computational complexity, two equivalent variants of CPCA are investigated to address the potential problem of limited computing resources. Our further theoretical study illustrates that CPCA provides the upper security bound of Correlation-Enhanced Collision Attack (CECA), and experimental results fully verify its superiority.

Side-channel attacks and evaluations have been incessantly pursuing an accurate leakage model and try to address the following question: “How good is my leakage model?” However, the existing works do not well alleviate the attackers and evaluators from model assumption error and estimation error. The recent work named maximum entropy distribution (MED) model does not depend on any assumptions but uses nonlinear programming Newton-Raphson method to fit the leakage distribution, thus avoiding assumption error and making the estimation error arbitrarily small. It tries to address a more fundamental problem: “How to achieve the optimal leakage model?,” but still have to face with two issues: 1) the large deviation of MED model from leakage distribution and 2) the difficulty in determining the moments required in model profiling. In this article, we first introduce the nonlinear programming optimizations Levenberg-Marquardt and Conjugate Gradient methods to tackle the first issue. We then exploit Hopfield neural network to solve the minimum entropy for leakage model. Unlike the MED indicating the theoretically most unbiased, objective and reasonable leakage model, the minimum entropy corresponds to the theoretically most biased, subjective and unreasonable leakage model. This facilitates us to build a MinMaxEntropy bound from the maximum entropy and minimum entropy for estimation errors in leakage model, which theoretically represents the amount of information contained on unused higher moments. This bound well provides theoretical support for the moments constraints required to profile the MED model, thus well tackling the second issue. Experimental results fully demonstrate the superiority of our above schemes.

Evaluating cryptographic implementations with respect to side-channel analysis (SCA) has been mandated at high security levels. Typically, the evaluation involves four stages: detection, modeling, certification and recovery. In pursuit of a specific goal at each stage, inherently different techniques were previously considered necessary. However, since the recent Eurocrypt 2022 and Eurocrypt 2024, linear regression analysis (LRA) has become the unique technique well-applied throughout all the stages. In this paper, we concentrate on this “silver bullet” technique within the field of SCA. In the first part of this paper, we answer three fundamental questions organized progressively. The first one relates to “why use LRA?”. Our discussion of the nominal and binary nature elucidates its critical role in underpinning the state-of-the-art techniques. Having understood the merits, a natural follow-up is “how to use it (correctly and effectively)?”. A theoretical analysis of the design matrix is provided, regarding the sample distribution of plaintext and the chosen degree of polynomial. We summarize the conditions for eliminating multicollinearity, a problem that can be harmful to all LRA-based techniques. The last question “who should use LRA?” reveals an intriguing evaluator-advantageous property: LRA can only unleash its full potential when the key is known. In the second part of this paper, we clarify the connections between LRA and traditional SCA techniques. Our proofs provide new insights into the prior investigation of SCA reduction, fostering a comprehensive understanding of this linear family. The conclusions suggest that the core working mechanisms of the state-of-the-art techniques can be traced back to those of earlier differential side-channel analyses. Experimental results are in line with the theory, confirming its correctness in practice.

Side-channel attacks (SCAs) seriously threaten the security of cryptographic hardwares and embedded systems, especially following the introduction of deep learning techniques, with their powerful feature extraction capability that enables attackers to analyze the key information more efficiently. However, deep learning models in side-channel attacks also face with the problems of excessive model complexity and long training time. In this paper, we introduce Broad Learning Systems (BLS) to power side-channel attacks (SCAs) and then construct an efficient model of broad learning for power SCAs from the core of BLS. Then we optimize the model by making full use of the excellent features of incremental learning and feature extraction of BLS. Finally, we verify the effectiveness of the optimization model in diverse side-channel attack scenarios, achieving stable accuracy levels above 85% while significantly reducing time consumption compared to other models. This fully illustrates the superiority of our scheme.

With the proliferation of IoT devices today, the need to strengthen the security of these devices is becoming increasingly urgent, particularly the need to review the security of lightweight block ciphers. SIMON is a lightweight block cipher proposed by the National Security Agency (NSA) of US to provide efficient and secure encryption for resource-constrained devices in IoT systems. This paper aims to evaluate the security of SIMON against mixture differential cryptanalysis, which was proposed in Eurocrypt 2017 to launch the best key-recovery attacks on the most widely used encryption standard AES. Though there have been intensive studies on this cryptanalysis method, its current targets are all aligned block ciphers. Whether the numerous bitwise block ciphers, including SIMON, have weaknesses regarding this method remains unknown. In this paper, we extend the mixture differential cryptanalysis to bit-wise ciphers and develop an SAT-based automatic tool to search for such distinguishers. We interpret the bit-wise mixture differential distinguisher as a variant of differential distinguisher in the multi-key setting with 2-3n as the boundary (n:block size), potentially boosting rounds or improving the signal-to-noise ratio of previous boomerang or classical differential distinguisher. Using SIMON as an example, we discover multi-key distinguishers for up to 17-round SIMON32, 18-round SIMON48, and 23-round SIMON64, which outperform previous results in terms of the number of rounds. This paper reconciles the disparity between mixture differential cryptanalysis applied to word-oriented target ciphers and its application to bit-oriented targets, thereby extending the mixture differential cryptanalysis to a broader range of block ciphers.

Success Rate (SR) is one of the most popular side-channel security metrics measuring the efficiency of key recovery. Theoretical expression of success rate reveals the functional dependency between relevant parameters such as number of measurements and Signal-to-Noise Ratio (SNR), helping researchers understand the resistance of a given implementation rapidly. However so far, existing works have exposed fundamental problems: (1) Evaluation is confined to a very limited range of distinguishers and specialized methods; (2) Evaluation assumes a perfect leakage model that is detached from reality. It is widely observed that an inaccurate leakage model will lead to a degraded or even distorted success rate. In this paper, we tackle above problems by introducing a novel framework which is able to evaluate seven side-channel distinguishers with a unified expression. Among them, we explore four new distinguishers that have not been investigated in the existing literature. Within the framework, DPA distinguishers are intuitively understood as linear maximum likelihood attack testing closeness between vectors with some easy-to-comprehend geometric metrics. Our evaluation is able to deal with profiled models of any quality and is agnostic to model profiling techniques. It uniquely enables the evaluation of success rates under inaccurate leakage models, whilst providing an (indirect) answer to the open question “how much information is lost due to the model biases” through quantifying the degradation of success rates. Finally, we formulate a set of criterion values for quantitative analyses of the model biases. It provides theoretical evidences for a more thorough explanation for the various behaviors of DPA attacks. Experimental results are inline with the theory, confirming its practical applicability.

In the persistent fault-based collision attack (PFCA) (Zheng et al. 2021), the adversary captures the information that the intermediate states have collided through identical correct/incorrect ciphertexts. However, fault countermeasures achieve suppression of incorrect ciphertexts and prevent the PFCA. In this paper, we measure the collision of internal states (or state bytes) using side-channel information. First, for round-level countermeasures, we identify state bytes hitting the same persistent fault during the first round of encryption by the shortest runtime. Additionally, we design sliding-window algorithms to automatically identify the runtime of one-round encryptions suitable for different execution environments. Second, for algorithm-level protections, we detect the collision of the internal states after the first round of encryption through the maximum similarity of power consumption traces. Meanwhile, to address the low success rate of key recovery caused by miss detection due to noise within runtime or power consumption, we further revise the original filtering algorithm in PFCA. Third, we implement round-level protected AES on PC to measure runtime, and both AES protected by round-level (or algorithm-level) countermeasures and SM4 (ISO/IEC 2021) protected by a round-level countermeasure on a smart card to collect power consumption. Finally, the experimental result proves that the revised PFCA successfully recovers the key.

By introducing collision information into divide-and-conquer distinguishers, the existing collision-optimized side-channel attacks transform the given candidate space into a significantly smaller collision space, thus achieving more efficient key recovery. However, the candidates of the first several subkeys shared by collision chains are still repeatedly detected, which happens very frequently and brings huge computational overhead. To alleviate this, we propose a highly efficient collision-optimized attack named collision tree (CoTree). This collision detection tool exploits tree structure to store the chains created from the same subchain on the same branch, thus significantly reducing the storage requirements. It then benefits from the properties of both tree and collisions and exploits a top-down tree building procedure and traverses each node only once when detecting their collisions with a candidate of the subkey currently under consideration. Finally, unlike the traditional top-down node removal, CoTree launches a bottom-up branch removal procedure to remove the chains unsatisfying the collision conditions from the tree after traversing all the considered candidates of this subkey, thus avoiding the traversal of the branches satisfying the collision condition. These strategies make our CoTree significantly alleviate the repetitive collision detection, and our experiments verify that it significantly outperforms the existing works.

Transport mode identification (TMI), which infers the travel modes of user trajectories, is essential to facilitate an understanding of urban mobility patterns and passengers’ choice behaviors with the goal of improving urban transportation systems. To achieve higher accuracy, existing TMI methods usually rely on mobility features obtained from densely sampled GPS trajectory points (e.g. 1 second per GPS point) or data measurements of additional inertial measurement unit (IMU) sensors (e.g. accelerometer, gyroscope, rotation vector). However, these lead to high energy consumption of the users’ mobile devices. In this paper, we propose a novel deep learning framework, Multi-Scale Attributes Attention (MSAA) model, to extract discriminating trajectory features from GPS data only, without the need to increase its sampling rate. The proposed model first partitions the trajectories into different scales and extract the latent representation of local attributes at each scale. The MSAA model relies on Convolutional Neural Network (CNN) to capture the spatial correlation of different trajectory segments, and utilizes attention mechanism to select the most suitable local attributes on the different trajectory scales that can effectively characterize the various transport modes. Since the learned latent local attributes are significantly different from the global features (e.g. average/min/max travel speeds which are measurable quantities), an ensemble model based on Neural Decision Forest (NDF) is employed to fuse the heterogeneous features consisting of both measurable quantities and non-measurable elements for determining the transport mode. Experiments on real-world datasets demonstrate the competitive performance of the proposed approach compared to several state-of-the-art baselines, with average improvements in accuracy ranging from 0.76% to 6.4%. In addition, the proposed multi-scale local attributes well complement the global features. Our results show that by incorporating the local attributes, the detection performance improved by 2.3% on average compared to using only global features.

With the explosive development of pervasive computing and the Internet of Things (IoT), indoor positioning and navigation have attracted immense attention over recent years. Pedestrian dead reckoning (PDR) is a potential autonomous localization technology that obtains position estimation employing built-in sensors. However, most existing PDR methods assume that the smartphone is held horizontally and points to the walking direction. To solve reckoning errors caused by inconsistency of headings between walking heading and pointing of smartphone, we design an accurate and robust PDR method based on walking patterns, which is identified by multihead convolutional neural networks. In addition to adaptively adjust the threshold of step detection and select the most suitable step length model according to the results of walking pattern recognition, a novel heading estimation approach independent of device orientation is proposed. To mitigate accumulative errors, we proposed an online trajectory calibration method based on forward and backward magnetic fingerprint trajectory matching. We conduct extensive and well-designed experiments in typical scenarios, and the experimental results indicate that the 75th percentile localization accuracy of the three scenarios is 1.06, 1.08, and 1.22 m, respectively, using the commercial smartphone embedded sensor without any dedicated infrastructures or training data. Despite the intricate pedestrian locomotion, the proposed PDR method has great potential in pedestrian positioning.

Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in side-channel attacks (SCAs). State-of-the-art collision-optimized divide-and-conquer attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a divide-and-conquer attack, and transform the very huge guessing space to a much smaller collision space. However, the inefficient collision detection makes them time consuming. The very limited collisions exploited and large performance difference between the collision attack and the divide-and-conquer attack in CODCAs also prevent their application in much larger spaces. In this article, we propose a Minkowski distance enhanced collision attack (MDCA) with performance closer to template attack (TA) compared to traditional correlation-enhanced collision attack (CECA), thus making the optimization more practical and meaningful. Next, we build a more advanced CODCA named full-collision chain (FCC) from TA and MDCA to exploit all collisions. Moreover, to minimize the thresholds while guaranteeing a high success probability of key recovery, we propose a fault-tolerant scheme to optimize FCC. The full key is divided into several big “blocks,” on which a fault-tolerant vector (FTV) is exploited to flexibly adjust its chain space. Finally, guessing theory is exploited to optimize thresholds determination and search order of subkeys. Experimental results show that FCC notably outperforms the existing CODCAs.

Existing power trace extractors consider the case where the number of power traces available to the attacker is sufficient to guarantee successful attacks, and the goal of power trace extraction is to extract a small part of traces with high signal-to-noise ratio (SNR) to reduce the complexity of attacks rather than to increase the success rates. Although strict theoretical proofs are given, the existing power trace extractors are too simple and leakage characteristics of Points-of-Interest (POIs) have not been thoroughly analyzed. They only maximize the variance of the data-dependent power consumption component and ignore the noise component, which results in very limited SNR that hampers the performance of extractors. In this article, we provide a rigorous theoretical analysis of SNR of power traces, and propose a simple yet efficient SNR-centric extractor, named shortest distance first (SDF), to extract power traces with the smallest estimated noise by taking advantage of known plaintexts. In addition, to maximize the variance of the exploitable component while minimizing the noise, we refer to the SNR estimation model and propose another novel extractor named maximizing estimated SNR first (MESF). Finally, we further propose an advanced extractor called mean-optimized MESF (MMESF) that exploits the mean power consumption of each plaintext byte value to more accurately and reasonably estimate the data-dependent power consumption of the corresponding samples. Experiments on both simulated power traces and measurements from an ATmega328p micro-controller demonstrate the superiority of our new extractors.

An accurate leakage model is critical to side-channel attacks and evaluations. Leakage certification plays an important role to address the following question: “how good is my leakage model?” Moreover, most of the current leakage model profiling only exploit the information from lower orders of moments. They still need to tolerate assumption error and estimation error from unknown leakage models. There are many probability density functions (PDFs) satisfying given moment constraints. As such, finding an unbiased, objective, and reasonable model still remains an unresolved problem. In this article, we address a more fundamental question: “which model can approach the leakage infinitely and is the optimal in theory?” In particular, we extract information from higher order moments and propose maximum entropy distribution (MED) to estimate the leakage model as MED is an unbiased, objective, and theoretically the most reasonable PDF conditioned upon the available information. MED is a moment-based statistical PDF model in side-channel attacks. It can theoretically use information on arbitrary higher order moments to infinitely approximate the leakage distribution, and well compensates the theory vacancy of model profiling and evaluation. Experimental results demonstrate the superiority of our proposed method for approximating the leakage model using MED estimation.

A transient fault-based collision attack always requires to inject fault multiple times. We present the first attack that uses collision information caused by a persistent fault in the substitution box (S-box) to recover the entire 128-bit key of the advanced encryption standard (AES). Moreover, a relatively relaxed fault model is required; i.e., the attacker does not know any information about the position, the length (i.e., the number of bytes), or the value of the injected fault. At most, 4096 chosen plaintexts are required for a persistent fault-based collision attack (PFCA), and the computational complexity is O(223) in the worst case in the single-byte fault setting. A filtering algorithm is presented in the multibyte fault setting, and we theoretically prove that the complexity can be reduced to O(212) in more than half of cases if the number of collision ciphertexts follows a uniform distribution. In addition, PFCAs against a software implementation of AES are simulated on a laptop, and the results show that the success probability of the attack either with online key searching or with offline key searching approaches 100%. In particular, more than 97% of all experiments output the right key with complexity O(212) in the multibyte fault setting. Therefore, the attack is more efficient in this scenario. Furthermore, the attack works on an AES implementation protected by Boolean masking. Finally, PFCAs against AES implementations separately protected by two widely used countermeasures-the inverse S-box and the parity-1 matrix-are performed. The experimental results illustrate that only a 10-round protection using the first method can completely defeat the attack.

Several combined attacks have shown promising results in recovering cryptographic keys by introducing collision information into divide-and-conquer attacks to transform a part of the best key candidates within given thresholds into a much smaller collision space. However, these Collision-Optimized Divide-and-Conquer Attacks (CODCAs) uniformly demarcate the thresholds for all sub-keys, which is unreasonable. Moreover, the inadequate exploitation of collision information and backward fault tolerance mechanisms of CODCAs also lead to low attack efficiency. Finally, existing CODCAs mainly focus on improving collision detection algorithms but lack theoretical basis. We exploit Correlation-Enhanced Collision Attack (CECA) to optimize Template Attack (TA). To overcome the above-mentioned problems, we first introduce guessing theory into TA to enable the quick estimation of success probability and the corresponding complexity of key recovery. Next, a novel Multiple-Differential mechanism for CODCAs (MD-CODCA) is proposed. The first two differential mechanisms construct collision chains satisfying the given number of collisions from several sub-keys with the fewest candidates under a fixed probability provided by guessing theory, then exploit them to vote for the remaining sub-keys. This guarantees that the number of remaining chains is minimal, and makes MD-CODCA suitable for very high thresholds. Our third differential mechanism simply divides the key into several large non-overlapping “blocks” to further exploit intra-block collisions from the remaining candidates and properly ignore the inter-block collisions, thus facilitating the later key enumeration. The experimental results show that MD-CODCA significantly reduces the candidate space and lowers the complexity of collision detection, without considerably reducing the success probability of attacks.

The ability to accurately estimate a user's stride length plays a great important role in various applications. For a new target pedestrian or device, their heterogeneity dramatically reduces the performance of the current stride-length estimation (SLE) methods. To address the issue of heterogeneity, in this article, we propose an SLE method based on a long short-term memory (LSTM) network and denoising autoencoders (DAEs). The LSTM network is used to mine temporal dependencies and extract significant eigenvectors from the corrupted inertial sensor observations. Then, DAEs are adopted to automatically eliminate the inherent noise in eigenvectors and obtain denoised eigenvectors. Finally, a regression module maps the denoised eigenvectors to the resulting stride length. To mitigate the heterogeneity, we propose an unperceived model updating framework based on active online learning to establish a personalized model for a given target pedestrian or device. The proposed framework utilizes a magnetism-aided map-matching approach to automatically generate personalized training data and utilizes online learning technologies to evolve the stride-length model. The extensive experimental results demonstrate that the proposed method outperforms other state-of-the-art algorithms and achieves a promising accuracy with a stride-length error rate of 4.59% at a confidence level of 80%.

By introducing collision information into divide-and-conquer attacks, several existing works transform the original candidate space, which may be too large to enumerate, into a significantly smaller collision space, thus making key recovery possible. However, the inefficient collision detection algorithms and fault tolerance mechanisms make them time-consuming and their success rate low. Moreover, they may still leave very huge chain spaces that makes it difficult for key recovery. In this article, we exploit collision attack to optimize Template Attack (TA), and propose a Lightweight Collision Detection (LCD) algorithm. The proposed method exploits a jump detection mechanism to efficiently reduce the repetitive collision detections on chains with the same prefix sub-chains. We then introduce guessing theory to reorder the collision detection of the sub-keys according to their guessing lengths, and provide us with an evaluation tool. Finally, we design a highly efficient fault tolerance mechanism for our LCD to allow flexible thresholds adjustment, and further optimize sieving mechanism to efficiently extract the best chains with the largest number of collisions. Experimental results fully demonstrate LCD's superiority.

An important prerequisite for side-channel attacks (SCAs) is leakage sampling where the side-channel measurements (i.e., power traces) of the cryptographic device are collected for further analysis. However, as the operating frequency of cryptographic devices continues to increase due to advancing technology, leakage sampling will impose higher requirements on the sampling rate and storage capacity of the sampling equipment. This article undertakes the first study to show that effective leakage sampling can be achieved without relying on sophisticated equipments through compressive sensing (CS). As long as the information is leaked in the low-frequency component, CS can obtain low-dimensional samples by simply projecting the high-dimensional signals onto the observation matrix. The power traces can then be reconstructed in a workstation for further analysis and storage. With this approach, the sampling rate to obtain power traces is no longer limited by the operating frequency of the cryptographic device and the Nyquist sampling theorem. Instead, it depends on the sparsity of the leakage signal. As such, CS can employ a much lower sampling rate and yet obtain equivalent leakage sampling performance, which significantly lowers the requirement of sampling equipments. The feasibility of our approach is verified theoretically and through experiments.

Key enumeration schemes are used to post-process the scores given by side channel distinguishers and enumerate the key candidates from the most possible one to the least possible one, which can be regarded as optimal tools of key search. However, the application of them is limited by very large key candidate space and computing power consumption. For example, the attacker may spend several weeks or months enumerating the whole 245key candidates. Unlike the former literature that try to propose a more efficient algorithm to process the distinguishers, scores of key candidates directly, we focus on pre-processing and reducing the key candidate space. To achieve this goal, a new divide and conquer strategy named group collision attack (GCA) is proposed in this paper. The GCA works as follows in brief. The key candidates are first divided into groups on which intra-group collision attack is used to remove the impossible key combinations in each group. Then, the inter-group collision attack is performed to further remove the impossible key combinations between groups. Thus, the complexity of key enumeration is reduced significantly. A series of practical experiments are carried out by using our GCA and the experimental results verify its efficiency.

Integrity trees are widely used in computer systems to prevent replay, splicing, and spoofing attacks on memories. Such mechanisms incur excessive performance and energy overhead. We propose a memory authentication framework that combines architecture-specific optimizations of the integrity tree with mechanisms that enable it to restructure at runtime based on memory access patterns. The integrity tree structure is customized based on the cache configuration in order to minimize the performance and energy overhead through speculative authentication. At runtime, the tree nodes that are accessed more frequently will be dynamically shifted closer to the root such that fewer levels of the tree are accessed during authentication. The framework is simulated with Multi2Sim and compared with other existing mechanisms [i.e., tamper-evident counter (TEC) tree and ASSURE] to demonstrate its performance and energy benefits. Experimental results using benchmarks from SPEC-CPU2006, SPLASH-2, and PARSEC show that the proposed dynamic integrity tree leads to an average reduction in instruction per cycle of 13% and 10% over TEC tree and ASSURE, respectively. The corresponding average reduction in authentication time is 30% and 20%, respectively. We show that the proposed framework facilitates the selection of a processor with a smaller cache size such that the energy consumption is reduced without sacrificing performance.

The efficiency can be significantly improved if the attacker uses interesting points to perform Correlation Power Analysis (CPA). The prerequisite for this is that the attacker knows the positions of interesting points. However, it is difficult for the attacker to accurately find the locations of interesting points if he only has a small number of power traces. In this paper, we propose a Frequency based Interesting Points Selection algorithm (FIPS) to select interesting points under the condition that the attacker only has a very small number of power traces. Moreover, an error tolerant Single Interesting Point based CPA (SIP-CPA) is proposed. Experiments on AES algorithm implemented on an AT89S52 single chip and power trace set of DPA contest v1 of DES algorithm implemented on the Side Channel Attack Standard Evaluation Board (SASEBO) show that, our SIP-CPA can significantly improve the efficiency of CPA.