Secure permutation of a 1e8 element set
Maaartin
customer numbers. The reason is simple, I need to store them back in
the database and do all the operations as it were the original plain
data. I need it in order to get rid of all the sensitive data while
still being able to work as before and also to find out the original
(I already replaced names and addresses etc. by some Gibberish, this
was easy).
Let's say, allowed are all numbers from the set 0..99999999. I can't
use any strong cipher, as imho they all deal with huge sets. I can't
use some home cooked bit twiddling as the cardinality of the set is
1e8 which is no power of two. I could generate a permutation of the
set using a deterministic secure random generator, but it takes a lot
of memory (and there are also numbers consisting of more digits).
Joseph Ashwood
news:175f3983-1471-4a97...@u28g2000hsc.googlegroups.com...
You simply will not find a secure permutiation, as you noted any permutation
could be simply stored in memory making it inherently weak. Based on that I
would choose RSA, it won't be secure, but limiting the range arbitrarily is
easier. Don't worry about secure formatting, whatever you do won't be secure
anyway, just use the original RSA algorithm.
Joe
Thomas Pornin
> Let's say, allowed are all numbers from the set 0..99999999. I can't
> use any strong cipher, as imho they all deal with huge sets. I can't
> use some home cooked bit twiddling as the cardinality of the set is
> 1e8 which is no power of two. I could generate a permutation of the
> set using a deterministic secure random generator, but it takes a lot
> of memory (and there are also numbers consisting of more digits).
A generic construction is given there:
"Perfect Block Ciphers with Small Blocks", L. Granboulan and T. Pornin,
Fast Software Encryption - FSE 2007, LNCS 4593, Springer-Verlag, 2007.
which can also be downloaded there:
http://www.bolet.org/~pornin/2007-fse-granboulan+pornin.pdf
but it is not easy to implement efficiently, due to the computation of a
probability distribution with enough precision. In my own tests, I got
to the speed of about 0.3s per encryption, which is pathetic.
--Thomas Pornin
Unruh
Except that there is no modulus N for RSA which will take 0-9999999
into 0-9999999 . 10^8 is a horribly composite number whith the only
prime factors being 2 and 5, and both are multiple factors.
Of course if there are numbers consisting of more digits, then all bets are
off. What is it you want to do? Do you reallywant to use 10 different
encryptions, one for each number limit?
I think you have to decide on one maximum. If it does not reallymatter then
choose some RSA number and use his suggestion. You could always cook up a
Feistel cypher based on digits, not bits (use base 10 modulus addition as
the combiner).
Paul Rubin
> Let's say, allowed are all numbers from the set 0..99999999. I can't
> use any strong cipher, as imho they all deal with huge sets. I can't
> use some home cooked bit twiddling as the cardinality of the set is
> 1e8 which is no power of two.
There is a well known trick used in Schroeppel's Hasty Pudding Cipher
for permuting arbitrary integer ranges. The basic idea is that
you map to within the nearest higher power of two using bit twiddling,
and if the result falls outside the desired range, iterate the map
til you get within range. Since the map has a unique inverse you
can get the original number back by iterating the inverse map, again
until the result is within range.
I posted some code here a while back for permuting 10 digit SSN's but
you should be able to adapt it straightforwardly to 8 digit numbers:
http://groups.google.com/group/sci.crypt/msg/c4bdd165ba12b92a
David Malone
>Let's say, allowed are all numbers from the set 0..99999999. I can't
>use any strong cipher, as imho they all deal with huge sets. I can't
>use some home cooked bit twiddling as the cardinality of the set is
>1e8 which is no power of two. I could generate a permutation of the
>set using a deterministic secure random generator, but it takes a lot
>of memory (and there are also numbers consisting of more digits).
It depends a little on what you actually want to do, but you could
seed a crypto PRNG with your key and then just generate a permutation
using the PRNG. The table would only be about 380MB. Something like:
int perm[1000000];
arc4random_seed(key);
for (i = 0; i < 1000000; i++)
perm = i;
i = 1000000;
for (i = 1000000; i > 0; i--) {
n = arc4random_uniform(0, i);
SWAP(perm[n], perm[i]);
}
Then you map customer i to customer perm[i]. You can then toss the
key if don't want to ever regenerate the permutation.
David.
David Malone
>You simply will not find a secure permutiation, as you noted any permutation
>could be simply stored in memory making it inherently weak.
That's probably a little unfair to permutations that one can store.
A arbitary permutation of 1e8 numbers is equivelent to a key size
of about 2513272986 bits, if you count the number of possible
mappings. If I gave you the values of (say) P[0], ... p[999], you
couldn't say much about p[1000], other than it wasn't any of the
previous values I'd given you.
OTOH, if you tried to use it as a more general block cipher, I guess
that might not be a very good idea because the block size would be
a bit small.
David.
Oleg Khovayko
with operation ADD/SUB in the ring, ring size = 10000;
For it, split your 8-digit customer number to left and right blocks.
For instance, if customer number is 12345678, then
left = 1234
right= 5678
Thereafter, perform some rounds of encryption:
for(i = 0; i < N; i++) {
left = (left + F(subkey[i], right)) % 10000;
right= (right + F(subkey[i], left )) % 10000;
}
Where
- int subkey[N] is array of subkeys.
- F() is absolute _any_ complex mixing function,
which mixes two numbers together.
For simple demo_example, F can be:
int F(int k, int v) {
return (k * v >> 1) ^ k ^ -v;
}
Decryption can be performed in back order, from N-1 to 0:
for(i = N-1; i >= 0; i--) {
right= (right - F(subkey[i], left )) % 10000;
left = (left - F(subkey[i], right)) % 10000;
}
Oleg H.
biject
The way you dscribe the data base do you have the customer
data in two places one with the socalled duplicate number or are
you talking a about two separate data bases?
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Greg Rose
David Malone <dwma...@maths.tcd.ie> wrote:
>Maaartin <graj...@seznam.cz> writes:
>
>>Let's say, allowed are all numbers from the set 0..99999999. I can't
>>use any strong cipher, as imho they all deal with huge sets. I can't
>>use some home cooked bit twiddling as the cardinality of the set is
>>1e8 which is no power of two. I could generate a permutation of the
>>set using a deterministic secure random generator, but it takes a lot
>>of memory (and there are also numbers consisting of more digits).
>
>It depends a little on what you actually want to do, but you could
>seed a crypto PRNG with your key and then just generate a permutation
>using the PRNG. The table would only be about 380MB. Something like:
>
> int perm[1000000];
>
> arc4random_seed(key);
> for (i = 0; i < 1000000; i++)
> perm = i;
>
> i = 1000000;
> for (i = 1000000; i > 0; i--) {
> n = arc4random_uniform(0, i);
> SWAP(perm[n], perm[i]);
Array index 1000000 out of bounds on first time through the loop.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
Maaartin
> You simply will not find a secure permutiation, as you noted any permutation
> could be simply stored in memory making it inherently weak. Based on that I
> would choose RSA, it won't be secure,
Ok, I know it can't be secure in the usual sense.
But if I do any better, there would be no working database anymore.
RSA would be fine, but very slow, wouldn't it?
> but it is not easy to implement efficiently, due to the computation of a
> probability distribution with enough precision. In my own tests, I got
> to the speed of about 0.3s per encryption, which is pathetic.
Quite unusable, but interesting reading.
> I think you have to decide on one maximum. If it does not reallymatter then
> choose some RSA number and use his suggestion.
I'like to be able to encrypt any customer number I get,
and it must fit into the range.
> You could always cook up a
> Feistel cypher based on digits, not bits (use base 10 modulus addition as
> the combiner).
Yes, I've got already a plan for it, maybe the addition, maybe some
lookup table with a precomputed permutation of 0..9 in each row.
Additionaly I could permute the digits.
> There is a well known trick used in Schroeppel's Hasty Pudding Cipher
> for permuting arbitrary integer ranges. The basic idea is that
> you map to within the nearest higher power of two using bit twiddling,
> and if the result falls outside the desired range, iterate the map
> til you get within range. Since the map has a unique inverse you
> can get the original number back by iterating the inverse map, again
> until the result is within range.
A really nice idea. On the average I need to iterate less than twice,
right?
> I posted some code here a while back for permuting 10 digit SSN's but
> you should be able to adapt it straightforwardly to 8 digit numbers:
That's really easy, thank you.
> The table would only be about 380MB.
There's an account number with two more digits.
> That's probably a little unfair to permutations that one can store.
> A arbitary permutation of 1e8 numbers is equivelent to a key size
> of about 2513272986 bits, if you count the number of possible
> mappings. If I gave you the values of (say) P[0], ... p[999], you
> couldn't say much about p[1000], other than it wasn't any of the
> previous values I'd given you.
Yes, this is exactly what I want.
> OTOH, if you tried to use it as a more general block cipher, I guess
> that might not be a very good idea because the block size would be
> a bit small.
I'm really not going to do anything like this.
Once again, thanks to everybody.