Opened 18 months ago
Closed 17 months ago
#25516 closed defect (fixed)
Huge delay introduced in SBox nonlinearity
Reported by:  asante  Owned by:  asante 

Priority:  major  Milestone:  sage8.3 
Component:  cryptography  Keywords:  sbox, linear approximation matrix, regression, days94 
Cc:  Merged in:  
Authors:  Friedrich Wiemer  Reviewers:  Rusydi H. Makarim, Sebastian Oehms 
Report Upstream:  N/A  Work issues:  
Branch:  a3b8c87 (Commits)  Commit:  a3b8c87756a5f0418d53fefe1ae3fd5d561dab0c 
Dependencies:  Stopgaps: 
Description
There is a regression in the computation of the nonlinearity of an SBox introduced from 8.1 to 8.2+
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 .....
I expect the cause being the modification of the linear_approximation_matrix
Method, i.e. the following diff
 B = BooleanFunction(self.m)  L = []  for j in range(ncols):  for i in range(nrows):  B[i] = ZZ(self(i)&j).popcount()  L.append(B.walsh_hadamard_transform()) + L = [self.component_function(i).walsh_hadamard_transform() for i in range(ncols)]
Change History (20)
comment:1 Changed 18 months ago by
 Owner changed from (none) to asante
comment:2 Changed 18 months ago by
 Branch set to u/asante/huge_delay_introduced_in_sbox_nonlinearity
comment:3 Changed 18 months ago by
 Commit set to 2817d9081f84f8ff403e0c6e1a1ab04cdf24f966
 Status changed from new to needs_review
comment:4 Changed 18 months ago by
You should probably also fix component_function
for speed (by using the popcount trick).
It might be in another ticket though.
comment:5 Changed 18 months ago by
 Commit changed from 2817d9081f84f8ff403e0c6e1a1ab04cdf24f966 to 96eafe481afe0195285d66bce90f911812aaa537
Branch pushed to git repo; I updated commit sha1. New commits:
96eafe4  Merge branch 'develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity

comment:6 Changed 18 months ago by
 Keywords days94 added
comment:7 Changed 18 months ago by
 Commit changed from 96eafe481afe0195285d66bce90f911812aaa537 to e16a34261303fd6a1bb21e2e5fe37149f26fb659
Branch pushed to git repo; I updated commit sha1. New commits:
e16a342  Merge remotetracking branch 'origin/develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity

comment:8 Changed 18 months ago by
Hi Friedrich,
I have tested the patch and it fixes the problem and pass the doctests. However, I suggest the fix for this ticket should actually be done on the component_function
. The value b
in the component_function
is kept as an integer. The Boolean function for the component function can be computed as
ret[x] = ZZ(b & self(x)).popcount() & 1
comment:9 Changed 18 months ago by
 Reviewers set to Rusydi H. Makarim
 Status changed from needs_review to needs_work
comment:10 Changed 18 months ago by
Additional notes : when converting b
in component_function
from a list/tuple of bits to integer, you may use self.from_bits()
inside the SBox module since it takes care of the "endianness". By default SageMath use littleendian ordering (i.e., the leftmost bit in a list/tuple/vector is the leastsignificant bit).
comment:11 Changed 18 months ago by
 Commit changed from e16a34261303fd6a1bb21e2e5fe37149f26fb659 to 383b74a38f24b51de9dee4f086d68ea251f2ce69
Branch pushed to git repo; I updated commit sha1. New commits:
383b74a  Improve speed of component_function to fix delay in walsh_hadamard_transform

comment:12 Changed 18 months ago by
 Status changed from needs_work to needs_review
Fixed the slow implementation of component_function
, now the walsh_hadamard_transform
can stay as it was without speed penalty. There is still some small decrease in speed, I guess because of the knowcorrected input checks?
comment:13 Changed 17 months ago by
 Status changed from needs_review to needs_work
patchbot tests are failing
comment:14 Changed 17 months ago by
 Commit changed from 383b74a38f24b51de9dee4f086d68ea251f2ce69 to edab1bc02da7e9145248e2e346063bb988dfefab
Branch pushed to git repo; I updated commit sha1. New commits:
edab1bc  look at .popcount % 2

comment:15 Changed 17 months ago by
 Commit changed from edab1bc02da7e9145248e2e346063bb988dfefab to a3b8c87756a5f0418d53fefe1ae3fd5d561dab0c
Branch pushed to git repo; I updated commit sha1. New commits:
a3b8c87  merge develop

comment:16 Changed 17 months ago by
 Status changed from needs_work to needs_review
comment:17 Changed 17 months ago by
FYI  All tests pass (the one failure from the patchbot is independent and transient).
comment:18 Changed 17 months ago by
 Reviewers changed from Rusydi H. Makarim to Rusydi H. Makarim, Sebastian Oehms
comment:20 Changed 17 months ago by
 Branch changed from u/asante/huge_delay_introduced_in_sbox_nonlinearity to a3b8c87756a5f0418d53fefe1ae3fd5d561dab0c
 Resolution set to fixed
 Status changed from positive_review to closed
The cause is as expected the use of the
component_function
method of the sbox. Reverting to the previous implementation restores the old speed.New commits:
Fix delay introduced in the computation of walsh hadamard transform