Rating:
# 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:
```python
def 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:
```python
def 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:
```python
def 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)
