Another case of "Hey, I have an idea" but someone already invented it 30 years ago.  That will be true in general. The key is that, while the idea is important, the implementation of the idea is more meaningful. For example, idea of capacitive touch screens was invented over forty years ago, but it wasn't until recently that they become good enough to be used ubiquitously. A better example, Bitcoin. Cryptomoney has been around for quite awhile as well, but it was never implemented as successfully as Bitcoin (having a blockchain being the breakthrough). I understand that HMAC would be better, but what's wrong with using the regular hash? Sorry for the terse response, I was in a rush at the time. Let's create a more general example, so I can better demonstrate why using SHA256 as a MAC is insecure. This is going to be a long one, but by your request I wrote it out long-wise to be educational. Suppose you have a chatroom server, and it receives messages from clients. The clients send along their username, and message. You want to ensure the messages actually belong to the given username. If you didn't, users could impersonate one another. So you establish a shared secret, unique to each user, and give it to each user when they register. Now, when clients send a message, they send their username, message, and a MAC. MAC is calculated like so: mac = SHA256 (secret + message) On the server side, the server can lookup the secret for the specified username, calculate what the MAC would be for the given message, and compare the calculated MAC to the one given by the client. If they match, all is well. Seems reasonable. Given that SHA256 is a one-way function, how could anyone forge a MAC? Well ... Suppose a client, named Alice, sends the message "Hello" to the server. Mallory, an attacker, intercepts this message and its MAC. Now Mallory can use this information to impersonate Alice. Recall the SHA256 algorithm: def sha256 (message):
data = pre_processing (message) # Does a specific kind of padding to bring the data length to a multiple of 512-bits
blocks = split (message) # Split into 512-bit blocks
state = initial_state # Specified by SHA-2 standard
for block in blocks:
state = process_block (state, block)
return state
For the message "Hello", Alice would call sha256 ("password" + "Hello") to calculate the MAC. The data given to SHA256 is 104 bits long. So the code boils down to this: mac = process_block (initial_state, "password" + "Hello" + 408_bits_of_padding)
The server would do the same thing, and verify the message's owner. How about Mallory? Mallory doesn't know "password", but he does know "Hello", he knows the MAC Alice calculated, and suppose he knows the length of "password" (it could be a fixed length key, like in TOTP). So, time for a fun trick! state = mac
new_mac = process_block (state, ". I'm stupid" + 416_bits_of_padding)
new_message = "Hello" + 408_bits_of_padding + ". I'm stupid"
Now, Mallory sends new_message and new_mac to the server. What will the server do? sha256 ("password" + new_message). Let's follow how it will execute the SHA256 algorithm: data = pre_processing ("password" + new_message)
blocks = split (data)
state = initial_state
for block in blocks:
state = process_block (state, block)
if state == new_mac:
return True
return False
We know ("password" + new_message) is 608 bits long, thus requiring 416 bits of padding, so we can simplify the code: data = "password" + new_message + 416_bits_of_padding
blocks = split (data) # Will be two blocks
state = process_block (initial_state, blocks[0])
state = process_block (state, blocks[1])
if state == new_mac:
return True
return False
Perhaps things are beginning to look suspicious, but let's keep going, given that we know what new_message is, and given that split just splits along 512-bit boundaries: blocks[0] = "password" + "Hello" + 408_bits_of_padding
blocks[1] = ". I'm stupid" + 416_bits_of_padding
state = process_block (initial_state, blocks[0])
state = process_block (state, blocks[1])
...
Uh oh ... look back a bit and look at how Alice calculated mac. "mac = process_block (initial_state, "password" + "Hello" + 408_bits_of_padding)". See how the data passed to process_block in Alice's calculation is equal to blocks[0] in the server-side calculation on Mallory's message? state = process_block (initial_state, "password" + "Hello" + 408_bits_of_padding)
state = process_block (state, blocks[1])
...
So, the first state the server calculates is equal to the mac that Alice sent awhile ago. The same mac Mallory intercepted and used in this attack. So we simplify the server-side code again: state = process_block (mac, ". I'm stupid" + 416_bits_of_padding)
...
Which, if you look back again, you'll see is equal to the calculation that Mallory performed. Oh dear ... Therefore, the server calculates the same MAC that Mallory sent for his manipulated message. Therefore, the server accepts the message, and makes the world think that Alice is stupid.  As you can see, using SHA256 as a MAC function leaves one vulnerable to a message extension attack. As you can also see, the message extension attack has a certain form: Mallory must always first append padding to his manipulated message, before tacking on his desired extra data. So, Mallory can't send any arbitrary message. That means this attack isn't always viable. In your case, for TOTP, it probably can't be used. That said, I still wouldn't use SHA256 in a TOTP implementation. It's bad practice and asking for trouble. Also, if I recall correctly, the HMAC construct has been shown to strengthen the underlying hash function. For example, I think HMAC-SHA1 is not vulnerable to the same attacks that SHA1 has fallen prey to in recent years (SHA1 has been "broken"; as of 2012 it costs ~$3 million to break a SHA1 hash). One of the golden rules in cryptography is to use an algorithm only for its intended purpose, never anywhere else without extensive research and vetting. If you use sledgehammer to put a nail into a wall, it'll probably work, but more often than not you'll find yourself with a much bigger problem than a nail in the wall... Looking for a good book? Cryptography for Developers. Ain't no developer got time for a cryptography degree. |
|
|
|
I wrote one of the Java implementations that is also listed on the BIP page. If this is the one you refer to, then please elaborate on the bugs. Yes, I was referring to the one linked from the BIP 0032 wiki page. I only took a quick glance over it, to double check my understanding of BIP 0032. More likely than not the things I noticed at a glance were either misunderstandings on my part, or pedantic bugs. I'll do a proper code audit in a day or two and let you know if I find anything. One thing I've heard a bit about is BIP "0032.5" - could you comment on the motivations for this and what the key differences with BIP 0032 are - or maybe point me to a draft version of this that I can read? Thanks! I have a discussion thread on the RFC that BIP is based on: https://bitcointalk.org/index.php?topic=285142.0Check gmaxwell's first reply for a link to his proposal for BIP 0032.5. I don't think there's a draft BIP yet. I'm disappointed that this is the first time I've heard your complaints. It has now been independently implemented by at least four parties. Your feedback sounds good though, do you have any proposed revised text? (And indeed, your understanding is correct). By the way, don't take my post as harsh criticism. As I alluded to, I like the idea, and I appreciate the efforts of those who researched and developed it. My comments merely reflect the trouble I had with it on a first time read through. I did a second read last night, and still think the wording could be greatly improved. There are a lot of overloaded words which make it difficult to read. When I get a chance I'll sit down and see if I can come up with alterations which may help make the document clearer. Here's an example of what I mean by overloaded words. Using the verbiage of BIP 0032 in its current state, I could write the following declaration: "The private child key derivation function can be used for both public and private derivation of public and private extended keys." Pretty confusing, eh? |
|
|
|
Beginner's Guide to TOTPIn fact, you can even use a regular hash function without HMAC, just by concatenating the two values. Do not do that.
|
|
|
|
Could you describe a specific use case? i'm having a hard time imaging what the hmac_sha512 of a blockhash could be used for. Since I think the nonce is fairly random Are you referring to the nonce in the block header? If so, it's not necessarily random (it's possible to mine with nonce set to a constant, for example), and it's certainly quite biased. |
|
|
|
Thank you for the update, digitalmagus. I'm fine with the no-refund policy; expected no different. I'm still excited the get the units. as of yesterday estimated to be somewhere around a total of 29 As in, they're shipping 29 units per day so far? That's not bad at all. Any estimate, based on that figure, of when our units might be ready for pick-up? By the way, there has been a few technical updates on their blog here. Nothing significant from what I saw. |
|
|
|
|
I think it's silly for ckolivas not to have a working and complete Avalon, especially when the the 703N's are so cheap. You never know when it might come in handy later.
If Bogart or someone else sends him one, preferably already modded (to save ckolivas the hassle), I'll comp the cost and shipping. Just let me know.
|
|
|
|
|
On a related note, I thought about a partial solution to this problem of weak password based private keys. My specific use case was deriving the seed for a deterministic wallet from a password on a hardware wallet. Though, it could certainly be applied elsewhere. (NOTE: I don't plan to implement this without further thought and experimentation.)
Ask the user for their full name, DOB, and/or any other personal information. Concat with their password. Chuck into an unusually expensive KDF, one that could take minutes or more to run. Save the seed in protected flash on the hardware wallet (inaccessible to the outside world). Feel free to encrypt that seed with a wallet pin/password (use the usual second long KDF here), if the user desires (for extra protection, and to prevent physical theft of the wallet).
Benefits: This adds extra entropy that the user already has and can easily remember. Some information may be difficult for an attacker to acquire (Social Security number, driver's license number, etc). It mimics existing security restrictions present in the banking system and elsewhere. By storing the derived seed (securely), the user only needs to enter this information once. Since this process occurs infrequently we can use a very expensive KDF to make brute forcing painful. The personal information also helps to make the derived seed unique to each user, even if two users choose the same (stupid) password.
It should be great at mitigating the kind of drive-by thefts demonstrated in this thread. But, if an attacker has access to some or all of the personal information, then we're back to depending on the user's password choice and the strength of the KDF. In extreme cases, one could set-up the KDF to take a day. Again, this happens infrequently for the user (certainly 24 hours is significantly better than the turn-around on a stolen credit card, for example). But, it would make attackers squirm. The top 10,000 passwords would take 10,000 CPU-days of effort (now imagine the attacker doesn't know the name of your first dog...).
|
|
|
|
(mod n) is typical notion, and it implies that all the arithmetic in the preceding equation is modulo n. So the wiki is correct. ( Look at the ECDSA wiki article for great examples.) I don't think that particular part of the wiki should be changed to make it more clear for those unfamiliar with crypto. I would argue that if one is unfamiliar with crypto, one should not implement HD wallets (at least in production; for fun, sure). I would, however, argue for better reference implementations (code is gospel). I found the Python one rather confusing. The Java one isn't bad, but it suffered from a few bugs at first glance. On a related note, I found the wiki confusing for other reasons. "Private derivation" uses a node's private key. If a second party is given only the public key for a node, they can't calculate that particular leaf. So, later in the article, how is the use case "Audit: M" possible? Since the wiki never explains "private derivation" beyond giving the algorithm, I can only make assumptions. My assumption is that it is a means of creating a branch in the tree that can be given to a second party, but from which that party cannot derive the proceeding tree. Backtracking resistance, in other words. Well ... that's useful. It means that, in the canonical wallet structure, compromises of one account do not endanger other accounts. But this is never explained, so I can only make assumptions. As the developer for the Titan hardware wallet project, BIP 0032 is relevant to me. But I was put off from it because of its current opaqueness. It's good in theory, but not well documented in my opinion. I'll probably revisit and implement it later. |
|
|
|
But, given y, how can we get x? In particular does someone know a solution to x^3+7 = 0 on the secp256k1 curve? Well, it's just a finite field, so this should work: x = modular_cube_root ((y^2 - 7) % p, p) I used the code listed here to solve your particular example. It returns None, so probably there isn't an x that solves the equation when y is 0. |
|
|
|
Wonderful and insightful comments, gmaxwell; thank you. but in a hardware wallet implementation this is impossible If the hardware is known, and it is running open source firmware, what concerns would there be? Also, malicious firmware doesn't need to leak information through signatures to enable an attack vector. It could be using a DRBG to select the private keys, seeded from a secret known to the attacker and a device specific id. This would enable the attacker to calculate potential private keys and search the blockchain. To an outside observer, the private keys would look random as usual. (This is the same worry people have about the RdRand instruction) it would sure be better if the device could be put in a mode which would make its behavior completely reproducible externally Perhaps deterministic signatures could be a user configurable option, allowing expert users to "pick their poison". |
|
|
|
Yup, that seems to resonate well with my conclusions. Thank you for the link. I just finished coding an HMAC_DRBG implementation in Python and threw it up on github, as a nice reference. I'll follow that up with an implementation of RFC 6979 in Python, to play around with. Personally, I'm leaning towards an implementation of RFC 6979, with an extra switch in the API to enable the usage of additional entropy. The switch could default on, thus avoiding concerns over leaking information about the private key. During unit or continuous tests, though, it could be switched off to verify conformance to RFC 6979, and switched back on to verify non-conformance (and thus confirm that entropy is being added). |
|
|
|
2) Given a public key, you can calculate the address. Check this wiki page for instructions on how addresses are calculated from public keys. 1) Well, you can verify that a public key (a point) is on the secp256k1 curve (the elliptic curve used by Bitcoin). That proves that a corresponding private key exists (but you don't know which one). I don't have a reference off the top of my head for you, but Google can probably help. |
|
|
|
Do you know what a shit-barometer is Bubbles? It measures the shit-pressure in the air, listen Bubs you hear that? The sounds of the whispering winds of shit |
|
|
|
I don't think I understand this, there are 400000 chips coming, but NOT for orders from April but for orders made in June or later? What they mean is, they're on schedule to meet the deadlines for all chip orders placed after June 1st. Anything before that, they have already missed the deadline, so they can't meet the deadline. It is not saying that these chips are for any specific orders; just statements about deadlines they're currently trying to meet. |
|
|
|
I noticed the HW rate is higher than the "Accepted" shares. Accepted is a useless statistic here; look at DiffA. Error % = HW * 100.0 / (DiffA + HW) |
|
|
|
|
It begins...
Today I began using the Titan on the live Bitcoin network. From now on it will be my day-to-day wallet, and will serve as a real world test of my device and code. So far ... I love it! It still doesn't have a case, so holding it is a little awkward, but the feeling of empowerment and security, after all the hard work, is rewarding. Here's the first address ever generated by the device for mainnet:
1LQC1bYR9W6YRnux4DnGP7GzBKm7oJuW5y
More to come...
|
|
|
|
Yeah - At block 227930, the previous 1000 contained the supermajority of 950. Very cool  Thank you for taking the time to look that up. |
|
|
|
Chip simply doesn't work on 3gh (this is not necessarily true), and if you take it as 2.7gh [consider its real power] then apparently there wouldn't be enough chips for everyone. Sounds to me like Metabank overestimated the performance of the chips, and thus didn't order enough of them and/or didn't order enough of the right resistors. *shrugs* Oh well. I'm glad they chose to ship as-is; better a slightly underperforming device now, than a proper device some undefined time in the future. Thank you for the update digitalmagus! My excitement shall continue... |
|
|
|
95% rule ("Point of no return"): If 950 of the last 1,000 blocks are version 2 or greater, reject all version 1 blocks. (testnet3: 75 of last 100) Are we here yet on mainnet? |
|
|
|
I've seen this RFC mentioned once or twice on this forum, but could not find any extensive dialog about it. I would like to implement this as part of my hardware wallet, but am hesitant to do so without seeing what others have to think about the approach. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)Summary of RFC 6979ECDSA signature generation uses a number k, which must be randomly and uniformly chosen each time a signature is created. Under deterministic ECDSA, as proposed by RFC 6979, k is chosen deterministically. We start by creating an instance of HMAC-DRBG, with the private key as the source of entropy, and the hash of the message as the nonce. k is generated from the output of this HMAC-DRBG instance. This makes k deterministic, given the message and the private key, but still uniformly distributed and ~impossible for an attacker to guess/calculate. Most importantly, signatures generated this way are compatible with existing ECDSA signature verification implementations. Why make ECDSA deterministic?There are two major reasons to use a deterministic algorithm here. In regular ECDSA, if two signatures are created (different messages) with the same k value, the private key can be calculated. This means that ECDSA immediately fails if k is not chosen randomly. The recent Android mishap led to such a problem. Using deterministic ECDSA avoids this. Secondly, it allows easy verification of ECDSA implementations, using fixed test vectors. Regular ECDSA implementations cannot use signature test vectors, because the signatures are random by design. Thoughts? |
|
|
|
|
Show Posts
