Re: streql - Constant-time string comparison
You can't change any of these variables if streql is running on a remote
server. Streql is especially valuable for, say, checking hashes of
passwords.
On 03/11/14 02:47, Leslie S Satenstein wrote:
> You should take the course at Software Security | CourseraTiming attacks are done with a special setup consisting of numerable measuring instruments, strict control over what is running alongside and other techniques, such as single threading execution code. But you are using python. One can simply modify the interpreter (VM machine), to walk through the code.
>
> Regards
> Leslie
> Mr. Leslie Satenstein
> Montréal Québec, Canada
>
>
>
> From: Riley Baird <BM-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch>
> To: Leslie S Satenstein <lsatenstein@yahoo.com>
> Cc: "debian-security@lists.debian.org" <debian-security@lists.debian.org>
> Sent: Sunday, November 2, 2014 12:09 AM
> Subject: 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
>
>
>>
>>
>>
>>
>
>
> --
> To UNSUBSCRIBE, email to debian-security-REQUEST@lists.debian.org
> with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
> Archive: [🔎] 5455AE7A.9020800@bitmessage.ch">https://lists.debian.org/[🔎] 5455AE7A.9020800@bitmessage.ch
>
>
>
>
Reply to: