# Tag Info

8

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 ...

6

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

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, ...

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 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 ... 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 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

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

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} ...

2

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 ...

2

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 ...

1

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 ...

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