As crypto expert we designed our own streamcipher that combines two linear elements into a secure design. It works as follows. The secret key of NONSENSE consists of two invertible matrices K 51 , K 52 ∈ Z 64×64 To encrypt a plaintext M of l bits, our algorithm takes a 64-bit IV, generates an l-bit key stream k and computes the ciphertext C = M ⊕ k. The keystream is generated in 64-bit blocks as implemented in our open source file. To enforce a bit more the security, we decided to include IV into the secret key as well, it is incremented after every encryption query by 1, i.e. IV = (int(IV) + 1 mod 2^64 i) with limited 64 bits. You can find attached our implementation and here is our incrackable test : BXkOb8rYcnNpR3db/Ly5cD+EyBJnm8sorjHZTx/yAhUi

The encryption is a stream cypher, where the bytes are generated with this procedure

def secure_custom(K51,K52,IV,l):
    k=""
    i=0
    S_2=IV
    while i*8<l:
        if i%2 == 0:
            S_2 = K51.dot(S_2)%2
        else :
            S_2 = K52.dot(S_2)%2
        sf=""
        for j in range(0,64):
           sf += str(S_2[j,0])
        #print(S_2[1,0])
        #sf = "".join([str(j) for j in S_2])
        sfl = [sf[j:j+8] for j in range(0, len(sf), 8)]
        sfa = "".join(list(map(lambda x : chr(int(x,2)),sfl)))
        k+=sfa
        i+=1
    return k[:l]

The message is then xored with the stream. Also, a long sample is provided

test_message = "Walder Frey eventually holds a hand up to cue the musicians to cease playing, addressing Robb and claiming that he has been negligent in his duties as a host by failing to present his king with a proper wedding gift. At this moment, Roose Bolton gives Catelyn a knowing look and glances towards his arm. Her eyes follow his gaze and she sees a bit of chain mail peaking out from his sleeve. She then lifts up his sleeve which reveals the chain mail he is wearing underneath. Roose smiles ominously and Catelyn realizes that they have been led into a trap: she slaps Roose across the face and then shouts to warn Robb, but it is too late. At Walder Frey's signal, Frey approaches Talisa Stark from behind and begins to repeatedly stab her in the abdomen with a dagger, killing her unborn child instantly and causing her to quickly succumb to her wounds. The musicians hired for the wedding reveal themselves to be a group of assassins, brandishing crossbows and firing on Robb Stark and the Northern leadership gathered in the hall.."

test_cipher='P8t1d0rMgqt/f4uGAg4dpyLxMyIR+JJ4hT8DOVAMX54gBVBwuZvZc0Z5LU+Gz/PHRVoWf+8GCsXaOFdVcY7jnXcQFxjqOOnLOo79TvJywdUw1ceM58fPE3Yso97c8DaKzLzf/lXgMn9AJymOjU6239PWGYn5kHjZ/vTGvIIeP4QGk7pxiD8S00LlyRK5+YWw7i435CfQqpIum8zBJXWGvUOtDADrwXD44Fo3TMOdzJaRiLaElTSPrbpXY8d8y1oFT+bC5jgqME38wesLgcc3JNOQO17hg414WXoNtmLMFw7I8pll1zYzMz4/C8uBUZ+g2MRFjtwWffS1S8DwsFq+9vfJNDXAETUsY+lVY2Ng1yEkRSl/xRuJkkNt0A9G5hi0gkoe3cDDLV6pqdCSBKwBwz7+ywb7TbitEybS5u/qkmOdsfoRfEXHYbclbDpwmd2MQ6HQoJi7jI7tEEz4vGw66gI3YSxx0c8NHTx+mSKgxzZnp270crRy8pU4Azvq/IqiDJyqEV0TLZquJ1DcmaWD4GluUGnK9s63ttuQqsghErR/j+NnPQrg5HjkTxlNVZk0xoTTg7q0uh55HloMs7YUQFizXM1pK9k0Uldu09jslAAQSw63yu0rbqHZuUAzG1jNl8x3nPfz9GjwJDcUVSn3hEz4Edc4iu48P3CBTf/4ZADmzjywMCDdxLn4LUjOao0PbUaeWYOjVwlcaxB6zRdfPalwolwCPcu+FoTi77NuJLyr4sSnS962IhJKGM7zeHkP9obk5dps1Ps9BnjsJYDF2CyC7Qplcf/iB2uW/RnjQnyuK72gIx8tBlYz7Qh1Kn2U03FESlfxk5Y3iaL0oq2P1oHkPeAIa7IEY5YLdMLyn7BNYJiXKdnTT4oOENcmHjteLen+lANqMb3wqj7GLjy6B32Vo8cM046+AEAm0mbNZZcQvBUZtbSTue1+8hg4N3s1MIxmAVwBkJQF32beWzw+QKPgaGyOMv84K43ZsOlOZq6gYx5O9PIfzcDCfIxmlhf83TSj5GCcC18tvyIfFBHWVHdj7l2u65X0M9MRN+/2ttnHVVZ7grUon4wseQGHfV4PDiY2LOk5LKw0t+qLsxHzQ0IodSX0QJH09lXxgDsTuIdY7c7f2nb1DiDiMdCMPPmW/aL7c6EwHJZq5O2OsHeZXLHi3WlxhJ+VAI+qOze1cYspwRncYSGsDJL8YrDtTBC841ngSqAHS/OXOEs8Ui2v2vlprvRjf17Bk/JzulSEvJkrweKO7bI29AdnaEzfWB1afaaxFctqBy/IdVjRaC84ajgUdYApyteFGi767rVTgjWjKTACR49hBmj3DIzKidQOYx3M+Fz8FoLujVK4g5fmGWWvh0eoiaaU'

Then the IV is increased (to prevent us to recover the random bits, xor the encrypted flag, and solve the challenge easily)

The stream generation works as follows:

  • there are two matrices of size 64x64 where each element is a bit
  • the IV is an array of 64 bits
  • Each S_2 is generated by multiplying one of the matrices with the previous S_2 (using the IV at the first step) and keeping all the values modulo 2

For example, using a single matrix of size 2x2, and an array of size 2

1 1  x  1  = 1
1 0     0    1

So if we start with the array 1 0 we obtain the array 1 1, and so on.

Notice that, having the long sample, we can recover all the generated S_2 by xoring the plaintext with the cyphertext.
For example, the first S_2 are:

68aa19132fbea2ed
0d1af2a6677878c9
5684524e7d81b210
ea53674a706d7ff6
416b3450ccebf907
29594e3ae3ef87af
207a7b0a9c6f69ac
bb56247505e1c3fe
1271647dca4885aa

So, we have for example that
K1 * IV = 68aa19132fbea2ed
K2 * 68aa19132fbea2ed = 0d1af2a6677878c9
K1 * 0d1af2a6677878c9 = 5684524e7d81b210
and so on.

Basically this gives us a huge set of equations, that we can use to recover K1 and K2.
For example, 68aa19132fbea2ed in binary is:
0110 1000 1010 1010 0001 1001 0001 0011 0010 1111 1011 1110 1010 0010 1110 1101
and 0d1af2a6677878c9 in binary is:
0000 1101 0001 1010 1111 0010 1010 0110 0110 0111 0111 1000 0111 1000 1100 1001

By how matrix multiplication is defined, for example, we have that the first row of K2, times 68aa19132fbea2ed, mod 2, must be equal to 0 (the first bit of 0d1af2a6677878c9) and so that the sum of the elements of the first row of K2 in position 2,3,5,9,… (the bits of 68aa19132fbea2ed equal to 1) mod 2 = 0

Basically, we can take our list of S_2, convert them to binary, and generate the equations. We need to create 2*64 sets of equations (2 matrices, 64 rows each)

for i in 0..64:
  //equations for the i-th row of K2
  i-th row of K2 * first = i-th bit of second
  i-th row of K2 * third = i-th bit of fourth
...

and

for i in 0..64:
  //equations for the i-th row of K1
  i-th row of K1 * second = i-th bit of third
  i-th row of K1 * fourth = i-th bit of fifth
...

Then we can use sage to solve the set of equation and find the matrices (GF(2) means to perform all operations modulo 2):

rows=[]
A=matrix(GF(2),[[0, 0, 0, 0, 1, 1, ..... ]] )
b=vector(GF(2),[0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0])
x=A\b
rows += [x]
A=matrix(GF(2),[[0, 0, 0, 0, 1 ... ]] )
b=vector(GF(2),[1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0])
x=A\b
rows += [x]
...
print(rows)

Also, since K1 is invertible, we can recover the IV, by solving K1 * IV = first

M1=matrix(GF(2),[(1, 0, 0, 1, 1, 1, 1,... ]
b=vector(GF(2),[0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1])
IV=M1\b
print(IV)

Once we finally managed to recover the IV used in the test encryption we can add 1 to it, and the use K1, K2 and the new IV in the secure_custom function from the source script to get the new keystream.

We can now xor the keystream with the ecrypted flag to get the plaintext: INSA{cust0m_crYpt0_1s_B4d_CryPt0}