tree 0622790a2e6ed2b67552a920a838531c4a9067e5
parent b01dd1c622448f185bde4626880611704a50be8b
author David Benjamin <davidben@google.com> 1516973455 -0500
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1517885494 +0000

Make bn_mul_recursive constant-time.

I left the input length as int because the calling convention passes
these messy deltas around. This micro-optimization is almost certainly
pointless, but bn_sub_part_words is written in assembly, so I've left it
alone for now. The documented preconditions were also all completely
wrong, so I've fixed them. We actually only call them for even tighter
bounds (one of dna or dnb is 0 and the other is 0 or -1), at least
outside bn_mul_part_recursive which I still need to read through.

This leaves bn_mul_part_recursive, which is reachable for RSA keys which
are not a power of two in bit width.

The first iteration of this had an uncaught bug, so I added a few more
aggressive tests generated with:

  A = 0x...
  B = 0x...

  # Chop off 0, 1 and > 1 word for both 32 and 64-bit.
  for i in (0, 1, 2, 4):
    for j in (0, 1, 2, 4):
      a = A >> (32*i)
      b = B >> (32*j)
      p = a * b
      print "Product = %x" % p
      print "A = %x" % a
      print "B = %x" % b
      print

Bug: 234
Change-Id: I72848d992637c0390cdd3c4f81cb919393b59eb8
Reviewed-on: https://boringssl-review.googlesource.com/25344
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>