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:
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.