Score:3

Crypto

Is SAT the mathematical problem behind SHA-2 and SHA-3?

Timur Timak

11/10/23, 8:25 AM

When I'm convincing non-believers that crypto is secure, I have a hard time with hash functions and the associated block ciphers.

It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step.

It is easy to show how Vernam cipher is secure: I tell them an Alice and Bob story with a flipping coin as an RNG.

But when it comes to the hashing, I am not even sure I know the underlying mathematical problem. It would be great to have a small intuitive example of that problem for illustration.

If it is indeed the boolean satisfiablity problem then I can at least mention that it is the hardest in the NP class, and if we solve it then P=NP, because many have heard about that.

I can use the argument that greed is innate to human nature and if there is at least one person who knows how to reverse hashes, they will incessantly mine crypto out of thin air and the exchange rate will eventually drop. But it is somewhat shaky I think.

260

1 + 3

sat

Maeher

11/10/23, 9:20 AM

"It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step." That's [lie-to-children](https://en.wikipedia.org/wiki/Lie-to-children) territory. The hardness of factoring is *not* known to imply security of RSA.

fgrieu

11/10/23, 10:48 AM

We can make a relatively convincing lie-to-children about how secure hashes are possible. For even word width $n$, for any $k\in[1,n/2)$, function$$\begin{align}f_k:\{0,1\}^n&→\{0,1\}^n\\u\mathbin\|v\;&↦(((u≪k)⊕(u≫(n-k)))+v)\mathbin\|u\end{align}$$(where $u$ and $v$ are $n/2$-bit bitstrings assimilated to integers modulo $2^{n/2}$) is a bijection. Now fix enough public haphazard $k_0,k_1…k_ℓ$. The function $f_{k_0}∘f_{k_1}∘…∘f_{k_ℓ}$ is an haphazard bijection $g$. Now form$$\begin{align}h:\{0,1\}^n&→\{0,1\}^n\\w\;&↦w⊕g(w)\end{align}$$and we have a "clearly" hard to invert haphazard function.

user253751

2/3/24, 8:39 PM

SAT is a mathematical problem behind **every algorithm in NP**. Both the easy ones and the hard ones.

Score:4

Crypto

Ievgeni

11/10/23, 9:07 AM

Cryptographic problems should be hard in average. NP-Complete problems such that SAT are supposed to be hard in the worst case. But, for many practical distributions, SAT is not hard in average.

If it is indeed the boolean satisfiability problem then I can at least mention that it is the hardest in the NP class

This sentence is wrong, if we consider a specific distribution on inputs.

To conclude briefly the answer is no. But, if P=NP, then no efficient cryptographic constructions are possible at all (neither symmetric nor asymmetric).

Here efficient means with asymptotic exponential gap between the standard operations (encryption, decryption, signature, etc), and the cryptanalysis.

You can read about the Impagliazzo's Five Worlds, if you want more details about this comparison.

+ 8

Maeher

11/10/23, 9:15 AM

They are *not* known to be hard in the worst case. They are *assumed* to be hard in the worst case and mostly *known* to be easy in the average case.

Polytropos

11/10/23, 9:33 AM

> But, if P=NP, then no cryptographic constructions are possible at all (neither symmetric nor asymmetric). I think that is oversimplified. Even if P=NP, fine-grained separations may be a thing (i.e. it might be possible to get constructions where the legitimate receiver has an advantage over the adversary that is merely polynomial (in some problem size parameter that we handwave in by embedding whatever construction we are looking at into a family of similar constructions that depend on a variable-size security parameter), but nonetheless sufficient for their security needs.

Titanlord

11/10/23, 9:39 AM

I see why the implications from P=NP hold for computational security but is this also true for perfect and quantum security?

Ievgeni

11/10/23, 10:09 AM

@Polytropos If I write efficient cryptographic constructions, does it seemed to you more correct?

Ievgeni

11/10/23, 10:23 AM

@Titanlord About quantum security, I think it is not related. About perfect security, it's still inefficient.

Polytropos

11/10/23, 11:06 AM

@Ievgeni: I am not sure about that either. Let's say P=NP with horrible constants. Who is to say that AES-128 is in this case not perfectly fine?

Maeher

11/10/23, 1:00 PM

The P vs NP question is only relevant in an asymptotic setting. Asymptotically AES is broken anyway. Concrete security is a completely different question.

user253751

2/3/24, 8:42 PM

@Maeher in a way. The relevance is that we make algorithms that take O(n) to decrypt and O(2^n) time to break, for example, then we just set n as high as we like. AES may technically be O(1) (as is any block cipher with fixed-size blocks, trivially) but you can surely make a family of "generalized AES" algorithms parameterized by the security level n.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is SAT the mathematical problem behind SHA-2 and SHA-3?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.