# Tag Info

9

First, from a direct witness of the events (i.e. myself): Serpent was indeed felt as "too slow" when compared with Rijndael, by a factor of 2 to 3. The performance of Rijndael was not the best there was on a PC (RC6 was faster) but it wasn't abysmal on any platform, especially 8-bit smartcard (contrary to, say, RC6). Serpent performance was consistently ...

9

This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved. Case 1, Zero Increment In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed $s_1$, multiplier $a$ and $b$ bits of state and $r$ bits returned. The modulus $M = 2^b$, and the ...

7

Walksat is an incomplete solver. This means that it tries to find a solution for a number of iterations. If it does find a solution it answers with the solution, otherwise it answers "don't know". Walksat uses a form of random walk to search for solutions with heuristics to guide its step. Minisat on the other hand, given enough computational resources, ...

7

This is a work-in-progress, mostly trying to address Case 3 in the question, since the problem of Case 2 is dealt with in another answer, and has been thoroughly researched: Jacques Stern: Secret linear congruential generators are not cryptographically secure, in proceedings of the 28th Annual Symposium on the Foundations of Computer Science, 1987 (try a ...

7

SAT solvers don't have a single approach -- not every approach works equally well for every problem. A SAT solver that performs well on a given problem will not necessarily work well in general. Typically SAT solvers employ a whole bag of tricks -- deciding what heuristic to employ is one of the big differences between solvers. Different heuristics work ...

5

Theoretically, the equations could be derived from the representation of the cipher in a hardware description language like VHDL or Verilog; you implement the cipher as if you want to make a FPGA/ASIC which runs it, but you stop at the symbolic representation of the logic gates (the "netlist"). However, I am not aware of any existing conversion tool which ...

5

You got three equations with two unknowns ($k$ and $x$). You only need two signatures to solve the private key $x$: $s_1k \equiv h_1 + xr_1 \pmod q$ $s_2k + s_2 \equiv h_2 + xr_2 \pmod q$ This might be solved using Gaussian elimination. Step 1: $s_1k/r_1 \equiv h_1/r_1 + x \pmod q$ - Divide 0.1 by $r_1$ $s_2k + s_2 - s_1kr_2/r_1 \equiv h_2 - ... 4 Putting some of my comments into writing. This is less than an answer but too much for a comment. In the comments I had claimed to apply SMT to solve case 1 - this is false, I was mistaken. I have had cases 2 and 3 running SMT (boolector, Z3, CVC4, yices) for some time without success. The closest thing to success is the identification of seeds that ... 3 tl;dr: Case 2 and 3 aren't any appreciable degree more secure than Case 1. I suspect that the issues people are having with SMT-based solutions is that these LCG problems are very under-constrained: The high-bit of the XOR is always unconstrained. The bitwise-negation of a valid XOR is always valid. Together these yield 4 guaranteed valid XORs regardless ... 3 There is of course but because of carry bits there will be data-dependent "nonlinear" terms. If I do it for 2 bits you can get the idea. It gets unwieldy but you can easily write code to do it for longer bitlengths. The list below is an XOR table expressed as integers: $$\begin{array}{c|ccc} \oplus & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & ... 3 T' method was introduced in the paper Cryptanalysis of Block Ciphers with Overdefined Systems of Equations by Nicolas Courtois and Josef Pieprzyk (see section 6.1 and Appendix E). It is a part of XSL attack on block ciphers (such as Rijndael and Serpent). During XSL attack cipher is represented as a system of multivariate quadratic polynomials and the goal ... 3 Trying to express the inverse of the non-linear Chi fonction of Keccak as a multivariate polynomial of the bits of the state will yield a degree 3 polynomial. How to derive such inverse is explained in section 6.6.2 of Joan Daemen PhD thesis as stated page 15 of http://keccak.noekeon.org/Keccak-reference-3.0.pdf 2 If the messages are unknown, there are no two messages m_i, m_j such that m_i = m_j and the messages have sufficiently high entropy (which might be shared across several messages, if the hash function is a CSOWF and the messages e.g. have low entropy unique sub strings or are made unique in some other way), and the underlying hash function is secure in a ... 2 I'm not sure exactly what you are asking. In the scenario, there are two certificates: Romeo's FOAF certificate and Juliet's SSL certificate. However Romeo's certificate is used in two different ways: once to authenticate (over mutually authenticated SSL) and once as posted on a domain he controls. I believe your question may be, if an active adversary saw ... 2 As discovered by D.W., this is in fact part of recommended IDEA implementation. IDEA uses a\cdot b \bmod (2^{16}+1), with a special case of handling 0 as 2^{16}. From the Handbook of Applied Cryptography, note 7.016: Note (implementing ab \bmod 2^{n}+1) Multiplication \bmod 2^{16}+1 may be efficiently implemented as follows, for 0 \leq a, ... 2 The rotational cryptanalysis considers applying the transformation E to both X and \overrightarrow{X}, where$$ \overrightarrow{(x_1, x_2,x_3,\ldots, x_n)} = (x_{r+1},x_{r+2},\ldots, x_n, x_1,\ldots, x_r) $$for some integer r. You know that \overrightarrow{X} \oplus \overrightarrow{Y} = \overrightarrow{X\oplus Y} always, and$$ \overrightarrow{X} ... 1 In full codebook, data complexity equals to all input of cryptosystem and in non full codebook is less than it. For example in SIMON 32/64, if data complexity=2^32, the attack is full codebook, and if DC < 2^32, the attack is non full codebook. 1 Of course, it is possible. It is possible to take a public key encryption algorithm which takes the private key and the known ciphertext into the known plaintext, convert that into a set of equations in$GF(2)\$ with the private key as unknown variables, and solve for those unknown variables. Alternatively, you can take the key generation algorithm, which ...

1

No, there is not. Your question is not well-posed. You have not specified whether you want worst-case complexity or average-case complexity, and over what class of SAT instances. The answer will depend heavily upon those details. If you want to know what is the world record for an algorithm for 3SAT, measured by its worst-case complexity over all ...

1

At first glance, it doesn't look like that interesting of a function. If we define: f(b, c) = (b*c)%k - (b*c)/k then we always have: f(b, c) == b*c (mod k+1) In other words, largely it's just an odd way of doing a modular multiplication. Of course, f(b, c) is not always (b*c) % (k+1); sometimes it is negative. At first glance, I don't see any ...

Only top voted, non community-wiki answers of a minimum length are eligible