Pentium bug and CRYPTO

-----BEGIN PGP SIGNED MESSAGE-----

Will the following error (Re Pentium Floating Point Bug     Date: 15 Nov 
1994)
cause problems with PGP key generation or any other normal operations with
PGP or other crypto.  I'm not a math mathmatics nerd but I know we generally 

deal with big numbers.

   For all of you paranoids out there, YES this is a plot by NSA to weeken
our crypto capabilities, this is the only bug that we KNOW about :)

NOTE:  I'm currently not receiving cypherpunks mailing for some reason.  I'm 
not
sure why, so please copy me on your posts.  (Hughes, have you had a chance 
to
look at this?)

     Thanks!

                                        ...  __o
                                       ..   -\<,
chris.claborne@sandiegoca.ncr.com      ...(*)/(*).          CI$: 76340.2422
PGP Pub Key fingerprint =  A8 FA 55 92 23 20 72 69  52 AB 64 CC C7 D9 4F CA
Avail on Pub Key server.
PGP-encrypted e-mail welcome!

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

> >>> >
> >>> > Subject: Pentium Floating Point Bug     Date: 15 Nov 1994
> >>> > Summary: Divisions might give incorrect results on Pentium
> >>> >
> >>> >               Pentium Floating Point Division Bug
> >>> >
> >>> > There has been a flurry of activity the last fews days on the
> >>> > Internet news group, comp.sys.intel, that should interest MATLAB
> >>> > users.  A serious design flaw has been discovered in the floating
> >>> > point unit on Intel's Pentium chip.  Double precision divisions
> >>> > involving operands with certain bit patterns can produce incorrect
> >>> > results.
> >>> >
> >>> > The most dramatic example seen so far can be extracted from a
> >>> > posting last night by Tim Coe of Vitesse Semiconductor.  In MATLAB,
> >>> > his example becomes
> >>> >
> >>> >     x = 4195835
> >>> >     y = 3145727
> >>> >     z = x - (x/y)*y
> >>> >
> >>> > With exact computation, z would be zero.  In fact, we get zero on
> >>> > most machines, including those using Intel 286, 386 and 486 chips.
> >>> > Even with roundoff error, z should not be much larger than eps*x,
> >>> > which is about 9.3e-10.  But, on the Pentium,
> >>> >
> >>> >     z = 256
> >>> >
> >>> > The relative error, z/x, is about 2^(-14) or 6.1e-5.  The computed
> >>> > quotient, x/y, is accurate to only 14 bits.
> >>> >
> >>> > An article in last week's edition of Electronic Engineering Times
> >>> > credits Prof. Thomas Nicely, a mathematics professor at Lynchburg
> >>> > College in Virginia, with the first public announcement of the
> >>> > Pentium division bug.  One of Nicely's examples involves
> >>> >
> >>> >     p = 824633702441
> >>> >
> >>> > With exact computation
> >>> >
> >>> >     q = 1 - (1/p)*p
> >>> >
> >>> > would be zero.  With floating point computation, q should be on
> >>> > the order of eps.  On most machines, we find that
> >>> >
> >>> >     q = eps/2 = 2^(-53) ~= 1.11e-16
> >>> >
> >>> > But on the Pentium
> >>> >
> >>> >     q = 2^(-28) ~= 3.72e-09
> >>> >
> >>> > This is roughly single precision accuracy and is typical of the
> >>> > most of the examples that had been posted before Coe's analysis.
> >>> >
> >>> > The bit patterns of the operands involved in these examples
> >>> > are very special.  The denominator in Coe's example is
> >>> >
> >>> >     y = 3*2^20 - 1
> >>> >
> >>> > Nicely's research involves a theorem about sums of reciprocals
> >>> > of prime numbers.  His example involves a prime of the form
> >>> >
> >>> >     p = 3*2^38 - 18391
> >>> >
> >>> > We're not sure yet how many operands cause the Pentium's floating
> >>> > point division to fail, or even what operands produce the largest
> >>> > relative error.  It is certainly true that failures are very rare.
> >>> > But, as far as we are concerned, the real difficulty is having to
> >>> > worry about this at all.  There are so many other things than can
> >>> > go wrong with computer hardware, and software, that, at least, we
> >>> > ought to be able to rely on the basic arithmetic.
> >>> >
> >>> > The bug is definitely in the Pentium chip.  It occurs at all clock
> >>> > rates.  The bug does not affect other arithmetic operations, or the
> >>> > built-in transcendental functions.  Intel has recently made changes
> >>> > to the on-chip Program Logic Array that fix the bug and is now
> >>> > believed to be producing error free CPUs.  It remains to be seen
> >>> > how long it will take for these to reach users.
> >>> >
> >>> > An unnamed Intel spokesman is quoted in the EE Times article as
> >>> > saying "If customers are concerned, they can call and we'll replace
> >>> > any of the parts that contain the bug."  But, at the MathWorks,
> >>> > we have our own friends and contacts at Intel and we're unable
> >>> > to confirm this policy.  We'll let you know when we hear anything
> >>> > more definite.  In the meantime, the phone number for Customer
> >>> > Service at Intel is 800-628-8686.
> >>> >
> >>> >    -- Cleve Moler     moler@mathworks.com
> >>> >    Chairman and Chief Scientist, The MathWorks, Inc.
> >>> >
> >>>
> >>
> >>
> >>--
> >>Steve
> >>
> >>
> 
>>--------------------------------------------------------------------------
> >>-----
> >>-
> >> I am in the field on the Outer Banks of North Carolina until 27 
November.
> >> From 28 Nov - 4 Dec I will be on the Dream Cruise in the Atlantic.
> >> After the cruise I will go to AGU, and finally to Pullman about 8 Dec.
> >>
> >>
> >> Steve Elgar                            FAX :      (919) 261-4432
> >> Army Research Pier                     ATT :      (919) 261-1706
> >> 1261 Duck Road                         OMNET:     s.elgar
> >> Kitty Hawk, NC 27949                   internet:  elgar@eecs.wsu.edu
> >>
> >>
> >>

 -----BEGIN PGP SIGNATURE-----
