I think I see the confusion between us. You are concerned with a fast algorithm for determining equality of strings, whereas this program is designed to be run in constant time, even if it is slower than a variable time comparison.
For example, I don't know any practical hashing algorithms for variable length strings that run in constant time. On 31/10/14 11:11, Leslie S Satenstein wrote: > > > Even if you inline your code, (previous examples) I don't think any of the > functions presented is faster than memcmp() from the standard C library. > Earlier email I presented a challenge for searching a table containing a > large number of strings. I indicated that class of problem brings about its > own method of solution. > I have used may tricks to speed up string matching, including the use of > hashing. This subject and example can be handled off line. > Regards > Leslie > Mr. Leslie Satenstein > Montréal Québec, Canada > > > > From: Joel Rees <joel.r...@gmail.com> > To: "debian-security@lists.debian.org" <debian-security@lists.debian.org> > Sent: Thursday, October 30, 2014 11:38 AM > Subject: Re: streql - Constant-time string comparison > > 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 > */ > > #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 UNSUBSCRIBE, email to debian-security-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/54549d14.1090...@bitmessage.ch
