NSA and ECC

[Mike Hearn]

These slides are interesting:

http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

It says right out that the NSA generated the curves:

Important example: IEEE P1363 standard
   Surveys all ECDLP attack techniques known in 1999
   Prohibits all curves breakable by these techniques
   Species method of generating random non-prohibited
curve  
      Jerry Solinas at NSA used this to generate the NIST
curves (or so he says)

However it also implies that the generation criteria might be more complicated than just "iterate a hash input until a functioning curve is found". Is it possible the seed looks strange because large classes of output curves were discarded due to known attacks?

This might be Mr Solinas' email address: jasolin@orion.ncsc.mil

We could ask him if how the curves were generated is reproducible.

Apparently the NSA controlled all membership to the IEE P1363 working group:

http://grouper.ieee.org/groups/1363/WorkingGroup/announcements/Nov96.txt

Due to NSA requirements, THOSE PLANNING TO ATTEND THE
MEETING MUST CONTACT JERRY SOLINAS IN ADVANCE OF THE
MEETING to be placed on the attendance list.

This just looks worse and worse, doesn't it. I didn't realise ECC was so heavily influenced by the NSA before. I thought it had been primarily developed by the academic sector.

[Carlton Banks]

This might be Mr Solinas' email address: jasolin@orion.ncsc.mil

We could ask him if how the curves were generated is reproducible.

Maybe better ask first if the generation methodology is classified.

[markm]

So maybe there is a class or category of attacks, making all ECC broken, and they iterated through SHA1 generating curves knowing they could, with their clever class or category, break them, but wanting to not bother recommending those the public already had found attacks for?

The attacks known to the public would maybe mostly be individual subsets of the secret class or individual classes of the secret category or something like that.

(I'd have to go read up on what class and category mean in class theory and category theory if I wanted to check whether I used the words set, class and category correctly.)

-MarkM-

[piotr_n]

It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards.

At the other hand, from what I understand these constants are like 10 years old.
If there is any secret math that can be used to exploit ECC with a certain curve parameters (and NSA had known about it before these constants were chosen), it would basically mean that all the academic world sucks, if it have not managed to discover the same formulas ever since then. It even seems unlikely that such a breakthrough math inventions would not have leaked out, for all these years.

So there is still hope... but it would still be good to find out how (and why) these constants were picked up.

[markm]

Whozit's conjecture or whatever, written in a margin long ago, took frikkin centuries for academics to figure out.

Had the guy maybe not really solved it himself afterall but just imagined he had?

I made a proof, as a child, of the four colour theorem that still looks good to me. In my late teens someone even tried submitting it to Scientific American because it looked so good. Yet to this day I still have not managed to get any actual proper refutation of it or explanations as to how, if it is not a "proof", it fails to be one.

My maths teacher when I first came up with it said the whole thing was so far beyond him he could not even begin to judge if it was or was not mathematically a proof but that it sure seemed to be an irrefutable argument to him, lacking as he was in deep enough mathematical training to figure out where it went wrong, if it did in fact go wrong. (It is so simple, even children "get it", thus suspect as in hmm maybe it is not state-able mathematically in rigorous math.)

So between the margin-written thing that people bumped heads with for so long, and my own personal experience, it does not seem far fetched at all to me that some kid somewhere pointed out some insanely simple thing that mathematicians had all overlooked and continue still to overlook.

Then too there is Bell's Theorem, which even now while Joy Christian keeps pointing out Bell's massive deep fundamental flaw in it a lot of physicists just cannot see / understand the flaw, seemingly because they make the same categorical or dimensional error themselves in judging his work.

-MarkM-

[piotr_n]

I guess many things are possible.
But for sure it is impossible that, if there is the secret math, nobody knows about it.
No matter how secret NSA would like to keep it, there should be at least tens of people who would know about it.
But more likely hundreds, or even thousands...

Ever since bitcoins have become an actual money, and since people are able to short BTC, there is an actual incentive to make such an info public - and leaking it out anonymously (using tor, or whatever) does not seem to be so much of a challenge.
At the other hand, if you know the secret math and how to exploit the constants, maybe you would earn more just by stealing bitcoins - but then we would also find out about it.

[markm]

Sure, if they actually believe it.

But suppose even though you see in front of your eyes the computer produce a solution, all your mathematicians claim it is impossible thus you believe what is really happening is rubber hoses are being wielded somewhere then the PR department is passing off the miraculous results as being due to a secret formula in the computer?

Maybe those who know solutions can be found by that computer think whistleblowing "the government has rubber hoses!" is not exactly breaking news...

The number of people who know the computer really is using math to get the answers need not be nearly as large as the number of people who know the computer is in regular use providing answers.

I probably wouldn't tell people only four colours are needed to colour a 2-D map if knowing it would kill gosh knows how many agents of the five-eyes (brits, canucks, yanks, aussies, kiwis) and the world had not yet proven it to be so. (Scientific American didn't consider it proven until some ridiculously huge computer-generated proof involving iterating over stuff finally proved it long after I thought I had, maybe because my "even a child can grok it" approach is just too darn simple for their complicated little minds.)

