Attacks on Fast Double Block Length Hash Functions

The security of hash functions based on a block cipher with a block length of m bits and a key length of k bits, where , is considered. New attacks are presented on a large class of iterated hash functions with a 2m -bit hash result which processes in each iteration two message blocks using two encryptions. In particular, the attacks break three proposed schemes: Parallel-DM, the PBGV hash function, and the LOKI DBH mode. Received 1 March 1996 and revised 16 December 1996     

KeeLoq密码Courtois攻击方法的分析和修正

KeeLoq密码是由Willem Smit设计的分组密码算法,广泛应用于汽车的无线门锁装置。Courtois等人在2007年提出了破译KeeLoq的4种滑动-代数攻击方法,其中第4种滑动-代数攻击方法的计算复杂性最小。本文证明了Courtois的第4种滑动-代数攻击方法的攻击原理是错误的,因而无法实现对KeeLoq的破译。此外,本文还对该方法进行了修正,提出了改进的攻击方法,利用232个已知明文能够以O(248) 次加密的计算复杂性求出KeeLoq密码的密钥,成功率为1。对于KeeLoq密码26％的密钥,其连续64圈圈函数形成的复合函数至少具有两个不动点,此时改进的攻击方法的计算复杂性还可降至O(248) 次加密。     

Security analysis of pure DDP-based cipher proper for multimedia and ubiquitous device

DDP-64, based on various controlled operations, is a 64-bit Feistel-like block cipher consisting of 10 rounds with a 128-bit key. It was designed to attempt to have a high security level and a high speed performance in hardware on ubiquitous computing systems and multimedia. In this paper, however, we show that DDP-64 doesn’t have a high security level, more precisely, we show that it is vulnerable to related-key differential attack. This attack, which is much faster than the key exhaustive search, requires about 2⁵⁴ data and 2⁵⁴ time complexities. This work is the first known cryptanalytic result on DDP-64 so far.     

A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony

Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2^?14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 2²⁶ data, 2³⁰ bytes of memory, and 2³² time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.     

Robust smart‐card‐based remote user password authentication scheme

Smart‐card‐based remote user password authentication schemes are commonly used for providing authorized users a secure method for remotely accessing resources over insecure networks. In 2009, Xu et al. proposed a smart‐card‐based password authentication scheme. They claimed their scheme can withstand attacks when the information stored on the smart card is disclosed. Recently, Sood et al. and Song discovered that the smart‐card‐based password authentication scheme of Xu et al. is vulnerable to impersonation and internal attacks. They then proposed their respective improved schemes. However, we found that there are still flaws in their schemes: the scheme of Sood et al. does not achieve mutual authentication and the secret key in the login phase of Song's scheme is permanent and thus vulnerable to stolen‐smart‐card and off‐line guessing attacks. In this paper, we will propose an improved and efficient smart‐card‐based password authentication and key agreement scheme. According to our analysis, the proposed scheme not only maintains the original secret requirement but also achieves mutual authentication and withstands the stolen‐smart‐card attack. Copyright © 2012 John Wiley & Sons, Ltd.     

Efficient Slide Attacks

The slide attack, presented by Biryukov and Wagner, has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by \(2^n\) (where n is the block size). There are only a few known scenarios in which the slide attack performs better than the \(2^n\) bound. In this paper, we concentrate on efficient slide attacks, whose time complexity is less than \(2^n\). We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least \(2^n\) operations. In particular, we present the first known slide attack on a Feistel construction with a 3-round self-similarity, and an attack with practical time complexity of \(2^{40}\) on a 128-bit key variant of the GOST block cipher with unknown S-boxes. The best previously known attack on the same variant, with known S-boxes (by Courtois), has time complexity of \(2^{91}\).     

基于AES算法改进的蓝牙安全机制研究

