[dragontamer]

1. You want an invertible operation. Invertible operations do _NOT_ lose information, and therefore have the maximum amount of entropy per step.

2. You want the invertible operation to pass a statistical test called "differential cryptography analysis". Over multiple rounds, it must be difficult / impossible to "predict" how 1-bit of difference changes the state. (ie: 1-bit of difference should lead to 50.0000000% change in every output bit. If its 50.1% or 49.9% change of bits, you fail because someone running cryptoanalysis will pick that up).

----------

#1 is somewhat easy. It turns out that Data XOR (Rotate-left Data) XOR (Rotate-right Data) is all you need to make an invertible operation. 5-operations, no more (any more is redundant and therefore unnecessary use of compute power), no less (any less is not invertible and therefore loses information / entropy each step).

#2 is complicated: you gotta understand differential cryptoanalysis and run a bunch of tests.

-----------

The discovery that (Data) XOR (Rotate-left Data) XOR (Rotate-right Data) was invertible became extremely popular in the 2010s through 2020s, and has become the cornerstone of XOR / Rotate / Add ciphers (aka: chacha), pseudorandom generators, and hash functions.

I don't know quite when it was originally discovered, but Jenkins was blogging about the importance of invertibility and playing with invertible xor/rotate stuff in (non-crypto) hash functions way back in the 90s.

I know Knuth's "Art of Computer Programming" book 2, Seminumerical Algorithms, discusses the importance of invertibility in random number generators, which is closely related to hashing / cryptographic procedures. So this "understanding" has been around for decades, but has only "become popular" in the SHA256 / Blake3 / pcg-random era.

------

In the 90s, ciphers were mostly using SBoxes for this step ("confusion", to grossly change a value to another value without losing information). But today, modern CPUs are much faster at add/xor/bitshift operations than reading/writing to memory. So SBoxes are no longer a high-speed methodology / primitive for these kinds of operations.

It makes more sense to change our algorithms to use a new "invertible confusion operation" (aka: what SBoxes did before, and what ((Data) XOR (Rotate-left Data) XOR (Rotate-right Data)) does today).

--------

EDIT: Remember: the modern crypto-primitive is just a combination of "confusion" principles and "diffusion" principles.

1. Confusion "lossless transforms" numbers into other numbers. (A "set permutation" of sorts)

2. Diffusion "moves" bits from one number into other numbers.

Iterating over confusion + diffusion many times (IIRC, SHA256 is 64 rounds) is all you need to make a cryptographic cipher. If you "just" need a pseudo-random number generator or hash function, maybe 5 to 10 rounds is all you need.

[y42]

Not sure if I understand you right, but sha256 is not invertible, there are a couple of steps where you actually just 'cut off' information that is lost afterwards.

[dragontamer]

The primitive (data) XOR (rotate-data) XOR (rotate-data) is invertible, which means there's no "bit funnel" (Bob Jenkin's term).

You want your "primitives" to be invertible, so that your one source of "non-invertible" operations is controlled very carefully.

Hash functions are non-invertible. But all operations on the "internal state" should be invertible (!!!!) to maximize the entropy per round.

--------

All good hash-functions have invertable operations (aka: a bijective (1-to-1 and onto) operation) over its state to "distribute" the bits around in some manner. You then perform a non-reversable XOR over the input message data (this is the one and only non-reversible step), maybe after operating over the input data somehow.

Whenever you're "mixing" bits around in a cipher or hash, you need every step to be invertible to maximize your entropy. If you have 2^256 possible input states, you want to have 2^256 output states. By the pigeon-hole principle, this only happens if you have a bijective / 1-to-1 and onto invertible operation.

--------

Lets look at the opposite. Lets say we have a non-invertible function. That is, 2^256 possible inputs become only 2^128 outputs. Guess what? We've just lose 128-bits of information (!!!).

It doesn't matter how complex your operation is. If you have 256-bits of input and only 128-bits of output, you've "lost information". You _NEVER_ want to lose internal-state information.

The hash-function's internal state should be at a maximum 256-bits (with 256-bits of entropy) every step. Sure, the input might be 512-bits, 4096-bits, or 100-MBs long, but each "step" of a 256-bit hash should retain 256-bits of state to be maximally "difficult" to reverse.

That's kinda-sorta obvious if you think of it from a pigeon-hole perspective.

[tptacek]

