objectivity and factoring analysis

Nicko van Someren nicko at ncipher.com
Sun Apr 21 14:37:32 EDT 2002


> ----- Forwarded message from Adam Back <adam at cypherspace.org> -----
> 
> To: Cryptography <cryptography at wasabisystems.com>
> Cc: adam at cypherspace.org
> From: Adam Back <adam at cypherspace.org>
> Subject: objectivity and factoring analysis
> Date: Fri, 19 Apr 2002 14:51:59 +0100
> Sender: owner-cryptography at wasabisystems.com
> 
> I'd just like to make a few comments about the apparently unnoticed or
> unstated conflicts of interest and bias in the analysis surrounding
> Bernstein's proposal.
...

> - I'm not sure any of the respondents so far except Bernstein have
> truly understood the math -- there are probably few who do, factoring
> being such a narrow research area.


I'm inclined to agree with you there

...

> - Nicko van Someren -- the person credited with originally making the
> exaggerated, or at least highly worst case interpretation at the FC02
> panel -- has a conflict interest -- hardware accelerator gear that
> ncipher sell will be more markedly needed if people switch to 2048 or
> larger keys.  Nicko has made no public comments in the resulting
> discussion.


Since you mention it, I will make a comment for the purpose of
clearing up a number of misunderstandings about what I said
and the context in which the comments were made.

At the Financial Cryptography 2002 conference a small and
impromptu panel was convened to discuss the Bernstein
proposal.  Since I'm in the business of building hardware I
was asked to comment on the cost of building some of the
hardware described therein.  I limited myself to comments
about the design for the engine that could be used to take
the results of the sieve process and compute values leading
to a pair of roots, and furthermore prefaced and qualified
my comments with strong statements about any numbers being
very rough back of an envelope calculations.  The estimate
of the cost of construction I gave was "some hundreds of
millions of dollars", a figure by which I still stand.

I was then asked how fast this machine would run and I tried
to do the calculation on the spot without a copy of the
proposal to hand, and came up with a figure on the order
of a second based on very conservative hardware design.
This figure is *wildly* erroneous as a result of both not
having the paper to hand and also not even having an
envelope on the back of which I could scratch notes.  The
number was based on a miscalculation of the number of
clock ticks the circuit would need by a factor of 10^11,
which is a vast error that is only slightly moderated by
the fact that on further analysis I concluded that the
hardware could be made to operate on a clock that ran
between 10^3 and 10^4 times faster since the inter-circuit
communication did not need to be as slow as I had originally
thought.  Thus I think that with care a matrix reduction
machine of the sort described could be built to run in a few
weeks or months for 1024 bit keys.

Despite all the qualifying of these statements I felt then,
and still feel now, that if you have keys that you think
rich governments might genuinely be interested in then you
should use ones that are longer than 1024 bits.  If you have
personal information that you want to keep secret from rich
governments for many years to come then you should probably
use longer keys anyway.  After all we can expect on past form
that the security agencies are some years ahead of the
academic state of the art in this field anyway.  On the
other hand if you are moving general commercial data around
on an everyday basis I don't think that there is much wrong
with 1024 bits keys and I would not, and have not, suggested
that there is anything insecure about such key lengths for,
say, electronic banking or e-commerce using SSL.

I have to say that Adam's suggestion that there was some
sort of ulterior motive for my comments is both disingenuous
and somewhat insulting.  In the context of short and impromptu
discussion on a topic which people felt was a live one, I made
a back of the envelope calculation in which I used the "time"
figure as the "cost" figure and came up with totally the wrong
number.  I wasn't expecting that this was going to then be
used as the basis for anything other than maybe an excuse for
looking into the problem a little more deeply.  The critical
problem here seems to be that Lucky then quoted this number on
a mailing list before I'd had a chance to look more closely.
I don't think that there was any conflict of interest involved
at all given both the nature of the discussion and the fact
that these days cryptographic acceleration is pretty peripheral
to the nature of my business.

> - Lucky on the other hand suggested a practical security engineering
> approach to start to plan for possibility of migrating to larger key
> sizes.  Already one SSH implementation added a configuration option to
> select a minimum key size accepted by servers as a result.  This seems
> like a positive outcome.  Generally the suggestion to move to 2048 bit
> keys seems like a good idea to me.  Somewhat like MD5 -> SHA1, MD5
> isn't broken for most applications but it is potentially tainted by a
> partial result.  Similarly I would concur with Lucky that it's prudent
> security engineering to use 2048 bit keys in new systems.
> Historically for example PGP has had similar migrations from minimum
> listed key sizes for casual use from 512 -> 768 -> 1024 over the
> years.  The progression to 2048 is probably not a bad idea given
> current entry level computer speeds and possibility of Bernstein's
> approach yeilding an improvement in factoring.


I agree entirely.  The field of factoring is still moving forward
and with luck Bernstien's proposal will lead to him getting funding,
which will lead to new advances, and this my yet necessitate longer
keys in the future.  The biggest cause for concern with regards to
factoring at the moment is that 17% of the SSL servers on the net
are still using 512 bit keys and in countries like France (which have
in the past had domestic usage controls) the figure is more like 40%.
My research student last winter showed that 512 bit keys can be
factored in a matter of weeks using only the hardware found in a
busy 70 person office.  People tend not to change over existing
keys for longer ones as time goes by and now that 512 bit keys are
low hanging fruit people's inertia and resistance to altering working
server configurations is in danger of becoming a real problem.


> The mocking tone of recent posts about Lucky's call seems quite
> misplaced given the checkered bias and questionable authority of the
> above conflicting claims we've seen quoted.


I think your suggestion of bias is itself misplaced.  Most of
the comments on this that I have seen have been pretty measured.
Even if your cynicism is well founded in some cases I think that
the real problem here has been people being too swift to quote
and too slow to check with the source.

	Nicko




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list