Nicolas314

All my geeky stuff ends up here. Mostly Unix-related

Archive for the ‘programming’ Category

Put on your shoes

leave a comment »

shoes


– Mister engineer, we are about to leave the house. Could you please lace your shoes?

– I’m afraid I can’t do that before at least next year.

– What? No! We are leaving the house right now. Tie your shoes and let’s go!

– Well, it is obvious you have not been in the shoe-lacing business for quite a while mate. See: in order to tie my shoes I’d have to get my hands closer to my feet. I see three main possibilities:

1. I lower myself down to the level of my feet (and shoes), which is dangerously close to the ground. I could trip and fall, bringing me to ground level with sufficient speed to hurt my nose, probably causing bleeding in the process. Who would want to leave blood on the floor? You don’t want me to hurt myself, do you? This would take us to a large amount of blood cleaning and nose healing, which could take a lot of time and make us both look bad in case someone on the street asks why I have a bloody nose.

2. I could bring the shoes up to my level. Considering my feet would stop touching the ground, I would have very little time to complete the movement needed to effectively tie a knot to what could be considered decent shoe-lacing. Bad knots would make us look bad, and we do not want someone to notice that we are not even able to come out on the street with properly tied shoes.

3. The third and last possibility is to wait for my feet to grow up enough so that my shoes do not fit any more. This would probably trigger some shoe-buying and shoe-replacing, which could then be put to practical use to purchase a new pair of lace-free shoes, which would then solve all the above issues once and for all.

My conclusion is that we should wait until my feet have grown enough. See you in a couple of months.

– Man, you have reached the end of my patience. Let me tie those shoes for you.

– I’m afraid I can’t let you do that, Dave. Your role as a caretaker is not to take responsibilities and do things in my stead, but to teach me to be autonomous and let me do that myself. In addition, may I let you know that I have had these shoes for a few months now and you have never laced them before in your entire life, therefore I am the only suitable person to achieve that.

– C’mere, let me do it.

– Are you questioning my authority with respect to my own shoes? When you bought them you said they were mine!

– They are still yours, let me just lace them.

– You did not understand the above mentioned points. Apologies for my poor choice of words, I always forget that English is not your native language and you may not get the full power of the most subtle nuances.

– Don’t patronize me. Just don’t.

– Oh that was never my intention. In order to patronize someone…

– WILL YOU FUCKING TIE YOUR SHOES?

– Why the harsh language? Is that really needed? I have only given you the current status and all you can do is react strongly against me. I have not invented laces, nor did I decide to place my own hands at a different altitude than my own feet. I suggest you review our options and come to your senses before we do something we might regret.

– Do you see my hand? I swear it can fly and land on your face in no time.

– Let’s not be too hasty now. I would have to inform legal of your perceived intentions and will have to quote your language. Research indicates that people in your situation have very little chances of winning a legal fight that involves strong wording and physical violence.

– … You know what? You… You just stay here, Ok?

– That’s what I have been telling you all the time. Glad you finally came to your senses mate.

Advertisements

Written by nicolas314

Monday 9 July 2018 at 11:08 pm

Wunder Weather

leave a comment »

wunderJust released this small piece of code a few days back:

https://github.com/nicolas31/wunder

I wanted to be able to bring up the weather forecast for the place I am currently visiting without having to yield my address book to a shady app, or suffer from tons of annoying ads eating through my data plan and phone storage.

The Yahoo weather app is fantastic but has too many ads. Weather web sites are incredibly data heavy, making it nearly impossible to get right to the information I am looking for: is it going to rain today or tomorrow? Expected temperatures?  Android has some ad-less widgets but they usually request GPS positioning and I’d rather not activate location services when I don’t need them.

So I hacked something. Made a web app that identifies your position by geolocating the requester’s IP address, obtains the weather forecast from a reliable source, and displays the only weather information I need on a fast loading page.

First issue: geolocalize an IP address.

There are many free services on the net to achieve that. Alternatively, you can download a static list and refresh it at regular intervals, but I wanted to get something a bit more dynamic. I chose:

http://ip-api.com

Their API is dead simple and just works. Provide an IP address, get a country code, city name, latitude and longitude. You do not need to subscribe to their services, just make sure you are not choking them with too many requests.

Second issue: find a reliable weather source.

I fist tried openweathermap.org. This is a very cool site but has a few shortcomings:

You can get the weather for a given [city, country] or [lat, lon]. The list of supported [city, country] pairs is static and can be downloaded from their web site. While they do support a lot of cities in the world, the problem was figuring out how to match [city, country] between what is returned by ip-api.com and what is understood by openweathermap.org. The matching is not 100% accurate.

Getting the weather by coordinates would work but it is far from user-friendly.  You end up with Weather forecast for location Lat=XX Lon=YY. I’d rather look up the weather for San Francisco than for a pair of coordinates that are not obviously recognizable.

I ended up looking up [city, country] by computing the smallest distance on the openweathermap list, but that is just tedious and a lot of work for very little gain.

Other major issue: the weather forecast is only provided GMT, which is utterly useless. What I want is local time, always. What do I care if I am told that it will rain from 2 to 5am GMT if I cannot relate that to local time?

Figuring out a conversion between GMT and local time is a lot trickier than it looks. Thanks to Daylight Saving Time rules that are changed at random intervals in various countries, it is very hard to predict the time offset in some places more than a couple of weeks ahead. Relevant:

A bit of googling around revealed there is an actual API from Google Maps to convert a Unix time stamp + latitude and longitude to a local time. This API takes into account local DST rules at the considered date/time, which is exactly what we want. No need to register with Google, as usual the API is free to use and rate-limited.

Example code can be found here: https://github.com/nicolas314/tz

In summary: getting the weather from openweathermap would require:

  • One external API call to associate IP to [lat, lon]

  • A search to associate [lat, lon] to [city, country]

  • One external API call to obtain actual weather data

  • One external API call to convert GMT to local time

I have implemented that and the result is ugly. Ok let’s see if we can find something smarter.

Next try: wunderground.com

They also offer an API to obtain weather data for any place in the world and they take care of two things: converting [lat, lon] to [city, country], and converting weather forecast to local time. This is exactly what we want.

Their API can also take care of geolocating an IP address but I found their results to be a lot less reliable than what I get from ip-api.com, so will stick to that for geolocation.

Their terms and conditions are fair. You need to register with them to obtain an API key and that’s about it. Results are delivered in metric units and can be localized in several languages. You also get a pointer to icons symbolizing the weather, which is perfect to generate a nice web page effortlessly.

Some comments about my implementation:

Results from wunderground contain a whole bunch of information I am not interested in, like temperatures in Farenheit. Not an issue: the Go JSON API allows defining fewer fields than what is parsed, so you can keep your structs small with only relevant data.

When running behind a reverse proxy, the incoming requesting IP address you see is the one for the proxy. In order to get the real incoming IP address you need to configure the reverse proxy to pass it along, usually in an HTTP header. Since I am running this service behind nginx, I get the address from X-Real-IP. That is probably different for each reverse proxy out there.

Hardcoded handlers are provided to take care of requests for /favicon.ico and /robots.txt. I was tired of seeing 404 requests in my logs for these two.

Results are cached by IP address for one hour to avoid flooding upstream API services with requests. Results are displayed from a template that can easily be tweaked. The one I wrote fits nicely enough on both mobile and desktops, your mileage may vary.

I installed the end result on a tiny VPS instance, for my own use. Hoping that could be useful to somebody else.

Written by nicolas314

Tuesday 16 August 2016 at 1:46 pm

Posted in go, programming

Tagged with , ,

easy-rsa alternative

leave a comment »

Glad to announce that 2cca, the two-cent Certification Authority has now been ported to pure C with libcrypto (openssl) as single dependency. The goal was to make it available on openwrt as it seems pyopenssl is not available on this platform — without a lot of efforts.

As always, I swear this is the last time I ever link one of my sources against OpenSSL… until a replacement is made available.

Back to the point: you can now generate a Root CA, server, and client certificates to use with OpenVPN, with a couple of commands.

Download it from here:

https://github.com/nicolas314/2cca

Compile it with:

cc -o 2cca 2cca.c -lcrypto

Generate a root with e.g.:

2cca root O=Home CN=MyRootCA C=FR L=Paris email=postmaster@example.com

Your root is entirely defined by ca.crt and ca.key in the current directory. Its default duration is 10 years. Now that you have a root, you are going to use it to sign server and client certificates with e.g.:

2cca server CN=vpn.example.com C=FR L=Roubaix email=vpnmaster@example.com
2cca client CN=jdoe C=UK L=London email=jdoe@example.com duration=365

Your server identity is defined by vpn.example.com.crt and vpn.example.com.key. Your first client is jdoe.crt/jdoe.key.

You can verify certificates using openssl verify, e.g.:

openssl verify -CAfile ca.crt jdoe.crt

Certificate serial numbers are 128-bit long, which guarantees that they can be unique without having to memorize an incremental index. Your certificate database is the current directory.

Enjoy!

 

 

Written by nicolas314

Wednesday 30 December 2015 at 10:52 pm

Posted in openvpn, openwrt, pki, programming

Tagged with , ,

Easier easy-rsa

leave a comment »

openvpnIf you have ever set up an OpenVPN server, you probably had to fight your way through the certificate generation steps. Something like what is detailed here:

https://openvpn.net/index.php/open-source/documentation/miscellaneous/77-rsa-key-management.html

The official OpenVPN guide refers to easy-rsa, which is a royal pain in the butt. Even with the HOWTO in front of me, it takes me ages to set things up and if I ever have to come back later to generate more client certificates, I inevitably end up restarting from scratch because I cannot remember which steps I took and where I stored files.

Does not seem so difficult though. You need to generate a Root CA, and then use it to sign a server certificate (which is stored on your server) and client certificates which you distribute to your clients. I re-implemented the whole thing as a Python script in a couple of hours, tested it with an openvpn instance, and it works quite well. The script can be found here:

http://github.com/nicolas314/2cca

It is called two-cent CA because that is exactly what it is. There is no support for security modules like smart cards or HSMs because I do not need them, but since it is based on python-openssl it should not be too hard to make it work with P11 tokens.

Here is an example session where I create the root, a server identity, and two client identities for Alice and Bob.

$ python 2cca.py root
Give a name to your new root authority (default: Root CA)
Name: MyRoot
Which country is it located in? (default: ZZ)
Provide a 2-letter country code like US, FR, UK
Country: ZZ
Which city is it located in? (optional)
City: 
What organization is it part of? (default: Home)
Organization: Home
--- generating key pair (2048 bits)
Specify a certificate duration in days (default: 3650)
Duration: 
--- self-signing certificate
--- saving results to root.crt and root.key
done
$ python 2cca.py server
--- loading root certificate and key
Give a name to your new server (default: openvpn-server)
Name: myopenvpn-server
Which country is it located in? (default: ZZ)
Provide a 2-letter country code like US, FR, UK
Country: ZZ
Which city is it located in? (optional)
City: 
--- generating key pair (2048 bits)
Specify a certificate duration in days (default: 3650)
Duration: 
--- signing certificate with root
--- saving results to myopenvpn-server.crt and myopenvpn-server.key
$ python 2cca.py client
--- loading root certificate and key
Give a name to your new client (default: openvpn-client)
Name: Alice
Which country is it located in? (default: ZZ)
Provide a 2-letter country code like US, FR, UK
Country: UK
Which city is it located in? (optional)
City: Cambridge
--- generating key pair (2048 bits)
Specify a certificate duration in days (default: 3650)
Duration: 
--- signing certificate with root
--- saving results to Alice.crt and Alice.key
$ python 2cca.py client
--- loading root certificate and key
Give a name to your new client (default: openvpn-client)
Name: Bob
Which country is it located in? (default: ZZ)
Provide a 2-letter country code like US, FR, UK
Country: US
Which city is it located in? (optional)
City: Boston
--- generating key pair (2048 bits)
Specify a certificate duration in days (default: 3650)
Duration: 
--- signing certificate with root
--- saving results to Bob.crt and Bob.key
& ls
2cca.py    Alice.key  Bob.key    myopenvpn-server.crt  root.crt
Alice.crt  Bob.crt    README.md  myopenvpn-server.key  root.key

You want to keep root.crt for what OpenVPN calls the CA certificate. Do not loose root.key, you will need it whenever you will want to issue more client or server certificates. Install the other files as required.

Tested on Linux (Debian, Archlinux) and OSX.

Enjoy!

Written by nicolas314

Monday 28 December 2015 at 12:51 am

One-time file-sharing

leave a comment »

oneSay you rent a box somewhere on the Internet. You installed Debian stable on it because you want it to be nice and stable and run a few daemons that are useful to have online. Could be to hold your vast music collection, family pictures, or use it as remote storage for backup. Imagine you wanted to share some of the files hosted on this box with your relatives, who may or may not be computer-literate. Most of them would know how to use a webmail but asking them to install an ftp client is just beyond reach.  Obviously, you do not want to give these guys too many rights over your box (like an ssh access for scp). What are the solutions?

Setting up a dedicated HTTP server

Simple enough: set up an HTTP server to distribute static files. lighttpd is simple enough to setup in a couple of minutes and is very efficient for static stuff. But you do not want to distribute your files to the whole Internet. Sooner or later a web spider will crawl in and index your family pictures and all sorts of things you never meant to be public.  Next step: configure password-protection on the server

Fair enough. Now you have limited file downloads to people who know the password — provided they know how to enter a password. Do you create multiple accounts, one for each of your peers? It would be preferrable, otherwise you will never know who downloaded what. But then you have to communicate their passwords to your peers and make sure they have a procedure in case they forget it. You know you are headed straight to massive butt pains.

Second issue: passwords can be shared. You shared that 2GB movie with a couple of friends and a couple of weeks later you find out that there are currently 1,549 active downloads for this file. Sharing is in human nature and that is completely Ok, but you probably did not sign up to become a content distributor over the whole Internet, only with a couple of friends and relatives.

Next step: use one-time authentication

There are better solutions out there: since you only mean to share one single file (or set of files) each time, you do not need to create accounts for your friends. You give them a one-time download token and forget about it.

A one-time download token is a URL. It looks like the kind of URLs you get from URL shorteners with the funny string at the end. Something like http://shortener/12398741

One-time tokens can be shared but since they can only be used once, the person who shared it has lost it. The token is randomly generated and invalidated immediately after it is used to avoid having robots automatically scan all possible URLs in a row until they find a valid one.

There are many ways to achieve this on regular HTTP servers. Apache probably has a million configuration options for user authentication, including one-time passwords or something similar, but I have to admit I did not even try. I already wasted enough of my life in Apache config files. lighttpd can be configured to do that but the only solution I found required some Lua scripting and I did not feel up to the task.

Next-step: Do It Yourself

After reviewing countless pages of configuration options for various HTTP servers, I decided that it would be shorter for me to implement this in a tiny web app rather than try and understand complex configuration options.  My first iteration made use of a Python FCGI script in web.py attached to a lighttpd process. Pointing out static files from a Python web app to the embedding lighttpd process is reasonably simple.

