9

How can you inexpensively two-way encrypt a 32 bit int, such that every number maps to some other int in that space and back in a way that's difficult to predict?

And doesn't require pre-storing 4.29 billion ints in a mapping table, of course.

ʞɔıu
  • 47,148
  • 35
  • 106
  • 149
  • See also http://stackoverflow.com/questions/858476/12-digit-number-java-encryption-question It's not exactly the same, but the same reasoning applies to explain why this is not secure. – erickson Jun 06 '09 at 15:30
  • 3
    erickson: "Not secure" depends on the context. There's nothing a-priori wrong with 'encrypting' 32 bit ints, as long as chosen-plaintext attacks aren't possible. – Nick Johnson Jun 07 '09 at 20:57

10 Answers10

19

What you want is a 32-bit block cipher. Unfortunately, most block ciphers are 64-bits or more due to the weaknesses of a short block size. If you can handle the encrypted int being twice as large as the input, then you can just use Blowfish, TDES, or some other nicely vetted 64-bit block cipher.

If you really need 32 bits and don't mind the decreased security then its easy enough to trim a Feistel network cipher like Blowfish down to any block length that's a multiple of 2 and less than the starting cipher. For Blowfish, just split your input number evenly between the two half blocks, and trim the output of the F function and the P-values down to 1/2 your target block size. This can all be done after keying the algorithm as usual.

Theran
  • 3,776
  • 20
  • 31
7

Obviously, you need some kind of random key for it to be secure. In that case:

int original = 42;
int key = give_me_a_random_int();

int encrypted = original ^ key;
int unencrypted = encrypted ^ key;

// now, unencrypted == original == 42

This is just a simple XOR. XORing again will reverse this process.

Also, I should note that this is only secure for one use. It's called the One time pad. If you use the same key twice on non-random data, it may be possible for an attacker to decipher it.

Zifre
  • 26,504
  • 11
  • 85
  • 105
  • 4
    If there are any patterns or biases in the plain text, they will show up when two messages that were encrypted with the same key are XORd together. (A ^ K) ^ (B ^ K) = A ^ B. – erickson Jun 06 '09 at 15:32
  • 2
    Also 2^32 is not a very large key space to brute force. – laalto Jun 06 '09 at 15:34
  • When you use same key more than once and attacker can preform known plaintext attack, the XOR algorithm is useless. Having known A and B = A ^ K one may simply obtain K = A ^ B. – lispmachine Jun 06 '09 at 15:43
  • 1
    @laalto: You can't brute force this, but you can only use it once on non-random data. – Zifre Jun 06 '09 at 15:51
5

Use a 32-bit block cipher, skip32 is the only one that I found: http://www.qualcomm.com.au/PublicationsDocs/skip32.c

Emre Yazici
  • 10,136
  • 6
  • 48
  • 55
1

One way is to XOR with a secret 32 bit number. When you XOR with this secret number again, it will return to the original number. This is quick but not very secure. If a secure method is needed, i'd be interested in seeing other methods here too.

nonopolarity
  • 146,324
  • 131
  • 460
  • 740
  • Assuming the key is secret and random, this is probably secure. – Zifre Jun 06 '09 at 15:27
  • 2
    This is terribly insecure: XORing two output numbers together will produce the XOR of the two input numbers, revealing a lot about the source, and possibly allowing an attacker to figure out what the secret was, too. – Nick Johnson Jun 07 '09 at 20:53
  • 1
    I meant for a single number. It is the MOST secure possible method for a single use (see One time pad). – Zifre Jun 10 '09 at 22:59
1

Use a standard algorithm and a random pad (assuming the ciphertext doesn't need be the same length as the plane text).

So basically, use a standard algo that uses chaining and plug four random 32-bit numbers in front of it. That should help to disguise any regularities/redundancy in your 32-bit message. Hell, pad at the end too, if it pleases you.

Basically, the less you write, the better off you are. Everyone screws this stuff up.

Alex Gartrell
  • 2,514
  • 5
  • 22
  • 23
  • "Everyone screws this stuff up" is true of inventing your own crypto _scheme_, too. – Nick Johnson Jun 07 '09 at 20:55
  • I invented the initialization vector? From _Applied Cryptography_ by Schneier, page 194 Some messages have a common header: a letterhead, or a "from" line or whatever. While block replay would still be impossible, this identical beginning might give a cryptanalyst useful information. Prevent this by encrypting random data as the first block. This block of random data is called the initialization vector (IV). – Alex Gartrell Jun 07 '09 at 23:27
  • 1
    Yup, but you suggested multiple blocks worth, which is pointless given that the state of a block cipher is only one block long. It also doesn't really apply when the OP wants to map a 32 bit int to another 32 bit int. – Nick Johnson Jun 07 '09 at 23:59
  • 1
    Also, most crypto libraries treat IVs as separate from the data, especially since some block chaining modes require it. :) – Nick Johnson Jun 07 '09 at 23:59
  • Well wasn't it a little presumptuous to assume that he was using such a library? I mentioned that the padding would screw over the 1 to 1 requirement. You win with the single block thing though. I didn't do my math thoroughly enough there. Still, don't you think it's a little unfair to say that I've "invented a scheme" here? – Alex Gartrell Jun 08 '09 at 00:27
  • Line breaks are not preserved in comments; apologies for the lack of logical path in my comments :) – Alex Gartrell Jun 08 '09 at 00:27
  • Not really - decent crypto libraries are available for most languages, and I'm not aware of any that don't directly implement chaining modes and IVs. But I was perhaps a bit over-harsh - I just hate seeing 'invent it yourself' crypto ansers. :) – Nick Johnson Jun 08 '09 at 03:47
  • One answer (above) recommends writing your own xor-and-shift algo. I recommended using an off-the-shelf algo w/ some random padding (albeit redundant random padding). Mine was the one worth striking down? (I'm just being argumentative for argument's sake atm :) ) – Alex Gartrell Jun 08 '09 at 05:19
  • I struck down the build-your-own, too. :P – Nick Johnson Jun 08 '09 at 13:17
0

Have a look at: github.com/msotoodeh/integer-encoder project. It supports 32 and 64 bit integers.

msotoodeh
  • 61
  • 3
0

There are two simple and reversible operations that you can use to scramble an integer value. You can use the xor operation, and you can swap bits in the number.

If you use both, then it won't be that trivial to figure out the method used. They will somewhat protect each other.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • 3
    You're essentially recommending that the asker invent their own block cipher. This seems like a bad approach. – Nick Johnson Jun 07 '09 at 20:53
  • 1
    It's fast and simple, so it does a pretty good work if you just want to scramble the value. Of course it doesn't do much towards a real encryption, but that's not really possible with the limitations given in the question anyway. – Guffa Jun 07 '09 at 22:16
  • 1
    Sure it is - use a block cipher, as the other poster suggested. There's no reason to roll-your-own. – Nick Johnson Jun 08 '09 at 03:29
0

If all you want is something real simple that the average user wont notice then use a series of XOR and shift operators.

The problem with not using an array to store the 4 billion or so INTs is that you need a function that does a one to one random map across a domain of 4 billion INTs. You can mix a number of XOR and shift operators to create your own but it wont be hard to crack. Even if there was a well known one to one map it would also fail. Without a salt someone could just generate a simple rainbow table to break it.

The problem with a salt in two way communication is that you have to securely communicate it. Salts have to be secret and once you know what they are they are pointless.

If your looking to setup a secure channel of communication take a look at Off-the-Record Messaging Protocol version 2. It will give you an example of how complex communication encryption can become. I'd suggest you find something well known that someone else has already created and tested. Even if you do use something someone else has created if you use it incorrectly it will fail.

gradbot
  • 13,732
  • 5
  • 36
  • 69
0

Take your 32 bit input, cut it into two 16 bit halves L and R, then repeat the following steps: compute a pseudorandom function of R, xor the result of this pseudorandom function to L and swap L and R. This is a Luby-Rackoff construction. The pseudorandom function does not need to be invertible. So you could for example take a block cipher, encrypt 16-bits and cut the result to 16 bit. Make sure that not all rounds use the same pseudorandom function (rsp. use different round keys).

Accipitridae
  • 3,136
  • 19
  • 9
-1

I used to use XOR + ADD with a 64 bit secret key. I also used to change the key every couple of minutes and trying to decrypt with current or previous key. (In my domain the integer didn't need to be secure for more than about four minutes.)

Joshua
  • 40,822
  • 8
  • 72
  • 132