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: