Graham Sutherland / Polynomial
Contacting Graham Sutherland / Polynomial
Federation handle:
@gsuberland@chaos.social
Graham Sutherland / Polynomial's Information
Graham Sutherland / Polynomial's Bio
he\him
Into electronics, windows internals, cryptography, security, compute hardware, physics, colourimetry, lasers, stage lighting, D&B, DJing, demoscene, socialism.
Currently looking for infosec work. See pinned post for details.
I am mothman.
Heavily ADHD.
Nullsector/laser team @ EMF Camp, lasers & lighting orga @ NOVA Demoparty.
I sell funny warning stickers at Unsafe Warnings: https://unsafewarnings.etsy.com
All posts encrypted with ROT256-ECB.
Header photo by @jtruk
Graham Sutherland / Polynomial's Posts
Graham Sutherland / Polynomial has 422 posts.
Graham Sutherland / Polynomial
In response to this post@ailurux "the packages are a bit late, the only explanation must be an evil conspiracy by the tangara people, there's just no way that a shipping company would be bad at their job!" sure is one of the takes of all time
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
tired: bliss.jpg
wired: galois fields
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@dysfun there's probably some fancy shit you can do with it (I'd bet there's cleverness you can do with things like upper/lower parity, alternating bit parity, etc. for further bit re-ordering shenanigans) but I've got a pretty hefty knowledge gap there.
ultimately if you can express existing bit twiddle tricks as matrix multiplications mod 2 with an optional xor on the end, then it'll do the job in a single instruction. it just happens to reduce to a parity calc due to the vector product step.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@schrottkatze ah it's using EtherDream's custom protocol
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@dysfun by setting b to all ones you can invert the parity in the same computation, too, if that turns out to be useful somehow.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@dysfun by setting the vector to zero the output will be parity(A*x), meaning you can compute the parity of any subset of bits you like in a given byte by setting or clearing bits in the row of A. and of course it works with any permutation of bits in A, so you can calculate the bytewise parities of any chosen subset of bits in a 128-bit vector.
if you wanted the overall parity you could then take the output and feed it back in with A set to all ones and finally POPCNT the resulting 16-bit word
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@dysfun the matrix-vector multiply is:
b[0]*A[0,0]+b[1]*A[0,1]+...+b[7]*A[0,7]
b[0]*A[1,0]+b[1]*A[1,1]+...+b[7]*A[1,7]
...
b[0]*A[7,0]+b[1]*A[7,1]+...+b[7]*A[7,7]
but since this is operating in GF(2) every element is 0 or 1 (a single bit) so a multiply by 0 is 0 and only 1*1 gets you a 1, thus each multiply is just and AND, and the sum is mod 2 so it turns into a parity calculation.
addition is xor so the vector addition is simply a 1-bit xor.
and that's basically it.
as for bit twiddles...
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@dysfun the instruction is doing the affine transformation step on the right hand page of my notes - the big matrix multiplication followed by vector addition step, mod 2.
Intel call it A*x+b, so A would be the 8x8 matrix, x is the input vector (b'[0-7] in my notes), b is the added vector (11000110 in AES).
it's mod 2 so the vector addition is just xor.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@schrottkatze it's the standard for laser projector imaging. covers both a file format (containing vector frame data for displaying on a laser projector) and a physical interface standard (differential signalling over DB25 connector) for laser projectors.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
In response to this post@schrottkatze ILDA output? :)
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
I'm up to 9 pages of notes on Galois field maths and the construction and properties of AES, based on Christof Paar's lectures.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
it's been forever since I made hand written notes. my knuckles hurt (arthritic joint condition and being left handed kinda sucks lol) but I'm quite happy with these.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@r they had been teaching it very much as "it's how you determine the slope of the graph" without any applied context and I just couldn't fathom why you would want to know what the gradient was on a graph at a particular x coordinate, let alone why you'd want to find the coordinate where a particular gradient was found, especially given how involved and unintuitive the procedures to do so could be. naturally once I could map it to a physics context it was trivial to understand why the use-case.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@r I'm also a visual learner. I can't do abstract concepts; I need a concrete example and application. I spent the first 75% of calculus at school being unable to grok it at all, blindly following rules and procedures by rote, until my physics teacher happened to put the equations of motion on the board in a certain order and suddenly it clicked that they were derivatives of one another, and that calculus was about modelling dependent behaviours like rates of change, and then I understood fine.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@r part of the problem I've found is that most of the lectures on the subject are being delivered to students who have been studying number theory and related topics as part of a dedicated mathematics module, so there's an expectation of comfort and recent familiarity with the underlying mathematical concepts, which I lack. I couldn't have really told you what a group, ring, or field was before the lecture, for example. my algebra is mostly only exercised for electronics.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
re: spoiler/help
@r because I haven't done polynomial division in years and can't remember the procedure at all. I think I had maybe two hours worth of tutoring on it back in 2005 or 2006. I remember being taught trial division at some point for factorisation, so that's the mental model I applied to understanding the approach here. wasn't until I had some time to percolate on it that I realised there was a rigorous procedure being followed rather than trialling based on elimination convenience.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
@r the direct focus on the procedure and minimal formalism with no expectations of knowing much beyond simple algebra (e.g. explaining the definitions of group, ring, field in basic terms) is the key here. any less focus on the implementation and examples would have been insufficient here; it's really not an accessible topic otherwise.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
spoiler/help
the reason xor is used here is because addition, subtraction, and xor are all the same operation in GF(2), so the c^=p' line does the addition step he showed in the example.
I'm not 100% sure the above is correct for all cases, but it does at least follow the same approach - sh represents the index you raise x to for each trial division step, so if you have x^4 as your highest index term in C' and x^3 as your highest index term in P, then you're going to trial divide by x^1, i.e. x.
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
In response to this postspoiler/help
I think if you do the polynomial product A(x)∙B(x) to get C'(x), then interpret the coefficients of C'(x) and P(x) as bit vectors, you can do the modulo reduction as follows:
```
c = c'
while c >= 2^3:
sh = msb(c)-msb(p)
p' = p<<sh
c ^= p'
```
where msb() returns the index of the MSB.
so in his example of C'(x)=x^4+x^3+x+1 and P(x)=x^3+x+1, the steps are:
p=1011 (x^3+x+1)
c'=11011 (x^4+x^3+x+1)
c=11011
c>=2^3
sh=1
p'=10110
c=1101
c>=2^3
sh=0
p'=1011
c=110
c<2^3
thus, c=x^2+x
Likes: 0
Replies: 0
Boosts: 0
Graham Sutherland / Polynomial
spoiler/help
the trickiest part for me was the polynomial reduction at the end.
if you get stuck there too: since the coeffs are mod 2 you just cancel out matching terms. he first trialled x as the divisor, getting us P*x so that the x^3 term in P would become x^4 and cancel out the x^4 term in C'. the result of this trial still had an x^3 term, so still not in GF(2^3), so he trialled x+1 as the divisor. he could test this by dividing the first trial result by P and that gave a result in GF(2^3)
spoiler/help
I think if you do the polynomial product A(x)∙B(x) to get C'(x), then interpret the coefficients of C'(x) and P(x) as bit vectors, you can do the modulo reduction as follows:
```
c = c'
while c >= 2^3:
sh = msb(c)-msb(p)
p' = p<<sh
c ^= p'
```
where msb() returns the index of the MSB.
so in his example of C'(x)=x^4+x^3+x+1 and P(x)=x^3+x+1, the steps are:
p=1011 (x^3+x+1)
c'=11011 (x^4+x^3+x+1)
c=11011
c>=2^3
sh=1
p'=10110
c=1101
c>=2^3
sh=0
p'=1011
c=110
c<2^3
thus, c=x^2+x
by Graham Sutherland / Polynomial ;
Likes: 0
Replies: 1
Boosts: 0