3 ms·
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
by baby 9y ago
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.
- kbeckmann 9y agoI 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/347189c50c053cf13ce1310818c2913f4904c1eb https://github.com/LoupVaillant/Monocypher/commit/347189c50c...
- baby 9y ago`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/monocypher.h#L58 https://github.com/LoupVaillant/Monocypher/blob/master/src/m...
- loup-vaillant 9y agoYour 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.
- deleted 9y ago[deleted]
- jwilk 9y agoCompile 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'
- fefe23 9y agoIf 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.
- baby 9y agoI 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/KeccakP-1600/Reference/KeccakP-1600-reference.c#L316 https://github.com/gvanas/KeccakCodePackage/blob/master/SnP/... )
- moefh 9y agoThe 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; or 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).
- baby 9y agofor 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; }
- masklinn 9y ago6.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.
- baby 9y agois it doing a sign extension though? If it promotes without adding a bunch of 1s it should be fine.
- masklinn 9y agoIt'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")
- baby 9y agoI 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-c/ https://www.cryptologie.net/article/418/integer-promotion-in...
- pm215 9y agoThe 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.)
- pbsd 9y agoThere'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!
- baby 9y agoright, 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.
- pbsd 9y agou8 gets promoted to signed int before the shift. That he only used unsigned types is irrelevant.