Mechanical hashing

[vjudeu]

To explain better, how crypto works, for less-technical and less-digital people, there is a need to explain hash functions mechanically, without involving any electricity. I think it should be technically possible to make a mechanical device, where any user could set any Initialization Vector for SHA-256, set any 512-bit message, and see the result of hashing this block once by SHA-256. That could be used to better explain, how mining works. If someone will make something like that, I will buy it for Bitcoin. I saw some interesting projects here, maybe this idea could inspire someone to make something like that for some hash functions, for example SHA-256.

[NotATether]

Or what about a device with an LED screen that simply does one round of initialization on an input, but allows you to customize the round by choosing which states to combine with others, how they combine (XOR, right-rotate and others)?

There would be a button and keypad that lets you input a random string for hashing (the button is for starting and resetting the input), and another "Hash 1 round" button.

Would definitely resemble more like a raspberry pi with an embedded screen, or TI-85, and would make it much easier to represent 2^64 states (or a similar large number) than a mechanical device.

[Zilon]

Looking at a device like a chaotic fluid where Hashing is simply done through hydrodynamics. We could liken it to stirring a muddy fluid a sort of mechanical device just like in a microfluidic device  which can be can be used in a digital information system.

This chaotic maps can encode information about the underlying flow dynamics into the relative arrangements of advected particle which in our case study is SHA-256 hash function with arbitrary message of 512-bit
https://www.pnas.org/doi/10.1073/pnas.1721852115

[DannyHamilton]

Not sure about a "mechanical" solution, but if you want to do it with paper and pencil...

http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html

https://www.youtube.com/watch?v=y3dqhixzGVo

[vjudeu]

Not sure about a "mechanical" solution, but if you want to do it with paper and pencil...

I did it with paper and pencil. And no conversion from hexadecimal to binary was needed, except rotations. But I know that mechanically it should be possible. When it comes to addition, it is possible to create "addition table", like this:

Code:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| + | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 4 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 5 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 6 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 7 | 7 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 8 | 8 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 9 | 9 | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a | a | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| b | b | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| c | c | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| d | d | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| e | e | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| f | f | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

I created more such tables, for moving values during addition, multiplication (needed to validate k-values), and other things like that. After few hours, I could add hexadecimal numbers as well as decimal ones. Constructing similar tables for rotations is also possible, but it is harder. So yes, I know how to do it by hand, and I can reach a bit better hashrate than on this video, but it is still not sufficient. I think about something similar to a mechanical calculator, but it should work on SHA-256 (or even better: should also allow hashing things multiple times), should use hexadecimal (or binary, or other power-of-two-based system) keyboard, and allow quite fast calculation, by setting IV, setting data, and then it should turn Initialization Vector into Exit Hash. It could work on-the-fly, and modify w-values on-the-fly, then going backwards could be possible by rotating it mechanically in the opposite direction.

[larry_vw_1955]

It could work on-the-fly, and modify w-values on-the-fly, then going backwards could be possible by rotating it mechanically in the opposite direction.

SHA-256 is not reversible by rotating a crank in reverse. 

[vjudeu]

SHA-256 is not reversible by rotating a crank in reverse.

It actually is, if you have the whole needed context. You can compute rounds backwards, if you have all data. Using IV and w-values from w[0] to w[15] is one option, but you can also go backwards, use Exit Hash, use the last 16 w-values, and compute everything backwards, you will then reach IV. I can demonstrate it further in my topic about hash functions if you cannot see that.

The only thing that is "irreversible" is getting IV and Exit Hash as your input, and getting data as your output. But if you have data, then you can go backward or forward, you can go from IV to Exit Hash, or from Exit Hash to IV, many operations are perfectly reversible.

Edit: Here you go, see this post about "irreversibility": https://bitcointalk.org/index.php?topic=5402178.msg60342783#msg60342783

[larry_vw_1955]

SHA-256 is not reversible by rotating a crank in reverse.

It actually is, if you have the whole needed context. You can compute rounds backwards, if you have all data. Using IV and w-values from w[0] to w[15] is one option, but you can also go backwards, use Exit Hash, use the last 16 w-values, and compute everything backwards, you will then reach IV. I can demonstrate it further in my topic about hash functions if you cannot see that.

Not sure about that. SHA-256 uses modular arithmetic which is not reversible. it also use some compound operations involving "xor" and "and". those are not reversible either most likely.

The only thing that is "irreversible" is getting IV and Exit Hash as your input, and getting data as your output. But if you have data, then you can go backward or forward, you can go from IV to Exit Hash, or from Exit Hash to IV, many operations are perfectly reversible.

I don't think a mechanical device could store all the needed data to be able to do it in reverse. it would have to store alot of information. think a computer. with memory.

Edit: Here you go, see this post about "irreversibility": https://bitcointalk.org/index.php?topic=5402178.msg60342783#msg60342783

i honestly didn't understand any of that. but sha-256 is a pretty complex thing. i don't think a mechanical device could reverse it in any meaningful way. now if you're talking about a mechanical machine that can store alot of data so that when you turn the crank backwards it spits out the intermediate outputs in reverse order, i guess it is theoretically possible but it's not really reversing it mathematically it's just spitting out stored data in a certain order.

[NotATether]

I gave this idea (sha256 device) some more thought and I've realized that you can even build a web service out of it if you can't afford manufaturing units.

No I'm not talking about "input text, get SHA256 hash out". You can actually design the rounds as if they were state machines. It could provide predefined rounds for most common hashing functions such as the SHA-2 and -3 families, Keccak, HMAC, RIPEMD160, etc. etc and of course it would allow you to design your own rounds.

In this way even normal people would be able to experiment with hash functions without the need to buy hardware for them.

[vjudeu]

Not sure about that. SHA-256 uses modular arithmetic which is not reversible.

Modulo is reversible, if you have enough context. For example:

Code:

a=badc0ded
b=c0deba5e
c=a+b=(badc0ded+c0deba5e)=7bbac84b
c=7bbac84b
b=c0deba5e
a=c-b=(7bbac84b-c0deba5e)=badc0ded
a=badc0ded

See? Addition modulo 2^32 is perfectly reversible. It is like a clock, you can use modulo 60 to represent the current second. You can add seconds, you will get them modulo 60. But you can also subtract them, then you will get it backwards. So, addition modulo 2^32 can be reversed by using subtraction modulo 2^32, it's that simple. The same with many other bijective operations: if you have xor, you can xor it again by the same value. If you have rotation, you can rotate it back. And if you can compute Addition, Rotation and Xor backwards, then you can implement the whole ARX model backwards.

it also use some compound operations involving "xor" and "and". those are not reversible either most likely

When it comes to "and", it is irreversible, but only partially (if you have "true" as your result, you know that all values were also "true"). Because it is used only internally, and is not a main operation to combine things, it can be reversed. Hash functions like SHA-1 and SHA-256 use Addition, Rotation, Xor, as their main core, functions like "and" or "or" are used only internally. Also, even if you think that "xor" alone is irreversible, then you are wrong, because having all 16 w-values is enough to xor and rotate them in any needed way, to recover all other w-values forward and backward.

it would have to store alot of information. think a computer. with memory

I don't think hash functions need more memory than a few kilobytes at most. The bare minimum for SHA-256 is eight 32-bit values for IV, eight 32-bit values for Exit Hash, and 16 32-bit values for the message. Then, maybe a few more 32-bit values will be needed to make it convenient, so the total memory cost could be, I don't know, 256 bytes? Maybe 512 bytes? Hash functions are not that complex to require a lot of memory, I think it is possible to do below 1 kB.

i honestly didn't understand any of that. but sha-256 is a pretty complex thing

Why do you think that SHA-256 is much more complex than SHA-1 in my examples? It has different k-values, and some different internal functions here and there, but the core of the whole hashing is pretty much identical. Also, when it comes to preimage attacks, it is also pretty much the same way of doing things, only some functions has to be changed here and there.

i don't think a mechanical device could reverse it in any meaningful way

Why not? Do you think that having a mechanical device that will perform 32-bit modulo addition is also impossible? Why? It is less complex than you think, you can write some simple code in any language, or even in some mathematical tool to see, that implementing hash functions is quite easy, much easier than implementing for example ECDSA. And then, if you have some hash function, executing all of my described attacks is pretty much straightforward, you just take one formula and transform it, for example:

Code:

w[i]=rol(w[i-16]^w[i-14]^w[i-8]^w[i-3])   //rotate both sides by 31 bits
rol31(w[i])=w[i-16]^w[i-14]^w[i-8]^w[i-3] //xor both sides by w[i-14]^w[i-8]^w[i-3]
rol31(w[i])^w[i-14]^w[i-8]^w[i-3]=w[i-16] //swap sides
w[i-16]=rol31(w[i])^w[i-14]^w[i-8]^w[i-3] //here we go, now we know, how to reverse w-values

but it's not really reversing it mathematically it's just spitting out stored data in a certain order

It actually is "reversing": if you have "a xor b = c", then you can mechanically xor "a" and "b", get your result in "c", and later use "c xor b = a" to restore "a". The same with addition modulo 2^32 that can be reversed by using subtraction modulo 2^32, and the same with rotations, that could be reversed by rotating it further: if you have rol5, you can reverse it by doing rol27, because 5+27=32, and rol32 means nothing will be changed.

[pooya87]

See? Addition modulo 2^32 is perfectly reversible.

That is not what reversing is though. Real reversing is when you only have c and want to compute both a and b otherwise you are just using modular arithmetic properties namely compatibility with translation.
In reality (such as hash digests) you don't have a or b.

[vjudeu]

That is not what reversing is though. Real reversing is when you only have c and want to compute both a and b otherwise you are just using modular arithmetic properties namely compatibility with translation.

Exactly. And that's all needed to make a physical device for it. I can imagine starting from Initialization Vector and w-values from w[0] to w[15], then by rotating it mechanically, like in a mechanical calculator, next rounds could be computed, round by round, that would tweak w-values one-by-one, and finally there will be Exit Hash, and the last 16 w-values, for example from w[48] to w[63], in case of SHA-256 and 64 rounds. Then, it could be possible to reverse everything, just by mechanically rotating it backwards, it would be an equivalent of starting with some fixed last round, taking the last 16 w-values, and computing it backwards, to get Initialization Vector again. I demonstrated it is possible for SHA-1, I think it could work in pretty much the same way for other hash functions, like SHA-256.

In reality (such as hash digests) you don't have a or b.

Yes, in reality you know the Initialization Vector, and the Exit Hash, but not the message in-between. And that is of course irreversible. But on the other hand, hash functions can be executed forwards and backwards, going from the Initialization Vector, by taking message, and reaching Exit Hash is as possible, as it is to start with the Exit Hash, take tweaked w-values, and compute everything backwards, to reach Initialization Vector. It is bidirectional, and that property is enough to make a physical device for such algorithm.

[larry_vw_1955]

Then, it could be possible to reverse everything, just by mechanically rotating it backwards, it would be an equivalent of starting with some fixed last round, taking the last 16 w-values, and computing it backwards, to get Initialization Vector again. I demonstrated it is possible for SHA-1, I think it could work in pretty much the same way for other hash functions, like SHA-256.

i think that is actually correct. you can do that with sha-256. the thing is, if you just have one single 512-bit chunk, then you don't really need to reverse anything if you know the 16 w-values since those hold the original message. cranking your mechanical machine in reverse wouldn't do any useful work it would just get you back the original 8 hash values which are already hardcoded into the algorithm so what would be the point?

if your machine could operate on messages with more than one chunk then it might be more interesting.

a more useful mechanical machine would be one that you could input a bitcoin private key and turn the crank and it would tell you the associated bitcoin address.

[vjudeu]

if your machine could operate on messages with more than one chunk then it might be more interesting

First, let's get anything that could work on one chunk. Then, expanding it, is just a matter of passing many chunks as an input in some fast way. I think to explain mining, a single chunk is more than enough. The block header itself has 80 bytes, so 640 bits, that would mean two chunks. The hash of the hash means hashing the 256-bit result, so also one chunk. To demonstrate mining, it is needed to hash three chunks, and I think it would be a good start, definitely easier and faster than doing everything with paper and pencil.

a more useful mechanical machine would be one that you could input a bitcoin private key and turn the crank and it would tell you the associated bitcoin address

Well, ECDSA is more complicated, but yes, if someone would be interested in making such physical devices, that could be the next step, to provide point addition/doubling (and point subtraction/halving by rotating it backwards).

cranking your mechanical machine in reverse wouldn't do any useful work it would just get you back the original 8 hash values which are already hardcoded into the algorithm so what would be the point?

It is a matter of construction: having it bidirectional can be easier to mount than making unidirectional device. And if going in one direction will be simpler, then the constructor can also make it that way, that would be also a good start. But I prefer having it bidirectional, because then it is easier to demonstrate some attacks, like meet-in-the-middle attack.

[larry_vw_1955]

Well, ECDSA is more complicated, but yes, if someone would be interested in making such physical devices, that could be the next step, to provide point addition/doubling (and point subtraction/halving by rotating it backwards).

I think a device like that would have a use case you can generate a private key by rolling dice but then you have to go to a computer to generate its address. if it could all be done mechanically that would be safer than having to use a computer.

It is a matter of construction: having it bidirectional can be easier to mount than making unidirectional device. And if going in one direction will be simpler, then the constructor can also make it that way, that would be also a good start. But I prefer having it bidirectional, because then it is easier to demonstrate some attacks, like meet-in-the-middle attack.

i'm aware of a mechanical calculator called the Curta but it seems that it's a pretty complex device and all it does is add, subtract, multiply 2 numbers together. I guess a machine that could perform sha-256 would be much more complex in construction with so many more parts. and the curta itself is pretty complicated as it is. but this would be taking things to a whole new level. not only that but adding two numbers on the curta you just rotate the crank a couple times and it spits out the answer. with this sha-256 machine, you probably have to crank it over 100 times to get the hash output for a single chunk. have 5 chunks? then crank it 500+ times. i guess it's still ok since it is not something you would do all the time just for demonstration purposes or similar.

[vjudeu]

but then you have to go to a computer to generate its address

Not really. If you can add and double points, you can handle ECDSA. If you can do that, you have private to public key conversion (and in general, you can multiply any number by any point). Then, if you need Taproot, it is more than enough to handle that, because no hashing is needed to sign a message, you need hashing only to compute the hash of the message you want to sign. To generate Taproot address alone, having a public key is sufficient, you can just encode it in bech32m.

I guess a machine that could perform sha-256 would be much more complex in construction with so many more parts.

Even if it will be quite large, like a Wintergatan Marble Machine, it may still be useful in places, where there is no electricity. But I think hash function has just a few functions, that are constantly repeated. I think having some parts should be enough to do that, for example one part can handle rotation, another part can handle addition, something else for xoring, there is not that many functions as you expect, you can read my description in a separate topic, it is just a few simple functions working on uint32 values, and a few constants here and there, for example a table with 64 k-values for SHA-256.

then crank it 500+ times. i guess it's still ok since it is not something you would do all the time just for demonstration purposes or similar

It is acceptable, as long as it will be simpler and faster than doing that by paper and pencil.

[darkv0rt3x]

Just wondering about this mechanical device and I cannot picture anything unless we're talking about something like it was used by the Americans in WWII to decrypt German messages? That Turing machine and Bombe machine developed by Alan Turing and Welchman? Is anything like that, people is talking about here?

[vjudeu]

Is anything like that, people is talking about here?

