search

hadipourh / zero

An Automatic Tool to Search for Full Impossible-Differential, Zero-Correlation and Integral Attacks
https://link.springer.com/chapter/10.1007/978-3-031-30634-1_5
MIT License
8 stars 1 forks source link

question #14

Closed lz233149 closed 4 days ago

lz233149 commented 1 week ago

Dear Professor. Thanks for your last reply, I solved the problem about the offset parameter, now I ran the results of a 19 rounds of craft's related-tweak's impossible differential attack with the following command:-Rb 4 -R1 5 -R2 5 -Rf 5 -of 0. The pdf of the related results is as follows, may I ask at the end of the graph of the differentiator, Why are there some completely blank matrices, may I ask how this problem can be solved?

Looking forward to your reply!

image

hadipourh commented 1 week ago

Thank you so much for your feedback! There was a small bug in the tool for related-tweak id attack that I resolved: https://github.com/hadipourh/zero/commit/88411ebf514ddf3c9110134c10a50456b434905c It should work properly now. The output looks like the following shape. Hope that it helps. Please let me know if you have any questions. image

lz233149 commented 6 days ago

Dear Professor, thank you for the modification that helped me with my last confusion, also, I have been trying to use your code to find longer differentiators, or better attacks, but I feel that running the iddist.py code alone might still have bugs.

For example, still using the previous 19 rounds of attacks as an example, the command to run is :-Rb 4 -R1 5 -R2 5 -Rf 5 -of 0. Getting the full attack pdf as shown before. There's nothing wrong with that. However, if I run the iddist.py code with the following command:python iddist.py -R1 5 -R2 5 -of 0,I get the distinguisher result as below, why do I feel that this result doesn't match with the distinguisher in the full attack pdf, and there will be some blank ATK matrices in the graph, I'm a bit confused, maybe you can give me help.

Looking forward to your reply! image

hadipourh commented 6 days ago

Thank you for your feedback!

The iddist.py script does not contain a bug. If it returns a single-tweak distinguisher, this is simply because the output is one of many possible solutions. Note that the solution is not unique; there may be multiple distinguishers of the same length (e.g., 10 rounds in your example): some are single-tweak and some others related-tweak. The solver just returns a solution.

In other words, iddist.py in the folder for related-tweak is capable of finding related-tweak distinguishers. However, this does not mean it will always return a related-tweak distinguisher; it may also return a single-tweak distinguisher.

If you prefer, you can enforce the model to find related-tweak distinguishers by limiting the tweak difference to non-zero values within the model. The variable for difference pattern in my model for craft is array[0..3, 0..15] of var 0..3: at;You can enforce the sum of at to be non-zero. Then it always returns a related-tweak distinguisher. However, I do not recommend it. Because, it is better to leave the solver's decision. In the current model, if the solver figures out that a related-tweak distinguisher works better for key recovery, it returns a related-tweak one.

lz233149 commented 5 days ago

Dear Professor, thanks for the reminder, based on your comment I added a constraint line in the code: constraint sum(i in 0..3, j in 0..15)(at[i, j]) != 0. Regardless of whether it helps the key recovery attack or not, after the modification, I reran the code with the following command: python iddist.py -R1 6 -R2 5 -of 1. The pdf file that I got is shown below, and to my relief it returned the related-tweak differentiator, but I manually verified the differentiator and found that it was missing ANY differences (in blue), such as the Y4, Y6, Y8, Y10 matrices, etc., which results in a mismatch between the before and after attack process, I don't know why this is, I just added a line of constraints as you said, I hope you can help me with this, thanks.

Looking forward to your reply!

image

hadipourh commented 5 days ago

Thanks for your feedback! I checked the model. The model is correct. However, there was a small bug in the shape generator: https://github.com/hadipourh/zero/commit/5a3f3a76755b6580894dc8762e66b97a2e8cf9d1 I fixed it. You can try again.

lz233149 commented 4 days ago

Dear Professor, Thank you for helping me with my last question, I appreciate it very much. Now my goal is to use the 12 rounds of differentiator to do the 19 rounds of related-tweak impossible differential attack, so I ran the command: -Rb 3 -R1 6 -R2 6 -Rf 4 -of 2, and the final pdf produced is as follows, and I don't quite understand the meaning of this result, did it fail or is it just the same as the last differentiator i.e., it returned the single-tweak result because its ATK matrix is blank.

Looking forward to your reply! image

hadipourh commented 4 days ago

The tool identifies that, in this case, a single-tweak attack is more effective than a related-tweak attack. Note that, related-tweak is not always better than single-tweak. It depends on the design.

lz233149 commented 4 days ago

Dear Professor, thanks for your reply, I see what you mean. But just now, I found a new problem, for different solvers (gurobi and ortools), they both run the same command: python iddist.py -R1 6 -R2 5 -of 0. Why do they get different results (the two graphs below correspond to gurobi and ortools)? Why is this and which one is correct? I hope you can answer.

Looking forward to your reply! image image

hadipourh commented 4 days ago

No problem! Different solvers may yield different solutions for the same problem, as many problems can have multiple valid solutions. Even running the same solver multiple times can result in different solutions, yet all are correct. When you include an objective function, the solver selects the solutions that best optimize this objective. By the way, if you use our tool in your project, we would be happy if you cite our paper.

lz233149 commented 4 days ago

Dear Professor, thank you for your reply. But for the idkr.py file, two different solvers seem to produce the same result, the reason why I run the iddist.py code, my purpose is to confirm which is the corresponding distinguisher in the full key recovery attack, for example, if I run the command: python idkr.py -Rb 4 -R1 6 -R2 5 -Rf 5 -of 0, I get the full attack as follows, so I want to run the iddist.py code to determine which of the 11 rounds of differentiators, but according to you, there are many possibilities for the result, so how should I determine which result is the differentiator used in the complete key recovery attack? I hope you can clear up the confusion.

Of course, I am researching for the creation of my thesis, and it would be an honour to cite your paper and ask you questions!

Looking forward to your reply! image

hadipourh commented 4 days ago

The process of searching for a distinguisher is entirely different. When searching for a key recovery attack, the tool optimizes the distinguisher specifically for key recovery purposes. However, when searching solely for a distinguisher, the tool returns a distinguisher (solution) without regard to where or how you intend to use it. Please refer to the paper for more details. Thanks for your understanding!