Topic: Reversible computations (Read 390 times)

Dear "doctor" mapping is an entirely different concept compared to what hash algorithms are actually doing to compute the digest from any given message.

i agree 100% with that and so criticizing NIST that their algos don't run on reversible computers is dumb.

no of course he can't.

don't expect much more from him in that regards, he already gave it his best shot...he might even put you on ignore too if you keep pestering him (like he did me  )

You still don't understand. NIST isn't picking algorithm that run on theoretical future architectures. They pick algorithms that run on current computer architectures. Can you point to a single fully implemented (not simulated) reversible computation CPU out there? (Outside quantum computers, which is clearly not the architecture you're promoting)

You also have not explained at all what the mistakes of a non-reversible computation friendly hash function like SHA256 are, in the current year of 2023. Don't ask us to fill in the details. Explain it like we're a group of five year old kids.

The best way to be as wrong as possible is to be anti-innovative.

No. Cryptographic hash functions are not reversibility unfriendly. When computing a hash, do you always delete the data being hashed? If not, then you are performing the procedure x->(x,H(x)) rather than the procedure x->H(x). The mapping x->(x,H(x)) is invertible. I have already made an case why the properties of hash functions including collision resistance make the notion of a cryptographic hash function inherently reversibility friendly. But even though cryptographic hash functions are inherently reversibility friendly, cryptographers really should have designed these hash functions with reversibility in mind, but since they did not, it is costing us.


-I am doing the testing that I need to do with the resources that I have (I have been developing algorithms that work well for block ciphers with a very simple round function, a small message size, and a very small round key size or if the block cipher has the kind of structure by which I can apply the tests; AES has such structure, so I can evaluate AES and assign the AES specific numbers and probability distributions of real numbers that are measures of the cryptographic security). Cryptographers are not interested in developing reversible hardware friendly hash functions and reversible friendly encryption functions because they are wrong. There is no way to justify this behavior. They are just wrong.

We will eventually need to fit cryptographic hash functions, CSPRNGs, and symmetric encryption functions so that they work well with reversible hardware. The NIST has only standardized one symmetric encryption function for everyone to use. Why couldn't the NIST standardize the AES along with the RES, the reversible encryption standard. Why couldn't they standardize SHA-2 along with SHAR-2 (Secure hashing algorithm reversible)? It will take time for cryptographers to completely analyze reversible block ciphers, so it is a good idea to analyze these reversible block ciphers well before we have the reversible hardware to

The NIST has made a horrendous mistake by failing to design SHA-256 for reversibility and by failing to standardize a reversible alternative to SHA-256. Please think about this. I hope you will be able figure out why, but I know that it is not reasonable for me to have high expectations from the entities on this site, so you probably cannot figure out why a non-reversible friendly SHA-256 is a disaster. Hmm. SHA-256 was standardized in 2002, and the irreversibility of SHA-256 is disasterous. This means that NIST should have been focusing on reversibility friendly cryptography as early as 2002 and well before that because it takes time to study the effect of reversibility friendliness. The worst thing that NIST can do is wait until we actually have energy efficient reversible computers to produce reversible cryptography. In 1989, Charles Bennett published some computational complexity results from which one should conclude that the computational complexity overhead incurred from reversible computation is low enough that reversible computation and especially partially reversible computation will eventually replace irreversible computation. This means that in the 1990's,cryptographers should have began investigating reversibility friendly cryptography. And this also means that in 2002, the NIST should have standardized a reversible cryptographic hash function like SHA-256 and a fully reversible symmetric encryption function like AES so that one can encrypt without any computational overhead incurred from reversibility.

-This really depends on what one is trying to compute. If one is mining Bitcoin on a CPU, then one will gain much more energy savings and a performance upgrade by using an ASIC than if one used a reversible CPU. Right now, since the amount of storage space on a hard drive in bits is far below Avogadro's number, and because hard drives do not use up to Avogadro's number of read/writes, it does not make sense to make reversible hard drives at the moment. But since transistors are almost the size of atoms,

-It is good that you notice this. There is absolutely no reason for there to be so much hype behind quantum computation while few people care about reversible computation. Either both of these areas should be ignored at least for now or both of them should attract an equal amount of attention.

-NIST does not know much about anything since it standardized AES without also standardizing a fully reversible alternative. Unfortunately, other agencies refused to pick of the slack and standardize reversible cryptographic functions of their own. I have explained (with some details for you to fill in if you are intelligent enough to do so) why NIST should have standardized a reversibility friendly AES and a reversibility friendly SHA-256. Since energy efficient reversible computers currently do not exist, the solution to this problem is to INNOVATE so that these energy efficient reversible computers come before the world ends. This is why cryptographers should have looked into reversibility friendly encryption and hashing as early as the 1990's. Damage has already been done since the NIST has refused to standardize a reversibility friendly hash function. Now, the only reversibility friendliness of SHA-256 and AES is there by pure accident.

To make things worse, it looks like NIST has given into the entire quantum hype by having its little contest where they standardize quantum resistant public key encryption algorithms and other algorithms. And as usual, the NIST is completely ignoring reversible computation by failing to standardize a reversibility friendly encryption function and hash function that they should have standardized back in 2002.

-Joseph Van Name Ph.D. (Mathematics/not engineering/not physics)

P.S. In addition to standardizing AES,SHA-256, and a few other cryptographic functions, the NIST should also have standardized other reversibility friendly functions including
encryption where the round function is as small and simple as possible (32 bit message size, 1 bit round key size, simple round function), and encryption with 1,000,000+ bits of security so that people can authenticate long messages from God. After all, one never knows when one may need reversibility friendliness, so it is essential to have the reversibility friendly functions preemptively standardized before they become useful. And the best way to advance the field of cryptography would be to make and break cryptographic functions that satisfy these unusual properties. The way one analyzes a 32 bit message size,1 bit round key block cipher round function will be much different than the way one analyzes SHA-256, and this difference is needed for better cryptography research.

Was thinking most about SHA and other hashing algorithms, which is inherently reversibility unfriendly by the fact that hashing is intended to map a large input space into a much smaller output space.


As you previously mentioned, "There is no reason to believe that reversible friendliness will make encryption significantly less efficient or secure. But then again, this is something that needs to be tested." - Well, are you doing this testing? Most cryptographers don't care about computational reversibility since that's not the computational paradigm we currently live in, so it is up to you, as a proponent of reversible computing to do this analysis.


I can produce evidence that no reversible computers were in general use back in 1998, and there are still no reversible computers in general use in 2023, by just vaguely waving in the direction of reality. Are there any practical implementations of reversible computers today outside simulations? (Not counting quantum computers since that's a whole different programming paradigm, even though it's reversible) If no reversible computing CPUs exist today, I can safely say that they will not have any significant presence in the next decades. Note that I said decades, not centuries.

Since NIST's job was to select algorithms that were usable for computers in general use at the time and in the near future after 1998, why should they care about making algorithms faster on theoretical computation models when they could instead make them faster on computers that people actually used?


I never said quantum computing was easy. I excluded it specifically because it is much harder. And quantum computing is designed for solving very narrow problems. No one is trying to make operating systems or servers that run on a pure quantum computing layer. But your ideas of reversible computation seems to be that it can completely replace irreversible computation. Yes, the energy and transistor density limit in classical computers is a real issue, but the actual data erasure energy is still magnitudes smaller than the full energy used in an operation, so the energy savings can be more easily gained elsewhere.

You have to understand that your hate for NIST is irrational. NIST doesn't hate you, they don't even know about you, because the architecture you're pushing doesn't physically exist.

Only one of your concerns can be valid. If AES is reversibility friendly, then there is no handicap incurred from reversibility. You are making a loaded question here. Please do not ask loaded questions because that is really bad. You should not automatically assume that NIST handicaps its own algorithm RIGHT AFTER CLAIMING THAT AES MAY BE REVERSIBILITY FRIENDLY AFTER ALL. There is no reason to believe that reversible friendliness will make encryption significantly less efficient or secure. But then again, this is something that needs to be tested. And that is why NIST and the rest of the cryptography community should have made an effort to investigate reversibility friendly block ciphers. And that is why I must give NIST an F- on AES, SHA-1,SHA-2,SHA-3, etc.

But no, AES is not reversibility friendly since reversible AES will have a computational complexity theoretic overhead incurred from reversibility. For example, in the MixColumns step of encryption, the process of multiplying by the polynomial modulo x^4+1 for encryption is different than the process for multiplying by the inverse polynomial for decryption. This means that any reversible computer performing MixColumns will have such a computational complexity theoretic overhead incurred from reversibility.


-Wow. This is a heavily loaded question. Please do not ask loaded questions. If you need to make a claim, please provide evidence of your claim. You have no evidence that energy efficient reversible computation is centuries away. And asking a loaded question does not count as evidence. Sure. The Drexlerian idea of computing using molecular machines may be far off since we currently have no way of manufacturing these molecular machines. But there are other proposals for reversible computing hardware such as adiabatic reversible computing, and there has been a lot of work done on adiabatic reversible computing so far.

So you are assuming for no reason that quantum computing will be easy while reversible computing will be exceedingly difficult? Sorry. You will need to have EVIDENCE of this ridiculous claim. Oh. And just because irreversible computation was the way things are up until now is not a very good reason why things can't change. In case you have not noticed, we are no longer able to shrink transistors. And energy efficiency is becoming a problem in case you have not noticed. If you ran an integrated circuit at full blast, it would instantly fry itself. We therefore need to make integrated circuits more energy efficient and the only way to do this is to use reversible computation. You simply do not like this because of science denial.

-Joseph Van Name Ph.D. (Mathematics but not engineering)

Why is AES not reversibility friendly? How would a reversible hash function work in practice, when the point of a hash often is to reduce a large amount of data to a small amount of data, implicitly requiring throwing away most bits?

Why would NIST handicap their own algorithms to accomodate hardware that didn't exist at the time, and still does not exist and will not exist for at least several decades?

I think the problem is that you are so deep in the field that you lose sight of the big picture. Reversible computation is interesting and worth studying, but the rest of us live in the real world where irreversible computation has dominated now for almost a century, and we've become darn good at wringing more performance out of that kind of computation. Every computer chip out there, every operating system, every program is designed from the paradigm of irreversible computation. In contrast, reversible computers are almost entirely theoretical if you exclude quantum computing.

Cryptographic hash functions are a good example of partial reversibility instead of complete reversibility.

1. There is a reason why the ARX operations used to built cryptographic hash functions are invertible in the sense that (x,y)->(x,x+y mod n),(x,y)->(x,x XOR y), and rotation are invertible. If one deletes information during the process of hashing, then one is more likely to end up with a collision or other maladies for the hash function.

2. Symmetric encryption functions (which are invertible; decryption is the inverse of encryption) can be used to build cryptographic hash functions in several different ways.

Set H_0=IV to be an initialization vector. Let H_n=f(x_n,H_{n-1}). Then the hash of x_1,...,x_n will be the final value H_n. Suppose that E_k(x) is the ciphertext of the plaintext x with key k.

a. Matyas-Meyer-Oseas hash: f(x_n,H_{n-1})=E_{g(H_{i-1})}(x_i) XOR x_i

b. Davies-Meyer hash: f(x_n,H_{n-1})=E_{x_i}(H_{i-1}) XOR H_{i-1}

c. Miyaguchi-Preneel hash: f(x_n,H_{n-1})=E_{g(H_{i-1})}(x_i) XOR x_i XOR H_{i-1}

SHA-256 uses the Davies–Meyer construction.

3. The failure to use reversible components in a cryptographic hash function is a really good way to construct a horribly insecure amateurish cryptographic hash function. For example, the hash function CURL for the cryptocurrency IOTA did not use enough invertibility, and that hash function was easily broken.

-Joseph Van Name Ph.D.

P.S. I am required to continue to call out NIST (and the NSA) for standardizing AES,SHA-256 and other cryptographic functions for not designing those function to run on reversible hardware. NIST or some other agency should have standardized a reversible hardware friendly cryptographic hash function, encryption function, and other reversible friendly functions. Or they should have simply made AES and SHA-256 reversibility friendly. There is no reason why they should not include hardware reversibility friendliness as a requirement for AES.

The primary reason that hash functions are irreversible is because in order to calculate words in each chunks, there are right-shift operations involved in addition to XORs and rotations. And also the fact that we are literally condensing words into smaller bits using addition. You can see it here interactively: https://sha256algorithm.com/

Right-shifting discards bits, so even if you have not only the digest but also captured all the working variables in the last step, this would still prevent you from reversing the hash.

I mean, it doesn't render it completely useless, but in our simple example where I can produce collisions by solving x + y = 10, it's useless in the sense that even a human can do it without work. SHA1 isn't useless as it isn't trivial to find collisions.

But, there is nothing to be reversed. An equation with two unknowns is an equation which waits for us to find a solution. It hasn't operated anything to reverse.

True. SHA-1 has known collisions, and we still have hardened SHA-1, or even original SHA-1, used in places, where only preimage resistance is required. Also, for the same reason, we can still see MD5 in some places, because even if you can generate MD5 collisions in seconds on your CPU, then still, nobody knows, how to create a preimage in reasonable time.

The equation has finite solutions since we are working in a finite group (eg. 0 to UInt32 max) and the values you posted (x=5 and y=5) is a collision not the solution to the problem which was "reversing" the operation. Also finding a collision would render the hash function weak (not useless, or rather useless for specific use cases not everything).

2 and 8

3 and 7

4 and 6

...

Nobody defines the origin but math. If there is a pre-image which results to a certain hash, then that's the "original". If another comes up, and we have a collision, then we have two "originals".

This analogy isn't good. The equation has pretty much infinite solutions, but for a hash function to be claimed useless, you only need to find one solution. In this case, x=5, y=5.

Hash functions are a poor example of reversible computing, as they are irreversible by design.
The fact that many hash functions are composed of Addition, Xor, and Rotation is not that relevant.
Sure, these operations are reversible when you fix (or replicate in the output) one input. But hash function
constructions have no fixed inputs and don't replicate.

A good example of reversible computing is symmetric encryption, such as AES.
Here we have functions E(k,x) for encrypting plaintext x with key k, and D(k,y) for decrypting cyphertext y with key k
such that D(k,E(k,x)) = x. And for fixed k, or with k preserved in the output, this is all perfectly reversible,
and could in principle be computed with arbitrarily low energy expenditure.

The step you said here only works when we have 2 equations with 2 variables. Like x+y=10 and x-y=3 which is not the case with hash algorithms.

What we have in a hash algorithm is a chain of simple operations, each using the result of the last one(s). So each step backwards adds more unknown variables in equations we can never reverse.
For example the addition is actually the last step in SHA256 hash algorithm (you add each uint32 in hash-state with the computed temp values a to h) the step before that is another irreversible equation which adds even more variables since you'll have to solve a = T1 + T2 with each T being more additions and "bit shuffles".

Reference of the variable names I used:
https://datatracker.ietf.org/doc/html/rfc6234#section-6.2

So can you tell me the value for x and y? Is it 9+1, 8+2, 7+3, 6+4, 5+5, 4+6, 3+7, 2+8, or 9+1? Your method seems to fail, x and y could be any of them, and this is only 10, now you can realize the possibilities when you increase the size of your number.😉

if (x+y=10)
x=10-y
then substitute  x as 10-y in the equation to get the unknown.
With this method, it makes it possible to reverse the hash algorithm

`a+b=c` is irreversible when `a` and `b` are variables, turning it into `a=c-b` doesn't change anything since you are still left with 2 variables. The more you go back up the algorithm (in reverse) the higher the number of these unknown variables. The more you try the more unknown variables you are left with.

To put simply if you could ever reverse something as simple as (x+y=10) and tell me what x and y are in this equation, then you can reverse hash algorithms too.

Once you start adding other outputs to your function, what you have isn't SHA256 anymore, it is...something else.

And I don't actually see what what the advantage of general reversible computations would be. In quantum computation, they aren't an advantage, but a necessary property of nature you have to work around with smart algorithms.

The main question is, even if we manage to reverse a hash to get back an input, how can we know the input is our original input, I think I asked this once before, but the answer wasn't what I expected, if we don't have access to the original input, which is the case in every hash function out there, not having/knowing the input. We can never truly reverse the output to an input knowing whether it's the same original input or not.
This is because of collisions, they exist for a reason and I think it's what makes hash functions secure, for example if you take a sha256 hash of an uncompressed  Bitcoin public key, can you guarantee that if we manage to reverse the output, we could get the same uncompressed public key back? You can't, because even if you get an actual collision as the result of your reversal, there is no way of knowing whether the result is our original "unknown" input. Unless you check all possible candidates aka every single possible collision, how many would that be for sha256?

However if you can figure that out by working on more blocks and correctly guess the original input, then we are screwed.

---

Now I'm a bit confused, our math ph.D talks about energy efficient computing when he mentions "reversible computers", which has something to do with erasing and writing bits of information, are they related?

Let's start from some quotes, because that's what I started with, before creating this topic.

Many people cannot understand it, especially the last sentence about "mostly reversible components". Which means, they repeat like a parrot that "hash functions can be executed only in one direction". They think that hash functions are "irreversible", which means, they treat it like a black box, and they think, that whatever gets in, then never can get out, or get in another direction. This is only partially true, and I will try to show you, why.

The first thing to note is that I already demonstrated a practical example, to show exactly, how to execute some hash function backwards: https://bitcointalksearch.org/topic/m.60342783

Also, I repeated that again in some other topics, for example here: https://bitcointalksearch.org/topic/m.62397317

So, let's talk more about "mostly reversible components". What they are, how they are defined, how to use them, and so on. Because I started my journey from SHA-1, I will use that in my examples, but a lot of things can be also applied to SHA-256, or other hash functions. The most important thing is the internal construction of a particular hash function: if it is identical for two different hash functions, then guess what: similar attacks can be performed on both, which I also demonstrated by attacking the first 16 rounds of SHA-256, exactly in the same way, as I did it for SHA-1: https://bitcointalksearch.org/topic/hardened-sha-1-vs-weakened-sha-256-how-to-test-them-5467882

The main keyword that helps a lot is called "ARX". Which is an abbreviation of "Addition, Rotation and Xor". Those three operations, combined together, can be used to make new hash functions, and reach certain properties. In case of SHA-1 and SHA-256, they both use that ARX model. Which also means, if you can think about any successful attack for ARX, then you can use that on both SHA-1, and SHA-256.

So, let's dig deeper, and explain, what I promised, step by step. First, we can take Addition. If we work with integers, we all know that addition can be reversed by using subtraction. Those two operations are connected. If you have "a+b=c", then you can also go back, and write it as "a=c-b". Which means, if you start from "a", combine it with "b", and reach "c" as a result, then you can obviously throw away your "b", and claim that your operation is "irreversible". But this is not the case!

So, how to write the same thing in a reversible way? Well, the answer is quite simple: you can just save your "b", instead of throwing it away. Which means, if you write "(a,b)" as your input, instead of just writing "a", and "c" as your output, then it is perfectly reversible operation. Then, you can take subtraction, pass "(c,b)" as your input, and reach "a" as your output.

Also, the best news is that using modulo, for example modulo 2^32, which is used in both SHA-1 and SHA-256, is not going to change anything. Addition modulo 2^32 can be simply reversed by using subtraction modulo 2^32. Other operations are also reversible. If you take Rotations, then left rotation by 30 bits can be reversed, if you just apply left rotation by 2 bits. Because left rotation by 32 bits is just a "do nothing" operation, so you can easily complete it. With Xor, it is even easier, because you can just Xor again by the same value, and you are done.