Maybe they tell people who would whistleblow if it were rubber hoses that it is math, and people who would whistleblow if it were math that it is rubber hoses, if just letting people imagine whichever they like doesn't seem likely to work in some particular case?

-MarkM-

[BurtW]

I for one would like to see your four color proof.  Can you publish it in an off topic thread or PM me a copy?

RE the parameter selection process:  I will email and ask if no one else has already.  We probably do not want to bury him him emails.

[markm]

Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain?

(You only need four whatzits to build a DNA strand? Hmm....)

Think like the game "sprouts".

(And maybe read Piers Anthony's "Macroscope" while you're at it.)

One point is a point, two is a line, three is a circle.

If the fourth is inside the circle, it is surrounded, no luck there.

If the fourth is outside the circle, how you gonna connect it to the other three without surrounding any of them?

-MarkM-

[maaku]

It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards.

It is not at all weird. Like I posted earlier, this was the case with the DES S-boxes as well, which was a similar opportunity to back-door symmetric encryption. In that case the NSA took the high route and strengthened the algorithm against attacks that would not be (re-)discovered by industry and academia until decades later. So when NSA employees stepped in and did a similar thing with ECC curve parameters, there was no compelling reason at the time not to trust them.

Of course looking back, DES was only strengthened against attacks that were known by IBM employees at the time, but kept classified. Other forms of attack have shown theoretical success in recent years, and may or may not have been known to the NSA at that time. Maybe this is being paranoid? But with these new revelations, what level of paranoia is justified?

Fool me once, shame on me, fool me twice...

[piotr_n]

It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards.

It is not at all weird. Like I posted earlier, this was the case with the DES S-boxes as well [...]

OK fine, but still: if they chose the constants to strengthen the algo, why is it then a secret how they came to these specific values?
Well at least, from what I see, nobody seems to have an idea why these constants and not some others... not even Bruce Schneier

[gmaxwell]

However it also implies that the generation criteria might be more complicated than just "iterate a hash input until a functioning curve is found". Is it possible the seed looks strange because large classes of output curves were discarded due to known attacks?

The procedure described to the public would not discard very many.

The seed is a very large number... so wherever they started from, it wasn't 0.  

It could be that they discarded many while making the curve stronger, not weaker, using unknown criteria. ... or that they hardly discarded any any at all and just used a secure RNG to pick their next seed instead of incrementing, a left over from a less deterministic procedure. It seems that there is no way to tell, and unless it turns out that the values are really just hashed newspaper headlines, it seems unlikely that they could convince the public any which way on the matter.

This just looks worse and worse, doesn't it. I didn't realise ECC was so heavily influenced by the NSA before. I thought it had been primarily developed by the academic sector.

I knew that that there was heavy NSA influence, at least in the public standards, but after all— NSA has a dual mission, the strengthening security / spying on people... and they likely are the single largest employer of cryptographic mathematicians, so it wouldn't be surprising or unusually concerning.

