Information Security and Privacy : Proceedings of the 9th Australasian Conference, ACISP 2004, Sydney, Australia, July 13-15, 2004.

Preface The 9th Australasian Conference on Information Security and Privacy (ACISP 2004) was held in Sydney, 13–15 July, 2004. The conference was sponsored by the Centre for Advanced Computing – Algorithms and Cryptography (ACAC), Information and Networked Security Systems Research (INSS), Macquarie University and the Australian Computer Society. The aims of the conference are to bring together researchers and practitioners working in areas of information security and privacy from universities, industry and government sectors. The conference program covered a range of aspects including cryptography, cryptanalysis, systems and network security. The program committee accepted 41 papers from 195 submissions. The reviewing process took six weeks and each paper was carefully evaluated by at least three members of the program committee. We appreciate the hard work of the members of the program committee and external referees who gave many hours of their valuable time. Of the accepted papers, there were nine from Korea, six from Australia, five each from Japan and the USA, three each from China and Singapore, two each from Canada and Switzerland, and one each from Belgium, France, Germany, Taiwan, The Netherlands and the UK. All the authors, whether or not their papers were accepted, made valued contributions to the conference. In addition to the contributed papers, Dr Arjen Lenstra gave an invited talk, entitled Likely and Unlikely Progress in Factoring. This year the program committee introduced the Best Student Paper Award. The winner of the prize for the Best Student Paper was Yan-Cheng Chang from Harvard University for his paper Single Database Private Information Retrieval with Logarithmic Communication. We would like to thank all the people involved in organizing this conference. In particular we would like to thank members of the organizing committee for their time and efforts, Andrina Brennan, Vijayakrishnan Pasupathinathan, Hartono Kurnio, Cecily Lenton, and members from ACAC and INSS.

Analysis of one-pass block cipher based authenticated encryption schemes

This project analyses and evaluates the integrity assurance mechanisms used in four Authenticated Encryption schemes based on symmetric block ciphers. These schemes are all cross chaining block cipher modes that claim to provide both confidentiality and integrity assurance simultaneously, in one pass over the data. The investigations include assessing the validity of an existing forgery attack on certain schemes, applying the attack approach to other schemes and implementing the attacks to verify claimed probabilities of successful forgeries. For these schemes, the theoretical basis of the attack was developed, the attack algorithm implemented and computer simulations performed for experimental verification.

Initialisation flaws in the A5-GMR-1 satphone encryption algorithm

A5-GMR-1 is a synchronous stream cipher used to provide confidentiality for communications between satellite phones and satellites. The keystream generator may be considered as a finite state machine, with an internal state of 81 bits. The design is based on four linear feedback shift registers, three of which are irregularly clocked. The keystream generator takes a 64-bit secret key and 19-bit frame number as inputs, and produces an output keystream of length between $2^8$ and $2^{10}$ bits. Analysis of the initialisation process for the keystream generator reveals serious flaws which significantly reduce the number of distinct keystreams that the generator can produce. Multiple (key, frame number) pairs produce the same keystream, and the relationship between the various pairs is easy to determine. Additionally, many of the keystream sequences produced are phase shifted versions of each other, for very small phase shifts. These features increase the effectiveness of generic time-memory tradeoff attacks on the cipher, making such attacks feasible.

Criptografia: Da origem aos dias atuais

Esta pesquisa foi realizada com a intenção de motivar o estudo da criptografia, mostrando que a matemática e a comunicação estão presentes em diversos momentos, tanto no passado quanto no presente. Este trabalho mostra a origem da criptoanálise e toda a sua evolução dando ênfase nos mecanismos de codificação e decodificação através de exemplos práticos. Além disso, alguns métodos criptográficos são destacados como a cifra de substituição monoalfabética, a cifra de Vigenère, a criptografia RSA que é o método mais conhecido de criptografia de chave pública, as cifras de Hill, o método das transformações lineares e o método de Rabin, devido a sua grande importância para a evolução de sistemas computacionais e assinaturas digitais entre outros. Por fim, mostra-se a importância e a necessidade dos recursos criptográficos nos dias de hoje, na tentativa de impedir que hackers e pessoas que fazem mau uso do conhecimento matemático possam causar danos a sociedade, seja por uma simples mensagem ou até mesmo através de situações mais imprudentes como as transações bancárias indevidas

