The Flaw in the Estonian ID Card

There is a theoretical flaw in the Estonian ID card system which seriously undermines its trustworthiness. Now that we know that a certain spying agency of a major ally actively engages in the weakening and subversion of cryptographic systems, we should seriously consider the possibility that any flaw is being exploited and could even speculate that it was introduced on purpose.
In recent months, reports in ProPublica, The New York Times and The Guardian reveal that the US National Security Agency (NSA) has been actively working to undermine the cryptographic systems that form the backbone of the Internet - in particular those that are relied on by the general public and businesses for the safety of their communications.
According to the reports, the NSA has apparently successfully attacked several cryptographic systems that were previously thought to be secure. These include TLS (and its predecessor SSL), the protocol every one of us relies on to safely communicate with our bank via the Internet, and VPN, the system that businesses rely on to shield their distributed internal networks from unauthorized incursions and eavesdropping.
However, there are very few details available on how this was done. At this time, it is not clear whether these attacks on the security of the Internet have compromised the very basis of the cryptographic systems, something that seems unlikely from a mathematical point of view but could be achieved through exploiting software flaws known only to the NSA, or whether the NSA has simply been successful at retrieving the cryptographic keys used by some major web services. The latter is possible through legal coercion such as a warrant or national security letter with a gag order. A gag order prohibits the recipient from talking about a national security letter or warrant that they have received.
At the very least we should now assume that the NSA can eavesdrop on our communications with major US web services such as Facebook, Google and Yahoo. Which means that the NSA can spy on any traffic to and from those services without needing any pesky warrants.
This also means that the disclosure, by those major US web companies, of the total number of users whose data was requested through warrants is essentially meaningless. Those probably only concerned stored data that the NSA for some reason did not collect when the data was in transit (maybe due to technical failures) or had previously chosen not to keep.
Meanwhile in e-Stonia
President Ilves regularly extols the blessings of Estonia's advanced e-governance and ID card system. The technology is indeed very forward looking and is based on the principles of public key cryptography. This is the very technology that the NSA hates the public to have easy access to.
For users of Estonian ID cards, the complexities of the underlying cryptography are hidden and all they know is that they have two PIN codes, one to identify themselves to online services and the other to sign documents - a signature that, incidentally, is legally binding. It is also possible to use it to encrypt e-mails and files.
There is no doubt that making a complex cryptographic technology usable for all citizens, to identify themselves and sign contracts, is in itself an incredible feat, not to mention a huge benefit to the economy in allowing almost any transaction to take place via the Internet. President Ilves is right to mention it as one of Estonia's great achievements.
The Basics of Cryptography
To understand the theoretical weakness we will need to explain a little bit about cryptography, so bear with me. Public key cryptography is based on the concept of a key pair. Two keys that are mathematically linked in such a way that if you use one key for a specific action you need the other for the opposite action.
For instance, if one key is used to encrypt a message, the other is needed to decrypt it. This is quite convenient, because if I want you to send me a secret message all I need to do is to give you one of those keys, a key that we shall now call my public key. With that key you can encrypt a message to me, but no one can decrypt it even if they know my public key. Only I can decrypt it with the other key, which we will now call my secret key or private key.
Similarly, if I sign a document with my secret key, the signature can be verified with the public key, but no one can fake my signature with the public key.
Estonian ID cards contain such private keys and the related public keys are published online.
We will not linger too much on the question of what happens when you lose your ID card, as you then also lose your private keys and can no longer read encrypted e-mails sent to you or decrypt files that you once encrypted. This problem in itself seems like a good reason not to use the Estonian ID card system for those purposes. Personally I have opted to use an open source tool named Gnu Privacy Guard (GPG), which has the additional benefit of not being restricted to one small country in Northern Europe.
Key Authenticity
But I digress, my short overview of public key cryptography would not be complete without covering the question of key authenticity. Or simply put: how does someone know for sure that they have my key and not one issued by an imposter?
To prevent such ugly abuse, we practice something called key signing. If we sign the keys of people whose keys we have verified and trust, sooner or later a network of trust will appear. For instance if Alex signed Birgit's key, who signed Doris' key and Alex trusts Birgit, then he can trust that Doris' key is indeed hers. Maybe Doris in turn signed Emma's key, giving Alex a degree of certainty about Emma's key, too.
With the Estonian ID card system, this problem has been solved with one clean stroke: the state signs all our keys. For Alex to trust Emma's key, he now only needs to trust the signature of the Estonian state on Emma's key. This is another major benefit of the Estonian ID card system - keys certified by the state.
Secret Keys Must Be Secret
For any cryptographic scheme to work, one thing is paramount: no one, absolutely no one else, should have a copy of your secret key.
If someone else did hold a copy, they could decrypt communications you received, identify themselves as you. More worryingly, in Estonia with the ID card system, they could access your bank account, and sign legally binding documents in your name.
Ever since receiving my first Estonian ID card many years ago, there has been an itch that I wanted to scratch: How can we trust that we have the only copies of the secret keys on the ID cards - secret keys that we did not create, that were issued to us by the state, and that we cannot replace with self generated keys?
Were I living in the United States, France, the United Kingdom, Russia or China, it would take me less than a microsecond to relegate to fantasy land the assumption that the state kept no copy.
There just is no way in the world that a government in one of those countries, so bent on surveillance of everything people do, would empower their citizens through a government created technology, to communicate in a secure fashion that even the state itself could not decipher.
No. No way. There would be a secret backdoor or a secret key escrow scheme. You can bet on that. The excuses to justify surveillance of the general public are just too many; child porn, terrorism, national security, foreign spies, extremism and what have you. The Snowden leaks prove this assumption to be true for the US and the UK, and we can quite safely assume that the other big countries in the world, most of which have historically had even less respect for civil liberties, are no better.
Of course, unlike Estonia, none of those countries even pretend to provide a secure cryptographic system to all their citizens in the first place.
Because this is Estonia, I am willing to entertain the possibility that the state is honest towards us and has not kept a copy. If this is so, it would truly set Estonia apart from nearly all other countries. It would be a privacy utopia with the state actively empowering us to protect our privacy, at least online.
Everything in me hopes this is so, and that I've somehow magically picked one of the best countries to live in when it comes to privacy and respect of our civil liberties.
A Glaring Flaw
I have tried to find out more about the technical details of the card and the cryptographic keys stored on them. Supposedly the key pair generation is a function of the card and it is claimed that the secret keys never leave the card. In that case, one wonders what reason there could be not to let users generate their own keys? If key generation is a function of the chip on the card, then this should be trivial, the initial key could be used to allow users to register a new one, and this process could be repeated as often as the user wants, each time identifying their new key with the previous one.
Secondly, I have seen no absolute guarantee that the keys cannot be retrieved from the card with some specialized hardware and software. It might be expensive, but that would not be an issue for the state or a well funded agency.
In fact even the statement that the secret keys never leave the card could be technically true, while still not guaranteeing that there is no copy of those keys. This is because key generation requires random data, and that random data must somehow be provided to the card externally as there are no random events on the card itself to generate random data. If you can control the random data fed to the card, or even just log it, you can in theory determine what key will be generated or at the very least significantly reduce the possible keys that it could generate. Such a reduction would make the key vulnerable to a simple brute force attack over a limited set of possibilities.
Alternatively, simply using flawed random data generators will produce weakened keys, vulnerable to attack by a well funded organization. Leaked documents have shown that the NSA has abused its influence to introduce such weakened random number generators into standards that were adopted worldwide.
Thus it appears to me that it is possible that copies of our keys are being made and kept or that our keys have been weakened. A cryptographic system that relies on the need to blindly trust others is not safe by definition, and unfortunately trust that our keys have not been tampered with is an essential part of the Estonian ID card system. Nothing short of allowing people to generate their own keys in an environment they control themselves with random data they generate themselves can ever really alleviate such fears.
If it turns out that our private keys have been compromised, did this happen on Estonia's own initiative, or was Estonia pressured into doing so by a foreign agency like the NSA in the same way that the NSA has managed to subvert other cryptographic systems? If it is the latter, the flaw may have been introduced on purpose when the system was designed. This might have sounded crazy just a few weeks ago, but with what we now know about the NSA it is suddenly well inside the realm of possibilities.
On the other hand, it would be foolish for the Estonian state to compromise the system in this way, as it would undermine the legality of elections and digital signatures. There would also always be a serious risk that someone would blow the whistle on this activity and expose the scheme. Why take such a risk?
Thus hopefully my fears are unfounded, but given the current climate of distrust created by the actions of US and UK spying agencies, members of our own government in Estonia would do well to do everything in their power to close any flaw in the ID card system, even if only theoretical. Their good intentions can be shown by allowing us henceforth to generate our own keys in environments under our own control.
Until then I would refrain from relying too much on the Estonian ID card system.
Otto de Voogd is a digital freedom warrior, a member of the non-profit Internet Society Estonia Chapter and a volunteer Mozilla contributor.