Ultimately if these curves can be weak based on unknown-to-the-world math, thats bad regardless of tinkering with the parameter selection— and another (actually) random curve could be worse against that kind of threat. But I suppose that there is nothing like postulating a specific attacker to help crystallize the attacks that perhaps we should have worried about all along.

[maaku]

Because even if the information they used to construct the S-boxes is now public, it still reveals the limit of the NSA's knowledge. What if X for some X in the intelligence agencies of Russia, China, Israel has Super Cryptanalysis Technique that the NSA doesn't know about. Then the NSA publishes what technique was used to come up with the S-boxes / curve parameters and -- egads! The NSA didn't check for weaknesses from Super Cryptanalysis Technique! That's exploitable knowledge.

This is why these things are kept secret for something like 70 years. Because showing the sum total of what you know reveals what you didn't know you didn't know.

[piotr_n]

Because even if the information they used to construct the S-boxes is now public, it still reveals the limit of the NSA's knowledge.

I'm starting to feel less and less comfortable reading how the ECC security might not rely as much on the well known math that proves their safety, but rather on NSA secretly choosing their shapes

[balanghai]

I think it's not just spying but also controlling.

[DeathAndTaxes]

While I don't believe NSA has compromised the secp256k1 curve it would be a good idea for Bitcoin to support different address "types".  Today Bitcoin only supports a single type of address construction (excluding P2SH) but this isn't a requirement.   It would be possible to extend the protocol to support multiple methods of address generation.  If ECDSA, RIPEMD-160 or SHA-256 are partially broken to avoid a loss of confidence (and eventually loss of fund security) it will eventually be necessary to extend the Bitcoin protocol to support a new address types.  Doing this now (before mandatory due to compromise of current primitives) would lay the foundation for a more extensible/adaptable protocol.  

Bitcoin uses both digital signatures (ECDSA) and hashing functions (RIPEMD-160, SHA-256) in transactions/addresses.  The protocol could be extended to support a second "type" of address using DSA, RSA, or ElGamal for key generation and a different hashing algorithm (RIPEMD without SHA, SHA-3, WHIRLPOOL) to derive the address from the public key. An even better solution would be one which allows mixing and matching keys and checksumed hashes (addresses).  Alternative curves for ECDSA could also be explored.  

The main disadvantage of using non-ECC based signature systems is that they generally have larger key and signature sizes for an equivalent 128 bit security.

Code:

Algorithm   PubKey Len    PrivKey Len     Sig Len
ECDSA        256 bit*      256 bit  	 512 bits        (* 512 bit using uncompressed PubKeys which was the default in older versions of the client)
DSA         3027 bit       256 bit       512 bits
RSA         3072 bit      3072 bit      3072 bits

Example 2 input, 2 output transaction size

Code:

ECC               370 bytes (434 bytes w/ uncompressed PubKey)
DSA             1,074 bytes (~3x ECC)
RSA             1,714 bytes (~5x ECC)

This assumes the use of explicit key (PubKey is included with signature).  I am unsure if Public Key Recovery is possible with DSA or RSA (it is for ECC but unused by Bitcoin protocol).  If possible then using implicit public keys would provide a significant reduction in transaction size (45% to 75%) as it would allow the elimination of the PubKey (384 bytes) in each input.

[theymos]

And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible.

