5 ms·

If I am not mistaken 0xAAAAAAAA5 is 45812984485 = 5 * 28297 * 323801. At least that is what factor $(echo -e "ibase=16\nAAAAAAAA5" | bc -l) claims.

dragontamer 8y ago
Oh man, a typo. Lol. I meant 0xAAAAAAA5... sorry about that. Lemme muse on the concept: "multiplying by 0xAAAAAAA5" is that the binary is 1010,1010,1010...0101. A multiplication at its core, is equivalent to a LOT of bitshift-left and add. Multiplying by "1000" is the same as bitshift left by 4. Multiplying by "1010" is bitshift left by 4 + bitshift left by 2. This is why its important to multiply by an odd number: all those bitshifts lose the top-most bit. You only keep the topmost bit if the bottom-most bit is set. So multiply by 0xAAAAAAA5 is the same as "bitshift left 31 + bitshift left 29 + bitshift left 27 ... + bitshift left 2 + bitshift left 0", all at once. Addition itself is a great "mixing" instruction, its an XOR innately with the potential for carries. The carries make the XORs far more complicated to analyze. The 31st bit after all of those bitshifts are not only the XOR of a bunch of bits... but also the "propagated carry bit". The topmost bit of any multiplication operation is very complex, while the bottom most bit is always the original bit (bit0 is only affected by bit0 from the input). That's why a rotation + 2nd multiply is needed.
- andromeduck 8y ago
  Addition and multiplication also leak more information via side channels than bit shift and xor.
  - dragontamer 8y ago
    I'd be surprised if that's true. I'm pretty sure addition is always 1-clock tick latency / 3-instructions per cycle. While Multiplication is 5-clock tick latency / 1-instruction per cycle IIRC. So if the timing of those instructions are constant, it seems difficult to side-channel / timing attack them.
    - andromeduck 8y ago
      there's also power, 0xffffffff + 0x1 results in 32 bit flips, 0x0 + 0x1 results in 1, they don't consume the same amount of energy.
- petschge 8y ago
  0xAAAAAAA5 make a lot more sense as it is a 32 bit integer. Btw it is 36 * 52 * 157109, so not an integer, just like you expected. Then again you don't care about that, but the bit pattern. Any reason why use use 0xAAAAAAA5 instead of 0xAAAAAAAA or 0xA5A5A5A5?
  - dragontamer 8y ago
    > 0xAAAAAAA5 instead of 0xAAAAAAAA or 0xA5A5A5A5? 0xAAAAAAAA isn't odd. Every time you multiply with 0xAAAAAAAA, you lose the top-most bit of your state (alternatively: the bottom-most bit will ALWAYS be zero. So you lost a bit). If you start with 32-bits of entropy, multiplying with 0xAAAAAAAA results with 31-bits of entropy. > 0xA5A5A5A5 That's where statistical tests need to come into the picture, to differentiate. I've written GPGPU programs to brute-force search for constants based on a few metrics. In these brute-force searches, even a simple number like 0xAAAAAAA5 works out decently. Its suboptimal in my experience, but its surprisingly "not bad". My only point is that you shouldn't limit your search to prime numbers. Any odd number works pretty decently as a multiplication constant.

dragontamer 8y ago

Oh man, a typo. Lol. I meant 0xAAAAAAA5... sorry about that. Lemme muse on the concept: "multiplying by 0xAAAAAAA5" is that the binary is 1010,1010,1010...0101. A multiplication at its core, is equivalent to a LOT of bitshift-left and add. Multiplying by "1000" is the same as bitshift left by 4. Multiplying by "1010" is bitshift left by 4 + bitshift left by 2. This is why its important to multiply by an odd number: all those bitshifts lose the top-most bit. You only keep the topmost bit if the bottom-most bit is set. So multiply by 0xAAAAAAA5 is the same as "bitshift left 31 + bitshift left 29 + bitshift left 27 ... + bitshift left 2 + bitshift left 0", all at once. Addition itself is a great "mixing" instruction, its an XOR innately with the potential for carries. The carries make the XORs far more complicated to analyze. The 31st bit after all of those bitshifts are not only the XOR of a bunch of bits... but also the "propagated carry bit". The topmost bit of any multiplication operation is very complex, while the bottom most bit is always the original bit (bit0 is only affected by bit0 from the input). That's why a rotation + 2nd multiply is needed.

andromeduck 8y ago
Addition and multiplication also leak more information via side channels than bit shift and xor.
- dragontamer 8y ago
  I'd be surprised if that's true. I'm pretty sure addition is always 1-clock tick latency / 3-instructions per cycle. While Multiplication is 5-clock tick latency / 1-instruction per cycle IIRC. So if the timing of those instructions are constant, it seems difficult to side-channel / timing attack them.
  - andromeduck 8y ago
    there's also power, 0xffffffff + 0x1 results in 32 bit flips, 0x0 + 0x1 results in 1, they don't consume the same amount of energy.
petschge 8y ago
0xAAAAAAA5 make a lot more sense as it is a 32 bit integer. Btw it is 36 * 52 * 157109, so not an integer, just like you expected. Then again you don't care about that, but the bit pattern. Any reason why use use 0xAAAAAAA5 instead of 0xAAAAAAAA or 0xA5A5A5A5?
- dragontamer 8y ago
  > 0xAAAAAAA5 instead of 0xAAAAAAAA or 0xA5A5A5A5? 0xAAAAAAAA isn't odd. Every time you multiply with 0xAAAAAAAA, you lose the top-most bit of your state (alternatively: the bottom-most bit will ALWAYS be zero. So you lost a bit). If you start with 32-bits of entropy, multiplying with 0xAAAAAAAA results with 31-bits of entropy. > 0xA5A5A5A5 That's where statistical tests need to come into the picture, to differentiate. I've written GPGPU programs to brute-force search for constants based on a few metrics. In these brute-force searches, even a simple number like 0xAAAAAAA5 works out decently. Its suboptimal in my experience, but its surprisingly "not bad". My only point is that you shouldn't limit your search to prime numbers. Any odd number works pretty decently as a multiplication constant.