[gmp-devel] new paper on cryptography compromise from bugs in arithmetic

[Nelson H. F. Beebe]

After I posted a note similar to the following one to the related mpfr
list, Paul Zimmermann suggested that I inform the gmp-devel list as well.
Here it is:

Earlier this week, I recorded the paper whose BibTeX appears below,
and four days ago, I finished reading it.  Its authors are well-known
cryptographers, and the third of them is the A in RSA public-key
cryptography, and co-winner of the 2002 ACM Turing Award for that
discovery.

Their paper describes how errors in arithmetic can be exploited to
recover encryption keys, sometimes with little effort at all, and
other times, with greatly reduced complexity of attack.  They list a
dozen or more known hardware errors, and suggest that CPU chips could
be intentionally compromised (and in fact, have been) to cause such
errors rarely, with little likelihood of detection (x * y, for
particular 64-bit x and y, would appear randomly with probability
2**(-128): it could take 2**(128) * 10**(-9) / (3600 * 24 * 365) ~=
10**22 years of testing before that pair was found, assuming a
nanosecond per operation).

They show that a chosen plaintext could be made to cause the (x,y)
pair to appear during the encryption, leading to a compromise, and
full key recovery.

Why is this of interest to the gmp-devel list?  Well, exhaustive
testing of arithmetic implementations, whether in software or in
hardware, is infeasible for 64-bit and larger operands, so
understanding how such attacks work might lead to a better
understanding of how to prepare unit tests of the implementation that
might be better at exposing obscure errors.

@String{j-J-CRYPTOLOGY = "Journal of Cryptology: the journal of the
                          International Association for Cryptologic Research"}

@Article{Biham:2016:BA,
  author =       "Eli Biham and Yaniv Carmeli and Adi Shamir",
  title =        "Bug Attacks",
  journal =      j-J-CRYPTOLOGY,
  volume =       "29",
  number =       "4",
  pages =        "775--805",
  month =        oct,
  year =         "2016",
  CODEN =        "JOCREQ",
  DOI =          "http://dx.doi.org/10.1007/s00145-015-9209-1",
  ISSN =         "0933-2790 (print), 1432-1378 (electronic)",
  ISSN-L =       "0933-2790",
  bibdate =      "Mon Sep 12 07:07:07 MDT 2016",
  bibsource =    "http://link.springer.com/journal/145/29/4;
                 http://www.math.utah.edu/pub/tex/bib/fparith.bib;
                 http://www.math.utah.edu/pub/tex/bib/jcryptology.bib",
  URL =          "http://link.springer.com/accesspage/article/10.1007/s00145-015-9209-1;
                 http://link.springer.com/article/10.1007/s00145-015-9209-1",
  acknowledgement = ack-nhfb,
  fjournal =     "Journal of Cryptology",
  journal-URL =  "http://link.springer.com/journal/145",
  keywords =     "Bug attack; ElGamal encryption; Fault attack; Pohlig
                 Hellman; RSA",
  remark =       "From the abstract: ``The best-known example of such a
                 bug is the Intel division bug, which resulted in
                 slightly inaccurate results for extremely rare inputs.
                 \ldots{} such bugs can be a security disaster:
                 decrypting ciphertexts on any computer which [sic]
                 multiplies even one pair of numbers incorrectly can
                 lead to full leakage of the secret key, sometimes with
                 a single well-chosen ciphertext.",
}

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------