Well, there is one main requirement: it should require no external power supply. If there is power outage, that device should still work. Someone proposed chemical hashing, I thought more about mechanical hashing, because it seems to be easier to compute than using paper and pencil, and it should be easier to learn, how to operate that. I thought about something simple, like constructing some tables for basic operations, like addition, rotation, xor, then it could be possible to compute hash functions manually, just by rotating a crank, or providing needed energy to the system in other simple ways. For example, it could be possible to paint squares in different colours to represent zeroes and ones, then negating the whole number could be done by simply rotating some wheels inside it by 180 degrees.

I thought about many different ways of doing that, but it seems some mechanical engineer is needed to make it real. It could use some buttons, some magnets, some rotating wheels with hex digits from "0" to "f", there are many options. Each state can be represented in many different ways, you could also place something here, like a marble (when it is present, it could represent "logical one", and when it is empty, it could represent "logical zero"). It could use gravity to implement logical gates. I don't know exactly how to make it, because I didn't find anything like that anywhere, maybe just nobody needed it yet.

To put it simply, it should be better than paper and pencil, and should work in cases, where no electricity is available, or if there is power outage, that's the general idea behind it. And I think making it in a mechanical way would be the simplest solution to that, but maybe there is something better available, I don't know (but I am not convinced for example to the chemical solution, that could be hard to do in a typical home, I think building a physical machine, or passing a ready-to-assemble project for some manufacturer, would be easier).

Edit: some visualization, how it could look like: https://upload.wikimedia.org/wikipedia/commons/4/44/Grant_mechanical_calculating_machine_1877.jpg
Of course it is just an example, because hash functions are more complex than that.

[larry_vw_1955]

I thought about many different ways of doing that, but it seems some mechanical engineer is needed to make it real. It could use some buttons, some magnets, some rotating wheels with hex digits from "0" to "f", there are many options. Each state can be represented in many different ways, you could also place something here, like a marble (when it is present, it could represent "logical one", and when it is empty, it could represent "logical zero"). It could use gravity to implement logical gates. I don't know exactly how to make it, because I didn't find anything like that anywhere, maybe just nobody needed it yet.

the thing about using marbles and gravity well it's an interesting idea but if you want it to be robust, then it can't make errors. it has to compute things correctly 100% of the time especially if it was used in some type of device that computed a bitcoin address. a mechanical device using marbles and gravity sounds like it might not be at that level. yes you could redo the same computation multiple times but that just adds to the complexity of the situation and unfortunately if the machine was somehow damaged and some marble wasn't falling correctly because of that then it would just be duplicating the same error and you would be none the wiser.

you could run a test vector through it every time first to make sure it was working correctly though. but still, a mechanical device seems like it could have some type of error rate. i'd say the error rate would need to be less than 1 in 1 million. maybe less than 1 in 1 billion. ideally even less than that.

[vjudeu]

the thing about using marbles and gravity well it's an interesting idea but if you want it to be robust, then it can't make errors

How it could be much worse than with using electricity? You have two marbles in a row. You release all gates, all marbles fall down, because of the gravity, and you collect the lowest row, if you want "logical or", or you collect the second row, if you want "logical and". It is that simple. Logical "or" means that there is at least one marble, logical "and" means that there are two of them, so they could be physically grabbed just by taking the second row, if they have the same size, then you will get one above the other if (and only if) both of them are present.

if the machine was somehow damaged and some marble wasn't falling correctly because of that then it would just be duplicating the same error and you would be none the wiser

I think it is just a matter of using the right materials, the right proportions, things like that. The whole world is physical, why using electricity is that important to make things tick? Another thing is that as long as we can use computers, it is just some interesting project that could be done "for fun", or maybe "for demonstration", it could be serious only if the whole world would be forced to abandon electricity altogether, because of some nuclear war, or other serious world-scale problems, but then, Bitcoin will be less important than having something to eat. I think crypto adoption is still too low to allow surviving in hard times, we are not there yet.