arbitrary length string comparisons with rudimentary protection against timing.

gistfile1.txt

/* Copyright 2012,2015 Dirk-Willem van Gulik <dirkx(at)webweaving.org>

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

With help from andya@apache.org / Andy Armstrong.
*/


#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

#define AP_DECLARE(x) x
#define CHAR_BIT (8)

#include <sys/time.h>
#include <stdio.h>

float timedifference_msec(struct timeval t0, struct timeval t1)
{
    return (t1.tv_sec - t0.tv_sec) * 1000.0f + (t1.tv_usec - t0.tv_usec) / 1000.0f;
}

/* Quick mickey mouse version to compare the strings. XXX fixme. 
 */

/* If a string is 'hostile' -- asume we can reveal its length. Otherwise
 * try to hide it by a runtime proprotional to the length of the other
 * string; if needed with a minimum of 1024 rounds; to somewhat protect
 * strings shorter than that (ignoring cache issues).
 */

typedef enum ap_compareflag_t {
	AP_HOSTILE_STR1 = 1,	
	AP_HOSTILE_STR2 = 2,
	AP_MIN1024 = 4 ,
	AP_MIN2048 = 8 ,
	AP_MIN4096 = 16
} ap_compareflag_t;

AP_DECLARE(int) ap_timingsafe_strcmp(const char * str1, const char * str2, ap_compareflag_t flags) {
        const unsigned char *p1 = (const unsigned char *)str1;
	const unsigned char *p2 = (const unsigned char *)str2;
        size_t i = 0;
        size_t i1 = 0 ,i2 = 0;
	unsigned int d1 = 1, d2 = 1;
        unsigned int res = 0;

	if (flags == 0)
		flags = AP_MIN1024;

#ifdef VALIDATE
	// suggestion of Martijn - to avoid the rolling of the bits; in ANSI-C
	// a !0 is guaranteed to be 1.
	assert((!!0) == 0);
	assert((!!1) == 1);
	assert((!!2) == 1);
	assert((!!-1) == 1);
	assert((!!12345) == 1);
#endif

#ifdef VALIDATE
	printf("Compare\t<%s> %s\n\t<%s> %s\n\t<", 
		str1,(flags & AP_HOSTILE_STR1) ? "hostile" : "private", 
		str2,(flags & AP_HOSTILE_STR2) ? "hostile" : "private");
#endif

#ifdef MODULO
        i1 = 1;
	i2 = 1;
#endif
	do {
          do {
#ifdef MODULO
		// we use modulo to run repeatedly through a (shorter)
		// string (or at least 1024 chars) as to avoid cache
		// timings having too much of an impact (if we where
		// to hit the (last) char once we've 'ran out' of
		// the shorter string. 
		//
		// Q: is there a cost/downside; like running over
		// a page boundery too often ?
		//
		res |= (p1[i % i1] - p2[i % i2]);

		// Set the left/right string advancers permanently
		// to zero once we've hit the the \0.
		//
		d1 &= !!p1[i % i1];
		d2 &= !!p2[i % i2];
#else
		res |= (p1[i1] - p2[i2]);
		d1 &= !!p1[i1];
		d2 &= !!p2[i2];
#endif
		i1 += d1;
		i2 += d2;
		i++;
#ifdef VALIDATE
		printf("%c", ((d1 & d2) ? '3' : (d1 ? '1' : (d2 ? '2' : '.'))));
#endif

	   } while(i < ((flags & ~(AP_HOSTILE_STR1|AP_HOSTILE_STR2)) * 256));
	} while (((flags & AP_HOSTILE_STR1) && d1) | ((flags & AP_HOSTILE_STR2) && d2));
#ifdef VALIDATE
	printf(">\n");
#endif

        // include the length in the coparision; as to avoid foo v.s. foofoofoo to match.
	//
	res |= (i1 - i2);

        return (int) res;
}


#define TT(x) { \
	struct timeval t0,t1; gettimeofday(&t0, 0); x; gettimeofday(&t1, 0); \
   	printf("%f,", timedifference_msec(t0, t1)); \
}