This implementation suffered from a number of pitfalls though. For one thing, performance was bad. For some reason, the Python process would eat insane amounts of CPU and RAM when sending big files, slowing down the server to a crawl. Second showstopper was the complexity involved for such a simple setup. I had to write a Python script to generate the lighttpd configuration file with a number of deployment options: where to put config files, log files, static files, port number, etc. And then came the inevitable issues with dependencies: Python version versus web.py version versus lighttpd version.  Some combinations worked fine, some did not.  Nothing specific to Python or lighttpd, but the more you have gears, the more you have places for grains of sand to fit in.

I still survived with this setup for a year or so, when Go came in. I have already reviewed the language in the past and will not come back to that, but suffice it to say that developing HTTP servers in Go is the most natural thing. Adding the one-time token ingredient to the soup was implemented in just one evening.

Once rewritten in Go, I found out that the end-result was about just as big as the Python implementation, excluding the script that created the lighttpd config. The main difference was of course that I do not have to maintain cross-references between package versions for Python, lighttpd, and web.py, since there is only one dependency to cover: Go itself.

It was straightforward to enhance the program to support more options, respond to favicon, and handle a JSON-readable database for active tokens.  Performance is astounding. The serving Go process never takes more than a few megs of RAM (about the size of the executable itself) and only uses tiny amounts of CPU since the process is mostly I/O based anyway.

There is one thing I should have foreseen and had to re-implement. I am sending the one-time links by email and more and more people are reading their emails from their smartphone or tablet. Many just clicked the link without thinking twice, triggering a 2-4GB download and killing both their mobile and data plan at the same time. Wrong move.

The next version features a two-time download page: the first link sends users to a page summarizing the download, offering a second link to actually start the real thing with a big warning about the size of what will actually be sent.

There are many other features I would like to add to the current version, and I am hoping other people have better ideas for new features, which is the reason why I shared it on github. Find it here:

https://github.com/nicolas314/onetime

Since we are talking about sharing private date between friends and relatives, protecting the download may be a good idea. A recently added feature was support for HTTPS. You only need to point your config to server certificate and key files and off you go. The HTTP/HTTPS thing is completely handled by Go.

The resulting program is far from top-quality but it fulfils the needs. Go give it a try if you want to. Careful though: it will only work on Linux boxes for now.

Written by nicolas314

Wednesday 24 July 2013 at 9:18 pm

Posted in fun, go, programming, webapp

Tagged with , , ,

Starbugs

leave a comment »

The night was clear, we would not be playing Bomberman in the VLT control room that night. Clear skies and a sub-arcsecond seeing meant we would have a full batch of data to process every hour or so until the next morning. Once the calibrations had finished, the telescope operator launched the first observation. I re-compiled the whole processing software once more, just to be sure we had not forgotten anything, ran a series of unit tests for good measure, and waited in front of my screen for the first incoming set of frames to appear on the local disk.

First batch of sixty frames was completed after exactly sixty minutes. As the machine started doing its number-crunching, everybody in the room turned to me, waiting for the first processed image to come out. It took a good fifteen minutes for all algorithms to run through the set: calibrate all frames, remove the infrared sky, take into account bad and crazy pixels that have been hit with cosmic rays during the observation, register all frames to a common position, and finally stack them to a single image. The final result appeared on the screen above me and I could see smiles all around. It seemed the results were up to what my customers were expecting.

Now we had a clear image of a set of bright object against a dark background. In order to assess how much infrared light is emitted by each object, it needs to be calibrated. Somewhere on the image is a standard: a star with precisely known photometry in the wavelength we had been observing. Compute how many photons were received in this image from this star and you can deduce the magnitudes for all other objects present on the same frame.

I checked once more the final frame position on the sky and then launched the photometry calibration routine. The standard star was found and identified by name, its photometry computed by integrating all received light in a small surrounding radius, and then all objects in the frame were suddenly known by magnitude rather than number of photons. Perfect score! With a sigh of relief, I finally pushed myself away from the desk and reached for some water. The memory routines had done their job, we did not crash in flight by lack of RAM this time. Eleven more hours to go and then we could all go to sleep.

Next incoming data batch was processed just fine. Another image emerged. And then another one. It seemed everything was working perfectly fine.

