In January 2014, researchers from the “Cryptography and Security” group of the Department of Computer Science of Aarhus University contacted Nets DanID A/S to receive a database of the public keys of all Danish NemID users, with the goal of checking whether NemID public keys were vulnerable to attacks.
NemID (which in English means “easy identification”) is the national digital signature scheme in Denmark, used by citizen and companies as an authentication and signing system for e-government, e-banking etc. Due to the importance of the system, a continuous auditing of the system against state-of-the art cryptographic attacks discovered by the scientific community is paramount.
One component of NemID is called “OCES” (Offentlige Certifikater til Elektronisk Service), which is used to login to public and private service providers as well as signing documents. In this scheme, each user has a private key and a public key. The private key can be used to “sign” documents, while the public key can be used to verify the authenticity of a signature. As the name suggests, private keys must be kept secret, while public keys can be known by everyone. When the keys are generated, it is important that they are chosen truly at random, since otherwise an attacker might have a chance at guessing the private key.
Bad randomness attacks
In the last few years, a number of scientific papers have been published pointing out that in some cases, biases in the randomness used to generate the secret key can lead to serious consequences for the security of users.
In particular, it has been shown that in systems with millions of users, it might be possible to recover the private key of some users by performing a joint analysis on all public keys. This lead to concrete attacks against some internet routers as well as the Taiwanese national identification scheme [1,2,3].
The auditing process
In January 2014, researchers from the “Cryptography and Security” group of the Department of Computer Science of Aarhus University contacted Nets DanID A/S to receive a database of the public keys of all Danish NemID users, with the goal of checking whether NemID public keys were vulnerable to a similar attack. Nets DanID A/S was very interested in this external validation, and extracted the full set, consisting of 4,841,990 public keys, on January 16th 2014. After a number of tests, we are happy to report that the NemID OCES public keys do not suffer from the same vulnerabilities described above. Of course, this is not an ultimate guarantee that the NemID system is “uncrackable”, as there might be other points of failure or vulnerabilities that might be discovered in the future.
Nets DanID A/S was naturally happy about the result: “Nets DanID A/S is pleased with this collaboration with Aarhus University. The randomness of the public/private keys is critical to the security of the overall system, and is something we take very seriously. For this reason, we keep up-to-date on the latest attacks in this area. We immediately welcomed this offer of an external audit of the keys, and we are of course happy it didn’t find any problems”.
Details on the NemID scheme
The NemID system has both so-called "short term keys" and "long term keys". The short term keys are only used for the banking flows, and the certificates involved are not logged. Hence, they were not tested. The long term keys/certificates are what is used in the OCES scheme, which is used when logging into public or private service providers (those that are not banks), signing documents at e.g. tinglysning.dk as well as using secure e-mail. The scheme is both used by private citizens (for signing in to public services) and by companies who can issue certificates to their employees among other things.
These certificates are valid for 3 years from issuance. The key pair and thus the public key in these certificates come from multiple sources: in most cases, the key is centrally generated and managed in Hardware Security Modules in the NemID backend system. In this scheme, the users authorizes the use of his/her personal key using a one-time code, which can come from either a printed card sent to the user’s address, an electronic code token or from an automated telephone call to the user’s phone (the latter option is mainly used by visually impaired users). However, the user can also decide to have the private key generated locally; for instance it can be generated and stored on a smartcard or in a file on his computer (the latter option is only available for the NemID-scheme used by companies).
Regardless of the source, all OCES certificates contain 2048 bit RSA keys and the actual certificate issuance (as opposed to key generation) takes place on the same CA infrastructure. Keys from all these sources were included in the auditing.
In the RSA signature scheme used in NemID, each user’s private key contains two big prime numbers, say p and q, while the public key is the product of these two numbers e.g., n=pq. The security of the signature scheme relies on the fact that it is hard to recover p and q having only access to their product n.
However, if the system generating the user’s private key uses (or reuses) bad randomness, it is possible that two users will end up sharing part of their private keys. For instance, one can have two users with public keys n and n’, where n= pq and n’ = p’q. Now, since the two moduli n and n’ “share” one of their prime numbers, it is easy to compute the “greatest common divisor” of n and n’, namely q, which allows an attacker to impersonate these users, sign contracts on their behalf etc.
We have verified that this this is not the case for the public keys in the dataset Nets DanID A/S has provided for this investigation (extraction date: January 16h 2014).
 Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, Christophe Wachter: Public Keys. CRYPTO 2012.
 Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren: Factoring RSA Keys from Certified Smart Cards: Coppersmith in the Wild. ASIACRYPT 2013.
 Nadia Heninger, Zakir Durumeric, Eric Wustrow, J Alex Halderman: Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Security 2012.