On the Collision and Preimage Resistance of Certain Two-Call Hash Functions

In this paper we present concrete collision and preimage attacks on a large class of compression function constructions making two calls to the underlying ideal primitives. The complexity of the collision attack is above the theoretical lower bound for constructions of this type, but below the birthday complexity; the complexity of the preimage attack, however, is equal to the theoretical lower bound. We also present undesirable properties of some of Stam’s compression functions proposed at CRYPTO ’08. We show that when one of the n-bit to n-bit components of the proposed 2n-bit to n-bit compression function is replaced by a fixed-key cipher in the Davies-Meyer mode, the complexity of finding a preimage would be 2 n/3. We also show that the complexity of finding a collision in a variant of the 3n-bits to 2n-bits scheme with its output truncated to 3n/2 bits is 2 n/2. The complexity of our preimage attack on this hash function is about 2 n . Finally, we present a collision attack on a variant of the proposed m + s-bit to s-bit scheme, truncated to s − 1 bits, with a complexity of O(1). However, none of our results compromise Stam’s security claims.

Cryptanalysis of Tav-128 Hash Function

Many RFID protocols use cryptographic hash functions for their security. The resource constrained nature of RFID systems forces the use of light weight cryptographic algorithms. Tav-128 is one such 128-bit light weight hash function proposed by Peris-Lopez et al. for a low-cost RFID tag authentication protocol. Apart from some statistical tests for randomness by the designers themselves, Tav-128 has not undergone any other thorough security analysis. Based on these tests, the designers claimed that Tav-128 does not posses any trivial weaknesses. In this article, we carry out the first third party security analysis of Tav-128 and show that this hash function is neither collision resistant nor second preimage resistant. Firstly, we show a practical collision attack on Tav-128 having a complexity of 237 calls to the compression function and produce message pairs of arbitrary length which produce the same hash value under this hash function. We then show a second preimage attack on Tav-128 which succeeds with a complexity of 262 calls to the compression function. Finally, we study the constituent functions of Tav-128 and show that the concatenation of nonlinear functions A and B produces a 64-bit permutation from 32-bit messages. This could be a useful light weight primitive for future RFID protocols.

On Randomizing Hash Functions to Strengthen the Security of Digital Signatures

Halevi and Krawczyk proposed a message randomization algorithm called RMX as a front-end tool to the hash-then-sign digital signature schemes such as DSS and RSA in order to free their reliance on the collision resistance property of the hash functions. They have shown that to forge a RMX-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. In this article, we will show how to use Dean’s method of finding expandable messages for finding a second preimage in the Merkle-Damgård hash function to existentially forge a signature scheme based on a t-bit RMX-hash function which uses the Davies-Meyer compression functions (e.g., MD4, MD5, SHA family) in 2 t/2 chosen messages plus 2 t/2 + 1 off-line operations of the compression function and similar amount of memory. This forgery attack also works on the signature schemes that use Davies-Meyer schemes and a variant of RMX published by NIST in its Draft Special Publication (SP) 800-106. We discuss some important applications of our attack.

SHA-3 Design and Cryptanalysis Report

The competition to select a new secure hash function standard SHA-3 was initiated in response to surprising progress in the cryptanalysis of existing hash function constructions that started in 2004. In this report we survey design and cryptanalytic results of those 14 candidates that remain in the competition, about 1.5 years after the competition started with the initial submission of the candidates in October 2008. Implementation considerations are not in the scope of this report. The diversity of designs is also reflected in the great variety of cryptanalytic techniques and results that were applied and found during this time. This report gives an account of those techniques and results.

Intermediate Status Report

This report was produced in partial fulfillment of contract ICT-2007-216676 (ECRYPT II), sponsored by the European Commission through the ICT Programme. The information in this paper is provided as is, and no warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability. We present a short overview of the recent results on the five finalists for NIST's SHA-3 competition. The next five chapters treat each one of the finalists.

A subexponential construction of graph coloring for multiparty computation