Around midnight, something weird happened: the result image was correctly processed but photometry calibration failed because it found no standard star in the frame.

– What? Emilio, did you include a standard in the last observation?
– Let me check… Yes I did. You should have it somewhere around the top-right corner.

The standard star was indeed there, so why did the photometry calibration routine fail to find it?
I immediately opened the database we had for infrared standards and started searching frantically for the star, finding it immediately. I reached for the debugger and re-ran the whole routine once more with breakpoints. Confirmed: the search for standard stars in this region returned nothing, and yet the database was correctly loaded and completely in memory. The debugger showed what seemed like correct values for star positions, but the search function failed for some reason.

The star database we had was pretty simple: a simple text file containing named columns: first the star name, then its position on the sky as Right Ascension and Declination (a couple of angles), and then its magnitude at various wavelengths. Something like:

# Name | Ra         |  Dec      | Sp |  J     |    H   |   K    
AS01-0 | 00 55 09.9 |  00 43 13 | -- | 10.716 | 10.507 | 10.470 
AS03-0 | 01 04 21.6 |  04 13 39 | -- | 12.606 | 12.729 | 12.827 
AS04-1 | 01 54 43.4 |  00 43 59 | -- | 12.371 | 12.033 | 11.962 
AS05-0 | 02 30 16.4 |  05 15 52 | -- | 13.232 | 13.314 | 13.381 
AS05-1 | 02 30 18.6 |  05 16 42 | -- | 14.350 | 13.663 | 13.507 
AS07-0 | 02 57 21.2 |  00 18 39 | -- | 11.105 | 10.977 | 10.946 
AS10-0 | 04 52 58.9 | -00 14 41 | -- | 11.349 | 11.281 | 11.259 
AS13-1 | 05 57 10.4 |  00 01 38 | -- | 12.201 | 11.781 | 11.648 
AS13-1 | 05 57 09.5 |  00 01 50 | -- | 12.521 | 12.101 | 11.970 
AS13-3 | 05 57 08.0 |  00 00 07 | -- | 13.345 | 12.964 | 12.812 
AS15-0 | 06 40 34.3 |  09 19 13 | -- | 10.874 | 10.669 | 12.628 
AS15-1 | 06 40 36.2 |  09 18 60 | -- | 12.656 | 11.980 | 11.792 
AS15-2 | 06 40 37.9 |  09 18 41 | -- | 13.711 | 12.927 | 12.719 
AS15-3 | 06 40 37.9 |  09 18 19 | -- | 14.320 | 13.667 | 13.415 
AS16-0 | 07 24 15.3 | -00 32 50 | -- | 14.159 | 14.111 | 13.305 
AS16-1 | 07 24 14.3 | -00 33 05 | -- | 13.761 | 13.638 | 13.606 
AS16-2 | 07 24 15.4 | -00 32 49 | -- | 11.411 | 11.428 | 11.445 
AS16-3 | 07 24 17.2 | -00 32 27 | -- | 13.891 | 13.855 | 13.818 
AS16-4 | 07 24 17.5 | -00 33 07 | -- | 11.402 | 11.106 | 11.043

J, H, K are infrared bands corresponding to a relatively narrow wavelength range.

Something went wrong in the star-loading routine, so I loaded the whole set into memory once more and dumped it back to a text file to plot it. The results were not particularly obvious:

catalog

Somebody in the room came up to the screen and asked what we were looking at. I said: “these are the positions of all known infrared standards we have. For some reasons we cannot find tonight’s star in here.”

Looking at it again, I found our star. It was not in the right position. It should have been below the x axis but had shifted symmetrically above it. Looking at the data set again, the Declination was indeed negative: something like -00 14 41, but it was plotted on the wrong side of the x axis.

And then it dawned on me: the star was plotted at +00 14 41 instead of -00 14 41.

How do you read numeric data in C? Using scanf(). When you scanf() for “-00”, what do you think ends up in memory? Zero. Positive zero, since it is technically the same as negative zero. Except the angle has now been flipped around the x axis.

