Topic: NSA and ECC (Read 48711 times)

Can we reverse this script, like we insert N for search P, in series search

pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice

here is your selection P
115792089237316195423570985008687907853269984665640564039457584007908834672377
115792089237316195423570985008687907853269984665640564039457584007908834672281
115792089237316195423570985008687907853269984665640564039457584007908834672279
115792089237316195423570985008687907853269984665640564039457584007908834672153
115792089237316195423570985008687907853269984665640564039457584007908834671901
115792089237316195423570985008687907853269984665640564039457584007908834671691
115792089237316195423570985008687907853269984665640564039457584007908834671663
115792089237316195423570985008687907853269984665640564039457584007908834671591
115792089237316195423570985008687907853269984665640564039457584007908834671583
115792089237316195423570985008687907853269984665640564039457584007908834671301
115792089237316195423570985008687907853269984665640564039457584007908834671033
115792089237316195423570985008687907853269984665640564039457584007908834670671


go to this ecc calc and fill following details
http://www.christelbach.com/eccalculator.aspx

p = 115792089237316195423570985008687907853269984665640564039457584007908834671583
a = 0
b = 7
px = 115301655840403608332148854465368444683257224081574702572138639602380667382125
py = 103799472776126890762485670055583971987299536955028941653349419016168013365384

qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667
qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565

and press P + Q
you will see B=7 changed to
b = 32267065813313537246304986561842436172856576584501774751507060994620472625355

mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed
save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site
can you all start again to find correct P other then - 977, which stand for b =7
or advice me where i am wrong
[/quote]

Question is below is simple formula for use P to substract 2 point, there is no n value involve,
p4 = int(2**256 - 2**32 - 977)

dx = (x1 - x2) % p4
dy = (y1 - ((p)-y2)) % p4
c1 = (dy * gmpy2.invert(dx, p4)) % p4
cu = dy * gmpy2.invert(dx, p4) % p4

Rx = (((c1*c1)%p4) - x2 - x1) % p4
Ry = ((c1*((x2 - Rx))) - y3) % p4
print (Rx , Ry) # 6 sub, 3 mul, 1 inv
print (hex(Rx), hex(Ry))

if P we choose from your generated P list as above you mention, results goes wrong, and even its fail to comply with B = 7

I wrote a small program that allows you to quickly check if a Bitcoin file has a transaction in it, and also checks whether it is a valid Bitcoin file and whether it is locked.
https://github.com/Humble2020/BitcoinFile-Verifier

The next value is far away from that, it is this one:
If you want to reproduce that, you can use this Sage script:
If you put "2^256-2^32" as your starting point, you can see this result:
You are simply checking p-value only, while you should also check n-value. Recently, garlonicon had the same problem, see this topic: https://bitcointalksearch.org/topic/selecting-p-values-for-secp160k1-secp192k1-and-secp224k1-5464362

Also note that p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 does not allow you to use n-value to form another curve, that will give you p-value back. But it is acceptable, because for other curves it is also not the case, it is just a coincidence that secp256k1 has such property.

pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice

here is your selection P
115792089237316195423570985008687907853269984665640564039457584007908834672377
115792089237316195423570985008687907853269984665640564039457584007908834672281
115792089237316195423570985008687907853269984665640564039457584007908834672279
115792089237316195423570985008687907853269984665640564039457584007908834672153
115792089237316195423570985008687907853269984665640564039457584007908834671901
115792089237316195423570985008687907853269984665640564039457584007908834671691
115792089237316195423570985008687907853269984665640564039457584007908834671663
115792089237316195423570985008687907853269984665640564039457584007908834671591
115792089237316195423570985008687907853269984665640564039457584007908834671583
115792089237316195423570985008687907853269984665640564039457584007908834671301
115792089237316195423570985008687907853269984665640564039457584007908834671033
115792089237316195423570985008687907853269984665640564039457584007908834670671


go to this ecc calc and fill following details
http://www.christelbach.com/eccalculator.aspx

p = 115792089237316195423570985008687907853269984665640564039457584007908834671583
a = 0
b = 7
px = 115301655840403608332148854465368444683257224081574702572138639602380667382125
py = 103799472776126890762485670055583971987299536955028941653349419016168013365384

qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667
qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565

and press P + Q
you will see B=7 changed to
b = 32267065813313537246304986561842436172856576584501774751507060994620472625355

mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed
save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site
can you all start again to find correct P other then - 977, which stand for b =7
or advice me where i am wrong

I understand that in Bitcoin the public address is a cryptographic hash of the public key thus the public key is obscured often until it is spent.

