An efficient CRT-RSA algorithm secure against power and fault attacks

RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.     

A new zero value attack combined fault sensitivity analysis on masked AES

Recently, a new kind of fault-based attacks called fault sensitivity analysis (FSA) has been proposed, which has significant advantage over the traditional Differential Fault Attacks (DFA). However, the masking countermeasure could resist original FSA attack. In this paper, we first find the zero value sensitivity model in masked AES, and propose a new FSA method combined with zero value attack, which could break the masked AES S-box. To further verify our zero value method, successful attack experiments were conducted on a masked AES implemented in hardware. Experimental results and comparisons confirm that the zero value attack method is more efficient than other FSA methods because of retrieving the secret key by set up the experiment once with only one clock frequency. Moreover, the offline calculation of our zero value method is saved by eliminating the correlation coefficient calculations, and the 2⁸ times searches in key guess process are also omitted in our method.     

Security beyond cybersecurity: side-channel attacks against non-cyber systems and their countermeasures

Side-channels are unintended pathways within target systems that leak internal information, exploitable via side-channel attack techniques that extract the target information, compromising the system’s security and privacy. Side-channel attacks are well established within the cybersecurity domain, and thus their cyber-physical systems are actively defended with countermeasures. Non-cyber systems are equally as vulnerable to side-channel attacks; however, this is largely unrecognised and therefore countermeasures to defend them are limited. This paper surveys side-channel attacks against non-cyber systems and investigates the consequent security and privacy ramifications. Side-channel attack techniques rely on respective side-channel properties in order to succeed; therefore, countermeasures that disrupt each side-channel property are identified, effectively thwarting the side-channel attack. This principle is captured within a countermeasure algorithm: a systematic and extensible approach to identifying candidate countermeasures for non-cyber systems. We validate the output of this process by showing how the candidate countermeasures could be applied in the context of each non-cyber system and in the real world. This work provides an extensible platform for translating cybersecurity-derived side-channel attack research into defending systems from non-cyber domains.

     

Fault tolerance in cellular automata at high fault rates

A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. We are concerned with the degree (the number of neighboring cells on which the state transition function depends) needed to achieve fault tolerance when the fault rate is high (nearly 1/2). We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We also consider both a purely probabilistic fault model (in which the states of cells are perturbed at exactly the fault rate) and an adversarial model (in which the occurrence of a fault gives control of the state to an omniscient adversary). We show that there are cellular automata that can tolerate a fault rate 1/2−ξ (with ξ>0) with degree O((1/ξ²)log(1/ξ)), even with adversarial combined faults. The simplest such automata are based on infinite regular trees, but our results also apply to other structures (such as hyperbolic tessellations) that contain infinite regular trees. We also obtain a lower bound of Ω(1/ξ²), even with only purely probabilistic transient faults.     

On two DES implementations secure against differential power analysis in smart-cards

Masking is one of the efficient and easily implemented countermeasures to protect cryptographic algorithms in such resource limited environments as smart-cards from differential power analysis as well as simple power analysis that were first introduced by Kocher et al. in 1999. To defend differential power analysis attacks, Akkar and Giraud presented a Transformed Masking Method and applied it to DES implementation in 2001. Unfortunately, in 2003, Akkar and Goubin showed a superposition attack that actually is a high-order differential power analysis attack on Akkar and Giraud’s DES implementation using Transformed Masking Method, and finally they presented a DES implementation using their proposed Unique Masking Method to defend any order differential power analysis attacks, which was later improved by Akkar, Bévan and Goubin in 2004. In this paper, by exploiting a new artifice to classify the electric consumption curves, we show that Akkar, Bévan and Goubin’s improved DES implementation using Unique Masking Method is still vulnerable to a high-order differential power analysis attack. Besides, we find it is also vulnerable to a superposition attack. We also present four new differential power analysis attacks on Akkar and Giraud’s DES implementation using Transformed Masking Method.     

A general and efficient countermeasure to relation attacks in mix-based e-voting

A mix network is an anonymous communication channel usually employed in e-voting applications. A relation attack is a serious threat to privacy of any mix network and can attack various mix networks in many ways. At present, there is no efficient countermeasure to relation attacks in general. In this paper, a novel countermeasure against relation attacks is proposed. It can prevent any relation attack in mix-based e-voting schemes. It adopts a new encryption algorithm specially designed to be robust against relation attacks. The new countermeasure does not need any costly operation and is more efficient than the existing countermeasures. The new countermeasure is applied to voting and shown to work effectively. It is illustrated to protect the existing mix-based e-voting schemes from any relation attack.     

REPORT ON THE DECIPHERMENT OF THE AMERICAN STRIP CIPHER 0–2 BY THE GERMAN FOREIGN OFFICE

This paper presents a new attack on a block cipher, which is stronger than all previously considered attacks. This “chosen-key attack” is a generalization of the well accepted chosen-text attack. We give an example of a block cipher which is strong under a chosen-text attack, but immediately vulnerable to a chosen-key attack. A general chosen-key attack breaks an n bit key cipher in 2 ^n/2 operations. A black-box argument shows that this is the best possible for general attacks.     

A planner-based approach to generate and analyze minimal attack graph

In the present scenario, even well administered networks are susceptible to sophisticated cyber attacks. Such attack combines vulnerabilities existing on different systems/services and are potentially more harmful than single point attacks. One of the methods for analyzing such security vulnerabilities in an enterprise network is the use of attack graph. It is a complete graph which gives a succinct representation of different attack scenarios, depicted by attack paths. An attack path is a logical succession of exploits, where each exploit in the series satisfies the preconditions for subsequent exploits and makes a causal relationship among them. Thus analysis of the attack graph may help in assessing network security from hackers’ perspective. One of the intrinsic problems with the generation and analysis of such a complete attack graph is its scalability. In this work, an approach based on Planner, a special purpose search algorithm from artificial intelligence domain, has been proposed for time-efficient, scalable representation of the attack graphs. Further, customized algorithms have been developed for automatic generation of attack paths (using Planner as a low-level module). The analysis shows that generation of attack graph using the customized algorithms can be done in polynomial time. A case study has also been presented to demonstrate the efficacy of the proposed methodology.     

Analyzing Security Scenarios Using Defence Trees and Answer Set Programming

Defence trees are used to represent attack and defence strategies in security scenarios; the aim in such scenarios is to select the best set of countermeasures that are able to stop all the vulnerabilities.In order to represent preferences among possible countermeasures of a given attack, defence trees are enriched with conditional preferences, obtaining a new structure called CP-defence tree. In this paper we transform a CP-defence tree with preferences among attacks and countermeasures in an Answer Set Optimization (ASO) program. The ASO program, representing the overall scenario, is a special composition of the programs associated to each branch of a CP-defence tree. We describe an implementation that select the best set of countermeasure able to mitigate all the vulnerabilities by computing the optimal answer set of the corresponding ASO program.     

From zero-shot machine learning to zero-day attack detection

Machine learning (ML) models have proved efficient in classifying data samples into their respective categories. The standard ML evaluation methodology assumes that test data samples are derived from pre-observed classes used in the training phase. However, in applications such as Network Intrusion Detection Systems (NIDSs), obtaining data samples of all attack classes to be observed is challenging. ML-based NIDSs face new attack traffic known as zero-day attacks that are not used in training due to their non-existence at the time. Therefore, this paper proposes a novel zero-shot learning methodology to evaluate the performance of ML-based NIDSs in recognising zero-day attack scenarios. In the attribute learning stage, the learning models map network data features to semantic attributes that distinguish between known attacks and benign behaviour. In the inference stage, the models construct the relationships between known and zero-day attacks to detect them as malicious. A new evaluation metric is defined as Zero-day Detection Rate (Z-DR) to measure the effectiveness of the learning model in detecting unknown attacks. The proposed framework is evaluated using two key ML models and two modern NIDS data sets. The results demonstrate that for certain zero-day attack groups discovered in this paper, ML-based NIDSs are ineffective in detecting them as malicious. Further analysis shows that attacks with a low Z-DR have a significantly distinct feature distribution and a higher Wasserstein Distance range than the other attack classes.

     

Clustering Collision Power Attack on RSA-CRT

