A note on quantum related-key attacks

In a basic related-key attack against a block cipher, the adversary has access to encryptions under keys that differ from the target key by bit-flips. In this short note we show that for a quantum adversary such attacks are quite powerful: if the secret key is (i) uniquely determined by a small number of plaintext–ciphertext pairs, (ii) the block cipher can be evaluated efficiently, and (iii) a superposition of related keys can be queried, then the key can be extracted efficiently.     

Ciphertext-only attacks and weak long-term keys in T-310

T-310 is an important Cold War cipher (Schmeh 2006 Schmeh, K. 2006. The East German encryption machine T-310 and the algorithm it used. Cryptologia, 30(3):251–257.[Taylor &; Francis Online] , [Google Scholar]). It was the principal encryption algorithm used to protect various state communication lines in Eastern Germany in the 1980s. The cipher is quite robust, and it outputs extremely few bits from the internal state. In this article, the authors study the choice of the long-term key in T-310. They show that if a key is faulty, for example if they omit to check just one condition which the keys should satisfy, and more or less each time the round function is not bijective, communications can be decrypted in a ciphertext-only scenario. The authors provide mathematical proofs that the main historical key classes KT1 and KT2 are secure against such attacks.     

Elastic block ciphers: method, security and instantiations

We introduce the concept of an elastic block cipher which refers to stretching the supported block size of a block cipher to any length up to twice the original block size while incurring a computational workload that is proportional to the block size. Our method uses the round function of an existing block cipher as a black box and inserts it into a substitution- permutation network. Our method is designed to enable us to form a reduction between the elastic and the original versions of the cipher. Using this reduction, we prove that the elastic version of a cipher is secure against key-recovery attacks if the original cipher is secure against such attacks. We note that while reduction-based proofs of security are a cornerstone of cryptographic analysis, they are typical when complete components are used as sub-components in a larger design. We are not aware of the use of such techniques in the case of concrete block cipher designs. We demonstrate the general applicability of the elastic block cipher method by constructing examples from existing block ciphers: AES, Camellia, MISTY1, and RC6. We compare the performance of the elastic versions to that of the original versions and evaluate the elastic versions using statistical tests measuring the randomness of the ciphertext. We also use our examples to demonstrate the concept of a generic key schedule for block ciphers.

Linear cryptanalysis and block cipher design in East Germany in the 1970s

Linear cryptanalysis (LC) is an important codebreaking method that became popular in the 1990s and has roots in the earlier research of Shamir in the 1980s. In this article we show evidence that linear cryptanalysis is even older. According to documents from the former East Germany cipher authority ZCO, the systematic study of linear characteristics for nonlinear Boolean functions was routinely performed in the 1970s. At the same time East German cryptologists produced an excessively complex set of requirements known as KT1, which requirements were in particular satisfied by known historical used in the 1980s. An interesting line of inquiry, then, is to see if KT1 keys offer some level of protection against linear cryptanalysis. In this article we demonstrate that, strangely, this is not really the case. This is demonstrated by constructing specific counterexamples of pathologically weak keys that satisfy all the requirements of KT1. However, because we use T-310 in a stream cipher mode that uses only a tiny part of the internal state for actual encryption, it remains unclear whether this type of weak key could lead to key recovery attacks on T-310.     

How to decrypt or even substitute DES-encrypted messages in 2 steps

In this paper we analyze the complexity of recovering cryptographic keys when messages are encrypted under various keys. We suggest key-collision attacks, which show that the theoretic strength of a block cipher (in ECB mode) cannot exceed the square root of the size of the key space. As a result, in some circumstances, some keys can be recovered while they are still in use, and these keys can then be used to substitute messages by messages more favorable to the attacker (e.g., transfer $1000000 to bank account 123-4567890). Taking DES as our example, we show that one key of DES can be recovered with complexity 2²⁸, and one 168-bit key of (three-key) triple-DES can be recovered with complexity 2⁸⁴. We also discuss the theoretic strength of chaining modes of operation, and show that in some cases they may be vulnerable to such attacks.     

一种分组密码强化安全方法的研究

分析了级联加密的特点,讨论了分组密码的三种强化技术:密码级联技术、多重加密技术和白化技术,提出了一种双重级联加密方案NCC,并用现有的级联加密模式进行了比较,分析了其安全性和特点。同时为了减少密钥量,设计了一种密钥生成方案,用两个主密钥生成三个加密密钥,并且分析了它的安全性。     

