Teaching myself Elliptic-curve cryptography

Public-key cryptography is useful because it allows the production of two related cryptographic keys; one which may remain private, while only the corresponding public key must be made known to another party. This increases the security of the private key since the private key may be used without sharing that key with any other party.

There are two main popular algorithms used in asymmetric (public key) cryptography:

* “RSA” (initials of its inventors Rivest, Shamir and Adelman )
* “EC”, or elliptic curve

The security of these algorithms depend upon two different specific mathematical things being “hard” to compute:

* RSA depends on it being computationally difficult to generate “prime
factors”

* EC depends on the hardness of solving the “discrete logarithm” problem over an “elliptic curve” (where a curve is the result of computing a function over a set of numbers called a “field”)

In practice, mathematical advances (number field sieve functions) have led to it becoming ever easier to factor prime numbers, lowering the computational cost. This has led to the need to continually increase the size of RSA keys in order to continue to make RSA cryptography hard to break. Increasing the size of keys, generally-speaking, will
decrease performance of a crypto-system.

Since EC cryptography does not depend on the difficulty of factorization, and also because it is much computationally harder to solve the elliptic curve discrete logarithm problem (ECDLP) with much smaller key sizes than are needed to provide equivalent security with
RSA, EC has recently become popular.

Some potential problems exist with EC-based systems:

* The security of EC-based systems does not depend solely on ECDLP. As EC has been little used or analyzed (relative to RSA), it is likely that there exist significant flaws in EC implementations (e.g. OpenSSL). It is not clear though whether these are of any more
consequence than previous non-EC-related flaws, such as the OpenSSL Heartbleed bug — so far, they have not been.

* In order to enable interoperability between implementations, standards exist for which curves should be used for EC cryptography. These standards have, so far, been published by NIST, a US government agency, currently in disrepute due the Snowden revelations. It is alleged that NSA representatives chose particular facets of the NIST standards in order to weaken crypto-systems using these curves. There is no actual evidence of this, although there is evidence, in the standards themselves, that the particular curves
chosen were chosen more for “efficiency” than “security”. Some reputable cryptographers (Lange, Bernstein) have provided plausible explanations for why _implementations_ of the NIST curves may be insecure. As of the writing of this document though, no known
practical attacks have been revealed.

* There have been few implementations of cryptography based on EC, and there appears little interoperability between implementations (except where they rely on the same library  – ie. OpenSSL). Further, encryption using EC is poorly standardized (ECIES is the only “standard” I can find)

* The NIST-standardized DUAL_EC_DRBG random number generator, which is also based on hardness of ECDLP, has a significant documented weakness, which has led to the widespread belief that this RNG has been backdoored by NSA. It should be noted that just because this RNG uses the same mathematical properties as EC cryptography, this does not imply that there is necessarily any property which transfers to non-RNG uses of ECDLP.

Recommendations
————————-

* Do not use the DUAL_EC_DRBG random number generator in your own code, since it is proven insecure (ie. do not use OpenSSL FIPS module, BSAFE or the MSFT S-Connect libraries). It is also possible to use EC cryptography WITHOUT using the DUAL_EC_DRBG RNG., since DUAL_EC_DRBG is only one of the NIST-approved RNGs.

* TLS clients: do not negotiate TLS EC ciphersuites with SSL/TLS servers since you cannot be sure that the server is not using the DUAL_EC_DRBG? @@TODO: investigate this some more! Is DUAL_EC_DRBG an option for non-EC ciphersuites?

* If you wish to have interoperability with external partners, use the NIST-specified EC curves (FIPS 186-4), as implemented in OpenSSL and BouncyCastle; specifically the P-244 curve appears to be a reasonable choice for efficiency.

* If you control all parties in the crypto-system, you may use Bernstein’s p25519 curve, but will be on your own when it comes to implementing encryption, since there is no current standard for encryption that uses curves other than the NIST curves.

* Unless your threat model includes attack by state actors, it is probably safe to assume that you are currently safe from other attacks that rely on any fundamental weakness in EC cryptography, or particular curves. You are less safe from implementation flaws in
any library or code you are using, but this is a common problem in all use of cryptography, no matter how commonly used (see Heartbleed).

References
—————

“What a difference a prime makes” – https://www.imperialviolet.org/2010/12/21/eccspeed.html
“NIST FIPS 186-4″ – http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
“Safe Curves” http://safecurves.cr.yp.to/
“Random Curves” – http://books.google.com/books?id=p2QalcsaNtIC&pg=PA312&lpg=PA312&dq=Jerry+Solinas+nsa&source=bl&ots=E0OF9z4lpJ&sig=V033idQQ4XafSzj70GvjPtcOpT8&hl=en&sa=X&ei=6c4RVM7WDqW1sQTwqYLwAg&ved=0CB0Q6AEwADgK#v=onepage&q=Jerry%20Solinas%20nsa&f=false
“Openssl ECIES example” – http://stackoverflow.com/questions/1152555/encrypting-decrypting-text-strings-using-openssl-ecc
“Google End-to-End” – https://code.google.com/p/end-to-end/
“OpenPGP ECC standard” – http://tools.ietf.org/html/rfc6637
“Dual EC in TLS” – https://projectbullrun.org/dual-ec/documents/dualectls-20140606.pdf

Jack Bristol Lake Waramaug 50 mile race report

The day didn’t start so well. After a fitful but pretty reasonable 6 hours sleep, I got up at 4:30am to make the drive down to Lake Waramaug. It should have been pretty easy. Maybe it was too easy. Before I knew it I had missed a turn and had no idea where I was going. Car GPS didn’t bat an eyelid, and just rerouted me without even letting me know. There I was visualizing myself coming across the finish line in my first 50 mile race. Aren’t you supposed to do that? OK, maybe not while you’re driving to the race.

Fortunately, I had allowed plenty of time, and still got there early enough for my pre-race prep. It was so cold (36F) that I stayed in the car mostly, but spent time a little time talking to some of the other runners who had driven from all over to be at this race.

WP_20140427_001

Jack Bristol Lake Waramaug is a historic ultramarathon. They’ve been running this race for 40 years now, and many of the sport’s old-time legends have run here. Now that ultras are trendy, and trails are the thing, attendance has dropped for the longer races. But still. 50K, 50M and 100K races around a lovely lake in northern Connecticut. At worst, it’s a lovely day out!

We were off promptly at 7:30am. My plan was just to run lightly, arms low and feet quiet, keeping somewhere close to a 9:45 min/mile pace. Through the first 4.4 mile out-and-back I did that pretty much perfectly – 41 minutes for that stretch. Now for the big stuff – 6 loops of 7.6 miles each.

I was in my Luna Mono sandals with a pair of Injinji toe socks. After the tests I did last week, I thought I could at least start the race in them, but I had put my GRUs in the drop bag for later in the race. Turns out that was a great idea because, you know, sandals and socks?!

The first real loop passed by without incident. I met a couple of people I would run with for the next couple of laps — Aaron, who was doing the 50 mile, and another guy whose name I never found out who was doing the 50K.

By the time we’d gone around almost two loops together though, we started to talk about pace, and Aaron said we were averaging 8:16 minute miles! I almost choked. I run by feel so apart from the race timer I’d see once a lap, I didn’t pay much attention to the pace. Anyway, at that point, I told them that I was going to slow down a bit. But at the end of loop 2, I was still a whopping 13 minutes ahead of schedule already! A bit before I came to the end of that lap I had decided that I was going to swap out of the Lunas because I could feel that the road miles were already making my legs very sore. I figured that with this huge cushion on my time I could take a 5 minute break and change shoes no problem at all. So, after 20 miles, I sat on the bank by the finish and changed shoes and socks. It felt so good!

Getting up after sitting down though did not feel so good. My heart rate went through the roof and it took me most of the next 4 miles to recover to the point my breathing felt normal.

One of the major selling points of this race are the aid station volunteers and the food on offer. I brought plenty of food with me, but I basically didn’t eat any of it. I’d decided to stay off the sugar train for as long as possible – at least the first 30 miles. Two egg wraps, some bacon, a few chips and water were what I ate up to the marathon distance. At my favorite aid station though half-way round the lake, I discovered my best running fuel ever – chicken broth. It was hot, so I took an extended walking break to down it, but it gave me so much energy! I fair pounded the last miles around that loop, ran the full marathon a shade under 3:58 (approximate, based on one of the very few road markers) and came around loop 3 for almost 28 miles in a touch under 4:13. I also passed Aaron for good around that point. He had apparently slowed and didn’t run with me when I came out of the aid station. I asked him if he was OK and he said yes, so I carried on.

Loops 4 and 5 were tougher. I had decided that I should walk in order to save energy for the last loop. As I was still on course to beat even my best goal, it seemed reasonable. So I walked the half mile at the mid-way aid station to drink my chicken broth, and I walked through the finish line section. Far from being helpful though, these walking breaks turned out to be such a bad idea for me. I started to feel like my legs would cramp when I would start running after walking! At first, I thought that maybe I didn’t have enough electrolytes in me, so I started up on the Gatorade — and continued with the chicken broth! Two pieces of banana and a few chocolate raisins too. I kept my footfalls loose, somehow, and my legs never actually cramped, but each time I walked, the running afterwards would suck. By the end of loop 5 I had realized that I simply couldn’t walk any significant distance if I wanted to be able to run afterwards. So although my pace had dropped significantly in loop 5, I actually started to pull it together at the end of that loop. I passed one of the old-timers (he has done this race every year since 1976!) doing the 100K race. He told me that the way I was going I could break 8 hours if I just kept a steady pace for the last lap. I wished him the best, and took off. Now that I had worked out that I shouldn’t walk, running was again easy! I couldn’t believe it. I was really going to finish. Just one more lap. I came through loop 5 in 6:45, knowing that I had to do a 75 minute lap to break 8 hours. If I could just avoid walking, I would do it. And even if I walked, well, I was going to finish, no matter what.

I didn’t even walk through the aid stations except the 3 steps it would take for me to drain a Gatorade and grab a banana piece. And coming around the back stretch it was all looking good until a couple of miles before the finish line, when I was suddenly incredibly tired. But I knew I couldn’t walk for more than a few steps before I wouldn’t be able to run again. Which was enough to force myself to get running after just a few walking steps each time. Just before the finish, Carl (the race organizer) started hopping and jumping around me, taking photos like crazy as I motored around the last bend. I had no idea, but I had apparently made it into 3rd place overall in the 50 mile race!

OK, so there were only something like 30 people in the 50 mile race. But it was a nice bonus.

An even nicer bonus was when the family turned up a half hour later (my wife had understood to be there no later than 4:30, when I had actually said 3:30). She was sporting a Big Elm IPA (a local Sheffield MA brew), from her chef friend Brian (who had said he had no idea that anyone actually did what I was doing!)

This course was pretty flat, so my quads were just fine. But my hamstrings, and whatever other muscles than run down the back of my legs to the insides of my knees. D e a d. I don’t even know how to get these with the foam roller. Two big blisters, one on each foot. Basically I never even notice blisters, so they were never a problem given that were always worse pains to think about.

All in all, a successful day’s effort. Weather was good for running, but otherwise chilly and rainy. Lake breeze was mostly welcome even though cold. The suntan I got on my face though is a reminder that a lot of different weather can happen in 8 hours! Staying off the sugar for the first marathon really worked for me, and I didn’t get sick of the sweet stuff in the second half of the race (as I have done in marathons before).

