1

I'm writing C and C# code (same example, same algorithm, two languages).

I was wondering is there a fast way to obfuscate an int? The fastest way I can think of is newInt = currentInt ^ harcodedNumber. But that's obvious and lame. You'll 100% know the numbers are sequential. The other solution I thought of is newInt = currentInt ^ randomInt ^ harcodedNumber then return both newInt and randomInt. I was wondering if someone could come up with something better?

-Edit- Duplicate isn't my question at all and isn't a solution either since it can't be reverse

Cal
  • 121
  • 8
  • @SeverinPappadeux looks like it, but what's a coprime with 2^64? I tried searching 18446744073709551616 with no luck – Cal Jul 01 '22 at 04:18
  • The transform doesn't seem to be reversible? I chose this number for being a coprime of `1<<40` and `(1<<40)-1` `#include long long transform(unsigned long long v) { return (511627973ULL*v + 41121546321) & 1099511627775ULL; } int main(int argc, char *argv[]) { auto a = transform(25); auto b = transform(a); printf("%llu %llu\n", a, b); }` – Cal Jul 01 '22 at 04:38
  • The LCG transform referred to by @SeverinPappadeux is "reversible" by moving forward. See [here](https://stackoverflow.com/a/48078247/2166798) for an explanation. – pjs Jul 01 '22 at 13:23
  • @pjs My comprehensions is bad sometimes. Since my mod is 2^40 do I need to call transform that many times? If so I can't use this solution. If not what's the formula in C? I tried `transform((a + ((1ULL<<40)-1)) & 1099511627775ULL);` and it didn't get me my original value – Cal Jul 01 '22 at 15:51
  • Your question *is* a duplicate of the link I provided above. And no, the math in that link shows that you don't need to call your generator 2^40 times. The Ruby script provided calculates the inverse transform which is the equivalent of (2^40) - 1 calls. However, it needs the original LCG to have a full cycle, which your choice of coefficients don't provide. `(25214903917 * v + 11) & 1099511627775` ***is*** a full cycle 40 bit generator, and the script calculates its inverse as `(963612709733 * v + 395376470697) & 1099511627775`. – pjs Jul 01 '22 at 17:13
  • @pjs should I edit my question to show the code I used (which is hard to read in the comments above)? I still have no idea how to solve my problem. I picked a coprime to 2^40 like the original comment suggested and I used the formula. I have no idea what's involved and getting a coefficient that'll let me have a full cycle to reverse this. I want to do something like `originalValue=untransform(transform(value)); assert(originalValue==value);` – Cal Jul 01 '22 at 17:53
  • 1
    1) All relevant info should always be in the question itself here on SO. 2) The [requirements to have a full cycle LCG algorithm](https://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length), where each value in the range maps to a unique other value, are available on Wikipedia. Your coefficients didn't meet those requirements. 3) I gave you two functions in my last comment which work as a transform/untransform pair for 40 bit quantities. – pjs Jul 01 '22 at 18:03
  • @pjs thank you! It works. I must have left an old value in my code or mixed something up. Rewriting it from scratch with your numbers worked immediately – Cal Jul 01 '22 at 18:19
  • @pjs would you happen to know numbers that would work on unsigned 64bit? I don't actually know if 2^40 will serve 100% of my uses but I imagine it does – Cal Jul 01 '22 at 18:27
  • I didn't know them but I looked up coefficients in the LCG wikipedia page for 64bits, and ran them through the Ruby script. I've given you the process and tools, after this you're on your own. xform: `(0x5851f42d4c957f2d * x + 0x14057b7ef767814f) & 0xffffffffffffffff`, inverse: `(0xc097ef87329e28a5 * x + 0x9995b5b621535015) & 0xffffffffffffffff`. – pjs Jul 01 '22 at 18:50
  • In C/C++ you don't need to do & 0xffffffffffffffff part, result will overflow which would be equivalent of taking lower 64bit. So xnext = (0x5851f42d4c957f2dULL * xprev + 0x14057b7ef767814fULL); is sufficient, assuming x is of type uin64_t (aka unsigned long long). Same for inverse. Values above for (a,c) are taken from Knuth, but if you want to get different good (a, c) pairs, check l'Ecuyer paper in the Wiki LCG page. Good luck. – Severin Pappadeux Jul 01 '22 at 19:43
  • @SeverinPappadeux I couldn't understand the wikipedia or pjs, I don't have hope on understanding the paper! The numbers work but it would be interesting if I knew several numbers to use to have it more obfuscate. But I could always use salt or something if I really wanted that – Cal Jul 01 '22 at 19:46
  • ok, here are three (a,c) 64bit pairs, in decimal, from l'Ecuyer paper (2862933555777941757,1) (3202034522624059733, 1) (3935559000370003845, 1). You could use any odd prime instead of 1 as c replacement. For inversion, look at pjs script in his link – Severin Pappadeux Jul 01 '22 at 20:17
  • @SeverinPappadeux oh I'm pretty slow. So if I give pjs's power_mod function an array of a and c (a is what I multiply, c is what I add) it returns a list of m and c that will inverse the result? I haven't looked at those numbers but I'm assuming they're either prime or coprime with 2^64? I have enough to go on but right now I'm using pjs numbers. I also need to install ruby so I can run that code or figure out how to rewrite it (which may or may not be fun, I have no idea what ruby is like) – Cal Jul 01 '22 at 20:32
  • 1
    Yes. Below is one example from origin pjs link, for 32 bit numbers arr = Array[1664525, 1013904223]; mod = 2**32; pwr = mod - 1; print power_mod(arr, mod, pwr); – Severin Pappadeux Jul 01 '22 at 23:03
  • 1
    And example for 64 bit just couple of comments above arr = Array[6364136223846793005, 1442695040888963407]; mod = 2**64; pwr = mod - 1; print power_mod(arr, mod, pwr); – Severin Pappadeux Jul 01 '22 at 23:05
  • 1
    Run them through ruby and check output – Severin Pappadeux Jul 01 '22 at 23:06
  • @SeverinPappadeux for fun I tried again. I put power_mod into https://www.tutorialspoint.com/execute_ruby_online.php and called `puts power_mod([0x5851f42d4c957f2d, 0x14057b7ef767814f], 0xFFFFFFFF, 64)`. I did not get any numbers mentioned on this page. This is the first time on stackoverflow that I didn't understand a word anyone said to me – Cal Jul 02 '22 at 03:01
  • 2
    Ok, here is the link. Numbers are decimal, you could make hex out of them. http://tpcg.io/_1MPTVS – Severin Pappadeux Jul 02 '22 at 03:16
  • 1
    @Cal The third argument to `power_mod` is the modulus, which is 2^64. (The method uses modulo arithmetic rather than bit masking because it works for any linear congruential generator, not just those with a modulus which is a power of 2.) The last argument is the power to which you want to raise the transform, i.e., the number of iterations to be applied. To get full cycle, that would be as many iterations as there are distinct values, so it would also be 16 F's. – pjs Jul 02 '22 at 03:30
  • @pjs last argument should be period - 1, I believe. 0xFFFFFFFFFFFFFFFF-1 – Severin Pappadeux Jul 02 '22 at 12:47
  • @SeverinPappadeux To get the predecessor of a value you need to conceptually iterate `cycle length-1` times. For a full cycle LCG with additive constant the cycle length is `modulus-1` , while for a purely multiplicative generator (i.e., the additive constant is zero) it’s `modulus-2` because 0 is not an allowable state. If you’re using a modulus which is a power of 2 you can bitmask with an `&`, but the mask is `modulus-1`. In other words, you need to understand your algorithm and its properties and adjust the arguments accordingly. – pjs Jul 02 '22 at 14:00
  • @pjs I was right writing last argument should be period-1, but I was wrong wrt FFFFFFFFFFFFFFFF-1, should be just FFFFFFFFFFFFFFFF. You are wrong, I believe, in stating that cycle length is modulus-1. For a full period LCG with proper a,c!=0 the cycle length is equal to m. https://faculty.ksu.edu.sa/sites/default/files/or441-lec05-random_number_generation_lcg_-sep_2017_0.pdf slide 15 – Severin Pappadeux Jul 02 '22 at 15:33
  • @SeverinPappadeux Yup, you're right that the cycle length is the modulus for a full period LCG with a proper multiplier and `c!=0.` That's why you get the predecessor value by conceptually going modulus - 1 iterations. It's very easy to get off-by-one, particularly in switching between modulo operations vs bitmasks for powers of 2. Thanks for catching and clarifying this! – pjs Jul 02 '22 at 17:12
  • @pjs I put your function with couple of examples at http://tpcg.io/_SQWBUG I think that is it for the question at hands – Severin Pappadeux Jul 03 '22 at 03:05

0 Answers0