CIS-6935-8: Security Issues (Fall 2004)

Mike Burmester (
Breno de Medeiros (
Class time/location
FRI 2:00 - 3:00pm, 151 James Love Bldg (LOV)


Coming Topic

The past decade has seen growing interest in techniques for protecting critical data even in the face of catastrophic storage failure. A number of loosely related approaches seek to guard data by massively replicating records across a geographically distributed network of thousands of machines connected by high-speed links. This approach, sometimes referred to as survivable or pervasive information storage has been the subject of a number of research efforts. The goal of a survivable storage network is to guarantee data availability by ensuring that copies of each data object are stored at different locations in the system. Additionally, many survivable systems require that data be continuously re-distributed from place to place in order to maintain availability as individual storages fail or leave the network.

Secure storage systems seek to maintain not only the availability, but also the confidentiality and integrity of stored data despite the efforts of a motivated adversary. Complicating the design of these secure survivable storage systems is the possibility that large-scale distributed systems, particularly those composed of volunteers, are at increased risk of including untrustworthy or even malicious elements. By far the most common approach to securing data in large-scale storage networks is to encrypt data on the clientside, before it is submitted to the storage system. Strong client-side encryption is sufficient to protect the confidentiality of stored data, regardless of nature of the storage network. Unfortunately, client-side encryption cannot prevent all attacks on a distributed storage system. One concern is the possibility of correlation attack, in which an adversary identifies identical copies of a ciphertext stored on different nodes, in order to gain information on file usage and distribution. This problem is easily addressed through the use of randomized encryption, providing the client submits multiple unlinkable ciphertexts to the network. Unfortunately, this approach requires the participation of the client; if the attacker is not online, the storage network cannot generate new, unlinkable ciphertexts. Therefore, it is of particular concern when storage networks dynamically replicate records from one storage node to another without contacting the client. Unfortunately, none of the proposed survivable storage schemes provide mechanisms for dynamically re-encrypting a file without cooperation from the publisher or some on-line trusted party.

In this talk, we consider the problem of using untrusted components to build correlation-resistant distributed storage systems capable of on-demand re-encryption of stored files. Correlation-resistant storage systems are designed to provide remote retrieval of stored files, while resisting correlation attacks in which an adversary targets a storage system by linking instances of files that have been stored in different places within a storage system. We discuss the security requirements of these systems, and propose a protocol designed to allow dynamic re-encryption ensuring unlinkability between different instances of a file.

Previous talks

Chameleon signatures are non-interactive signature schemes that provide non-transferability. For wide applicability, a chameleon signature scheme should address the key exposure problem, or otherwise non-transferability is supported through exposure of the recipients secret key, and subsequent invalidation of all signatures issued to the associated public key.

Two distinct approaches have been proposed to address this key-revocation issue. Identity-based schemes employ single-use public keys (called customizable identities) tied to specific transactions, while key-exposure-free constructions directly eliminate the problem of key-exposure, for instance by splitting the public key into two components, one ephemeral and transactiondependent and the other permanent a scenario that requires multiple trapdoors. By clarifying the definitions and properties of identity-based and key-exposure-free schemes we reveal that, under certain assumptions, the two notions are equivalent.

We present several efficient and practical constructions of key exposure-free chameleon hash functions based on different cryptographic assumptions, such as the RSA and the discrete logarithm assumptions, including the first key-exposure free scheme that relies on a single trapdoor, instead using multiple signatures. This scheme is realizable over a large set of cryptographic groups (where the discrete logarithm is hard). Finally, we demonstrate the potential applicability of identity-based chameleon signatures in e-commerce by using them in the design of a closed auction protocol, and describe a proof-of-concept implementation of the protocol.
Dr. Wang presents his paper [1], to appear in IEEE Transactions on Computers.
Wireless has recently become a widely discussed research topic. Many people have already enjoyed the convenience provide by mobile phone systems. With the inclusion of mobile data services in the foreseeable future, we shall march into a new era of personal multimedia mobile communications service.
The paper presents a secure and anonymous conference call set-up scheme for a portable cellular mobile system. It uses techniques from identity-based cryptography to enable a mobile unit and a base station to directly authenticate each other by their public identity.
It provides subscribers with user identification privacy from other members of the conference call: Each mobile unit joining this system can determine whether it is part of a conference call, but it cannot derive any further information about who else is also in the conference.
Re-authentication in the course of hand-off is also discussed, and the reauthentication procedure is performed through a privacy homomorphism mechanism. The time computation with an 8-bit microcontroller handset is acceptable for performing an anonymous conference call in such mobile systems.
  1. Shiuh-Jeng Wang. Anonymous Wireless Authentication of a Portable Cellular Mobile System. In IEEE Transactions on Computers, vol. 53, no. 10, October 2004. Pp. 1317--1329.

  1. Goce Jakimoski will talk about (acyclic) AND/OR trust graphs, in which flows are used to measure trust (with appropriate weights: hopefully this will be defined by then(!)).

  2. Jiangyi Hu will talk about reputation models for secure routing in ad-hoc networks, in which trust/reputation is used to mitigate "node selfishness".

  3. Breno M. will introduce the topic of revocation. This topic is a natural continuation of the discussion on trust: Even if one has a robust infrastructure for authentication and for conveying trust, it does not follow that one has adequate mechanisms to withdraw this trust if it is violated, for instance by exposure of a private key. As a result, trust may be placed on entities and keys which are not trustworthy because trust revocation does not take place efficiently, timely, or at all. This topic will be followed by presentations by several students on our next meeting.

Trust is an essential component of any distributed system. We cannot have security without it. Trust is particularly needed in the context of public key cryptography.

But, what kind of trust do we need? Is "binary trust" sufficient, or do we need to work with a more fine-grained "degree" of trust? How do we define metrics for trust?

The seminar consist of two presentations:

  1. Mike B. will start with a discussion on Public Key Infrastructures Based on the Aug. 2004 article in the CACM (collaboration w. Yvo Desmedt): "Hierarchical Public-Key Certification: The Next Target for Hackers?". Viewable at: (skip 1st page).

  2. Karolina Maneva-Jakimoska will talk about weighted (acyclic) trust graphs, in which flows are used to measure trust (with probabilistic weights, based on good behavior).

Cryptography, once a subject of scientific inquiry only within military and intelligence circles, has established itself as a fertile area of academic research over the past few decades.  Increasing Governmental recognition of the maturity of non-classified cryptographic research is translated into an ongoing trend for standardization efforts to embrace transparent, competitive processes to choose cryptographic standards, such as the one that determined AES (Advanced Encryption Standard).  Indeed, it had become a matter of tacit agreement among security experts that reasonably strong cryptographic primitives were available in the open, commercial domain, and that practical security efforts should concentrate more on system engineering and human engineering aspects (e.g. protocol design and analysis, trust assumptions, economic incentives).

However, over the past few years developments in crypto-analytic techniques have placed question marks on many of these comfortable assumptions.  In particular, secure hash functions such as MD5 (highly used in practice)  seemed less and less resilient to increasingly sophisticated theoretical attacks, until it was successfully crypto-analyzed via a practical attack that takes an hour in an IBM P690 cluster (CRYPTO, 08/17/2004).  Equally worrisome are developments (also presented at CRYPTO 2004) that undermine confidence in the security of SHA-1, a NIST standard drafted by the NSA, and the only secure hash function approved for use by US Government agencies (and amended as recently as Feb. 2004).

Have we overestimated the security of our basic cryptographic primitives?  While good cryptography is only one piece in the edifice of a secure infrastructure, the economic consequences of adopting insecure cryptography can be  much bigger than mistakes at the higher levels -- for instance, a single cryptographic standard gets implemented in a myriad of systems.  If it needs to be replaced, all these systems need to be upgraded, often without the luxury of backward compatibility.

*Join us for an investigation of these very recent results.  I will give a slide presentation on secure hash
functions and the new developments, follow it with a video screening of the now notorious
CRYPTO 2004 Rump Session, and then open the floor to questions and discussions.*

During the past few years we have witnessed the rapid growth in the use of
network devices that are power-constrained and have limited computation
and communication capabilities. These devices range from PDAs and embedded
processors to arrays of sensors. They may be used in networks deployed in
hostile areas where communication can be monitored and altered, and thus
require cryptographic protection. However, the use of traditional
cryptographic constructs (e.g., public-key cryptography, conventional
authenticated encryption modes, and random number generators) may be
hampered by energy and computation constraints of these network devices.
"lightweight cryptography" offers practical alternatives
for use with many such devices particularly when they are networked on an
ad-hoc basis.

"Lightweight cryptography, or cryptolight" encompasses symmetric
encryption algorithms, modes of encryption, and key-management schemes
that require reduced levels of energy and can be deployed without
substantial infrastructures.

Valid HTML 4.01!