Identifying attributes and insecurity of a public-channel key exchange protocol using chaos synchronization

Klein et al. proposed a key exchange protocol using chaos synchronization. The first protocol comprises two parties with chaotic dynamics that are mutually coupled and undergo a synchronization process, at the end of which they can use their identical dynamical state as an encryption key. From cryptographic point of view, their key exchange protocol is a key agreement protocol. Klein et al. claimed that their key agreement can be carried out over a public channel. In order to increase the key space and decrease the precision of the calculation, they made an extension of the system to a network of N Lorenz equations. In this paper, we will provide a cryptanalysis of their key agreement protocol. We will first point out some weaknesses, and then show that their protocol is not secure against several attacks including impersonation attack.     

Properties of certain semigroups and their potential as platforms for cryptosystems

In this paper, we study some properties of semigroups with presentation 〈a,b ; a ^p =b ^r ,a ^q =b ^s 〉. We will also study their potential as platforms for the Diffie-Hellman key exchange protocol.     

Anonymity and one-way authentication in key exchange protocols

Key establishment is a crucial cryptographic primitive for building secure communication channels between two parties in a network. It has been studied extensively in theory and widely deployed in practice. In the research literature a typical protocol in the public-key setting aims for key secrecy and mutual authentication. However, there are many important practical scenarios where mutual authentication is undesirable, such as in anonymity networks like Tor, or is difficult to achieve due to insufficient public-key infrastructure at the user level, as is the case on the Internet today. In this work we are concerned with the scenario where two parties establish a private shared session key, but only one party authenticates to the other; in fact, the unauthenticated party may wish to have strong anonymity guarantees. We present a desirable set of security, authentication, and anonymity goals for this setting and develop a model which captures these properties. Our approach allows for clients to choose among different levels of authentication. We also describe an attack on a previous protocol of Øverlier and Syverson, and present a new, efficient key exchange protocol that provides one-way authentication and anonymity.     

The <Emphasis Type="Italic">SU</Emphasis>(3) symmetry and macroscopic dynamics of magnets with spin <Emphasis Type="Italic">s</Emphasis> = 1

In the Hamiltonian approach, we derive nonlinear dynamic equations for magnetic media with spin s = 1. We introduce two types of magnetic exchange Hamiltonians corresponding to the Casimir invariants of the SU(3) group. We find the spectra of spin and quadrupole waves corresponding to the states with different symmetries under the time reversal transformation. We consider the effect of dissipative processes and find relaxation fluxes caused by the exchange symmetry of the magnetic Hamiltonian.     

Application of (v, k, λ)-configuration to generation of a conference key

In order for all participants at video conference to communicate mutually, the conference key should be necessary. In this paper, we present the communication protocol that generates a conference key efficiently based on (v,k,λ)-configuration, one class of block designs, which minimizes message transmission overhead needed for this key. Especially, in the case of λ=1, the protocol requires only O(v√v) messages, where v is the number of participants.     

Efficient RFID authentication protocols based on pseudorandom sequence generators

In this paper, we introduce a new class of PRSGs, called partitioned pseudorandom sequence generators(PPRSGs), and propose an RFID authentication protocol using a PPRSG, called S-protocol. Since most existing stream ciphers can be regarded as secure PPRSGs, and stream ciphers outperform other types of symmetric key primitives such as block ciphers and hash functions in terms of power, performance and gate size, S-protocol is expected to be suitable for use in highly constrained environments such as RFID systems. We present a formal proof that guarantees resistance of S-protocol to desynchronization and tag-impersonation attacks. Specifically, we reduce the availability of S-protocol to pseudorandomness of the underlying PPRSG, and the security of the protocol to the availability. Finally, we give a modification of S-protocol, called S*-protocol, that provides mutual authentication of tag and reader.      

EXCHANGE MORITA RINGS

