Hacker News Reader

Comment by baby | Hacker News Reader

First let me say that I've followed your work a bit and I'm really impressed with the library. I'm currently planning on rolling my own crypto as well and your library is on my list of the things to look at.

One question:

> 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.

This sounds weird to me, how is a shift (which only apply itself on the bit value, not the number value) triggering a sign extension? I don't think you're talking about integer promotion here unless you had a uint16_t = uint8_t << 24 or something like this.

View on HN

The problem happens if you do uint64_t = uint8_t << 24, for example. The shift will promote the uint8_t to int (not unsigned int), and then the conversion to uint64_t will sign extend, so

   uint8_t u8 = 255;
   uint64_t u64 = u8 << 24;
   printf("%016llx\n", (long long) u64);

prints "ffffffffff000000". If you instead do

   uint64_t u64 = (uint64_t) u8 << 24;

   uint64_t u64 = (uint32_t) u8 << 24;

It prints "00000000ff000000" as most people expect. (I think the second example with (uint32_t) will only work if "int" is at most 32 bits, but I might be wrong).

for anyone who wants to run that themselves:

  #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;
  }

If you say "foo + 3", and foo is a uint8_t, then 3 is technically an int, so the addition will do an integer promotion.

If you say "foo + bar" and both are uint8_t, then both will be promoted to integer. That's how C works. Assigning the result to another uint8_t will truncate it.

Please do not write your own crypto library until you really understand how C works, especially including this kind of detail.

I understand the issue, but not the explanation.

Your example is different, this is because you're doing an addition. I can see how this could be a problem if you want to do a rotation (a << 4) + (a >> 60) and hence why you should use a ^ instead of a + here (example: https://github.com/gvanas/KeccakCodePackage/blob/master/SnP/... )

6.5.7.3 of the C99 standard specifies that each operand of a bit shift first undergoes integer promotion.

yesh! Alright I see the issue. This `int` then gets sign extended to a 64-bit register.

There's no sign-extension involved. Let's say the input is (uint8_t)128. This gets promoted to (int)128, which is then shifted 24 bits to the left. If the input was (int8_t)128, it would get sign-extended into (int)-128, but that is not the case here.

With 32-bit ints, this operation will result in 0x80000000, shifting a bit into the sign bit, which constitutes an overflow (and undefined behavior). Think about it in terms of multiplication: you're multiplying a positive integer by 2^24, and it turns out negative!

right, but he only used unsigned types. I think there is another problem here:

u64 = u8 << 24

Here the integer promotion might transform u8 into a 16-bit or 32-bit int (depending on the arch). Which will then be converted to a u64 AFTER the shift. Which might have you lose half or more of the bits.

His code is not that though, it's

u32 = u8 << 24

which should work only if ints are 32-bit on the system you compile on.

u8 gets promoted to signed int before the shift. That he only used unsigned types is irrelevant.

> That he only used unsigned types is irrelevant

If he had used a signed type, it would have got sign extended and the result would have been different.

We can agree on that. But now I am completely lost as to what your original point was...

I admit I am as well :D

6.5.7 Bitwise shift operators

> Each of the operands shall have integer type.

> The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand.

6.3.1.1 § 2

> If an int can represent all values of the original type (as restricted by the width, for a bit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions.

So if you shift a uint8_t, it is first converted to a (machine-dependent) signed int, then shifted, then converted to whatever the expression type ends up being.

is it doing a sign extension though? If it promotes without adding a bunch of 1s it should be fine.

It's probably the latter part (conversion to "whatever the expression's type ends up being) doing the sign-extension, see moefh's sibling comment with a uint64_t final destination, the int -> uint64_t is sign-extending.

I should have quoted the proper part I was replying to ("I don't think you're talking about integer promotion here")

I just checked that myself, it is not the casting to uint64_t since the sign-extension happens even before that. The problem is that the result from the shift is stored in a register, which is probably 64-bit on your machine, and to do that it is sign extended from a signed int to a signed 64-bit value. Wrote more about that here: https://www.cryptologie.net/article/418/integer-promotion-in...

The size of the cpu registers don't matter here. What matters is that 'int' is a bigger type than uint8_t and smaller than uint64_t: the resulting unexpected behaviour is mandated by the C standard regardless of the register size of the cpu (for instance both 32-bit i386 and 64-bit x86_64 will behave the same, because both typically have 32 bit 'int').

More generally, reasoning about this kind of thing by thinking about the CPU leads you down the wrong path -- modern C as implemented by compilers today is an implementation of a standardized language, and they behave as that standard says, which is not always as you might expect from the hardware behaviour. (Simple example: left shifting of negative numbers does a simple straightforward thing on practically all hardware, but the C spec says it's UB and if you write code that assumes the h/w behaviour you'll get bitten.)

Even if the code would still be bad for 32-bit machines, I'm not sure they would suffer from the bug (if they had 32-bit signed int as well).

1. Your uint8_t would get promoted to a 32-bit int

2. Your int would get shifted, getting a 1 in the signing bit

3. The result would get stored in a uint32_t when being casted

Now I don't know how uint64_t works on a 32-bit machine, I'd have to compile the C code with -m32 to see.

EDIT: just tested and you're right, it's still a problem on 32-bit machines.

I believe this[1] is the patch that fixes this bug. I tried to reproduce the behavior but couldn't succeed. Maybe I was doing something wrong. Would really appreciate it if someone here could show a test case where this matters.

[1] https://github.com/LoupVaillant/Monocypher/commit/347189c50c...

`ctx->c` is a u32[1] and msg is u8. So yeah there is integer promotion here.

[1]: https://github.com/LoupVaillant/Monocypher/blob/master/src/m...

Your failure to reproduce the behaviour is normal: on the compilers I have tested, this doesn't affect the generated binary.

To see the difference, you need to first modify the makefile to use UBSan instead of just GCC (just comment the active CC line, and uncomment the right one). You may want to tone down the optimisations for faster compilation as well. Then you can run `make clean` and `./test.sh`. You should have a warning on commits prior to this patch.

Compile this program with -fsanitize=undefined:

  #include <stddef.h>
  #include <inttypes.h>
  
  int main(int argc, char **argv)
  {
  	uint8_t msg[] = { 255 };
  	size_t i = 0;
  	size_t c_index = 255;
  	return msg[i] << ((c_index % 4) * 8);
  }

You get:

  runtime error: left shift of 255 by 24 places cannot be represented in type 'int'

Reply on news.ycombinator.com