Hacker News Reader

Comment by barkingcat | Hacker News Reader

It's an algorithm, so you're probably looking for a higher level block diagram or something like a pseudocode explainer?

https://www.maximintegrated.com/en/design/technical-document... has a block diagram

https://www.maximintegrated.com/content/dam/images/design/te...

many of the decisions made in cryptographic algorithms (ie why this constant? why this hardcoded value?) are made as a trade off for security concerns, but also for memory size, performance during calculations, and feasibility of hardware implementation.

A good cryptographic algorithm is a balanced trade-off between all those factors (and more, for example, resistance to cryptanalysis attack would be something desirable as well)

It's not that useful to ask "why" when it comes to cryptographic primitives since sometimes the answer is "because this constant works well and gives us the performance characteristics we were looking for"

View on HN

In particular, the constants are very critical to the algorithm's security. If the constants are maliciously chosen, the algorithm could be "backdoored" with an exploitable structure. For example, if you modify just four 32-bit constants in SHA-1, without touching any other operations, it becomes nearly trivial to obtain collisions (current SHA-1 collisions have required enormous amounts of compute to achieve): https://malicioussha1.github.io/

The constants for SHA-256 are chosen to be simple mathematical constants, reducing the number of "degrees of freedom" for an attacker to manipulate the standard. At the same time, the constants need to be "random" enough to avoid producing exploitable structure. It's a careful balancing act! Roots of primes and functions or digits of transcendental numbers (e, pi, etc) make good random-ish numbers which don't provide much room for manipulation.

> Roots of primes and functions or digits of transcendental numbers (e, pi, etc) make good random-ish numbers which don't provide much room for manipulation.

Those are termed "nothing-up-my-sleeve numbers":

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

There's a big difference between symmetric and public key cryptography when it comes to this sort of explainability.

Public key cryptography like RSA, Elliptic Curves and Lattices have elegant mathematical theories behind them. Learning those will teach you much about why things are the way they are and how the security boils down to well known hard problems.

Symmetric key cryptography like SHA2, SHA3 and AES don't have nearly as much theory behind them. It's a bit of a dark art where functions are designed to thwart known attacks. There is no foundation like a proof that shows breaking SHA2 is equivalent to prime factorization or anything like that.

This doesn't necessarily have to be the case, there is research in 'provable secure hash functions', but these tend to perform worse, and we value performance a lot in symmetric crypto.

And yet...it's because of that theory that public key crypto is known to be more vulnerable to quantum computing attacks. Quantum computers can't break modern symmetric crypto.

http://www.pqcrypto.org/www.springer.com/cda/content/documen...

Indeed, understand-ability is a double-edged sword in cryptography. In general it's best to follow Kerckhoffs's principle and make sure you understand why it works, or risk that your adversary learns more than you do.

> Quantum computers can't break modern symmetric crypto.

Much like we don't have proofs that it is classically secure we also don't have proofs it is secure in a quantum setting. But absence of proof is not proof of absence. In fact we know that Grover's algorithm halves the strength of any hash function. In general you should assume that symmetric cryptography is easier to break on a quantum computer than on a classical one because they are strictly more powerful.

In case of RSA and Elliptic Curves, we known there are theoretical quantum algorithms that undermine the security. But for Lattice cryptography there are actually proofs that they remain secure in a quantum setting.

> It's an algorithm, so you're probably looking for a higher level block diagram or something like a pseudocode explainer?

Not so much. What I'd really like is a differential design analysis, i.e. "if it didn't do [this step], then the output distribution would look like [graph] instead of [graph], or it would be vulnerable to [attack]" or "if, instead of doing [step] here, it did [other step], then we would have what is known as the [some other algorithm]."

Echoing this request -- knowing this stuff also helps make sense of seemingly bizarre parts of the system.

It is useful to ask why. The constants are often for confusion and diffusion properties: https://en.m.wikipedia.org/wiki/Confusion_and_diffusion

No, I guess the question is:

Why s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)

instead I dunno, rightrotate 5 xor rr 21 xor rr 9

Or any of the other steps that have apparently "magic numbers" or "magical steps"

the replies from nneonneo and remcob shed a bit of light.

magic numbers and magic steps are part of the algorithm. It's not a result of a "planned" proof but more about choosing the right constants and right operations to resist attacks and decasteve added, to be obvious by using numbers that are generally known to be calculable (instead of obscure random numbers, you pick random numbers that anyone knows - like 1st 10 digits of pi, etc)

There are many different hash algorithms where they do indeed alter some of the rotations and the constants. and from time to time they are found to be vulnerable to collisions. For example, SHA1 had weaknesses, and I highly suspect the "apparantly magic" steps for SHA2, which you see here, are to "fix" the weaknesses of SHA1

I think it's useful to investigate how SHA1 works/breaks, and how the steps in SHA2 fixes them - that's how I would start in learning how these steps work. Going straight to SHA2 would be a bit harder because SHA2 specifically has steps to fix SHA1 weaknesses, and if you didn't know what those weaknesses were, it would seem like magic.

Reply on news.ycombinator.com