The per message secret and address reuse

[Altoidnerd]

I find this paper quite good and well written: https://eprint.iacr.org/2013/734.pdf

For the sake of notation, please refer to section 2.4.  In section 2.4, there is a clean mathematical explanation of the vulnerability if the "per message k secret" is reused.

The relevant question that is floating around now is this: does signing a message in the protocol blatantly recycle the k-secret, or are k-secrets only recycled if an address is reused AND there is another critical flaw, such as a poor random number generator?

so, choices:

k-secret is always recycled if a key signs a message twice

-or-

the risk of the k-secret being revealed is higher if keys are used more than once AND there is some other critical problem

[other_side]

K is a random number. Should be used once.

[Altoidnerd]

K is a random number. Should be used once.

Should indeed.  The question is what does happen?

I feel you're suggesting the failure is of random number generation, then.

[other_side]

Should indeed. The question is what does happen?

It is a well known case of some implementation.

[Altoidnerd]

I suspected this, and my interpretation of the study I linked agrees.

If so, we needn't waste time discussing secp256k1^[1] and agree once and for all the problem at hand is the generation of truly random numbers.

^[1] in regards to repeated address use.  Discrete log shortcuts on y^2 = x^3 + 7 are a separate issue.

[Ix]

If so, we needn't waste time discussing secp256k1^[1] and agree once and for all the problem at hand is the generation of truly random numbers.

Generating random numbers is one problem, one that is solved by using the message hash as a seed, such as with Ed25519--and I believe ECDSA can be modified to support this construct as well. It is possible, however, that signatures leak information that can eventually be used to determine the private key, with the added information of multiple signatures potentially leading to speed ups as well. It is possible that one day there will be a way to crack private keys from only the public keys in polynomial time.

Having the public key hidden behind a safe hash is definitely the most secure construct. Generating true random numbers is not the only problem.

[Altoidnerd]

But suppose you could cheaply generate real entropy with a physical procedure, not only would the secrets be random, but the hashes could potentially be strengthened, or?  

Having the public key hidden behind a safe hash is definitely the most secure construct. Generating true random numbers is not the only problem.

Then what are the other problems?  Are you suggesting the degeneracy in secp256k1 due to the 0 coefficient is a considerable weakness?  I'd rather not guess what you mean.  Do tell.

[Ix]

Physical entropy sources already exist, and I think Intel is considering adding a RNG to their processors, but [tinfoil] there is no way to verify that the microcode has not been tampered with.

Then what are the other problems?  Are you suggesting the degeneracy in secp256k1 due to the 0 coefficient is a considerable weakness?  I'd rather not guess what you mean.  Do tell.

As I said, signatures may leak enough information to perform potential attacks in the future. Public keys might even. Hashing algorithms have much stronger security assumptions than digital signatures.

[Altoidnerd]

Physical entropy sources already exist, and I think Intel is considering adding a RNG to their processors, but [tinfoil] there is no way to verify that the microcode has not been tampered with.

I think the quadrupole interaction in spin-3/2 nuclei can take care of this.  Chlorine NQR comes to mind, which can be performed on tabletops.  A good example of a high signal to noise obtainable from low power excitations is para-dichlorobenzene single crystals.

No proprietary irreversible silicon required.  Just a coil and a pulse generator.

[prezbo]

Recycling of the secret random number has only been the case in one implementation, as far as I know, that has since been fixed. Mind you however, that the number k could just as well be a part of a sequence, as long as it is not reused it's ok.

[Altoidnerd]

Recycling of the secret random number has only been the case in one implementation, as far as I know, that has since been fixed. Mind you however, that the number k does not need to be random, it could just as well be a part of a sequence, as long as it is not reused it's ok.

Even if the sequence is identified?

[prezbo]

Recycling of the secret random number has only been the case in one implementation, as far as I know, that has since been fixed. Mind you however, that the number k does not need to be random, it could just as well be a part of a sequence, as long as it is not reused it's ok.

Even if the sequence is identified?

My mistake, it has to be unknown.

[Altoidnerd]

Recycling of the secret random number has only been the case in one implementation, as far as I know, that has since been fixed. Mind you however, that the number k does not need to be random, it could just as well be a part of a sequence, as long as it is not reused it's ok.

Even if the sequence is identified?

My mistake, it has to be unknown.

Well fuck intel I can make this thing.

The focus should not be deterministic generation.  That's what quantum mechanics is for.

[Ix]

Well fuck intel I can make this thing.

They already exist: https://en.wikipedia.org/wiki/Hardware_random_number_generator

But it is not really practical to outfit every possible device with something like this (yet), but even then the problem will be the layers between the physical generator and the output. If they are compromised, the hardware entropy is useless. If they aren't, software entropy is usually enough, but obviously there are going to be instances of bad coding.

One property of a scheme like Ed25519's is that the same signature is always generated for the same message, there is therefore no room to exploit any of those layers for this particular problem.

[Altoidnerd]

