It seems it's too much to ask experts to spend a few minutes to explain something. I'm not pretending to be a genius, I'm not in the encryption field, I'm just trying to get an answer that makes sense. I hope my explanation clears things up a bit. If not, feel free to ask questions. I did intend my reply to explain more than it chastises; though forgive me if any parts of it come off as chastising. You probably shouldn't take the replies here as a good measure of this community. The reason why, is that cryptography is hard, and it is very often that cryptographers and related engineers see developers come along thinking that they know better, but end up implementing something horrifying. Since this is so common, the natural reaction to anyone cooking their own encryption is to, as you put it, bash them with clubs. Sure, it's not ideal, but it's understandable. Anyone with a modicum of knowledge in the field grows quickly jaded by all the horrific pseudo-crypto in the world. |
|
|
|
Forgive me if this has already been mentioned. The method described is, roughly, what existing encryption schemes do. They are nothing more than scramblers. Modern encryption schemes like AES evolved from older methods like the Enigma machine. That evolved from ancient encryption like the Caesar cipher. A Caesar Cipher is where you take each letter of the message, and count some number of letters further down the alphabet. For example, A becomes B, B becomes C, Z becomes A. The word DOG becomes EPH, if shifting by 1 letter. As can be seen, this forms a simple mapping from one alphabet to another. AES also maps from one alphabet to another. Except with AES, the alphabet is very large (2^128), and the way that it maps from one alphabet to the other is so complex that, without the key, no one can figure it out. Each key in AES creates a different mapping. Wrapping back around to the method described in the OP, we can see that if you took the sum total of all the steps, what you're ultimately doing is mapping from one alphabet to another. Given a certain sequence of steps, we can map from a private key to a scrambled key. We have an alphabet of private keys, an alphabet of scrambled keys, and the sequence of steps describes the mapping between the two. As the OP mentioned, one can encode the sequence of steps as a list of words/numbers. This list of words/numbers describing the steps to take is the key (i.e. the password). Therefore, this is not fundamentally different than AES or any other modern encryption scheme. As to whether the method should be used, I would strongly suggest no. This is because AES is well studied by the best minds mankind has to offer. We know with high confidence that it is secure. It is also specifically designed to resist all known crypt-analytic attacks. The method described in the OP is more akin to the Enigma Machine, which was completely demolished by early crypt-analytic attacks developed by people like Alan Turing. If what you want is "security through obscurity", use the well studied methods for doing so. Steganography is a great example. Encrypt your data with world class encryption schemes like AES, and then use steganography to hide it somewhere. This is well studied as well, and if someone feels that obscurity adds an extra level of protection, that is the way to do it. EDIT: Spelling; thanks Meni! |
|
|
|
Here's another interesting data point. If we search all primes of the form 2**256 - 2**32 - t, starting from t = 0 to t = infinity, the first prime order curve with a = 0 and b < 1000 is the secp256k1 curve. Code: from sage.all import *
def find_group (prime):
K = FiniteField (prime)
for b in xrange (1, 1000):
E = EllipticCurve (K, [0, b])
if E.order () in Primes ():
return b, E.order ()
return None
p = 2**256 - 2**32 + 1
while True:
p -= 1
if not p in Primes ():
continue
result = find_group (p)
if result is not None:
break
print "Found curve: "
print "p = %X" % p
print "a = 0"
print "b = %d" % result[0]
print "N = %X" % result[1]
That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10). |
|
|
|
I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10). An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful. I've implemented a secp256k1 specific reduction algorithm before ( link to source), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively. Nor do I understand why they chose the smallest p, and not the largest. Perhaps that particular p allowed a small (a,b) for the curve? I recall there being better (less code required) Mersenne-like primes to choose. |
|
|
|
|
Keep up the great work, BitCentury!
|
|
|
|
That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order. Well, you put in the work to check p for us, so here's my contribution: secp256k1_parameter_proof.pyfrom sage.all import *
# Find the smallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024.
def find_prime ():
for t in xrange (1023, -1, -1):
p = 2**256 - 2**32 - t
if p in Primes ():
return p
return None
# Find the smallest b, where b results in an elliptic curve of prime order, of the form y^2 = x^3 + a*x + b.
# p specifies the modulus of the underlying finite field.
def find_elliptic_curve (p, a, max_b):
K = FiniteField (p)
for b in xrange (max_b + 1):
if a == 0 and b == 0:
continue
E = EllipticCurve ([K (a), K (b)])
order = E.order ()
if order in Primes ():
return b
return None
p = find_prime ()
# Searches all combinations of a and b, where a and b < 7, until a prime order group is found.
for a in xrange (7, -1, -1):
print "Testing", a
b = find_elliptic_curve (p, a, 7)
if b is not None:
break
print ""
print "p = 0x%064X" % p
print "a = %d" % a
print "b = %d" % b
print "N = 0x%064X" % EllipticCurve (FiniteField (p), [0, b]).order ()
print ""
This requires sagemath, and can be executed by running "sage -python secp256k1_parameter_proof.py" Here is my output: Testing 7
Testing 6
Testing 5
Testing 4
Testing 3
Testing 2
Testing 1
Testing 0
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
real 3m1.191s
user 3m0.716s
sys 0m0.148s
I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7. So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice. |
|
|
|
and specifically about these five constants: They've already been explained in this thread. In summary: The first constant we care about is p; TierNolan already explained that one. It's the largestsmallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024From that we can explain b. If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one. I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless. N is just the order of the elliptic curve; no explanation needed. The last piece of the puzzle is the choice for G. Since the order of the elliptic curve is prime, we can pick any point on the curve (except infinity), and get a group with the same order (i.e. there are no subgroups). Why SECG picked the particular G they did is unexplained. However, there is no reason to believe any G is weaker or stronger than any other G (against a compliant ECDSA verifier). I would guess that either G is totally random, or it has sentimental meaning to the author(s). Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1? |
|
|
|
Thanks for all the hard work, BitCentury crew! 3. We have packed 1 unit for shipping so far, and plan to still ship 2 units later today. * fpgaminer crosses fingers. |
|
|
|
I've tried fixing things myself, but I'm not even sure what to use as a reference anymore. You get to choose what to use as a reference. In my personal opinion, the Bitcoin protocol and Satoshi client should be used as the reference. That seems like a sane choice. Variable length integer is defined here: https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integerSome of the discrepancies you have found are due to endian mis-matches. The Bitcoin Protocol uses little endian in its Variable length integers. Brainwallet gets it wrong and uses big endian encoding. Go ahead, sign a long (>=253 bytes) using Brainwallet, and then try to verify it in Bitcoin-QT. The PHP code you posted looks to have it correct. Your byte order is wrong in the 16 and 32 bit words. Try Cn and CN. If we're using Bitcoin-QT/d and the associated protocol as the reference, then no, Cv is correct. |
|
|
|
There you go: Oh, thank you. Guess I got too excited and didn't read the whole thing.  |
|
|
|
|
Man this is moving fast! Great work, BitCentury!
Any estimates on when units will start shipping out?
|
|
|
|
Awesome news! We picked up ALL units late this evening, or should I say morning. It's 3:30 AM Thu Moscow time, Woohoo! |
|
|
|
I like this Timur guy. Give him a high five for me! So customers in the USA, unless you have specifically modified your power panels to support 230V outlets (not something that is ever done by default), do NOT plug in and use the shipped power supplies as it may cause major problems or even be dangerous, you will have to source your own 110V power supplies that should be readily available at most computer retail or online stores. Feel free to leave the PSU out of my order, to save on shipping and customs issues. but I hope as a community we can share some info with each other. Heck, I'll record a short documentary. Some nice footage of the miner in its natural habitat, hunting wild Bitcoins amongst the trees. |
|
|
|
Have I mentioned that these frequent updates are great? By the way, have you seen http://bitfury.metabank.ru/?p=37? Shows a couple of points to check for shorts, assuming you have a multimeter handy. Overall, this definitely looks like something that came out of a workshop, rather than any kind of professional fabrication. I don't care if it looks like a purple dinosaur, as long as it hashes when it gets here |
|
|
|
But bare single SHA-2 can accept as input an infinite set, right? I see that mentioned a lot around these parts. To be really strict about it, SHA-2's input set is finite, because it uses a Merkle–Damgård construction. In other words, before a message is chucked into SHA-2's meat grinder, it's padded and the message length (in bits) is appended as a 64-bit big endian integer. If I remember MD compliance correctly, this forces the message length to be less than 2^64 bits in length (~2.3 exabytes). So ... technically finite, but only Google would care. don't know about PBKDF2 to be honest, but at least SHA256^2 has then the same order You're right, those are good points about the properties if the model were a bijection. Regarding PBKDF2, you'd get an order ~63% the size of the input set. You get the same result when XORing random integers. e.g. if you XOR 256 random integers, each within the range [0, 255], you can expect to see only ~161 unique outputs on average. |
|
|
|
Programmer Adventures in Modelling and Simulating Hash FunctionsI've been curious about the properties of hash functions lately. I had three questions, that I attempted to answer: - What is the order of SHA-2 (x)?
- What is the order of SHA-2 (SHA-2 (x))?
- What is the order of PBKDF2 (x)?
For this research, I define order to mean the size of the output set of the given function (in other words, how many unique outputs there are). Ideally, this would be 2^256 for SHA-256. If the cost of executing the function is considered to be one operation, than the complexity of finding a collision is directly related to the order of the function. When the input set is small, finding the order of a given function is easy. Just run all possible inputs through the function, and count the number of unique results. Unfortunately, the input set of SHA-256 is impossibly large (though technically finite). Since I'm a programmer by nature, I chose to answer the above questions by modelling and simulating. The model I use is a random oracle. These represent perfect hash functions; they are impossible to invert except through brute-force. For small input sizes, one can generate a random oracle easily. It's just a random LUT! To answer the first question using this model, we need to know the expected order of a random oracle. This is equal to the average of all possible random oracles (for a given input size). Again, we run into a problem, because the set of possible random oracles is too large. So, instead, I estimate the expected order by generating a suitably large number of random oracles and averaging their orders. To answer the last two questions, we do the same, but apply the random oracle in the specified construct. e.g. Oracle (Oracle (x)). With enough samples, we should hopefully get good estimates for the expected orders and thus have answers to my questions. The Python code for all of this is listed at the bottom of this post. In the meantime... ResultsTesting 8 bits
Oracle: 162.212890625
Exponential: 19.470703125
Chained: 120.920898438
Testing 12 bits
Oracle: 2589.109375
Exponential: 95.3359375
Chained: 1920.23925781
Testing 16 bits
Oracle: 41426.6992188
Exponential: 1278.45996094
Chained: 30704.7412109
Testing 17 bits
Oracle: 82854.8759766
Exponential: 2516.46582031
Chained: 61408.5410156
Testing 18 bits
Oracle: 165699.530273
Exponential: 5046.56347656
Chained: 122825.053711
Testing 19 bits
Oracle: 331412.545898
Exponential: 10073.0644531
Chained: 245653.294922
Testing X bits means running the simulations with an input set of size 2 ^ X. Oracle is just the plain random oracle model. Exponential is 101 iterations of a random oracle iteratively applied (e.g. Oracle (Oracle (x)), but with 101 Oracles). Chained is similar to PBKDF2 (password and salt combined, no HMAC). The results are certainly interesting. Over all the tested input sizes, we see consistently that the estimated expected order of a hash function is only 63% of the input set. In other words, based on these models, one would expect the order of SHA-256 to be ~2^255.3. Pretty good! On the other hand, SHA-256 in an Exponential construct is weaker, resulting in an order of ~2^250.3. SHA-256 in PBKDF2 would be ~2^254.9. None of this is particularly surprising, but it's educational to have some concrete numbers. Of particular interest is the result for the Exponential construct. Some have conjectured that double SHA-2 is weaker than regular SHA-2. While this seems to be strictly true, the weakness is nowhere near significant. After 100 iterations of SHA-2, one would expect to see the output space cut down to 1% of its usual size. But 1% of 2^256 is still impossibly massive and impossible to search. If we factor in increased computational complexity, searching the space is still more expensive than single SHA-2. (NOTE: Doubling hash functions can have other benefits, too. e.g. HMAC_SHA1 should remain strong in spite of SHA1's weaknesses) Chained (pseudo-PBKDF2) is interesting too. At its core it uses the hash function recursively like Exponential does, so seemingly the larger your iteration parameter for PBKDF2 is, the less pseudo entropy you're injecting into the system. But the expected order is still quite large, and of course computational complexity grows drastically. Perhaps all of this could have been easily proven using modern algebra, but I'm a better programmer than I am a mathematician. So to all those crypto-interested programmers out there, I hope this has been useful. The Codeimport random
import os
# If True, causes the PRNG to be reseeded with entropy often.
EXTRA_RANDOM = True
# Represents an instance of a PseudoRandom Function
class PRF (object):
def __init__ (self, func, input_bits):
self.input_bits = input_bits
self.func = func
# Calculates the size of the output set
def output_order (self):
outputs = set ()
for x in xrange (2 ** self.input_bits):
y = self.func (x)
outputs.add (y)
return len (outputs)
# Estimates the size of the output set
def estimate_output_order (self, num_samples=2**16):
num_samples = min (num_samples, 2 ** self.input_bits)
inputs = random.sample (xrange (2 ** self.input_bits), num_samples)
outputs = set ()
for x in inputs:
y = self.func (x)
outputs.add (y)
return len (outputs) * (2 ** self.input_bits) / num_samples
# A real random oracle generator
class RandomOracle (object):
def __init__ (self, input_bits):
self.input_bits = input_bits
def generate (self):
if EXTRA_RANDOM:
random.seed (os.urandom (32))
permutation = [random.randrange (2 ** self.input_bits) for i in xrange (2 ** self.input_bits)]
def model (x):
return permutation[x]
return PRF (model, self.input_bits)
# Generates exponential versions of the given PRF generator.
# i.e. y = PRF (PRF (PRF (x)))
class ExponentialPRF (object):
def __init__ (self, prf, iterations):
self.prf = prf
self.iterations = iterations
def generate (self):
prf = self.prf.generate ()
def model (x):
U = x
for i in xrange (self.iterations):
U = prf.func (U)
return U
return PRF (model, prf.input_bits)
# Generates chained versions of the given PRF generator.
# i.e. y = PRF (x) ^ PRF (PRF (x)) ^ PRF (PRF (PRF (x))) ^ ...
class ChainedPRF (object):
def __init__ (self, prf, iterations):
self.prf = prf
self.iterations = iterations
def generate (self):
prf = self.prf.generate ()
def model (x):
U = x
T = 0
for i in xrange (self.iterations):
U = prf.func (U)
T = T ^ U
return T
return PRF (model, prf.input_bits)
# Given a PRF generator, estimates the expected size of the output set.
def estimate_family_order (generator, num_samples=1024):
total = 0
for i in xrange (num_samples):
prf = generator.generate ()
total += prf.output_order ()
return total / float (num_samples)
# Some tests
for bits in [8, 12, 16, 17, 18, 19, 20, 21, 22, 23, 24]:
print "Testing %d bits" % bits
oracle = RandomOracle (bits)
exponential = ExponentialPRF (oracle, 101)
chained = ChainedPRF (oracle, 101)
print "Oracle: ", estimate_family_order (oracle)
print "Exponential: ", estimate_family_order (exponential)
print "Chained: ", estimate_family_order (chained)
print ""
Recursively applying hash functions like SHA-2 insignificantly weakens the function, if one ignores computational complexity. Blah, blah, blah, programming is fun and cryptography is awesome.
|
|
|
|
|
Very cool to Pywallet getting some much needed spring cleaning. Besides its obvious uses, I've found it to be a useful reference for understanding how bitcoind uses BDB, quickly bringing up some ECDSA math in Python, etc.
Keep it up!
|
|
|
|
I believe the order #E(Fp) of our elliptic curve n is prime and is in fact their n.
I think this is also validated by the fact that h = 1. To be specific, n in BurtW's quote is any prime number that divides the order of the elliptic group. In our case, the order of the secp256k1 group is prime, which means n can only be the order of the elliptic group (convenient!). Given that our elliptic group is of prime order, we know a few things. There are no subgroups. It's cyclic. It's abelian. To the best of my knowledge, that also implies that we can pick any element of the group, except the identity element, to be our generator. Which makes me wonder how secp256k1's generator was picked. I don't yet know what restrictions one must apply to the generator. I can only assume it doesn't matter ... By the way, I ran a little experiment. Given our finite field, and setting a to 0, 7 is the first (counting from 0) value for b that results in a prime order elliptic group. I don't understand GLV well enough to know what restrictions it places on a and b, but if we have to pick a curve where a is 0, it seems like b being 7 would be a logical choice (again, given our finite field). |
|
|
|
Using my own implementation of RFC 6979 on top of warner's ECDSA code, I generated a few test vectors. slush's patch matches up perfectly! For future reference, here are the test vectors: # Test Vectors for RFC 6979 ECDSA, secp256k1, SHA-256
# (private key, message, expected k, expected signature)
test_vectors = [
(0x1, "Satoshi Nakamoto", 0x8F8A276C19F4149656B280621E358CCE24F5F52542772691EE69063B74F15D15, "934b1ea10a4b3c1757e2b0c017d0b6143ce3c9a7e6a4a49860d7a6ab210ee3d8dbbd3162d46e9f9bef7feb87c16dc13b4f6568a87f4e83f728e2443ba586675c"),
(0x1, "All those moments will be lost in time, like tears in rain. Time to die...", 0x38AA22D72376B4DBC472E06C3BA403EE0A394DA63FC58D88686C611ABA98D6B3, "8600dbd41e348fe5c9465ab92d23e3db8b98b873beecd930736488696438cb6bab8019bbd8b6924cc4099fe625340ffb1eaac34bf4477daa39d0835429094520"),
(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140, "Satoshi Nakamoto", 0x33A19B60E25FB6F4435AF53A3D42D493644827367E6453928554F43E49AA6F90, "fd567d121db66e382991534ada77a6bd3106f0a1098c231e47993447cd6af2d094c632f14e4379fc1ea610a3df5a375152549736425ee17cebe10abbc2a2826c"),
(0xf8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181, "Alan Turing", 0x525A82B70E67874398067543FD84C83D30C175FDC45FDEEE082FE13B1D7CFDF1, "7063ae83e7f62bbb171798131b4a0564b956930092b33b07b395615d9ec7e15ca72033e1ff5ca1ea8d0c99001cb45f0272d3be7525d3049c0d9e98dc7582b857")
]
|
|
|
|
The ability to flashing the firmware is an attack vector, as is the existence of firmware in the first place. Flashing firmware is not an attack vector, if the firmware is signed by a trusted party. An ASIC would be far worse; there are no ways for third parties to truly audit the ASIC. Open source code, on the other hand, can be audited by a large swath of programmers. with specific attention payed to avoiding information leaks that could lead to a successful side channel attack. What side channel attacks are you specifically worried about on a hardware wallet? The only opportunity for a hardware wallet to leak secret information through a side channel is during signing. When the hardware wallet is secured by a password, this will only occur when the user is using the device for signing legitimate transactions. This will occur infrequently, to put it lightly. Power and timing side channel attacks require huge sample sizes, relative to the number of transactions a user will ever have signed. Not to mention that it's impossible for the host to time the actual signing, unless it's correlating with power consumption and I don't believe a PC can extract that information from their USB host chips. |
|
|
|
|
Show Posts
