Re: Investigating the Origins of RSA Public Keys

This post is about a research done by one of our co-founders. Petr showed that it is possible to find which tool or hardware device generated RSA keys from just a few public keys. I’m thinking it’s an attack, unexpected data leakage channel, but also an excellent source for audit-related analytics.

Petr will present this at USENIX Security Symposium next week so I will update the information in a week’s time or so. However, the abstract has been already published and it provides some food for thoughts.

digital_shamrockPetr and colleagues analysed over 60 million freshly generated key pairs from 22 crypto libraries and 16 types of smartcards and showed their RNG implementations are the source of significant data leakage. The bias introduced by different choices is sufficiently large to classify keys by their origin. If shamrock had 30 odd leaves, the attack can say, which leaf does a given key belongs to.

They also looked at 10 million RSA-based  TLS keys and were able to independently verify market share of web servers.

In the abstract, they name a few examples where this may have a direct impact on security: e.g., to decrease anonymity of users privacy systems like Tor, or to quickly detect vulnerable keys as soon as one finds a vulnerability in a particular cryptographic library.

From my point of view – as I am in touch with people from the corporate environment, one thing you may want to do is to check if administrators use the correct tools for server keys (HTTPS, SSH, MQ, IIS, database access, …). In some cases, there are lists of tools that must be used so that the company can efficiently control security.

While the presented method requires more than one key, it is not really a barrier when there is one person that looks after a number of servers. In fact, there is an opportunity to identify administrators by the tools they use. This can be due to different system platforms and/or operational environments.

I guess the point is that while keys themselves are not compromised as a loss of a few bits of entropy doesn’t create a practical vulnerability. There is the privacy issue that may be significant and certainly should be part of any metrics measuring privacy of users where it’s of interest.

For companies, I wouldn’t consider this an immediate problem as it may take years for someone to find a vulnerability. I find it, however, an excellent tool to learn about your network and how it is managed.


Published by

Dan Cvrcek

Founder and CEO of Enigma Bridge, engineer, entrepreneur, cryptography SME, security architect, and professor.