In this paper, we propose two new attack algorithms on RSA implementations with CRT (Chinese remainder theorem). To improve the attack efficiency considerably, a clustering collision power attack on RSA with CRT is introduced via chosen-message pairs. This attack method is that the key parameters d_p and d_q are segmented by byte, and the modular multiplication collisions are identified by k-means clustering. The exponents d_p and d_q were recovered by 12 power traces of six groups of the specific message pairs, and the exponent d was obtained. We also propose a second order clustering collision power analysis attack against RSA implementation with CRT, which applies double blinding exponentiation. To reduce noise and artificial participation, we analyze the power points of interest by preprocessing and k-means clustering with horizontal correlation collisions. Thus, we recovered approximately 91% of the secret exponents manipulated with a single power curve on RSA-CRT with countermeasures of double blinding methods.     

Efficient elliptic curve scalar multiplication algorithms resistant to power analysis

This paper presents four algorithms for securing elliptic curve scalar multiplication against power analysis. The highest-weight binary form (HBF) of scalars and randomization are applied to resist power analysis. By using a special method to recode the scalars, the proposed algorithms do not suffer from simple power analysis (SPA). With the randomization of the secret scalar or base point, three of the four algorithms are secure against differential power analysis (DPA), refined power analysis (RPA) and zero-value point attacks (ZPA). The countermeasures are also immune to the doubling attack. Fast Shamir’s method is used in order to improve the efficiency of parallel scalar multiplication. Compared with previous countermeasures, the new countermeasures achieve higher security and do not impact overall performance.     

Security analysis of CRT-based cryptosystems

A side channel attack (SCA) is a serious attack on the implementation of cryptosystems, which can break the secret key using side channel information such as timing, power consumption, etc. Recently, Boneh et al. showed that SSL is vulnerable to SCA if the attacker gets access to the local network of the server. Therefore, public-key infrastructure eventually becomes a target of SCA. In this paper, we investigate the security of RSA cryptosystem using the Chinese remainder theorem (CRT) in the sense of SCA. Novak first proposed a simple power analysis (SPA) against the CRT part using the difference of message modulo p and modulo q. In this paper, we apply Novak’s attack to the other CRT-based cryptosystems, namely Multi-Prime RSA, Multi-Exponent RSA, Rabin cryptosystem, and HIME(R) cryptosystem. Novak-type attack strictly depends on how to implement the CRT. We examine the operations related to CRT of these cryptosystems, and show that an extended Novak-type attack is effective on them. Moreover, we present a novel attack called zero-multiplication attack. The attacker tries to guess the secret prime by producing ciphertexts that cause a multiplication with zero during the decryption, which is easily detected by power analysis. Our experimental result shows that the timing with the zero multiplication is reduced about 10% from the standard one. Finally, we propose countermeasures against these attacks. The proposed countermeasures are based on the ciphertext blinding, but they require no inversion operation. The overhead of the proposed scheme is only about 1–5% of the whole decryption if the bit length of modulus is 1,024.     

故障模型下MORUS算法的差分扩散性质研究

MORUS算法是由H.Wu等人设计的一类认证加密算法,目前已顺利进入CAESAR竞赛第3轮竞选.研究MORUS算法故障模型下的差分扩散性质.采用面向比特的随机故障模型,结合差分分析技术与中间相遇思想,改进了针对MORUS算法的差分链搜索算法.运用该算法找到了5步概率为2^-85的差分链,从而实现了对初始化过程5步的简化版MORUS-640-128算法的差分-区分攻击,攻击所需的数据量和区分优势分别为2⁸⁹和0.99965.最后,利用差分故障分析方法对认证过程3步的简化版MORUS-640-128算法进行了伪造攻击.     

面向AES密码芯片的DPA攻击技术研究

给出针对AES密码芯片的DPA攻击实现方法,并基于Atmel-AES平台使用DPA攻击技术分析得到AES的密钥。证实AES算法面对DPA攻击时的脆弱性,同时也证明对AES芯片抗DPA攻击进行研究的必要性。     

Treatment of the initial value in Time-Memory-Data Tradeoff attacks on stream ciphers

Time-Memory Tradeoff (TMTO) attacks on stream ciphers are a serious security threat and the resistance to this class of attacks is an important criterion in the design of a modern stream cipher. TMTO attacks are especially effective against stream ciphers where a variant of the TMTO attack can make use of multiple data to reduce the off-line and the on-line time complexities of the attack (given a fixed amount of memory).In this paper we present a new approach to TMTO attacks against stream ciphers using a publicly known initial value (IV): We suggest not to treat the IV as part of the secret key material (as done in current attacks), but rather to choose in advance some IVs and apply a TMTO attack to streams produced using these IVs. We show that while the obtained tradeoff curve is identical to the curve obtained by the current approach, the new technique allows to mount the TMTO attack in a larger variety of settings. For example, if both the secret key and the IV are of length n, it is possible to mount an attack with data, time, and memory complexities of ²4n/5, while in the current approach, either the time complexity or the memory complexity is not less than n².     

A statistical unsupervised method against false data injection attacks: A visualization-based approach

To achieve intelligence in the future grid, a highly accurate state estimation is necessary as it is a prerequisite for many key functionalities in the successful operation of the power grid. Recent studies show that a new type of cyber-attack called False Data Injection (FDI) attack can bypass bad data detection mechanisms in the power system state estimation. Existing countermeasures might not be able to manage topology changes and integration of distributed generations because they are designed for a specific system configuration. To address this issue, an unsupervised method to distinguish between attack and normal patterns is proposed in this paper. This method can detect FDI attacks even after topology changes and integration of renewable energy sources. In this method, we assume that injecting false data into the power systems will lead to a deviation in the probability distribution of the state vector from the normal trend. The main phases of the proposed algorithm are: (1) Normalizing the dataset, (2) Adding several statistical measures as the new features to the dataset to quantify the probability distribution of the state vectors, (3) Employing principal component analysis to reduce the dimensionality of the dataset, (4) Visualizing the reduced data for humans and exploiting their creativity to detect attacks, and (5) Locating the attacks using Fuzzy C-means clustering algorithm.The proposed method is tested on both the IEEE 14-bus and IEEE 9-bus systems using real load data from the New York independent system operator with the following attack scenarios: (1) attacks without any topology change, (2) attacks after a contingency, and (3) attacks after integration of distributed generations. Experimental results show that our proposed method is superior to the state-of-the-art classification algorithms in dealing with changes. In addition, the reduced data which is helpful in distinguishing between attack and normal patterns can be fed into an expert system for further improvement of the security of the power grid.     

Security analysis of a new stream cipher

From 1st February of 2004, Europe launches the ECRYPT project, which collects lots of stream ciphers from all over the world. These new stream ciphers are unlike the tradi- tional stream ciphers that use LFSRs as basic building blocks; instead they use mo…     

On hash functions using checksums

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one-way checksum functions, is not secure against the second preimage attack of Kelsey and Schneier, the herding attack of Kelsey and Kohno and the multicollision attack of Joux. Our attacks also apply to a large class of cascaded hash functions. Our second preimage attacks on the cascaded hash functions improve the results of Joux presented at Crypto’04. We also apply our attacks to the MD2 and GOST hash functions. Our second preimage attacks on the MD2 and GOST hash functions improve the previous best known short-cut second preimage attacks on these hash functions by factors of at least 2²⁶ and 2⁵⁴, respectively. Our herding and multicollision attacks on the hash functions based on generic checksum functions (e.g., one-way) are a special case of the attacks on the cascaded iterated hash functions previously analysed by Dunkelman and Preneel and are not better than their attacks. On hash functions with easily invertible checksums, our multicollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman and Preneel.     

Faults, Injection Methods, and Fault Attacks

An active attacker can induce errors during the computation of the cryptographic algorithm and exploit the faulty results to extract information about the secret key in embedded systems. We call this kind of attack a fault attack. Fault attacks can break an unprotected system more quickly than any other kind of side-channel attack such as simple power analysis (SPA), differential power analysis (DPA), or electromagnetic analysis (EMA). For example, the attacker can break RSA-CRT (RSA with Chinese Remainder Theorem) with one faulty result, and Data Encryption Standard (DES) and Advanced Encryption Standard (AES) with two. Furthermore, the protection of fault attacks is more costly in terms of chip area. Here, we survey fault injection methods, types of faults, and fault attack models.