On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

On gap functions for nonsmooth multiobjective optimization problems

A set-valued gap function, \(\phi \), existing in the literature for smooth and nonsmooth multiobjective optimization problems is dealt with. It is known that \(0\in \phi (x^*)\) is a sufficient condition for efficiency of a feasible solution \(x^*\), while the converse does not hold. In the current work, the converse of this assertion is proved for properly efficient solutions. Afterwards, to avoid the complexities of set-valued maps some new single-valued gap functions, for nonsmooth multiobjective optimization problems with locally Lipschitz data are introduced. Important properties of the new gap functions are established.     

Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem

The new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. The purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all ElGamal-type schemes have variants giving message recovery. For each of the six basic ElGamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. Moreover, the six basic signature schemes have different properties regarding security and implementation. It turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the DSA requires computing of inverses in both generation and verification of signatures. In general, message recovery variants can be given for ElGamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of GF(2n) or elliptic curve over a finite field.The present paper also shows how to integrate the DLP-based message recovery schemes with secret session key establishment and ElGamal encryption. In particular, it is shown that with DLP-based schemes the same functionality as with RSA can be obtained. However, the schemes are not as elegant as RSA in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.     

Robust decentralized diagnosability of networked discrete event systems against DoS and deception attacks

Denial-of-Service (DoS) are attacks conducted by malicious agents that consists in disrupting, temporally or indefinitely, the services provided by a communication network. When a malicious agent gets access to some network node, it may also perform deception attacks by inserting valid packets with fake information into vulnerable channels. We address, in this paper, DoS and deception attacks (DoS-D attack) that flood some communication channels with fake packets causing delays, loss of observations and insertion of fake observations, and their implications in decentralized fault diagnosability of networked discrete event systems (NDES). To this end, we propose an automaton model for NDES subject to DoS-D attacks that represents the adverse effects of DoS-D attacks on the observations of local diagnosers. We introduce a new codiagnosability definition called DoS-D-robust codiagnosability, and present a necessary and sufficient condition for a language to be DoS-D-robustly codiagnosable. We also propose a verification algorithm for regular languages to check DoS-D-robust codiagnosability.     

A combinatorial-probabilistic analysis of bitcoin attacks*

In 2008, Satoshi Nakamoto famously invented bitcoin, and in his (or her, or their, or its) white paper sketched an approximate formula for the probability of a successful double spending attack by a dishonest party. This was corrected by Meni Rosenfeld, who, under more realistic assumptions, gave the exact probability (missing a foundational proof); and another formula (along with foundational proof), in terms of the Incomplete Beta function, was given later by Cyril Grunspan and Ricardo Pérez-Marco, that enabled them to derive an asymptotic formula for that quantity. Using Wilf-Zeilberger algorithmic proof theory, we continue in this vein and present a recurrence equation for the above-mentioned probability of success, that enables a very fast compilation of these probabilities. We next use this recurrence to derive (in algorithmic fashion) higher-order asymptotic formulas, extending the formula of Grunspan and Pérez-Marco who did the leading term. We then study the statistical properties (expectation, variance, etc.) of the duration of a successful attack.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

Truncated differential based known-key attacks on round-reduced SIMON

At Crypto 2015, Blondeau, Peyrin and Wang proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight block cipher with an SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction. We notice that there are good linear hulls for bit-oriented block cipher SIMON corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced SIMON block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced SIMON. We also involve some key guessing technique and further extend the basic attacks to more rounds. Our known-key attacks can reach as many as 29/32/38/48/63-rounds of SIMON32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher SIMON.     

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.     

Md2 is not Secure Without the Checksum Byte

In 1989, Ron Rivest introduced the MD2 Message Digest Algorithm which takes as input a message of arbitrary length and produces as output a 128-bit message digest, by appending some redundancy to the message and then iteratively applying a 32 bytes to 16 bytes compression function. MD2 Message Digest Algorithm is one of the most frequently used hashing function with MD4, MD5, SHA, SHA-1. Some attacks against MD4 and MD5 have been presented by Dobbertin. Up to now, no attack against MD2 has been presented.This function has been updated in 1993 in the RFC 1423 document. It was conjectured that the number of operations needed to get two messages having the same message digest is on the order of 2⁶⁴ (using the birthday paradox), and that the complexity of inverting the hash function is on the order of 2¹²⁸ operations. No attack against this function has been published so far. In this paper, we propose a low complexity method to find collisions for the compression function of MD2. The easiness to find these collisions could imply that the first conjecture is false if these collisions can be used to make global collisions for MD2.     

Zero-correlation attacks: statistical models independent of the number of approximations

Multiple and multidimensional zero-correlation linear cryptanalysis have been two of the most powerful cryptanalytic techniques for block ciphers, and it has been shown that the differentiating factor of these two statistical models is whether distinct plaintexts are assumed or not. Nevertheless, questions remain regarding how these analyses can be universalized without any limitations and can be used to accurately estimate the data complexity and the success probability. More concretely, the current models for multiple zero-correlation (MPZC) and multidimensional zero-correlation (MDZC) cryptanalysis are not valid in the setting with a limited number of approximations and the accuracy of the estimation for data complexity can not be guaranteed. Besides, in a lot of cases, using too many approximations may cause an exhaustive search when we want to launch key-recovery attacks. In order to generalize the original models using the normal approximation of the \(\chi ^2\)-distribution, we provide a more accurate approach to estimate the data complexity and the success probability for MPZC and MDZC cryptanalysis without such approximation. Since these new models directly rely on the \(\chi ^{2}\)-distribution, we call them the \(\chi ^{2}\) MPZC and MDZC models. An interesting thing is that the chi-square-multiple zero-correlation (\(\chi ^{2}\)-MPZC) model still works even though we only have a single zero-correlation linear approximation. This fact puts an end to the situation that the basic zero-correlation linear cryptanalysis requires the full codebook under the known-plaintext attack setting. As an illustration, we apply the \(\chi ^{2}\)-MPZC model to analyze TEA and XTEA. These new attacks cover more rounds than the previous MPZC attacks. Moreover, we reconsider the multidimensional zero-correlation (MDZC) attack on 14-round CLEFIA-192 by utilizing less zero-correlation linear approximations. In addition, some other ciphers which already have MDZC analytical results are reevaluated and the data complexities under the new model are all less than or equal to those under the original model. Some experiments are conducted in order to verify the validity of the new models, and the experimental results convince us that the new models provide more precise estimates of the data complexity and the success probability.     

Optimising Gröbner Bases on Bivium

Bivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of 2^39.12 s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.     

Algebraic attacks on a class of stream ciphers with unknown output function

Attacks on linear feedback shift register (LFSR) based cryptosystems typically assume that all the system details except the initial state of the LFSR are known. We address the problem assuming that the nonlinear output function is also unknown and frame the problem as one of a multivariate interpolation. The solution to this problem yields a system that produces an output identical to that of the original system with some other initial state. The attack needs to observe M bits of data and has complexity O(M ^ω) where ${M = \sum_{i=0}^{d} C(n, i)}$ is the number of monomials of degree at most d in n variables, n being the state size and d the degree of the output function. When the output function has annihilators of degree e < d then with O(D) bits of data one can reconstruct parts of the keystream where ${D = \sum_{i=0}^{e} C(n, i)}$ .     

Vibrational mixing of a fluid between two quasiconcentric cylinders

We consider the possibility of intense mixing of a viscous fluid in the gap between two quasiconcentric cylinders, with one of the cylinders performing high-frequency vibrations about its axis. The motion of the fluid is described by Navier-Stokes equations for the axisymmetric case. The stream function is represented by a generalized Fourier series. The small parameter is the ratio of the vibration amplitude to the radius of the external cylinder. Calculations carried out in the zeroth approximation produced the pattern of stream lines for various Reynolds numbers, vibration amplitudes, and ratios of external and internal radii. The mixing intensity was found to increase substantially with the reduction of the gap between the cylinders, whereas variation of the ratio of the vibration amplitude to the Reynolds number did not produce marked qualitative changes. The fluid flow in this system generates a contraction semigroup, which makes it possible to derive the ergodicity criterion for the stream function.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 59, pp. 35–39, 1986.     

Stochastic non-convex envelopment of data: Applying isotonic regression to frontier estimation

Isotonic nonparametric least squares (INLS) is a regression method for estimating a monotonic function by fitting a step function to data. In the literature of frontier estimation, the free disposal hull (FDH) method is similarly based on the minimal assumption of monotonicity. In this paper, we link these two separately developed nonparametric methods by showing that FDH is a sign-constrained variant of INLS. We also discuss the connections to related methods such as data envelopment analysis (DEA) and convex nonparametric least squares (CNLS). Further, we examine alternative ways of applying isotonic regression to frontier estimation, analogous to corrected and modified ordinary least squares (COLS/MOLS) methods known in the parametric stream of frontier literature. We find that INLS is a useful extension to the toolbox of frontier estimation both in the deterministic and stochastic settings. In the absence of noise, the corrected INLS (CINLS) has a higher discriminating power than FDH. In the case of noisy data, we propose to apply the method of non-convex stochastic envelopment of data (non-convex StoNED), which disentangles inefficiency from noise based on the skewness of the INLS residuals. The proposed methods are illustrated by means of simulated examples.     

A system for priority routing and capacity assignment in packet switched networks

A model and its associated solution procedure for the problem of concurrent flow and capacity assignment in a packet switched network are presented. The distinguishing feature of the model lies in the fact that a user defined priority level is associated with each message in the network. Different service requirements and message characteristics are associated with each message class. An algorithm that generates good feasible solutions to the model, together with tight lower bounds on the value of the objective function, is developed. Results of numerical experiments using several network topologies are reported.     

Protection of flows under targeted attacks

We present a new robust optimization model for the problem of maximizing the amount of flow surviving the attack of an interdictor. Given some path flow, our model allows the interdictor to specify the amount of flow removed from each path individually. In contrast to previous models, for which no efficient algorithms are known, the most important basic variants of our model can be solved in poly-time. We also consider extensions where there is a budget to set the interdiction costs.     

Improved distinguishers for HC-128

HC-128 is an eSTREAM final portfolio stream cipher. Several authors have investigated its security and, in particular, distinguishing attacks have been considered. Still, no one has been able to provide a distinguisher stronger than the one presented by Wu in the original HC-128 paper. In this paper we first argue that the keystream requirement in Wu’s original attack is underestimated by a factor of almost 2⁸. Our revised analysis shows that the keystream complexity of Wu’s original attack is 2^160.471 32-bit keystream blocks. We then go on to investigate two new types of distinguishers on HC-128. One of them, a distinguisher counting the number of zeros in created blocks of bits, gives a biased distribution that requires 2^143.537 such constructed block samples (2^152.537 32-bit keystream blocks). For fairness, the same metric is used to compare our attack to Wu’s, and our improvement is significant compared to Wu’s original result. Furthermore, the vector-based methodology used is general and can be applied to any cryptographic primitive that reveals a suitable probability distribution.     

Minimal antiderivatives and monotonicity

We consider settings in convex analysis which give rise to families of convex functions that contain their lower envelope. Given certain partial data regarding a subdifferential, we consider the family of all convex antiderivatives that comply with the given data. We prove that this family is not empty and, in particular, contains a minimal antiderivative under a fairly general assumption on the given data. It turns out that the representation of monotone operators by convex functions fits naturally in these settings. Duality properties of representing functions are also captured by these settings, and the gap between the Fitzpatrick function and the Fitzpatrick family is filled by this broader sense of minimality of the Fitzpatrick function.     

Cover attacks for elliptic curves with cofactor two

For cryptographic applications, in order to avoid a reduction of the discrete logarithm problem via the Chinese remainder theorem, one usually considers elliptic curves over finite fields whose order is a prime times a small so-called cofactor c. It is, however, possible to attack specific curves with this property via dedicated attacks. Particularly, if an elliptic curve \(E/\mathbb {F}_{q^n}\) is given, one might try to use the idea of cover attacks to reduce the problem to the corresponding problem in the Jacobian of a curve of genus \(g \ge n\) over \(\mathbb {F}_q\). In the given situation, the only attack so far which follows this idea is the GHS attack, this attack requires that the cofactor c is divisible by 4 as otherwise the genus of the resulting curve is too large. We present an algorithm for finding genus 3 hyperelliptic covers for the case \(c=2\). The construction works in odd characteristic and the resulting cover map has degree 3. As an application, two explicit examples of elliptic curves whose order are respectively 2 times a 149-bit prime and 2 times a 256-bit prime vulnerable to the attack are given.     

Complexities of four problems on two-agent scheduling

In the two-agent scheduling with the global objective function to be minimized being the number of tardy jobs and the specified agent’s objective function to be minimized being makespan or maximum lateness, the computational complexities of four problems were posed as open in the literature. We show in this paper that the four problems are binary NP-hard and two of them are solvable in pseudo-polynomial time.