Re: streql - Constant-time string comparison
Afaict, your solution works, but it is dependent on the 1024 string
table never changing.
The code fragment was written in Python. In Python, len() is a constant
time operation[1]. That being said, there was a problem with my code
which was described by Richard van den Berg earlier, so you shouldn't
use it if you're concerned about hiding the length of strings. However,
the usage of len() in upstream's code shouldn't be a problem as it is a
constant time operation.
[1] At least for lists; I couldn't find a reference for strings. Please
correct me if you can show otherwise.
https://wiki.python.org/moin/TimeComplexity
On 31/10/14 10:46, Leslie S Satenstein wrote:
> Once again, suppose I have a table 1024 strings, and I need to check if my string is one of them. If my string is not one of them, I report 0, or 1 for match. I can do that test in linear time. Suppose I need to run this test a few hundred times per run, here is an option.
>
> One way is to sort the 1024 string table, once per run. Then I can do a binary search and come out with a yes/no in 10 or fewer tests. That will work well. I also have other tricks to do that test in even less cpu and clock time.
>
> What is it that is the real requirement?
> Rileys code fragment does not show how he arrived at string length. That in itself requires a pass through each string to determine the number of characters in each.
> 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 6:43 PM
> Subject: Re: streql - Constant-time string comparison
>
> I gotta quit coding when I should be asleep.
>
> On Fri, Oct 31, 2014 at 12:38 AM, Joel Rees <joel.rees@gmail.com> wrote:
>> 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
>
> Correct that to:
> ** Use of those parts original with Joel Rees allowed specifically under
> ** the Apache License version 2.0:
> ** http://opensource.org/licenses/Apache-2.0 ,
> ** or the Academic Free License v. 2.1
> ** http://opensource.org/licenses/AFL-3.0 ,
> ** or the GPL v. 2.0, 3.0 or later:
> ** http://www.gnu.org/copyleft/gpl.html
> **
> ** Permission granted in advance
> ** for the Python Software Foundation to license or re-license
> ** any source code copyrights and/or patent rights held in such parts
> by Joel Rees
> ** as part of Python Software Foundation publications and distributions.
> **
> ** No claims or licensing assertions made concerning those parts not
> original with Joel Rees.
>
>> */
>>
>> #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: