From msuinfo!caen!batcomputer!munnari.oz.au!metro!news.cs.uow.edu.au!news.cs.uow.edu.au!not-for-mail Wed Dec 15 10:38:16 1993 Path: msuinfo!caen!batcomputer!munnari.oz.au!metro!news.cs.uow.edu.au!news.cs.uow.edu.au!not-for-mail From: yuliang@orlith.cs.uow.edu.au (Yuliang Zheng) Newsgroups: sci.crypt Subject: Cryptography & Computer Security Techreports Available Date: 6 Dec 1993 09:51:11 +1100 Organization: University of Wollongong, NSW, Australia. Lines: 285 Message-ID: <2dtokv$18r@orlith.cs.uow.edu.au> NNTP-Posting-Host: orlith.cs.uow.edu.au The following technical reports on cryptography and computer security are available via anonymous-FTP at ftp.cs.uow.edu.au pub/papers >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>|<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Yuliang Zheng Centre for Computer Security Research Department of Computer Science E-mail: yuliang@cs.uow.edu.au University of Wollongong Voice: +61 42 21 4331 (office) Wollongong, NSW 2522 +61 42 21 3859 (dept) AUSTRALIA Fax: +61 42 21 4329 tr-93-1 Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng " Highly Nonlinear Balanced Boolean Functions Satisfying High Degree Propagation Criterion" ABSTRACT Three of the most important nonlinearity criteria for cryptographically strong functions are balancedness, nonlinearity and propagation criterion. In this paper we study systematic methods for constructing highly nonlinear balanced Boolean functions satisfying the high degree propagation criterion. In particular, we present a method for constructing highly nonlinear balanced Boolean functions on $V_{2k+1}$ satisfying the propagation criterion with respect to {\em all but one\/} vectors in $V_{2k+1}$, and a method for constructing highly nonlinear balanced Boolean functions on $V_{2k}$ satisfying the propagation criterion with respect to {\em all but three\/} vectors in $V_{2k}$. We then show that the vectors where the propagation criterion is not satisfied can be moved upward in such a way that the functions constructed on $V_{2k+1}$ satisfy the propagation criterion of degree $2k$, while the function constructed on $V_{2k}$ satisfy the propagation criterion of degree $\frac{4}{3}k$. The moving technique does not alter the balancedness and nonlinearity of the functions. The methods are illustrated by concrete constructions of such cryptographically strong functions. The algebraic degrees of the functions are also discussed. tr-93-2 Yuliang Zheng, Thomas Hardjono and Jennifer Seberry "New Solutions to the Problem of Access Control in a Hierarchy" ABSTRACT The access control problem in a hierarchical organization consists of the management of information among a number of users who are divided into different security classes according to their suitability in accessing the information. Within the scope of cryptography the problem can be reduced to generating a cryptographic key for each security class in such a way that the key of a security class can be used to derive the keys of all lower security classes. This paper presents a new approach to solving the problem, based on pseudo-random function families, universal hash function families and in particular, sibling intractable function families. The approach is illustrated by two types of solutions. The first type of solution allows keys of lower security classes to be obtained indirectly from that of higher security classes through the calculation of the keys of all intermediate security classes, while the second type of solution allows keys of lower security classes to be obtained directly from that of higher security classes without involving other security classes. A formal definition of security for key generation schemes is introduced and the security of the proposed schemes is proven. Issues in key management are also addressed and several possible polices are suggested. The proposed solutions have theoretical significance in that their security relies only on the existence of any one-way function, and they also have practical applications in that they can be easily incorporated into existing information systems. tr-93-4 Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng "Nonlinearity and Propagation Characteristics of Balanced Boolean Functions" ABSTRACT Three of the most important criteria for cryptographically strong Boolean functions are the balancedness, the nonlinearity and the propagation criterion. The main contribution of this paper is to reveal a number of interesting properties of balancedness and nonlinearity, and to study systematic methods for constructing Boolean functions that satisfy some or all of the three criteria. We show that concatenating, splitting, modifying and multiplying (in the sense of Kronecker) sequences can yield balanced Boolean functions with a very high nonlinearity. In particular, we show that balanced Boolean functions obtained by modifying and multiplying sequences achieve a nonlinearity higher than that attainable by any previously known construction method. We also present methods for constructing balanced Boolean functions that are highly nonlinear and satisfy the strict avalanche criterion (SAC). Furthermore we present methods for constructing highly nonlinear balanced Boolean functions satisfying the propagation criterion with respect to {\em all but one or three\/} vectors. A technique is developed to transform the vectors where the propagation criterion is not satisfied in such a way that the functions constructed satisfy the propagation criterion of high degree while preserving the balancedness and nonlinearity of the functions. The algebraic degrees of functions constructed are also discussed, together with examples illustrating the various constructions. tr-93-5 Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng "On Constructions and Nonlinearity of Correlation Immune Functions" ABSTRACT A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper we study balanced correlation immune functions using the theory of Hadamard matrices. First we present a simple method for directly constructing balanced correlation immune functions of any order. Then we prove that our method generates exactly the same set of functions as that obtained using a method by Camion, Carlet, Charpin and Sendrier. Advantages of our method over Camion et~al's include (1) it allows us to calculate the nonlinearity, which is a crucial criterion for cryptographically strong functions, of the functions obtained, and (2) it enables us to discuss the propagation characteristics of the functions. Two examples are given to illustrate our construction method. Finally, we investigate methods for obtaining new correlation immune functions from known correlation immune functions. These methods provide us with a new avenue towards understanding correlation immune functions. tr-93-9 Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng "Improving the Strict Avalanche Characteristics of Cryptographic Functions" ABSTRACT This letter presents a simple yet effective method for transforming Boolean functions that do not satisfy the strict avalanche criterion (SAC) into ones that satisfy the criterion. Such a method has a wide range of applications in designing cryptographically strong functions, including substitution boxes (S-boxes) employed by common key block encryption algorithms. tr-93-9 Yuliang Zheng, Josef Pieprzyk and Jennifer Seberry "HAVAL --- A One-Way Hashing Algorithm with Variable Length of Output" ABSTRACT A one-way hashing algorithm is a deterministic algorithm that compresses an arbitrary long message into a value of specified length. The output value represents the fingerprint or digest of the message. A cryptographically useful property of a one-way hashing algorithm is that it is infeasible to find two distinct messages that have the same fingerprint. This paper proposes a one-way hashing algorithm called HAVAL. HAVAL compresses a message of arbitrary length into a fingerprint of 128, 160, 192, 224 or 256 bits. In addition, HAVAL has a parameter that controls the number of passes a message block (of 1024 bits) is processed. A message block can be processed in 3, 4 or 5 passes. By combining output length with pass, we can provide fifteen (15) choices for practical applications where different levels of security are required. The algorithm is very efficient and particularly suited for 32-bit computers which predominate the current workstation market. Experiments show that HAVAL is $60\%$ faster than MD5 when 3 passes are required, $15\%$ faster than MD5 when 4 passes are required, and as fast as MD5 when full 5 passes are required. It is conjectured that finding two collision messages requires the order of $2^{n/2}$ operations, where $n$ is the number of bits in a fingerprint. tr-93-14 Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng "Systematic Generation of Cryptographically Robust S-boxes" ABSTRACT Substitution boxes (S-boxes) are a crucial component of DES-like block ciphers. This research addresses problems with previous approaches towards constructing S-boxes, and proposes a new definition for the robustness of S-boxes to differential cryptanalysis, which is the most powerful cryptanalytic attack known to date. A novel method based on group Hadamard matrices is developed to systematically generate S-boxes that {\em simultaneously\/} satisfy a number of critical cryptographic properties. Among the properties are the high nonlinearity, the strict avalanche characteristics, the balancedness, the robustness against differential cryptanalysis, and the immunity to linear cryptanalysis. An example is provided to illustrate the S-box generating method. tr-93-17 Yuliang Zheng "Amending Leighton and Micali's Key Distribution Protocol" ABSTRACT A key distribution protocol is a set of rules by which two users can establish a shared common key between them and then use the key in future secure communications. We analyze a key distribution protocol presented by Leighton and Micali at the CRYPTO'93 conference, which is based on tamper-proof hardware, and show that the protocol fails in that a common key shared between two users can always be obtained by a number of other legitimate users in a system where the proposed protocol is employed. An interesting point is that the legitimate users can derive the key without opening a single tamper-proof chip. We also propose a very simple identity based conference key distribution protocol that frees of the flaw possessed by Leighton and Micali's protocol. Furthermore, we employ ideas behind our protocol to successfully repair Leighton and Micali's failed protocol.