Certificateless signature: a new security model and an improved generic construction

Certificateless cryptography involves a Key Generation Center (KGC) which issues a partial key to a user and the user also independently generates an additional public/secret key pair in such a way that the KGC who knows only the partial key but not the additional secret key is not able to do any cryptographic operation on behalf of the user; and a third party who replaces the public/secret key pair but does not know the partial key cannot do any cryptographic operation as the user either. We call this attack launched by the third party as the key replacement attack. In ACISP 2004, Yum and Lee proposed a generic construction of digital signature schemes under the framework of certificateless cryptography. In this paper, we show that their generic construction is insecure against key replacement attack. In particular, we give some concrete examples to show that the security requirements of some building blocks they specified are insufficient to support some of their security claims. We then propose a modification of their scheme and show its security in a new and simplified security model. We show that our simplified definition and adversarial model not only capture all the distinct features of certificateless signature but are also more versatile when compared with all the comparable ones. We believe that the model itself is of independent interest.A conventional certificateless signature scheme only achieves Girault’s Level 2 security. For achieving Level 3 security, that a conventional signature scheme in Public Key Infrastructure does, we propose an extension to our definition of certificateless signature scheme and introduce an additional security model for this extension. We show that our generic construction satisfies Level 3 security after some appropriate and simple modification. A preliminary version of the extended abstract of partial results appeared in ACISP 2006 [9].     

The (related-key) impossible boomerang attack and its application to the AES block cipher

The Advanced Encryption Standard (AES) is a 128-bit block cipher with a user key of 128, 192 or 256 bits, released by NIST in 2001 as the next-generation data encryption standard for use in the USA. It was adopted as an ISO international standard in 2005. Impossible differential cryptanalysis and the boomerang attack are powerful variants of differential cryptanalysis for analysing the security of a block cipher. In this paper, building on the notions of impossible differential cryptanalysis and the boomerang attack, we propose a new cryptanalytic technique, which we call the impossible boomerang attack, and then describe an extension of this attack which applies in a related-key attack scenario. Finally, we apply the impossible boomerang attack to break 6-round AES with 128 key bits and 7-round AES with 192/256 key bits, and using two related keys we apply the related-key impossible boomerang attack to break 8-round AES with 192 key bits and 9-round AES with 256 key bits. In the two-key related-key attack scenario, our results, which were the first to achieve this amount of attacked rounds, match the best currently known results for AES with 192/256 key bits in terms of the numbers of attacked rounds. The (related-key) impossible boomerang attack is a general cryptanalytic technique, and can potentially be used to cryptanalyse other block ciphers.     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.     

Identifying large robust network clusters via new compact formulations of maximum k-club problems

Network robustness issues are crucial in a variety of application areas. In many situations, one of the key robustness requirements is the connectivity between each pair of nodes through a path that is short enough, which makes a network cluster more robust with respect to potential network component disruptions. A k-club, which by definition is a subgraph of a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We develop a new compact linear 0-1 programming formulation for finding maximum k-clubs that has substantially fewer entities compared to the previously known formulation (O(kn²) instead of O(n^k+1), which is important in the general case of k > 2) and is rather tight despite its compactness. Moreover, we introduce a new related concept referred to as an R-robust k-club (or, (k, R)-club), which naturally arises from the developed k-club formulations and extends the standard definition of a k-club by explicitly requiring that there must be at least R distinct paths of length at most k between all pairs of nodes. A compact formulation for the maximum R-robust k-club problem is also developed, and error and attack tolerance properties of the important special case of R-robust 2-clubs are investigated. Computational results are presented for multiple types of random graph instances.     

A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.     

Cryptanalysis of the Stream Cipher LEX

Biryukov (The Design of a Stream Cipher LEX, Proceedings of Selected Areas in Cryptography, 2006 Springer, pp 67–75, 2007) presented a new methodology of stream cipher design called leak extraction. The stream cipher LEX, based on this methodology and on the AES block cipher, was selected to round 3 of the eSTREAM competition. The suggested methodology seemed promising, and LEX, due to its elegance, simplicity, and performance, was expected to be selected to the eSTREAM portfolio. In this article we present a key recovery attack on LEX. The attack requires about 2⁴⁰ bytes of key-stream produced by the same key (possibly under many different IVs), and retrieves the secret key in time of about 2¹⁰⁰ AES encryptions. Following a preliminary version of our attack, LEX was discarded from the final portfolio of eSTREAM.     

Improved cryptanalysis of rank metric schemes based on Gabidulin codes

We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck’s structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way corrects less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender. Consequently, an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.     

The timing and deterrence of terrorist attacks due to exogenous dynamics

In this paper, we develop a model for the timing and deterrence of terrorist attacks due to exogenous dynamics. The defender moves first and the attacker second in a two-stage game which is repeated over T periods. We study the effects of dynamics of several critical components of counter-terrorism games, including the unit defence costs (eg, immediately after an attack, the defender would easily acquire defensive funding), unit attack costs (eg, the attacker may accumulate resources as time goes), and the asset valuation (eg, the asset valuation may change over time). We study deterministic dynamics and conduct simulations using random dynamics. We determine the timing of terrorist attacks and how these can be deterred.     

Light tails and the Hermitian dual polar graphs

This paper investigates ciphers where the set of encryption functions is identical to the set of decryption functions, which we call reflection ciphers. Equivalently, there exists a permutation P, named the coupling permutation, such that decryption under k corresponds to encryption under P(k). We study the necessary properties for this coupling permutation. Special care has to be taken of some related-key distinguishers since, in the context of reflection ciphers, they may provide attacks in the single-key setting. We then derive some criteria for constructing secure reflection ciphers and analyze the security properties of different families of coupling permutations. Finally, we concentrate on the case of reflection block ciphers and, as an illustration, we provide concrete examples of key schedules corresponding to several coupling permutations, which lead to new variants of the block cipher prince.     

Asymptotically fast solution of toeplitz and related systems of linear equations

We present an inversion algorithm for the solution of a generic N X N Toeplitz system of linear equations with computational complexity O(Nlog²N) and storage requirements O(N). The algorithm relies upon the known structure of Toeplitz matrices and their inverses and achieves speed through a doubling method. All the results are derived and stated in terms of the recent concept of displacement rank, and this is used to extend the scope of the algorithm to include a wider class of matrices than just Toeplitz and also to include block Toeplitz matrices.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.     

Sampled-data-based consensus of multi-agent systems under asynchronous denial-of-service attacks

This paper investigates the sampled-data-based consensus problem of multi-agent systems (MASs) under asynchronous denial-of-service (DoS) attacks. In order to describe asynchronous DoS attacks, a new definition of complete DoS attack and novel double-layer switched systems are proposed. A complete DoS attack refers to a DoS attack that consists of several consecutive successful DoS attacks. While a successful DoS attack denotes an attack that can break the connected communication topology into several isolated subgraphs. Based on this, the original system is transformed into a double-layer switched systems with a stable mode and several unstable modes. It should be pointed out that each unstable subsystem is also composed of finite second-level unstable subsystems that represent consecutive successful DoS attacks. Moreover, a new double-mode-dependent Lyapunov function (DMDLF) method is employed to obtain the lower and upper bounds of the corresponding average dwell time (ADT) of subsystems. It is proved that the consensus of MASs under asynchronous DoS attacks can be achieved by using the feedback consensus controllers which can be designed simultaneously. Finally, an illustrative example is provided to illustrate the effectiveness of the results proposed in this paper.     

Performance evaluation of evolutionary class of algorithms—An application to 0–1 knapsack problem

The 0–1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification. We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.     

A New Approach for Visual Cryptography

Visual cryptography is to encrypt a secret image into some shares (transparencies) such that any qualified subset of the shares can recover the secret visually. The conventional definition requires that the revealed secret images are always darker than the backgrounds. We observed that this is not necessary, in particular, for the textual images.In this paper, we proposed an improved definition for visual cryptography based on our observation, in which the revealed images may be darker or lighter than the backgrounds. We studied properties and obtained bounds for visual cryptography schemes based on the new definition. We proposed methods to construct visual cryptography schemes based on the new definition. The experiments showed that visual cryptography schemes based on our definition indeed have better pixel expansion in average.     

Encomplexed Brown invariant of real algebraic surfaces in ℝP 3

We construct an invariant of parametrized generic real algebraic surfaces in ?P ³ which generalizes the Brown invariant of immersed surfaces from smooth topology. The invariant is constructed using self-intersections, which are real algebraic curves with points of three local characters: the intersection of two real sheets, the intersection of two complex conjugate sheets or a Whitney umbrella. In Kirby and Melvin (Local surgery formulas for quantum invariants and the Arf invariant, in Proceedings of the Casson Fest, Geom. Topol. Monogr. 7, pp. 213–233, Geom. Topol. Publ., Coventry, 2004) the Brown invariant was expressed through a self-linking number of the self-intersection. We extend the definition of this self-linking number to the case of parametrized generic real algebraic surfaces.     

On the Security of the Digital Signature Algorithm

We present a key-recovery attack against the Digital Signature Algorithm (DSA). Our method is based on the work of Coppersmith [7], and is similar in nature to the attacks of Boneh et al. [5,9] which use lattice reduction techniques to determine upper bounds on the size of an RSA decryption exponent under which it will be revealed by the attack. This work similarly determines provable upper bounds on the sizes of the two key parameters in the DSA for which the system can be broken. Specifically if about half of the total number of bits in the secret and ephemeral keys, assuming contiguous unknown bits in each key, are known, the system can be shown to be insecure. The same technique shows that if about half of the total number of bits in two ephemeral keys are known, again assumed contiguous unknown bits in each key, but with no knowledge of the secret key, the system can be shown to be insecure.     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

On linear forbidden submatrices

In this paper we study the extremal problem of finding how many 1 entries an n by n 0-1 matrix can have if it does not contain certain forbidden patterns as submatrices. We call the number of 1 entries of a 0-1 matrix its weight. The extremal function of a pattern is the maximum weight of an n by n 0-1 matrix that does not contain this pattern as a submatrix. We call a pattern (a 0-1 matrix) linear if its extremal function is O(n). Our main results are modest steps towards the elusive goal of characterizing linear patterns. We find novel ways to generate new linear patterns from known ones and use this to prove the linearity of some patterns. We also find the first minimal non-linear pattern of weight above 4. We also propose an infinite sequence of patterns that we conjecture to be minimal non-linear but have Ω(nlogn) as their extremal function. We prove a weaker statement only, namely that there are infinitely many minimal not quasi-linear patterns among the submatrices of these matrices. For the definition of these terms see below.     

Secure sets and their expansion in cubic graphs

Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.