Gamer’s Cipher

This is the first challenge from the Cryptography section of BambooFox CTF 2021. It introduced Nimber field and do encryption using it.


We are given haskell implementation of a custom made Cipher that is based on Nim.


I spent a lot of time analyzing the multiplication defined in the code only to realize that it is actually something well known. The Nim group has well defined addition and multiplication which has additive inverse, multiplicative inverse, associative and commutative for both addition and multiplication. There are also multiplicative identity 1 and additive identity 0. Here is the wiki link, Nimber


Each element in the encrypted flag basically means

\[flag[i] = key^{i} + f(key,i)\] \[f(key,i) = \sum_{j = 0}^{n-1} m[j] \cdot key^{j} \cdot (key^{i})^{n-1-j}\]

Note: The \(+\) and \(\cdot\) are nim’s addition and multiplication respectively.

Now that’s really great! Because we have n unknowns (which is each character of the flag) and n equations. We can then find a solution using gaussian elimination.

Here’s the python code for the complete solution.

import math

# Start Nim Definition

add = lambda x,y :x^y

def nimLength(a):
    return 2 ** int(math.log2(int(math.log2(a))))

def nimSplit(a,n):
    higher = a>>n
    lower = a & (2**n - 1)
    return (higher,lower)

def mul(a,b):
    if a == 0 or b == 0:
        return 0
    if a == 1:
        return b
    if b == 1:
        return a
    k = max(nimLength(a),nimLength(b))
    p = 2**k
    p2 = 2**k + 2**(k-1)
    a1, a0 = nimSplit(a,k)
    b1, b0 = nimSplit(b,k)

    ans1 = mul(mul(a1,b1),p2)
    ans2 = add(mul(a0,b1),mul(a1,b0)) << k
    ans3 = mul(a0,b0)

    return add(add(ans1,ans2),ans3)

def pow(a,b):
    ans = 1
    while (b > 0) :
        if (b & 1):
            ans = mul(ans,a)
        a = mul(a,a)
        b = b//2
    return ans

# End Nim Definition

c = [13,1,114,230,244,145,218,78,204,36,81,48,148,35,40,50,78,40,88,43,122,39,41,149,208,208,191,68,65,61,224,140,18,239,104,210,110,119,178,27,173,253,15,237,85,192,82,74,148,15,250]
n = len(c)

keys = []

# Generate all the valid keys
for key in range(2**8):
    t = [pow(key,i) for i in range(1,n)]
    if (pow(key,n) == 1 and t.count(1) == 0):
        keys = t

# Generate the multiplicative inverse
inv = [0 for i in range(256)]
for i in range(256):
    for j in range(256):
        if (mul(i,j) == 1):
            inv[i] = j
            inv[j] = i

for key in keys:

    # Gaussian Elimination
    cc = []
    M = []
    for i in range(n):
        arr = [pow(key,(i*j+n-1-j)%n) for j in range(n)]
    for i in range(n):
        inve = inv[M[i][i]]
        cc[i] = mul(inve,cc[i])
        for k in range(n):
            M[i][k] = mul(M[i][k],inve)
        for j in range(i+1,n):
            cc[j] = add(cc[j],mul(M[j][i],cc[i]))
            for k in range(i+1,n):
                M[j][k] = add(M[j][k],mul(M[j][i],M[i][k]))
    ans = []
    anss = ""

    # Backward Substitution
    for i in range(n):
        for j in range(i):
            cc[i] = add(cc[i],mul(ans[j],M[n-1-i][n-1-j]))
        anss += chr(cc[i])
    if "flag" in anss:

flag : flag{did_you_solve_with_dft_or_lagrange_polynomial}