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]