In addition to reusing addresses, doesn't also the ability to sign a message to prove you own some coins reveal the public key? And the adversary has a lot of time to attempt to crack your public key then (but no publicly known feasible attacks exist at this time).

Also I made the point else where recently that since one Bitcoin pool sometimes controls near to or more than 50% of the hashrate, then intercepting a transaction before it is on the blockchain is feasible. In this case, I understand ECDSA would still need to be more than just a little bit broken because the time to crack would be measured in minutes, thus a quantum computer would need much more than just a few qubits or the number theoretic breakage would need to be severe.

You can transform any pubkey on any G to a pubkey on another generator by means of addition.  In particular, if there is some bad generator O where you can compute the log of Ox for arbitrary x easily, one can use find the discrete log of Gx as log_O(Gx)/log_O(G) mod order. One doesn't need to prove anything about the hardness of the discrete log to just show the arithmetic relation that if on a curve discrete log is insecure with respect to one generator then discrete log is insecure with respect to all generators of that group.

A better example that I could have given is how the byte order is chosen (big endian or little endian). You surely can't create an implementation without knowing how to deseralize the bytes, but byte order isn't relevant to security.

I'd like to clarify this terminology a bit. 

When I think of your three examples, yes the word irrelevant comes to mind.  The issuer of the paper, the spell checker, and the short name of the curve, are all things which I don't even need to know to use bitcoin or to write my own client.  One might even say "provably" irrelevant for that reason, in that the relevance in question here implied by the forum in which we are using.  However I personally would avoid using that terminology, perhaps because of my mathematics background.   

