Re: streql - Constant-time string comparison

[Riley Baird <BM-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch>]

On 31/10/14 09:43, Joel Rees wrote:
> I gotta quit coding when I should be asleep.
> 
> On Fri, Oct 31, 2014 at 12:38 AM, Joel Rees <joel.rees@gmail.com> wrote:
>> Here's the result of my work to this point:
>>
>> ---------------------------
>> /* Near-constant run time string/memory compare, with test frame.
>> ** by Joel Rees,
>> ** derived from work by Peter Scott, Riley Baird, et. al., see
>> ** https://lists.debian.org/debian-security/2014/10/msg00060.html
>> ** https://github.com/PeterScott/streql
>> **
>> ** Use allowed under GPL v. 3, see
>> ** http://www.gnu.org/copyleft/gpl.html
> 
> Correct that to:
> ** Use of those parts original with Joel Rees allowed specifically under
> ** the Apache License version 2.0:
> **     http://opensource.org/licenses/Apache-2.0 ,
> ** or the Academic Free License v. 2.1
> **     http://opensource.org/licenses/AFL-3.0 ,
> ** or the GPL v. 2.0, 3.0 or later:
> **     http://www.gnu.org/copyleft/gpl.html
> **
> ** Permission granted in advance
> ** for the Python Software Foundation to license or re-license
> ** any source code copyrights and/or patent rights held in such parts
> by Joel Rees
> ** as part of Python Software Foundation publications and distributions.
> **
> ** No claims or licensing assertions made concerning those parts not
> original with Joel Rees.
> 
>> */
>>
>> #include <string.h>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>>
>> /* dbg */ static int gcount = 0;
>>
>> // The core function: test two regions of memory for bytewise equality
>> with constant time.
>> // If cmplength is less than min( xlen, ylen ), comparison is incomplete.
>> // Lengths should be signed to make conditionals more balanced.
>> static int equals_internal_constime(
>> const char *x, int xlen,
>> const char *y, int ylen,
>> int cmplength) {
>>
>>   int result = 0;
>>
>>   while ( --cmplength >= 0 ) {
>>     char xtemp;
>>     char ytemp;
>>
>>     /* Using unsigned lengths here would induce unbalanced conditionals:
>>     ** unsigned int xlen;
>>     ** if ( xlen > 0 ) {
>>     **   xtemp = *x++;
>>     **   --xlen;
>>     ** }
>>     ** else {
>>     **   xtemp = 0;
>>     ** }
>>     ** While this might be a problem with 16 bit ints,
>>     ** you really aren't going to be comparing strings > 2^31 bytes
>> with this function.
>>     */
>>     xtemp = ( --xlen >= 0 ) ? *x++ : 0;
>>     ytemp = ( --ylen >= 0 ) ? *y++ : 0;
>>
>> /* dbg */    ++gcount;
>>     result |= xtemp ^ ytemp;
>> /* dbg  printf( "%c(%d):%c(%d) =>%d@%d\n", xtemp, xlen, ytemp, ylen,
>> result, gcount ); */
>>   }
>>
>>   return (xlen == ylen) && (result == 0);
>> }
>>
>>
>> int main( int argc, char * argv[] ) {
>>
>>     char * left, * right;
>>     int max = 32;
>>     int result = 0;
>>
>>     if ( argc > 2 ) {
>>       left = argv[ 1 ];
>>       right = argv[ 2 ];
>>       if ( argc > 3 ) max = strtol( argv[ 3 ], NULL, 0 );
>>       gcount = 0;
>>       result = equals_internal_constime( left, strlen( left ), right,
>> strlen( right ), max );
>>       printf( "result: %d, strcmp: %d, count: %d\n", result, strcmp(
>> left, right ), gcount );
>>       if ( result != ( strcmp( left, right ) == 0 ) ) {
>>         fputs( "*** failed ***\n", stdout );
>>       }
>>     }
>>
>>
>>     return EXIT_SUCCESS;
>> }
>> ---------------------------
>>
>> Note the change to signed lengths and the reasoning.
>>
>> --
>> Joel Rees

To clear up any licensing concerns:

For any code which I have the copyright on in the above code sample, I
also allow use under the Apache License 2.0 or the Academic Free License
v. 2.1 or the GNU General Public License version 2.0 as published by the
Free Software Foundation or, at your option, any later version.

Furthermore, permission is granted in advance for the Python Software
Foundation to license or re-license any source code copyrights and/or
patent rights held in such parts by Riley Baird as part of Python
Software Foundation publications and distributions.

----

This is a good way of doing the string comparison. However, it would
seem that upstream isn't really interested in hiding the length of the
strings, and doing so would only provide minimal security benefits.

Would you be willing to sponsor the upstream streql, or do you think
that this version should be packaged instead after being modified for
Python?