# Tag Info

52

A collision in any hash function gives a collision in a "squared" variant of the hash function. This is easy to see. If hash(x)==hash(y), then hashing the outputs will also be the same. So the wiki entry is wrong. To see the real purpose of the double hash see this question and answers.

48

The main difference is that secp256k1 is a Koblitz curve, while secp256r1 is not. Koblitz curves are known to be a few bits weaker than other curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough. The other difference is how the parameters have been chosen. In secp256r1 they are supposedly ...

29

A common rationale for hashing twice is to guard against the length-extension property of the hash (if it has that property, as many hashes before SHA-3 did). For SHA-256, this property allows to compute $\operatorname{SHA-256}(X\|Y\|Z)$ knowing $\operatorname{SHA-256}(X)$ and the length of $X$, for some short $Y$ function only of the length of $X$, and some ...

21

The curves secp256r1 and secp256k1 have comparable security. If we consider only the best known attacks today, they have very close security. Both curves are defined over prime fields and have no known weakness, therefore the best attack that applies is Pollard's Rho. Its complexity is: $\sqrt{\frac{{\pi}n}{2m}}$ where $n$ is the order of the curve (if it's ...

18

The Bitcoin mining algorithm can not be simplified by exploiting any weakness in the SHA-2 hashing algorithm with the current state of the art. The problem is manyfold. From the SHA-256 point of view, there is no (partial) preimage search algorithm that applies to the full hash function. Even worse, the attacks that penetrate a fewer number of rounds have ...

15

There's a good reason many democracies reserve mail voting to rare cases where that's the only option: it allows one's vote to be influenced by duress or bribery, because one can prove how one voted. No remote voting technology that I know has solved that issue. Ergo, physically going to a polling station with isoloirs should remain the normal voting ...

15

Since the initial release of Bitcoin is 9 January 2009, the designer had these NIST hash functions (NIST-FIPS 180-4) as available options: SHA-1( 1995), SHA-256 (2001), SHA-512 (2001), and some more. The main difference between SHA-256 and SHA-512 is the target CPU. SHA-256 is designed for 32-bit CPUs and SHA-512 is designed for 64-bit CPUs. That makes a ...

13

secp256k1 fails the following SafeCurves criteria, but it doesn't matter for Bitcoin's use of secp256k1: CM field discriminant. secp256k1 is a Koblitz curve that admits a fast endomorphism for speeding up scalar multiplications. There is no particular vulnerability here: the same speedup you get in computing with secp256k1, an adversary gets in trying to ...

12

Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers. Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad). Symmetric encryption is ...

12

Strictly speaking, hashing twice might actually increase the chances of a collision. If there is a hash collision of two outputs of the hash function then any string that has that colliding hash will be a new collision. Actually, it's easier to give an example: For a terrible hypothetical hash function F... F("Alice") -> "aaa" F("Bob") -> "bbb" F("...

12

If any filtering criterion on the output of SHA-256 (with its definition independent of SHA-256 internals) leaves $n$ possible values out of $2^{256}$, then as far as we know, the best method to exhibit an input to SHA-256 matching that criterion involves trying distinct inputs; the expected number of hashes (compressions) required for this is $2^{256}/n$; ...

11

Cryptography (and real security in general) offer quantitative analysis of the security provided - Meaning, real security products will describe how long they will resist a certain class of attack. With cryptography, we select our parameters such that the time required to perform the best attack would exceed the amount considered to be practical, realistic,...

10

Uniformity is a tricky one. SHA-256 (as well as SHA-3 for that matter) follows a heuristic approach. That is, the design is not based on a hardness assumption (for example, the factoring or discrete-log assumption) but on criteria that have only been verified empirically. As such, also the study of uniformity is an empirical study. The development of SHA-1/...

8

This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets. By Kerckhoffs's principle, you should assume that the adversary already knows the algorithm, and the only thing unknown are the secret keys – in your case, the passphrases. Therefore, the adversary by definition knows that you ...

8

The major issue will be size difference. The size of ECDSA in bitcoin is much less than the Lamport Signature. For ECDSA in bitcoin The public key is only 33 Bytes (1 byte for prefix, and 32 bytes for 256-bit integer x) Signature is at maximum 73 bytes Whereas in Lamport Signature The public key is 512 numbers of 256-bit (total of 16KB) The Signature ...

8

Assume that there are $2^{50}$ keys out there. Then calculating one of these keys by chance is $2^{50} \over 2^{255}$ for each calculation or a chance of one in $2^{205}$. Now say that you generate $2^{64}$ keys then you'd still only have a chance of one out of $2^{91}$ of hitting the right key. Note that making sure that you hit a key would however require ...

7

