IP: Bernstein, Factoring, and RSApkc

[Dave Farber <dave () farber net>]

------ Forwarded Message
From: Vin McLellan <vin () shore net>
Date: Wed, 03 Apr 2002 13:07:07 -0500
To: Dave Farber <dave () farber net>
Subject: <fyi> Bernstein, Factoring, and RSApkc

Dave,

Information Security Magazine just published my column about public and
professional reaction to Dan Bernstein's innovative design ideas for a new
Factoring Engine.  It might be of interest to IPers.

Regards,  _Vin

-----------------------------------

"Factoring Friction"

Daniel Bernstein's proposal for crunching encryption keys sparks a lively
debate in the crypto community.

URL: http://www.infosecuritymag.com/2002/apr/news.shtml#factoringfriction
By Vin McLellan
Information Security Magazine


When mathematician Daniel Bernstein quietly published "Circuits for Integer
Factorization" last fall, there was little indication that the brief
research proposal would roil the industry in debate and threaten confidence
in the widely used RSA public key cryptosystem.

The difficulty of factoring a composite number into two primes is the
so-called "hard problem" that Ron Rivest, MIT cryptographer and RSA
Security (www.rsasecurity.com) cofounder, used 25 years ago as the basis
for RSApkc. Advances in factoring-brute-force key searches, in the context
of RSA-have prompted incremental increases in the size of the RSA keys used
in common systems like SSL (now typically between 1,024 and 2,048 bits).

Bernstein, a widely respected University of Illinois computer theorist,
asked the National Science Foundation to fund a two-month, $67,000 research
project that would explore the prospects for using special-purpose chips
and an eccentric configuration of parallel operations to cut the cost of
factoring with the Number Field Sieve (NFS). For a decade, the evolving NFS
paradigm has been the "known best method" for factoring composite numbers.

Bernstein claimed that his design for a new two-stage factoring machine
could-under certain conditions-triple the price performance of the
convoluted NFS algorithm. Gilding his proposal with the provocative tone of
an experienced grant writer, he wrote, "A team led by Herman te Riele used
the number field sieve on general-purpose computers to factor a difficult
512-bit integer in August 1999. Is it now possible to factor 1,536-bit
integers at reasonable cost?"

The open question, Bernstein acknowledged later, is whether the theoretical
shortcuts he has discovered for factoring gargantuan numbers, "maybe
billions of bits long," can survive a transition from abstract number
theory to computer science, and perhaps still be relevant in the range of
much smaller numbers, used in RSA keys.

According to Moore's Law, the speed of computers doubles every 18 months,
something that benefits both cryptographers and cryptanalysts. While the
cost of using longer crypto keys rises linearly for every bit added, the
cost of attacks upon longer keys rises exponentially. This matrix leaves
mathematicians who specialize in measuring the resistance of crypto to
brute-force attacks pushing the envelope in their search for conceptual
breakthroughs. They argue about viable metrics: time, cost, space and
energy.

Two years ago, NFS pioneer Robert Silverman calculated-using the celebrated
1999 crack of RSA-512 as a base-that it would take an effort 7 million
times greater and require 2,650 times more memory to factor a 1,024-bit
number.

Calling Silverman's figures "obsolete," Bernstein argued that he could
radically speed the process, cut the cost and sidestep the overwhelming
memory demands of NFS by replacing memory with a huge number of tiny
"elliptic curve method" factorization units mounted on chips.

Incremental advances in the craft of factoring have paced the industry's
recommendations for "safe" crypto key sizes. Yet, "there is virtually no
relationship between the cost of a brute-force attack and IT security,"
notes veteran infosec consultant William H. Murray. Given the
vulnerabilities routinely discovered in computer systems, applications
(even crypto applications) and implementations, he declared, "If DES or
512-bit RSA are the weak links in your security, then you are very secure
indeed."

"One Cute Idea"

The intense, sometimes emotional public reaction to Bernstein's claims
reflects a fearful uncertainty that haunts commercial crypto. Conventional
wisdom presumes that the cutting-edge expertise in attacking cryptosystems
lies not in the public realm, but in the murky domain of the huge, lushly
funded signals intelligence agencies, such as the National Security Agency.

In late February, debates about Bernstein's ideas exploded in a sometimes
near-hysterical 500-message thread on Slashdot.org. As the subject came to
dominate several other prominent Internet forums, some of the leading
experts on factoring, number theory and cryptography began analyzing
Bernstein's model.

Leading numbers theorist Carl Pomerance of Bell Labs says Bernstein's ideas
are "fresh and exciting" and well worth further study. However, others-even
Bernstein admirers-are skeptical.

"To be honest, I have no idea what all the fuss is about," says Arjen
Lenstra, Citibank's VP for emerging technologies and perhaps the dean of
American factoring practitioners. "My impression is that [Bernstein's
paper] contains one cute idea." That idea: using a fast-sorting device to
obtain the "sparse matrix times vector product," part of the classic NFS
endgame.

"A much faster factoring method should not come as a surprise, since there
is no evidence the problem is intrinsically hard. Unfortunately, Dan's
paper does not provide any important new insights. We're still stuck at L
(the traditional NFS run-time function), maybe even more so than before,"
says Lenstra. "I expect more interesting practical factoring results from
quantum computers than I do from Dan's circuits."

However, the debate among security professionals had reached such a fevered
pitch by mid-March that the organizers of the Financial Cryptography
Conference (FCC) in Bermuda felt compelled to scheduled a special "rump"
session on Bernstein's research and its implications.

By then, Bernstein was begging reporters to find something else to write
about. After all, Bernstein only sought to further explore its feasibility
and estimate the cost of implementing his idea, not build such a
machine-which would likely cost millions of dollars.

"This is a theoretical advance," he says. "I have no idea and, unless the
NSA has built a circuit for this already, nobody else has any idea how
practical it might be."

[This column appears in the April 2002 issue of Information Security
magazine <www.infosecuritymag.com>. Copyright (c) 2002. All rights
reserved.]




------ End of Forwarded Message

For archives see:
http://www.interesting-people.org/archives/interesting-people/