COSIC: COmputer Security and Industrial Cryptography
The research activities in this group are concentrated on the design,
evaluation, and implementation of cryptographic algorithms and protocols,
and on security architectures for computers and telecommunications networks.
The research is oriented to fundamental problems with a practical importance.
COSIC's theoretical work on cryptographic algorithms and protocols is mainly based on discrete mathematics (number theory, finite fields, Boolean functions, finite geometry); other fields of mathematics relevant to our research include statistics and optimization. The goal is to achieve efficient and (provably) secure solutions.
COSIC intends to integrate these solutions into different applications including computer systems, telecommunications systems (Internet security, mobile communications), and payment systems. Important aspect here are the efficient implementation (in both software and hardware) of cryptographic primitives and the security evaluation of components and systems.
COSIC is headed by René Govaerts and Joos Vandewalle, and has three post-doctoral researchers and 10 Ph.D. students.
COSIC collaborates closely with the company Utimaco Belgium.
COSIC also cooperates with the University of California at Berkeley,
R
Security Engineering,
Entrust Technologies, Bell Northern Research, RSA Laboratories,
Stanford University, Diva Communications,
the Dutch organization for Applied Scientific Research (TNO),
Vodafone Ltd, Siemens-ATEA, Giesecke & Devrient, Panafon SA, Royal Holloway
University of London, Siemens AG, Lernout and Hauspie,
Dutch Ministry of Transport and Public Works, TÜV Rheinland,
Finnish National Road Administration, RAPP Engineers and Planners Ltd,
Transport Research Laboratory, Association Européenne des
Concessionnaires d'Autoroutes et d'Ouvrages à Péage,
U.C.L., Banksys, Belgacom, Europay International, Roularta N.V., ICRI.
Design and Analysis of Block Ciphers
R. Govaerts, J. Vandewalle, B. Preneel, L.R. Knudsen, V. Rijmen,
J. Borst, J. Daemen.
IDEA is a block cipher developed by X. Lai and J.L. Massey. It is used in several applications, PGP being probably the most commonly known example. IDEA uses algebraic operations from three different groups (exor, modular addition and multiplication) to obtain a very high resistance against linear and differential cryptanalysis.
We observed that the probability of linear relations for IDEA can vary substantially over all possible keys. While the average probabilities are indeed low, it is possible to define a family of relations such that for every key at least one relation has high probability. In this way we were able to break IDEA reduced to three rounds.
In a second stage a truncated differential attack was mounted on IDEA reduced to 3.5 rounds. The attack exploits the key dependency of the differentials' probability.
RC5 is a block cipher developed by R. Rivest in 1994. It has received widespread attention because of its simplicity and apparent strength. A first analysis of RC5 was made by Kaliski and Yin in 1995. We improved the existing attacks considerably and showed that the strength of RC5 is less than first assumed. However, our attacks are still not practical.
On the design front, the block cipher Square was developed in cooperation with Joan Daemen. Like Shark, Square uses an MDS-code to obtain good diffusion. Where Shark was oriented towards high-end computer architectures, Square can be implemented on a wide range of processors. Much attention was paid to facilitate encryption on a smart card.
We demonstrated how to build a block cipher with a trapdoor that allows to recover the key with a small amount of known plaintexts. A user that does not know the trapdoor, cannot detect it, even if he suspects that a trapdoor is present. Trapdoor block ciphers can be used to build a public key encryption scheme that does not depend on the difficulty of a number theoretic problem such as discrete log and factorization.
Analysis and Design of Hash Functions
{R. Govaerts, J. Vandewalle, B. Preneel, L. Knudsen, A. Bosselaers,
H. Dobbertin.
Cryptographic hash functions are functions that compress an input of arbitrary size to a fixed length result. They are a useful building block for applications such as the authentication of information, digital signatures, and the protection of passwords and pass-phrases.
A new approach has been developed for the design of hash functions based on block ciphers. A new class of constructions has been proposed based on quaternary error-correcting codes. The resulting hash functions are more efficient than previous proposals. Under reasonable assumptions about the underlying block cipher, the construction yields collision resistant compression functions. The approach has been extended to codes over larger fields, and to block ciphers with a key larger than the block size (such as IDEA).
The hash function RIPEMD-160 has been designed in collaboration with Hans Dobbertin of BSI, Germany. RIPEMD-160 is a 160-bit cryptographic hash function which is intended to be used as a secure replacement for the 128-bit hash functions MD4, MD5, and RIPEMD. MD4 and MD5 were developed by Ron Rivest for RSA Data Security, while RIPEMD was developed in the framework of the EU RACE/RIPE project. For backwards compatibility, RIPEMD-128 has been designed, with a 128-bit result. Both hash functions have been included in ISO/IEC 10118-3, which will be published in 1997. More info at http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.
Cryptanalysis of Message Authentication Codes
R. Govaerts, J. Vandewalle, B. Preneel, V. Rijmen,
P.C. van Oorschot.
Message Authentication Codes or MACs are cryptographic hash functions that take as a secondary input a secret key; they are mainly used for conventional message authentication. The most important requirement for a MAC is that someone who does not know the secret key is not able to forge the MAC on a message of his choice.
A new forgery attack applicable to all iterated MAC algorithms
has been developed in 1995.
In 1996, this attack has been further extended to a key recovery attack.
This key recovery attack has been applied to two standardized MAC algorithms,
one from ISO 8731-2 and one from ANSI X9.19/ISO/IEC 9797. As a consequence,
the Message Authenticator Algorithm (MAA) will be removed from the
new edition of ISO 8731-2, and ISO/IEC 9797 will be revised to warn
users for this attack. The latter attack reduces a 
key search to a 
key search using only 
known text-MAC
pairs.
Elliptic Curve Public-Key Cryptosystems
R. Govaerts, J. Vandewalle, B. Preneel, E. De Win.
Elliptic curves are relatively new in cryptography. An elliptic curve is the set of solutions of a cubic bivariate equation over a field, typically a finite field of characteristic 2. The definition of an appropriate binary operation turns this set into a group.
The discrete logarithm problem over this group is considerably
more complex than the discrete logarithm problem over finite fields or
than integer factorization. Therefore, block sizes and keys can be
considerably smaller than for other public key algorithms. E.g., to
obtain the security of RSA with a 1024-bit modulus, it is estimated that
an elliptic curve over a finite field with only 
elements
(155 bits) is required.
To perform operations over an elliptic curve, one must be able to calculate in the underlying field. Several ways to do arithmetic operations in finite fields of characteristic 2 have been examined and the fastest have been implemented. The table below gives timing information for some important operations and estimates timings for elliptic curve operations over fields of approximately 177 bits.
Table 1:
Times for basic operations on polynomials over GF(2) and
over GF(
). The lengths of the polynomials are suited for field
operations in GF(
) and GF(
), respectively. The tests
ere
run on a Pentium/133 based PC using the Watcom 10.6 ANSI-C compiler.
Exploiting Parallelism in a Family of Dedicated Hash Functions
R. Govaerts, J. Vandewalle, A. Bosselaers.
The most popular cryptographic hash functions, currently used in a wide variety of applications, are the custom designed iterative hash functions from the MD4-family. MD4 was introduced in 1990 by R. Rivest. One of the design principles was to be fast on 32-bit machines in general, and on the Intel Architecture (IA) in particular. Since the introduction of MD4, and as a result of developments in cryptanalysis a whole family of MD4-like hash functions has been developed: MD5, RIPEMD, SHA-1, RIPEMD-128, and RIPEMD-160.
With the advent of the Pentium processor parallelization finally became available to Intel based computer systems. Carefully coded implementations of these hash functions are able to exploit the Pentium's superscalar architecture to its maximum effect: the performance with respect to execution on a non-parallel architecture increases by about 75%. The performance penalty incurred by non-cached data and endianness conversion is limited, and in the order of 10% of running time. Table 2 compares the performance of our Assembly implementation with a portable C implementation.
Table 2:
Code size and hashing speeds of the different compression functions
on a 90 MHz Pentium both for our Assembly
implementations and a corresponding portable C implementation (Watcom C 10.6).
The code size only refers to the Assembly implementations.
Both code and data are assumed to reside in the 8K on-chip caches.
Key Escrow
R. Govaerts, J. Vandewalle, L.R. Knudsen, T. Petersen.
We have shown that a key escrow scheme proposed by Y. Desmedt can be broken. We showed how to repair Desmedt's scheme, such that our attacks are no longer possible, but by allowing slightly more general attacks also this improved system was broken.
Our attacks illustrate that software key escrow, as proposed by Desmedt, will be very hard to implement as it requires that the distributed public keys are only used in few, well-defined systems. In general, we showed how most key escrow applications to key distribution can be broken.
Security Aspects of Electronic Payment Systems
R. Govaerts, J. Vandewalle, C. Radu.
We proposed a coin-based electronic payment system suitable for small payments. It is derived from Brands' scheme presented at Crypto'93, in the sense that the coins are built using the representation problem. The main contribution of our solution consists of the speedup of the withdrawal protocol. The gain in efficiency is achieved without sacrificing the level of integrity for user, shop, or bank. A coin remains untraceable with respect to the user. This feature is fulfilled even if one assumes that the bank has unlimited computing power and colludes with shops in order to trace a coin to a specific user. However, a set of coins is linkable to a pseudonym of the user, restricting in this way his privacy. This drawback can be limited by ``rotating'' coins derived from different pseudonyms in a set of consecutive payment transactions.
Security on the Internet
R. Govaerts, J. Vandewalle, M. Vandenwauver
In recent years, many organizations have shifted their computing facilities from central mainframes (accessed from simple terminals via serial lines) to servers accessed from personal computers via a local area network (LAN). The Internet is a prime example of this. The move to LANs removed some old problems and introduced some new ones. Many of these new challenges are not particularly related to security. For example, backup and recovery from equipment failures require a different approach. However, our work stresses the security problems involved in this picture.
If one does not know where data has come from or where it is going to, it is difficult to enforce almost any kind of security policy. It is therefore essential that one has an effective form of authentication that works in the new LAN environment. Research in this area resulted in the project SESAME ( http://www.esat.kuleuven.ac.be/cosic/sesame). It is based on the Kerberos system but adds several extra features:
Thanks to the widespread success of the Internet, the use of electronic mail has become common practice. More and more people are even using it as a primary means of communication. Unfortunately, regular users are not aware of the risks they are facing. If you send a regular letter, you can rely on the confidentiality of its content but not so with plain e-mail. Each message can be intercepted by a trained computer user connected to the net. It is fairly easy to read other people's e-mail, and even change it without being caught. Thanks to an extensive use of cryptography, we can limit these risks. An overview of the latest available standards and tools has been compiled and analyzed.
Due to the demands for Electronic Commerce, introducing security on the World Wide Web, has become a hot topic. There exist at this moment several solutions that usually work on different layers of the OSI transport model. In a first stage SSL (Secure Sockets Layers) is being implemented and tested. Afterwards we plan to build a sort of client proxy so that regular export-allowed browsers (Navigator or IE) that typically only support low-grade security, will be able to build highly secure (128 bit) connections to enhanced servers.
Visual Cryptography
R. Govaerts, J. Vandewalle, B. Preneel, V. Rijmen
At Eurocrypt'94, M. Naor and A. Shamir have introduced the concept of visual cryptography. The basic idea is to ``share'' the information of a black-and-white picture over two or more transparencies. While the separate transparencies reveal no information, the picture reveals itself when enough transparencies are stacked. This technique relies heavily on the abilities of the human visual system.
The technique was extended to encode multi-colour pictures in an
efficient way. A second extension makes the black-and-white pictures
more robust against misalignment in one direction, which often results
from transmitting pictures with a fax. More info at
http://www.esat.kuleuven.ac.be/~rijmen/vc.
Evaluation of Cryptographic Soft- and Hardware
R. Govaerts, J. Vandewalle, B. Preneel, A. Bosselaers,
M. Vandenwauver, V. Rijmen, E. De Win, D. De Cock, S. Hoeben.
In an industrial environment the communications network is the first place where special protection is introduced, as this is certainly one of the most vulnerable parts of an information system. Depending on the application, the users require protection of the information against disclosure and/or the protection of the authenticity of the information and its origin. This protection can only be achieved through the use of cryptographic algorithms, implemented either in hardware or in software. Two types of algorithms are available on the market: algorithms that are public and widely used, and secret algorithms.
A public algorithm has the advantage that is has been thoroughly analyzed and that security properties are well-known. However, the fact that an algorithm is widely used implies that the number of potential attackers increases, and that it offers an interesting target. A breakthrough in cryptanalysis will result in a substantial benefit and the cost of special purpose hardware can be depreciated over different applications. These considerations explain the preference of several organizations for secret algorithms or for variations on publicly known algorithms. However, one has to be very careful with this type of algorithms as a large number of them were declared secure by their designers but have been broken afterwards. As a consequence, a secret algorithm must be evaluated by different cryptographic experts before it can be given any trust. Such an independent evaluation is based on literature study, and both algebraic and statistical evaluation. In addition, recommendations can be made to improve the security of the system. The difference with an academic evaluation is that imposed requirements are to be related to the economic implications of a successful fraud. For both types of algorithms one also has to pay special attention to the cryptographic protocols and the key management system.
Advanced Security for Personal Communications Technologies (ACTS 095
ASPeCT)
R. Govaerts, J. Vandewalle, B. Preneel, L. Knudsen,
K. Martin, F. Mertens, A. Bosselaers.
The mobile telecommunications world is undergoing a continuing transformation as increasing numbers of services are being offered to a growing number of users by more and more operators. It is essential for the continuing success of this process that the evolving security requirements of users and service providers are addressed in an appropriate and timely way.
The goal of ASPeCT is to study the feasibility and acceptability of new and advanced security features in existing and future personal communications networks, based on trials and demonstrations.
In the second year of the project, COSIC has been working on the use of Trusted Third parties to support encryption offering end-to-end confidentiality with key escrow. COSIC is mainly contributing to the design of protocols and the software implementation of the certificates. COSIC has also been working on fraud detection in UMTS (Universal Mobile Telecommunication System); COSIC is exploring an approach based on neural networks in collaboration with SISTA. COSIC is also involved in an exploration of the capabilities of future User Identity Modules and in work on protocols offering security and integrity of billing in UMTS. More information can be found on the ASPeCT WWW home page http://www.esat.kuleuven.ac.be/cosic/aspect.
Motorway Operators Validate EFC for Interoperable Transport
(TR 1105 MOVE-it)
R. Govaerts, J. Vandewalle, C. Radu, A. Bosselaers.
The objective of the MOVE-it consortium is to pave the way towards trans-European interoperability for motorway tolling. The project is part of the Telematics Application Programme, funded by the European Commission. MOVE-it primarily focuses on the aspects of contractual interoperability: achieving consensus on the ways to identify and overcome the legislative, institutional and commercial obstacles towards interoperability. The project also performs a high level analysis of the user needs identified in existing and emerging standards as well as in related projects. More in particular MOVE-it addresses issues concerning security, vehicle classification and non-equipped users. Together with the investigations into contractual interoperability this will result in a consensus view from the European motorway operators and national authorities.
COSIC is involved in elaborating a security framework for the Electronic Fee Collection (EFC) system. In the first year a general EFC model was developed, based on existing work from CEN/TC278/WG1 and other European projects like CASH, CARDME, and CAFE. Next, a threat and risk analysis was done, concentrating on the threats and risks associated with each entity involved in the EFC system. In the second year a security framework will be designed.
Digital time-stamping and the evaluation of security primitives
(TimeSec)
R. Govaerts, J. Vandewalle, B. Preneel, B. Van Rompay.
The aim of this project is to develop a complete system for digital time-stamping as well as an evaluation methodology for security primitives. Technical solutions for time-stamping have been proposed in the past, but they leave some open problems, and no consensus on a single scheme has emerged. It is anticipated that additional precompetitive research in this area will result in an acceptable standard. A related problem is the evaluation of security primitives for digital time-stamping in particular, and for other information security services in general. A comprehensive evaluation methodology for such primitives will be developed.
The project started in the second half of 1996 with the the development of an evaluation methodology for cryptographic hash functions and block ciphers.
Media On-Line (MOL)
R. Govaerts, J. Vandewalle, B. Preneel, A. Bosselaers, S. Hoeben.
The goal of this project is to study several aspects of secure electronic publishing: secure messaging, public-key infrastructure, secure electronic payments, and copyright protection.
The project started in the second half of 1996 with a study phase on public-key infrastructures.