Treefrog Enterprises Home
Click here for Wikipedia on ECC
--First step -- you must be this tall (at least) to make judgements about the security of Elliptic Curve Cryptography
Click to see the cartoon
The reason ECC is interesting is that you may not have to be very tall
to DEFEAT ECC - no one knows for sure. Asymmetrical warfare at its best.
If you thought I was going to have fun with Error Checking and
Correction algorithms, I apologize for the confusion. Maybe later.
Wed Sep 25 19:10:11 2013 - out of my league --
The paper I'm criticizing from Blackhat may not have been written by these luminaries but they are way above the type of person I would feel
comfortable criticizing and their names appear on the paper. Antoine Joux and Dan Boneh are top experts in the theoretical and practical
implementation of ECC. 'JasonP' and 'Ryan Winkelmaier' are two other people who may have been responsible for the atual writing of the paper
and who may be responsible for the L(1) complexity claim for ECC, versus the actual L(1/2) complexity of ECC. I apologize for any aspersions
cast or implied against Joux and Boneh.
I actually was not traveling, except on a journey of biochemical recovery from a ancer operation. I'm getting stronger every day and hope to
resume my role as a student of all aspects, practical and theoretical, of ECC, especially as regards the latest theoretical breakthrough. I
elieve ten of the 15 NIST standard ECC curves are compromised right now, but I'll try to characterize that for people at my level of
sophistication as my next project. I'm nowhere near 100 percent and also have a lot of work to do planning for my wife's continued
prosperity if things go wrong, but I'll move as fast as possible.
I also want to mention the spectacular breakthrough in speeding up quantum calculationsusing the Grassmannian versus Feynmann diagrams whic
came out last week . See the arxiv mix tape for this week for some comments on the possible scope of this discovery
Wed Aug 21 17:53:48 2013 - followup on ECC breakage --
I'm done with what was taking up so much time, but I have to travel tomorrow so I'll make this quick:
THERE IS NO WAY THE AUTHORS OF THE BLACKHAT ECC PAPER (SEE BELOW) COULD NOT HAVE KNOWN ECC WAS VULNERABLE TO ATTACKS
After I got started looking a few minutes ago (literally) I just googled a phrase I remembered: MOV attack.
That should get you all the references you need. If you just go to the Wikipedia ECC page, and search for MOV, you will also find the
baby-step, giant-step attack. Here's the difference between these two: only poorly chosen curves are vulnerable to MOV, although recent
breakthroughs may have influenced the numer of curves and the severity of theproblem if you use one of them. The baby-step, giant-step attack
is applicable to all elliptic curves and is a L(1/2) attack, which has been in existence for quite a while - SINCE 1978!!!
So contact the authors of the Blackhat paper and ask them what they mean by saying ECC is L(1). The difference between L(1) and L(1/2) is
that the key size has to be twice as long as the number of bits of security.
I have to run but I'll try to flesh this out later, and maybe do some stuff on the security of lattice-based crypto, too.
It is true that key sizes for ECC are smaller than for RSA, and that is why it is preferable. It is also true that the best L(1/3) and L(1/4) methods
do not yet apply to key sizes as small as those used in ECC today - at least up to a few weeks ago. The claim that ECC has not been
attacked, in the Blackhat ECC paper, is totally false.
It's good to be back.
Mon Aug 12 03:37:45 2013 -- What about lattice-based crypto?
The linkedin discussion got a good contribution today suggesting lattice-based crypto might be the last man standing if RSA and ECC fail.
I need to brush up on that. Both RSA and ECC have some lattice roots, and I know that hyperelliptic curve crypto has a vulnerability when the
genus is high. I'm not really the person to do the work. I just want to research the literature and see if these things are already broken or
just unpopular because ECC and RSA are getting all the research bucks. This is a marker to remind me to do some work as soon as possible and
I think there may be other subexponential attacks for ECC than the one below. I am still irked by the claim that ECC is L(1) in the Blackhat
slides, I just do not have the time to find the proof that this is false by looking through my stuff right now, maybe in a couple weeks I
can get back to this. I think ECC is broken a little bit already but not so bad as RSA, which is why each ECC bit gives much more protection
than an RSA bit. I don't like to make unsubstantiated charges, and it might be something I'm remembering wrong. Apologies beforehand if I
don't come up with a source for this claim in a couple weeks. Anyone more knowledgeable please email me.
Fri Aug 9 08:14:59 2013 -- so, am I right to say ECC is on shaky ground?
OK, the Blackhat talk made rosy assertions about the future of ECC.
I found a link which supports my assertion that 10 of the 15 NIST-approved elliptic curves are actually breakable in subexponential time.
"...Our analysis suggests that ECDLP over F(2^n) can be solved in time roughly 2^(cn^(2/3)log(n)) for some constant c<2, while the problem
was previously thought to be exponential. However, the result is mainly of theoretical interest so far. According to our estimations,
generic algorithms will be beaten for parameters n larger than 2000, far beyond the 160 bits security currently recommended for ECC...."
That link may be what I remembered. ellipticnews also says basically the same thing.
So is the Blackhat talk totally wrong? NO! The subexponential algorithm has some high overhead so that it is not competitive with current
exponential methods at the field sizes recommended by NIST. But I did not detect any reason not to expect that the breakeven point between
exponential (L(1)) and subexponential (L(0)) algorithms will not becoming down rapidly. And normal Moore's law speedups in computing will
eventually require larger fields for the same level of protection with ECC.
So the Blackhat paper is not wrong, but it is a little more optimistic about ECC than it should be, and I think people should worry about
EEC now rather than later.
I still haven't done anything to work out the details myself. With luck, I will find the answers on the Internet before I get time to work
them out myself.
Thu Aug 8 14:26:47 2013 -- threatpost podcast on Blackhat ECC talk
A podcast with Matthew Green, a cryptographer at Johns Hopkins, talking to Dennis Fisher, asserts there is no danger to ECC and that RSA should be
phased out in favor of ECC. Defending my position that ECC is also in danger is now a higher priority with me than it was a few days ago,
but unfortunately I have a couple of even higher priority items to tackle.
I agree that RSA is old, but I do not see that the recent advances attack RSA at all. Where I disagree is that I believe the recent advances
can speed up attacks on ECC. I will get on this as soon as I can. At the very least, I want to justify to myself the lack of alarm the rest
of the community seems to be trying to sell.
They then go on to talk about BREACH and some other general crypto issues. Lots of good information.
Thu Aug 8 04:10:45 2013 -- ECC 2013
The ECC 2013 conference will be in Belgium in September. Joux will speak on his
L(1/4) discovery, but no one cares about that. If I were in attendance I would want to know what he has been doing since then.
Several other talks look interesting. I have seen the slides and/or pdfs from several of the last few of these conferences and this does
seem to be the premier event for ECC theorists.
Tue Aug 6 21:02:32 2013 -- The 'pros' are picking up the narrative
It looks like the big boys waited until Blackhat to weigh in on the recent spate of cracks appearing in ECC, discrete log, and more
worrying, the possibility that it will also lead to breaking of RSA.
I am relieved that I no longer have to try to gain knowledge so rapidly to try to analyze the possibilities all by myself.
The first I heard of the big boys whipping up concerns over this was on Slashdot today, with a mention of this article.
Then in the Cryptography and Cryptanalysis group on linkedin I found a discussion based on this article.
The linkedin thread also has a link to a pdf of the original slides where indeed they claim that ECC is not hurt by the new developments.
Based on my reading of the original documents, and their admission that htyey are not real mathematicians, I hold firm in my claim that ECC
is more threatened right now than RSA. (I don't claim to be a real mathematician either, more like a mathematical investigative journalist.)
Until someone connects discrete log and factoring as subproblems of a parent problem, or until corresponding speedups
in factoring are actually found, the crypto problem is much, much worse than alluded to in the articles. ECC is used today in cell phones
and low power situations, and if it is fully broken there is no way to use RSA in those applications without sucking up a lot of battery
life. And ECC is definitely NOT the path to salvation for all of us to follow before RSA is broken.
I hope the wrong thrust of the articles is merely a mistake on the part of the presenters or the journalists, and not some sort of effort to
generate churn and revenue by deliberately misleading the crypto buying market. Don't run out and switch your RSA to ECC right now! Where
there is churn, there is malware on the lookout for mistakes, so we need to minimize that.
The problem is much more serious if RSA does fall. Not only do lots of encrypted documents become less secure, but then there is NO CLEAR
REPLACEMENT for crypto. Look for mathematicians and theorists specializing in crypto to get lots of grant money, hopefully. This is the
scenario where the introverted geek has to come up with something that saves the entire planet from chaos before the apocalypse comes, while
a band of hackers tries to destroy his credibility and distort his work, by burrowing into his encrypted identity before he can find a way
to protect it. Is Keanu Reeves too old? What about the Spiderman dude?
Both of these articles cover essentially the same news, and enlightened me in some ways. I still see a need to apply Joux's
algorithm to practical ECC to see if there are some hidden constants that mean the new breakthroughs only speed up cracking much larger DL
or ECC instances than are used in practice.
To do this requires that I learn a bit more, and I'm tied down right now by some exciting developments in another problem I'm interested in.
So bear with me. Hopefully for both of us, someone else will do the work before I do, and I'll only have to post it. Cheers.
Wed Jul 24 07:21:07 2013 -- UPDATE -- how broken is ECC????
Anyone looking in NIST SP800-57 Part 1 Rev 3 to figure out how long their
ECC-encrypted data will be safe should probably take the NIST recommendation
of year 2031 with a grain of salt. 2013 might be more like it depending
on which prime they used. B- and K- standard NIST curves should be
suspected of a large decrease in safety since about a month ago.
P-curves or RSA encryption are safer for now.
NIST just released a new version of FIPS 186-4 Digital Signature
Standard, which does not change its support for the B and K curves.
Wondering if I'm a little bit ahead of the curve for warning about this.
In my last post I mentioned most people are still using RSA, but there
are numerous vendors touting their ECC implementations. In my next post
I'll report on my efforts to get any comments out of Symantec and others
about how worried they are.
Also note this new IACR paper. I'm beginningto get the idea that the
new speed records carry some overhead since the sizes they can handle are much bigger than the NIST curve sizes.
I'll check and report on that soon as well.
Fri Jul 19 04:51:26 2013 -- UPDATE -- how broken is ECC????
It looks like for now the current success at breaking ECC discrete log are confined to 10 of the 15 NIST cirves.
(Specifically the binary and Koblitz curves for five finite fields based on high powers of two.)
My impression is that ECC in practice is still being adopted rather slowly and that RSA predominates right now, so the practical impact is not high.
(I'll beef this up with references later when I get time. Probably after today's stage of the Tour de France.)
No one has yet updated either the Wikipedia ECC page or the Wikipedia Discrete Log page. In all modesty I do not feel ready to make such changes myself.
If RSA is in use, the only danger is the bleeding over of success with discrete log into success with factoring, as described in my previous posting.
However the Network World article indicates some serious efforts to use ECC commercially.
(details on this to follow later today as well.
This wikipedia article has not addressed quasipolynomial breakage yet, but has the May advance by Joux, and a lot of other interesting material.)
Thu Jul 4 03:59:28 2013 -- ECC is broken?
I have some bad news and some worse news, all of which might actually be
At the Workshop on Number-Theoretic Algorithms for Asymmetric Cryptology,
a major breakthrough in the discrete logarithm problem was announced.
The complexity has gone from subexponential (2^an, where a < 1). to
quasipolynomial (2^x, where x is of the order of log(n)).
This is bad news for the people whose hopes for fast cheap low-power
cryptography were based on the difficulty of the discrete logarithm
problem. See the latest entries in the mostly Steven Galbraith blog
for an analysis showing that ECC is steaming towards an iceberg but has
not quite hit it yet. Another great blog about this is here.
Richard Lipton, a luminary in complexity theory has weighed in on Joux's L/4 algorithm
but not (yet) on the quasipolynomial result.
This is bad news for me personally as I am just beginning to understand
elliptic curves and elliptic curve cryptography well enough to comment
on these developments.
This is good news for me because I have been predicting this development
since around 2009 when the word on the street about ECC went -- SUDDENLY
-- from 'there is too much we do not understand about it' to 'it is perfect for
smartphones' based mostly on economic and profit motives rather than any
real new assurances that ECC was safe. So now 4 years later it seems
close to being irrevocably broken.
This is a serious situation. While we are still talking about long time
periods to crack a key, the time periods are about 1000 times shorter
now than they were just a few days ago. There is also a strong
possibility these developments will impact not only ECC but also RSA
(this is speculation on my part about RSA, but it already needs huge
keys relative to ECC).
This pretty much might eliminate public key crypto for the internet, unless
there is a version of TLS which uses ??? -- (As soon as I can I will insert
here a list of links to possible public key algoritms which have not yet
been broken) -- Even if there is, it would take time to upgrade everything needing an
What would happen to the world if online commerce suddenly ground to a
halt and transactions were required to be done in person and/or by
phone? What if no database was safe any more? Would the health care
industry have to backtrack from going paperless, and lots of other
industries follow them back into a world of paper records? It seems safe
to say that time just got more interesting, as in the Chinese curse: may
you live in interesting times. If you hate secrecy, wait until you try
the absence of secrecy, where every place in the world is just as scary
as any jungle or ocean.
The good news part of this is that my world may go back to the way it was before I
got sucked into the surge of interest in ECC, and I can go back to
working on small math problems without too much importance to the world.
Fri May 31 04:20:46 2013
If you have been following along, the latest in what should seem to you to be a
scarily-rapid series of advances in the ability to crack elliptic curve crypto
eliminates one half of the types of pairing-based algorithms, those implemented
in base 2 or other small primes. See here for the expert,
or here for a more accessible summary of Joux's work.
Sat May 4 19:32:07 2013
The 'L/4' result below is a major breakthrough, but with a major caveat:
it only works for a highly restricted range of finite field
characteristics and exponents (so far). Nevertheless, the importance of
the result can be gleaned from the fact that despite its newness it is
also being mentioned in several recent arxiv and iacr postings. The big
question people are trying to track down is where the L/4 algorithm
becomes more efficient than the other recent advances, which are
improvements to the 'Function Field Sieve' index calculus method, which
has been around longer and is better understood. Stay tuned here for
Sun Apr 28 05:23:59 2013
Recent startling developments in discrete logarithms should be mentioned here. I'm
no expert but when
- researchers go from discrete logarithm records of 600 bit numbers to
discrete logarithm records of 6000 bit numbers in a matter of days,
- other researchers devise a breakthrough from 'L/3' to 'L/4'
algorithms (essentially meaning that you can now compute the discrete
logarithm on numbers 4/3 longer than before in the same time),
people who are worried about security and encryption should pay close
attention to these rather stunning advances.
I'm pedaling as fast as I can but not even the real experts can yet say
how soon these developments will impact practical cryptography. As I
find out more I'll add to this page.
I'll also add a sentence or two on
the relation of the discrete logarithm problem and the integer factoring
problem, as soon as I get around to it.