Sixth Selected Areas of Cryptography (SAC '99)
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.