Right: plotting a denser set of stars revealed a clear white patch for Declinations between zero and minus one. I had just forgotten to take into account the first character as a sign since scanf() does not make any difference between “00” and “-00”. Once I corrected the database-loading line, everything fell into place and photometry computations could take place as expected.

Interestingly enough, it seems the same bug hit a large number of GPS devices over the past years. The German C’t magazine told the story a few years back about somebody who planned a bike tour around Bordeaux and ended up with intermediate points in the middle of the ocean. Bordeaux is located around longitude zero (Greenwhich), so you do have data points located at an angle that starts with -00. In effect, you could see all points correctly plotted on the map except for the ones located between zero and minus one degree, which flipped over the other side of the meridian. As soon as I saw the map I knew exactly what had happened.

At least the guy was clever enough not to bike into high waters. It could have been worse: though probably related to time manipulation errors rather than angles, you may want to read how F22 Raptors spontaneously rebooted upon crossing the international date line:

F22 Raptor gets zapped by international date line

There are some assumptions you should not make about handling time in software. Some of them are presented in this blog article:

Falsehoods programmers believe about time

Time and angles can be tricky scalars.

Written by nicolas314

Wednesday 26 June 2013 at 12:39 am

Sorting Certificates

leave a comment »

As I went for a smoke the other day, I found two colleagues trying to solve a puzzle they had to code. The game is the following: first you get a list of certificates belonging to Certification Authorities. A certificate is a list of key/value pairs that are expressed in a canonical way in binary (in a format called ASN.1) and then signed with a cryptographic key. Among the key/value pairs are:

  • A name for the identity corresponding to this certificate, or DN for Distinguished Name
  • A name for the entity that delivered (signed) the certificate: Issuer name
  • A serial number that is unique for this Issuer+Certificate
  • Validity dates: valid from and valid until
  • … and a bunch of other fields that are irrelevant for this issue

Certificates are always delivered by a Certification Authority (CA) except the ones for Root CAs that are self-signed (or self-issued), in which case Issuer and Issuee have the same name. The way Certification Authorities work, you normally start by creating a Root CA then issue certificates for subordinate CAs (subCA) that are themselves in charge of creating their own CAs, or just issuing certificates to end-users, machines, or applications. CA hierarchies may look like this in their simplest tree-like approach:

CA hierarchy

CA hierarchy

Now you received a list of unsorted certificates and you are asked to sort them out so that any CA certificate must have its Issuing Root CA on its left. If there are multiple roots, they are allowed to appear anywhere in the list as long as they are left of their daughter CAs. How do you sort them?

A very straightforward approach would be re-building the CA tree. Find out Root CAs: they are easy to identify as their issuer is themselves. Then parse all remaining certificates and find the immediate daughters for Root CAs you already have. Parse again and re-attach in a tree-like structure, sorting siblings together. Once you have a sorted tree, iterate on all root CAs, then subCAs, etc. until you reach a terminal node, i.e. a CA that has not issued CA certificates itself.

Fancy, but that requires some tree-like structures in memory that may be tricky to get right on the first attempt. I also did not like the fact that emitting CAs in a list would probably have to use recursion to remain elegant. I have very bad memories of recursive algorithms in production, I have seen stacks vaporize in flight more than once. Sure, they can be translated to iterative methods but then forget about elegance.

My colleagues were looking into fancier ways of achieving the same result by designing some kind of clever sorting algorithm with a bit of memory to end up with a sorted list in a limited number of passes. When I joined them they had just found a sort in O(Nˆ3). I tried to understand their method but just could not figure it out.

I thought about it for a moment and got one of these a-ha! insights:

“Guys, have you tried sorting the input list by validity date? Since a daughter CA is always younger than its parent, just sort on the valid from field.”

Problem solved.

Written by nicolas314

Thursday 20 June 2013 at 11:31 pm