I guess sort of intuitively (I'm not a cryptographer):

If your round function isn't invertible, then it's going to converge at some point on some fixed value, and the round function is going to stop doing anything useful.

More broadly, SHA2 is a sort of instance of a construction called Davies-Meyer, which treats each message block as the key to a bona-fide block cipher (SHACAL, in SHA's case), each encrypting the previous block. It's hopefully pretty obvious why a block cipher core needs to be invertible. :)

So I also find it kind of helpful to remember that you can take any block cipher and turn it into a hash, and then a "good" hash function is just optimizing the block cipher core around the goals of a hash function (be fast, be nonlinear, be hard to find differential trails through the whole sequence of round functions, &c).

It's a thing I don't love about illustrations like the one we're discussing, in that it sort of presents this "intelligent design" problem of, like, "how did we arrive at this incredibly complex fully functioning eyeball", when there's a whole series of smaller evolutionary steps that led to this point; it's more productive maybe to look at the bones of the whole design before diving into the details of which bits go where at each precise step.

[dragontamer]

> I guess sort of intuitively (I'm not a cryptographer):

Don't worry. I'm not one either. And I think that's why I am actually able to tell you that invertibility / 1-to-1 onto bijections is an important concept :-)

An actual cryptographer would tell you its 1-to-1 and onto and move on.

> It's a thing I don't love about illustrations like the one we're discussing, in that it sort of presents this "intelligent design" problem of, like, "how did we arrive at this incredibly complex fully functioning eyeball", when there's a whole series of smaller evolutionary steps that led to this point; it's more productive maybe to look at the bones of the whole design before diving into the details of which bits go where at each precise step.

Agreed. There's a lot of history here, and knowing all of the history helps a _LOT_.

Go back 50 years ago, and ciphers are way easier to grok. DES / Feistel ciphers are really easy for example. But then we discovered issues about them and iteratively improved.

The old "DES" / Feistel cipher principles of confusion and diffusion remain with us today, but each step has been honed for 90s-era computers (SBoxes and 32-bit numbers), and then honed again for 2010s-era computers (recognition that XOR / Rotate / Add is a faster primitive today than memory-based SBoxes).

I don't think any of the principles have changed since DES / Feistel cipher days. Its just that today's designs are better for today's computers.

------

EDIT: As far as I can tell: "confusion" can be created by (data) XOR (rotate-data) XOR (rotate-data) primitives. "diffusion" can be created by the "ADD" operator (in particular: "carries" will diffuse the bits around).

So XOR, rotate, and Add are the only primitives you need to make a modern crypto-cipher. All three primitives are outrageously fast on modern machines.

AES and other older ciphers tried to make each round relatively high quality. Modern ciphers try to make each round low-quality, and then do something like 64-rounds or 80-rounds to make up for it.

So you'll see old ciphers like AES with just 11 rounds, but modern ciphers / crypto algorithms like SHA256 use 64-rounds.

[y42]

That's right, but sha256 also utilizes eg shift operation with a fixed length for the result. Meaning: your moving information "out of the scope". Or all the additions: the result is often greater then 32bit (2 words) and therefore being reduced.

[dragontamer]

Everything in context.

The operation you're talking about is "sigma_0" and "sigma_1" I believe, which is defined as:

sigma_0(x) = Rotate7(x) XOR Rotate18(x) XOR shift3(x).

sigma_1(x) = Rotate17(x) XOR Rotate19(x) XOR shift10(x).

Where "shift3" and "shift10" are both lossy operations.

----------------

While "shift3" and "shift10" are lossy, I'm not 100% certain that "sigma_0" or "sigma_1" is lossy. But that discussion aside, both sigma_0 and sigma_1 are applied to the _message_, not the internal SHA256 state.

The _message_ needs to be compressed, so a lossy operation over the message is not only expected, but required. 4096-bits of input need to become 256-bits of output. 8192 bits of message-input needs to become 256-bits of output.

-----------

But if you look at the "intermediate hash chain" where H(i) = a + H(i-1) for 64 rounds, all operations over "a" and the internal hash-state are invertible operations (SIGMA_0 and SIGMA_1 are both invertible, being (x) XOR (rotate x) XOR (rotate x) style functions).

------

I'm not saying that the "whole" hash function needs to be invertible. I'm saying that __particular__ elements of the hash function _should_ be invertible. The design of these particular elements (in particular, SIGMA_0, which is (Rotate2(x) XOR Rotate13(x) XOR rotate22(x))) is _clearly_ and evidently invertible / 1-to-1 and onto bijection / confusion principles.

The particular constants (why "rotate2", "rotate13" and "rotate22") is chosen for other reasons: probably differential cryptoanalysis but I admit that I'm not 100% sure on that (that's my expectation though).

[manceraio]

Do you recommend any resources to learn about this?

[dragontamer]

The information in the above post is a merger of like, 20 different sources of information.

Your standard cryptographic books from any undergraduate program will tell you about the basics of confusion / diffusion, but I don't think the concept is very difficult at all.

Invertibility is hugely important but not discussed very much. It seems like crypto-experts 'obviously' know about it so they just don't talk about it? Knuth and Bob Jenkins both talked about the importance of invertibility to random number generators. EDIT: Invertibility is the basis of bijective / 1-to-1 and onto permutation functions. To be fair, I think everyone discusses the concept but maybe with different words.

Here's Jenkin's discussion on (non-crypto) hash functions, including a few paragraphs on "invertibility" (or "funnels" as they put it): http://www.burtleburtle.net/bob/hash/doobs.html

The "pcg-random" generator also has a large discussion on invertibility. Honestly, one of the best writeups on the subject, and I felt like my IQ went up severely after reading the paper end-to-end: https://www.pcg-random.org/paper.html

--------

The study of the invertibility of (data XOR (rotate-right data) XOR (rotate-left data)) is covered in many blogposts. https://marc-b-reynolds.github.io/math/2017/10/13/XorRotate....

The study of invertibility in general was covered by Lemire: https://lemire.me/blog/2016/08/09/how-many-reversible-intege...

-----

So as you can see, invertibility is "important", but rarely discussed as important. Its just assumed that everyone knows how important it is. Once you realize that invertibility / lack of funnels is important, everything else makes sense.

Galois field multiplication is useful in AES because its invertible (multiply by the GF(2^8) reciprocal). Aaaaah. I see. Why didn't my undergrad teacher just start with the importance of invertibility before talking about prime numbers and extension fields?

-----

Ah right. Once you know that these things have great properties (ie: invertible), then you can just read the SHA256 paper directly and the rest is just "obviously" confusion + diffusion principles.

-----

Linear Cryptoanalysis is the "standard" run a distribution kinda thing. Anyone who has done Chi-squared tests over random numbers kinda-gets this principle. Honestly, your standard non-crypto RNGs are roughly at this level at this point, so the study of any statistical-test for any random-number generator is good. Knuth / Art of Computer Programming Vol2 is one source of information on Chi-squared tests, but the study of statistics in general also results in Chi-squared tests and the like.

Differential Cryptoanalysis is more difficult and looks at the change-of-bits at each step of every operation. I don't quite remember how I was introduced to the concept, but differential-cryptoanalysis of many popular ciphers is a well-studied thing throughout the field.

--------

Knowledge of "what is fast" and "what is not fast" is... not really easy to come by, and seems to change as computer architectures change. I know that memory has gotten relatively slower compared to CPU-speeds in the past 30 years. I can imagine that in the 90s, an XOR-rotate-add cipher would take "relatively more" time than today, and that SBox-based / lookup table based ciphers were far more popular back then.

I'm not sure where I learned that information. Maybe software optimization manuals in general?

[rhengles]

Forgive me for replying here, I couldn't find an option to DM you. And I cannot find any implementation of this in javascript, nor anyone else able to help me.

Can you shed some light here why I'm getting these differences?

https://jsfiddle.net/7kf15dje/

Here is an example of the output I'm getting:

  //       X  A  B           X^1         X^-1 :: Difference
   471490377  6 13 =  1365552781 =  471490377 :: 0
  1528396978  9 11 = -1576695076 = 1528396978 :: -0
  1592322722  9 20 =   622346385 = 1592322722 :: -0
  1214152986  8 16 = -1748578289 = 1214152985 :: -1
  1193897367  2 16 =   907713766 = 1193897366 :: -1
   335642564  9 10 =   318891964 =  335642564 :: -0
   486208953 16 23 =   894211128 =  486208952 :: -1
   629577059 13 14 =  1383225523 =  629577058 :: -1
  1609442937  8 18 =   674046110 = 1609442937 :: -0
   234450967  6 12 =  -459008694 =  234450966 :: -1
  1840721644 19 28 =  -602984005 = 1840721644 :: -0

[rhengles]

I can't edit my post anymore but I found the solution. All I had to do was to convert the random input value (X above) to an uint32 using (X >>> 0).

[dragontamer]

You did things the hard way by trying to construct the exact inverse.

---------

I suggest the following instead:

1. Create a 16-gigabyte file consisting of f(x) from x=0x00000000 to x=0xFFFFFFFF.

2. Sort the file.

3. Determine that no repeats exist, that is, the values go from 0x00000000 to 0xFFFFFFFF.

--------

Once you have determined that all 32-bit inputs result in all 32-bit outputs, you've determined that the function is invertible. 4-bytes x 2^32 possible inputs == only 16GB these days, small enough to be handled by any old computer... possibly entirely in RAM.

But if you don't got enough RAM for that, an SSD or even Hard Drive would be fast enough for the above procedure. It may take a few minutes but its not that hard.

You see, the goal is to "prove you have an invertible function". At no point do you have to accomplish the difficult task of actually finding the inverse.

-------

Well, I guess if you're "just following the blogpost" about the inverse, maybe that's easier. But from the perspective of "I don't know the inverse yet", its really difficult to figure it out. So you should think about the simpler brute-force methodologies that a modern computer can do in just a few minutes.