The race was well organized, and the volunteers wonderful. It’s already tempting to say that I’ll go back next year. The loop format makes this an ideal first ultra where you’re so unsure of everything. But road miles. Phew! I really have to figure out shoes that will work for the full distance. Neither the GRUs or the Lunas are completely ideal for that many road miles for me. The GRUs took a real pounding too – in just 28 miles, the sole is completely worn away over the balls of my feet (there was no significant wear before yesterday). They seem more like road->trail shoes rather than dedicated road shoes. I think I’ve pretty much trashed them and yet they only have about 250 miles in them total. The Luna Monos have more cushion for road miles than my beloved (trail) Leadville sandals, but the cushion is probably what caused the big blister on my toe, as they are less flexible because of the extra material. Flexible + cushioned + road-specific. Hmmm.

My accurate splits will be posted on the Lake Waramaug website some time, but here are my approximate splits (rounded up to nearest minute since I usually forgot how many seconds were on the clock, except for the last two laps):

1 (out and back, 4.4 miles) 0:41 elapsed (41 minutes)
2 (loop 1, 7.6 miles, 12 miles total) (missing, I forget…)
3 (loop 2, 7.6 miles, 19.6 miles) 2:59 elapsed (missing)
4 (loop 3, 7.6 miles, 27.2 miles) 4:13 elapsed (74 minutes/lap)
5 (loop 4, 7.6 miles, 34.8 miles) 5:28 elapsed (75 minutes/lap)
6 (loop 5, 7.6 miles, 42.4 miles) 6:45 elapsed (77 minutes/lap)
7 (loop 6, 7.6 miles, 50 miles) 7:59 elapsed (74 minues/lap)

The time has come to talk of many things*… (on vaccination, trust and public policy)

It is quite clear. All the studies show it. Vaccination is helping “save society” from previously common, potentially-deadly diseases.

So why do I feel so queasy about vaccination, and about the whole debate that surrounds it?

Well. What do we know about vaccination?

We know that for individuals who are vaccinated against a particular disease, such individuals (usually) do not catch the disease against which they are vaccinated.

We also know that by vaccinating a large section of the population against a particular disease, we can effectively eradicate that disease in humans.

These things are simply proven by studies and direct experience. I do not dispute them.

There is a lot we don’t know.

What organisms arise when a particular organism is eradicated or weakened? We do know, for example, that increases in deer population are correlated with increases in tick population, for example. And that by reducing the numbers of bees, we reduce pollination of plants, leading to the potential for animal and human food shortages. These things are also “proven” (or at least studied) by science.

But we seem to know very little about what happens to the environment when particular bacteria or viruses either increase or decrease in number, at least in the general case.

What happens to the general immunity of people who have been vaccinated? We know they are, for some time, protected from the disease against which they are vaccinated. Does vaccination either improve, or inhibit their immunity to other organisms? I would argue that we don’t know. Does the eradication/weakening of one viral species cause the strengthening of another virus or bacteria? Who knows for sure in each individual case? But intuition tells me it’s a possibility, and one supported by analogues such as the bee, and tick examples.

This is the kind of problem we get with all public policy decisions made on the basis of science.

It is, in fact, possible to overstate the importance of science in making public policy decisions.

What, I hear you say, this man is ANTI-SCIENCE?!

No.

What I am wary of is:

Public policy: because science
I am an expert: because science
I am right: because science
This situation is clear: because science
Trust me: because science

These are all examples of the poor use of an excellent tool.

The best scientific studies are intentionally grounded in a specific thesis which may be provable, or dis-provable via specific methods. Specific studies deliberately control for, or ignore “the rest of the world” in order to provide very specific results. That is no accident. That is good science.

However, the world at large, is just not that simple. Everything actually is inter-connected. Everything is ambiguous. Specific results do not generalize beyond what they actually prove. And what the best studies prove, are very specific things.

So what should we do?

