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.     

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.     

CRYPTOLOGY AND THE LAW

Abstract

Skipjack is a block cipher designed by the NSA for use in US government phones, and commercial mobile and wireless products by AT&;T. Among its initial implementations in hardware were the Clipper chip and Fortezza PC cards, which have since influenced the private communications market to be compatible with this technology. For instance, the Fortezza card comes in PCMCIA interface and is a very easy plug-n-play device to add on to mobile and wireless systems to provide encryption for wireless transmissions. Initially classified when it was first proposed, Skipjack was declassified in 1998, and it sparked numerous security analyses from security researchers worldwide because it provides insight into the state-of-the-art security design techniques used by a highly secretive government intelligence agency such as the NSA. In this paper, commemorating a decade since Skipjack's public revelation, we revisit the security of Skipjack, in particular its resistance to advanced differential-style distinguishers. In contrast to previous work that considered conventional and impossible differential distinguishers, we concentrate our attention on the more recent advanced differential-style and related-key distinguishers that were most likely not considered in the original design objectives of the NSA. In particular, we construct first-known related-key impossible differential, rectangle and related-key rectangle distinguishers of Skipjack. Our related-key attacks (i.e., related-key miss-in-the-middle and related-key rectangle attacks) are better than all the previous related-key attacks on Skipjack. Finally, we characterize the strength of Skipjack against all these attacks and motivate reasons why, influenced by the Skipjack structure, some attacks fare better. What is intriguing about Skipjack is its simple key schedule and a structure that is a cross between conventional Feistel design principles and the unconventional use of different round types. This work complements past results on the security analysis of Skipjack and is hoped to provide further insight into the security of an NSA-designed block cipher; the only one publicly known to date.     

基于正交表的概率加密体制

公开密钥密码体制易受到已知明文密文攻击，如何安全有效地进行数据加密，是现代密码学中最重要的问题，本文给出了一种特殊的正交表，并基于这种正交表和离散对数问题给出了新的概率加密方案，最后，对该密码体制的安全性进行了分析。     

Hill密码加密解密时矩阵的求法

在计算机网络中,为了保证数据的安全,常常要对数据进行加密和解密。文章运用数学知识和Madab语言,介绍了Hill密码加密时如何给出密钥矩阵以及解密时如何求密钥矩阵的逆,从而实现Hill密码快速加密和解密。     

CH混沌序列图像加密算法分析

分析了一个基于混沌序列的图像加密算法的安全性,发现该加密算法本质上是一个移位密码且密钥空间太小,利用古典密码中对移位密码的分析方法得到混沌序列,进而给出了穷举参数求解其密钥的已知明文攻击方法。对于大小为M×N的明文图像,该攻击方法的计算复杂性为O(M+N)。理论分析和实验结果均表明该图像加密算法是不安全的。     

FROM THE ARCHIVES: U-BOAT HF WT SIGNALLING

A Royal Navy document on U-boat radio procedures in WWI is reproduced, with annotations.     

NUGGETS FROM THE ARCHIVES: YARDLEY TRIES AGAIN

Several readers solved the HC-9 challenge ciphier and describe how they did it. Another challenge message using a different alphabet sheet and punched card, plus a less obvious key then used previously, is provided. Lengthy plaintext with matching ciphertext offers some help.     

Impossible differential cryptanalysis of advanced encryption standard

Impossible differential cryptanalysis is a method recovering secret key, which gets rid of the keys that satisfy impossible differential relations. This paper concentrates on the impossible differential cryptanalysis of Advanced Encryption Standard (AES) and presents two methods for impossible differential cryptanalysis of 7-round AES-192 and 8-round AES-256 combined with time-memory trade-off by exploiting weaknesses in their key schedule. This attack on the reduced to 7-round AES-192 requires about 294.5 chosen plaintexts, demands 2129 words of memory, and performs 2157 7-round AES-192 encryptions. Furthermore, this attack on the reduced to 8-round AES-256 requires about 2101 chosen plaintexts, demands 2201 words of memory, and performs 2228 8-round AES-256 encryptions.     

一种基于Hill密码思想的数据库密码编码算法

