On Mon, Feb 10, 2014 at 06:36:18PM +0800, Tjerk Meesters wrote:
> I've given this problem some more thought and the following looked
> promising; it would be great to get your feedback on it.
I had considered this approach, and felt it was not worth suggesting to
you because it has serious drawbacks. Also, it appeared that the
consensus was not to try avoiding the length leaks, although maybe to
provide for the option of adding something to that extent in the future
by specifying which parameter is secret and which is user-provided.
(Specifying this is also needed for possible alternate implementations
making use of blinding, should we choose to switch to that in the future.)
> Basically, to remove the modulo and MAX(), I've used a combined buffer
> that's used for the comparison, in two ways:
>
> 1. PAD := known (padded with \0 based on given_len)
> 2. PAD := known CONCAT given
>
> The comparison is straightforward because we already know the buffer is at
> least given_len.
>
> Implementations of above can be found here:
> 1. https://github.com/datibbaw/php-src/compare/master...const-cmp
> 2. https://github.com/datibbaw/php-src/compare/master...const-cmp-2
>
> Bottom line is that this attempts to compromise memory against time
> stability.
Not only that. Other issues, in arbitrary order:
1. ecalloc(1, known_len + given_len); might leak known_len - moreover,
not only via the total time it takes on a specific occasion (which I
admit is not very leaky for lengths typical for secret strings), but
also via probing via different given_len values adjusted to trigger
ecalloc() to switch between different approaches (e.g., allocating from
different size buffers, or switching to mmap() - whatever thresholds of
this kind the underlying implementation has). This may be used to
figure out the length with byte granularity, and the timing leak for a
most suitable threshold - e.g. for one involving the switch to mmap(),
which is an extra syscall to make - may well be more significant than it
would have been for a straightforward strcmp() that was not even trying
to hide anything (strcmp() doesn't make syscalls!)
2. "memcpy(known_padded, known, known_len);" leaks known_len, albeit to
a smaller extent than strcmp() does (since relative measurements
comparing to a user-provided input can't be done).
3. We're making it more likely that sensitive data will end up in
coredumps, etc. - especially if "efree(known_padded);" does not wipe the
memory it's about to free. This is easy to mitigate by adding a
memset() just before freeing the memory, but even then we've made things
a bit worse, and given #1 and #2 we did so for no good reason.
I could help you fix things while still using variations of this
approach, but I think this approach is just not good enough even if we
do fix whatever is fixable with it. I recommend that you abandon it.
Now, I could try to write a function like this for you, that would try
to hide the length to some limited extent while being clearly not worse
than strcmp(). I'd probably go along the lines of your original code
that had modulo division, but replace the division with index wraparound
implemented with some "magic" bitwise ops, add/sub, and maybe fixed
count shifts (all of these being constant time). I've been writing this
sort of code before - implementing the equivalents of conditional
branching without actually branching (nor incurring any other variable
time operations) - in other contexts. I am just unsure this is what we
want. Well, maybe - with proper documentation. Cache timing leaks will
remain. And like others said, there's little use for hiding the length,
and needing to do so generally indicates that something else is wrong.
Alexander