#25516 closed defect (fixed)

Huge delay introduced in SBox nonlinearity

Reported by: asante Owned by: asante
Priority: major Milestone: sage-8.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+

Quoted from https://ask.sagemath.org/question/42492/huge-delay-in-sagecryptosboxsbox-method-nonlinearity-introduced-in-v82/

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 asante

  • Owner changed from (none) to asante

comment:2 Changed 18 months ago by asante

  • Branch set to u/asante/huge_delay_introduced_in_sbox_nonlinearity

comment:3 Changed 18 months ago by asante

  • Commit set to 2817d9081f84f8ff403e0c6e1a1ab04cdf24f966
  • Status changed from new to needs_review

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:

2817d90Fix delay introduced in the computation of walsh hadamard transform

comment:4 Changed 18 months ago by ylchapuy

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 git

  • Commit changed from 2817d9081f84f8ff403e0c6e1a1ab04cdf24f966 to 96eafe481afe0195285d66bce90f911812aaa537

Branch pushed to git repo; I updated commit sha1. New commits:

96eafe4Merge branch 'develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity

comment:6 Changed 18 months ago by asante

  • Keywords days94 added

comment:7 Changed 18 months ago by git

  • Commit changed from 96eafe481afe0195285d66bce90f911812aaa537 to e16a34261303fd6a1bb21e2e5fe37149f26fb659

Branch pushed to git repo; I updated commit sha1. New commits:

e16a342Merge remote-tracking branch 'origin/develop' into t/25516/huge_delay_introduced_in_sbox_nonlinearity

comment:8 Changed 18 months ago by ruhm

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 ruhm

  • Reviewers set to Rusydi H. Makarim
  • Status changed from needs_review to needs_work

comment:10 Changed 18 months ago by ruhm

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 little-endian ordering (i.e., the leftmost bit in a list/tuple/vector is the least-significant bit).

comment:11 Changed 18 months ago by git

  • Commit changed from e16a34261303fd6a1bb21e2e5fe37149f26fb659 to 383b74a38f24b51de9dee4f086d68ea251f2ce69

Branch pushed to git repo; I updated commit sha1. New commits:

383b74aImprove speed of component_function to fix delay in walsh_hadamard_transform

comment:12 Changed 18 months ago by asante

  • 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 know-corrected input checks?

comment:13 Changed 17 months ago by asante

  • Status changed from needs_review to needs_work

patchbot tests are failing

comment:14 Changed 17 months ago by git

  • Commit changed from 383b74a38f24b51de9dee4f086d68ea251f2ce69 to edab1bc02da7e9145248e2e346063bb988dfefab

Branch pushed to git repo; I updated commit sha1. New commits:

edab1bclook at .popcount % 2

comment:15 Changed 17 months ago by git

  • Commit changed from edab1bc02da7e9145248e2e346063bb988dfefab to a3b8c87756a5f0418d53fefe1ae3fd5d561dab0c

Branch pushed to git repo; I updated commit sha1. New commits:

a3b8c87merge develop

comment:16 Changed 17 months ago by asante

  • Status changed from needs_work to needs_review

comment:17 Changed 17 months ago by tscrim

FYI - All tests pass (the one failure from the patchbot is independent and transient).

comment:18 Changed 17 months ago by soehms

  • Reviewers changed from Rusydi H. Makarim to Rusydi H. Makarim, Sebastian Oehms

comment:19 Changed 17 months ago by soehms

  • Status changed from needs_review to positive_review

LGTM

comment:20 Changed 17 months ago by vbraun

  • Branch changed from u/asante/huge_delay_introduced_in_sbox_nonlinearity to a3b8c87756a5f0418d53fefe1ae3fd5d561dab0c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.