I have done a significant amount of considering on the very questions raised
in this. This consideration has spanned approximately a month of time. These
are my basic conclusions:
Bernstein's proposal does have an impact, but I do not believ that 3x the
key size is necessary
I believe Bernstein's proposal results in the necessity of a keysize of
approximately 1.5 times what was required before
I believe that there are further similar advances available to the
algorithms involved that can push this to approximately 2x
I have reached these considerations through a very long thought process that
involved digging through old textbooks on electrical engineering, and a
fundamental assumption that people will only construct these machines when
there is a stimulus to do so. So for example it would not be reasonable for
me to construct one to break 768-bit keys because I have little interest in
the actual data, merely whether or not the data is secure. Similarly, IBM
would not likely construct one simply because it would be economically more
feasible to dedicate that money towards research. The NSA and similar
organizations is extremely likely to strongly consider building such a
machine because they have the money, and the mandate to to whatever it takes
to gain access to the data encrypted by militaries around the world. Are
these assumptions necessarily correct? In their fundamental form they are
not, Linux is proof of this (people giving their freetime to something that
they get effetively nothing out of), however since we are talking about a
very significant investment of money to make one of usable size, these
assumptions are likely to be approximately correct.
This means that according to my considerations it seems reasonable to
decommission all 512-bit keys immediately (these ahouls hyave been
decomissioned years ago, but there are still a few floating around), 768-bit
keys should be decommissioned at the earliest realizable opportunity (I
don't believe they are in immediate danger of compromise, but they are
compromisable), 1024-bit keys should now be considered moderately secure in
the immediate future and decommissioned over the next couple years, 1536-bit
keys are for reasonable purposes secure, 2048-bit keys are secure for all
but the most demanding situations, and 4096-bit keys are still effectively
invulnerable.
This of course makes some very blanket assumptions about the desirability of
breaking a specific key. If no one wants to read what's inside, you don't
even really need to encrypt it (note the difference between need and want).
It will still cost a minimum of 10^9 US dollars to break 1024-bit keys.
Considering that most businesses and many governments won't have this value
of information transferred in the next 100 years, the desire to break
1024-bit keys simply isn't there.
Also examine _who_ wants to read your data. If it's just messages back and
forth from your girlfriend/wife/mistress it's unlikely that 512-bits will be
broken. If you are protecting state secrets, obviously you need to consider
things more carefully, and 4096-bit keys may not even offer enough security.
As usual there is no one-stop solution for every situation, only more
considerations that need to be made. I welcome any comments on my
conclusions.
Joe