Here's a good amount of hard data on a variety of curves, well-analysed and the findings summarised in a readable way: http://safecurves.cr.yp.to/ The article linked from this answer is not nearly up to the same standard of analysis and, I would argue, deceptive, whether maliciously (v. unlikely) or just due to lack of understanding of basic research ...

7

TL;DR: there is no mathematical certainty that every output value of common cryptographic hash functions is reachable, but for most that's overwhelmingly likely. A notable exception is double-SHA-256 (SHA256d) used in Bitcoin mining, where overwhelmingly likely there are some unreachable outputs. For an idealized 256-bit hash, it becomes likely that every ...

7

Short answer: Because the public key is derived from the private key. Recall that when we are working with elliptic curves, we rely on the elliptic curve discrete logarithm problem (ECDLP). That is that we assume that if we have: $$Q = [k]P$$ given the points $P, Q$ on our elliptic curve, it is hard to compute the scalar $k$. Bitcoin uses ECDSA over ...

7

Yes, it is possible to do this. You can just try each and every PIN, decrypt and then verify the private key; i.e. try a brute force approach. If you don't know the format, the toughest thing will be to think of a way to verify that the result is indeed the private key. With 6 digits there is a maximum of $10^6$, i.e. a million times SHA-256, SHA-256 and ...

7

Comparing double sha256 to sha512 is like comparing apples to oranges. For one, the result of sha512 is 512 bits in length. The result of double sha256 (or triple sha256, or quadruple sha256, for that matter) is 256 bits in length. There has been a lot of conjecture over the years as to why the creator of bitcoin chose to use double sha256 in the protocol. ...

6

Designing such signature schemes from scratch without having strong experience is very likely to fail and very dangerous (see the tons of bad papers out there being accepted to "dubious" conferences and journals). Your proposed scheme Your verification relation is to check if: $sP - Q + R \stackrel{?}{=} zP + mP$ where $Q$ is the public key of the signer ...

6

The access codes were recently leaked (by whom, I don't know). My Yubikey is listed and I can confirm that the access codes were necessary and sufficient to reprogram it. You can change or remove the access code as part of reprogramming too. The leak doesn't make the Yubikeys useless in the extremely unlikely event of Gox rising from the flames — no ...

6

In ECDSA, the message is never encoded as a point in the elliptic curve. Signing in ECDSA loosely works like this: \begin{align*} k &= \text{random}(0, n) \\ (x, \_) &= k \cdot G \\ r &= x \bmod n \\ s &= k^{-1}(H(m) + r \alpha) \bmod n \end{align*} $r$ and $s$ are the signature, and as you can see $H(m)$ is only ever used as an ...

6

I write here a partial answer to my own question (but it is only partial, feel free to write an answer of your own). In the book "Introduction to Cryptography with Coding Theory" (2nd edition), by Wadde Trappe and Lawrence C. Washington, chapter 11, Digital Cash, p.288, we can find the following list of properties coined by T. Okamoto and K. Ohta: The ...

6

Doesn't this mean we could attempt to brute force a private key by using: $$\mathit{privKey} = \mathit{pubKey}/G$$ for all potential values of $G$? There seems to be a misunderstanding here: $\mathit{pubKey}$ and $G$ are fixed and publicly known, so there's nothing left to brute-force. The operation of "dividing" $\mathit{pubKey}$ by $G$ is (to the best ...

6

No, in textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$, there is no method to deduce $\operatorname{Sig}(15)$ from $\operatorname{Sig}(5)$ and $\operatorname{Sig}(10)$. It is possible to deduce $\operatorname{Sig}(50)$, by using the general fact that in textbook RSA signature, if $x$ and $y$ are positive integers (with $xy$ below the limit ...

6

Half-extended binary GCD The extended binary GCD of the HAC's algorithm 14.61 mentioned in the question, when given positive integers $x$ and $y$ , computes integers $a$ , $b$ , $v$ with $ax+by=v=\gcd(x,y)$ . When $v=1$, it follows that $a$ is the multiplicative inverse of $x$ . In our context, $0<x<y$, $y$ odd, $\gcd(x,y)=1$ (the last two conditions ...

5

Is this (cryptographically) secure? That is hard to say without knowing the exact details of the bitcoin protocol (which I would like to understand better, but don't have the time at the moment). Looking at the document you linked to, the public child key is created as $\text{HMAC-SHA512}(Key = c_{par}, Data = ser_P(K_{par}) || ser_{32}(i))$. This value ...

5

I will assume you mean the nonce that bitcoin miners iterate. Depending on e.g. wallet software other salts or nonces may be involved. That nonce is only used once, because every miner1 will be hashing a different transaction block (hash) – one which sends the reward for solving the proof of work to their address. A miner could reuse a nonce but they would ...

Only top voted, non community-wiki answers of a minimum length are eligible