Distinguishing attacks on stream ciphers based on arrays of pseudo-random words

In numerous modern stream ciphers, the internal state consists of a large array of pseudo-random words, while the output key-stream is a relatively simple function of the state. It has been heuristically shown in several situations [3], [8], [9], [10], [11] and [14] that this structure may lead to distinguishing attacks on the cipher. In this note we present a more rigorous treatment of this structural attack. First, we present a rigorous proof of the main probabilistic claim behind it in the basic cases. We then apply it concretely to the cipher sn3 [12], and demonstrate that the heuristic assumptions of the attack are remarkably precise in more complicated cases.     

混沌密码系统弱密钥随机性分析

弱密钥问题是混沌密码系统设计中的关键问题,已有研究主要从混沌序列退化角度进行分析.然而,本文指出保证混沌序列不退化的密钥参数仍可能构成混沌密码的弱密钥.本文提出以混沌密码序列随机性作为评价标准,应用严格的统计检验方法对混沌密码的弱密钥进行检测.进一步,对一类混沌密码系统进行了弱密钥研究,检测出了该系统大量未被发现的弱密钥.这确证了所提出方法的有效性.另一方面,虽然已有较多研究采用统计检验对混沌比特序列进行测试,但将统计检验用于分析混沌密码弱密钥或弱序列的研究还很少见.本文给出的统计检验弱序列分析,对当前混沌密码统计检验研究是一个很好的补充.     

Identifying Italian ciphers from continuous-figure ciphertexts (1593)

Italian ciphers of the 16th century often used Arabic figures written continuously without a break. The first step in reading such a ciphertext is to split the continuous sequence of figures into individual cipher symbols. However, this is not straightforward for codebreakers when the cipher symbols are not of fixed length. I succeeded in splitting the continuous sequence into individual symbols for three undeciphered ciphertexts from 1593, which all turned out to employ different schemes. Once the figures were broken into individual groups, the ciphers were simple enough to allow preliminary decipherment without knowledge of Italian.     

对8轮mCrypton-96的中间相遇攻击

在分析分组密码算法的安全性时,利用密钥关系来降低时间、存储和数据复杂度是一个常用的手段.在4轮mCrypton-96性质的基础上,利用密钥生成算法的弱点和S盒的性质,降低了攻击过程中需要猜测的密钥比特数,提出了对8轮mCrypton-96算法的中间相遇攻击,攻击的时间复杂度约为2\\+{93.5}次8轮mCrypton-96加密运算,存储复杂度为2\\+{47}B,数据复杂度为2\\+{57}个选择明文.     

关于Trivium-型序列密码代数次数估计的研究

对于序列密码,输出密钥流比特可以视为关于密钥变元和Ⅳ变元的布尔函数,而该布尔函数的代数次数是影响密码算法安全性的重要因素;当代数次数偏低时,密码算法抵抗代数攻击、立方攻击和积分攻击的能力比较弱.目前,针对Trivium-型序列密码算法,最有效的代数次数估计方法是数值映射方法和基于MILP的可分性质方法.本文通过分析两种典型方法的特点,结合两种方法的优势,对Trivium-型算法的代数次数估计进行了改进.我们利用改进后的方法对大量随机选取的Ⅳ变量集进行了实验.实验结果表明,对于Trivium-型算法,改进后的方法能够给出比数值映射方法更紧的代数次数上界.特别地,针对Trivium算法,当输入变元为全密钥变元和全Ⅳ变元时,即80个密钥变元和80个Ⅳ变元,输出比特代数次数未达到160的最大轮数从907轮提高到912轮,这是目前已知的全变元情形下的最优代数次数估计结果.     

Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem一个基于矩阵分解的非对称密码协议的分析

Advances in quantum computation threaten to break public key cryptosystems such as RSA, ECC, and ElGamal that are based on the difficulty of factorization or taking a discrete logarithm, although up to now, no quantum algorithms have been found that are able to solve certain mathematical problems on noncommutative algebraic structures. Against this background, Raulynaitis et al. have proposed a novel asymmetric cipher protocol using a matrix decomposition problem. Their proposed scheme is vulnerable to a linear algebra attack based on the probable occurrence of weak keys in the generation process. In this paper, we show that the asymmetric cipher of the non-commutative cryptography scheme is vulnerable to a linear algebra attack and that it only requires polynomial time to obtain the equivalent keys for some given public keys. We also propose an improvement to enhance the scheme of Raulynaitis et al.     

Soviet VIC Cipher: No Respector of Kerckoff's Principles

In this article, the author demonstrates that cracking the Soviet VIC cipher is possible if one knows the enciphering algorithm. Without this knowledge, the VIC cipher appears to be very strong, and it is almost impossible to crack a single message encrypted with it.     

Encryption System with Variable Number of Registers

Encryption in wireless communication systems is an extremely important factor to protect information and prevent fraud. In this paper, we propose a new encryption system for use in stream cipher applications. The design proposed is intended for hardware implementation and based on (n+1) feedback shift registers interconnected in such a way that one register controls the clocking of the other n registers. The aim of this construction is to allow the production of a large family of distinct keystreams when the initial states and feedback functions of the feedback shift registers are unchanged. The produced keystreams are shown to possess the basic security requirements for cryptographic sequences such as long period, high linear complexity and good statistical properties, provided that suitable parameters are chosen. Furthermore, the design is shown to resist various types of cryptanalytic attacks. These characteristics and properties enhance its use as a suitable encryption system for stream cipher applications.     

Construction of a polynomial invariant annihilation attack of degree 7 for T-310

Abstract

Cryptographic attacks are typically constructed by black-box methods and combinations of simpler properties, for example in [Generalised] Linear Cryptanalysis. In this article, we work with a more recent white-box algebraic-constructive methodology. Polynomial invariant attacks on a block cipher are constructed explicitly through the study of the space of Boolean polynomials which does not have a unique factorisation and solving the so-called Fundamental Equation (FE). Some recent invariant attacks are quite symmetric and exhibit some sort of clear structure, or work only when the Boolean function is degenerate. As a proof of concept, we construct an attack where a highly irregular product of seven polynomials is an invariant for any number of rounds for T-310 under certain conditions on the long term key and for any key and any IV. A key feature of our attack is that it works for any Boolean function which satisfies a specific annihilation property. We evaluate very precisely the probability that our attack works when the Boolean function is chosen uniformly at random.     

18TH CENTURY SHORTHAND EXPERT NEEDED (RE-RUN)

Abstract

Fialka M-125 (sometimes called the “Russian Enigma”) is an electro-mechanical rotor cipher machine used during the Cold War. The designers of this cipher eliminated the known weaknesses of Enigma. In this article, the authors summarize the main principle of the Fialka algorithm from public sources. Moreover, they introduce a mathematical model of the Fialka cipher, and they analyse the effect of blocking pin settings on the cipher's period.     

Fast correlation attack on streamcipher ABC v3

ABC v3 is a stream cipher submitted to the ECRYPT eStream project and has entered the second evaluation phase. Its key length is 128 bits. In this paper, we find large numbers of new weak keys of ABC family and introduce a method to search for them, and then apply a fast correlation attack to break ABC v3 with weak keys. We show that there are at least 2^103.71 new weak keys in ABC v3. Recovering the internal state of a weak key requires 236.05 keystream words and 2^50.56 operations. The attack can be applied to ABC vl and v2 with the same complexity as that of ABC v3. However, the number of weak keys of ABC vl as well as ABC v2 decreases to 2^97 ＋ 20^95.19,It reveals that ABC v3 incurs more weak keys than that of ABC vl and v2.     

Differential fault analysis on Camellia

Camellia is a 128-bit block cipher published by NTT and Mitsubishi in 2000. On the basis of the byte-oriented model and the differential analysis principle, we propose a differential fault attack on the Camellia algorithm. Mathematical analysis and simulating experiments show that our attack can recover its 128-bit, 192-bit or 256-bit secret key by introducing 30 faulty ciphertexts. Thus our result in this study describes that Camellia is vulnerable to differential fault analysis. This work provides a new reference to the fault analysis of other block ciphers.     

RC4密码的改进方法及其性能分析

针对RC4密码技术在工程应用中存在的弱密钥和相关密钥攻击、不变性弱点、数据流偏向性弱点等安全问题,提出一种将ECC技术与RC4技术相结合的方法。对改进后的RC4的数据处理效率、密钥管理、安全性能进行研究和分析。改进后的RC4技术在保证与RC4数据处理效率相近的同时,对当前针对RC4流密码的密码分析方法具有一定的抗攻击性。该技术较好地解决了密钥的共享和更新问题,具有重要的工程应用意义。