Topic: Mechanical hashing (Read 410 times)

It is simpler than you think. If you can implement addition, getting it modulo 2^32 means simply rejecting the highest bit. And addition can be handled just as a combination of XOR and the majority function. First, you use the lowest bit from "a", the lowest bit from "b", and zero as a carry, and execute a XOR on that to get the lowest bit of the result of addition. Then, using the same input, you execute the majority function: if there are at least 2-of-3 bits set to one, then there is a carry equal to one, otherwise zero. And you can go through it bit-by-bit, then you can save the last carry, if you want to produce 33-bit result for your addition, or just skip it, and then you will have it modulo 2^32, just by dropping one bit.

Another thing is that "modulo addition" and "modulo subtraction" is like rotating a clock: if you have modulo 60, then you can represent seconds. If you add 45 and 50, then you will get 95, but modulo 60 it will be 35. So, modulo addition is like rotating a huge wheel, where after 0xffffffff, you will get 0x00000000 (and the same in the opposite direction is true when you have subtraction). So, I can imagine for example 8 wheels with numbers from 0 to f, when they can be rotated to handle addition, and when each next wheel will tick only when the previous one was rotated by 360 degrees, and jumped from "f" to "0".

Well it seems like the key thing would be to break this device down into functional subunits that each performs a certain type of task. like XOR, AND,Rightrotate, + mod 2^32. then you can manufacture these subunits in quantity and assemble them into larger subunits that perform any general task.

Yes, I know. I just wanted to have an idea if these hashing machine would be anything like that concept of the Enigma machine! Other than that, yes, it would probably be even more complex as the mathematical processes that take part in the hashing functions are also complex (I have the idea, not the actual knowledge).
So, this said, and as I also said, to pull something like this out, we would need multiple people thinking, writing, modeling parts, drawing parts, manufacturing parts, not to even mention all the theoretical part before all the hardware work, right?

yeah but the electrical part was how it operated. based on making and breaking different circuits. if the battery ran out of juice there is no way that thing would have operated.

The electrical part of the Enigma was purely used for current flow to highlight the result of the purely mechanical change of rewirering of characters. The encryption process ie. the change of character to character wirering is completely mechanical.

a mechanical sha-256 hashing machine would probably be more complex than this enigma thing.  keep in mind too that the enigma was not purely mechanical. it was really electronic in nature.

Well, I don't even have all the knowledge present in memory to at least make a mental sketch of what would be needed. I am an electrical engineer but I am not even close to be able to put up something like this. This is something probably to be put up as a project with several stages an probably multiple teams working on each stage! Or someone really bright/smart/intelligent capable of pulling this off alone! I'm not that one for sure!

You need to know exactly about bits and bytes, cryptography, probabbly mechanical engineering, learn or find someone to design components in 3D software with great precision, think about probably thousands of details in each stage of the project etc.

If you are really into this, maybe we should start by making a statement and say: I have this goal. I want to do this and that. Whoever is interested and whoever has any type of skills, feel free to onbard. After that, we would need to start laying down the stages, tasks for each stage, what knowledge and skills are needed in each stage, etc. I can't see this done by simply throwing ideas in the air like we are doing!

If this machine is anything like the Turing machine, I can't imagine how many thousands of hours were spent by those 2 guys and probably by a bunch of other unknown people in the background!

Check this thing: Enigma machine used by Germans to encrypt messages
https://www.youtube.com/watch?v=G2_Q9FoD-oQ

xD

And then check the craking machine here, at aroun 5:30. Machine Turing built to decrypt Enigma machine encryption!
https://www.youtube.com/watch?v=Hb44bGY2KdU

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.

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.

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.

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.

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?

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.

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.

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

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.

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.

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.

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).

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 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.

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.

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.

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.

Modulo is reversible, if you have enough context. For example:
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.

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.

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.

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.

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:

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.

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.

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.

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.

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.