Topic: NSA and ECC - page 10. (Read 48804 times)

No. While I prefer people behave in privacy maximizing ways, I think mandating it is unrealistic or at least too risky to be worth the benefit. Fortunately we don't have to.

What you can do is construct N lamport keys, where N is some reasonable number like say 1024 or 8192 (this is super fast, of course, since it's just hashes)... and then your public key is a hashtree over those lamport public keys. And in your signature you just provide the log2(N) additional hashes to connect the particular key you are using.  Alternatively the hashtree could be some other binary tree than a fully populated one, to give you different tradeoffs between reuse amount and signature size.  (google: merkle signature scheme)

The usage is still finite, but it's not just one use.  (and Lamport doesn't become completely insecure if you reuse it, it just starts losing its security... so if you had some extra unsolicited payments past your keys lifetime, it isn't the end of the world.)

Of course, the fact that privacy in Bitcoin calls for minimizing address reuse makes the finite lifetime even less of an issue then it would be in some other cases.

"The system that".

The concept of _deterministic_ wallets is general and works for just about any cryptographic system.  Are you talking specifically about derivation using the "public" type-2 homorphism? That works only with cryptosystems based on trapdoor permutation that have certain properties (the permutation must support composition), and obviously a single derivation chain only works with a single cryptosystem.

If you're asking about BIP32,  BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem.

Lamport signatures - cool I never heard of that until today. However, one property (I think) is that a keypair can only be used to sign something once (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message). Is this another reason you favor Lamport - to essentially mandate the single use of addresses to enhance privacy?

The system that deterministic wallets use is inherently linked to the elliptic curves.

If an alternative system is used (or a different curve), then deterministic wallets would no long work.  All funds would have to be moved to a new root.

Huh? What do you mean by determinstic wallets there?

Deterministic wallets are presumably also broken if ECC is broken?

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.

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.

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.

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.

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?

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.

Example 2 input, 2 output transaction size

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.

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

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

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.

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.

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.

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

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...

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-

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.

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-

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.