Timeline for Making a cipher non-malleable using a plaintext transform?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 13, 2020 at 11:00 | comment | added | Modal Nest | Yeah the "i" is local to the function. And clearly if fst8 did nothing then it would return the same data. You are being obtuse and silly regarding passes now. Have a look at your answer again for your own definition of pass. I do it in one pass. Not two passes. There are no more operations at each stage for 1MB which is processed quicker than 1024 * 1KB. | |
| Dec 13, 2020 at 10:26 | comment | added | Surprised Seagull | it seems some functions are not used. Assuming only rollF is called, we have: line 12 "while (i<xl.length){", line 17 "roll=fst8(roll,con);", line 76 "while (i<10){", and unrolled set of operations just after line 76. In total you do about N^3 operations. Its not a general solution. If you would have 1MB of input data, you will have more operations on each stage. N^3 means that for 1000 data blocks, you will need a million 'passes', if each pass is N operations. You may like thisfor generality: en.wikipedia.org/wiki/Linear-feedback_shift_register but it is still excessive I think. | |
| Dec 13, 2020 at 2:51 | comment | added | Surprised Seagull | It can not be done in one pass, unless you have N cores, you need 2N sequential steps minimum. It can not be speed up by parallelization more than twice, to 1N, assuming you have as many cores as there are N. PCG can also work on big words like 160bits, if CPU supports it. | |
| Dec 11, 2020 at 13:18 | comment | added | Modal Nest | Well with a Feistel set in an OAEP way (with additional capacity) you've got message (N long) and capacity (x long). Unlike a hash you keep the capacity as it's a nonce. I said (I think) it can be done in one pass. I said parallel to an extent. For those 3 pcg constants in a 256bitFeistel you can process 160bits of the message at once. Anyway I'll go into better detail when I update my answer. | |
| Dec 11, 2020 at 12:15 | comment | added | Surprised Seagull | ... already takes more state than PCG state. One pass solution is impossible without massively bigger state. How would you know if end of message affected the beginning without storing the message in state, and lots of pointers? PCG solution does not need to store additional pointers. If you want to count state a solution takes, then count all of it. For PCG it is message (N long) + pcg state (1 word) + pcg constants (3 words) + counter of current location (1 word) + flag if its a first or second run (1 word). How do you expect to take less memory, or do this task in parallel? | |
| Dec 11, 2020 at 12:09 | comment | added | Surprised Seagull | There is no way to run this algorithm in parallel, even in theory, for O(N), unless unnecesary actions are made. You want all data to be linked to all data. This requires O(n) in series, or O(N^2) in parallel, and N^2 is much larger. Any solution you will have will be a few times slower at least. The only faster solution is LCG itself, or xorshift-like, with bad avalanche property. Additional state can be reduced to 32bit, comparable to the counter you are using to take next element. Any other solution will take more state (or the same. again, LCG or xorshift-like). Remembering pointers... | |
| Dec 11, 2020 at 11:51 | comment | added | Modal Nest | Note how I've edited the links. You've probably been voted down for that or the unnecessary/unclear paragraph "For example, initial seed". This idea had crossed my mind (not PCG specifically). Regarding speed of operation, I'm a bit dubious. A tweaked OAEP might run more operations but it can run parallel (to an extent) and the state size is the plaintext and nonce. And (I think) it can be done in one pass. I will update my answer later. Using a "decent" PRNG requires running additional state on top. Admittedly, so does my initial hack code. | |
| S Dec 11, 2020 at 11:33 | history | suggested | Modal Nest | CC BY-SA 4.0 |
fixed spelling/links
|
| Dec 11, 2020 at 10:40 | review | Suggested edits | |||
| S Dec 11, 2020 at 11:33 | |||||
| Dec 11, 2020 at 7:56 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
proof reading
|
| Dec 11, 2020 at 7:48 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
finally figured out how to decode chained prng reseeding
|
| Dec 11, 2020 at 7:13 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
i got what maleability means; added 154 characters in body
|
| Dec 11, 2020 at 7:07 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
i got what maleability means; added 154 characters in body
|
| Dec 11, 2020 at 5:04 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
changed the explanation a bit, for decoding
|
| Dec 11, 2020 at 4:28 | history | edited | Surprised Seagull | CC BY-SA 4.0 |
need to find example of PCG reversing, for decoding
|
| Dec 11, 2020 at 4:17 | history | answered | Surprised Seagull | CC BY-SA 4.0 |