Bitcoin Forum
March 28, 2024, 10:10:30 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 [13]  All
  Print  
Author Topic: [ANNOUNCE] Android key rotation  (Read 66319 times)
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
August 20, 2013, 06:04:44 PM
 #241

I would be more comfortable xoring than concatenating multiple inputs.
Your better off concatenating and then hashing the concatenation to the needed size. XORing is not a good idea. To see why, consider which of these is safer (where | is concatenation).

1) XOR(SHA256(X), SHA256(X))

2) SHA256(X | X)

The former is zero no matter what X is. The latter is safe so long as X is safe.

Now, consider this. X and Y are fairly random but, due to a broken PRNG, only differ in a few bits. Which is safer:

1) XOR(X, Y)

2) SHA256(X | Y)

The former can be insecure even if both X and Y are secure alone because all the common bits drop out. 2 is at least as strong as the stronger of X alone or Y alone.

I was referring to seeded random generators f(xor(A,B)) versus f(A|B). With an ideal function, it shouldn't matter. With a broken one, it might matter.

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
1711620630
Hero Member
*
Offline Offline

Posts: 1711620630

View Profile Personal Message (Offline)

Ignore
1711620630
Reply with quote  #2

1711620630
Report to moderator
1711620630
Hero Member
*
Offline Offline

Posts: 1711620630

View Profile Personal Message (Offline)

Ignore
1711620630
Reply with quote  #2

1711620630
Report to moderator
1711620630
Hero Member
*
Offline Offline

Posts: 1711620630

View Profile Personal Message (Offline)

Ignore
1711620630
Reply with quote  #2

1711620630
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
JoelKatz
Legendary
*
Offline Offline

Activity: 1596
Merit: 1012


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 20, 2013, 11:23:24 PM
 #242

I was referring to seeded random generators f(xor(A,B)) versus f(A|B). With an ideal function, it shouldn't matter. With a broken one, it might matter.
With a broken one, you're much better off with f(A|B) than f(xor(A,B)). If A and B have too many bits in common, the xor is a disaster.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
grau
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1021


bits of proof


View Profile WWW
August 22, 2013, 08:48:32 AM
 #243

I was referring to seeded random generators f(xor(A,B)) versus f(A|B). With an ideal function, it shouldn't matter. With a broken one, it might matter.
With a broken one, you're much better off with f(A|B) than f(xor(A,B)). If A and B have too many bits in common, the xor is a disaster.
If the generator is broken no operator will make it better. Feed a shifted pattern to | and see an other sort of disaster.
JoelKatz
Legendary
*
Offline Offline

Activity: 1596
Merit: 1012


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 22, 2013, 06:05:48 PM
 #244

If the generator is broken no operator will make it better. Feed a shifted pattern to | and see an other sort of disaster.
Agreed, but it's still important to prefer an operator that won't make it worse over one that will.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
grau
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1021


bits of proof


View Profile WWW
August 22, 2013, 06:32:03 PM
 #245

If the generator is broken no operator will make it better. Feed a shifted pattern to | and see an other sort of disaster.
Agreed, but it's still important to prefer an operator that won't make it worse over one that will.
do not get your point. xor is not worse than or since none of them add any value in this context.
JoelKatz
Legendary
*
Offline Offline

Activity: 1596
Merit: 1012


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 22, 2013, 07:34:13 PM
 #246

do not get your point. xor is not worse than or since none of them add any value in this context.
We are comparing XOR to concatenation. And XOR is much worse. If you XOR two values that have a lot of bits in common, even if each of them is secure individually, the result of the XOR may be predictable, even if you hash it afterwards. If you concatenate, the result is at least as strong as the weakest thing you concatenated, even if you hash it afterwards (up to the strength of the hash function).

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
August 22, 2013, 09:30:06 PM
 #247

do not get your point. xor is not worse than or since none of them add any value in this context.
We are comparing XOR to concatenation. And XOR is much worse. If you XOR two values that have a lot of bits in common, even if each of them is secure individually, the result of the XOR may be predictable, even if you hash it afterwards. If you concatenate, the result is at least as strong as the weakest thing you concatenated, even if you hash it afterwards (up to the strength of the hash function).
You have chosen a particular state of brokenness of the two sources of entropy, so they tend to have bits in common, and so that xoring indeed leads to low-entropy seed. I have chosen a particular state of brokenness, so that one of the two sources is broken, the other is not. In that case, xoring will be at least as strong as the stronger source itself (the extreme case of broken source always returning the same number).
Having said all that, I can't remember why I thought concatenation might be worse - I was imagining a broken hash function whose output depends, for example, more on the first half of the input block, and less on the second half. But that still wouldn't help my original claim, since presumably my two inputs are the same size or larger than the block size - definitely not smaller, as that would be a glaring mistake.
Thanks for being patient with this. I've obviously realized a few things in the process, most importantly that amateur cryptography makes as much sense as amateur brain surgery.

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
TippingPoint
Legendary
*
Offline Offline

Activity: 905
Merit: 1000



View Profile
August 23, 2013, 03:36:17 AM
 #248

More amateur cryptography:

Is there a compound function that could address both examples of brokenness better than either XORed or concatenated seeds alone?

