Score:2

Linearization attack on group with automorphism

vu flag

Recently, I've had an exchange with Lorenz Panny about Xifrat. He says, that the quasigroup that I use can be linearized and then attacked, and he provided a script that linearized the quasigroup. His result is as follow:

f:
2 0 4 3 5 7 1 6
1 5 3 4 0 6 2 7
7 4 0 5 3 2 6 1
0 2 7 6 1 4 5 3
3 6 1 2 7 5 4 0
6 3 5 0 4 1 7 2
4 7 2 1 6 0 3 5
5 1 6 7 2 3 0 4

g:
2 5 0 6 7 1 3 4
5 2 1 4 3 0 7 6
0 1 2 3 4 5 6 7
6 4 3 2 1 7 0 5
7 3 4 1 2 6 5 0
1 0 5 7 6 2 4 3
3 7 6 0 5 4 2 1
4 6 7 5 0 3 1 2

A: 7 6 2 4 5 1 0 3
B: 4 7 2 1 6 0 3 5
c: 0

where $f$ is my quasigroup, $g$ is the linearized group, $f(x,y)$ can be evaluated as $Ax+By+c$ where $+$ is the group operation, $A$ and $B$ are 2 independent automorphisms.

A question I have on my mind is: How does a linearization attack apply to a group with automorphisms?

I'd like to see a practical example of such attack, so let's suppose we built a 64-bit block and key toy blockcipher entirely out of the quasigroup operation, and how a linearization attack might apply to the blockcipher.

Score:0
vu flag

For the public record, I'm posting this exchange a group of us had last year, where Lorenz said (quotes' his, others' my comments that're new and original to this post):

Now the crucial thing to notice is that in the end, combining many of these quasigroup operations in an arbitrary way will just end up being a sum (with respect to the new group law + recovered in the script) of the input elements twisted by compositions of A,B in various ways,

That's what basically any such entropic quasigroups boils down to - groups with independent automorphisms.

so we can linearize the group + by computing some discrete logarithms, then simply solve a linear-algebra problem to recover the secret-key operation.

Now, one thing to know is that, the composition of automorphism forms group, what Lorenz mean by here would be that, represent the automorphisms in a form that can be solved using some some algorithm for linear-algebra.

This had been the focus of some follow up discussion within the group, where another participant - Danilo Gligoroski - questioned emphasizing:

abstract existence does not imply we can also construct something efficiently.

Another thing is that, the group of automorphism composition and the group of linearized quasigroup do not form field, so the best currently known Gaussian elimination will not be capable of solving it even when it's formed.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.