IP: New security vulnerability: 13-year-old 'r00ts' popular polynomial Risks Digest 21.03

[Dave Farber <farber@cis.upenn.edu>]

>Date: Thu, 24 Aug 2000 13:59:24 -0500
>From: Leonard Richardson <leonardr@segfault.org>
>Subject: New security vulnerability: 13-year-old 'r00ts' popular polynomial
>
>   [With permission, at the request of PGN.]
>
>13-Year-Old 'r00ts' Popular Polynomial
>
>The well-known polynomial x^2+8x+6 was defaced today by a teenager who had
>"r00ted" the beloved function of one variable through the use of a popular
>script known as "QuAd 3QaZh0n".  The attack set off the usual sequence of
>events: an initial panic setting off an orgy of media hype reaching a
>crescendo with an article in the mainstream media, a string of copycat
>successors, and a meaningless stream of empty promises from vendors who
>immediately lapsed back into apathy as the incident left the public's
>short-term memory.
>
>Segfault spoke with the culprit, who goes by the name of "2o31js34g",
>although his real name is Alvin Schumaker.  "I did it for the kicks," said
>the eighth-grade desperado.  "Also, it was problem 12 on my algebra homework."
>
>Schumaker's admission that he had learned the technique used to crack the
>equation "in class" led to sweeping reforms at Nathan Hale Middle School,
>his alma mater.  These range from a draconian school uniform policy to
>periodic cavity searches to Internet filters on library computers so
>restrictive that they ban the school's own home page.
>
>"If these kids would just study their math, we wouldn't have anybody
>learning these dangerous equation things," said Nathan Hale principal Fred
>Fractal, previously known for shutting down the wood shop because "those
>nail things look like weapons."
>
>Numerous other tools are available for cracking polynomials exist, such as
>Fac-t0R.  More worrying are tools for "solving" large groups of linear
>equations at a time; one such program makes reference to a "matrix",
>obviously an homage to the sci-fi classic.
>
>Many such programs are distributed for the TI series of "calculators",
>tools widely viewed as a security threat in many fields and rings.
>Disturbingly, such devices are increasingly being made avaliable to high
>school and college students.  Public policy must now answer the question:
>where is the line to be drawn between useful tool and bloodthirsty weapon
>of mathematical carnage? Who will answer for the countless linear equations
>to have undergone Gaussian elimination?
>
>Predictably, immediately following the defacement, thousands of polynomial
>security companies came out of the woodwork to hawk their shoddy products.
>
>"Our proprietary polynomials are one hundred percent safe because they have
>no roots at all," said Len Eir of Rootless.com, a company offering sales
>and consulting for polynomials such as x^2+4 and x^6+x^2+101.  Despite Eir's
>claims, attacks on such polynomials are not uncommon, although Eir
>dismissed all such reports as "imaginary".
>
>Dave Errential of Integrated Systems stated: "Integration technology makes
>it easy to add roots to your polynomial.  Take 60x^2+264x, for instance.  The
>roots for that polynomial have been posted in a million places on the web.
>But our proprietary integration technology can turn that into 5x^4+44x^3!
>I'd like to see someone try and find the roots of that polynomial!" [Try
>x=0. --Ed.] Research has shown that IS polynomials are vulnerable to several
>types of attacks, but, again, the vendor has chosen to go after the
>research, calling it "derivative", rather than investigate the
>vulnerabilities.
>
>"Our polynomials are of a magnitude so high that it would be impossible to
>find their roots even with the most sophisticated technology," said
>OrderOfMagnitude.com's Sean Gular.  "Our proprietary technology allows us to
>offer x to the power of one billion, x to the power of one trillion, even x
>to the power of ten gazillion! No one can crack these polynomials!" [Try
>x=0. --Ed.]
>
>"It's irresponsible to distribute these polynomial-cracking kits," says
>security expert Bruce Schneier of Counterpane Internet Security.  "It's like
>teaching a baby how to do surface integrals.  He doesn't understand the
>socially responsible way to use this knowledge, so he wreaks havoc." For
>improved security, Schneier urges all polynomials to be of fourth order or
>higher, and to change roots at least once every two weeks.
>
>Originally published on segfault.org:
>   http://segfault.org/story.phtml?id=396f3e5c-0958dfa0
>Written by Leonard Richardson <leonardr@segfault.org>
>Posted on Fri 14 Jul 09:24:53 2000 PDT
>
>   [Bastille Day, eh?  Well, although it is a little late for the 1 April
>   RISKS issue, this item seemed very timely in light of certain continuing
>   efforts to control the underpinnings of cryptography.  PGN]