You might want to see this article: https://en.wikipedia.org/wiki/Timing_attack
On 02/11/14 02:45, Leslie S Satenstein wrote: > Please explain the constant time requirement. As I see it, any software > (multi-tasking or other) that I wrote has a requirement to not exceed a > max_time. > > What is the application requirement that requires a waste of cpu cycles to > yield constant time? It is not for security, or multitasking, so what is it? > Regards > Leslie > Mr. Leslie Satenstein > Montréal Québec, Canada > > > > From: Riley Baird <bm-2cvqnduybau5do2dfjtrn7zbaj246s4...@bitmessage.ch> > To: debian-security@lists.debian.org; Leslie S Satenstein > <lsatenst...@yahoo.com>; Joel Rees <joel.r...@gmail.com> > Sent: Saturday, November 1, 2014 4:43 AM > Subject: 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.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 > > > > -- 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/5455ae7a.9020...@bitmessage.ch