对蓝牙安全机制鉴权过程中的加密算法进行了研究.分析了目前采用的基于序列密码的加密算法存在的安全隐患,提出利用分组密码实现加密的思路.详细讨论了蓝牙鉴权过程中的各类攻击方式,从硬件和软件两个方面阐述了防范的措施.对128位AES加密算法进行了研究和改进,使之能够适用于运算速度相对较低、存储资源相对较少的蓝牙移动系统环境.测试表明,改进后的AES算法可以为蓝牙的鉴权过程提供更为可靠的安全保证.     

Structural Cryptanalysis of SASAS

In this paper we consider the security of block ciphers which contain alternate layers of invertible S-boxes and affine mappings (there are many popular cryptosystems which use this structure, including the winner of the AES competition, Rijndael). We show that a five-layer scheme with 128-bit plaintexts and 8-bit S-boxes is surprisingly weak against what we call a multiset attack, even when all the S-boxes and affine mappings are key dependent (and thus completely unknown to the attacker). We tested the multiset attack with an actual implementation, which required just 2¹⁶ chosen plaintexts and a few seconds on a single PC to find the 2¹⁷ bits of information in all the unknown elements of the scheme.     

Improved impossible differential and biclique cryptanalysis of HIGHT

HIGHT is a lightweight block cipher introduced in CHES 2006 by Hong et al as a block cipher suitable for low‐resource applications. In this paper, we propose improved impossible differential and biclique attacks on HIGHT block cipher both exploiting the permutation‐based property of the cipher's key schedule algorithm as well as its low diffusion. For impossible differential attack, we found a new 17‐round impossible differential characteristic that enables us to propose a new 27‐round impossible differential attack. The total time complexity of the attack is 2^120.4 where an amount of 2^59.3 chosen plaintext‐ciphertext pairs and 2^107.4 memory are required. We also instantiate a new biclique cryptanalysis of HIGHT, which is based on the new idea of splitting each of the forward and backward keys into 2 parts where the computations associated to each one are performed independently. The time complexity and data complexity of this attack are 2^125.7 and 2⁴², respectively. To the best of our knowledge, this is the fastest biclique attack on full‐round HIGHT.     

Partial Key Recovery Attack Against RMAC

In this paper new “partial” key recovery attacks against the RMAC block cipher based Message Authentication Code scheme are described. That is we describe attacks that, in some cases, recover one of the two RMAC keys much more efficiently than previously described attacks. Although all attacks, but one, are of no major threat in practice, in some cases there is reason for concern. In particular, the recovery of the second RMAC key (of k bits) may only require around 2^k/2 block cipher operations (encryptions or decryptions). The RMAC implementation using triple DES proposed by NIST is shown to be very weak.     

基于FPGA平台的Piccolo功耗分析安全性评估

为了评估Piccolo密码算法的功耗分析安全性,该文提出一种针对Piccolo末轮的攻击模型,基于SASEBO (Side-channel Attack Standard Evaluation BOard)实测功耗数据对该算法进行了相关性功耗分析攻击。针对Piccolo末轮运算中包含白化密钥的特点,将末轮攻击密钥(包括轮密钥RK24L, RK24R, WK2, WK3)分成4段子密钥,逐个完成各个子密钥的攻击,使80位种子密钥的搜索空间从280降低到(2220+2212+216),使种子密钥的恢复成为可能。攻击结果表明,在实测功耗数据情况下,3000条功耗曲线即可恢复80位种子密钥,证实了该攻击模型的有效性和Piccolo硬件面向功耗分析的脆弱性,研究并采取切实有效的防护措施势在必行。     

A quantization-based semi-fragile watermarking scheme for image content authentication

This paper presents a novel semi-fragile watermarking scheme for image content authentication with tampering localization. The proposed scheme uses a non-traditional quantization method to modify one chosen approximation coefficient of each non-overlapping block to ensure its robustness against incidental attacks and fragileness against malicious attacks. The image content authentication starts with extracting watermark using the parity of quantization results from the probe image, where the round operation is used to ensure the semi-fragile property. It then constructs a binary error map and computes two authentication measures with M₁ measuring the overall similarity between extracted and embedded watermarks and M₂ measuring the overall clustering level of tampered error pixels. These two measures are further integrated to confirm the image content and localize the possible tampered areas. Our experimental results show that our scheme outperforms four peer schemes and is capable of identifying intentional tampering and incidental modification, and localizing tampered regions.     

Cryptanalysis and security enhancement of a robust two‐factor authentication and key agreement protocol

Two‐factor user authentication scheme allows a user to use a smart card and a password to achieve mutual authentication and establish a session key between a server and a user. In 2012, Chen et al. showed that the scheme of Sood et al. does not achieve mutual authentication and is vulnerable to off‐line password guessing and smart card stolen attacks. They also found that another scheme proposed by Song is vulnerable to similar off‐line password guessing and smart card stolen attacks. They further proposed an improved scheme. In this paper, we first show that the improved scheme of Chen et al. still suffers from off‐line password guessing and smart card stolen attacks, does not support perfect forward secrecy, and lacks the fairness of session key establishment. We then propose a new security‐enhanced scheme and show its security and authentication using the formal verification tool ProVerif, which is based on applied pi calculus. Copyright © 2014 John Wiley & Sons, Ltd.     

Secure Remote User Mutual Authentication Scheme with Key Agreement for Cloud Environment

Authentication schemes are widely used mechanisms to thwart unauthorized access of resources over insecure networks. Several smart card based password authentication schemes have been proposed in the literature. In this paper, we demonstrate the security limitations of a recently proposed password based authentication scheme, and show that their scheme is still vulnerable to forgery and offline password guessing attacks and it is also unable to provide user anonymity, forward secrecy and mutual authentication. With the intention of fixing the weaknesses of that scheme, we present a secure authentication scheme. We show that the proposed scheme is invulnerable to various attacks together with attacks observed in the analyzed scheme through both rigorous formal and informal security analysis. Furthermore, the security analysis using the widely-accepted Real-Or-Random (ROR) model ensures that the proposed scheme provides the session key (SK) security. Finally, we carry out the performance evaluation of the proposed scheme and other related schemes, and the result favors that the proposed scheme provides better trade-off among security and performance as compared to other existing related schemes.

     

On the Importance of Eliminating Errors in Cryptographic Computations

We present a model for attacking various cryptographic schemes by taking advantage of random hardware faults. The model consists of a black-box containing some cryptographic secret. The box interacts with the outside world by following a cryptographic protocol. The model supposes that from time to time the box is affected by a random hardware fault causing it to output incorrect values. For example, the hardware fault flips an internal register bit at some point during the computation. We show that for many digital signature and identification schemes these incorrect outputs completely expose the secrets stored in the box. We present the following results: (1) The secret signing key used in an implementation of RSA based on the Chinese Remainder Theorem (CRT) is completely exposed from a single erroneous RSA signature, (2) for non-CRT implementations of RSA the secret key is exposed given a large number (e.g. 1000) of erroneous signatures, (3) the secret key used in Fiat—Shamir identification is exposed after a small number (e.g. 10) of faulty executions of the protocol, and (4) the secret key used in Schnorr's identification protocol is exposed after a much larger number (e.g. 10,000) of faulty executions. Our estimates for the number of necessary faults are based on standard security parameters such as a 1024-bit modulus, and a 2 ^-40 identification error probability. Our results demonstrate the importance of preventing errors in cryptographic computations. We conclude the paper with various methods for preventing these attacks. Received July 1997 and revised August 2000 Online publication 27 November, 2000     

Quantum rebound attacks on reduced-round ARIA-based hash functions

ARIA is a block cipher proposed by Kwon et al. at ICISC 2003 that is widely used as the national standard block cipher in the Republic of Korea. Herein, we identify some flaws in the quantum rebound attack on seven-round ARIA-DM proposed by Dou et al. and reveal that the limit of this attack is up to five rounds. Our revised attack applies to not only ARIA-DM but also ARIA-MMO and ARIA-MP among the PGV models, and it is valid for all ARIA key lengths. Furthermore, we present dedicated quantum rebound attacks on seven-round ARIA-Hirose and ARIA-MJH for the first time. These attacks are only valid for the 256-bit key length of ARIA because they are constructed using the degrees of freedom in the key schedule. All our attacks are faster than the generic quantum attack in the cost metric of the time–space tradeoff.     

The Full Cost of Cryptanalytic Attacks

An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanks method for computing discrete logarithms in cyclic groups of prime order n, which requires n^1/2+o(1) processor steps, but, when all factors are taken into account, has full cost n^2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.     

VLSI design of an RSA encryption/decryption chip using systolic array based architecture

This article presents the VLSI design of a configurable RSA public key cryptosystem supporting the 512-bit, 1024-bit and 2048-bit based on Montgomery algorithm achieving comparable clock cycles of current relevant works but with smaller die size. We use binary method for the modular exponentiation and adopt Montgomery algorithm for the modular multiplication to simplify computational complexity, which, together with the systolic array concept for electric circuit designs effectively, lower the die size. The main architecture of the chip consists of four functional blocks, namely input/output modules, registers module, arithmetic module and control module. We applied the concept of systolic array to design the RSA encryption/decryption chip by using VHDL hardware language and verified using the TSMC/CIC 0.35 m 1P4 M technology. The die area of the 2048-bit RSA chip without the DFT is 3.9 × 3.9 mm² (4.58 × 4.58 mm² with DFT). Its average baud rate can reach 10.84 kbps under a 100 MHz clock.     

Quark: A Lightweight Hash

The need for lightweight (that is, compact, low-power, low-energy) cryptographic hash functions has been repeatedly expressed by professionals, notably to implement cryptographic protocols in RFID technology. At the time of writing, however, no algorithm exists that provides satisfactory security and performance. The ongoing SHA-3 Competition will not help, as it concerns general-purpose designs and focuses on software performance. This paper thus proposes a novel design philosophy for lightweight hash functions, based on the sponge construction in order to minimize memory requirements. Inspired by the stream cipher Grain and by the block cipher KATAN (amongst the lightest secure ciphers), we present the hash function family Quark, composed of three instances: u-Quark, d-Quark, and s-Quark. As a sponge construction, Quark can be used for message authentication, stream encryption, or authenticated encryption. Our hardware evaluation shows that Quark compares well to previous tentative lightweight hash functions. For example, our lightest instance u-Quark conjecturally provides at least 64-bit security against all attacks (collisions, multicollisions, distinguishers, etc.), fits in 1379 gate-equivalents, and consumes on average 2.44 μW at 100 kHz in 0.18 μm ASIC. For 112-bit security, we propose s-Quark, which can be implemented with 2296 gate-equivalents with a power consumption of 4.35 μW.     

Multimedia Broadcast Authentication Based on Batch Signature [Advances in Mobile Multimedia]

Conventional block-based broadcast authentication protocols overlook the heterogeneity of receivers in mobile computing by letting the sender choose the block size, divide a broadcast stream into blocks, associate each block with a signature, and spread the effect of the signature across all the packets in the block through hash or coding algorithms. They suffer from some drawbacks. First, they require that the entire block with its signature be collected before authenticating every packet in the block. This authentication latency can lead to the jitter effect on real-time applications at receivers. Second, the block-based approach is vulnerable to packet loss in mobile computing in the sense that the loss of some packets makes the other packets unable to be authenticated, especially when the block signature is lost. Third, they are also vulnerable to DoS attacks caused by the injection of forged packets. In this article we propose a novel broadcast authentication protocol based on an efficient cryptographic primitive called a batch signature. Our protocol supports the verification of the authenticity of any number of packets simultaneously and avoids the shortcomings of the block-based approach.