We care about bitcoin's curve ;p
Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.OpenPGP ECDSA uses those curves right? (and the 512r one too)
Topic: NSA and ECC - page 7. (Read 48727 times)
OpenPGP ECDSA uses those curves right? (and the 512r one too)
We care about bitcoin's curve ;p
Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.
We care about bitcoin's curve ;p
So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.
From all the recent revelations it appears that NSA operates also by proxies and shills in private and academic institutions who push the NSA agenda.
Ok, our friend Dan at SECG is really trying to dig into this and find out exactly how the random curves were generated. He has asked me to narrow down the search to the curves we are actually interested in so he does not waste time researching curves we do not care about.
So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.
Here is what he has done and found out so far in his preliminary analysis:
So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.
Here is what he has done and found out so far in his preliminary analysis:
Quote
Yesterday, I dug a little into this:
I extracted the seeds from the LaTeX source, using a not very careful grep search, and found 22 seeds (some of which are now commented out in SEC2). I may have missed some seeds whose LaTeX did not match my criteria.
Twelve seeds contain the ASCII string “MinghuaQu”, but in some cases they are shifted by 4 bits. I concluded that these 12 were not NIST curves, and that the remaining 10 curves must be NIST curves.
I believe that the 12 seeds containing “MinghuaQu” are curves are mostly 163 bit or smaller, so I doubt that you are considering them.
So far, I have not detected any clear pattern in the remaining ten seeds, but I have not tried hard, mainly I suspect that they are the output of some PRNG, and therefore such tests would likely fail. My main check so far was to compare the sorted set of byte frequencies among the 400 seed bytes to the same statistic for random sets of 400 pseudorandom bytes. A few trials of the random sets had a higher maximum frequency, and some had a lower maximum frequency. I did not calculate any kind of P-test. The point of this test was to see the seeds were some byte-encoding which might favour some particular bytes. I have done to nothing examine the order of the bytes.
Again: many of the smaller curves are now absent from SEC2 version 2.0, which has 11 random curves, 10 of which are NIST curves.
Best regards,
Dan
I extracted the seeds from the LaTeX source, using a not very careful grep search, and found 22 seeds (some of which are now commented out in SEC2). I may have missed some seeds whose LaTeX did not match my criteria.
Twelve seeds contain the ASCII string “MinghuaQu”, but in some cases they are shifted by 4 bits. I concluded that these 12 were not NIST curves, and that the remaining 10 curves must be NIST curves.
I believe that the 12 seeds containing “MinghuaQu” are curves are mostly 163 bit or smaller, so I doubt that you are considering them.
So far, I have not detected any clear pattern in the remaining ten seeds, but I have not tried hard, mainly I suspect that they are the output of some PRNG, and therefore such tests would likely fail. My main check so far was to compare the sorted set of byte frequencies among the 400 seed bytes to the same statistic for random sets of 400 pseudorandom bytes. A few trials of the random sets had a higher maximum frequency, and some had a lower maximum frequency. I did not calculate any kind of P-test. The point of this test was to see the seeds were some byte-encoding which might favour some particular bytes. I have done to nothing examine the order of the bytes.
Again: many of the smaller curves are now absent from SEC2 version 2.0, which has 11 random curves, 10 of which are NIST curves.
Best regards,
Dan
Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner.
FOIA only applies to the US government agencies, it is irrelevant in the context of secg, fujitsu, certicom,etc. You might be able to get something from the US-based governmental member (NIST).
I'd already tried hextoasciiing the p256r curve's seed, before ever commenting on it, no such joy. (I'd also hoped to find a similar answer to our generator, but no such question, as the message said though— the generator isn't a known cause for concern, as you can generally convert numbers relative to one generator relative to another trivially. I'd though perhaps the generator would result in low hamming weight in the multiplies, allowing some stems to be avoided but it seems not)
Anyone have contact info for MinghuaQu ?
Here is a suggestion from Dan on the seeds for the random curves: Convert them to ASCII and see what pops!
It would be fun to convert all the seeds we can find, especially the seeds used for the curves we are interested in, to ASCII and see what is there.
Quote
Hmm,
I just checked some of the seeds for the non-NIST random curves in SECG.
I noticed that some of the seeds look similar to each other, and had very non-random looking hex representations. So, I just converted them to ASCII, and noticed that a large middle portion of some of the seeds contain the string “MinghuaQu”, which is the name of one of the inventors of MQV, and the person who was generating the seeds. I would not be surprised if the remainder of the seeds also had some meaning, with just a little part left for the necessary searching. If so, then the curves are really nothing-up-sleeve type values. Unfortunately, most of these curves may be too small by today’s recommendations.
Best regards,
Dan
I just checked some of the seeds for the non-NIST random curves in SECG.
I noticed that some of the seeds look similar to each other, and had very non-random looking hex representations. So, I just converted them to ASCII, and noticed that a large middle portion of some of the seeds contain the string “MinghuaQu”, which is the name of one of the inventors of MQV, and the person who was generating the seeds. I would not be surprised if the remainder of the seeds also had some meaning, with just a little part left for the necessary searching. If so, then the curves are really nothing-up-sleeve type values. Unfortunately, most of these curves may be too small by today’s recommendations.
Best regards,
Dan
It would be fun to convert all the seeds we can find, especially the seeds used for the curves we are interested in, to ASCII and see what is there.
Does anyone have a copy of ANSI X9.62 I can borrow? Or does anyone know of a free link? I would like to read it but don't really want to shell out the $100 for it.
Have not read it yet but this looks to be interesting: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf
Part:
Since ANSI X9.62 was accepted into IEEE as 1363-2000 I can probably get it there since I am a member.
Have not read it yet but this looks to be interesting: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf
Part:
Quote
The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue
of the DSA. ECDSA was first proposed in 1992 by Scott Vanstone [108] in response
to NIST’s (National Institute of Standards and Technology) request for public comments
on their first proposal for DSS. It was accepted in 1998 as an ISO (International
Standards Organization) standard (ISO 14888-3), accepted in 1999 as an
ANSI (American National Standards Institute) standard (ANSI X9.62), and accepted
in 2000 as an IEEE (Institute of Electrical and Electronics Engineers) standard (IEEE
1363-2000) and a FIPS standard (FIPS 186-2). It is also under consideration for inclusion
in some other ISO standards. In this paper, we describe the ANSI X9.62
ECDSA, present rationale for some of the design decisions, and discuss related security,
implementation, and interoperability issues.
of the DSA. ECDSA was first proposed in 1992 by Scott Vanstone [108] in response
to NIST’s (National Institute of Standards and Technology) request for public comments
on their first proposal for DSS. It was accepted in 1998 as an ISO (International
Standards Organization) standard (ISO 14888-3), accepted in 1999 as an
ANSI (American National Standards Institute) standard (ANSI X9.62), and accepted
in 2000 as an IEEE (Institute of Electrical and Electronics Engineers) standard (IEEE
1363-2000) and a FIPS standard (FIPS 186-2). It is also under consideration for inclusion
in some other ISO standards. In this paper, we describe the ANSI X9.62
ECDSA, present rationale for some of the design decisions, and discuss related security,
implementation, and interoperability issues.
Since ANSI X9.62 was accepted into IEEE as 1363-2000 I can probably get it there since I am a member.
I think you guys got a wrong idea.
I was not criticizing the guy who wrote that email - not at all.
In fact I also find him as a very nice and sincere person who is trying to help.
Still, it does not help us at all, does it?
So let me quote again what I believe all the other answers concerning this issue will be about:
Making the sarcastic comment, my only point was: if anyone will manage to get an answer that goes beyond what I had already figured, then we can talk..
I will be more than happy to turn out as an asshole again, if this is the price for finding out where these values come from.
And if we don't ever get to know how the values in question were chosen - well, feel free to perceive me as an asshole, anyway.
I was not criticizing the guy who wrote that email - not at all.
In fact I also find him as a very nice and sincere person who is trying to help.
Still, it does not help us at all, does it?
So let me quote again what I believe all the other answers concerning this issue will be about:
Quote
Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about.
Making the sarcastic comment, my only point was: if anyone will manage to get an answer that goes beyond what I had already figured, then we can talk..
I will be more than happy to turn out as an asshole again, if this is the price for finding out where these values come from.
And if we don't ever get to know how the values in question were chosen - well, feel free to perceive me as an asshole, anyway.
Sorry BurtW, but I totally disagree.
What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?
This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...
What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?
This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...
His answer appears honest (at least so far as we've been able to check), rather than arguing from authority as you claimed. He admits what he doesn't know, and why. He made reasonable guesses at some points and stated they were such.
I agree that the answer is not perfect nor complete, but neither was your characterization of it accurate. Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner.
It might look different were it a submission to a peer reviewed journal and meant to withstand critical review, instead it was a VERY swift and candid response at no benefit to himself. Gratitude is warranted.
What you are seeking (a justification of values along with the path taken to calculate) may yet come, but that will take them some research and effort. Just our asking for this may stimulate such an effort. We are helping to guide them to do more meaningful work in light of the current reports and questions raised.
Sorry BurtW, but I totally disagree.
What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?
This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...
What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?
This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...
piotr_n:
Your post is totally unfair and uncalled for. Having been a contributing member of several technical specifications I can assure you that his email rings true. Just try to find out how any decision was made on any technical specification and you will find that most of the decisions and grunt work are done by emails, phone calls, hallway conversations, conversations over meals during face to face meetings, etc.
Unless you actually participated in the decision the reason for most technical decisions in all the technical specifications I have worked on would be almost impossible to find. For example, one time we were having a problem where the disk drive I was designing would not properly work in master/slave mode with a competitor’s disk drive. I called up the competitor’s lead architect and we re-designed the master/slave protocol right there, on the spot, over the phone. Our two companies implemented it and it eventually found its way into the ATA specification and is still there to this day.
The fact that the prime selected has the highest possible value of t lower than 1024 looks to be the answer to that particular question – unless we can find the person who actually selected the prime number, or the people present in the meeting that day when he presented the number and explained his selection to them.
This guy did not need to take the time to answer my query. He did not know me from Adam. If the situation was as you described he would have simply not answered my email and been done with it.
TierNolan:
Thanks for that! Great work!
Your post is totally unfair and uncalled for. Having been a contributing member of several technical specifications I can assure you that his email rings true. Just try to find out how any decision was made on any technical specification and you will find that most of the decisions and grunt work are done by emails, phone calls, hallway conversations, conversations over meals during face to face meetings, etc.
Unless you actually participated in the decision the reason for most technical decisions in all the technical specifications I have worked on would be almost impossible to find. For example, one time we were having a problem where the disk drive I was designing would not properly work in master/slave mode with a competitor’s disk drive. I called up the competitor’s lead architect and we re-designed the master/slave protocol right there, on the spot, over the phone. Our two companies implemented it and it eventually found its way into the ATA specification and is still there to this day.
The fact that the prime selected has the highest possible value of t lower than 1024 looks to be the answer to that particular question – unless we can find the person who actually selected the prime number, or the people present in the meeting that day when he presented the number and explained his selection to them.
This guy did not need to take the time to answer my query. He did not know me from Adam. If the situation was as you described he would have simply not answered my email and been done with it.
TierNolan:
Thanks for that! Great work!
The explanations are exactly like the one I had expected to be. I am quite sure you would receive a very similar ones from NIST.
It all can all be wrapped in one sentence:
Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about.
Professional scientists like hell
It all can all be wrapped in one sentence:
Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about.
Professional scientists like hell
I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected.
I did a quick check on this assumption
Quote
Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check.
The test code finds all primes of the form p = 2^256 - 2^32 - t where t < 1024.
Code:
import java.math.BigInteger;
public class PrimeTest {
public static void main(String[] args) {
BigInteger a = BigInteger.valueOf(2).pow(256);
BigInteger b = BigInteger.valueOf(2).pow(32);
BigInteger top = a.subtract(b);
for (int t = 0; t < 1024; t++) {
BigInteger test = top.subtract(BigInteger.valueOf(t));
if (test.isProbablePrime(1024)) {
System.out.println(test.toString(16) + " (t = " + t + ")");
}
}
}
}
The result is
Code:
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99 (t = 359)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97 (t = 361)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19 (t = 487)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d (t = 739)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b (t = 949)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f (t = 977)
The prime for t = 977 is the one that was selected for the curve. It is the highest t that is lower than 1024.
Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe".
I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre.
I am totally impressed by the calibre of the math, programing and cryptographers we have already. Just read this very thread.I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected.
I am waiting for responses to my emails on that subject.
I am similarly more than impressed with the abilities of our current development team. What I'm suggesting is a dedicated team for long-term analysis and theoretical work, not only accomplished software developers that have well honed cryptography knowledge who apply pre-existing work to this project. You'll notice if you look at the SCIP thread that one well seasoned developer admits to being out of his depth at a certain stage, and he's certainly a capable developer.
The answers he gives can be interpreted as given, but could also be a well devised evasion tactic, although there is no way of knowing for certain at this stage. I commend that you did this, despite any misgivings. As I say, it could be that he is being totally upfront and honest, so whatever the eventual assessment, you have done us all a service.
Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe".
I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre.
I am totally impressed by the calibre of the math, programing and cryptographers we have already. Just read this very thread.I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected.
I am waiting for responses to my emails on that subject.
This is the reply I got form Dan Brown the current SECG chair:
Quote
Hi Burt,
[...]
I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.
[...]
I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.
Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe". Well, I suppose he could've skimped on information, and he certainly did not do that. But lines like the bolded text are concerning; you'd think they would be pretty meticulous, given that any rogue mathematician who deliberately did not disclose or document flaws and promptly moved to China for a "quiet retirement" could be a candidate for the "disposition matrix"
. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre. At least in the more medium term that is. I fail to see how contributing mathematical prowess to the fundamental substance of what could morph into the 21st century monetary system couldn't attract the right talent. And the average Bitcoiner has to pay how much to join, only to discover this is not happening for whatever reason? This should be a serious endeavour, and their current focus is a political meat shield. [/cynical bullishness]
Very interesting, thanks for that Burt.
Jump to: