Simon Josefsson: Why I don t Use 2048 or 4096 RSA Key Sizes
I have used non-standard RSA key size for maybe 15 years. For example, my old OpenPGP key created in 2002. With non-standard key sizes, I mean a RSA key size that is not 2048 or 4096. I do this when I generate OpenPGP/SSH keys (using GnuPG with a smartcard like this) and PKIX certificates (using GnuTLS or OpenSSL, e.g. for XMPP or for HTTPS). People sometimes ask me why. I haven t seen anyone talk about this, or provide a writeup, that is consistent with my views. So I wanted to write about my motivation, so that it is easy for me to refer to, and hopefully to inspire others to think similarily. Or to provoke discussion and disagreement that s fine, and hopefully I will learn something.
Before proceeding, here is some context: When building new things, it is usually better to use the Elliptic Curve technology algorithm Ed25519 instead of RSA. There is also ECDSA which has had a comparatively slow uptake, for a number of reasons that is widely available and is a reasonable choice when Ed25519 is not available. There are also post-quantum algorithms, but they are newer and adopting them today requires a careful cost-benefit analysis.
First some background. RSA is an asymmetric public-key scheme, and relies on generating private keys which are the product of distinct prime numbers (typically two). The size of the resulting product, called the modulus 
Before proceeding, here is some context: When building new things, it is usually better to use the Elliptic Curve technology algorithm Ed25519 instead of RSA. There is also ECDSA which has had a comparatively slow uptake, for a number of reasons that is widely available and is a reasonable choice when Ed25519 is not available. There are also post-quantum algorithms, but they are newer and adopting them today requires a careful cost-benefit analysis.
First some background. RSA is an asymmetric public-key scheme, and relies on generating private keys which are the product of distinct prime numbers (typically two). The size of the resulting product, called the modulus n, is usually expressed in bit length and forms the key size. Historically RSA key sizes used to be a couple of hundred bits, then 512 bits settled as a commonly used size. With better understanding of RSA security levels, the common key size evolved into 768, 1024, and later 2048. Today s recommendations (see keylength.com) suggest that 2048 is on the weak side for long-term keys (5+ years), so there has been a trend to jump to 4096. The performance of RSA private-key operations starts to suffer at 4096, and the bandwidth requirements is causing issues in some protocols. Today 2048 and 4096 are the most common choices.
My preference for non-2048/4096 RSA key sizes is based on the simple and na ve observation that if I would build a RSA key cracker, there is some likelihood that I would need to optimize the implementation for a particular key size in order to get good performance. Since 2048 and 4096 are dominant today, and 1024 were dominent some years ago, it may be feasible to build optimized versions for these three key sizes.
My observation is a conservative decision based on speculation, and speculation on several levels. First I assume that there is an attack on RSA that we don t know about. Then I assume that this attack is not as efficient for some key sizes than others, either on a theoretical level, at implementation level (optimized libraries for certain characteristics), or at an economic/human level (decision to focus on common key sizes). Then I assume that by avoiding the efficient key sizes I can increase the difficulty to a sufficient level.
Before analyzing whether those assumptions even remotely may make sense, it is useful to understand what is lost by selecting uncommon key sizes. This is to understand the cost of the trade-off.
A significant burden would be if implementations didn t allow selecting unusual key sizes. In my experience, enough common applications support uncommon key sizes, for example GnuPG, OpenSSL, OpenSSH, FireFox, and Chrome. Some applications limit the permitted choices; this appears to be rare, but I have encountered it once. Some environments also restrict permitted choices, for example I have experienced that LetsEncrypt has introduced a requirement for RSA key sizes to be a multiples of 8. I noticed this since I chose a RSA key size of 3925 for my blog and received a certificate from LetsEncrypt in December 2015 however during renewal in 2016 it lead to an error message about the RSA key size. Some commercial CAs that I have used before restrict the RSA key size to one of 1024, 2048 or 4096 only. Some smart-cards also restrict the key sizes, sadly the YubiKey has this limitation. So it is not always possible, but possible often enough for me to be worthwhile.
Another cost is that RSA signature operations are slowed down. This is because the exponentiation function is faster than multiplication, and if the bit pattern of the RSA key is a 1 followed by several 0 s, it is quicker to compute. I have not done benchmarks, but I have not experienced that this is a practical problem for me. I don t notice RSA operations in the flurry of all of other operations (network, IO) that is usually involved in my daily life. Deploying this on a large scale may have effects, of course, so benchmarks would be interesting.
Back to the speculation that leads me to this choice. The first assumption is that there is an attack on RSA that we don t know about. In my mind, until there are proofs that the currently known attacks (GNFS-based attacks) are the best that can be found, or at least some heuristic argument that we can t do better than the current attacks, the probability for an unknown RSA attack is therefor, as strange as it may sound, 100%.
The second assumption is that the unknown attack(s) are not as efficient for some key sizes than others. That statement can also be expressed like this: the cost to mount the attack is higher for some key sizes compared to others.
At the implementation level, it seems reasonable to assume that implementing a RSA cracker for arbitrary key sizes could be more difficult and costlier than focusing on particular key sizes. Focusing on some key sizes allows optimization and less complex code.
At the mathematical level, the assumption that the attack would be costlier for certain types of RSA key sizes appears dubious. It depends on the kind of algorithm the unknown attack is. For something similar to GNFS attacks, I believe the same algorithm applies equally for a RSA key size of 2048, 2730 and 4096 and that the running time depends mostly on the key size. Other algorithms that could crack RSA, such as some approximation algorithms, does not seem likely to be thwarted by using non-standard RSA key sizes either. I am not a mathematician though.
At the economical or human level, it seems reasonable to say that if you can crack 95% of all keys out there (sizes 1024, 2048, 4096) then that is good enough and cracking the last 5% is just diminishing returns of the investment. Here I am making up the 95% number. Currently, I would guess that more than 95% of all RSA key sizes on the Internet are 1024, 2048 or 4096 though. So this aspect holds as long as people behave as they have done.
The final assumption is that by using non-standard key sizes I raise the bar sufficiently high to make an attack impossible. To be honest, this scenario appears unlikely. However it might increase the cost somewhat, by a factor or two or five. Which might make someone target a lower hanging fruit instead.
Putting my argument together, I have 1) identified some downsides of using non-standard RSA Key sizes and discussed their costs and implications, and 2) mentioned some speculative upsides of using non-standard key sizes. I am not aware of any argument that the odds of my speculation is 0% likely to be true. It appears there is some remote chance, higher than 0%, that my speculation is true. Therefor, my personal conservative approach is to hedge against this unlikely, but still possible, attack scenario by paying the moderate cost to use non-standard RSA key sizes. Of course, the QA engineer in me also likes to break things by not doing what everyone else does, so I end this with an ObXKCD.
Debian LTS
October marked the eighteenth month I contributed to 
This month s update falls onto a national holiday in Japan. My recent start as a normal company employee in Japan doesn t leave me enough time during normal days to work on Debian, so things have to wait for holidays. There have been a few notable changes in the current packages, and above all I wanted to fix an RC bug and on the way fixed also several other (sometimes rather old) bugs.
From the list of new packages I want to pick 
Finally also a word about removals: Several ConTeXt packages have been removed due to the fact that they are outdated. These removals will find their way in an update of the Debian ConTeXt package in near future. The TeX Live packages lost 
Welcome to gambaru.de. Here is my monthly report that covers what I have been doing for Debian. If you re interested in Android, Java, Games and LTS topics, this might be interesting for you.
Debian Android
My monthly report covers a large part of what I have been doing in the free software world. I write it for 
The Arduino IDE does not work properly with tiling window managers, because they do some interesting reparenting.
To solve this, add
Wishing every one a happy Gujarati New Year, Vikram Samvat 2073 named Kilaka and hoping the upcoming year will be yuuge for you.
These next couple of paragraphs are totally not an excuse for why it will take a few more days for me to reach seven blog posts.
Reading reports about Diwali in the American press, I see a bit of confusion whether Diwali is one day or five. Well, technically it is just one (Sunday 30th this year.) but there are a number of other observances around it which could be classed as subsidiaries if you want to look at it that way.
The season commenced last Wednesday with Rama Ekadashi. (where the Gujarati name is different I'll use that and put the Sanskrit name in parentheses.) That's a fast day and therefore not much fun.
Thursday was Vagh Barash (vyaghra dvadashi) which as the name suggests is something to do with tigers but we don't in my experience particularly do anything special that day.
Friday, things began in earnest with Dhan Terash (dhana trayodashi) when Lakshmi the Goddess of prosperity is worshipped. It is also a good day to buy gold.
Saturday was Kali Chaudash (Kali Chaturdashi or Naraka Chaturdashi) On this day many Gujarati families including mine worship their Kuladevi (patron Goddess of the family) even if She is not an aspect of Kali. (Others observe this on the Ashtami of Navaratri.) The day is also associated with the God Hanuman. Some people say it is His Jayanti (birthday) though we observe it in Chaitra (March-April.) It is also the best day for learning mantras and I initiated a couple of people including my son into a mantra I know.
Sunday was Diwali (Deepavali) proper. As a Brahmana I spent much of the day signing blessings in the account books of shopkeepers. Well, nowadays only a few old people have actual account books so usually the print out a spreadsheet and I sign that. But home is where the main action is. Lights are lit, fireworks are set off, and prayers are offered to Lakshmi. But most important of all, this is the day good boys and girls get presents. Unfortunately I have nothing interesting to report; just the usual utilitarian items of clothing. Fireworks by the way are technically illegal in New Jersey not that that ever stopped anyone from getting them. The past few years, Jersey City has attempted to compromise by allowing a big public fireworks display. Although it was nice and sunny all day, by nighttime we had torrential rain and the firework display got washed out. So I'm glad I rebelled against the system with my small cache of sparklers.
Today (or yesterday by the time this gets posted.) was the Gujarati New Years Day. There is also the commemoration of the time the God Krishna lifted up Mt Govardhan with one finger which every mandir emulates by making an annakuta or mountain of food.
Tuesday is Bhai Beeja (Yama Dvitiya in Sanskrit or Bhai Duj in Hindi) when sisters cook a meal for their brothers. My son is also going to make something (read: microwave something) for his sister.
So those are the five days of Diwali. Though many will not consider it to be truly over until this Saturday, the lucky day of Labh Pancham (Labha panchami.) And if I still haven't managed to write seven blog posts by then, there is always Deva Diwali...
So, it's now been twenty years since I became a Debian Developer. I
couldn't remember the exact date I signed up, but I
decided to do some forensics to find out. First, I can check on the
dates on my first Debian system, as I've kept it running as a Debian
system ever since!
Here is my monthly update covering what I have been doing in the free software world (
I m at an airport, about to board the first of three flights across the world, from timezone +8 to timezone -8. I ll be in transit 27 hours to get to Seattle, Washington state. I m leaving my wife and two young children behind.
My work has given me a days worth of leave under the Corporate Social Responsibility program, and I m taking three days annual leave, to do this. 27 hours each way in transit, for 3 days on the ground.
Why?
Backstory
I started playing in technology as a kid in the 1980s; my first PC was a clone (as they were called) 286 running MS-DOS. It was clunky, and the most I could do to extend it was to write batch scripts. As a child I had no funds for commercial compilers, no network connections (this was pre Internet in Australia), no access to documentation, and no idea where to start programming properly.
It was a closed world.
I hit university in the summer of 1994 to study Computer Science and French. I d heard of Linux, and soon found myself installing the Linux distributions of the day. The Freedom of the licensing, the encouragement to use, modify, share, was in stark contrast to the world of consumer PCs of the late 1980 s.
It was there at the UCC at UWA I discovered Debian. Some of the kind network/system admins at the University maintained a Debian mirror on the campus LAN, updated regularly and always online. It was fast, and more importantly, free for me to access. Back in the 1990s, bandwidth in Australia was incredibly expensive. The vast distances of the country mean that bandwidth was scarce. Telcos were in races to put fiber between Perth and the Eastern States, and without that in place, IP connectivity was constrained, and thus costly.
Over many long days and nights I huddled down, learning window managers, protocols, programming and scripting languages. I became a system/network administrator, web developer, dev ops engineer, etc. My official degree workload, algorithmic complexity, protocol stacks, were interesting, but fiddling with Linux based implementations was practical.
Volunteer
After years of consuming the output of Debian and running many services with it I decided to put my hand up and volunteer as a Debian Developer: it was time to give back. I had benefited from Debian, and I saw others benefit from it as well.
As the 2000 s started, I had my PGP key in the Debian key ring. I had adopted a package and was maintaining it load balancing Apache web servers. The web was yet to expand to the traffic levels you see today; most web sites were served from one physical web server. Site Reliability Engineering was a term not yet dreamed of.
What became more apparent was the applicability of Linux, Open Source, and in my line-of-sight Debian to a wider community beyond myself and my university peers. Debain was being used to revive recycled computers that were being donated to charities; in some cases, unable to transfer commercial software licenses with the hardware that was no longer required by organisations that had upgraded. It appeared that Debian was being used as a baseline above which society in general had access to fundamental capability of computing and network services.
The removal of subscriptions, registrations, and the encouragement of distribution meant this occurred at rates that could never be tracked, and more importantly, the consensus was that it should not be automatically tracked. The privacy of the user is paramount more important than some statistics for the Developer to ponder.
When the Bosnia-Herzegovina war ended in 1995, I recall an email from academics there, having found some connectivity, writing to ask if they would be able to use Debian as part of their re-deployment of services for the Tertiary institutions in the region. This was an unnecessary request as Debian GNU/Linux is freely available, but it was a reminder that, for the country to have tried to procure commercial solutions at that time would have been difficult. Instead, those that could do the task just got on with it.
There s been many similar project where the grass-roots organisations non profits, NGOs, and even just loose collectives of individuals have turned to Linux, Open Source, and sometimes Debian to solve their problems. Many fine projects have been established to make technology accessible to all, regardless of race, gender, nationality, class, or any other label society has used to divide humans. Big hat tip to 
The 
I have just released version 1.20 of 
