The Russian Attack (500 + 300 pts)

Question:

The goal of this challenge is to break the original Niederreiter encryption scheme, which is based on the Generalized Reed-Solomon (GRS) codes. The parameters, public key, and the challenge ciphertext of the Niederreiter encryption scheme can be found in the file Challenge.txt.bz2. You should decrypt the challenge ciphertext, and recover the plaintext, which is of the form SharifCTF{flag}, where flag is a 16-byte hexadecimal number.

To aid you in solving this challenge, several useful functions are provided in the file Niederreiter_Implementation.gap, which is written for the GAP system. The file is heavily commented to make it easier to read (hopefully!).

Further instructions, as well as description of building blocks used in this challenge, can be found in the file The Russian Attack Description.

Write-Up:

Google for "Niederreiter" and "GRS". The first result (at the time of this writing!) is a paper by Wieschebrink.He describes an attack by Sidelnikov & Shestakov, two Russian researchers. (Thus the name "The Russian Attack"!)

The attack is implemented by the following GAP program. It expects to find the file "Challenge.txt" on the desktop.

#!/usr/bin/env gap

LoadPackage("GUAVA");;

####################################################################################

FindAlpha := function(M, q, k, n, guess)
    local b, _alpha, x, i, j;;
    _alpha := List([1..n], i->0*Z(q));;
    _alpha[2] := Z(q)^0;;
    for j in [k+1..n] do
        b := M[1][j] / M[2][j];;
        if guess - b = 0*Z(q) then
            return [];;
        fi;;
        _alpha[j] := guess / (guess - b);;
    od;;

    for i in [3..k] do
        x := M[i][k+1]*M[1][k+2]*_alpha[k+2];;

        if x = 0*Z(q) then
            return [];;
        fi;;

        x := M[1][k+1]*M[i][k+2]*_alpha[k+1] / x;;

        if x - 1 = 0*Z(q) then
            return [];;
        fi;;

        _alpha[i] := (x*_alpha[k+2] - _alpha[k+1]) / (x-1);;
    od;;

    return _alpha;;
end;;

####################################################################################

DecodeVectorAsString := function(V, L, k, q)
    local msg_num, i, s, len, msg;;

    msg_num := 0;;
    for i in [k-L+1..k] do
        msg_num := msg_num * q;;
        msg_num := msg_num + Int(V[i]);;
    od;;

    s := HexStringInt(msg_num);;
    len := Length(s) / 2;;

    msg := [1..len];;
    for i in [1..len] do
        msg[i] := CharInt(IntHexString(s{[2*i-1..2*i]}));;
    od;;

    return msg;;
end;;

####################################################################################

Sidelnikov_Shestakov_Attack := function(ctxt, M, q, k, n)
    local EchelonM, L, c, i, _alpha, poly_ring, _GRS, decoded, RightInvM, V, msg;;

    EchelonM := TriangulizedMat(M);;
    L := ctxt[1];;
    c := Codeword(ctxt[2]);;

    for i in [0..q-1] do
        _alpha := FindAlpha(EchelonM, q, k, n, i*Z(q));;
        if _alpha <> [] then
            poly_ring := PolynomialRing(GF(q), ["t"]);;
            _GRS := GeneralizedReedSolomonCode(_alpha, k, poly_ring);;
            decoded := GeneralizedReedSolomonDecoderGao(_GRS, c);;
            if decoded <> "fail" then
                break;;
            fi;;
        fi;;
    od;;

    RightInvM := TransposedMat(M)*Inverse(M*TransposedMat(M));;
    V := decoded * RightInvM;;

    msg := DecodeVectorAsString(V, L, k, q);;

    return msg;;
end;;

####################################################################################

filename := Filename(DirectoryDesktop(), "Challenge.txt");;
Read(filename);;

# Convert to GAP notation
M := M*Z(q);;
ctxt[2] := ctxt[2]*Z(q);;

Print(Sidelnikov_Shestakov_Attack(ctxt, M, q, k, n));;

Run the program. After a few seconds, it outputs the plaintext: SharifCTF{291695110d56d9731697921686fbe9b1}.

Source Code

Sidelnikov_Shestakov_Attack.gap.