Cryptanalysis of columnar transposition cipher with long keys

The classical columnar transposition cipher was the most popular type of transposition cipher. It was in use mainly during the second half of the nineteenth century and the first half of the twentieth century. It also served as a building block for more complex ciphers, such as the ADFGVX cipher and the double transposition cipher. Pen-and-paper as well as computerized methods for the cryptanalysis of the columnar transposition cipher have been published, but those apply mainly to the easier cases of short keys and complete transposition rectangles. In this article, a novel approach for the cryptanalysis of the columnar transposition cipher (when used with long keys) is presented. It is based on a two-phase hill climbing algorithm, a two-dimensional fitness score, and special transformations on key segments. This ciphertext-only method allows for the recovery of transposition keys with up to 1,000 elements, and up to 120 elements for worst case transposition rectangles.     

一个基于混沌系统的动态换位加密方案

在对换位加密技术研究的基础上,提出了一个基于混沌系统的动态换位加密方案。该方案通过二进制数据转换、数据替换及动态换位等加密步骤,很好地实现了明文的混淆与扩散。与传统的换位加密相比,新方案不仅有较大的密钥空间,而且产生的换位序列具有很强的随机性。理论分析及实验结果表明,给出的新方案可以抵抗多种已知的密码攻击,克服了传统换位加密技术的弱点,具有较高的安全性。     

MY RECOLLECTIONS OF G.2 A.6

Abstract

In this article, we consider an attack on the SIGABA cipher under the assumption that the largest practical keyspace is used. The attack highlights various strengths and weaknesses of SIGABA and provides insight into the inherent level of security provided by the cipher.     

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.

James Sanborn’s Kryptos and the matrix encryption conjecture

James Sanborn’s sculpture, Kryptos, commissioned by the CIA, consists (in part) of four enciphered messages. These have attracted a tremendous amount of attention, and only the first three have been solved. In the present article, the authors provide a brief summary of each cipher and examine evidence that the fourth makes use of matrix encryption. They also provide results of brute force attacks for the 2 × 2 and 3 × 3 cases. Sanborn’s latest hint was of great value in testing these possibilities. Room for further testing is indicated for those wishing to continue the attack.     

ZF-02分组密码算法的设计与分析

提出了一种以换位变换为核心的分组密码算法(ZF-02算法)．该算法的分组长度为128bits，密钥长度可变．其加解密算法的基本结构可归结为：密钥控制下的入口状态复合换位变换、非线性性能良好的可逆置换和密钥控制下的出口状态复合换位变换．该算法逻辑结构简洁规范，而且易于在软、硬件及多种环境下实现．文中给出了算法的加解密流程和必要的数据参数表，并对其安全性做了基本分析，结果表明它拥有相当好的安全性．     

基于混沌序列和分组密码的数字图像置乱技术

给出了一种全新的数字图像置乱方案,其中混沌序列用于给出分组密码算法的初始密钥,分组密码采用以换位变换为核心的ZF-02分组密码算法.该算法的优点是能够很好地抵抗线性、差分等多种攻击,又易于软、硬件实现.     

A related key impossible differential attack against 22 rounds of the lightweight block cipher LBlock

LBlock is a new lightweight block cipher proposed by Wu and Zhang (2011) [12] at ACNS 2011. It is based on a modified 32-round Feistel structure. It uses keys of length 80 bits and message blocks of length 64 bits.In this letter, we examine the security arguments given in the original article and we show that we can improve the impossible differential attack given in the original article on 20 rounds by constructing a 22-round related key impossible differential attack that relies on intrinsic weaknesses of the key schedule. This attack has a complexity of 2⁷⁰ cipher operations using 2⁴⁷ plaintexts. This result was already published in Minier and Naya-Plasencia (2011) [9].     

HOW STATISTICS LED THE GERMANS TO BELIEVE ENIGMA SECURE AND WHY THEY WERE WRONG: NEGLECTING THE PRACTICAL MATHEMATICS OF CIPHER MACHINES

Only in 1974 did German intelligence and cryptologists admit that the Enigma cipher machine was not, and had not been, a secure system. Throughout World War II, German experts relied on a theoretical statistical security that took neither wartime operational reality nor their opponents' years of attention and attack into account. They ignored the far more important operational weaknesses and human errors that actually provided enemy cryptanalysts with their most valuable entries into the cipher system.     

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.     

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

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

CRYPTANALYSTS' CORNER

Abstract

The Hill cipher, also known as matrix encryption, is a polygraphic substitution cipher, developed by the mathematician Lester S. Hill in 1929. While various attacks had been known on the Hill cipher, the ciphertext-only attack without assumptions about the encryption matrix or probable plaintext words was introduced only recently by Bauer and Millward. They obtained high efficiency of attack by recovering the decryption matrix row by row rather than all rows at once. In this paper, we extend their ciphertext-only attack in two ways. First, we present a better scoring system for cryptanalysis based on the goodness-of-fit statistics. Specifically, we reduce the average number of candidate rows from 24.83 to 7.00 for 3 × 3 matrix and from 4027.78 to 1220.38 for 4 × 4 matrix. Second, we show how to apply our attacks to the Hill cipher without knowing the numeric equivalents of the letters of the plaintexts.     

A practical distinguisher for the Shannon cipher

In this paper, we present a practical linear distinguisher on the Shannon stream cipher. Shannon is a synchronous stream cipher that uses at most 256-bit secret key. In the specification for Shannon, designers state that the intention of the design is to make sure that there are no distinguishing attacks on Shannon requiring less than 2⁸⁰ keystream words and less than 2¹²⁸ computations. In this work we use the Crossword Puzzle attack technique to construct a distinguisher which requires a keystream of length about 2³¹ words with workload about 2³¹.     

Immunity against Correlation Attack on Quantum Stream Cipher by Yuen 2000 Protocol

This paper presents the security analysis on the quantum stream cipher so called Yuen-2000 protocol (or αη scheme) against the fast correlation attack, the typical attack on stream ciphers. Although the security of a very simple experimental model of the quantum stream cipher without a randomization may be reduced to a complexity based security against the correlation attacks under a large number of known plaintexts, it is not a basic feature of Yuen 2000 protocol. In fact, we clarify that there exists a randomization scheme which attains the perfect correlation immunity against such attacks under an approximation. And in this scheme, the running key correlation from the second randomization that determines the mapping patterns is broken off also by quantum noise. In such a case, any fast correlation attack does not work on the quantum stream cipher.      

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.     

Slide attacks and LC-weak keys in T-310

T-310 is an important Cold War cipher (Cryptologia 2006). In a recent article (Cryptologia 2018), researchers show that, in spite of specifying numerous very technical requirements, the designers do not protect the cipher against linear cryptanalysis and some 3% of the keys are very weak. However, such a weakness does not necessarily allow breaking the cipher because it is extremely complex and extremely few bits from the internal state are used for the actual encryption. In this article, we finally show a method that allows recovering a part of the secret key for about half of such weak keys in a quasi-realistic setting. For this purpose, we revisit another recent article from Cryptologia from 2018 and introduce a new peculiar variant of the decryption oracle slide attack with d?=?0.     

随机分组密码算法框架及实现

针对现有的对分组密码的攻击方法对于未知结构的密码算法是无效的特点,提出了一个根据已有分组密码算法生成随机密码算法的框架,其密码算法是由随机控制密钥生成的,因而算法是随机的,能抵抗针对固定结构的密码算法的线性密码分析和差分密码分析。同时还提出了一个具体的AES的随机化算法,该算法具有可证明的安全性,其安全性高于原始的AES,性能与原始的AES算法接近。     

Commentary on Alan M. Turing: The Applications of Probability to Cryptography

Abstract

In April 2012, two papers written by Alan Turing during the Second World War on the use of probability in cryptanalysis were released by GCHQ. The longer of these presented an overall framework for the use of Bayes's theorem and prior probabilities, including four examples worked out in detail: the Vigenère cipher, a letter subtractor cipher, the use of repeats to find depths, and simple columnar transposition. (The other paper was an alternative version of the section on repeats.) Turing stressed the importance in practical cryptanalysis of sometimes using only part of the evidence or making simplifying assumptions and presents in each case computational shortcuts to make burdensome calculations manageable. The four examples increase roughly in their difficulty and cryptanalytic demands. After the war, Turing's approach to statistical inference was championed by his assistant in Hut 8, Jack Good, which played a role in the later resurgence of Bayesian statistics.     

基于字的流密码Dragon的分析

研究一种新型的流密码——Dragon。Dragon使用了非线性反馈移位寄存器(NLFSR)和S盒,密钥长度是可变的128 bit或256 bit。探讨了Dragon的设计原理,从内部结构角度分析讨论其安全性,指出Dragon对暴力攻击和TMD攻击是安全的,同时构造了Dragon的线性逼近式,给算法提了2点建议。