Version: 2.7

iQCVAwUBLtCzSlzvpSsKhLftAQEvLgQApXWCmyqkp2gh66Kpfk7EQk0XQL9aqb3b
i18QnfYFYYtzvK+wZHEtB+AR3ksZGDJ7RgNkRlB3JF1sFF1HnRhUOnjppJGCMqhY
f0ZzrwEN+k0jHg6K3sfXdKCmbZ/CKdypc+eZW69Nh2WVtO/RPwIrKo/GlAVSzeK1
1pVXULR+qxE=
=SUYe
 -----END PGP SIGNATURE-----

This floating point bug is only in double-precision floating-point
division.  No division is used in RSA Key Generation, RSA Encryption,
or RSA Decryption, so this bug should not cause any problems in PGP.

-derek

On Mon, 21 Nov 1994, Derek Atkins wrote:

> This floating point bug is only in double-precision floating-point
> division.  No division is used in RSA Key Generation, RSA Encryption,
> or RSA Decryption, so this bug should not cause any problems in PGP.

Some time ago I checked with Mr. Z as to whether PGP was integer
arithmetic and was told yes.  This seems to confirm the above.


-NetSurfer

#include <standard.disclaimer>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
==  =     = |James D. Wilson        |V.PGP 2.7:   512/E12FCD 1994/03/17 >
 "  "  o  " |P. O. Box 15432        |     finger for full PGP key        >
 "  " / \ " |Honolulu, HI  96830    |====================================>
\"  "/ G \" |Serendipitous Solutions|    Also NetSurfer@sersol.com      >
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Claborne, Chris wrote:

> Will the following error (Re Pentium Floating Point Bug     Date: 15 Nov 
> 1994)
> cause problems with PGP key generation or any other normal operations with
> PGP or other crypto.  I'm not a math mathmatics nerd but I know we generally 
> 
> deal with big numbers.

We do indeed deal with "big numbers," but big INTEGER numbers. Whole
numbers.

The Pentium FDIV bug shows up only, so far as is known, with certain
floating point numerator/denominator combinations. No crypto
computation I can imagine would use the FDIV instruction.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
Cypherpunks list: majordomo@toad.com with body message of only: 
subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tcmay

"Claborne, Chris" <claborne@microcosm.sandiegoca.NCR.COM> writes:

 > Will the following error (Re Pentium Floating Point Bug
 > Date: 15 Nov 1994) cause problems with PGP key generation or
 > any other normal operations with PGP or other crypto.  I'm
 > not a math mathmatics nerd but I know we generally deal with
 > big numbers.

No problems for released versions of PGP, which use only the 8086
instruction set and require neither a floating point coprocessor
nor emulation.

Most other crypto should be fine as well.  Crypto is pretty much
an integer exercise.

People have been known to use floating point to do multiprecision
integer arithmetic on Sparcs and large engineering mainframes
which lack a complete integer instruction set, but I've never
heard of anyone trying such things on an Intel processor.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

On Mon, 21 Nov 1994, Mike Duvos wrote:

> Most other crypto should be fine as well.  Crypto is pretty much
> an integer exercise.

I'd be horrified if a crypto implementation used floating point, with
the implied imprecision...

-- 
Dave Horsfall (VK2KFU) | dave@esi.com.au | VK2KFU @ VK2AAB.NSW.AUS.OC | PGP 2.6
Opinions expressed are mine. | E7 FE 97 88 E5 02 3C AE  9C 8C 54 5B 9A D4 A0 CD

Dave Horsfall writes:
 > I'd be horrified if a crypto implementation used floating point, with
 > the implied imprecision...

The imprecision in floating point is a factor only if you choose to
pay attention to it.  It is possible to use floating point all day
long to do what are essentially integer calculations.  indeed, there
have been CPUs (the CDC 6000 series come to mind) that have no integer
multiply or divide instruction.  Instead, one used the floating point
instructions and then extracted the result (carefully) from the
mantissa.

Floating point isn't magic, it's just microcode.  (Well, not in the
CDC 6000 I guess...)

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

On Wed, 23 Nov 1994, Mike McNally wrote:

> The imprecision in floating point is a factor only if you choose to
> pay attention to it.  It is possible to use floating point all day
> long to do what are essentially integer calculations.  indeed, there
> have been CPUs (the CDC 6000 series come to mind) that have no integer
> multiply or divide instruction.  Instead, one used the floating point
> instructions and then extracted the result (carefully) from the
> mantissa.

Quite so - my mistake.  It's been a while since I last looked at FPUs...

> Floating point isn't magic, it's just microcode.  (Well, not in the
> CDC 6000 I guess...)

Indeed - Seymour Cray was proud of the fact that his CDC machines
did not use microcode - that's what made them so fast.

-- 
Dave Horsfall (VK2KFU) | dave@esi.com.au | VK2KFU @ VK2AAB.NSW.AUS.OC | PGP 2.6
Opinions expressed are mine. | E7 FE 97 88 E5 02 3C AE  9C 8C 54 5B 9A D4 A0 CD