NSA and ECC

[runeks]

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.

How large are Lamport signatures with security equal to 256 bit ECDSA?

Also, would there be any reason not to get this into Bitcoin right now? Instead of waiting for cryptography doomsday? The addition of new opcodes shouldn't impact the security the existing ones, so as far as I can see we're only adding an option for the paranoid.

But maybe that's the exact issue. Without making this new scheme the default one, there's really no reason to add it now, instead of waiting to see if secp256k1 is compromised and then adding it. If no one is using it it won't really be tested anyway.

[1714943745]

1714943745

[1714943745]

1714943745

[1714943745]

1714943745

[1714943745]

1714943745

[1714943745]

1714943745

[1714943745]

1714943745

[BurtW]

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.

Done.

Waiting for a response.

[fpgaminer]

How large are Lamport signatures with security equal to 256 bit ECDSA?

256-bit ECDSA has a security strength of 128-bits under classical computing.  Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB.  The public keys would be 4 KB. (Source)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)

Also, would there be any reason not to get this into Bitcoin right now?

I would say the size of the signatures would be one reason.  The inability to re-use them being another.  What if you received bitcoins to a Lamport derived address after you already spent from it?  Now you can't spend the extra bitcoins.

Also, are Lamport signatures going to offer significantly more protection than one-time ECDSA with pay-to-hash?  Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block.  Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes?

Seems like the real issue is that broken ECDSA will break BIP32, our means of allowing convenient one-time-addresses.  And BIP32 can't be applied to Lamport, so Lamport doesn't help here either.

[runeks]

How large are Lamport signatures with security equal to 256 bit ECDSA?

256-bit ECDSA has a security strength of 128-bits under classical computing.  Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB.  The public keys would be 4 KB. (Source)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)

Thanks. Does that also apply when using a Merkle hash tree over your public keys? If I understand gmaxwell's description, a public key reusable at least 1024 times would be 128 bits + log2(1024)=10 * 128 bits = 176 bytes.

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)

Also, would there be any reason not to get this into Bitcoin right now?

I would say the size of the signatures would be one reason.  The inability to re-use them being another.  What if you received bitcoins to a Lamport derived address after you already spent from it?  Now you can't spend the extra bitcoins.

As gmaxwell points out, security decreases for every additional signature you publish made with the same key. It's not like it disappears all at once.

Also, are Lamport signatures going to offer significantly more protection than one-time ECDSA with pay-to-hash?  Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block.  Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes?

That is a good point. I'd be inclined to say it's not worth it yet.

[superduh]

sorry, but, what's the consensus

[gmaxwell]

How large are Lamport signatures with security equal to 256 bit ECDSA?

256-bit ECDSA has a security strength of 128-bits under classical computing.  Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB.  The public keys would be 4 KB. (Source)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)

In Bitcoin the public key would be part of the signature, when both are sent together there are several 'compression' schemes you can apply which allow you to avoid specify unneeded parts of the keys (since both are tree structured), you can do something which has 256 bits of QC security in about 11kbytes.  This also benefits reducing the size of the public key to a single hash— addresses would be no longer (or only somewhat longer, for 256 bit ones) than the addresses we use today.

There is no severe reuse issue, for a very minor increase in size you use a merkle signature scheme, where you have a tree of lamport keys. This significantly reduces the reuse problem. In the context of Bitcoin some reuse would also not be completely fatal.

You could very nearly implement lamport signatures in our existing script with no special functionality at all, we're basically only missing code to push the raw data-to-be-signed onto the stack... though doing it that way wouldn't get you public key compression.

I'm not sure if we should implement such things prophylacticly: It would be great to have an already deployed answer to "OMG WHAT ABOUT QCs?!" or "OMG WHAT IF NSA ECDSA?!"... but I suspect a lot of people who would ask such things aren't really looking for answers.  Our common infrastructure is also very sensitive to size— my "structure it so you can forget old signatures" is a major security model change which might have severe economic consequences in the long run... and additional block-chain bloat absolutely would have consequences. So ::shrugs::.

[Etlase2]

Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block.  Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes?

It depends on how ECDSA is broken. It also depends on how ECDSA is used. While using pubkeys only once is "recommended", it is certainly not a requirement, and it is not possible to predict how ECDSA will be used by the bitcoin protocol in the future. But if discrete logarithm problem over elliptic curves stops being "hard", only the pubkeys are necessary, and they will probably be broken at break-neck speed. If it is a weakness with the signatures revealing information (much more likely), it will take time, but reused pubkeys are at serious risk.

I would say the size of the signatures would be one reason.  The inability to re-use them being another.

Well Merkle-Lamport constructions are probably what is of interest. On the bright side, the pubkey is only n bits where n is the security level.

However, there is research into merkle + one-time sig schemes with smaller signatures.

"On the Security of the Winternitz One-Time Signature Scheme" by Buchmann et al shows signature sizes of about 800 bytes for 129-bit effective security level at a Winternitz parameter of 16 (increasing it raises the difficulty of creating signatures, but makes the signatures smaller and weaker, I don't know the exact tradeoffs). 800 bytes is well within reason for a QC-resistant signature algo (although it might have to be more depending on how many qubits are available to crack hash algos). It is still a significant hurdle though for world-wide use, and will obviously increase the costs of running the network significantly.

[BurtW]

While everyone is gathered here I have a quick easy question.  I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course):

https://en.bitcoin.it/wiki/Secp256k1  

However, this wiki page states that the valid private keys are specified by the parameter n:

https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys

Either I need to be fixed (ouch!) or the wiki needs to be fixed.

[jackjack]

While everyone is gathered here I have a quick easy question.  I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course):

https://en.bitcoin.it/wiki/Secp256k1 

However, this wiki page states that the valid private keys are specified by the parameter n:

https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys

Either I need to be fixed (ouch!) or the wiki needs to be fixed.

The correct number is n as G^(n+1) = G

[BurtW]

While everyone is gathered here I have a quick easy question.  I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course):

https://en.bitcoin.it/wiki/Secp256k1 

However, this wiki page states that the valid private keys are specified by the parameter n:

https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys

Either I need to be fixed (ouch!) or the wiki needs to be fixed.

The correct number is n as G^(n+1) = G

Bummer.  I have been quoting the wrong number for almost two years now.  I sure wish someone had corrected me at some point.  Embarassing.

[NewLiberty]

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.

Done.

Waiting for a response.

Thank you for this.

[piotr_n]

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.

Done.

Waiting for a response.

Thank you for this.

I'm betting they won't say.
Who's in?

[gmaxwell]

Presumably, since it was government work,  it should be possible to FOIA any records they have relating to the procedures they used to generate those ECC parameters.

If no secret information was used to select them, e.g. strengthening or weakening the selection there should be no reason for the result to be classified.

If we don't get a response with a casual request we could try the FOIA route. Might be fun.

(As an aside: I think that there is weak evidence that they didn't use the selection to strengthen the curves as there are criteria by which these curves are considered weaker (see the Brainpool curves RFC for the extra criteria they used))

[balanghai]

It would be cool if the engineers of the agency will mine altcoins for fun!

[marcus_of_augustus]

It would be cool if the engineers of the agency will mine altcoins for fun!

Would be even cooler if they just fucked off and died and left the rest of us alone to do the right thing .... just saying.

[BurtW]

Here is Jerry's response:

Hello Burt,

  I have looked at the SECG standard you pointed to.  The secp256k1 curve is not one of the NIST curves, and I'm afraid I had nothing to do with it.  It uses the technology described in the Crypto 2001 paper by Gallant, Lambert, and Vanstone (https://www.iacr.org/archive/crypto2001/21390189.pdf).  Since the authors were all affiliated with Certicom, and Certicom was the main partner in the SECG consortium, I'm guessing the Certicom folks came up with that curve.  I would suggest getting in touch with one of them for more info on where the particular parameters came from.

Regards,

-- Jerry S.

I have emailed all three authors.

[BurtW]

From the referenced paper I would expect our curve to at least satisfy these criteria:

5 Security Considerations

Elliptic curves having effciently-computable endomorphisms should be regarded
as "special" elliptic curves. Using "special" instances of cryptographic schemes
is sometimes done for effciency reasons (for example the use of low encryption-
exponent RSA, or the use of small subgroups hidden in a larger group as with
DSA). However in any instance of a cryptographic scheme, there is always the
chance that an attack will be forthcoming that applies to the special instance
and signifcantly weakens the security. Such is the case here as well.

When selecting an elliptic curve E over F_q for cryptographic use, one must
ensure that the order #E(F_q) of the elliptic curve is divisible by a large prime
number n (say n >= 2¹⁶⁰) in order to prevent the Pohlig-Hellman [22] and Pol-
lard's rho [23, 21] attacks. In addition, one must ensure that #E(F_q) != q in
order to prevent the Semaev-Satoh-Araki-Smart attack [26, 25, 28], and that n
does not divide qⁱ - 1 for all 1 <= i <= 20 in order to prevent the Weil pairing [16]
and Tate pairing attacks [8]. Given a curve satisfying these conditions, there is
no attack known that signifcantly reduces the time required to compute elliptic
curve discrete logarithms. Many such curves having effcient endomorphisms ex-
ist and hence appear suitable for cryptographic use. One attack on the elliptic
curve discrete logarithm problem on such curves is along the lines of [9] and [34].
The application of such ideas does not reduce the time to compute a logarithm
by more than a small factor.

The number of curves for which this technique applies seems to be reasonably
large. For instance, one of the Examples 3, 4, 5 and 6 provide a candidate for
most primes p.

[BurtW]

1) I believe that #E(F_q) of the elliptic curve is divisible by a large prime
number n (say n >= 2¹⁶⁰) is true

2) I believe that #E(F_q) != q is true [#E(F_p) != p in our case]

3) n does not divide qⁱ - 1 for all 1 <= i <= 20

We would need to write a small program to verify the last one.

[jackjack]

What is n?

[BurtW]

q = p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141