What's bad about shifting a 32-bit variable 32 bits?

Question

I recently picked up a copy of Applied Cryptography by Bruce Schneier and it's been a good read. I now understand how several algorithms outlined in the book work, and I'd like to start implementing a few of them in C.

One thing that many of the algorithms have in common is dividing an x-bit key, into several smaller y-bit keys. For example, Blowfish's key, X, is 64-bits, but you are required to break it up into two 32-bit halves; Xl and Xr.

This is where I'm getting stuck. I'm fairly decent with C, but I'm not the strongest when it comes to bitwise operators and the like.

After some help on IRC, I managed to come up with these two macros:

#define splitup(a, b, c) {b = a >> 32; c = a & 0xffffffff; }
#define combine(a, b, c) {a = (c << 32) | a;}

Where a is 64 bits and b and c are 32 bits. However, the compiler warns me about the fact that I'm shifting a 32 bit variable by 32 bits.

My questions are these:

• What's bad about shifting a 32-bit variable 32 bits? I'm guessing it's undefined, but these macros do seem to be working.
• Also, would you suggest I go about this another way?

As I said, I'm fairly familiar with C, but bitwise operators and the like still give me a headache.

EDIT

I figured out that my combine macro wasn't actually combining two 32-bit variables, but simply ORing 0 by a, and getting a as a result.
So, on top of my previous questions, I still don't have a method of combining the two 32-bit variables to get a 64-bit one; a suggestion on how to do it would be appreciated.

Answer 1

Yes, it is undefined behaviour.

ISO/IEC 9899:1999 6.5.7 Bitwise shift operators ¶3

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

^{C11 aka ISO/IEC 9899:2011 says the same.}

You should first cast b to the target integer type. Another point is that you should put parentheses around the macro parameters to avoid surprises by operator precedences. Additionally, the comma operator is very useful here, allowing you to avoid the braces, so that the macro can be used as a normal command, closed with a semicolon.

#define splitup(a,b,c) ( (b) = (a) >> 32, (c) = (a) & 0xffffffff )
#define combine(a,b,c) ( (a) = ((unsigned long long)(b) << 32) | (c) )

Additional casts may be necessary for `splitup to silence warnings about precision loss by over-paranoid compilers.

#define splitup(a,b,c) ( (b) = (unsigned long)((a) >> 32), (c) = (unsigned long)((a) & 0xffffffff) )

And please don't even think about using your self-written encryption for production code.

Answer 2

Shifting a 32-bit value by 32 bits or more is undefined in C and C++. One of the reasons it was left undefined is that on some hardware platforms the 32-bit shift instruction only takes into account 5 lowest bits of the supplied shift count. This means that whatever shift count you pass, it will be interpreted modulo 32. Attempting to shift by 32 on such platform will actually shift by 0, i.e. not shift at all.

The language authors did not want to burden the compilers written for such platform with the task of analyzing the shift count before doing the shift. Instead, the language specification says that the behavior is undefined. This means that if you want to get a 0 value from a 32-bit shift by 32 (or more), it is up to you to recognize the situation and process it accordingly.

Answer 3

what's bad about shifting a 32-bit variable 32 bits?

Its better to assign 0 to n-bit integer than to shift it by n-bits.

Example:

 0 0 1 0 1 ----- 5 bit Integer  
 0 1 0 1 0 ----- 1st shift  
 1 0 1 0 0 ----- 2nd shift  
 0 1 0 0 0 ----- 3rd shift  
 1 0 0 0 0 ----- 4th shift  
 0 0 0 0 0 ----- 5th shift (all the bits are shifted!)  

---

I still don't have a method of combining the two 32-bit variables to get a 64-bit one

Consider: a is 64 bit, b and c are 32 bit

a = b;
a = a << 32; //Note: a is 64 bit
a = a | c;

Answer 4

Unless this is some "reinventing the wheel to understand how it works" project, don't implement your own crypto functions.

Ever.

It's hard enough to use the available algorithms to work (and to choose the right one), don't shoot yourself in the foot by putting in production some home grown cryptor API. Chances are your encryption won't encrypt

Answer 5

What's bad about shifting a 32-bit variable 32 bits?

In addition to what have been already said, the 32nd bit is the sign bit, and you may get sign extension to preserve the sing, thereby losing significant bits.