What is the differences between Hash and Secp256k1?

[GR Sasa]

Hello guys, i have a interesting question about Scep256k1 that Satoshi implemented for the developlment of Bitcoin.

Now of course i know that Hashing is the process of transforming any given input into another completely Random fixed output value which is in bits.

But since the output of Hashing is completely Randomized and non-reversible, does ECC(Scep256k1) theoretically work the same as Hashing?

Because in Hashing (E.x Let's take SHA256) we have a a relation between the Input and the output. We give any input and we get a random fixed 256 bits value back to us. In Hashing, We need to imagine the input as the private key and the output as the public key.

In ECC(Scep256k1) We can also generate and give any wanted private key input within 256 bits and take back as a output a random fixed 256 bits public key.

So what is the differences between Scep256k1 and Hashing exactly if both give us random outputs?

Are they both non-reversible?`

Which is more secure e.x for bruteforce attacks/reverse attack?

[BtcMaxi2090]

No, ECC (Elliptic Curve Cryptography) and hashing are different concepts with different purposes in cryptography.

ECC is a public-key cryptographic algorithm that relies on the mathematics of elliptic curves to provide key exchange, digital signatures, and encryption

 hashing is a one-way function that takes an input (such as data or a message) and produces a fixed-size output, called a hash value or digest

[odolvlobo]

The short answer is that both encryption and hashing produce outputs that look random, but encryption is reversible and a hash function is not.

[GR Sasa]

but encryption is reversible and a hash function is not.

If encryption is reversible, then how is still Bitcoin's alive? Every day thousands of public keys are exposed

[gmaxwell]

The input to a hash is arbitrary size, while the input to the pubkey generating function hast to be 256 bits or smaller.

The ECC key function is additively homomorphic:   PUBKEY(x) + PUBKEY(y) = PUBKEY(x + y)  while  HASH(x+y) is unrelated to HASH(x)+HASH(y).

This structure would be considered a vulneablity for a hash in the applications where hashes are used, but it's what makes ECC digital signatures possible.

Someone could use ECC to create a hash function, but they would need to produce a way to handle larger inputs and modify the output destroy the homomorphic property.  It would also be slow.   The NSA did this once, as part of a deterministic random bit generator. DRBGs usually use hash functions, in DualEC the NSA built one out of elliptic curve cryptography ... specifically so they could engineer a backdoor into it the special properties of ECC.     The DRBG was so slow and complicated that most people paid it little attention and assumed no one would use it,  but then the NSA paid RSA $10 million dollars to make it the default RNG in RSA's bsafe library.  RSA also use to use the threat of patent litigation to force people to use BSAFE for many years, so it wasn't an obscure library.

[NotATether]

The DRBG was so slow and complicated that most people paid it little attention and assumed no one would use it,  but then the NSA paid RSA $10 million dollars to make it the default RNG in RSA's bsafe library.  RSA also use to use the threat of patent litigation to force people to use BSAFE for many years, so it wasn't an obscure library.

Quite sad how a large multinational corporation would sell out for a few million bucks. I could understand an individual being tempted by that much money, but for corporations who (are expected to) make several hundred millions or even billions of dollars every year, a $10M bribe just looks like a blip in the financial accounting books.

Fortunately projects like OpenSSL got up to speed quickly - the NSA can't pull this garbage again with an open source project.

[pooya87]

but encryption is reversible and a hash function is not.

If encryption is reversible, then how is still Bitcoin's alive? Every day thousands of public keys are exposed

There are a couple of mistakes in the odolvlobo's comment.
First of all Elliptic Curve Cryptography used in bitcoin has nothing to do with encryption. The primary use of ECDSA (the signature algorithm used by bitcoin) is also for asymmetric cryptography not symmetric cryptography (ie. encryption/decryption).
Secondly what we have in symmetric cryptography is encryption and decryption which is not the same as "reversing" the result. You are "decrypting" the encrypted result using the passphrase used for encryption. Otherwise the encryption is also irreversible, meaning you can't compute the message by having the encrypted result alone.

[witcher_sense]

So what is the differences between Scep256k1 and Hashing exactly if both give us random outputs?

In the case of elliptic curve cryptography, produced outputs have a strong mathematical relationship with input: consequent private keys always produce consequent public keys, albeit in a way that makes it almost impossible to deduct the former from the latter. This relation is clear and may be described just by a single function. In the case of hashing algorithms, the relationship between input and output is obfuscated by design: it can no longer be described by a simple mathematical formula but still produces a deterministic result. In my view, the main difference between these two algorithms is their use case regarding data itself. The elliptic curve cryptography can be used to verify the ownership over a specific piece of data, while the hashing algorithm can be used to verify the integrity and authenticity of data and create data fingerprints.

[gmaxwell]

First of all Elliptic Curve Cryptography used in bitcoin has nothing to do with encryption.

Not to dispute your post overall, but a cool thing about science and especially mathematics is that it's rare that any two subjects are really unrelated.  That's especially true here.

Digital signatures with elliptic curves (and many other asymmetric schemes) can be understood as an example of encryption, it's easiest to see using a schnorr signature (which Bitcoin uses) but the point applies to ECDSA as well.

First, I'll describe the Schnorr identification protocol as an application of encryption:

Alice and Bob have access to an encryption algorithm that is additive homomorphic, meaning that enc(A+B) = enc(A)+enc(B)  (this also necessarily means that you can multiply ciphertexts by integers).  For this scheme decryption will never be needed, so it doesn't have to support decryption (though it could be done with schemes that could be decrypted too).  It's not absurd for additive homomorphic schemes to not allow decryption in general, it's the case for the additively homomorphic version of elgamal encryption (it can't be decrypted without solving a discrete log problem).

Alice picks a secret value z and encrypts it to produce a public value P that she publishes.

Later Alice meets Bob and Bob wants to validate Alice's identity.  To do this Alice constructs a random line based on her secret by picking a random value k,  so that the line is k + xz.   Alice encrypts k to get the value R which she sends to Bob.

After getting R, Bob picks a random point x and can compute an encrypted evaluation of the line at x using the encrypted coefficients sent by Alice:  enc_s = R + xP.  He sends x to Alice.

Since Alice has the unencrypted values k and z Alice can compute the unencrypted evaluation s = k + xz.  Alice sends this to Bob.

Bob now encrypts the s he got from Alice and compares it to the one he computed himself.  If it matches Alice had to know the unencrypted versions of k and z.

Now this is not yet a signature, because it requires Bob's cooperation, only convinces Bob, and doesn't involve a message.

The first step to fixing that is to eliminate Bob's active role in the protocol.  All bob is doing is picking a random number!  You might think one random number is is as good as any other, so Alice can pick the random number x.    But the problem is that x must be picked after k/R is chosen.  Otherwise anyone could pick a random s and x then compute R = xP - enc(x) and claim that {R,s} is a valid identification for P-- they don't need to know the secret for P (z).

So bob's real purpose in the identification protocol was just making sure Alice picked k/R first.

So to accomplish that without Bob, we can use a one way function to pick the random value based on R.  The usual way is with a hash function, though if you wanted to overdue the theme here encryption could be used (but in this case, it needs to be one where no one involved can decrypt).

So Alice sets:

k = random()
R = enc(k)
s = k + H(R)z

And publishes R,s;  which will convince anyone that she's the holder of P's secret when they check if enc(s) == R + H(R)P.

And we're almost to a signature, to get a signature we just need to make the choice of H() depend on a message, the easiest way to do that is to just concatenate it and replace H(R) in the protocol with H(R || message).   Tada: this is a standard schnorr signature, but just described as an application of additively homomorpic encryption (and a hash).

Beyond just making a weird point about encryption, this perspective could potentially help people understand on the signature works other than "magic":   The signer computes a secret line using their private key as the slope and a secret random value as the intercept. They evaluate the line at a random location determined by a hash of the encryption of their intercept and a message. They disclose the evaluation and the encryption of their intercept.  The verifier can check that the evaluation is correct because they have the evaluation location and encryption of the coefficients.  The common attacks on signatures e.g. using nonce reuse are just high school linear algebra on solving for a line giving evaluations.

With a little elaboration can even use this scheme to securely communicate a secret message which is indistinguishable from a signature too!  Lets imagine Alice has pubkey W (encryption of z1) and Bob has pubkey Q (encryption of z2) and wants to send the (short) encrypted message m to bob over a channel that only lets Alice communicate valid signatures.

Alice picks a cover message c that she's signing. Care must be taken to not ever reuse the same cover message with the same two parties and a different secret message.

Alice generates a new secret z that she'll use as her fake 'pubkey' for this signature:

z1 = H(W || Q || z1 * Q)   # (c could be included in this hash for better privacy if you want)
W = enc(z1)


Then signs:

k =  H(c || z1) + m
R = enc(k)
s = k + H(R||c)z


The result {W, R, s} is a valid signature for message c and can be transmitted over the signature only channel.  There are simpler ways of doing this (just set K to your message and have alice and bob share z) but they have more security footguns other than the requirement that c can't be reused.

Bob can use his knowledge of z2 to recover m from W, R, s, c. (exercise left for reader). Third parties can't distinguish this from an ordinary signature.

[odolvlobo]

but encryption is reversible and a hash function is not.

There are a couple of mistakes in the odolvlobo's comment. ...

Gah! Corrected by pooya87 again! It appears that I know just enough about cryptography to get myself in trouble. Luckily, I know enough to leave the implementation to the real experts.

However, my statement is true, though perhaps not clear. You can restore an encrypted message by decrypting, but you cannot unhash a hash.

[vjudeu]

You can restore an encrypted message by decrypting, but you cannot unhash a hash.

Yes, you cannot "unhash a hash" if you only know the final hash, and the hashing algorithm. However, you can execute hash function backwards, if you have enough data. Precisely speaking, if you know initial hash, and final hash, you cannot compute data in-between without breaking hash function. However, you can make it bidirectional: not only you can start from initial hash and data as your input, and reach final hash as your output, but you can also take the final hash and data as your input, and reach initial hash as your output (execute it backwards).

If you want to see in practice, how SHA-1 can be executed backwards, you can see this post when I started from "2328fad3 75109b40 3f121481 02e1def6 cfd74e98", and passing the message with all zeroes resulted in the same final hash.

[digaran]

You can restore an encrypted message by decrypting, but you cannot unhash a hash.

Yes, you cannot "unhash a hash" if you only know the final hash, and the hashing algorithm. However, you can execute hash function backwards, if you have enough data. Precisely speaking, if you know initial hash, and final hash, you cannot compute data in-between without breaking hash function. However, you can make it bidirectional: not only you can start from initial hash and data as your input, and reach final hash as your output, but you can also take the final hash and data as your input, and reach initial hash as your output (execute it backwards).

If you want to see in practice, how SHA-1 can be executed backwards, you can see this post when I started from "2328fad3 75109b40 3f121481 02e1def6 cfd74e98", and passing the message with all zeroes resulted in the same final hash.

But it's impossible to go backwards, even going backwards does not reveal anything about the original input, because the input is irrelevant to the output. You could have empty string as input, how can we perform the hash function backwards to reach something that doesn't exist? What you have done with SHA-1 is possible because you already know the input, without knowing the input whatever you do is blind guessing.

The difference between a hash and a public key in secp256k1 is that you can verify the authenticity of a file or data having the said file or data, but in ECC you can't have the data (private key) while by having a message signed by that data you can confirm the authenticity of the message, the message could be a transaction or just a message.

What sets them apart is the fact that both hash function and ECC can be solved, you could solve the "hash problem" by finding a collision, also you could solve a public key by finding a divisor.
Finding a collision should be easier IMO since the number of collisions is far far greater than number of private keys in EC.

[vjudeu]

But it's impossible to go backwards

Why do you think it is impossible to go backwards? Imagine you have two values:

Code:

std::uint32_t a=0xbadc0ded;
std::uint32_t b=0xc0deba5e;
std::uint32_t c=a+b;

In this case, "c" is just a sum of "a" and "b", with implicit modulo 2^32, as used in SHA-1, SHA-256, and other hash functions. Imagine that in some round you have to calculate "c". Does it mean that going backwards is impossible? Of course not, it is impossible if you only have "c", and from that alone you want to get "a" and "b". Then it is impossible, because there is more than one solution. However, if you have for example "c" and "b", then you can easily calculate "a" as a difference between "c" and "a", modulo 2^32, and you will reach this value.

Using the same trick, instead of starting from initial hash, and passing w-values from w[0] to w[80], you can start from the final hash, and pass w-values from w[80] to w[0] instead, then you can compute things backwards, because you can reverse a round, if you have enough data to have a single solution.

because the input is irrelevant to the output

The input has to be relevant to the output, because for identical input, you have to reach identical output. It has to be deterministic, the only thing is that you cannot say "this input bit changes that output bit", but only because it is a combination of addition, rotation, and xor. That makes it messy, but there is still a strict, deterministic connection, it is just more complex, and it involves many bits, for that reason hash functions are safe.

You could have empty string as input, how can we perform the hash function backwards to reach something that doesn't exist?

There is always at least one 512-bit block of data, no matter what you have as your input. If you have empty string, it looks like that:

Code:

80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

To start calculating things backwards, you can compute all w-values, and then start from w[80], and apply it to the last round, instead of starting from w[0], and applying it to the first round.

What you have done with SHA-1 is possible because you already know the input, without knowing the input whatever you do is blind guessing.

Of course you have to know the input. There are three different things:

Code:

+--------------+----------------+------------+
| Initial hash | 512-bit blocks | Final hash |
+--------------+----------------+------------+
| input        | input          | output     | regular hash function
| output       | input          | input      | executing things backwards
| input        | output         | input      | breaking hash function
+--------------+----------------+------------+

The second case and the third case are different. Executing things backwards is not the same as breaking things, because you have different inputs and outputs.

Finding a collision should be easier IMO since the number of collisions is far far greater than number of private keys in EC.

There are different security levels, depending on what do you want to get:
1. Breaking a public key: 128-bit
2. Breaking some deeply confirmed hash of a public key, by reaching identical address: 160-bit
3. Getting two identical legacy addresses: 80-bit
And then, finding a collision is easier or harder than breaking some public key, it depends if by saying "collision" you think about the second, or the third case.

[BlackHatCoiner]

Precisely speaking, if you know initial hash, and final hash

By "initial hash", do you mean the pre-image of the final hash?

You could have empty string as input, how can we perform the hash function backwards to reach something that doesn't exist?

"Nothing" is actually something. There's just no user inserted input, but there's at least a 512-bit block of data as vjudeu has pointed out. I do understand your concern though. You could respectively make the question as following: "how can we perform the hash function backwards to reach something that is larger than the hash itself?". It'd be quite strange from a compression perspective. Also, a similar query would be: "how can we perform the hash function backwards, knowing that there is no unique origin due to collisions?".

Nonetheless, arguing that it's impossible to go backwards is incorrect, because NP != P isn't proved.

I've always had this question. Why isn't it provable that going backwards is impossible? Why is NP != P required to prove it? With some quick thought, taking the simplest hash function (hash = input % prime), it is trivial to prove it can't go backwards, because you can't reach the divisor by only knowing the remainder and the dividend. You can only guess numbers until find one.

[vjudeu]

By "initial hash", do you mean the pre-image of the final hash?

For SHA-1, the initial hash is defined as: 67452301 efcdab89 98badcfe 10325476 c3d2e1f0. However, this value is used only for the first 512-bit block. After that, the final hash after processing the first block becomes the initial hash for the second 512-bit block. It is all about Merkle–Damgård construction: you have some initial hash, some data in-between, and some final hash in the end, that is passed as input for the next block of data. In this way, SHA-1, SHA-256, or any hash function using this scheme, has to be defined only for a single block, and then it can be easily expanded into N blocks by splitting data into K-bit chunks during the preparation phase.

how can we perform the hash function backwards to reach something that is larger than the hash itself?

The size of the message is included only in the latest 512-bit block. That means, if you want to perform a single-block attack, then yes, you have to be careful, and create a message, where the last 64 bits define the size of the whole message (in bits), before that there are zeroes for padding, and a one as a separator. However, you can create for example two 512-bit blocks, then in the first block you can put anything anywhere, and the second block will be a constant, in this case it will always be equal to that:

Code:

80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000200

Then, your hash function will work in this way:

Code:

67452301 efcdab89 98badcfe 10325476 c3d2e1f0   initial hash
........ ........ ........ ........            the first 512-bit block
........ ........ ........ ........ 
........ ........ ........ ........
........ ........ ........ ........
........ ........ ........ ........ ........   middle hash
80000000 00000000 00000000 00000000            the second 512-bit block
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000200
........ ........ ........ ........ ........   final hash

Then, if you will reach some identical "middle hash", it will move you to the identical "final hash". That means, you only have to focus on processing a single 512-bit block, because if that will ever be broken, it will also allow reaching any hash by just modifying a single 512-bit block, reaching identical hash in the middle, and the rest will stay the same, because identical operations will be repeated on identical data.

If you analyze the consequences of breaking the hash function, you will notice that replacing a single 512-bit block is enough to perform a lot of attacks. You can for example limit SHA-1 or SHA-256 to the first 16 rounds. Then you will notice, how easily you can create any hash you want, and how you can start from some empty message, and reach some 256-bit message that will lead you to the identical hash.

how can we perform the hash function backwards, knowing that there is no unique origin due to collisions?

You can take initial hash, and the first 512-bit block data as your input. Then, hash function will produce the middle hash. However, you can also take the middle hash, and the first 512-bit block, and by computing things backwards, it will produce the initial hash. You can go backwards or forwards, because a lot of operations are reversible: if you know that "c=a+b", and that is the default flow, then you can also do "a=c-b" instead, and just execute it backwards. It is all about having enough data.

If you use 512-bit blocks, and some hash on one side as your input, you can reach some hash on another side. This is different from practical attacks, because then you don't know the content of the 512-bit blocks, and you only know hashes on both ends.

Why isn't it provable that going backwards is impossible?

Going backwards is possible. You can reduce SHA-1 or SHA-256 into the first 16 rounds, and then you can go backwards, forwards, or even modify things in the middle, because then w-values can be set to any values you want. The only reason why you cannot do the same with the real hash functions, is that by going through all rounds, you reach a spaghetti of dependencies. Then, it is harder to see, which bits you have to touch to reach the values you want, but still, it is fully deterministic, and fully reversible, just more messy, when you can trace some bit, and notice that it is connected with for example 80 other bits.

Also, I shared an example, when I executed SHA-1 backwards. If you start from 2328fad3 75109b40 3f121481 02e1def6 cfd74e98 as your initial hash, and you use a block of all zeroes as your 512-bit block, then you reach the same value as your middle hash. The only reason why this attack cannot be used in practice, is that in SHA-1, the initial hash is defined as 67452301 efcdab89 98badcfe 10325476 c3d2e1f0. However, if you look at values in each round, you can clearly see that it is perfectly valid to compute things backwards, if you have enough data.

Why is NP != P required to prove it?

There are two different things: one is computing 512 bits in the middle, by knowing hashes from both ends. This is breaking hash function, and nobody knows, how to do that. However, knowing 512 bits in the middle, and some hash on one side, is another thing. When I say that going backwards is possible, I mean it is not only possible to go from initial through middle to final hash, but I mean you can start from the end, and by passing some data, you can execute hash function in the opposite direction: if you have left rotation by 5 bits, you can do left rotation by 27 bits instead. If you have addition modulo 2^32, you can use subtraction modulo 2^32 instead. And so on.

[Flexystar]

Just about the time I posted links to article about what is Keccak256 and Elliptic Curve Digital Signature Algorithm. Good to see various explanation done by various users here. However I would still encourage OP to read the below quoted articles. They are in depth and will help you understand the entire concept easily.

By definition Keccak256 is a hash function that produces fixed output of 256 bits. Mostly used in ethereum ecosystem and works by taking inputs with arbitrary length data set. Also responsible for transaction ID, cortical value creation.

While on the other hand elliptical curve is also mentioned as secp256k1. This has another function as compared to the above one and helps in asymmetric cryptographic systems features, including encryption, signatures, and key exchange.

You can read in detail how both of them work here:

1. Keccak-256 hashing alghorithm
2. secp256k1 elliptic curve