We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal (secure against an adversary who possesses any t

Low probability differentials and the cryptanalysis of full-round CLEFIA-128

So far, low probability differentials for the key schedule of block ciphers have been used as a straightforward proof of security against related-key differential analysis. To achieve resistance, it is believed that for cipher with k-bit key it suffices the upper bound on the probability to be 2− k . Surprisingly, we show that this reasonable assumption is incorrect, and the probability should be (much) lower than 2− k . Our counter example is a related-key differential analysis of the well established block cipher CLEFIA-128. We show that although the key schedule of CLEFIA-128 prevents differentials with a probability higher than 2− 128, the linear part of the key schedule that produces the round keys, and the Feistel structure of the cipher, allow to exploit particularly chosen differentials with a probability as low as 2− 128. CLEFIA-128 has 214 such differentials, which translate to 214 pairs of weak keys. The probability of each differential is too low, but the weak keys have a special structure which allows with a divide-and-conquer approach to gain an advantage of 27 over generic analysis. We exploit the advantage and give a membership test for the weak-key class and provide analysis of the hashing modes. The proposed analysis has been tested with computer experiments on small-scale variants of CLEFIA-128. Our results do not threaten the practical use of CLEFIA.

Anonymous Authentication with Shared Secrets

Anonymity and authenticity are both important yet often conflicting security goals in a wide range of applications. On the one hand for many applications (say for access control) it is crucial to be able to verify the identity of a given legitimate party (a.k.a. entity authentication). Alternatively an application might require that no one but a party can communicate on its behalf (a.k.a. message authentication). Yet, on the other hand privacy concerns also dictate that anonymity of a legitimate party should be preserved; that is no information concerning the identity of parties should be leaked to an outside entity eavesdropping on the communication. This conflict becomes even more acute when considering anonymity with respect to an active entity that may attempt to impersonate other parties in the system. In this work we resolve this conflict in two steps. First we formalize what it means for a system to provide both authenticity and anonymity even in the presence of an active man-in-the-middle adversary for various specific applications such as message and entity authentication using the constructive cryptography framework of Mau11, MR11]. Our approach inherits the composability statement of constructive cryptography and can therefore be directly used in any higher-level context. Next we demonstrate several simple protocols for realizing these systems, at times relying on a new type of (probabilistic) Message Authentication Code (MAC) called key indistinguishable (KI) MACs. Similar to the key hiding encryption schemes of BBDP01] they guarantee that tags leak no discernible information about the keys used to generate them.

Efficient Protocol for Authenticated Email Search

Executing authenticated computation on outsourced data is currently an area of major interest in cryptology. Large databases are being outsourced to untrusted servers without appreciable verification mechanisms. As adversarial server could produce erroneous output, clients should not trust the server's response blindly. Primitive set operations like union, set difference, intersection etc. can be invoked on outsourced data in different concrete settings and should be verifiable by the client. One such interesting adaptation is to authenticate email search result where the untrusted mail server has to provide a proof along with the search result. Recently Ohrimenko et al. proposed a scheme for authenticating email search. We suggest significant improvements over their proposal in terms of client computation and communication resources by properly recasting it in two-party settings. In contrast to Ohrimenko et al. we are able to make the number of bilinear pairing evaluation, the costliest operation in verification procedure, independent of the result set cardinality for union operation. We also provide an analytical comparison of our scheme with their proposal which is further corroborated through experiments.

一种网格环境下的密码计算模型

由于密码学和信息安全领域的许多问题最终都被转化为一个耗时的计算,其中许多计算需要利用多台异构的和地理分布的计算机协同,才能有效完成.密码算法的设计、分析和应用对于计算环境敏感,且依赖性较强,不同类型的算法和算法的不同实现模式对计算环境要求差异很大,而且到目前为止还不存在一种通用的分布式密码计算模型.为此,本文根据密码计算本身的需求,首先分别分析了密码算法设计、分析和应用的目标和特征,提出了相应的计算模式,给出了一种网格环境下的通用密码计算模型.进而讨论了密码计算任务分割策略,资源分配和负载平衡问题.最后给出了网格环境Globus Toolkit下的模型构架、实现与实验结果.

mod 2n加运算与F2上异或运算差值的概率分布和递推公式

提出了一种计算单mod 2~n加运算与F_2上的异或运算的“异或差值”概率分布的有效算法，该算法的计算复杂度为O（（n-1）／2），与Maximov的结果相比计算复杂度更低．对于多mod 2~n加运算的情形，给出了多mod 2~n加运算与F_2上的异或（XOR）运算的“异或差值”的递推计算公式．

视觉密码方案的构造