In this paper we characterize the largest exchange ideal of a ring R as the set of those elements x ∈ R such that the local ring of R at x is an exchange ring. We use this result to prove that if R and S are two rings for which there is a quasi-acceptable Morita context, then R is an exchange ring if and only if S is an exchange ring, extending an analogue result given previously by Ara and the second and third authors for idempotent rings. We introduce the notion of exchange associative pair and obtain some results connecting the exchange property and the possibility of lifting idempotents modulo left ideals. In particular we obtain that in any exchange ring, orthogonal von Neumann regular elements can be lifted modulo any one-sided ideal.     

The Las-Vegas Processor Identity Problem (How and When to Be Unique)

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is that upon termination of the algorithm, the processes must have unique IDs always. Our results include tight characterization of the problem in several respects. We call a protocol solving this task Las Vegas if it has finite expected termination time. Our main positive result is the first Las-Vegas protocol that solves the problem. The protocol terminates in O(log n) expected asychronous rounds, using O(n) shared memory space, where n is the number of participating processes. The new protocol improves on all previous solutions simultaneously in running time (exponentially), probability of termination (to 1), and space requirement. The protocol works under the assumption that the asynchronous schedule is oblivious, i.e., independent of the actual unfolding execution. On the negative side, we show that there is no finite-state Las-Vegas protocol for the problem if the schedule may depend on the history of the shared memory (an adaptive schedule). We also show that any Las-Vegas protocol must know n in advance (which implies that crash faults cannot be tolerated) and that the running time is Ω(log n). For the case of an arbitrary (nonoblivious) adversarial schedule, we present a Las-Vegas protocol that uses O(n) unbounded registers. For the read-modify-write model, we present a constant-space deterministic algorithm.     

An improved key agreement protocol based on chaos

Cryptography based on chaos theory has developed fast in the past few years, but most of the researches focus on secret key cryptography. There are few public key encryption algorithms and cryptographic protocols based on chaos, which are also of great importance for network security. We introduce an enhanced key agreement protocol based on Chebyshev chaotic map. Utilizing the semi-group property of Chebyshev polynomials, the proposed key exchange algorithm works like Diffie–Hellman algorithm. The improved protocol overcomes the drawbacks of several previously proposed chaotic key agreement protocols. Both analytical and experimental results show that it is effective and secure.     

Authentication and authenticated key exchanges

We discuss two-party mutual authentication protocols providing authenticated key exchange, focusing on those using asymmetric techniques. A simple, efficient protocol referred to as the station-to-station (STS) protocol is introduced, examined in detail, and considered in relation to existing protocols. The definition of a secure protocol is considered, and desirable characteristics of secure protocols are discussed.This work was done while Whitfield Diffie was with Northern Telecom, Mountain View, California.     

A Formal Language for Cryptographic Protocol Requirements

In this paper we present a formal language for specifying and reasoning about cryptographic protocol requirements. We give sets of requirements for key distribution protocols and for key agreement protocols in that language. We look at a key agreement protocol due to Aziz and Diffie that might meet those requirements and show how to specify it in the language of the NRL Protocol Analyzer. We also show how to map our formal requirements to the language of the NRL Protocol Analyzer and use the Analyzer to show that the protocol meets those requirements. In other words, we use the Analyzer to assess the validity of the formulae that make up the requirements in models of the protocol. Our analysis reveals an implicit assumption about implementations of the protocol and reveals subtleties in the kinds of requirements one might specify for similar protocols.     

On the Direct Indecomposability of Infinite Irreducible Coxeter Groups and the Isomorphism Problem of Coxeter Groups

In this article, we prove that any irreducible Coxeter group of infinite order, which is possibly of infinite rank, is directly indecomposable as an abstract group. The key ingredient of the proof is that we can determine, for an irreducible Coxeter group W, the centralizers in W of the normal subgroups of W that are generated by involu-tions. As a consequence, the problem of deciding whether two general Coxeter groups are isomorphic is reduced to the case of irreducible ones. We also describe the automorphism group of a general Coxeter group in terms of those of its irreducible components.     

