Constant-time subrange copy

Objective: Given the address p and length psz of a source buffer, the address q and length qsz of a destination buffer, and a secret offset o, copy up to qsz bytes starting from p + o to the destination, without leaking o.

Motivation

There are two obvious applications for this algorithm.

• RSA PKCS #1 v1.5 decryption. After applying the RSA private-key operation, the buffer contains 00 || 02 || PS || 00 || M, where PS is a string of eight or more random nonzero padding bytes. This scheme is, unfortunately, unaccountably popular despite it being broken in 1999. There's a standard countermeasure if the payload M is supposed to be a random key, which involves substituting a fresh random key if the padding is bad; but doing this means that the entire process needs to run in constant time.

• TLS MAC tag extraction. A TLS record, prior to or after encryption, consists of a payload, a MAC tag, and between 1 and 256 bytes of padding. Unfortunately, having the MAC inside the encryption and padding was a terrible mistake, leaving the whole scheme open to chosen-ciphertext attacks. Checking the tag first means finding and extracting it, but that has to be done without leaking how much padding there is.

Algorithm

This algorithm is an improvement on the one used in Langley's code in OpenSSL. It proceeds in two stages.

• Firstly, copy the wanted bytes from the source to the destination. This requires a full pass over the source, but that's unavoidable if we want to equivocate on the secret offset. The trick here (from OpenSSL) is that we get the right bytes, but not necessarily in the right places: they might end up rotated, by o mod qsz bytes.

• Secondly, undo the rotation so that the destination contains the correct data. OpenSSL does the obvious qsz² loop; but there's a better way: if we equivocate on each bit of the offset separately, we can undo the rotation in qsz log qsz copies.

Code

WIP...