Re: streql - Constant-time string comparison
On Sat, Nov 1, 2014 at 4:49 PM, Riley Baird
<BM-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch> wrote:
> On 31/10/14 09:43, Joel Rees wrote:
>> [...]
> This is a good way of doing the string comparison. However, it would
> seem that upstream isn't really interested in hiding the length of the
> strings, and doing so would only provide minimal security benefits.
They're kind of right, I'm discovering.
> Would you be willing to sponsor the upstream streql,
Not sure what you mean there.
> or do you think
> that this version should be packaged instead after being modified for
> Python?
No. I'm still playing with the concepts (Current state of things
below.) and realizing several things.
Probably, the best solution for a constant-time compare is to
pre-zero-fill the buffers and do binary compares (memcmp()) on the
entire buffers. That means that these routines are a bit superfluous
anyway.
My current results:
-------------------------------
/* 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 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 software distributions and
publications.
**
** 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 near constant time.
// If cmplength is less than min( xlen, ylen ), comparison is incomplete.
// Lengths should be signed to make conditionals more balanced.
// Maximum string length is greater than 2^30 for 32 bit ints.
// Impervious to embedded NUL characters.
static int equals_internal_constimebin(
const char *x, int xlen,
const char *y, int ylen,
int cmplength) {
int result = 0;
/* dbg */ gcount = 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; // much quicker than indexed load and counter decrement
** }
** While signed lengths 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);
}
#define MAX_PASSWORD_LENGTH 32
/* Fails silently on passwords longer than MAX_PASSWORD_LENGTH bytes.
// Note that using strlen() on the parameters will still induce some
timing leaks.
// DO NOT use this macro in real code.
*/
#define Mequals_internal_password( guess, key ) \
equals_internal_constimebin( \
guess, strlen( guess ), \
key, strlen( key ), MAX_PASSWORD_LENGTH )
#define DEFAULT_PASSPHRASE_LENGTH 64
/* Constant to default length, then dependent on length of guess.
// See above on use of strlen().
*/
static int equals_internal_passphrase( const char *guess, const char *key ) {
int guesslen = strlen( guess );
int keylen = strlen( key );
int complen = ( guesslen > DEFAULT_PASSPHRASE_LENGTH ) ? guesslen :
DEFAULT_PASSPHRASE_LENGTH;
return equals_internal_constimebin( guess, guesslen, key, keylen, complen );
}
// The core function: test two regions of memory for bytewise equality
with near constant time.
// If cmplength is less than length of x or y, comparison is incomplete.
// Lengths should be signed to make conditionals more balanced.
// Maximum string length is 2^31 for 32 bit ints.
// Sensitivity to NULs allows use without strlen().
static int equals_internal_constime(
const char *x,
const char *y,
int cmplength) {
int result = 0;
int xstopped = 0;
int ystopped = 0;
/* dbg */ gcount = 0;
while ( --cmplength >= 0 ) {
char xtemp = xstopped ? 0 : *x++;
char ytemp = ystopped ? 0 : *y++;
/* dbg */ ++gcount;
result |= xtemp ^ ytemp;
if ( xtemp == '\0' ) xstopped = cmplength;
if ( ytemp == '\0' ) ystopped = cmplength;
/* dbg printf( "%c:%c =>%d@%d (stopped x:%d y:%d)\n", xtemp, ytemp,
result, gcount, xstopped, ystopped ); */
}
return (xstopped == ystopped) && (result == 0);
}
/* allow quick, simple tests from the command line
*/
int main( int argc, char * argv[] ) {
char * left, * right;
int max = MAX_PASSWORD_LENGTH;
int result = 0;
if ( argc > 2 ) {
left = argv[ 1 ];
right = argv[ 2 ];
if ( argc > 3 ) max = strtol( argv[ 3 ], NULL, 0 );
result = equals_internal_constimebin( left, strlen( left ),
right, strlen( right ), max );
printf( "raw result: %d, strcmp: %d, count: %d\n", result,
strcmp( left, right ), gcount );
if ( result != ( strcmp( left, right ) == 0 ) ) {
fputs( "*** failed ***\n", stdout );
}
result = equals_internal_constime( left, right, max );
printf( "raw result, no strlen: %d, strcmp: %d, count: %d\n",
result, strcmp( left, right ), gcount );
if ( result != ( strcmp( left, right ) == 0 ) ) {
fputs( "*** failed ***\n", stdout );
}
result = equals_internal_passphrase( left, right );
printf( "cooked 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;
}
-------------------------------
You can see two things here. One is that, from C, you end up having to
do a few calls to strlen() anyway if you depend on the lengths, which
undermines your efforts.
If Python has counted strings instead of C/Null-terminated strings,
that may mitigate things and make the approach more reasonable.
But even eliminating the need for a call to strlen() by testing the
end of the strings as you compare (new version above), generalizing
means you need to know the maximum lengths. So you end up just
preferring, as I say, to allocate a pair of same-length buffers,
pre-zero-fill them, and do a binary compare on the entire buffers
after you have stored the login attempt string and the actual key in
the buffers.
So these functions are fun to play with, but not really relevant.
Sample test strings:
-------------------------------
me@machine:~/work/primer/C$ ./constimecomp "This is a test" "This is a test " 5
raw result: 0, strcmp: -1, count: 5
raw result, no strlen: 1, strcmp: -1, count: 5
*** failed ***
cooked result: 0, strcmp: -1, count: 64
me@machine:~/work/primer/C$ ./constimecomp "This is a test" "This is a tes " 5
raw result: 1, strcmp: 1, count: 5
*** failed ***
raw result, no strlen: 1, strcmp: 1, count: 5
*** failed ***
cooked result: 0, strcmp: 1, count: 64
me@machine:~/work/primer/C$ ./constimecomp "This is a test" "This is a test "
raw result: 0, strcmp: -1, count: 32
raw result, no strlen: 0, strcmp: -1, count: 32
cooked result: 0, strcmp: -1, count: 64
me@machine:~/work/primer/C$ ./constimecomp "This is a test of the
emergency broadcast system braxahalia raspberries, ha ha." "This is a
test of the emergency broadcast system braxahalia raspberries, ha ha."
raw result: 1, strcmp: 0, count: 32
raw result, no strlen: 1, strcmp: 0, count: 32
cooked result: 1, strcmp: 0, count: 79
me@machine:~/work/primer/C$ ./constimecomp "This is a test of the
emergency broadcast system braxahalia raspberries, ha ha." "This is a
test of the emergency broadcast system braxahalia raspberries, ha ha "
raw result: 1, strcmp: 1, count: 32
*** failed ***
raw result, no strlen: 1, strcmp: 1, count: 32
*** failed ***
cooked result: 0, strcmp: 1, count: 79
-------------------------------
--
Joel Rees
Be careful when you see conspiracy.
Look first in your own heart,
and ask yourself if you are not your own worst enemy.
Arm yourself with knowledge of yourself.
Reply to: