Ask Your Question
3

HUGE delay in sage.crypto.sbox.SBox method nonlinearity() introduced in v.8.2

asked 2018-06-04 05:23:32 -0600

sageuser1 gravatar image

updated 2018-06-05 00:39:27 -0600

Average time in nonlinearity() in v.8.1. was *200 ms Average time in nonlinearity() in v.8.2 is 5.1 s*

Here is the code I have used in order to track the issue:

sage: for j in range(10):
....:     S = [x for x in range(256)];shuffle(S)
....:     S = sage.crypto.sbox.SBox(S)
....:     %time S.nonlinearity()

Results from Sage 8.1

CPU times: user 237 ms, sys: 1.87 ms, total: 239 ms
Wall time: 236 ms
94
CPU times: user 208 ms, sys: 12.5 ms, total: 220 ms
Wall time: 220 ms
94
CPU times: user 287 ms, sys: 1.41 ms, total: 288 ms
Wall time: 288 ms
92
....

Results from Sage 8.2

CPU times: user 5.12 s, sys: 30.6 ms, total: 5.15 s
Wall time: 5.16 s
92
CPU times: user 5.04 s, sys: 14.3 ms, total: 5.05 s
Wall time: 5.05 s
96
CPU times: user 5.08 s, sys: 13 ms, total: 5.09 s
Wall time: 5.09 s
94
CPU times: user 5.03 s, sys: 8.56 ms, total: 5.04 s
Wall time: 5.04 s
92
.....
edit retag flag offensive close merge delete

Comments

Please provide the code that exhibits the slowdown. The next step will be to run with profiling to see if any changes stick out.

nbruin gravatar imagenbruin ( 2018-06-04 10:44:17 -0600 )edit

I have updated the post with the code I have used to profile the slowdown.

sageuser1 gravatar imagesageuser1 ( 2018-06-05 00:40:20 -0600 )edit

2 answers

Sort by ยป oldest newest most voted
2

answered 2018-06-05 01:58:04 -0600

nbruin gravatar image

Thank you for reporting this. It looks like a rather severe regression. With

S = [x for x in range(256)];shuffle(S)
S = sage.crypto.sbox.SBox(S)
%prun -s cumtime S.nonlinearity()

on 8.1 and 8.2+ you can see that the call graph has changed significantly. Recent changes on sbox have been made by Friedrich Wiemer. You should file a trac ticket and CC him on it. He would likely have a good idea what the cause of the slowdown is and if it can be fixed.

edit flag offensive delete link more

Comments

Samuel informed me, I'll take a look into this.

asante gravatar imageasante ( 2018-06-06 02:53:27 -0600 )edit

Please update us with the final resolution. Beside that, don't you think that the time needed (200 ms) for finding nonlinearity() of one vectorial boolean function (8 x 8) in SageMath 8.1 is too much, too?

sageuser1 gravatar imagesageuser1 ( 2018-06-06 07:16:11 -0600 )edit

@sageuser1 yes that may well be the case. If I find some spare time, I'll try to investigate if this could be improved.

asante gravatar imageasante ( 2018-06-08 13:07:17 -0600 )edit

@sageuser1 I finally had some spare time and checked the timings of a simple c implementation to compute the LAT (which is the main time consuming part for computing the nonlinearity). I guess the Sage implementation can definitely be improved. I opened a ticket for it, https://trac.sagemath.org/ticket/25633 and will work on it at the upcoming SageDays.

asante gravatar imageasante ( 2018-06-21 12:47:13 -0600 )edit

@asante Thank you for your update!

sageuser1 gravatar imagesageuser1 ( 2018-06-26 00:32:49 -0600 )edit
3

answered 2018-06-07 10:42:11 -0600

asante gravatar image

I've opened the following ticket: https://trac.sagemath.org/ticket/25516 The regression was indeed introduced by recent changes to the SBox module and should be fixed with the above patch.

Thanks for reporting this!

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-06-04 05:23:32 -0600

Seen: 184 times

Last updated: Jun 07