However the G points are hardly irrelevant in this context, please correct me if I am wrong.  If I don't know them I can't validate TXs, can't sign TXs, and so I can't use bitcoin at all.  Every ECC operation in bitcoin requires every bit of G to be exactly right.  When you say G is provably irrelevant, I can only assume (and I'd rather not hence this reply) that you mean a choice of G cannot effect the ability of an attacker to brute force a private key.  While there are convincing arguments of that in this thread, I wouldn't call any of them a proof.  AFAIK the difficulty of discrete logs, on elliptic curves, or even the difficulty in factoring large numbers, has not been proven and probably a proof that these things cannot be done in polynomial time would be equivalent to a proof that P!=NP. 

   

   

Seems no one knows, but likewise— who created the paper the printed version of the spec was printed on?  What software was used to spell check the document?  Who came up with the shortname for the curve? maybe they were a secret NSA plant!   if you want to go down the rat whole of _provably_ irrelevant things there is no end to it.  Ultimately people who are not technically sophisticated are at risk of being FUDed by people who are dishonest or themselves confused, but no amount of good process can prevent that.

I understand how the choice of G can be irrelevant.  However this fact is irrelevant to my question: why were they chosen as such?  My argument here is for better marketing.  I'm sure you understand the "nothing up your sleeve" motivation..  sure having something in your sleeve is not going to have relevance to ECC but the idea is to still show that there is nothing in your sleeve. 

My question stands:  where did those numbers come from?  The probable answer is that they came from a random number generator that was lying around at the time, probably initialized by the date.  It's too bad this wasn't documented.     

 

Awesome.  A provable "secrecy bond".

On second thought I believe you are right.  My thinking was it is unlikely but possible someone (maybe NSA with their super secret hashing farm) could attempt multiple blocks and discard them until it found one which produced a weak curve.  In essence stacking the deck.  I failed to realize that adding more blocks wouldn't help as they are indirectly included in the prev_block and to change the seed the attacker would still only need to change the last block. So control over block n is the only thing which matters.   Honestly it is probably a non-issue as even if the attacker rented a majority of the hashrate and discarded blocks he is paying a cost per block and eventually he will fall to far behind.  As you indicate below    Also there is the human element while it isn't doesn't disprove manipulation, any manipulation would be very easy to spot.  If there suddenly was a 238 block reorg which replaced the magic block well it might be prudent to not use the results.


That is a good analogy.


Agreed.  That should be ~2^66 not 2^70 right?  I assume it represents the average amount of work needed to solve one block and thus created and test one set of curve parameters for vulnerabilities.


Agreed and I would lean towards minimal validity testing.  Still if some people decide to be more restrictive the use of a standard how to cheat generator is still beneficial.  For example lets say curve 283 is minimally valid but it doesn't have some properties that DJB et all see are important for security.  If they can convince people to not used curve 283 (the first valid nonce) and instead use curve 13,288 (the first nonce which passes all his tests) than more power to him.  If nothing else it puts them both out there on an equal playing field.  If the additional criteria worth the possibility of manipulating the selection by bypassing other currently valid curves? 

A neat variation is that for the parties that compute H(R_n) you make H() really be g*R_n  on bitcoin, and require that the transaction commuting to the scheme actually be doing a coinjoin with the R_n parties, putting up some non-trivial amount of bitcoin to be held under each of the private keys for the duration of mining time.  This means that if any of the parties leak their R_n value to a miner (or other R_n) holders during the mining interval so that the miner could attempt to grind a solution with a particular output then someone could instead steal their coins... so the integrity of the process would be bonded.  The bonds could potentially be very large.

I think since each block already hashes the prev block we already have that property without doing it explicitly!

There is an argument that it should be using toeplitz hashing with as much data as possible as an input as the entropy extraction, but there is a tradeoff that more "unusual crypto" in the scheme makes it harder to trust.

Yep. The idea is that you lay out all the "influence" parts up front, then use the blockchain to 'cut the deck' in a hard to rig way.

Even if someone didn't personally witness the process they still have the blockchain POW as evidence for a minimum computational cost in retrying. E.g. doing 2^70 blockchain work multiple times to rig it might be conceivable, but not the 2^128 work required to do 2^58 retries.

The next annoying property is that you want to have curve-acceptability tests but too many tests and perhaps you are actually testing for weakness-included. E.g. DJB would perhaps have you test that there exists a specific mapping to nearly uniform scalars (e.g. elegator), but perhaps that guarantees a vulnerability. Or in our case secp256k1 is selected with the efficient endomorphism to permit the GLV method for faster operations.

That is true however it is about reducing the window as much as possible.  The number of permutations of possible hash functions and serializations is relatively small compared to the number of "random" seeds that can be produced at "reasonable" cost by an intelligence agency.  Thanks for pointing out that the system used by Certicom/NIST does have some merit in preventing the exploit of weak parameters which occur rarely.  Those flawed parameters which occur less frequently than than 1 in > 2^96 are probably not exploitable .  The problem is that computing 2^80 curves (or at least 2^64) would be possible and would allow exploit of even weaknesses which occur rarely.  If (and it may not be possible) one found a weakness which occurs at least one in 2^80 random parameters an agency could produce a "verifiably random" curve that they have pre-compromised.  It may not even be a scenario where they know the curve can be compromised but rather generating a huge number of curves and then having their top minds pick the curves they believe show the most promise for cryptanalysis in the future.

So while it would be possible for one to try more than one permutation of an incrementing nonce curve the window would be significantly smaller right?  How many possible serializations and hash functions could be used.  2^20? 2^10? less?  Of those how many would be greeted with suspicion?  There are only a handful of hashing algorithms which would be seen as logical choices.  Likewise with serialization, simple is better and more transparent.  Using some exoteric serialization would be seen with suspicion "why did you do x,y,z when you could just do x".

Still I do like the idea of using the blockchain to act as both a timestamp mechanism and very difficult to manipulate entropy source.  Instead of a single block hash the computational cost can be easily increased by using a sequence of n block hashes starting from the the block containing the commitment txn (block_x).  Since miners are in fact distrusting parties you could optionally avoid the need for step #2.

H(scheme||blockhash_x || blockhash_x+1 ... || blockhash_x+n-1)
or
H(scheme||R_n...||blockhash_x || blockhash_x+1 ... || blockhash_x+n-1)

I also like the idea that you can in essence do a trial run.  Pretest the system to be sure it works as expected without knowing what the official seed is going to be.  Get peer reviewed feedback and then commit it to the blockchain and wait for the entropy source to be generated.  Now everyone can use the generator to produce curves in an open and transparent manner.   I know I would trust it more than any other so called "provably random" curves.

Well, it is different— say there is a class of weak curves known to the NSA but the weakness requires you to select a one in 2^128 set of parameters... without a pre-image attack on the hash function you couldn't use one of these 'random' procedures to pick such a curve.

If the weakness was a 2^32 one— you could, thus the bada55 curves.

The scheme you suggest has a weakness in that there are potentially too many plausible schemes.  For example, an attacker might use their ability to choose a hash function and value serializations to choose insecure parameters.

What I would prefer is a scheme that worked like this:

(1) Take a scheme like yours, but give it an initialization seed as an input. The scheme should be designed such that all acceptable parameters are equally likely to be selected (assuming good properties of some cryptographic hash).
(2) Publish the scheme, and ask various mutual distrusting parties to compute random values R_0, R_1 ... and each of them publishes X_n = H(R_n).
(3) Take the H(scheme) and X_n and commit to them in a bitcoin transaction, publicly announce this commitment.
(4) 100s blocks after the commitment, take the block hash 100 blocks after the comment and have the parties release their R_x numbers. H(scheme||R_n...||block hash)

The idea here is that up to the preimage resistance of the hash function, to influence the selection you must both compromise all the distrusting parties AND do a huge amount of sha256 computation.

But thats all for where a random selection can't be avoided... the "fixed by security/performance considerations" approach is probably best.  An interesting question how reasonable it would be to formalize all those considerations in order to combine the approaches... since DJB's claims notwithstanding, there really is many degrees of freedom in within that (otherwise secp256k1 _and_ ed25519 wouldn't both exist).

That is the rub isn't it.  Any "verifiably random" curve which is just a deterministic process starting from an arbitrary and claimed (but completely unprovable) random seed value is worthless.  I mean provably fair bitcoin casinos are better constructed in their proof and transparency.

This is the logic one is suppose to accept from NIST/NSA:
Generate "random value" -> curve parameters = insecure because one could just pick "random values" until they find one which produces a weak curve.
Generate one* "random value" -> seed -> deterministic process -> curve parameters are the first valid curve = "secure" because look it is a deterministic process.

Yes NIST claims the seed for secp256r1 was the first and only one they generated.  It might actually be but it can't be proven and they know it can't be proven so the "provably random" is just "random".  It is no different than NIST just randomly generating curves directly.  In both cases you have to trust that what they published as the "first valid curve" is actually the first valid curve and not the
first valid but weak curve" after they attempted and discarded quadrillions of other more secure curves. Trusting the seed is actually random is no different than trusting the parameters are random.

Now doing something like the following the term "provably random" might actually mean something:

The process is completely deterministic, each curve can be documented as to the reason for rejection.  The criteria for "valid" can be closely analyzed.   Some may choose to use a lower nonce curve that while less efficient is purer in the sense that the window for manipulation by setting criteria is small.  Others may select a higher nonce curve which is more efficient than a lower nonce one.  The probability that the hash of an incrementing nonce would in sequence produce a curve that looks secure but has a flaw NIST/NSA is aware of before a strong curve is remote.   There would be some value in random curves using a generator that is open and transparent.  Now this isn't a very hard concept and NIST/NSA have lots of very smart people so I am sure someone had to think of something functionally similar to this.   It wasn't used and instead they created a dog and pony show about deterministic curve generation from a random seed which does nothing but make the process more opaque.  So the obvious question becomes why?

In making its recommendations, the VCAT specifically addressed NIST's interactions with the National Security Agency (NSA). The report states, "NIST may seek the advice of the NSA on cryptographic matters but it must be in a position to assess it and reject it when warranted."

"The report also recommends that NIST review the current requirement for interaction with the NSA and recommends changes in instances where it "hinders [NIST's] ability to independently develop the best cryptographic standards."

"We will continue to work with the best cryptography experts in the world, both inside and outside of government," said May. "At the same time, we recognize and agree with the VCAT that NIST must strengthen its in-house cryptography capabilities to ensure we can reach independent conclusions about the merits of specific algorithms or standards."

http://www.nist.gov/public_affairs/releases/crypto-review-071414.cfm

Please read the thread. We explain in detail how choice of G is not relevant for our own applications. If you don't believe that, DJB also argues why choice of G is usually irrelevant on safe-curves (SafeCurves does not place restrictions on the choice of this base point. If there is a "weak" base point W allowing easy computations of discrete logarithms, then ECDLP is weak for every base point)— an argument he added after I emailed him and suggested he add an explanation of his own G choice, which he did not previously provide... it took me inventing a novel attack against a contrived hypothetical protocol (not Bitcoin) where choice of G actually mattered to convince him to say anything at all.

Thanks, if you mean me yes I was not talking specifically about the bada55 curves, though thanks for explaining how they are badass   I was looking for some insight into whether any of the vulnerabilities mentioned by Daniel J. Bernstein and Tanja Lange are serious and why nobody has added more curves to the openssl default list. 

I'm not too concerned with the 977 parameter but to the untrained eye of for example an investor the presence of unexplained numbers in the generator could still be troubling.  Earlier in the thread we heard: 
 
SECG chair Dan Brown: 

3. The base point G is something I cannot explain, [snip]...   I strongly doubt that G is malicious, [snip]

OK so I took him a little bit out of context but you can see how someone researching the security of the DSA of bitcoin might not feel 100% satisfied.   It's a pity we can't do better and determine where they really came from but I guess whoever picked those points probably had no idea they would one day secure millions of people's finances.

Shall we offer a bounty?