Mdw: Created page with "'''Objective:''' Given the address `p` and length `psz` of a source buffer, the address `q` and length `qsz` of a destination buffe..."

2016-10-18T00:52:39Z

Created page with "'''Objective:''' Given the address <code>p</code> and length <code>psz</code> of a source buffer, the address <code>q</code> and length <code>qsz</code> of a destination buffe..."

New page

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

== 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 <code>00</code> || <code>02</code> || ''PS'' || <code>00</code> || ''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 <code>o</code> mod <code>qsz</code> bytes.

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

== Code ==

WIP...

Constant-time subrange copy - Revision history

Mdw: Created page with "'''Objective:''' Given the address p and length psz of a source buffer, the address q and length qsz of a destination buffe..."

Mdw: Created page with "'''Objective:''' Given the address `p` and length `psz` of a source buffer, the address `q` and length `qsz` of a destination buffe..."