Linearization Method and Linear Complexity

We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.

分组密码的分析与设计

分组密码作为现代密码学的一个重要组成部分，是目前最重要和流行的一种数据加密技术，有着非常广泛的应用。此外，近年来分组密码或其组件还经常作为基础模块用于构造Hash函数，MAC算法等。因此对分组密码安全性的分析以及设计安全高效的分组密码算法，在理论研究及实际应用中都有着非常重要的意义。本文的研究内容主要包括两个方面：对现有常用分组密码的安全性分析，以及分组密码及其组件的设计。这两个方面是密不可分，相互融合的。通常都是利用算法存在的弱点或算法设计特点，提出新的密码分析算法。而在算法设计过程中，正是从密码分析获取经验，掌握设计算法的技巧和避免可能存在的缺陷。 本文首先对分组密码分析方法作了大量的调查和研究，在此基础上分析了一些国内外常用和有影响的分组密码，得到了一系列有价值的分析结果。并在密码分析工作的经验基础上，结合现有密码设计理论，在分组密码及其组件的设计方面做了比较深入的研究。本文的主要成果包括： (1) DES算法的分析。DES算法是迄今最重要的分组密码算法之一，目前在一些金融领域，DES和Triple-DES仍被广泛使用着。本文考察了DES算法针对Boomerang攻击和Rectangle攻击的安全性。通过利用DES算法各轮的最优差分路径及其概率，分别给出了这两种攻击方法对DES的攻击算法。 (2) Rijndael算法的分析。Rijndael算法是高级加密标准AES的原型。本文针对大分组Rijndael算法的各个不同版本，利用算法行移位和列混淆变换的一些密码特性，改进了原有的不可能差分攻击结果，极大的降低了攻击的数据和时间复杂度。同时还分别构造了一些新的更长轮的不可能差分路径，利用这些路径给出了一系列对大分组Rijndael算法的改进的不可能差分攻击，这些结果是目前已知的对该算法的最好攻击结果。 (3) SMS4算法的分析。SMS4算法是中国公布的用于无线局域网产品保护的算法。本文首先构造了SMS4算法的一类5轮循环差分特征，利用该特征分别给出了对16轮SMS4算法的矩阵攻击和对21轮SMS4算法的差分分析。随后考察了SMS4算法抵抗差分故障攻击的能力，基于字节故障模型，结合实验指出需要32次故障诱导来恢复全部密钥。后续的工作又进一步将结果改进为只需要进行一次故障诱导再结合2^{44}次密钥搜索即可恢复全部密钥。 (4) CLEFIA密码算法的分析。CLEFIA算法是索尼公司于2007年提出的用于产品版权保护和认证的分组密码算法。针对CLEFIA算法，本文构造了一条概率为1的5轮截断差分特征，再结合其扩散矩阵的密码特性构造了一条3轮线性逼近。随后利用这两条路径组成的8轮差分-线性区分器，给出了对10轮CLEFIA算法的有效的差分-线性攻击。 (5) 分组密码结构的设计及其应用。本文提出了两种新的分组密码结构，并指出了其与原有结构相比的优势，同时分别评估了这两种结构针对差分分析和线性分析等常用密码分析方法的安全性。基于这两个密码结构，结合部分密码组件的设计和测试工作，本文还完成了两个分组密码算法的概要设计，并简要评估了它们的实现效率及针对现有的几种主要密码分析方法的安全性。

TAE模式的分析和改进

TAE(tweakable authenticated encryption)模式是一种基于可调分组密码的加密认证模式.研究结果表明,安全的可调分组密码不是安全的TAE模式的充分条件.只有当可调分组密码是强安全的时候,TAE模式才是安全的.同时,还给出了TAE模式的一些改进,得到模式MTAE(modified tweakable authenticat edencryption),并且证明了其安全性.

