Field Trace function crash on specific irreducible polynomial

[geostergiop]

Hi again Matt,

So, this time there is another weird issue. After running trace on elements from dozens of irr. polynomials, I came across an irr. polynomial that seems able to crash the library although galois seems to work fine with the rest of them (!).
In:

poly = galois.Poly.Degrees([256, 6, 3, 1, 0])
galois.is_irreducible(poly)  
GF = galois.GF((2**256), irreducible_poly=poly, primitive_element=2, verify=False)`

Out:

GF(2^256):
  characteristic: 2
  degree: 256
  order: 115792089237316195423570985008687907853269984665640564039457584007913129639936
  irreducible_poly: x^256 + x^6 + x^3 + x + 1
  is_primitive_poly: True
  primitive_element: x

And when I feed the following element x = GF(α^255 + α^254 + α^250 + α^249 + α^242 + α^238 + α^237 + α^236 + α^235 + α^234 + α^233 + α^232 + α^231 + α^228 + α^226 + α^222 + α^216 + α^215 + α^214 + α^213 + α^211 + α^210 + α^208 + α^206 + α^205 + α^204 + α^203 + α^202 + α^200 + α^198 + α^197 + α^195 + α^194 + α^192 + α^189 + α^188 + α^182 + α^178 + α^176 + α^174 + α^166 + α^165 + α^163 + α^162 + α^161 + α^159 + α^156 + α^154 + α^152 + α^151 + α^150 + α^142 + α^141 + α^140 + α^139 + α^138 + α^135 + α^134 + α^132 + α^131 + α^126 + α^124 + α^123 + α^122 + α^118 + α^117 + α^116 + α^114 + α^113 + α^112 + α^111 + α^107 + α^106 + α^105 + α^102 + α^99 + α^97 + α^96 + α^95 + α^91 + α^90 + α^87 + α^86 + α^85 + α^83 + α^82 + α^81 + α^80 + α^77 + α^76 + α^75 + α^74 + α^71 + α^69 + α^66 + α^65 + α^64 + α^63 + α^61 + α^59 + α^57 + α^56 + α^55 + α^53 + α^51 + α^50 + α^43 + α^40 + α^39 + α^37 + α^36 + α^35 + α^32 + α^30 + α^28 + α^27 + α^26 + α^22 + α^21 + α^20 + α^15 + α^12 + α^11 + α^10 + α^9 + α^7 + α^6 + α^5 + α^2 + 1, order=2^256) it throws an error during x.field_trace():

****************** Starting execution... ******************
Traceback (most recent call last):
  File "loop_rev.py", line 332, in <module>
    result = looptest(priv, GF)
  File "loop_rev.py", line 255, in looptest
    tr1 = x.field_trace() # f_trace(x, gf_p)  (f_trace(x), f_trace(y))
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 809, in field_trace
    return subfield(trace)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 118, in __new__
    return cls._array(array, dtype=dtype, copy=copy, order=order, ndmin=ndmin)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 173, in _array
    array_like = cls._check_array_like_object(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 200, in _check_array_like_object
    cls._check_array_values(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 259, in _check_array_values
    raise ValueError(f"{cls.name} arrays must have elements in `0 <= x < {cls.order}`, not {values}.")
ValueError: GF(2) arrays must have elements in `0 <= x < 2`, not 108935003246320077271910298639875189614369932296706429304701758788567068285781.

I tested multiple elements with this polynomial and all seem to crash.

I promise I won't find anything weird-er until 2022 :-)

[geostergiop]

I think I found a second one: [256, 42, 3, 1, 0]. This too broke for element 40959117867387407762835010102124901456272111140381905491657637690235696092387 (decimal).

[mhostetter]

Hey George,

In both cases, the "irreducible" polynomial is actually not irreducible over GF(2). The galois.GF() class factory would have warned you about this, but we have verify=False due to the issue in #187.

A reducible polynomial can be passed to galois.GF() without error due to verify=False. However, the "field" that is created from such a reducible polynomial is actually not a field. Because of that the field trace operation doesn't correctly produce a value in GF(2).

I believe this is an expected result. Do you agree?

In [14]: poly = galois.Poly.Degrees([256, 6, 3, 1, 0])

In [15]: poly
Out[15]: Poly(x^256 + x^6 + x^3 + x + 1, GF(2))

In [16]: galois.is_irreducible(poly)
Out[16]: False

In [17]: galois.factors(poly)
# Still running on my PC... will update with result when done

In [10]: poly = galois.Poly.Degrees([256, 42, 3, 1, 0])

In [11]: poly
Out[11]: Poly(x^256 + x^42 + x^3 + x + 1, GF(2))

In [12]: galois.is_irreducible(poly)
Out[12]: False

# Factored quickly
In [13]: galois.factors(poly)
Out[13]: 
([Poly(x^3 + x^2 + 1, GF(2)),
  Poly(x^7 + x^6 + x^5 + x^2 + 1, GF(2)),
  Poly(x^113 + x^112 + x^111 + x^109 + x^107 + x^106 + x^104 + x^103 + x^102 + x^101 + x^99 + x^97 + x^96 + x^95 + x^91 + x^90 + x^89 + x^87 + x^86 + x^82 + x^76 + x^74 + x^72 + x^70 + x^68 + x^66 + x^65 + x^62 + x^61 + x^59 + x^57 + x^53 + x^51 + x^49 + x^48 + x^44 + x^43 + x^40 + x^39 + x^37 + x^36 + x^35 + x^32 + x^31 + x^28 + x^26 + x^19 + x^18 + x^17 + x^14 + x^10 + x^9 + x^8 + x^7 + x^4 + x^3 + 1, GF(2)),
  Poly(x^133 + x^132 + x^130 + x^129 + x^128 + x^126 + x^123 + x^121 + x^120 + x^116 + x^115 + x^111 + x^110 + x^107 + x^105 + x^103 + x^101 + x^100 + x^99 + x^96 + x^94 + x^92 + x^91 + x^90 + x^89 + x^88 + x^87 + x^85 + x^84 + x^83 + x^81 + x^80 + 
x^79 + x^78 + x^76 + x^75 + x^72 + x^71 + x^66 + x^64 + x^63 + x^61 + x^58 + x^57 + x^56 + x^55 + x^49 + x^48 + x^44 + x^43 + x^42 + x^41 + x^40 + x^37 + x^35 + x^34 + x^32 + x^31 + x^30 + x^29 + x^28 + x^25 + x^24 + x^23 + x^22 + x^21 + x^18 + x^17 + x^14 + x^10 + x^8 + x^7 + x^3 + x + 1, GF(2))],
 [1, 1, 1, 1])

[geostergiop]

Good morning Matt,

Ok, this is logical, only thing is that all used polynomials were auto-generated using the Galois library with the following snippet. My testbed contains thousands of correct polynomials provided by this script and (until now) I only found these two reducible ones written inside.

Thanks. Will cross-check the code again and let you know, seems to be a bug on my side, it's unnatural for the galois.is_irreducible(poly) to contain a bug that only showed twice in 10000 instances.

hs = open("polys256.txt","a", buffering=1)
for j in range(1,256):
    for k in range(1,255):
        for l in range(1,254):
            poly = galois.Poly.Degrees([256, j, k, l,0])
            if galois.is_irreducible(poly):
                print("Found one: ", poly)
                hs.write(poly.string + "\n")
print("Done")

[mhostetter]

That's truly perplexing!!

All the code inside is_irreducible() and your testbed is deterministic code. So I couldn't imagine how it'd return True one time but False another. If you run it manually like I did, does it return False for you?

Is there any chance it was copied from the file incorrectly? Or the file was accidentally modified?

The only other thing I could think of is some mismatch between the polynomial and poly.string. For instance, poly = galois.Poly.Degrees([256, j, k, l,0]) maybe doesn't have poly.string == "'x^256 + x^j + x^k + x^l + 1"?? However, I test for that, so I don't believe that's it...

I'm genuinely stumped.

[mhostetter]

@geostergiop can you provide me the section in the output file with 2 polys before x^256 + x^6 + x^3 + x + 1 and two polys after (5 polys total)?

Maybe I can rerun your script to find how / when the "bad" polynomial is produced and returned as True.

[geostergiop]

@geostergiop can you provide me the section in the output file with 2 polys before x^256 + x^6 + x^3 + x + 1 and two polys after (5 polys total)?

Maybe I can rerun your script to find how / when the "bad" polynomial is produced and returned as True.

Sorry for the late reply, I am out of office for the holidays. I am not sure if I have kept the original output due to data sanitization, but in any case the earliest output version I can find right now is the following (as per your request):

256, 155, 2, 1, 0
256, 209, 2, 1, 0
256, 239, 2, 1, 0
256, 06, 3, 1, 0
256, 24, 3, 1, 0
256, 27, 3, 1, 0
256, 36, 3, 1, 0
256, 96, 3, 1, 0
256, 042, 3, 1, 0
256, 077, 3, 1, 0
256, 202, 3, 1, 0
256, 204, 3, 1, 0

Although, again, I have to admit that I believe it is a bug on our side, it is way less probable than your library making 2 errors in 10,000.

Hope this helps, will check for bugs when I get back.

[geostergiop]

Update: Oldest output I found agrees with the one above. Didn't keep raw output before string manipulation so I can't be sure. Probably best to table this until any new instances come up.

[mhostetter]

I was testing with this... One thing I noticed is the script you're using will sometimes have j == k == l. And as I say in #218, this can produce a different polynomial than expected.

I modified the script to use select a unique combination of nonzero degrees between 1 and 255. That's what I'm testing with. I suspect the issue discovered here was from the bug in #218.

import itertools
import galois

for j, k, l in itertools.combinations(range(1, 256), 3):
    poly = galois.Poly.Degrees([256, j, k, l, 0])
    if galois.is_irreducible(poly):
        print("Found one: ", j, k, l, poly, poly.string)