int main(int argc, char ** argv) {
	long long i,n = 10000000000;
#ifdef MODULO
	printf("== modulo version ==\n");
#endif
	if (argc > 2) {
		printf("Syntax: %s [iterations]\n", argv[0]);
		exit(1);	
	};
	if (argc == 2)
		n = strtoll(argv[1],NULL,10);

	assert(ap_timingsafe_strcmp("fa","fr",AP_HOSTILE_STR1 | AP_MIN1024) != 0);

	assert(ap_timingsafe_strcmp("f","fredandsoon",AP_HOSTILE_STR1) != 0);
	assert(ap_timingsafe_strcmp("fredandsoon","fr",AP_HOSTILE_STR2) != 0);
	assert(ap_timingsafe_strcmp("fred","fred",AP_HOSTILE_STR1) == 0);

	assert(ap_timingsafe_strcmp("ffre","fred",AP_HOSTILE_STR1) != 0);
	assert(ap_timingsafe_strcmp("ffre","fred",AP_HOSTILE_STR2) != 0);

	assert(ap_timingsafe_strcmp("ffree","fred",AP_HOSTILE_STR1) != 0);
	assert(ap_timingsafe_strcmp("ffree","fred",AP_HOSTILE_STR2) != 0);

	assert(ap_timingsafe_strcmp("ffreee","fred",AP_HOSTILE_STR1) != 0);
	assert(ap_timingsafe_strcmp("ffreee","fred",AP_HOSTILE_STR2) != 0);

	assert(ap_timingsafe_strcmp("fred","fred",0) == 0);
	assert(ap_timingsafe_strcmp("A","fred",0) != 0);
	assert(ap_timingsafe_strcmp("fred","frid",0) != 0);
	assert(ap_timingsafe_strcmp("fred","Fred",0) != 0);
	assert(ap_timingsafe_strcmp("freD","fred",0) != 0);
	assert(ap_timingsafe_strcmp("fred","f",0) != 0);

	assert(ap_timingsafe_strcmp("fredfredfredfredfredfredfredfred","fred",0) != 0);
	assert(ap_timingsafe_strcmp("fred","fredfredfredfredfredfredfredfred",0) != 0);
	assert(ap_timingsafe_strcmp("fredfredfredfredfredfredfredfred","fredfredfredfredfredfredfredfred",0) == 0);

        assert(ap_timingsafe_strcmp("fred","fRed",0) != 0);	
        assert(ap_timingsafe_strcmp("f","f",0) == 0);	
        assert(ap_timingsafe_strcmp("f","d",0) != 0);	
        assert(ap_timingsafe_strcmp("","",0) == 0);	
        assert(ap_timingsafe_strcmp("fred","fredfred",0) != 0);	
        assert(ap_timingsafe_strcmp("fredfred","fred",0) != 0);
        assert(ap_timingsafe_strcmp("fredfred","fred",0) != 0);
        assert(ap_timingsafe_strcmp("fredfred","fredfred",0) == 0);

	printf("\n---\n");
	for(int j = 0; j < 100; j++) {
		// slow to fastest. Delta in the order of 1E-5
#ifdef HOSTITLE
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fred",AP_HOSTILE_STR1) == 0)); // 2
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fredfre",AP_HOSTILE_STR1) != 0)); // 3
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fr",AP_HOSTILE_STR1) != 0)); // 4
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fredfred",AP_HOSTILE_STR1) != 0)); // 5
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fredfredfred",AP_HOSTILE_STR1) != 0)); // 1
#else
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fredfredfre","fred",0) != 0)); // 2
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fredfre",0) != 0)); // 3
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fred",0) == 0)); // 4
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fred","fredfred",0) != 0)); // 5
		TT(for(i =0; i < n; i++) assert(ap_timingsafe_strcmp("fredfredfred","fred",0) != 0)); // 1
#endif
		printf("0\n");
	};
	printf("\n---\n");
}