Timeline for Collision-free one-wayish function mapping 32 bit to 32 bit
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2018 at 16:30 | vote | accept | VincBreaker | ||
| Feb 25, 2018 at 18:45 | comment | added | Meir Maor | A full table lookup of this size is only 16GB, this fits easily into RAM on my laptop. | |
| Feb 25, 2018 at 16:25 | history | edited | Ella Rose | CC BY-SA 3.0 |
moved the actual goal from a comment into the question body
|
| Feb 24, 2018 at 23:25 | answer | added | fgrieu♦ | timeline score: 5 | |
| Feb 24, 2018 at 16:04 | history | tweeted | twitter.com/StackCrypto/status/967429994472452097 | ||
| Feb 22, 2018 at 19:04 | comment | added | VincBreaker | @mikeazo The function will be used to obfuscate if-statements (by comparing the outputs of the function. | |
| Feb 21, 2018 at 17:38 | comment | added | mikeazo | This may be somewhere that white box crypto could be used. Can you explain to us what the application you are targeting is? Maybe there is a different approach besides this 32 bit to 32 bit mapping. | |
| Feb 21, 2018 at 16:35 | comment | added | VincBreaker | @Ruggero I know that once the lookup tyble is build, you don't need to bruteforce again, but the attacker still has to do all 2^{32} calculations. What I'm trying to prevent is the attacker being able to recover a key for an underlying block-cipher and then being able to invert the function with $O(1)$ komplexity. | |
| Feb 21, 2018 at 16:29 | comment | added | VincBreaker | @mikeazo Yes, I'm afraid that an attack knowing the key would be able to invert the typical PRP (or block-cipher) significantly faster since they would be able to use an invertion function for the block-cipher. | |
| Feb 21, 2018 at 9:00 | comment | added | Ruggero | @Maeher No. Input size is $2^{32}$, you just need $2^{32}$ calls to your function to build a look-up table. $2^{32}$ calls to e.g. SHA-512 is very feasible. A whitebox implementation can be used to build such a table and then inverting any output will be trivial. The requirement "the goal is to not let attackers find the input in a way faster than bruteforce" is senseless in my opion. It should be better explained. | |
| Feb 20, 2018 at 18:58 | comment | added | mikeazo | It is not clear to me why a function that relies on a key (which will be fixed in source code) will not work. Are you afraid that the attacker (knowing the key) can be significantly faster than brute force? | |
| Feb 20, 2018 at 18:19 | comment | added | Maeher | @Ruggero If we use a random member of a large enough family of functions (i.e. the way one-way functions are defined) precomputing a look-up table should be infeasible. This is strictly necessary, otherwise as you correctly note inverting is essentially a single memory access. | |
| Feb 20, 2018 at 17:00 | comment | added | VincBreaker | @Ruggero Yes, I know, but the attack still shouldn't be able to inverse the function with significantly faster than brute-forcing / building a lookup-table. | |
| Feb 20, 2018 at 16:49 | comment | added | Ruggero | Same number of input and output, no collision, then it will be a permutation. Attacker can just build a LookUpTable through bruteforce and then use it to invert any value just through a table lookup. | |
| Feb 20, 2018 at 16:44 | history | edited | VincBreaker | CC BY-SA 3.0 |
Added attack vector and discarded ideas
|
| Feb 20, 2018 at 16:40 | comment | added | VincBreaker | I've already thought about PRP's, but since it will have to run in a white-box environment and probably will face some competent reverse engineers, I'd rather use a function not relying on keys to be secure. | |
| Feb 20, 2018 at 16:34 | comment | added | mikeazo | Okay, then how about a stream cipher with a fixed key? Or a PRP. | |
| Feb 20, 2018 at 16:31 | comment | added | VincBreaker | I tried a couple of hash function, sadly all of them had collisions when being truncated to 32 bit. | |
| Feb 20, 2018 at 16:30 | comment | added | mikeazo | Have you tried truncating a common hash function (maybe SHA-256)? | |
| Feb 20, 2018 at 16:20 | history | asked | VincBreaker | CC BY-SA 3.0 |