Re: streql - Constant-time string comparison
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.rees@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
>
>
Reply to: