)]}'
{
  "commit": "801a801024febe1a33add5ddaa719e257d97aba5",
  "tree": "441dfa69117d7bc360f4153e20e5c2132c146e62",
  "parents": [
    "13c9d5c69d04485a7a8840c12185c832026c8315"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Fri Jun 03 14:51:45 2022 -0400"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Fri Jun 03 20:24:06 2022 +0000"
  },
  "message": "Add an extra reduction step to the end of RSAZ.\n\nRSAZ has a very similar bug to mont5 from\nhttps://boringssl-review.googlesource.com/c/boringssl/+/52825 and may\nreturn the modulus when it should return zero. As in that CL, there is\nno security impact on our cryptographic primitives.\n\nRSAZ is described in the paper \"Software Implementation of Modular\nExponentiation, Using Advanced Vector Instructions Architectures\".\n\nThe bug comes from RSAZ\u0027s use of \"NRMM\" or \"Non Reduced Montgomery\nMultiplication\". This is like normal Montgomery multiplication, but\nskips the final subtraction altogether (whereas mont5\u0027s AMM still\nsubtracts, but replaces MM\u0027s tigher bound with just the carry bit). This\nwould normally not be stable, but RSAZ picks a larger R \u003e 4M, and\nmaintains looser bounds for modular arithmetic, a \u003c 2M.\n\nLemma 1 from the paper proves that NRMM(a, b) preserves this 2M bound.\nIt also claims NRMM(a, 1) \u003c M. That is, conversion out of Montgomery\nform with NRMM is fully reduced. This second claim is wrong. The proof\nshows that NRMM(a, 1) \u003c 1/2 + M, which only implies NRMM(a, 1) \u003c\u003d M, not\nNRMM(a, 1) \u003c M. RSAZ relies on this to produce a reduced output (see\nFigure 7 in the paper).\n\nThus, like mont5 with AMM, RSAZ may return the modulus when it should\nreturn zero. Fix this by adding a bn_reduce_once_in_place call at the\nend of the operation.\n\nChange-Id: If28bc49ae8dfbfb43bea02af5ea10c4209a1c6e6\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/52827\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\nCommit-Queue: David Benjamin \u003cdavidben@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "4bc1fa2c59820a18597e5b5ca016edb1b10dba47",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/bn_tests.txt",
      "new_id": "9a1a5db9291aec2ae52122c59a050d065ded067c",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/bn_tests.txt"
    },
    {
      "type": "modify",
      "old_id": "7e15aaf948f286f3649b886416758644409b9899",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/rsaz_exp.c",
      "new_id": "074f05d89545749425c6fb8edb98d358655ad45c",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/rsaz_exp.c"
    },
    {
      "type": "modify",
      "old_id": "104bb7a41c5f5569651ef031a4ce338b2f4060d8",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/rsaz_exp.h",
      "new_id": "bc7a439e75c6002895ca8017db654537ba7c6aae",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/rsaz_exp.h"
    }
  ]
}