Re: streql - Constant-time string comparison
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-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch>
> To: debian-security@lists.debian.org; Leslie S Satenstein <lsatenstein@yahoo.com>; Joel Rees <joel.rees@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.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
>>
>>
>
>
> --
> To UNSUBSCRIBE, email to debian-security-REQUEST@lists.debian.org
> with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
> Archive: [🔎] 54549D14.1090006@bitmessage.ch">https://lists.debian.org/[🔎] 54549D14.1090006@bitmessage.ch
>
>
>
>
Reply to: