)]}'
{
  "commit": "de434576d7412b95a8eb90d613fc9f01e2d7166b",
  "tree": "a74904a6068ffc143d9fc18335c1e26ea192062c",
  "parents": [
    "3ae0778f3d60a078356a683ee3a9a825008c6711"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Tue Nov 15 20:34:28 2022 -0500"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Mon Nov 28 23:17:25 2022 +0000"
  },
  "message": "Fix allocation size in BN_mod_exp_mont_consttime.\n\npowerbuf\u0027s layout is:\n- num_powers values mod m, stored transposed\n- one value mod m, tmp\n- one value mod m, am\n- (mont5-only) an extra copy of m\n\npowerbuf_len broadly computed this, but where tmp + am would be\nsizeof(BN_ULONG) * top * 2, it used\nsizeof(BN_ULONG) * max(top * 2, num_powers).\n\n(In the actual code it\u0027s written as a ternary op and some\nmultiplications are factored out.)\n\nThat is, it allocated enough room for tmp + am OR an extra row in the\nnum_powers table, as if each entry were top + 1 words long instead of\ntop, with the space overlapping. This expression dates to upstream\u0027s\nhttps://github.com/openssl/openssl/commit/361512da0d900ba276096cbd152e304d402aca65,\nthough the exact layout has shifted over the years as mont5 evolved.\n(Originally, it only contained one extra value mod m.)\n\nAt the time, this was necessary because bn_mul_mont_gather5 actually\noverreads the table by one row! Although it only uses top * 32 words, it\nrequires the table to have (top + 1) * 32 words. This is because the\ncomputation was scheduled so that the .Louter4x loop would read and mask\noff the next iteration\u0027s value while incorporating the previous\niteration:\n\nThere were masked reads from $bp into XMM registers at the start of the\nloop:\nhttps://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L541\n\nThe XMM logic is interleaved throughout and does not move to a\ngeneral-purpose register, $m0, until much later. $m is not read again\nuntil after the jump.\nhttps://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L700\n\nMeanwhile, the loop is already reading $m0 at the start of the\niteration.\nhttps://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L551\n\nThe whole thing is bootstrapped by similar code just above it:\nhttps://github.com/openssl/openssl/blob/361512da0d900ba276096cbd152e304d402aca65/crypto/bn/asm/x86_64-mont5.pl#L531\n\nIn the final iteration, we read one extra row into $m0 but never use it.\nThat is the overread.\n\nI also confirmed this by rewinding our x86_64-mont5.pl to this state,\nhacking things up until it built, and then hacking up\nBN_mod_exp_mont_consttime to place the table in its own allocation, with\nno extra slop using C11 aligned_alloc. This was so valgrind could\naccurately instrument the bounds. When I did that, valgrind was clean if\nI allocated (top + 1) * num_powers, but flagged an out-of-bounds read at\ntop * num_powers.\n\nThis no longer applies. After\nhttps://github.com/openssl/openssl/commit/25d14c6c29b53907bf614b9964d43cd98401a7fc,\nbn_mul_mont_gather5\u0027s scheduling is far less complicated. .Louter4x now\nbegins with a masked read, setting up $m0, and then it incorporates $m0\ninto the product. The same valgrind strategy confirmed this. Thus, I\ndon\u0027t believe this extra row is needed and we can allocate the buffer\nstraightforwardly.\n\nChange-Id: I6c1ee8d5ebdb66eb4e5fec63d2140814c13ae146\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/55231\nReviewed-by: Bob Beck \u003cbbe@google.com\u003e\nCommit-Queue: Bob Beck \u003cbbe@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "2903ede77efde4c4ad29a52c5e34050a3981cea5",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/exponentiation.c",
      "new_id": "afa8e71020b96c79c19880f77acdddeba32ad11e",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/exponentiation.c"
    }
  ]
}