一类密钥流生成器的相关分析

多输出逻辑函数是构造密码系统的重要工具,相关免疫性是设计安全逻辑函数的重要准则.该文利用一种较为简单的方法证明了多输出逻辑函数相关免疫性两种刻划的等价性.还对一类利用多输出逻辑函数相关免疫函数构造的密钥流生成器进行了相关性分析,证明了这种构造方法是不成立的,并不能达到构造者期望的相关免疫性,并且分别利用Walsh变换技术和线性序列电路逼近方法找出了这类密钥流生成器的漏洞,从而说明这类生成器在相关攻击下是脆弱的.

MAGENTA的差分密码分析

对１５个ＡＥＳ候选算法之一的ＭＡＧＥＮＴＡ算法进行了差分密码分析，利用的是ＭＡＧＥＮＴＡ算法的结构缺陷。结果显示：利用算法１和算法２攻击ＭＡＧＥＮＴＡ算法，所需的选择明密文对分别为２~（７０）和２~（６４）。

LOKI97的线性密码分析

该文利用线性密码分析对 L OKI97进行了攻击 ,结果显示 ,L OKI97的安全性并没有达到高级加密标准的要求 ;利用线性密码分析中的算法 1和 2 50 个明密文对 ,以 0 .977的成功率预测 92比特子密钥 ;利用线性密码分析中的算法 2和 2 4 5个明密文对 ,以 0 .96 7的成功率预测 LOKI97的种子密钥 .

基于身份的可验证加密签名协议的安全性分析

利用Hess的基于身份的数字签名方案,Gu和Zhu提出了一个基于身份的可验证加密签名协议,并认为该协议在随机预言模型下是可证明安全的,从而可以作为基本模块用于构建安全的基于身份的公平交换协议.文章对该协议的安全性进行了深入分析,结果表明该协议存在如下的安全缺陷:恶意的签名者可以很容易地构造出有效的可验证加密签名,但是指定的仲裁者却不能把它转化成签名者的普通签名,因此不能满足可验证加密签名协议的安全需求;而且该协议容易遭受合谋攻击.

一个具有消息恢复的签名方案的安全性分析

李子臣和杨义先基于离散对数和素因子分解两个困难问题提出了具有消息恢复的数字签名方案-LY方案，武丹和李善庆指出了LY方案的安全性仅仅依赖于因子分解问题，为弥补这个缺陷他们同时给出了一个改进方案——WL方案．但是，该改进方案的安全性并不象作者所认为的那样依赖于两个难题．一旦因子分解问题可解，攻击者就可以伪造签名．

截断差分-线性密码分析

对差分 -线性密码分析方法进行推广 ,提出了截断差分 -线性密码分析方法 .对 9-轮和 11-轮 DES( dataencryption standard)密码算法的分析表明 ,该方法具有更加方便、灵活 ,适用范围更广的特点 .同时 ,利用截断差分 -线性密码分析方法得出 ,在类似 DES结构的算法中 ,S-盒的摆放顺序对密码的强度有较大的影响 .由此 ,截断差分 -线性分析方法给出了优化 S-盒排序的一种参考判别准则

一类广义Feistel密码的安全性评估

该文评估一类广义Feistel密码（GFC）抵抗差分和线性密码分析的能力：如果轮函数是双射且它的最大差分和线性特征的概率分别是p和q，则16轮GFC的差分和线性特征的概率的上界为p~7和q~7；如果轮函数采用SP结构且是双射，S盒的最大差分和线性特征的概率是pS和qS，P变换的分支数为P_d，则16轮GFC的差分和线性特征的概率的上界为(pS)~(3P_d+1)和(qS)~(3P_d+1)。

Q的线性密码分析

对NESSIE公布的17个分组密码之一的Q进行了线性密码分析，攻击所需的数据复杂不大于2^118(相应的成功率为0．785），空间复杂度不大于2^33+2^19+2^18+2^12+2^11+2^10。此结果显示Q对线性密码分析是不免疫的。