We’re rewarding the question askers & reputations are being recalculated! Read more.
55

SHA-256(SHA-256(x)) was proposed by Ferguson and Schneier in their excellent book "Practical Cryptography" (later updated by Ferguson, Schneier, and Kohno and renamed "Cryptography Engineering") as a way to make SHA-256 invulnerable to "length-extension" attack. They called it "SHA-256d". We started using SHA-256d for everything when we launched the Tahoe-...


51

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.


43

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


28

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


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


17

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


12

I have a list of Bitcoin-related publications here: Bitcoin Bibliography (Crypto & Security) They are all the academic papers (as opposed to whitepapers) that I know about, relating to security or cryptographic aspects (as opposed to economic or implementation aspects) of Bitcoin. Most are published.


12

For a second preimage attack: hash(x) = hash(y) implies hash(hash(x)) = hash(hash(y)) So it wouldn't protect against a direct preimage attack. Bitcoin builds a Merkle tree for a b c like this: hash(hash(hash(a)+hash(b))+hash(hash(c)+hash(c))). You can see again that if someone found a c' that has the same SHA-256 hash as c, they could substitute it and ...


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


12

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


11

Here's the Research article on the Bitcoin wiki: http://en.bitcoin.it/wiki/Research You might find some of the authors in the list have related research that is not directly related to Bitcoin so is absent from that list.


11

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


9

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


7

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


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


6

Yes (to the encrypting part of the titular question). In fact, Bruce Schneier has recommended encrypting using multiple rounds for AES due to attacks (each word a link): Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we're learning is that the safety margin of AES is much less ...


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

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

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


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

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


5

Depends on what you mean by secure. If you merely want the ability to detect and then presumably punish double spending, you can do that in a way that is secure and anonymous: double spending reveals enough information to provably identify the user. Since honest users don't double spend, they are still anonymous. This is used in Camenisch et al.'s Compact E-...


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


5

Short version: the signature is correct, it is a real signature and therefore it is possible to verify it with one's favourite software. The scam is not based on a cryptographic attak but on what is signed. Craig Wright has recovered an old (and real) Satoshi's signature and tried to provide it as a new signature to validate his identity. It's, as someone ...


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