encryption algorithm

Robert J. Hansen rjh at sixdemonbag.org
Wed Dec 18 04:28:43 CET 2013

On 12/17/2013 9:20 PM, Daniel Kahn Gillmor wrote:
> sigh.  "weakest link" analysis is clearly useful, and just as
> clearly not the only analytic tool to use.

I don't understand your position.  First you're saying, "we currently
have 112 bits of keyspace, we need at least 128," and then you're saying
that you want to see the system evened out -- but the difference between
a 128-bit keyspace and a 256-bit keyspace is so enormous that you might
as well be talking about a 112-bit keyspace and a 256-bit keyspace.

If a 3072-bit key makes you happy and makes you feel it's "evened out,"
well, my question is -- why?  256 bit keyspace versus 112 is not much
different from 256 bit versus 128.

> Your argument in response seems to be "whoa! if we improve them all
> the way to the symmetric cipher length it would be computationally
> infeasible!"

No.  My argument is that your reasoning is incoherent.  If you want to
even out the system -- or, as you advocated later, make the asymmetric
component stronger than the symmetric component -- the *only possible*
interpretation is that you're advocating for at least RSA-15000.  If you
truly believe the asymmetric component should be stronger, you're
advocating for RSA-30000.

I don't think that's what you want.  (And I note that you have
explicitly repudiated that notion.)  And since I think that's not what
you want, that means I have to conclude your reasoning is faulty.

> so, how much weaker are you ok with?

At least 128 bits of keyspace less, obviously.  And when weighed in that
respect, whether we're talking about 128 bits or 140 bits is really
quite irrelevant.

That's why we need to focus on keeping each component at or greater than
our minimum specification.  112 bits of keyspace is a reasonable minimum
for the time being; therefore, I'm happy with the current defaults.  I
don't want to see them used for the next ten years, mind you, but I
absolutely reject the fierce moral urgency of immediate change that you
seem to be subscribing to.

> (i'm glad you still feel they're trustworthy, even in the context of
> them having issued a deliberately bad RNG, and their keylength
> recommendations being weaker than everyone else's!)

That's a naked slander against NIST.  You're better than that, Daniel.

No one, and I emphasize *no one*, has presented any evidence that NIST
issued a deliberately bad PRNG, or for that matter whether Dual_EC_DRBG
is even backdoored.  _Wired_ magazine wrote of it,

	A surprising uncertainty is still smouldering over
	whether Dual_EC_DRBG really is backdoored.  The _Times_,
	crypto experts note, hasn't released the memos that
	purport to prove the existence of a backdoor, and the
	paper's direct quotes from the classified documents
	don't mention any backdoor in the algorithm or efforts
	by the NSA to weaken it or the standard.  They only
	discuss efforts to push the standard through committees
	for approval.

	Jon Callas, the CTO of Silent Circle ... saw the
	presentation by Shumow.  He says he wasn't alarmed by
	it at the time and still has doubts that what was
	exposed was actually a backdoor, in part because the
	algorithm is so badly done.  "If [NSA] spent $250
	million weakening the standard and this is the best
	that they could do, then we have nothing to fear from
	them," he says.  "Because this was really ham-fisted.
	When you put on your conspiratorial hat about what the
	NSA would be doing, you would expect something more
	devious, Machiavellian... and this thing is just
	laughably bad.  This is Boris and Natasha sort of

	Indeed, the Microsoft presenters themselves -- who
	declined to comment for this article -- didn't press
	the backdoor theory in their talk.  They didn't mention
	NSA at all, and went out of their way to avoid accusing
	NIST of anything.  "WE ARE NOT SAYING: NIST
	intentionally put a back door in this PRNG," read the
	last slide of their deck.

	The Microsoft manager who spoke with WIRED on
	condition of anonymity thinks the provocative title of
	the 2007 presentation overstates the issue with the
	algorithm and is being misinterpreted -- that perhaps
	reporters at the _Times_ read something in a classified
	document showing that the NSA worked on the algorithm
	and pushed it through the standards process, and quickly
	took it as proof that the title of the 2007 talk had
	been right to call the weakness in the standard and the
	algorithm a backdoor.


	[Schneier] adds that the uncertainty around the algorithm
	and the standard is the worst part of the whole matter.

	"This is the worst problem that the NSA has done,"
	Schneier says.  "They have so undermined the fundamental
	trust in the internet, that we don't know what to trust.
	We have to suspect everything.  We're never sure.  That's
	the greatest damage."

(Link: http://www.wired.com/threatlevel/2013/09/nsa-backdoor/all/ )

I emphatically agree there's a lot of uncertainty around Dual_EC_DRBG.
It is possible it was subverted -- but it's also possible it wasn't.
It's possible it was subverted, NIST knew of the subversion, and
approved the standard anyway -- but it's also possible NIST was caught
unawares.  It's possible that... etc.

Claiming that they offered a *deliberately bad* PRNG is, quite frankly,
a slander.  There is no certainty there.  There isn't even much in the
way of evidence.  There is a possibility.  Let's not go about declaring
NIST guilty based on nothing more than the possibility of wrongdoing.

> Of course when ECC is available, we may want to shift to ECC.  But
> ECC is not currently available, and even when it becomes available,
> RSA will be the dominant key type for years.

Sure.  That's because we can't retroactively change keys that have
already been made.  Even if we adopt your recommendation of moving to
RSA-3072 immediately, RSA-2048 will still be the dominant key type for

> This is a terrible argument for not improving the default RSA key
> length today.

I think it's a great one.  One of the best things about GnuPG has been
its stability.  Changing the defaults is not something to be done
lightly.  Doing so invalidates FAQs and tutorials, it forces people to
edit their scripts, it causes uncertainty and doubt and "why did you
change...?" on the mailing lists.  Changing to RSA-3072 now, and then to
ECC in nine months or a year, is (IMO) unwise.  "Why are you changing
the defaults again?  Did you make a mistake the last time?"

Etc., etc.  Better to wait until ECC is ready, make a single change to
the defaults, and keep the transition crisp and clean.

> It costs very little to change the default, and it signals the user
> community that we take the existence of well-funded adversaries 
> seriously.

I think GnuPG has already clearly established its reputation in that field.

> We're engineers talking about building safety and security 
> infrastructure here.

Yes -- and part of that is recognizing when the additional expense to
mitigate a risk is greater than the risk itself.  I'm sure we could
reduce airplane crashes by 90% if we were to overengineer airplanes so
much that a ticket cost a million dollars, but we don't do that.

You want perfection.  You're not going to get it.  It's like trying to
build a bridge that simply will not collapse, period, no matter how
large a weight is moved over it.

What I want instead is a quality bridge, one that's well-inspected, and
has a big sign a half-kilometer out reading, "Maximum Load 10,000kg".
That, we can do pretty easily.

More information about the Gnupg-users mailing list