视觉密码学是在最近十余年间逐渐发展起来的新型密码学分支。近年从事视觉密码学研究的学者越来越多，研究结果频现于三大密码学会和Journal of Cryptology, Designs, codes and cryptography和IEEE Transactions on Image Processing等高水平期刊上。视觉密码方案（VCS）具有的针对图片加解密，视觉解密，秘密共享和无条件安全等特点，较之传统的秘密共享方案，它具有解密设备简单的优点，解密过程不需要使用者拥有任何密码学知识，可以直接观察到解密图片。而较之传统的秘密隐藏方案，他具有信息容量大的优点，可以加密整幅图片的秘密信息，而且由于其加解密的对象是图片，因此其信息内容可以灵活多变。视觉密码方案可以应用在秘密共享，信息隐藏，身份认证/鉴别以及版权保护等方面。随着具有更多特殊性质的视觉密码方案的提出，其应用范围也会越来越广。本文的工作主要集中在两个方面：视觉密码方案的构造和分析以及视觉密码相关问题的研究。 在视觉密码方案的构造和分析方面，本文所做的工作主要包括： 本文在第二章提出一个利用嵌入技术构造有意义分享图片视觉密码方案（EVCS）的方法。与已知的构造相比，其优点包括：(1) 可以直接处理灰度图片；(2) 具有较小的秘密图片像素扩张；(3) 可以针对一般存取结构构造，且总是无条件安全的；(4)每个参与者只分配一张分享图片；(5) 具有在分享图片像素扩张、分享图片视觉效果和秘密图片像素扩张之间相互取舍的灵活性。 本文在第三章提出了一种针对一般存取结构的VCS的递归构造方法，与过往的VCS相比，在大多数存取结构下，本文的方法在平均像素扩张，像素扩张和对比度方面都有所改进。根据本文的构造方法，可知针对一般存取结构的VCS的构造可以通过递归调用(2,2)-VCS来实现，而无论其所基于的是“OR”还是“XOR”运算。本文的方案最终可能分配给某个参与者多张分享图片，由于平均像素扩张的降低，因此这一点并不能称之为缺点。另外，利用本文中的方案可以构造出针对一般存取结构的基于“XOR”运算的VCS。 对于彩色视觉密码方案（CVCS），基于Naor-Shamir视觉密码模型，本文在第四章提出一个的没有像素扩张的(k,n)-CVCS，以及与对应的黑白(k,n)-EVCS具有相同像素扩张的(k,n)-CEVCS；基于Tuyls视觉密码模型，本文首先分别提出了黑白(k,n)-VCS和黑白(k,n)-EVCS，并以此为构件提出(k,n)-CVCS和(k,n)-CEVCS。仿真实验结果表明，本文提出的方案具有较好的视觉效果。 对于防止欺骗的视觉密码方案，本文在第五章首先分析了已知的几种防止欺骗的视觉密码方案（CIVCS）的缺陷，然后提出一个新的CIVCS来避免这些缺陷。本文所提出的CIVCS构建于已知的VCS之上，在只泄漏极少量秘密图片的信息的情况下达到了很高的安全性。并且可以针对一般存取结构。本文所提出的CIVCS也可以应用在底层运算为“XOR”运算的VCS之上。另外，本文所提出的CIVCS可以根据参与者携带验证信息的多少，可以检测出欺骗行为或者可以揪出具体的欺骗者。 本文在第六章研究了基于“XOR”运算的(2,n)-VCS的最优化问题。给出了基于“XOR”运算的(2,n)-VCS的最小像素扩张，以及具有最小像素扩张条件限制下的最大对比度和最大平均对比度。另外给出了基于“XOR”运算的(2,n)-VCS的最大对比度，以及具有最大对比度条件限制下的最小像素扩张。上述四类方案在本文中都给出了具体的构造方法，以及相关对比度，像素扩张和基矩阵的结构性质的证明。本文中的结果表明基于“XOR”运算下的(2,n)-VCS的各个参数都要比基于“OR”运算下的对应的参数要好。本文还证明了构造具有最大对比度的(2,n)-VCS的基矩阵等价于构造具有相应参数且达到最大容量的二元码。故根据本文的研究结果，便可以通过利用已知的构造达到最大容量的二元码的方法来构造具有最大对比度的(2,n)-VCS，最后对于n=2^k-1的情况，本文还给出了一个利用m-序列来构造具有最大对比度的(2,n)-VCS的方法。 本文在第七章证明了Droste提出的基于“OR”运算的(k,n)-VCS同样在“XOR”运算下也成立。同时基于“OR”运算和“XOR”运算的VCS会给参与者带来便利，他们可以根据不同的环境而选择不同的视觉密码模型。另外，本文还提出一个进一步降低VCS的像素扩张的方法，与Tuyls等人所提出的(k,n)-VCS比较，本文的方法可以显著的降低方案的像素扩张。本文在第七章还提出一个可以运行在Tuyls视觉密码模型之上的同色(k,n)-VCS的构造方法，其中每个分享图片都是同色的，而叠加k个分享图片可以得到黑白的秘密图片。本文证明了当k为奇数时，同色的(k,n)-VCS是不存在的，并给出了当k为偶数时，同色(k,n)-VCS的构造方法。同色(k,n)-VCS可以用来防止分享图片被隐蔽的监控摄像头窃取。 在视觉密码相关问题的研究方面，本文所做的工作主要包括： 本文在第八章研究了视觉密码方案的幻灯片对齐问题，证明了，在幻灯片没有精确对齐的情况下，人眼仍能观察到秘密图片，且其平均对比度满足-(m-r)e/(m2(m-1))。这项研究可以为确定幻灯片中像素的尺寸做参考。本研究也证明了视觉密码方案本身具有一定的纠错能力。 本文在第九章研究了视觉密码中的对比度定义的表示问题。首先给出了四个关于VCS对比度的观察结论，并分析了已知的几种对比度定义的缺陷，从而提出了一个新的对比度定义。本文在理论和实验上说明了，其所提出的对比度定义符合上述观察结论，可以更精确的衡量所恢复的秘密图片的视觉效果。本文最后还针对概率视觉密码方案的定义给出了针对概率视觉密码方案的对比度的定义。 最后我们对本文的工作进行了总结，并对今后的一些研究方向进行了展望。

a new client-to-client password-authenticated key agreement protocol

Natl Univ Defen Technol, China & Nanyang Technol Univ, NUDT

separation of duty in trust-based collaboration

Chinese Assoc Cryptol Res, State Key Lab Informat Secur, Inst Software, Grad Univ Chinese Acad Sci, Natl Nat Sci Fdn China