Ah, very interesting! I never bothered to check that (and I bet a lot of other people didn't, either). Wouldn't it be hilarious if Satoshi managed to choose one of the few standard curves that was not backdoored?

[Mike Hearn]

An alternative CHECKSIG would almost certainly use curve25519 for various reasons, including but not limited to side channel attack resistance. It also doesn't use random values for K.

[gmaxwell]

Today Bitcoin only supports a single type of address construction (excluding P2SH) but this isn't a requirement.

Why do you ignore P2SH?  It is the only practical way to actually _deploy_ another cryptosystem... without it you couldn't start using your fooknapsack key until everyone you might want to send you funds updated, and why would they update when you're not using fooknapsack?  P2SH removes the script-type catch22.

The protocol could be extended to support a second "type" of address using DSA, RSA, or ElGamal

Integer F_p systems with acceptable security have pubkey+signature sizes which make merkle/lamport keys look more attractive than by comparison with ECC.

More importantly, you don't mention the validation speed: My laptop can do 7000 RSA verifies per second vs twice that with secp256k1.

They're all based on the effectively the same underlying security assumptions. If we were to support something else out of prudence and paranoia, something orthogonal to the hidden subgroup problem would be good, which is why I would prefer we implement merkle/lamport keys.  They are QC hard, have security assumptions unrelated to those of the DLP/factoring asymmetric crypto, and very fast implementations are trivial (unlike DSA/RSA/ElGamal/Ecc).

By curve25519 I assume Mike means Ed25519 (curve25519 is for ECDH only).  I'm not a big fan of the idea of using it for us (though I'm a big fan of Ed25519 generally): Another fast ECC implementation means another pile of orthogonal highly complicated (probably assembly) ECC validation code that all full nodes will need to have to validate and keep up with the chain.  If we accept the idea that there exists mathematical weaknesses unknown to the public which could be found with enough searching in randomly selected curves, which is the reason for wanting an alternative here, then what reason do we have to believe that Ed25519 doesn't suffer from the same or worse?  Arguably NSA could have known about such weaknesses and _strengthened_ their choices based on that. Reasoning under uncertainty stinks.  The Curve25519 curve also, like our SECP256K1, has some special structure which yields fast implementations... which could ultimately turn out to be a source of weakness.

I would go further to suggest this transaction structure optimization:

OP_CHECKSIG2

If stack.size() < 2: fail

The "public key" is popped.
The "signature" is popped.

If the size of  "public key" <1: fail

mode = publickey[0]&63;

Modes:
0    SECP256k1
1    COMPRESSED LAMPORT
2-63 NOP

If mode is 2-63: return PASS the signature is accepted for forwards compatibility.

hashtype = pubkey[0]>>6;

Hashtypes:
0: HASH160(pubkey)+SHA256
1: SHA256
2: (Some non-nist cryptographic hashfunction)
3: SHA3-512-256

The remainder of the "public key" [1..n] and the signature value are taken to be hashtype hashes of the mode-relevant public key and signature.

The actual public key and signature are not included in the transaction (thus making future proofs over transactions which don't care about the signatures compact) but the data is instead appended to the end of the transaction externally and only included in the transaction hash through the embedded hash. When the public key or signature data is being stored or transmitted, the opcodes in the script could be replaced with placeholder references, so there would be no storage/bandwidth overhead of the indirection, just as there is no overhead from using hashtrees in our blocks.

This would also permit, if we were to choose the degrade the Bitcoin security model slightly, us to declare that once a transaction is "XXX deep" in a chain no node will need verify its signature, and so _no_ node would need to store the signatures older than that point. (XXX perhaps being sum POW equal to two months of the highest difficulty ever seen in that chain). Though this security model reduction does have some moral hazard, as it potentially increases the economic benefits of an enormous rewrite attack. Realistically, I think, XXX can be set high enough that such a rewrite attack would be simply infeasible as manual consensus could resolve it.

The overhead of longer signature schemes would be pure bandwidth, and not long term storage.

Even if we didn't go the full route of drooping old signature data we could use the hash of a block committing to a transaction as the virtual counterparty in a non-interactive cut and choose.  E.g. The block hash randomly tells you which 1/2 of the lamport signature data you can drop... the weaking of the signature offset by the huge computational work of producing a block committing to the whole thing.

Even vs our current compressed EC signatures this CHECKSIG2 operator could halve long term storage signature size.

[gmaxwell]

I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday.

I'd like to go even further with a new checksig and totally replace the sighash type with the ability to include operators inside the pubkey and/or signature which instruct the node to PUSH various values from the transaction to be signed onto a tagged stack, and then the stack is signed instead of the masked transaction.  This would allow you to do things like "I sign any transaction that pays >=3 BTC to XYZ -- love, pubkey Q", or even just the equal of SIGHASH_SINGLE_AND_ALSO_OUTPUT_N...  but everyone has a pet design, I guess.