Making a decision based on science may or may not be “better” than making a decision based on intuition. It’s not possible to know everything before a decision, thus it is not possible to make only good decisions. A good decision can only be labelled as such only in hindsight (and with the benefit of history and sufficient analysis), and only when applied within a certain context. Science does not, any more than any other mechanism, help you know everything.

Decisions made “on behalf” of large numbers of people have wide-ranging consequences; beware of making them at all, or those who say that they know (anything at all) when making such decisions. Especially beware of those in public policy who believe that they can ever be “right” before making wide-ranging public policy decisions. Beware of people who say that in order to help you, you need to regard them as an “expert”, and that their expertise should necessarily carry any more weight than your “intuition”. Such people cannot help you in the way you need help; nor are they helpful in the way they think.

(*) http://www.jabberwocky.com/carroll/walrus.html

 

Aggressive Dog 13

Brutally cold, but beautiful

New Marlborough 16

On Hayes, waiting for snow

Twelve thirty-five. I have to make it back by two-fifteen. Ten miles then, not thirteen. Bitter wind. Ground hard as iron. My shoes are tighter than I’d like. Up the hill, I feel my heart strain a little with the incline. Broken down stone house wall on my left. What happened to those people? Why did they leave their house to the woods. Wind whipping across the top of the hill. Feet slipping a little, but not as much as the day before when I couldn’t stop on the ice sheet that covered the dirt. I run past the impassive statuesque bullsand the silo barn. No more dirt road; I’m on the tarmac. Squished porcupine in the middle of the raod, not far from where I saw the squished but not-yet-dead water snake this last May. Past the junction down Hayes, and I speed up as Brewer Hill inclines some more. Past Mill River Farm, and the identical stucco houses looming over Brewer Branch road. Warming up. Legs turning over, but I can feel my left hip and knee; still sore and complaining. Downhill hurts more. Will I make it all the way? I hope I don’t have to walk – then I’ll never make it back in time. I don’t even really notice the winding chalky path that leads to some mansion back up the hill, but I can feel it there in my mind. On to Konkapot, my knee better for the flatter road. Past the river and up around the curve, and I switch to the other side of the road. Yes, there might be a car that doesn’t see me around the bend. But I also need to be on this side so as not to offend the unpleasant border collie who likes to rush out and surprise me with his snarling ripping. I imagine punching his nose and pulling on his tongue if he really did bite me. But he doesn’t come today. Just watches me from the garage as I wind my way along Konkapot. Past the lovely two-level covered porch that I admire almost every time I run here. And the corrugated box house. Horses standing in the field, backs turned to me. Puffing up the hill and over the top, down towards Umpachene and the ominous road sign “Travel this road at your own risk”. My knee is doing fine now, and I still have plenty of speed up to Lumbert Cross. Few cars. Sky steely and braced for snow. Down into Mill River, and the knee complains briefly about the incline. I wonder about my bucket of grit “per-storm” from the town, and whether it’s worth the trip. Last downhill before the climb up Hayes. Around the town hall and library. Past the messy-looking house on the corner, chimney puffing billows of smoke. To the stop sign, and a left on Hayes. Straight up. Slow down. Into the woods. I wonder if I can make it back home before I need to pee? Then walking. I take a photo – trees waiting for the snow.

1504052_10152119029723523_1540611512_n

A young man walking on, orange hunting cap, but just walking. We greet each other, but I’m running again now the incline isn’t as sharp. Rolling on with the lovely view to the south over the hills I can see a patch of orange and blue through the grey. Nice weather, somewhere. Not here. The horse looks up, alarmed. I shuffle by him, turn up Brewer Hill again, getting tired finally. Must push up the last part of the dirt road though. Finish the run. “Way to finish the run, John”. Two oh-nine. Made it.

Stoney ledge Sunday

I wore a balaclava today more in anticipation of cold than the feeling itself.

The run up to the ledge was fairly typical but coming down was slower due to my not wearing glasses.

When I lost concentration on the lower part if the trail, I also lost my footing. Note to self: bring glasses for the descent.