[whispersystems] libsignal-protocol-c: integer truncation in device consistency comparison

[Matthew Fernandez]

Hello all,

Perhaps this belongs on the Github issue tracker, but I wasn't sure this was a bug and the issue template [0] suggests
anything without a clear reproducer doesn't belong there.

The function device_consistency_signature_list_sort_comparator currently appears as follows [1]:

int device_consistency_signature_list_sort_comparator(const void *a, const void *b)
{
int result;
const device_consistency_signature *sig1 = *((const device_consistency_signature **)a);
const device_consistency_signature *sig2 = *((const device_consistency_signature **)b);
signal_buffer *buf1 = device_consistency_signature_get_vrf_output(sig1);
signal_buffer *buf2 = device_consistency_signature_get_vrf_output(sig2);
size_t len1 = signal_buffer_len(buf1);
size_t len2 = signal_buffer_len(buf2);

if(len1 == len2) {
result = memcmp(signal_buffer_data(buf1), signal_buffer_data(buf2), len1);
}
else {
result = (int)(len1 - len2);
}

return result;
}

It seems like casting the length subtraction to an int can produce an undesirable result on platforms where sizeof(int)
!= sizeof(size_t), for example x86_64. I think you need a fairly large buffer (e.g. 1ul << 32) to trigger anything
interesting, so I'm not sure whether this is a practical scenario. The logic of this comparator doesn't match the
libsignal-protocol-java equivalent [2], so I'm not even sure whether the "correctness" of the sort order here matters as
long as it's internally consistent. Any thoughts?

Thanks,
Matt

[0]: https://github.com/WhisperSystems/libsignal-protocol-c/blob/master/ISSUE_TEMPLATE.md
[1]:
https://github.com/WhisperSystems/libsignal-protocol-c/blob/f0e97126af67248b5b492d6b53b391e2315e1265/src/device_consistency.c#L639-L657
[2]:
https://github.com/WhisperSystems/libsignal-protocol-java/blob/84084697760e6ab7f7f86014b7cbdbaa73b5f2dc/java/src/main/java/org/whispersystems/libsignal/util/ByteArrayComparator.java#L5-L16

[Derek Konigsberg]

In theory, this is a valid concern. If you submit a pull request to fix
that specific result case, I will accept it.

In practice, this issue won't happen. The actual sizes of the VRF output
buffers are constant, so the lengths won't ever mismatch.

Looking at an actual implementation [0] of the C memcmp() function, it
returns the difference of the first mismatched byte. So, unless I'm
reading things wrong, this code actually is equivalent to the Java
library's ByteArrayComparator.


[0]
https://github.com/freebsd/freebsd/blob/f1cb0bb9b17c62ff45420ac865743e9d049b531a/sys/libkern/memcmp.c#L41-L52

-Derek

Post by Matthew Fernandez
Hello all,
Perhaps this belongs on the Github issue tracker, but I wasn't sure
this was a bug and the issue template [0] suggests anything without a
clear reproducer doesn't belong there.
The function device_consistency_signature_list_sort_comparator
int device_consistency_signature_list_sort_comparator(const void *a, const void *b)
{
int result;
const device_consistency_signature *sig1 = *((const
device_consistency_signature **)a);
const device_consistency_signature *sig2 = *((const
device_consistency_signature **)b);
signal_buffer *buf1 =
device_consistency_signature_get_vrf_output(sig1);
signal_buffer *buf2 =
device_consistency_signature_get_vrf_output(sig2);
size_t len1 = signal_buffer_len(buf1);
size_t len2 = signal_buffer_len(buf2);
if(len1 == len2) {
result = memcmp(signal_buffer_data(buf1),
signal_buffer_data(buf2), len1);
}
else {
result = (int)(len1 - len2);
}
return result;
}
It seems like casting the length subtraction to an int can produce an
undesirable result on platforms where sizeof(int) != sizeof(size_t),
for example x86_64. I think you need a fairly large buffer (e.g. 1ul
<< 32) to trigger anything interesting, so I'm not sure whether this
is a practical scenario. The logic of this comparator doesn't match
the libsignal-protocol-java equivalent [2], so I'm not even sure
whether the "correctness" of the sort order here matters as long as
it's internally consistent. Any thoughts?
Thanks,
Matt
https://github.com/WhisperSystems/libsignal-protocol-c/blob/master/ISSUE_TEMPLATE.md
https://github.com/WhisperSystems/libsignal-protocol-c/blob/f0e97126af67248b5b492d6b53b391e2315e1265/src/device_consistency.c#L639-L657
https://github.com/WhisperSystems/libsignal-protocol-java/blob/84084697760e6ab7f7f86014b7cbdbaa73b5f2dc/java/src/main/java/org/whispersystems/libsignal/util/ByteArrayComparator.java#L5-L16

[Matthew Fernandez]

Thanks for your reply, Derek. I've submitted a PR for this just now [0]. What I was referring to with the difference in
logic was that the Java comparator does a bytewise comparison even if the lengths aren't equal, whereas the C comparator
does not. However, as you've said, this case never happens here.

[0]: https://github.com/WhisperSystems/libsignal-protocol-c/pull/83

In theory, this is a valid concern. If you submit a pull request to fix that specific result case, I will accept it.
In practice, this issue won't happen. The actual sizes of the VRF output buffers are constant, so the lengths won't ever
mismatch.
Looking at an actual implementation [0] of the C memcmp() function, it returns the difference of the first mismatched
byte. So, unless I'm reading things wrong, this code actually is equivalent to the Java library's ByteArrayComparator.
[0] https://github.com/freebsd/freebsd/blob/f1cb0bb9b17c62ff45420ac865743e9d049b531a/sys/libkern/memcmp.c#L41-L52
-Derek

Post by Matthew Fernandez
Hello all,
Perhaps this belongs on the Github issue tracker, but I wasn't sure this was a bug and the issue template [0] suggests
anything without a clear reproducer doesn't belong there.
int device_consistency_signature_list_sort_comparator(const void *a, const void *b)
{
int result;
const device_consistency_signature *sig1 = *((const device_consistency_signature **)a);
const device_consistency_signature *sig2 = *((const device_consistency_signature **)b);
signal_buffer *buf1 = device_consistency_signature_get_vrf_output(sig1);
signal_buffer *buf2 = device_consistency_signature_get_vrf_output(sig2);
size_t len1 = signal_buffer_len(buf1);
size_t len2 = signal_buffer_len(buf2);
if(len1 == len2) {
result = memcmp(signal_buffer_data(buf1), signal_buffer_data(buf2), len1);
}
else {
result = (int)(len1 - len2);
}
return result;
}
It seems like casting the length subtraction to an int can produce an undesirable result on platforms where
sizeof(int) != sizeof(size_t), for example x86_64. I think you need a fairly large buffer (e.g. 1ul << 32) to trigger
anything interesting, so I'm not sure whether this is a practical scenario. The logic of this comparator doesn't match
the libsignal-protocol-java equivalent [2], so I'm not even sure whether the "correctness" of the sort order here
matters as long as it's internally consistent. Any thoughts?
Thanks,
Matt
[0]: https://github.com/WhisperSystems/libsignal-protocol-c/blob/master/ISSUE_TEMPLATE.md
https://github.com/WhisperSystems/libsignal-protocol-c/blob/f0e97126af67248b5b492d6b53b391e2315e1265/src/device_consistency.c#L639-L657
https://github.com/WhisperSystems/libsignal-protocol-java/blob/84084697760e6ab7f7f86014b7cbdbaa73b5f2dc/java/src/main/java/org/whispersystems/libsignal/util/ByteArrayComparator.java#L5-L16