1
$\begingroup$

I would like to hash numbers less than 1000000000, so generally they could be stored on 30 bits. The aim is to obtain numbers that are not reversible, so my initial plan was to use SHA256 (with some salt). However, I would like to keep the output as short as possible, but I want to be sure that there are no collisions. Hash functions do not guarantee me that-- especially when I truncate their output. Probably I could check if there are collisions for my numbers, but maybe there is some better way?

Is it possible to reduce the size of the output of AES and keep uniqueness-- assuming that I don't need to decrypt and it is even desired to not be able to do so? Maybe divide each output into four parts and XOR all of them to get a 32-bit output?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ One way is using FF1 to construct arbitrary block-sized block cipher. If the security is not important then see CS collision resolution techniques like separate chaining and open hashing. $\endgroup$
    – kelalaka
    Commented Aug 2, 2019 at 20:34
  • $\begingroup$ I would like to use cryptographic functions already available in my database software and avoid writing my own functions. Only typical encryption algorithms are available in it like AES for example. Concerning security, I would like to be possibly hard to decypher my numbers even for someone that knows exactly what range of numbers are cyphered. $\endgroup$
    – Cob
    Commented Aug 2, 2019 at 20:42
  • $\begingroup$ You could do something with RSA, but the small primes necessary would limit your security. $\endgroup$
    – Eugene Styer
    Commented Aug 2, 2019 at 20:50
  • 1
    $\begingroup$ @kodlu you can find FF1,FF3, FF3-1 in SP 800-38G Rev. 1 (DRAFT) $\endgroup$
    – kelalaka
    Commented Aug 3, 2019 at 14:22
  • 1
    $\begingroup$ @mentallurg, thanks, I read carelessly. The OP should state their exact goal and threat model. $\endgroup$
    – kodlu
    Commented Aug 4, 2019 at 11:28

1 Answer 1

Reset to default
0
$\begingroup$

For the parameters you gave, the birthday paradox will kick in and you will get collisions, since the set of integers you want to process is much larger than $\sqrt{2^{30}}$.

A very simple countermeasure would be for input $x_k$ to use bits $(y_{k,1}\ldots,y_{k,30})$ of the AES output $$ (y_{k,1}\ldots,y_{k,128}):=AES_K(x_k) $$ (for a fixed randomly chosen secret key $K$, you can use some fixed padding on $x$ if you wish).

Say you you have processed $x_1,x_2,\ldots,x_m$ with no collision and placed the outputs $$ (y_{1,1}\ldots,y_{1,30}),\ldots, (y_{m,1}\ldots,y_{m,30}), $$ in a sorted list. Say $(y_{m+1,1}\ldots,y_{m+1,30})$ collides with a previously chosen output vector. Then keep checking $$ (y_{m+1,j},\ldots,y_{m+1,j+29}),\quad j\geq 2, $$ until you get a 30 bit pattern that doesn't collide with that vector. Due to the good randomness properties of AES this will succeed in a few iterations after each collision, with high probability.

You can then store the cordinate index $j_x$ used to generate this vector together with $x_{m+1}$ if reproducibility is required.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ In fact my situation is not as bad, because I have to process about 35000000 of numbers from that range, but still collisions may easily occur occording to your answer. Your solution is nice, but I would have to do kind of a preprocessing, and check my whole set of numbers with some script. I wanted to avoid that, but probably it is not possible. Would it be better to use AES or for example SHA256 for your algorithm? $\endgroup$
    – Cob
    Commented Aug 3, 2019 at 5:48
  • $\begingroup$ Either AES or SHA would work $\endgroup$
    – kodlu
    Commented Aug 3, 2019 at 5:52
  • $\begingroup$ What is exactly unclear? $\endgroup$
    – kodlu
    Commented Aug 3, 2019 at 22:23
  • $\begingroup$ @kelalaka see edit $\endgroup$
    – kodlu
    Commented Aug 4, 2019 at 1:17
  • $\begingroup$ Ok. I can see better now. There is still a possibility that the all $ (y_{m+1,j},\ldots,y_{m+1,j+29}),\quad j\geq 2,$ can produce collision. One may also change the key in that case. $\endgroup$
    – kelalaka
    Commented Aug 4, 2019 at 8:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.