integer promotion in C posted August 2017

Loup Vaillant wrote a good blog post about his new crypto library Monocypher.

In spite of the obvious controversy of launching a new crypto library, I really like it. Note that this is not me officially endorsing the library, I just think it's cool and I would only consider using it after it had matured a bit more.

The whole thing is one ~1500LOC file and is pretty clear to read. It only implements a few crypto functions.

The blog post mentions a few bugs that were found in his library (and I appreciate how open he is about it). Here's an interesting one:

Bug 5: signed integer overflow
This one was sneaky. I wouldn't have caught it without UBSan.
I was shifting a uint8_t, 24 bits to the left. I failed to realise that integer promotion means this unsigned byte would be converted to a signed integer, and overflow if the byte exceeded 127. (Also, on crazy platforms where integers are smaller than 32 bits, this would never have worked.) An explicit conversion to uint32_t did the trick.
At this point, I was running the various sanitisers just to increase confidence. Since I used Valgrind already, I didn't expect to actually catch a bug. Good thing I did it anyway.
Lesson learned: Never try anything serious in C or C++ without sanitisers. They're not just for theatrics, they catch real bugs.

This is the problem patched.

Simplified, the bad code really looks like this:

uint32_t = uint8_t << 8 * i;

And all the theory behind the problem can be dismissed, if he had written his code with precautions. When I see something like this, the first thing I think about is that it should probably be written like this:

uint32_t = (uint32_t)uint8_t << 8 * i;

This would avoid any weird C problems as a casting (especially to a bigger type) usually goes fine.

OK but what was the problem with the above code?

Well, in C some operations will usually promote the type to something bigger. See the C standard:

shift-expression << additive-expression
The integer promotions are performed on each of the operands

What is an integer promotion? See the C standard:

If an int can represent all values of the original type, the value is converted to an int;
otherwise, it is converted to an unsigned int.
These are called the integer promotions

So looking back at our bad snippet:

uint32_t = uint8_t << 8 * i;

1. the maximum value of uint8_t is 255, which can largely be hold in a signed int of 16-bit or 32-bit (depends on the architecture). So 01 is promoted to 00 00 00 01 if a signed int is 32-bit (which it probably is). (In the case were we would have been dealing with a uint32-t, there would have been no problems as "big" values that cannot be represented in a signed int of 32-bit would have been promoted to a unsigned int instead of a signed int.)
2. the bits are shifted on the left. For example of 8 places 00 00 01 00.
3. the result gets casted to uint32_t. We still get 00 00 01 00.

This doesn't look like an issue, and it probably isn't most of the time. Now imagine if in 1. our value was 80 (which is 1000 0000 in bits).

Imagine now that in 2. we shift it of 24 bits on the left, that will give us 80 00 00 00 which is an all zero bitstring except for the most significant bit (MSB). In an int type the MSB is the signing bit. I believe at this point, the value will be automatically sign extended to the size of the register, so in your 64-bit machine it will be saved as ff ff ff ff 80 00 00 00.

Now in 3. The result now get casted to a uint32_t. Which doesn't do anything but change the value of the pointer. But we now have a wrong result! What we wanted here was 00 00 00 00 80 00 00 00. If you're not convinced, you can run the following script on your computer:

#include <stdio.h>
#include <stdint.h>

int main(){

uint8_t start = -1;
printf("%x\n", start); // prints 0xff
uint64_t result = start << 24;
printf("%llx\n", result); // should print 00000000ff000000, but will print ffffffffff000000
result = (uint64_t)start << 24;
printf("%llx\n", result); // prints 00000000ff000000
return 0;
}

Looking at the binary in Hopper we can see this:

And we notice the movsxd instruction which is "move doubleword to quadword with sign-extension".
It moves the result of the shift left (shl) into a register, making sure that its result is the same for an int64_t which is the maximum value your register can hold.