Bitcoin Forum
April 01, 2023, 08:22:25 AM *
News: New CAPTCHA now required before posting
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 [4] 5 6 7 8 9 10 11 »  All
  Print  
Author Topic: NSA and ECC  (Read 48418 times)
runeks
Legendary
*
Offline Offline

Activity: 966
Merit: 1008



View Profile WWW
September 11, 2013, 08:11:16 PM
 #61

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.
1680337345
Hero Member
*
Offline Offline

Posts: 1680337345

View Profile Personal Message (Offline)

Ignore
1680337345
Reply with quote  #2

1680337345
Report to moderator
1680337345
Hero Member
*
Offline Offline

Posts: 1680337345

View Profile Personal Message (Offline)

Ignore
1680337345
Reply with quote  #2

1680337345
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1680337345
Hero Member
*
Offline Offline

Posts: 1680337345

View Profile Personal Message (Offline)

Ignore
1680337345
Reply with quote  #2

1680337345
Report to moderator
1680337345
Hero Member
*
Offline Offline

Posts: 1680337345

View Profile Personal Message (Offline)

Ignore
1680337345
Reply with quote  #2

1680337345
Report to moderator
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 11, 2013, 10:16:36 PM
 #62


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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 508



View Profile WWW
September 12, 2013, 12:20:35 AM
Merited by ETFbitcoin (3)
 #63

Quote
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)

Quote
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
Legendary
*
Offline Offline

Activity: 966
Merit: 1008



View Profile WWW
September 12, 2013, 01:46:15 AM
 #64

Quote
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)

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

Quote
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
Hero Member
*****
Offline Offline

Activity: 602
Merit: 500


View Profile
September 12, 2013, 04:46:02 AM
 #65

sorry, but, what's the consensus

ok
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3864
Merit: 7355



View Profile
September 12, 2013, 05:12:12 AM
Merited by ETFbitcoin (3)
 #66

Quote
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
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
September 12, 2013, 05:15:27 AM
 #67

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.


Quote
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
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 12, 2013, 04:10:40 PM
 #68

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1185


May Bitcoin be touched by his Noodly Appendage


View Profile
September 12, 2013, 04:17:05 PM
 #69

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

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 12, 2013, 04:47:22 PM
 #70

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1002


Gresham's Lawyer


View Profile WWW
September 12, 2013, 07:02:56 PM
 #71


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.

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
piotr_n
Legendary
*
Offline Offline

Activity: 2053
Merit: 1310


aka tonikt


View Profile WWW
September 12, 2013, 07:12:46 PM
 #72


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? Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3864
Merit: 7355



View Profile
September 12, 2013, 07:17:27 PM
 #73

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
Sr. Member
****
Offline Offline

Activity: 364
Merit: 253


View Profile
September 13, 2013, 03:18:54 PM
 #74

It would be cool if the engineers of the agency will mine altcoins for fun! Tongue
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2347


Eadem mutata resurgo


View Profile
September 14, 2013, 03:50:07 AM
 #75

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

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
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 11:18:38 AM
Last edit: September 15, 2013, 12:14:04 PM by BurtW
Merited by ETFbitcoin (3)
 #76

Here is Jerry's response:

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:02:07 PM
Last edit: September 15, 2013, 12:19:17 PM by BurtW
Merited by ETFbitcoin (1)
 #77

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

Quote
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 Fq for cryptographic use, one must
ensure that the order #E(Fq) of the elliptic curve is divisible by a large prime
number n (say n >= 2160) in order to prevent the Pohlig-Hellman [22] and Pol-
lard's rho [23, 21] attacks. In addition, one must ensure that #E(Fq) != q in
order to prevent the Semaev-Satoh-Araki-Smart attack [26, 25, 28], and that n
does not divide qi - 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.


Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:27:05 PM
 #78

1) I believe that #E(Fq) of the elliptic curve is divisible by a large prime
number n (say n >= 2160) is true

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

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

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1185


May Bitcoin be touched by his Noodly Appendage


View Profile
September 15, 2013, 12:40:16 PM
Last edit: September 15, 2013, 01:01:34 PM by jackjack
 #79

What is n?

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1114

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:51:35 PM
 #80

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

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Pages: « 1 2 3 [4] 5 6 7 8 9 10 11 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!