Bug#765893: streql - Constant-time string comparison
On 29/10/14 17:00, Joel Rees wrote:
> 2014/10/29 4:59 "Riley Baird" <
> BM-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch>:
>>
>> On 29/10/14 00:20, Joel Rees wrote:
>>> On Tue, Oct 28, 2014 at 12:08 PM, Riley Baird
>>> <BM-2cVqnDuYbAU5do2DfJTrN7ZbAJ246S4Xix@bitmessage.ch> wrote:
>>>> Dear debian-security,
>>>>
>>>> I am looking for a sponsor for my package "streql".
>>>>
>>>> In Python, the code for testing the equality of strings is susceptible
>>>> to a "timing side channel attack". The package 'streql' provides a
>>>> function for comparing strings of equal length in equal time,
> regardless
>>>> of the content of the strings.
>>>>
>>>> * Package name : streql
>>>> Version : 3.0.2-1
>>>> Upstream Author : Peter Scott <peter@cueup.com>
>>>> * URL :https://github.com/PeterScott/streql
>>>> * License : Apache 2.0
>>>> Section : python
>>>>
>>>> It builds those binary packages:
>>>>
>>>> python-streql - Constant-time string comparison (Python 2)
>>>> python3-streql - Constant-time string comparison (Python 3)
>>>> pypy-streql - Constant-time string comparison (PyPy)
>>>>
>>>> To access further information about this package, please visit the
> following
>>>> URL:
>>>>
>>>> http://mentors.debian.net/package/streql
>>>>
>>>> Alternatively, one can download the package with dget using this
> command:
>>>>
>>>> dget -x
>>>> http://mentors.debian.net/debian/pool/main/s/streql/streql_3.0.2-1.dsc
>>>>
>>>> Changes since last upload:
>>>>
>>>> * Initial release (Closes: #764443)
>>>>
>>>> Regards,
>>>> Riley Baird
>>>
>>> Let me try this suggestion again:
>>>
>>> -----------------------
>>> // The core function: test two regions of memory for bytewise equality.
>>> static int equals_internal(const char *x, unsigned int xlen, const
>>> char *y, unsigned int ylen) {
>>>
>>> int minlen = ( xlen > ylen ) ? ylen : xlen;
>>> int i, result = 0;
>>>
>>> for (i = 0; i < minlen; i++) result |= x[i] ^ y[i];
>>>
>>> return ( xlen == ylen ) && ( result == 0 );
>>> -----------------------
>>>
>>> I haven't tested it, but I think the corner case I'm thinking about is
>>> fairly clear.
>>
>> 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?
>>
>
> Yeah.
>
> It still leaks length information, but not as obviously.
>
> You could add a busy loop to push the leak to the other side of the sweep.
>
> You could even play games with the busy loop to randomly extend it beyond
> the place it would naturally terminate, just to reduce the incentive to
> look. (Making sure your pseudo-random selection code is not data dependent,
> of course.)
>
> You could change the semantics of the API to allow making the execution
> time depend on the length of attacker's guess.
>
> Of course, it's not really hard to get true constant compare times, and
> that's what I think I'd aim at.
I've taken your code, and I've also done the required Python
translation. You can see the pull request here:
https://github.com/PeterScott/streql/pull/3
I'm reluctant to make the changes that you mentioned above, because from
what I can tell, the objective of streql is to ensure that for a given
length of string, the time taken to determine equality is constant.
Of course, the changes that you mentioned could be applied only to
strings where the length is unequal, but if the same input is used
twice, and the time taken for each operation is different, then that
would alert an attacker that the strings are of different lengths, which
takes away the whole point of the exercise.
Reply to: