Ssssecret (400)

  • Challenge description: Let's share a secret...
  • Points: 400
  • Contents: message.txt
I want to share a secret,
A secret dear to me.
But the secret to keeping a secret
Is to never give out the key.

So I broke it up in little pieces
As small as they can be.
Then after that you wouldn't expect
I handed them out for free.

Follow up these pieces
Understand them to a degree
At the very root of it all
The answer you will see

AES-ECB('6eeb7683e9242ed56080e847c2f94cfc50634c29a3a50f14b31e7e3f97e34df0', key)

(1, d8877abe8c795a869b1fe28ed9a328a4)
(2, 1a1c134fc5c474899ee9d573b8895388)
(3, da143ab7a656e69a91b22414de846d0e)
(4, e4c6d40f50bd5f37d5c2f5e356a0af94)
(5, f344401d9a20a8ea1f08598434bfbf8e)

When I saw the key data, I immediately thought of some key splitting algorithm I had heard of in the past. I didn't remember its name, but after some googling I found the Shamir's Secret Sharing algorithm Wikipedia page.

To save you some time, Shamir's Secret Sharing algorithm allows you to split up a key into pieces, where a subset of the pieces allow you to reconstruct the full key. This means that if you can choose to generate 5 pieces, and from any 3 of them generate the original key again. The reason this works is because for a polynomial (a mathematical function in the format of f(x) = a, f(x) = ax + b, f(x) = ax^2 + bx + c, f(x) = a^4 + bx^3 + cx^2 + dx + e, etc.), you can only recover all the terms of the function by knowing at least N points on its graph, where N is the number of terms (in the case of f(x) = ax + b, that would be 2, ie. a and b). For example, an infinite amount of polynomials can go through 2 points, but once you add a third point, only 1 can go through.

Wikipedia has a great image that explains this visually:

3rd degree polynomials through 2 points

Image by Vlsergey on Wikipedia

By specifying eg. 5 points on on a 3rd degree polynomial, you can pick any 3 of them to recover the terms of that polynomial. Shamir's Secret Sharing algorithm is based on this idea. It creates a polynomial with terms where f(x) for x=0 is the secret we wish to share, and it then outputs the values f(x) for x being 1, 2, 3, etc. for as many pieces you want.

Knowing how Shamir's Secret Sharing works, we can go back to our input. It should be relatively trivial to recover the original key now, but reality is sadly never that simple. I tried many different online tools, but none of them produced a key that worked. I also tried the ssss-combine commandline tool, but that didn't work either. Eventually, a friend told me to use a specific commandline flag (-D) to disable some new feature, which was supposed to work.

I wrote the keys into a file called shamir in the following format:

01-d8877abe8c795a869b1fe28ed9a328a4
02-1a1c134fc5c474899ee9d573b8895388
03-da143ab7a656e69a91b22414de846d0e
04-e4c6d40f50bd5f37d5c2f5e356a0af94
05-f344401d9a20a8ea1f08598434bfbf8e

Then, I sent them to the commandline tool with cat shamir | ssss-combine -t 5 -D -x. The parameter -t 5 indicates that we require 5 pieces to reconstruct a key (using a 5th degree polynomial) and -x indicates that the output should be encoded in hex. This produced the key 5f616c65615f69616374615f6573745f. Some of you may recognize that this would result in ascii text when decoded, and you would be correct! This key would be _alea_iacta_est_, which is Latin for "the die is cast". This is a clear indication we've correctly decoded the key.

We're still not quite there yet. We now need to use this key to decode the ciphertext in the challenge. When solving this challenge I just used some online AES decryptor but it turns out CyberChef can do this too. We now have our flag, RTN{ssso_v4ry_s3cr3t}, which we can hand in for 400 points.