Triangular Witt groups Part II: From usual to derived

   Abstract. We establish that the derived Witt group is isomorphic to the usual Witt group when 2 is invertible. This key result opens the Ali Baba's cave of triangular Witt groups, linking the abstract results of Part I to classical questions for the usual Witt group. For commercial purposes, we survey the future applications of triangular Witt groups in the introduction. We also establish a connection between odd-indexed Witt groups and formations. Finally, we prove that over a commutative local ring in which 2 is a unit, the shifted derived Witt groups are all zero but the usual one. Received July 15, 1999; in final form November 8, 1999 / Published online October 30, 2000     

H-supplemented Modules and Generalizations of Quasi-discrete Modules

In this article, we introduce a generalization of quasi-discrete (a GQD-module) by using the notion of H-supplemented modules and investigate some properties of GQD-modules. First we consider some properties of a relative radical projectivity which is useful in analyzing the structure of H-supplemented modules. We apply them to the study of direct sums of GQD-modules. Moreover, we prove that any H-supplemented (lifting) module with finite internal exchange properly (FIEP) has an indecomposable decomposition and show that, for an H-supplemented (lifting) module, the finite exchange property implies the full exchange property.     

Cryptography in Quadratic Function Fields

We describe severalcryptographic schemes in quadratic function fields of odd characteristic.In both the real and the imaginary representation of such a field,we present a Diffie-Hellman-like key exchange protocol as wellas a public-key cryptosystem and a signature scheme of ElGamaltype. Several of these schemes are improvements of systems previouslyfound in the literature, while others are new. All systems arebased on an appropriate discrete logarithm problem. In the imaginarysetting, this is the discrete logarithm problem in the idealclass group of the field, or equivalently, in the Jacobian ofthe curve defining the function field. In the real case, theproblem in question is the task of computing distances in theset of reduced principal ideals, which is a monoid under a suitableoperation. Currently, the best general algorithms for solvingboth discrete logarithm problems are exponential (subexponentialonly in fields of high genus), resulting in a possibly higherlevel of security than that of conventional discrete logarithmbased schemes.     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

An improvement of the Diffie–Hellman noncommutative protocol

Designs, Codes and Cryptography - The main purpose of this paper is to propose a new version of the Diffie–Hellman noncommutative key exchange protocol invented in 2000 by Ko, Lee, Cheon,...     

Structure of <Emphasis Type="Italic">K</Emphasis>-interval exchange transformations: Induction,trajectories, and distance theorems

We define a new induction algorithm for k-interval exchange transformations associated to the “symmetric” permutation i ↦ k − i + 1. Acting as a multi-dimensional continued fraction algorithm, it defines a sequence of generalized partial quotients given by an infinite path in a graph whose vertices, or states, are certain trees we call trees of relations. This induction is self-dual for the duality between the usual Rauzy induction and the da Rocha induction. We use it to describe those words obtained by coding orbits of points under a symmetric interval exchange, in terms of the generalized partial quotients associated with the vector of lengths of the k intervals. As a consequence, we improve a bound of Boshernitzan in a generalization of the three-distances theorem for rotations. However, a variant of our algorithm, applied to a class of interval exchange transformations with a different permutation, shows that the former bound is optimal outside the hyperelliptic class of permutations.     

Strengthening the security of authenticated key exchange against bad randomness

Recent history has revealed that many random number generators (RNGs) used in cryptographic algorithms and protocols were not providing appropriate randomness, either by accident or on purpose. Subsequently, researchers have proposed new algorithms and protocols that are less dependent on the RNG. One exception is that all prominent authenticated key exchange (AKE) protocols are insecure given bad randomness, even when using good long-term keying material. We analyse the security of AKE protocols in the presence of adversaries that can perform attacks based on chosen randomness, i.e., attacks in which the adversary controls the randomness used in protocol sessions. We propose novel stateful protocols, which modify memory shared among a user’s sessions, and show in what sense they are secure against this worst case randomness failure. We develop a stronger security notion for AKE protocols that captures the security that we can achieve under such failures, and prove that our main protocol is correct in this model. Our protocols make substantially weaker assumptions on the RNG than existing protocols.