Kingston, Ontario, Canada

August 9-10, 1999

The Sixth Annual Workshop on Selected Areas of Cryptography (SAC '99) was held at Queen's University in Kingston, Ontario, Canada. 52 people from 11 countries attended the workshop. After opening remarks, the first session "Cryptosystems and Pseudorandom Number Generators" began with a presentation by Helena Handschuh on a "Universal Encryption Standard", an idea she developed with Serge Vaudenay. The idea of the research was to design a symmetric cipher which can be set up to be compatible with DES and triple DES, but also supports the 128 bit block size and key lengths of 128, 192, and 256 bits as required in the Advanced Encryption Standard (AES) criteria. The cipher design uses a pair of triple DES chains, with some bits of the output of each DES block swapped with those of the second chain. Pre and post-whitening is used to defend against collision attacks. The key schedule is the same as that used in DEAL. John Kelsey presented the second paper, titled "Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator" and co-authored with Bruce Schneier and Niels Ferguson. The talk began with a review of how pseudorandom number generators (PRNGs) are often compromised: - the sources of random data are not as nondeterministic as the designer assumed, - the PRNG is not re-seeded often enough, - when the PRNG is re-seeded, not enough new entropy is provided. Yarrow addresses the first issue by allowing multiple sources of entropy and designing the system to ensure that even if one of the sources of entropy were to fail, the system would remain secure. Yarrow also makes use of two entropy pools; a fast entropy pool and a slow entropy pool. Every second reading from each entropy source is stored in each entropy pool. The PRNG is re-seeded whenever either the fast entropy pool contains entropy from a single source of at least 100 bits, or the slow entropy pool contains entropy from two sources of at least 160 bits each. The idea here is that the fast pool provides frequent re-seeding to reduce the amount of time that the PRNG sequence can be deduced after a compromise, while the slow pool tries to assure that complete knowledge of the PRNG state cannot be maintained indefinitely. Three-key triple DES is used to generate output bits. The last talk of the session was given by Guang Gong on the paper "Elliptic Curve Pseudorandom Sequence Generators", joint work with Thomas Berson and Douglas Stinson. Many PRNGs are composed of one or more linear feedback shift registers, combined in such a way as to destroy the linearity of the system. These and all other periodic binary sequences can always be considered as a sequence arising from applying a trace function to a Reed-Solomon codeword. In this paper, the authors suggest replacing the Reed-Solomon code with a sequence generated from an elliptic curve. More precisely, a randomly chosen supersingular curve is chosen over GF(2^n). A point P of maximum order is chosen at random on the curve, and the sequence iP (0 < i < order(P) ) calculated. The output sequence is the sequence of traces { Tr(P_x),Tr(P_y),Tr((2P)_x),Tr((2P)_y),...}. The resulting PRNG is compared with other PRNGs and it is shown that the elliptic curve PRNG compares favourably with others in terms of period, frequency range of 1 occurrence, unbalance range, and linear span. The second session, "Security Aspects of Block Ciphers I" began with a talk by Serge Vaudenay titled "Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomness". In this work, the decorrelation analysis presented at SAC '98 is extended by defining two new norms. With these norms, the concept of decorrelation can be applied to provide lower bounds on the difficulty of performing adaptive attacks and chosen plaintext and chosen ciphertext attacks. The results are applied to the Peanut construction, on which the Round 1 AES candidate DFC is based. This talk was followed by "Guesswork and Variation Distance as Measures of Cipher Security", presented by John Pliam. Known plaintext and chosen plaintext attack effort are described in terms of the idea of "guesswork", the expected number of guesses required to successfully identify the key given an oracle that can only state whether or not a key is correct. It is suggested that the resistance of an iterated cipher against all possible known or chosen plaintext attacks often exhibits a "cutoff" phenomenon, a rapid jump from low to high security as the number of rounds is increased. Next on the program was lunch, followed by an invited talk titled "From DES to AES: Twenty Years of Government Initiatives in Cryptography", presented by Miles Smid of the National Institute of Science and Technology (NIST). The talk began with the Brooks Act of 1965, requiring new standards for improving the utilization of computers by the federal government. The Data Encryption Standard (DES), first published in March 1975 after two Federal Register Solicitations, became a US government standard in January 1977. Controversies surrounded the DES during the 1980s, with concerns about the key size, s-box design criteria, and the possibility of trap doors. This had the effect of motivating public research in the field of cryptography. DES use became more widespread, present in 48% of U.S. cryptographic products according to a 1997 survey. Meanwhile, standards emerged including the DES modes of operation (FIPS 81) message authentication codes (ANSI X9.9, FIPS 113), and key management protocols (ANSI X.9.17). In 1987, the second five year review of DES reaffirmed DES for another five years, and allowed its implementation in "software, firmware, hardware, or any combination thereof". 1990 marked the introduction of Biham and Shamir's differential cryptanalysis, followed in 1993 by Matsui's linear cryptanalysis. The Secure Hash Algorithm (SHA), based on MD4, was introduced in 1993 and modified to SHA-1 in 1995 after a weakness was discovered. The Digital Signature Algorithm (DSA) indicated the government's acceptance of public key cryptography in 1994, and a PKI Study that year recommended the use of a PKI hierarchy in the government. The late 1990s saw much controversy over key escrow, with the Escrowed Encryption Standard (1994), Clipper and Capstone. In 1997, the AES process was conceived out of the need for a DES replacement, e-commerce privacy, and existing weaknesses in the DES. Triple-DES, although suitable in the short term, was not ideal. The ongoing AES effort is aimed at producing a new symmetric algorithm, and is a cooperation between government, industry, and the academic community. At the end of the talk, Miles Smid announced that five AES candidates have been chosen for the Round 2 evaluation. Those candidates are: Mars, RC6, Rijndael, Serpent, and Twofish. During the question period he also said that NIST had asked the NSA for a new hash algorithm. The final session of the day, "Efficient Implementations in Cryptosystems", began with a talk by Detlef Huehnlein. His presentation "Efficient Implementation of Cryptosystems Based on Non-maximal Imaginary Quadratic Orders" introduced a new arithmetic for use in NICE (New Ideal Coset Encryption) cryptosystems. The arithmetic improves signature generation by a factor of 40 compared with conventional ideal arithmetic when combined with a previously noted improvement based on the Chinese Remainder Theorem. The next talk, "Improving and Extending the Lim/Lee Exponentiation Algorithm", was given by Biljana Cubaleska (co-written with Andreas Reike and Thomas Hermann) and discussed several improvements on the Lim/Lee exponentiation algorithm. The authors re-parameterized the second algorithm by Lim/Lee and presented an efficient precomputation step. The performance of the improved algorithm was compared with that of the original, and with that of a windowing algorithm. Optimizations were considered for the unlimited and limited memory scenarios. The session ended with "Software Optimization of Decorrelation Module", by Fabrice Noilhan. The talk was presented by Serge Vaudenay. The implementation of the decorrelation module of the first round AES candidate DFC, ax+b mod 2^64+13 mod 2^64, was considered in ANSI C, C with platform specific optimizations, assembly language, and Java. The results show that, although with ANSI C code DFC is one of the slowest algorithms, it becomes one of the fastest once platform specific optimizations are considered. On Tuesday August 10 the first session, "Cryptanalysis of Block Ciphers", began with a presentation by Shiho Moriai titled "Security of E2 Against Truncated Differential Cryptanalysis", joint work with Makoto Sugita, Kazumaro Aoki, and Masayuki Kanda. The presentation expanded on work by Matsui and Tokita in which truncated differential cryptanalysis was applied to a modified 7 round variant of E2. In this presentation, an algorithm for searching for all truncated differentials leading to a successful attack was given, and the algorithm applied to E2. It was determined that no suitable truncated differentials exist for 8 or more rounds of E2. A second truncated differential with higher probability than the first was also found for the 7 round variant. This truncated differential could also be used to distinguish the reduced-round E2 from a random permutation. The search algorithm was also applied to Rijndael, showing that no differentials exist for a 6 round variant with probability greater than 1/(2^128-1). This talk was followed by work by John Kelsey and Bruce Schneier, presented by John Kelsey. In "Key-Schedule Cryptanalysis of DEAL", the authors show that equivalent keys exist in DEAL-128, DEAL-192 and DEAL-256. Related key attacks also exist against 192 and 256 bit DEAL. The attacks exploit the key schedule, which is theoretically interesting because the key schedule is based on DES, a cryptographically strong primitive. The attacks are possible because the encryption algorithm ignores the DES parity bits of the round keys generated by the key schedule. It was noted that, in addition to finding weak keys as described in the paper, weak keys could also be found algebraically. Although DEAL is not one of the Round 2 AES candidates, the attacks are interesting from a practical standpoint because the fact that DEAL is designed around the DES implies that it can be made using readily available DES implementations. Kazumaro Aoki presented the last talk of the session, "Efficient Evaluation of Security against Generalized Interpolation Attack". In this work, the author introduces the linear sum attack, a generalized interpolation attack. This generalization makes it possible to verify the security of several AES candidates (E2, Crypton, Rijndael) against the generalized attack. A relationship between the linear sum attack and higher order differential attack is also demonstrated. After a short break, the fifth session, "Security Aspects of Block Ciphers II", began with a presentation by Liam Keliher (joint work with Henk Meijer and Stafford Tavares). In this work, the resistance of substitution-permutation networks (SPNs) to linear cryptanalysis is analysed. Upper bounds on the probability of existence of a linear characteristic providing a more efficient attack than exhaustive search are found for an R round cipher. The results show that, for a 14 round SPN using 8x8 s-boxes generated by randomly choosing permutations for the s-boxes, the probability that a linear characteristic suitable for linear cryptanalysis exists is less than 10^(-18). It is also observed that often the best linear characteristic involves only one active s-box per round, and this is confirmed with experimental evidence. The second talk of the session, "Strong Linear Dependence and Unbiased Distribution of Non-propagative Vectors" analysed the nonlinearity properties of boolean functions. The work was presented by Xian-Mo Zhang and co-written with Yuliang Zheng. In the paper, two results are presented. First, in any n-1 dimensional linear subspace, the non-propagative vectors of a function with n variables are linearly dependent. Secondly, except for functions with one of three specific nonlinearities, there exists a non-propagative vector in every n-2 dimensional linear subspace and three non-propagative vectors in every n-1 dimensional linear subspace. Following lunch, Mike Reiter presented an invited talk, "A Biometric Technique for Improving Security in Virtual Private Networks". The talk proposed a method for using biometric information to protect stored credentials (such as a private key and trusted public key certificate) on a system with no special hardware. Although such information is usually protected by a password, these are often weak, and hardware tokens must be tamper resistant to resist attack. Using keystroke information, such as the time between keystrokes, has been considered in several studies but reliability can be a concern (in particular if changing keyboards). The speaker proposed a solution in which various "features" of keyboard input are used in combination with the text of a password. For example, the duration of the first keystroke and latency between keystrokes could be used; for eight character passwords, fifteen features could be identified. A hardened password could be generated from a large space (e.g. 2^160 elements). Using an n of m secret sharing scheme, the hardened password could be divided into m shares. A table containing a row for each of the m features, and two values for the share associated with that feature, would have one of the entries replaced with random data if the feature was a distinguishing feature for the user. In this way, an attacker not knowing the password would first need to decrypt the table using password guesses. If the guess was correct, the table would be seen, but the attacker would still need to guess which features the user exhibited. The table would need to be formatted so that it is difficult to differentiate between a correct and an incorrect table. If the hardened password table was re-generated after each login, each time identifying distinguishing features of the individual, the password scheme could automatically adjust to gradual changes in typing behaviour. A trial implementation has revealed that users typically have many distinguishing features (e.g. 7-7.7 out of 15), and login reliability ranges from 51% to 75% success rates for the legitimate users. The proposal does have some limitations; for example, it cannot be used over a network because the timing information is not available. Also, a recovery method is needed; brute force recovery given the table (i.e. given the text password) takes 11 hours, and would be necessary if typing characteristics changed drastically. Salting should also be used to increase the scheme's security. The last session of the conference, "Cryptography for Network Applications", began with a talk by Anna Lysyanskaya, "Pseudonym Systems" (joint work with Ronald Rivest and Amit Sahai). In this presentation, a construction for pseudonym systems was presented having the property that there is a deterrent to sharing anonymous credentials with other users. This would prevent, for example, a subscription to an online commercial magazine using anonymous credentials to be shared by several users. Proofs of existence of such pseudonym schemes are given for both single-use and multiple-use credentials. A practical single-use scheme was also presented. The next talk, "Unconditionally Secure Proactive Secret Sharing Scheme with Combinatorial Structures" was presented by Doug Stinson. The work, co-authored with R. Wei, presented three unconditionally secure secret sharing schemes. The first scheme is a verifiable secret sharing scheme; provided that an adversary can control at most a certain number of participants in the secret sharing scheme, each good participant can verify the correctness of their own shares. The second scheme extends the first, producing a proactive secret sharing scheme in which an opponent can corrupt at most a fixed number of participants of their choice at any one time. In this scenario, any good servers can re-construct their shares after they have been destroyed by the attacker and together can recover the shared secret. The last scheme makes use of combinatorial structure to improve the computational efficiency of the proactive secret sharing scheme. This technique can also be applied to other secret sharing schemes. The talk was followed by a presentation by Dirk Westhoff, "Protecting a Mobile Agent's Route against Collusions" (joint work with Markus Schneider, Claus Unger, and Firoz Kaderali). The research focuses on protecting the route of a mobile agent such that no honest hosts on the route can be skipped, replaced, or added without detection, even in the presence of colluding hosts on the route. The scheme prevents hosts on the route from determining the identities of other non-colluding hosts on the route other than its immediate predecessor and successor. The idea is based on "onion routing", in which the remainder of the route is superencrypted by each node preceding it in turn (starting from the last node in the route). The last talk of the conference was presented by William Simpson, on a proposed Internet session-key management protocol named Photuris. The protocol was designed to provide perfect forward secrecy of the session keys, privacy protection, resistance against some denial of service attacks, scalability, and simplicity of design. At the end of the conference the conference chairs announced that there would be another conference next year, but that the exact date and location are still to be announced.