[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: streql - Constant-time string comparison



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

-- 
Joel Rees

Somebody should take the Berne Convention out behind the barn and burn
it with the other trash.


Reply to: