Security Group

# 1996 seminars

### 5 December
Cryptographic algorithm engineering / *Josef Pieprzyk,
University of Wollongong, Australia*

###
3 December Factoring and smart cards
/ *Richard Pinch, DPMMS, University of Cambridge*

Seminar Room 1, DPMMS

Dr Pinch will be talking specifically about an attack on a proposal for server-aided RSA computation using some factoring methods which go back to Lehmer.

Please note that this seminar is held at the DPMMS and not in The Computer Laboratory. Tea will be available in the DPMMS Common Room from 15:45.

### 26 November
Information warfare and infosec - future challenges
/ *David Ferbrache, Defence Research Agency, Malvern*

###
19 November The gabidulin
cryptosystem / *Keith Gibson, Birkbeck College, London*

Room TP4, Computer Laboratory

The Gabidulin Cryptosystem is a Public Key Cryptosystem (PKC) based on error correcting codes. Two versions of it have been published. After I showed how to break medium sized instances of the first version, Prof. Gabidulin agreed that his choice of system parameters was unfortunate, and produced a second set of parameters which he claimed were the most secure set possible. They turn out to be the least secure set possible, and this talk will show how to break even large instances of the second version in a matter of seconds, while at the same time showing how to choose the parameters so as to defeat my methods. Finding a secret key of an instance of the PKC can be reduced to solving an instance of an intriguing search problem of linear algebra, and it would be of great interest to know whether this problem is NP-complete, since there is no known PKC for which finding secret keys is NP-complete. One can make an intractability assumption that members of a certain family of instances of the search problem are almost always hard, and on this assumption the Gabidulin PKC is provably secure.

###
12 November Formal analysis of
protocols using induction / *Larry Paulson, Cambridge
University*

Room TP4, Computer Laboratory

Security protocols can be formally specified in terms of traces, which may involve many interleaved runs. Traces are defined inductively. Protocol descriptions model accidental key losses as well as attacks. The model spy can send spoof messages made up of components decrypted from previous traffic.

The approach has been implemented using the proof assistant Isabelle/HOL. Several symmetric-key protocols have been analysed, including Needham-Schroeder, Yahalom and Otway-Rees. A new attack has been discovered in a variant of Otway-Rees (already broken by Mao and Boyd). Assertions concerning secrecy and authenticity can be proved.

The approach rests on a common theory of messages, with three operators. The operator "parts" denotes the components of a set of messages. The operator "analz" denotes those parts that can be decrypted with known keys. The operator "synth" denotes those messages that can be expressed in terms of given components. The three operators enjoy many algebraic laws that are invaluable in proofs.

###
5 November Linking trust with
network reliability - the byzantine generals strike back / *Mike
Burmester, Royal Holloway, London*

Room TP4, Computer Laboratory

Reliability against failures from faulty links in an open network is usually assured by employing a network which has an appropriate topology. Security is assured by authenticating (and/or encrypting) the exchanged messages. For this, however, a certain degree of trust among the participating entities is needed. `Trusted paths' can be regarded as edges of a graph which we call the security graph. Usually it is assumed that this graph is almost complete, and that the entities are aware of its topology. In our scenario this is not the case.

We link trust with reliability, by analyzing the security graph. There are two models, a deterministic one in which the relative trust in a path is a Boolean expression, and a probabilistic one in which the vertices are assigned probabilities, and the trust in a path is a probability associated with the Boolean expression. We then discuss the `consensus problem' in the new scenario.

The talk is based on recent work with Yvo Desmedt. It is related to earlier work by Beth-Borcherding-Klein, Maurer and Reiter-Stubblebine, but differs in some important respects.

###
29 October New technologies and
better privacy / *Francis Aldhouse, Office of the Data Protection
Registrar*

Room TP4, Computer Laboratory

The Information Society will soon be upon us. Government and the private sector are looking to the new information technologies as a means of delivering goods and services more efficiently, more profitably and less expensively. Smart Cards and Active Badges to personalise network systems, Multimedia Work Space systems, e-mail communication can all be a benefit to the individual. At the same time these systems have the capability of increasingly tracking and recording our activities. They create a surveillance society by accident.

This need not be so. Technologies can be implemented to enhance and not invade personal privacy. Privacy enhancing technology should be the approach of the ethical engineer.

###
22 October Clock controlled sequence
generators and their cryptanalysis / *Bill Chambers, King's
College, London*

Room TP4, Computer Laboratory

There have been a number of recent developments in the design of clock-controlled shift registers, where feedback shift registers are stepped irregularly in an attempt to break up their linearity while maintaining good statistical properties. Among recent developments are the shrinking generator, and the "alleged A5" cipher. At the same time there have been a number of cryptanalytic attacks by Menicocci, by Zivkovic and by Golic, amongst others. I shall talk about basic generators such as the step-1/2 and shrinking generators and the attacks proposed by Zivkovic ("embedding") and Golic ("linearisation"). Then I shall consider the stop-go Gollmann cascades and the attacks proposed by Menicocci and by Park et al. (Here the clocking sequences are XOR'd with the outputs from the clocked registers.) The attacks proposed by Zivkovic have been extended to step-1/2 Gollmann cascades, and have been found equivalent to the "lock-in" attacks discovered earlier.

One of my big points is that most of these attacks are easily parried.

If time permits I shall mention some systems which have not yet been seriously attacked, in the hope of encouraging someone to have a go. Among these are systems with mutual clock-control, for which no very rigorous theory is known.

### 15 October
On the elgamal family signatures and electronic cash
/ *Wenbo Mao, Hewlett Packard Laboratories, Bristol*

###
8 October A calculus for
cryptographic protocols: the spi calculus / *Andy Gordon,
University of Cambridge*

Room TP4, Computer Laboratory

We introduce the spi calculus, an extension of the pi calculus designed for the description and analysis of cryptographic protocols. We show how to use the spi calculus, particularly for studying authentication protocols. The pi calculus (without extension) suffices for some abstract protocols; the spi calculus enables us to consider cryptographic issues in more detail. We represent protocols as processes in the spi calculus and state their security properties in terms of coarse-grained notions of protocol equivalence.

This is joint work with Martin Abadi.

###
23 September Symmetric-key ciphers
based on hard problems / *Matt Blaze, AT&T Research*

Room TP4, Computer Laboratory

A useful principle in cipher design is to reduce or at least relate closely the cryptanalysis of the cipher to some long-studied problem that is believed to be difficult. Most public-key ciphers follow this principle fairly closely (e.g., RSA is at least similar to factoring). Modern symmetric-key ciphers, on the other hand, can rarely be reduced in this way and so are frequently designed specifically to resist the various known cryptanalytic attacks. In this informal talk, we examine a simple cipher primitive, based on Feistel networks, for which recovery of its internal state given its inputs and outputs is NP-complete. We outline simple and efficient block- and stream- cipher constructions based on this primitive.