Running time could depends on guess length, because it is not secure parameter. Problem can appear in the produced machine code after compiler optimisations. // running time depends of length of guess bool check_password(const char *guess, const char *actual) {     char result = 0;     const char *g = guess, *a = actual;     while(*g) {         result |= *g++ ^ *a;         a += *a ? 1 : 0;    //stop skipping at '\0'     }     result |= *g ^ *a;        // compare last byte in case len(a)>0     return !result; } On 30.10.2014 9:38, Joel Rees wrote: ```On Thu, Oct 30, 2014 at 4:58 AM, Riley Baird wrote: ``` ```On 29/10/14 19:55, Richard van den Berg wrote: ``` ```On 28-10-14 20:59 , Riley Baird wrote: ``` ```As far as I can tell, your code ensures that even if the strings are of different length, an equality calculation should be performed anyway, however returning 0, on the grounds that this would make it more difficult for an attacker to know that the two strings entered were of different lengths. Is this right? ``` ```Pardon my ignorance, but how much more difficult does it actually become to determine the two inputs are of different length? In the original the function returns right away if xlen != ylen. If the attacker can control one of the inputs (say x), the change proposed by Joel will cause the time of the compare to increment when xlen in increased until xlen == ylen. If this can be observed with enough precision the same objective can be achieved. ``` ```Good point. Perhaps this could be fixed by, origleny=len(y) while len(x) >= len(y): y += '0' result = i = 0 for i in xrange(len(x)): result |= ord(x[i]) ^ ord(y[i]) return result == 0 and len(y) == origleny This way, the time taken to complete the function will increase even after xlen >= ylen However, with this I'm concerned that the 'while' loop will take up too much time, thus still allowing an attacker to see when the string lengths become equal. Is there a quicker way to append zeros to a string such that it is equal in length to the other string? ``` ```Well, allocation of a string would tend to make the run time somewhat arbitrary, but whether it would mask the length or not is kind of hard to predict. Considering that the attack uses statistics, it's not hard to look for double peaks. I had a sort of similar idea, using a pair of local buffers, cycling the string through the buffers, and got workable code. But I realized I was just working too hard. A one byte buffer is plenty, and simplifies the loop. Seriously simplifies the loop. (I think. Still haven't really tested it or looked for corner cases.) I'm going to spend some time testing the following today and tomorrow: ----------------------------- // 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. static int equals_internal_constime( const char *x, unsigned int xlen, const char *y, unsigned int ylen, int cmplength) { int result = 0; while ( --cmplength >= 0 ) { char xtemp = 0; char ytemp = 0; if ( --xlen >= 0 ) xtemp = *x++; if ( --ylen >= 0 ) ytemp = *y++; result |= xtemp ^ ytemp; } return (xlen == ylen) && (result == 0); } ----------------------------- Picking the minimum length for cmplength when you call it would be the same as I posted before. Picking the maximum length would bias the execution time to the longer of the pair. Either way, sequencing through lengths of guesses would (using statistical methods) reveal a point where the time goes from constant to variable, as Richard notes above. If you can set an absolute max cmplength, you can always call it with the absolute max and get strictly constant time compares. (Or maybe use a manifest constant for cmplength.) For instance, for an API dedicated to passwords, if you know that all passwords are 31 bytes or less, you can pass 31 for cmplength on the call. But when the same API could be used for passwords or 2048 bit keys, you'd need to pass 256 for cmplength, which might be too long a wait for some things. That's why I suggested the possibility of needing to change the API. Another possibility is to use the greater of xlen, ylen, and cmplength in this function, which would avoid the problem of incomplete compares I put in the comments, and would allow one to set a length, beyond which we would not care if the length leaked. (20 or 32 might be reasonable.) This could be done without changing the API from the Python side. A third possibility might be to offer an API where we call the x parameter "guess" and the y parameter "actual_key", and always set the cmplength parameter to the guess length. That way, the time would always be dependent on the attacker's guess (assuming the caller function treated the parameters correctly). Completely separate topic, but with just a little more effort and care in the conditional paths, that could even be made an ordered compare, by noting the difference of the first pair of bytes that differ. ```