Opened 4 years ago
Closed 3 years ago
#22453 closed defect (fixed)
A mistake in the mq.Sbox.polynomials
Reported by:  thecow  Owned by:  asante 

Priority:  major  Milestone:  sage8.3 
Component:  cryptography  Keywords:  sbox, cryptography, rank, days94 
Cc:  Merged in:  
Authors:  Friedrich Wiemer  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  d74a8da (Commits, GitHub, GitLab)  Commit:  d74a8da6b08053115bf0a5fbe37ed8ae47a09097 
Dependencies:  Stopgaps: 
Description (last modified by )
There is a mistake in gens = (RR.column(ncols1)[1<<m:]).list()
string. The rank of the system may be less than 2^{m.
}
In that case this function doesn’t return any polynom. AES sbox has a lot of polynoms with degree=2 satisfying.
This is the minimal code to verify it. There should be much more than one polynomials (see http://link.springer.com/chapter/10.1007/3540361782_17 for example).
sage: S = mq.SBox([99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22]) sage: S.polynomials() []
Change History (14)
comment:1 followup: ↓ 3 Changed 4 years ago by
 Description modified (diff)
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 in reply to: ↑ 1 Changed 4 years ago by
comment:4 Changed 4 years ago by
 Description modified (diff)
comment:5 Changed 4 years ago by
 Branch set to u/thecow/a_mistake_in_the_mq_sbox_polynomials
comment:6 Changed 3 years ago by
 Branch changed from u/thecow/a_mistake_in_the_mq_sbox_polynomials to u/asante/a_mistake_in_the_mq_sbox_polynomials
comment:7 Changed 3 years ago by
 Commit set to 06ac820697f69cbf9eef041b1170a44651868e4f
Branch pushed to git repo; I updated commit sha1. New commits:
06ac820  add test for method if bug is fixed

comment:8 Changed 3 years ago by
 Description modified (diff)
 Keywords sbox days94 added; box removed
 Milestone changed from sage7.6 to sage8.3
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to defect
The fix that was already included in the old branch was to change the computation of the spanning set, i.e.
rankSize = A.rank()  1 [...] # extract spanning stet gens = (RR.column(ncols1)[rankSize:]).list()
before, it was gens = (RR.column(ncols1)[1<<m:]).list()
.
comment:9 Changed 3 years ago by
 Owner changed from (none) to asante
comment:10 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
Some little things with the formatting:
TESTS: Check that :trac:`22453` is fixed:: sage: from sage.crypto.sboxes import AES sage: aes_polys = AES.polynomials() sage: p = aes_polys[0].parent("x3*y0 + x5*y0 + x7*y0 + x6*y1 + x2*y2" ....: " + x3*y2 + x4*y2 + x2*y3 + x3*y3 +" ....: " x5*y4 + x6*y4 + x3*y5 + x4*y5 + x4*y7" ....: " + x2 + x3 + y2 + y3 + y4 + 1") sage: p in aes_polys
Otherwise LGTM.
comment:11 Changed 3 years ago by
 Commit changed from 06ac820697f69cbf9eef041b1170a44651868e4f to d1ef281a7735862009f6834faa11bd0d5443fea0
Branch pushed to git repo; I updated commit sha1. New commits:
d1ef281  reformatted the tests

comment:12 Changed 3 years ago by
 Commit changed from d1ef281a7735862009f6834faa11bd0d5443fea0 to d74a8da6b08053115bf0a5fbe37ed8ae47a09097
Branch pushed to git repo; I updated commit sha1. New commits:
d74a8da  Merge remotetracking branch 'origin/develop' into t/22453/a_mistake_in_the_mq_sbox_polynomials

comment:13 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 3 years ago by
 Branch changed from u/asante/a_mistake_in_the_mq_sbox_polynomials to d74a8da6b08053115bf0a5fbe37ed8ae47a09097
 Resolution set to fixed
 Status changed from positive_review to closed
There is a file that works well: https://github.com/alexkorovkov/sage/blob/master/src/sage/crypto/mq/sbox.py