由于数据库系统仅支持ASC Ⅱ字符集中的可打印字符，将加密后的记录编码成可打印字符是保证数据库系统正常运行的关键，文中将这一过程称作密文编码。许多现有算法不能将对记录的加密和编码过程结合起来，在时间效率或安全性上存在不足。本文提出一种基于Hill密码思想的数据库密文编码算法，该算法将对记录的加密和加密后的编码合为一个过程，可以很好地解决数据库记录加密和编码问题。它实际上是一种对数据库记录的双重保护机制，具有比同类算法更高的安全性和时间效率。文中还分析了该算法的时间复杂性和安全性，最后提出了下一步的研究方向和目标。     

Lester Hill Revisited

Abstract

Lester Sanders Hill (1890–1961) is best known for the Hill cipher which he published in 1929. However, there seem to be four periods of Hill's career. First, in 1926 and 1927, Hill published a series of papers on mathematical error-detection. Hill's ideas for error-detection are similar to the ideas he used in his cipher. Next, in 1929 and 1931, Hill published two papers that describe the Hill cipher. The third period of Hill's career, from 1927 until 1960, was the time he served on the mathematics faculty of Hunter College. During his time at Hunter College, Hill seems to have had a relationship with the Navy in which he served during World War I. Finally, while teaching at Hunter College, in the 1950s, Hill wrote his “later papers” on cryptography, which were not published but were sent to Naval Communications.     

HOW TO MAKE THE HILL CIPHER SECURE

ABSTRACT

This paper presents a symmetric cipher that is actually a variation of the Hill cipher. The new scheme makes use of “random” permutations of columns and rows of a matrix to form a “different” key for each data encryption. The cipher has matrix products and permutations as the only operations which may be performed “efficiently” by primitive operators, when the system parameters are carefully chosen.     

A TENSOR-THEORETIC ENHANCEMENT TO THE HILL CIPHER SYSTEM

The Hill matrix algorithm[3], published in 1929, is known for being the first purely algebraic cryptographic system and for starting the entire field of algebraic cryptology. In this paper, an operator derived from ring isomorphism theory is adapted for use in the Hill system which greatly increases the block size that a matrix can encrypt; specifically, a k×k invertible matrix over Z _n represents an invertible matrix of order k ³, which produces ciphertext blocks k ²-times as long as the original matrix could. This enhancement increases the Hill system's security considerably.     

多重线性密码分析中线性逼近方程的构造

到目前为止,还没有利用构造多个逼近方程来实现B.S.Kaliski和M.J.B.Robshaw的多重线性逼近的例子。利用Mastui构造的线性组合传递链是周期为8的线性组合传递链这个特点,选取该线性组合传递链的8个不同起点,就可由该线性组合传递链构造出8条新的线性组合传递链,再加上其对偶的线性组合传递链,共可构造出16条线性组合传递链,利用它们可实现对DES的密钥比特进行攻击。     

针对简化版Trivium算法的线性分析

流密码Trivium算法是欧洲密码工程eSTREAM的7个最终获选算法之一.该文针对初始化为288轮的简化版Trivium算法进行了线性分析,更正了Turan等人给出的关于密钥、初始化向量和密钥流比特的表达式,并给出了当允许选取特殊的密钥和Ⅳ时,搜索最佳线性逼近式的算法.据此算法,找到了3个线性偏差为2-25的线性逼近式,改进了Turan等人给出的线性偏差为2-31的线性分析结果.     

Format-preserving encryption: Overview and NIST specification

This article reviews the concepts of and motivation for format-preserving encryption (FPE), and then describes three FPE algorithms approved by the National Institute of Standards and Technology (NIST).     

FROM THE ARCHIVES JAPANESE FEARS AND THE IRONIES OF INTERCEPTION

ABSTRACT

The author presents two 1940 intercepts from the GC & CS archive dealing with Japanese disquiet over the resumption of American Black Chamber activities.     

数据置乱算法的分析

基于二维矩阵信号乱序原理的数据信息置乱算法,以下简称MDA算法,是一种用于计算机文件的方便、快速的加密算法。综观该算法的加密方式,我们从密码分析学的角度对其进行了分析,并提出了改进的方法。