You are correct - the physics is random but the signal path thereafter is a black box. I am roughly aware of the current state of hardware RNGs...they tend to rely on shot noise and thermal fluctuations which is pretty good, but AFIK always route the signal through proprietary integrated circuits at some point making their usefulness in an open source project dubious.

I am very interested in making provably cheatless quantum random bits, even perhaps in such a way that the user can construct the "antenna" themselves - none of the commercial hardware solutions I am aware of take advantage of NMR which is and has been my hope for some time.

I feel as time goes on, the reliability of deterministic RNGs will only worsen. The code to support them becomes more and more complex to fight off attackers.

NMR on the other hand is described by advanced physics and as such is conceptually prohibitive as of today but I hope to change that...the math is weird BUT the circuits used are actually very simple - shockingly so...anyone would be able to tell there is nothing fishy going on. I have been interested in "Open NMR" for a few years in fact...even before i became involved in bitcoin. I specifically work on a type technique called zero field NMR or NQR which doesn't require expensive magnets so could be done cheaply.

See the outdated but historical title of my website which was originally intended to display an open source NMR spectrometer.

Anyway, I think these solutions would be surprisingly straight forward because this is very simple analog circuitry - but more research is needed and I am having a hard time finding like minded individuals to team up with.

------

Now you seem to like Ed25519...I am not familiar with this curve, can you point me to a resource?

[Ix]

http://ed25519.cr.yp.to/

The relevant part:

Foolproof session keys. Signatures are generated deterministically; key generation consumes new randomness but new signatures do not. This is not only a speed feature but also a security feature, directly relevant to the recent collapse of the Sony PlayStation 3 security system.

The only time you need randomness is when generating new keys. The Android wallet app problem could not have happened with this feature. Introducing biases into the RNG when creating private keys would either 1) have to be so unnoticeable that it could only reduce security by a few bits, or 2) a collision would eventually happen (and could be tested for, much quicker than generating keys), alerting everyone to the compromised hardware.

Now, hardware/software has to be intentionally compromised, and bad programmers would be off the hook. Well, mostly, as really bad RNGs could still produce duplicate keys. I'm not familiar with the exact method that caused the app problems, but at the very least you could import private keys from a trusted source (generated yourself or whatever) onto an untrusted device and trust that it is not leaking information via the signatures it makes.

[Altoidnerd]

http://ed25519.cr.yp.to/ed25519-20110926.pdf

It looks like these curves have seven parameters instead of two. Well I can't say much - this is the first I've seen them and need to do some reading, but I'm optimistic they CAN be more secure however positive with more complexity comes more room for engineer error.

[Crowex]

Generating random numbers is one problem, one that is solved by using the message hash as a seed, such as with Ed25519--and I believe ECDSA can be modified to support this construct as well.

RFC6979

It is possible, however, that signatures leak information that can eventually be used to determine the private key, with the added information of multiple signatures potentially leading to speed ups as well.

I am very interested in this topic and would be grateful if anybody could link me to any proper research papers regarding weaknesses caused by multiple signatures. (I don't mean weaknesses caused by bad RNG) I sometimes see this referred to as a potential problem but can't seem to find much proper research.

[deepceleron]

If you want more to read:

http://eprint.iacr.org/2013/346.pdf

http://home.deib.polimi.it/barenghi/lib/exe/fetch.php?media=host2011.pdf and
http://ecdsacuda.googlecode.com/git/Documentation/sin2011.pdf

http://www-salsa.lip6.fr/~goyetc/doc/ImplicitECDSA_Goyet.pdf

a postscript doc http://www.di.ens.fr/~pnguyen/pub_NgSh02.htm

and then a primer on faults: http://books.google.com/books?id=fUoSjJp1S5QC&pg=PA144&lpg=PA144&dq=invalid-curve+fault+attacks&source=bl&ots=pvntdCK83D&sig=Wo6Ndzwk9n25-WKyPKgr2Tj2TvI&hl=en&sa=X&ei=qknfUrLvBIH9oATCkYD4DQ&ved=0CD0Q6AEwAQ#v=onepage&q=invalid-curve%20fault%20attacks&f=false

[Altoidnerd]

Generating random numbers is one problem, one that is solved by using the message hash as a seed, such as with Ed25519--and I believe ECDSA can be modified to support this construct as well.

RFC6979

It is possible, however, that signatures leak information that can eventually be used to determine the private key, with the added information of multiple signatures potentially leading to speed ups as well.

I am very interested in this topic and would be grateful if anybody could link me to any proper research papers regarding weaknesses caused by multiple signatures. (I don't mean weaknesses caused by bad RNG) I sometimes see this referred to as a potential problem but can't seem to find much proper research.

The paper I linked at the top

https://eprint.iacr.org/2013/734.pdf

is one of my favorite expositions of the subject.  It includes enough background to let you research the buzzwords, and is the summary of an empirical study of the effectiveness of various attacks.

If the per message secret is recycled, an attacker can perform an old method of cryptanalysis that compares two ciphertexts encrypted in the same way.

The technique is quite old in fact http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Operating_shortcomings