# Nibelung (crypto, 525p, 22 solved)
A very interesting crypto challenge.We get [server code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-03-07-zer0ptsCTF/nibelung/server.py) and a [library](https://raw.githubusercontent.com/TFNS/writeups/master/2020-03-07-zer0ptsCTF/nibelung/fglg.py) presumably implementing a FiniteGeneralLinearGroup.It seems to provide a way to perform operations on Matrices mod p (default p is random 512 bit prime).
The server turns flag into a matrix, then generates a random matrix `U`, encrypts the flag and sends the encryption result to us.Encryption and decryption is:
```pythondef encrypt(U, X):    return U * X * U ** -1
def decrypt(U, X):    return U ** -1 * X * U```
The results of those operations are elements of `fglg` so matrices mod p.
The server allows us to encrypt and decrypt data at will, but there is a small twist -> we can only provide data using:
```pythondef bytes2gl(b, n, p=None):    assert len(b) <= n * n    X = FiniteGeneralLinearGroup(n, p)    padlen = n * n - len(b)    b = bytes([padlen]) * padlen + b    for i in range(n):        for j in range(n):            X.set_at((j, i), b[i*n + j])    return X
def recv_message(n, p):    print("Data: ", end="", flush=True)    b = base64.b64decode(input())    return bytes2gl(b, n, p)```
This means we can only encrypt or decrypt matrix with elements `0..255`, so we can't simply send the encrypted flag for decryption, because the matrix elements are much bigger than that.
The key observation here is to notice that the name of the library is a lie.While it claims to implement a `Group`, in reality what we get is a `Ring` instead.This is also suggested by the task name -> https://en.wikipedia.org/wiki/Der_Ring_des_Nibelungen
As everyone, I'm sure, remembers from Algebra a Group has only `additive` operation defined, while a Ring has also a `multiplicative` operation available.It's clearly the case here -> we can both add and multiply matrices provided by the library.
Going back to Algebra, we know that there are some properties which hold:
```(x+y)+z = x+(y+z)x*y = y*x(x+y)*z = x*z + y*z```
Those properties hold just as well with matrices we have.This means the encryption and decryption process is homomorphic, for example: `encrypt(A+B) == encrypt(A)+encrypt(B)`.
This means we can split the encrypted flag into parts, decrypt each one of them separately, and then combine them back! It's a classic example of `blinding attack`.
We don't even have to work with whole matrix, we can focus on single cell!Notice that:
```[A B] = [A 0] + [0 B] + [0 0] + [0 0] [C D]   [0 0]   [0 0]   [C 0]   [0 D]```
In order to get decrypted value for element `A` we need to perform two decryptions, one for `255` and another for `A%255`.Once we do that we can simply do `dec_matrix(255)*A/255 + dec_matrix(A%255)` to recover the original value.
We effectively split the value into `x*255 + y`.
We proceed like that for every cell of the encrypted flag and combine the results:
```pythondef solver(res, p, dec_oracle):    n = len(res)    recovered = FiniteGeneralLinearGroup(n, p)    for i in range(n):        for j in range(n):            print('recovered', i, j)            val = res[i][j]            k = val / 255            remainder = val % 255            payload = list('\0' * n * n)            payload[i * n + j] = chr(255)            result_255 = dec_oracle("".join(payload))            X = create_from_matrix(result_255, n, p)            recovered += X * k            payload[i * n + j] = chr(remainder)            result_remainder = dec_oracle("".join(payload))            X = create_from_matrix(result_remainder, n, p)            recovered += X    return recovered```
And once we run this we get `zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}`
Complete solver, including some sanity checks, [here](https://raw.githubusercontent.com/TFNS/writeups/master/2020-03-07-zer0ptsCTF/nibelung/solver.py)