apetersson
Hero Member
*****
Offline Offline

Activity: 668
Merit: 501



View Profile
August 23, 2013, 09:41:11 AM
 #249

instead of toying around with XOR and |  you want to feed it in a cryptographic hash function such as sha256 to accumulate the entropy. "simply" feed every new genuine randomness to a MessageDigest
 and read the randomness from it. A proper application of this approach is the Fortuna PRNG. I will dedicate some resources into providing a library for Android + java from it, so we no longer have to trust /dev/urandom exclusively.
phatsphere
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
August 23, 2013, 11:21:36 AM
 #250

I will dedicate some resources into providing a library for Android + java from it, so we no longer have to trust /dev/urandom exclusively.
the google opensource/android blog just recently featured a workaround with a code example. have you seen it?
JoelKatz
Legendary
*
Offline Offline

Activity: 1596
Merit: 1012


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 23, 2013, 05:25:20 PM
 #251

More amateur cryptography:

Is there a compound function that could address both examples of brokenness better than either XORed or concatenated seeds alone?
I don't think there's any defect in using the hash of the concatenated seeds. Of course you have to choose an appropriate hash function, but other than that you should be fine. The output should be at least as strong as the strongest of the seeds you concatenated, up to the strength of the hash function.

I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
August 23, 2013, 05:43:50 PM
 #252

You have chosen a particular state of brokenness of the two sources of entropy, so they tend to have bits in common, and so that xoring indeed leads to low-entropy seed. I have chosen a particular state of brokenness, so that one of the two sources is broken, the other is not.

In support of this, in my case, I've suggested that two sources of entropy should be so different such that the possibility of them being broken in the same way is negligible.

(e.g. source #1 = keyboard mash, source #2 = /dev/urandom, and the likelihood of the hash of my keyboard mashing having any coincidence with the output of /dev/urandom being zilch.  The only plausible worst case scenario - which would have to be "/dev/urandom is really just a keylogger that returns the hash of recent keyboard input" is something easily proven to be false to anyone even remotely familiar with how /dev/urandom really works)

If this is done, then XORing and concatenation should be equally effective.

On the other hand, if source #1 and source #2 are similar or the same RNG that is suspected to be broken, then I believe concatenation and XOR to both be ineffective, because both of them are pretending that it's a safe assumption that an RNG found to lack entropy (i.e. is broken) can suddenly be redeemed by running it twice.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
JoelKatz
Legendary
*
Offline Offline

Activity: 1596
Merit: 1012


Democracy is vulnerable to a 51% attack.


View Profile WWW
August 23, 2013, 06:50:12 PM
 #253

In support of this, in my case, I've suggested that two sources of entropy should be so different such that the possibility of them being broken in the same way is negligible.
...
If this is done, then XORing and concatenation should be equally effective.
The difference is that XORing can produce an output weaker than either input, concatenation cannot. The point is to protect against very unexpected failures without having to make assumptions about how well the underlying code is working. For example, you might write your code to use two different sources of entropy but then someone realizes that one of your sources is weak and so changes it to use a better source and now you're not using different sources anymore. Concatenation is robust, XOR is not.

Quote
On the other hand, if source #1 and source #2 are similar or the same RNG that is suspected to be broken, then I believe concatenation and XOR to both be ineffective, because both of them are pretending that it's a safe assumption that an RNG found to lack entropy (i.e. is broken) can suddenly be redeemed by running it twice.
The idea is to tolerate the unexpected case where source 1 and source 2 are similar or the same. XOR doesn't. The best imaginable algorithm can't produce an output stronger than the sum of the strengths of all of its inputs.

If we didn't have to tolerate unexpected cases, we wouldn't need any of this. An algorithm that can make things worse in unexpected cases is a bad idea, especially when it's so easy to make algorithms that don't.


I am an employee of Ripple. Follow me on Twitter @JoelKatz
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
August 23, 2013, 07:01:35 PM
 #254

In support of this, in my case, I've suggested that two sources of entropy should be so different such that the possibility of them being broken in the same way is negligible.
...
If this is done, then XORing and concatenation should be equally effective.
The difference is that XORing can produce an output weaker than either input, concatenation cannot. The point is to protect against very unexpected failures without having to make assumptions about how well the underlying code is working. For example, you might write your code to use two different sources of entropy but then someone realizes that one of your sources is weak and so changes it to use a better source and now you're not using different sources anymore. Concatenation is robust, XOR is not.

Quote
On the other hand, if source #1 and source #2 are similar or the same RNG that is suspected to be broken, then I believe concatenation and XOR to both be ineffective, because both of them are pretending that it's a safe assumption that an RNG found to lack entropy (i.e. is broken) can suddenly be redeemed by running it twice.
The idea is to tolerate the unexpected case where source 1 and source 2 are similar or the same. XOR doesn't. The best imaginable algorithm can't produce an output stronger than the sum of the strengths of all of its inputs.

If we didn't have to tolerate unexpected cases, we wouldn't need any of this. An algorithm that can make things worse in unexpected cases is a bad idea, especially when it's so easy to make algorithms that don't.



Given the assumption of doing something to hedge against a bad RNG versus nothing, I agree with you on both points.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 [13]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!