If the last $448$ bits of a SHA-1 block input are known and only the first $64$ bits are unknown, is it possible to do a preimage attack using SAT solvers or something else? Or do I have to brute force all $2^{64}$ possibilities? Is this a kind of reduced SHA-1?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ If there's a significantly better attack than trying an expected $2^{63}$ possibilities among the $2^{64}$, then it's worth publication, and I missed it. $\endgroup$– fgrieu ♦Feb 14, 2019 at 16:05
-
1$\begingroup$ You can start to solve bt SAT with small cases, 4,8,16, and so on. Also, the 64-bit search may not be far away. If you have the money you can achieve it in a very short time. $\endgroup$– kelalakaFeb 14, 2019 at 16:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
If you know the last 448 bits, we can assume that this part actually the padding part with length at the end, then you will have 64-bit unknown data for the input to pre-image attack. Since you know the output hash value you can set up a system of equations. In this case, the hash function can be considered as
$$\operatorname{F}:\{0,1\}^{64}\times\{0,1\}^{448} \to \{0,1\}^{160}$$
Now, for every output bit, set up an equation by algebraic evaluation of SHA-1. You will have 160 equations and 64 unknowns.
This type of system is called over-defined when there are more equations than unknowns. However, keep in mind that the system may be inconsistent that means there is a collision there an that has an expected negligible probability.
According to Bard, Courtois, and Jefferson paper;
if the system of equations is sparse or over-defined, then the SAT-solver technique works faster than brute-force exhaustive search. If the system is both sparse and over-defined, then the systems can be solved quite effectively.
The only problem that we can't see, immediately, the degree of the equations. If they are low degree then the SAT solvers, as Mini-SAT, can be faster than brute-force, according to the result of the paper.
answered Feb 14, 2019 at 17:18
-
1$\begingroup$ I'd be surprised if the quoted statement applies in the context of the question. That statement is made for a random multivariate simultaneous system of quadratic equations over $GF(2)$, and the SHA-1 round function is far from being defined at random (only some of its constants are). Again if that worked, that would make the headlines. $\endgroup$– fgrieu ♦Feb 14, 2019 at 17:40
-
$\begingroup$ @fgrieu I mentioned in the last paragraph about the degrees, not clear?. The point of this article is if this is the case then Algebraic attack can be better then brute force. And, I know from the first hand that applying one result to another in algebraic attacks is not easy. $\endgroup$– kelalakaFeb 14, 2019 at 17:47
-
2$\begingroup$ The last paragraph is clear, but the condition deemed favorable to SAT being faster than brute force (low degree) does not apply in the question's context, because the 80 rounds of SHA-1 cause deep non-linear diffusion and thus high degree. SAT solvers tend to fail miserably at breaking good symmetric crypto faster than brute force, often even for reduced rounds. Not coincidentally, the quoted paper is about using SAT solvers to break asymmetric crypto. $\endgroup$– fgrieu ♦Feb 15, 2019 at 7:05