# INS'hAck CTF 2018 - CustomA5/1

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}`